memhash_tsip.mx raw

   1  //go:build runtime_memhash_tsip
   2  
   3  // This is the tsip hash developed by Damian Gryski, based on ideas from SipHash.
   4  // It is slower than leveldb's hash, but should be "stronger".
   5  
   6  // https://en.wikipedia.org/wiki/SipHash
   7  // https://github.com/veorq/SipHash
   8  // https://github.com/dgryski/tsip
   9  
  10  package runtime
  11  
  12  import (
  13  	"internal/binary"
  14  	"math/bits"
  15  	"unsafe"
  16  )
  17  
  18  type sip struct {
  19  	v0, v1 uint64
  20  }
  21  
  22  func (s *sip) round() {
  23  	s.v0 += s.v1
  24  	s.v1 = bits.RotateLeft64(s.v1, 13) ^ s.v0
  25  	s.v0 = bits.RotateLeft64(s.v0, 35) + s.v1
  26  	s.v1 = bits.RotateLeft64(s.v1, 17) ^ s.v0
  27  	s.v0 = bits.RotateLeft64(s.v0, 21)
  28  }
  29  
  30  func hash64(ptr unsafe.Pointer, n uintptr, seed uintptr) uint64 {
  31  	p := unsafe.Slice((*byte)(ptr), n)
  32  
  33  	k0 := uint64(seed)
  34  	k1 := uint64(0)
  35  
  36  	s := sip{
  37  		v0: k0 ^ 0x736f6d6570736575,
  38  		v1: k1 ^ 0x646f72616e646f6d,
  39  	}
  40  
  41  	b := uint64(len(p)) << 56
  42  
  43  	for len(p) >= 8 {
  44  		m := binary.LittleEndian.Uint64(p[:8])
  45  		s.v1 ^= m
  46  		s.round()
  47  		s.v0 ^= m
  48  		p = p[8:]
  49  	}
  50  
  51  	switch len(p) {
  52  	case 7:
  53  		b |= uint64(p[6]) << 48
  54  		fallthrough
  55  	case 6:
  56  		b |= uint64(p[5]) << 40
  57  		fallthrough
  58  	case 5:
  59  		b |= uint64(p[4]) << 32
  60  		fallthrough
  61  	case 4:
  62  		b |= uint64(p[3]) << 24
  63  		fallthrough
  64  	case 3:
  65  		b |= uint64(p[2]) << 16
  66  		fallthrough
  67  	case 2:
  68  		b |= uint64(p[1]) << 8
  69  		fallthrough
  70  	case 1:
  71  		b |= uint64(p[0])
  72  	}
  73  
  74  	// last block
  75  	s.v1 ^= b
  76  	s.round()
  77  	s.v0 ^= b
  78  
  79  	// finalization
  80  	s.v1 ^= 0xff
  81  	s.round()
  82  	s.v1 = bits.RotateLeft64(s.v1, 32)
  83  	s.round()
  84  	s.v1 = bits.RotateLeft64(s.v1, 32)
  85  
  86  	return s.v0 ^ s.v1
  87  }
  88  
  89  type sip32 struct {
  90  	v0, v1 uint32
  91  }
  92  
  93  func (s *sip32) round() {
  94  	s.v0 += s.v1
  95  	s.v1 = bits.RotateLeft32(s.v1, 5) ^ s.v0
  96  	s.v0 = bits.RotateLeft32(s.v0, 8) + s.v1
  97  	s.v1 = bits.RotateLeft32(s.v1, 13) ^ s.v0
  98  	s.v0 = bits.RotateLeft32(s.v0, 7)
  99  }
 100  
 101  func hash32(ptr unsafe.Pointer, n uintptr, seed uintptr) uint32 {
 102  	p := unsafe.Slice((*byte)(ptr), n)
 103  
 104  	k0 := uint32(seed)
 105  	k1 := uint32(seed >> 32)
 106  
 107  	s := sip32{
 108  		v0: k0 ^ 0x74656462,
 109  		v1: k1 ^ 0x6c796765,
 110  	}
 111  	b := uint32(len(p)) << 24
 112  
 113  	for len(p) >= 4 {
 114  		m := binary.LittleEndian.Uint32(p[:4])
 115  		s.v1 ^= m
 116  		s.round()
 117  		s.v0 ^= m
 118  		p = p[4:]
 119  	}
 120  
 121  	switch len(p) {
 122  	case 3:
 123  		b |= uint32(p[2]) << 16
 124  		fallthrough
 125  	case 2:
 126  		b |= uint32(p[1]) << 8
 127  		fallthrough
 128  	case 1:
 129  		b |= uint32(p[0])
 130  	}
 131  
 132  	// last block
 133  	s.v1 ^= b
 134  	s.round()
 135  	s.v0 ^= b
 136  
 137  	// finalization
 138  	s.v1 ^= 0xff
 139  	s.round()
 140  	s.v1 = bits.RotateLeft32(s.v1, 16)
 141  	s.round()
 142  	s.v1 = bits.RotateLeft32(s.v1, 16)
 143  
 144  	return s.v0 ^ s.v1
 145  }
 146