jeudi 20 juillet 2017

How to create a custom Murmur Avalanche Mixer?

I'm trying to use an Avalanche mixer to hash integer coordinates. I've been using Murmur3's 32bit and 64bit avalanche mixers to do so (and not the actual total hash function). For my application the entire hash function is not needed, only the Avalanche Mixer seen here:

uint32_t murmurmix32( uint32_t h )
{
  h ^= h >> 16;
  h *= 0x85ebca6b;
  h ^= h >> 13;
  h *= 0xc2b2ae35;
  h ^= h >> 16;

  return h;
}


uint64_t murmurmix64( uint64_t h )
{
  h ^= h >> 33;
  h *= 0xff51afd7ed558ccdULL;
  h ^= h >> 33;
  h *= 0xc4ceb9fe1a85ec53ULL;
  h ^= h >> 33;

  return h;
}

These appear fast on my machine, I take two uint32_ts and mix them into these functions to produce avalanched results, this produces a psuedorandom distribution to my liking.

I want to introduce more coordinates to this system (ie z and w), so I want to use larger avalanche mixers to hash my coordinates. I believe for my puroposes the max value I want to see come out of the function itself is uint64_t, collisions themselves are not a problem, but the randomness of the results are.

It does not appear that murmur3 has a larger avalanche mixer than 64. I've looked at this website and this one to get a few clues on some alternative avalanche hashes:

The quality of these avalanches seem to be good enough for my application but I'm particularly interested in City hash's murmur inspirations.

In CityHash, they have a "murmur inspired" mixer:

uint64 Hash128to64(const uint64_t& x_high, const uint64_t& x_low) {
  // Murmur-inspired hashing.
  const uint64 kMul = 0x9ddfea08eb382d69ULL;
  uint64 a = (x_low ^ x_high) * kMul;
  a ^= (a >> 47);
  uint64 b = (x_high ^ a) * kMul;
  b ^= (b >> 47);
  b *= kMul;
  return b;
}

This seems quite fast for two 64 bit numbers. I'm confused as to how they derived their own "inspired" hash from Murmur. How would one go about creating their own 2^n bit murmur avalanche mixer?




Aucun commentaire:

Enregistrer un commentaire