murmur32.go 2.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144
  1. package murmur3
  2. // https://github.com/spaolacci/murmur3/blob/master/murmur32.go
  3. import (
  4. "hash"
  5. "math/bits"
  6. "unsafe"
  7. )
  8. // Make sure interfaces are correctly implemented.
  9. var (
  10. _ hash.Hash32 = new(digest32)
  11. _ bmixer = new(digest32)
  12. )
  13. const (
  14. c1_32 uint32 = 0xcc9e2d51
  15. c2_32 uint32 = 0x1b873593
  16. )
  17. // digest32 represents a partial evaluation of a 32 bites hash.
  18. type digest32 struct {
  19. digest
  20. h1 uint32 // Unfinalized running hash.
  21. }
  22. // New32 returns new 32-bit hasher
  23. func New32() hash.Hash32 { return New32WithSeed(0) }
  24. // New32WithSeed returns new 32-bit hasher set with explicit seed value
  25. func New32WithSeed(seed uint32) hash.Hash32 {
  26. d := new(digest32)
  27. d.seed = seed
  28. d.bmixer = d
  29. d.Reset()
  30. return d
  31. }
  32. func (d *digest32) Size() int { return 4 }
  33. func (d *digest32) reset() { d.h1 = d.seed }
  34. func (d *digest32) Sum(b []byte) []byte {
  35. h := d.Sum32()
  36. return append(b, byte(h>>24), byte(h>>16), byte(h>>8), byte(h))
  37. }
  38. // Digest as many blocks as possible.
  39. func (d *digest32) bmix(p []byte) (tail []byte) {
  40. h1 := d.h1
  41. nblocks := len(p) / 4
  42. for i := 0; i < nblocks; i++ {
  43. k1 := *(*uint32)(unsafe.Pointer(&p[i*4]))
  44. k1 *= c1_32
  45. k1 = bits.RotateLeft32(k1, 15)
  46. k1 *= c2_32
  47. h1 ^= k1
  48. h1 = bits.RotateLeft32(h1, 13)
  49. h1 = h1*4 + h1 + 0xe6546b64
  50. }
  51. d.h1 = h1
  52. return p[nblocks*d.Size():]
  53. }
  54. func (d *digest32) Sum32() (h1 uint32) {
  55. h1 = d.h1
  56. var k1 uint32
  57. switch len(d.tail) & 3 {
  58. case 3:
  59. k1 ^= uint32(d.tail[2]) << 16
  60. fallthrough
  61. case 2:
  62. k1 ^= uint32(d.tail[1]) << 8
  63. fallthrough
  64. case 1:
  65. k1 ^= uint32(d.tail[0])
  66. k1 *= c1_32
  67. k1 = bits.RotateLeft32(k1, 15)
  68. k1 *= c2_32
  69. h1 ^= k1
  70. }
  71. h1 ^= uint32(d.clen)
  72. h1 ^= h1 >> 16
  73. h1 *= 0x85ebca6b
  74. h1 ^= h1 >> 13
  75. h1 *= 0xc2b2ae35
  76. h1 ^= h1 >> 16
  77. return h1
  78. }
  79. func Sum32(data []byte) uint32 { return Sum32WithSeed(data, 0) }
  80. func Sum32WithSeed(data []byte, seed uint32) uint32 {
  81. h1 := seed
  82. nblocks := len(data) / 4
  83. for i := 0; i < nblocks; i++ {
  84. k1 := *(*uint32)(unsafe.Pointer(&data[i*4]))
  85. k1 *= c1_32
  86. k1 = bits.RotateLeft32(k1, 15)
  87. k1 *= c2_32
  88. h1 ^= k1
  89. h1 = bits.RotateLeft32(h1, 13)
  90. h1 = h1*4 + h1 + 0xe6546b64
  91. }
  92. tail := data[nblocks*4:]
  93. var k1 uint32
  94. switch len(tail) & 3 {
  95. case 3:
  96. k1 ^= uint32(tail[2]) << 16
  97. fallthrough
  98. case 2:
  99. k1 ^= uint32(tail[1]) << 8
  100. fallthrough
  101. case 1:
  102. k1 ^= uint32(tail[0])
  103. k1 *= c1_32
  104. k1 = bits.RotateLeft32(k1, 15)
  105. k1 *= c2_32
  106. h1 ^= k1
  107. }
  108. h1 ^= uint32(len(data))
  109. h1 ^= h1 >> 16
  110. h1 *= 0x85ebca6b
  111. h1 ^= h1 >> 13
  112. h1 *= 0xc2b2ae35
  113. h1 ^= h1 >> 16
  114. return h1
  115. }