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 armbe m68k mips mipsle nios2 ppc s390 sh shbe sparc 10 11package runtime 12 13import "unsafe" 14 15// For gccgo, use go:linkname to export compiler-called functions. 16// 17//go:linkname memhash 18 19const ( 20 // Constants for multiplication: four random odd 32-bit numbers. 21 m1 = 3168982561 22 m2 = 3339683297 23 m3 = 832293441 24 m4 = 2336365089 25) 26 27func memhash(p unsafe.Pointer, seed, s uintptr) uintptr { 28 if GOARCH == "386" && GOOS != "nacl" && useAeshash { 29 return aeshash(p, seed, s) 30 } 31 h := uint32(seed + s*hashkey[0]) 32tail: 33 switch { 34 case s == 0: 35 case s < 4: 36 h ^= uint32(*(*byte)(p)) 37 h ^= uint32(*(*byte)(add(p, s>>1))) << 8 38 h ^= uint32(*(*byte)(add(p, s-1))) << 16 39 h = rotl_15(h*m1) * m2 40 case s == 4: 41 h ^= readUnaligned32(p) 42 h = rotl_15(h*m1) * m2 43 case s <= 8: 44 h ^= readUnaligned32(p) 45 h = rotl_15(h*m1) * m2 46 h ^= readUnaligned32(add(p, s-4)) 47 h = rotl_15(h*m1) * m2 48 case s <= 16: 49 h ^= readUnaligned32(p) 50 h = rotl_15(h*m1) * m2 51 h ^= readUnaligned32(add(p, 4)) 52 h = rotl_15(h*m1) * m2 53 h ^= readUnaligned32(add(p, s-8)) 54 h = rotl_15(h*m1) * m2 55 h ^= readUnaligned32(add(p, s-4)) 56 h = rotl_15(h*m1) * m2 57 default: 58 v1 := h 59 v2 := uint32(seed * hashkey[1]) 60 v3 := uint32(seed * hashkey[2]) 61 v4 := uint32(seed * hashkey[3]) 62 for s >= 16 { 63 v1 ^= readUnaligned32(p) 64 v1 = rotl_15(v1*m1) * m2 65 p = add(p, 4) 66 v2 ^= readUnaligned32(p) 67 v2 = rotl_15(v2*m2) * m3 68 p = add(p, 4) 69 v3 ^= readUnaligned32(p) 70 v3 = rotl_15(v3*m3) * m4 71 p = add(p, 4) 72 v4 ^= readUnaligned32(p) 73 v4 = rotl_15(v4*m4) * m1 74 p = add(p, 4) 75 s -= 16 76 } 77 h = v1 ^ v2 ^ v3 ^ v4 78 goto tail 79 } 80 h ^= h >> 17 81 h *= m3 82 h ^= h >> 13 83 h *= m4 84 h ^= h >> 16 85 return uintptr(h) 86} 87 88func memhash32(p unsafe.Pointer, seed uintptr) uintptr { 89 h := uint32(seed + 4*hashkey[0]) 90 h ^= readUnaligned32(p) 91 h = rotl_15(h*m1) * m2 92 h ^= h >> 17 93 h *= m3 94 h ^= h >> 13 95 h *= m4 96 h ^= h >> 16 97 return uintptr(h) 98} 99 100func memhash64(p unsafe.Pointer, seed uintptr) uintptr { 101 h := uint32(seed + 8*hashkey[0]) 102 h ^= readUnaligned32(p) 103 h = rotl_15(h*m1) * m2 104 h ^= readUnaligned32(add(p, 4)) 105 h = rotl_15(h*m1) * m2 106 h ^= h >> 17 107 h *= m3 108 h ^= h >> 13 109 h *= m4 110 h ^= h >> 16 111 return uintptr(h) 112} 113 114// Note: in order to get the compiler to issue rotl instructions, we 115// need to constant fold the shift amount by hand. 116// TODO: convince the compiler to issue rotl instructions after inlining. 117func rotl_15(x uint32) uint32 { 118 return (x << 15) | (x >> (32 - 15)) 119} 120