memhash_leveldb.mx raw

   1  //go:build runtime_memhash_leveldb || (wasip1 && !runtime_memhash_fnv && !runtime_memhash_tsip)
   2  
   3  // This is the default for WASI, but can also be used on other targets with the
   4  // right build tag.
   5  
   6  // This is the hash function from Google's leveldb key-value storage system. It
   7  // processes 4 bytes at a time making it faster than the FNV hash for buffer
   8  // lengths > 16 bytes.
   9  
  10  // https://github.com/google/leveldb
  11  // https://en.wikipedia.org/wiki/LevelDB
  12  
  13  package runtime
  14  
  15  import (
  16  	"unsafe"
  17  )
  18  
  19  // leveldb hash
  20  func hash32(ptr unsafe.Pointer, n, seed uintptr) uint32 {
  21  
  22  	const (
  23  		lseed = 0xbc9f1d34
  24  		m     = 0xc6a4a793
  25  	)
  26  
  27  	b := unsafe.Slice((*byte)(ptr), n)
  28  
  29  	h := uint32(lseed^seed) ^ uint32(uint(len(b))*uint(m))
  30  
  31  	for ; len(b) >= 4; b = b[4:] {
  32  		h += uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
  33  		h *= m
  34  		h ^= h >> 16
  35  	}
  36  	switch len(b) {
  37  	case 3:
  38  		h += uint32(b[2]) << 16
  39  		fallthrough
  40  	case 2:
  41  		h += uint32(b[1]) << 8
  42  		fallthrough
  43  	case 1:
  44  		h += uint32(b[0])
  45  		h *= m
  46  		h ^= h >> 24
  47  	}
  48  
  49  	return h
  50  }
  51  
  52  // hash64finalizer is a 64-bit integer mixing function from
  53  // https://web.archive.org/web/20120720045250/http://www.cris.com/~Ttwang/tech/inthash.htm
  54  func hash64finalizer(key uint64) uint64 {
  55  	key = ^key + (key << 21) // key = (key << 21) - key - 1;
  56  	key = key ^ (key >> 24)
  57  	key = (key + (key << 3)) + (key << 8) // key * 265
  58  	key = key ^ (key >> 14)
  59  	key = (key + (key << 2)) + (key << 4) // key * 21
  60  	key = key ^ (key >> 28)
  61  	key = key + (key << 31)
  62  	return key
  63  }
  64  
  65  // hash64 turns hash32 into a 64-bit hash, by use hash64finalizer to
  66  // mix the result of hash32 function combined with an xorshifted version of
  67  // the seed.
  68  func hash64(ptr unsafe.Pointer, n, seed uintptr) uint64 {
  69  	h32 := hash32(ptr, n, seed)
  70  	return hash64finalizer((uint64(h32^xorshift32(uint32(seed))) << 32) | uint64(h32))
  71  }
  72