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