Cryptographic Hashing without Double limitation (Pull Request as issue)

[Reptorian1125]

I decided to implement a hashing method that bypass the inherent limitation of double-type for G'MIC by doing the following method: Treat double as unsigned long long, then do math operations within unsigned, then return the double modulo 16777216. Intended to work with G'MIC hash table irrespective of how big or small the number is. I'm doing a pull request this way because for some reason I see 14000+ difference within clone of mine, so I don't know how to fix that. Also, I don't really know what I'm doing, but so far tests do work, but I'll let you decide on the changes, and doing two seed leads to beautiful randomness.

            if (!std::strncmp(ss, "hash(", 5)) { // hash(value_or_vector [,seed1 [,seed2]])
                _cimg_mp_op("Function 'hash()'");
                s0 = ss + 5;
                s1 = s0;

                // First argument: the value or vector to hash.
                s1 = s0; while (s1 < se1 && (*s1 != ',' || level[s1 - expr._data] != clevel1)) ++s1;
                arg2 = compile(s0, s1, depth1, 0, block_flags);

                // Optional trailing seed1, seed2 (both scalars, both default to 0 if omitted).
                arg3 = ~0U; arg4 = ~0U;
                if (s1 < se1) {
                    s0 = ++s1; while (s0 < se1 && (*s0 != ',' || level[s0 - expr._data] != clevel1)) ++s0;
                    arg3 = compile(s1, s0, depth1, 0, block_flags);
                    _cimg_mp_check_type(arg3, 2, 1, 0);
                    if (s0 < se1) {
                        s1 = ++s0; while (s1 < se1 && (*s1 != ',' || level[s1 - expr._data] != clevel1)) ++s1;
                        arg4 = compile(s0, s1, depth1, 0, block_flags);
                        _cimg_mp_check_type(arg4, 3, 1, 0);
                    }
                }

                const unsigned int seed1 = arg3 == ~0U ? const_scalar(0) : arg3;
                const unsigned int seed2 = arg4 == ~0U ? const_scalar(0) : arg4;

                // Constant-folding: fold when the data (element-wise if a vector) and both seeds are constant.
                bool arg2_const = is_const_scalar(arg2);
                if (is_vector(arg2)) {
                    arg2_const = true;
                    for (unsigned int i = 1; i <= size(arg2) && arg2_const; ++i) arg2_const &= is_const_scalar(arg2 + i);
                }
                if (arg2_const && is_const_scalar(seed1) && is_const_scalar(seed2)) {
                    CImg<ulongT>::vector((ulongT)mp_hash, 0, arg2, size(arg2), seed1, seed2).move_to(opcode);
                    _cimg_mp_const_scalar(mp_hash(*this));
                }

                _cimg_mp_scalar4(hash, arg2, size(arg2), seed1, seed2);
            }

      static double mp_hash(_cimg_math_parser& mp) {
          unsigned int seed1_bits, seed2_bits, h, mult;
          unsigned long long bits64;

          std::memcpy(&bits64, &_mp_arg(4), sizeof(bits64)); // seed1 reg = opcode[4]
          seed1_bits = (unsigned int)(bits64 ^ (bits64 >> 32));
          std::memcpy(&bits64, &_mp_arg(5), sizeof(bits64)); // seed2 reg = opcode[5]
          seed2_bits = (unsigned int)(bits64 ^ (bits64 >> 32));

          mult = seed2_bits | 1U;
          h = 2166136261U ^ seed1_bits;

          const ulongT siz = (ulongT)mp.opcode[3]; // 0 = scalar, else vector length
          const double
              * const ptrb = siz ? &_mp_arg(2) + 1 : &_mp_arg(2), // vector data starts past the NaN sentinel
              * const ptre = ptrb + (siz ? siz : 1),
              * ptr = ptrb;

          while (ptr < ptre) {
              std::memcpy(&bits64, ptr++, sizeof(bits64));
              h = h * mult + (unsigned int)(bits64 & 0xFFFFFFFFU); // low 32 bits
              h = h * mult + (unsigned int)(bits64 >> 32);         // high 32 bits
          }

          // Avalanche finalizer (Murmur3 fmix32).
          h ^= h >> 16; h *= 0x85ebca6bU;
          h ^= h >> 13; h *= 0xc2b2ae35U;
          h ^= h >> 16;

          return (double)(h & 0xFFFFFFU);
      }

[Reptorian1125]

Also, the Avalanche part, I don't think it should be part of the code, but I am not too sure about that.

[Reptorian1125]

I have updated the code, slightly faster, closer to CImg convention.

[dtschump]

Hello. I think this is a too much specific feature to be included in the math parser of CImg.
There are already alternative for computing integer hashes (via math parser macro functions) so I don't really see the benefit of adding that piece of code. I understand this fullfills one of your need, but I can't add small code snippets like this each time a user needs one very-specific feature.

[Reptorian1125]

What would you suggest as a working code that doesn't have issues with really large or small double? I tried different approach just to run into only even buckets filled or just one bucket filled (though in average cases, it works)?

[dtschump]

This G'MIC code, for instance does not fill only even buckets:

foo :
  sp colorful,8192 b 10
  N:=2^24 # Number of buckets (large)
  100%,100%,100%,1,": # Compute hashes
    H = 1; repeat (s#0,c,i = j(#0,0,0,0,c); ((H*=2654435761)+=2246822519*(isnan(i)?0:i))%=$N); int(H)"

  # Check histogram of buckets.
  +histogram. $N,0,{$N-1}

[dtschump]

I could add that using the double datatype already allows to accurately store integers from -2^53 to 2^53, which is... well, not that bad!

[Reptorian1125]

Yeah, I tested it. I believe the limit is actually close to 4M. (1<<53)/2654435761 would be the breaking point.

foo :
  a=40008861 #Bucket breaking
  16777216,1,1,3,v($a,$a+100)
  N:=2^13 # Number of buckets (large)
  100%,100%,100%,1,": # Compute hashes
    H = 1; repeat (s#0,c,i = j(#0,0,0,0,c); ((H*=2654435761)+=2246822519*(isnan(i)?0:i))%=$N); int(H)"

  # Check histogram of buckets.
  +histogram. $N,0,{$N-1}   

[Reptorian1125]

Okay, I figured it out. I did used your hash number, but allowed for seed. However, what I had to do is use a % factor before doing the multiplication part to avoid numbers going over the safe double limit 1<<53. That way, it works. It's not ideal and requires more lines, but it works.