murmurhash3.go 1.7 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889
  1. /*
  2. * Public Domain Software
  3. *
  4. * I (Matthias Ladkau) am the author of the source code in this file.
  5. * I have placed the source code in this file in the public domain.
  6. *
  7. * For further information see: http://creativecommons.org/publicdomain/zero/1.0/
  8. */
  9. package bitutil
  10. import "fmt"
  11. const (
  12. c1 uint32 = 0xcc9e2d51
  13. c2 uint32 = 0x1b873593
  14. )
  15. /*
  16. MurMurHashData hashes a given array of bytes. This is an implementation
  17. of Austin Appleby's MurmurHash3 (32bit) function.
  18. Reference implementation: http://code.google.com/p/smhasher/wiki/MurmurHash3
  19. */
  20. func MurMurHashData(data []byte, offset int, size int, seed int) (uint32, error) {
  21. // Check parameters
  22. if offset < 0 || size < 0 {
  23. return 0, fmt.Errorf("Invalid data boundaries; offset: %v; size: %v",
  24. offset, size)
  25. }
  26. h1 := uint32(seed)
  27. end := offset + size
  28. end -= end % 4
  29. // Check length of available data
  30. if len(data) <= end {
  31. return 0, fmt.Errorf("Data out of bounds; set boundary: %v; data length: %v",
  32. end, len(data))
  33. }
  34. for i := offset; i < end; i += 4 {
  35. var k1 = uint32(data[i])
  36. k1 |= uint32(data[i+1]) << 8
  37. k1 |= uint32(data[i+2]) << 16
  38. k1 |= uint32(data[i+3]) << 24
  39. k1 *= c1
  40. k1 = (k1 << 15) | (k1 >> 17) // ROTL32(k1,15);
  41. k1 *= c2
  42. h1 ^= k1
  43. h1 = (h1 << 13) | (h1 >> 19) // ROTL32(h1,13);
  44. h1 = h1*5 + 0xe6546b64
  45. }
  46. // Tail
  47. var k1 uint32
  48. switch size & 3 {
  49. case 3:
  50. k1 = uint32(data[end+2]) << 16
  51. fallthrough
  52. case 2:
  53. k1 |= uint32(data[end+1]) << 8
  54. fallthrough
  55. case 1:
  56. k1 |= uint32(data[end])
  57. k1 *= c1
  58. k1 = (k1 << 15) | (k1 >> 17) // ROTL32(k1,15);
  59. k1 *= c2
  60. h1 ^= k1
  61. }
  62. h1 ^= uint32(size)
  63. h1 ^= h1 >> 16
  64. h1 *= 0x85ebca6b
  65. h1 ^= h1 >> 13
  66. h1 *= 0xc2b2ae35
  67. h1 ^= h1 >> 16
  68. return h1, nil
  69. }