vendor/github.com/gxed/hashland/murmur3/murmur32.go

   1 package murmur3
   2
   3 // http://code.google.com/p/guava-libraries/source/browse/guava/src/com/google/common/hash/Murmur3_32HashFunction.java
   4
   5 import (
   6         "hash"
   7         "unsafe"
   8 )
   9
  10 // Make sure interfaces are correctly implemented.
  11 var (
  12         _ hash.Hash   = new(digest32)
  13         _ hash.Hash32 = new(digest32)
  14 )
  15
  16 const (
  17         c1_32 uint32 = 0xcc9e2d51
  18         c2_32 uint32 = 0x1b873593
  19 )
  20
  21 // digest32 represents a partial evaluation of a 32 bites hash.
  22 type digest32 struct {
  23         digest
  24         h1 uint32 // Unfinalized running hash.
  25 }
  26
  27 func New32() hash.Hash32 {
  28         d := new(digest32)
  29         d.bmixer = d
  30         d.Reset()
  31         return d
  32 }
  33
  34 func (d *digest32) Size() int { return 4 }
  35
  36 func (d *digest32) reset() { d.h1 = 0 }
  37
  38 func (d *digest32) Sum(b []byte) []byte {
  39         h := d.h1
  40         return append(b, byte(h>>24), byte(h>>16), byte(h>>8), byte(h))
  41 }
  42
  43 // Digest as many blocks as possible.
  44 func (d *digest32) bmix(p []byte) (tail []byte) {
  45         h1 := d.h1
  46
  47         nblocks := len(p) / 4
  48         for i := 0; i < nblocks; i++ {
  49                 k1 := *(*uint32)(unsafe.Pointer(&p[i*4]))
  50
  51                 k1 *= c1_32
  52                 k1 = (k1 << 15) | (k1 >> 17) // rotl32(k1, 15)
  53                 k1 *= c2_32
  54
  55                 h1 ^= k1
  56                 h1 = (h1 << 13) | (h1 >> 19) // rotl32(h1, 13)
  57                 h1 = h1*5 + 0xe6546b64
  58         }
  59         d.h1 = h1
  60         return p[nblocks*d.Size():]
  61 }
  62
  63 func (d *digest32) Sum32() (h1 uint32) {
  64
  65         h1 = d.h1
  66
  67         var k1 uint32
  68         switch len(d.tail) & 3 {
  69         case 3:
  70                 k1 ^= uint32(d.tail[2]) << 16
  71                 fallthrough
  72         case 2:
  73                 k1 ^= uint32(d.tail[1]) << 8
  74                 fallthrough
  75         case 1:
  76                 k1 ^= uint32(d.tail[0])
  77                 k1 *= c1_32
  78                 k1 = (k1 << 15) | (k1 >> 17) // rotl32(k1, 15)
  79                 k1 *= c2_32
  80                 h1 ^= k1
  81         }
  82
  83         h1 ^= uint32(d.clen)
  84
  85         h1 ^= h1 >> 16
  86         h1 *= 0x85ebca6b
  87         h1 ^= h1 >> 13
  88         h1 *= 0xc2b2ae35
  89         h1 ^= h1 >> 16
  90
  91         return h1
  92 }
  93
  94 /*
  95 func rotl32(x uint32, r byte) uint32 {
  96         return (x << r) | (x >> (32 - r))
  97 }
  98 */
  99
 100 // Sum32 returns the MurmurHash3 sum of data. It is equivalent to the
 101 // following sequence (without the extra burden and the extra allocation):
 102 //     hasher := New32()
 103 //     hasher.Write(data)
 104 //     return hasher.Sum32()
 105 func Sum32(data []byte) uint32 {
 106
 107         var h1 uint32 = 0
 108
 109         nblocks := len(data) / 4
 110         var p uintptr
 111         if len(data) > 0 {
 112                 p = uintptr(unsafe.Pointer(&data[0]))
 113         }
 114         p1 := p + uintptr(4*nblocks)
 115         for ; p < p1; p += 4 {
 116                 k1 := *(*uint32)(unsafe.Pointer(p))
 117
 118                 k1 *= c1_32
 119                 k1 = (k1 << 15) | (k1 >> 17) // rotl32(k1, 15)
 120                 k1 *= c2_32
 121
 122                 h1 ^= k1
 123                 h1 = (h1 << 13) | (h1 >> 19) // rotl32(h1, 13)
 124                 h1 = h1*5 + 0xe6546b64
 125         }
 126
 127         tail := data[nblocks*4:]
 128
 129         var k1 uint32
 130         switch len(tail) & 3 {
 131         case 3:
 132                 k1 ^= uint32(tail[2]) << 16
 133                 fallthrough
 134         case 2:
 135                 k1 ^= uint32(tail[1]) << 8
 136                 fallthrough
 137         case 1:
 138                 k1 ^= uint32(tail[0])
 139                 k1 *= c1_32
 140                 k1 = (k1 << 15) | (k1 >> 17) // rotl32(k1, 15)
 141                 k1 *= c2_32
 142                 h1 ^= k1
 143         }
 144
 145         h1 ^= uint32(len(data))
 146
 147         h1 ^= h1 >> 16
 148         h1 *= 0x85ebca6b
 149         h1 ^= h1 >> 13
 150         h1 *= 0xc2b2ae35
 151         h1 ^= h1 >> 16
 152
 153         return h1
 154 }