1 // Copyright 2014 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 // Hashing algorithm inspired by 6 // xxhash: https://code.google.com/p/xxhash/ 7 // cityhash: https://code.google.com/p/cityhash/ 8 9 // +build 386 arm mips mipsle 10 11 package runtime 12 13 import "unsafe" 14 15 const ( 16 // Constants for multiplication: four random odd 32-bit numbers. 17 m1 = 3168982561 18 m2 = 3339683297 19 m3 = 832293441 20 m4 = 2336365089 21 ) 22 23 func memhash(p unsafe.Pointer, seed, s uintptr) uintptr { 24 if GOARCH == "386" && GOOS != "nacl" && useAeshash { 25 return aeshash(p, seed, s) 26 } 27 h := uint32(seed + s*hashkey[0]) 28 tail: 29 switch { 30 case s == 0: 31 case s < 4: 32 h ^= uint32(*(*byte)(p)) 33 h ^= uint32(*(*byte)(add(p, s>>1))) << 8 34 h ^= uint32(*(*byte)(add(p, s-1))) << 16 35 h = rotl_15(h*m1) * m2 36 case s == 4: 37 h ^= readUnaligned32(p) 38 h = rotl_15(h*m1) * m2 39 case s <= 8: 40 h ^= readUnaligned32(p) 41 h = rotl_15(h*m1) * m2 42 h ^= readUnaligned32(add(p, s-4)) 43 h = rotl_15(h*m1) * m2 44 case s <= 16: 45 h ^= readUnaligned32(p) 46 h = rotl_15(h*m1) * m2 47 h ^= readUnaligned32(add(p, 4)) 48 h = rotl_15(h*m1) * m2 49 h ^= readUnaligned32(add(p, s-8)) 50 h = rotl_15(h*m1) * m2 51 h ^= readUnaligned32(add(p, s-4)) 52 h = rotl_15(h*m1) * m2 53 default: 54 v1 := h 55 v2 := uint32(seed * hashkey[1]) 56 v3 := uint32(seed * hashkey[2]) 57 v4 := uint32(seed * hashkey[3]) 58 for s >= 16 { 59 v1 ^= readUnaligned32(p) 60 v1 = rotl_15(v1*m1) * m2 61 p = add(p, 4) 62 v2 ^= readUnaligned32(p) 63 v2 = rotl_15(v2*m2) * m3 64 p = add(p, 4) 65 v3 ^= readUnaligned32(p) 66 v3 = rotl_15(v3*m3) * m4 67 p = add(p, 4) 68 v4 ^= readUnaligned32(p) 69 v4 = rotl_15(v4*m4) * m1 70 p = add(p, 4) 71 s -= 16 72 } 73 h = v1 ^ v2 ^ v3 ^ v4 74 goto tail 75 } 76 h ^= h >> 17 77 h *= m3 78 h ^= h >> 13 79 h *= m4 80 h ^= h >> 16 81 return uintptr(h) 82 } 83 84 func memhash32(p unsafe.Pointer, seed uintptr) uintptr { 85 h := uint32(seed + 4*hashkey[0]) 86 h ^= readUnaligned32(p) 87 h = rotl_15(h*m1) * m2 88 h ^= h >> 17 89 h *= m3 90 h ^= h >> 13 91 h *= m4 92 h ^= h >> 16 93 return uintptr(h) 94 } 95 96 func memhash64(p unsafe.Pointer, seed uintptr) uintptr { 97 h := uint32(seed + 8*hashkey[0]) 98 h ^= readUnaligned32(p) 99 h = rotl_15(h*m1) * m2 100 h ^= readUnaligned32(add(p, 4)) 101 h = rotl_15(h*m1) * m2 102 h ^= h >> 17 103 h *= m3 104 h ^= h >> 13 105 h *= m4 106 h ^= h >> 16 107 return uintptr(h) 108 } 109 110 // Note: in order to get the compiler to issue rotl instructions, we 111 // need to constant fold the shift amount by hand. 112 // TODO: convince the compiler to issue rotl instructions after inlining. 113 func rotl_15(x uint32) uint32 { 114 return (x << 15) | (x >> (32 - 15)) 115 } 116
