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.
5 // Hashing algorithm inspired by
6 // xxhash: https://code.google.com/p/xxhash/
7 // cityhash: https://code.google.com/p/cityhash/
9 // +build 386 arm armbe m68k mipso32 mipsn32 mips mipsle ppc s390 sparc
15 // For gccgo, use go:linkname to rename compiler-called functions to
16 // themselves, so that the compiler will export them.
18 //go:linkname memhash runtime.memhash
21 // Constants for multiplication: four random odd 32-bit numbers.
28 func memhash(p unsafe
.Pointer
, seed
, s
uintptr) uintptr {
29 if GOARCH
== "386" && GOOS
!= "nacl" && useAeshash
{
30 return aeshash(p
, seed
, s
)
32 h
:= uint32(seed
+ s
*hashkey
[0])
37 h
^= uint32(*(*byte)(p
))
38 h
^= uint32(*(*byte)(add(p
, s
>>1))) << 8
39 h
^= uint32(*(*byte)(add(p
, s
-1))) << 16
40 h
= rotl_15(h
*m1
) * m2
42 h
^= readUnaligned32(p
)
43 h
= rotl_15(h
*m1
) * m2
45 h
^= readUnaligned32(p
)
46 h
= rotl_15(h
*m1
) * m2
47 h
^= readUnaligned32(add(p
, s
-4))
48 h
= rotl_15(h
*m1
) * m2
50 h
^= readUnaligned32(p
)
51 h
= rotl_15(h
*m1
) * m2
52 h
^= readUnaligned32(add(p
, 4))
53 h
= rotl_15(h
*m1
) * m2
54 h
^= readUnaligned32(add(p
, s
-8))
55 h
= rotl_15(h
*m1
) * m2
56 h
^= readUnaligned32(add(p
, s
-4))
57 h
= rotl_15(h
*m1
) * m2
60 v2
:= uint32(seed
* hashkey
[1])
61 v3
:= uint32(seed
* hashkey
[2])
62 v4
:= uint32(seed
* hashkey
[3])
64 v1
^= readUnaligned32(p
)
65 v1
= rotl_15(v1
*m1
) * m2
67 v2
^= readUnaligned32(p
)
68 v2
= rotl_15(v2
*m2
) * m3
70 v3
^= readUnaligned32(p
)
71 v3
= rotl_15(v3
*m3
) * m4
73 v4
^= readUnaligned32(p
)
74 v4
= rotl_15(v4
*m4
) * m1
89 // Note: in order to get the compiler to issue rotl instructions, we
90 // need to constant fold the shift amount by hand.
91 // TODO: convince the compiler to issue rotl instructions after inlining.
92 func rotl_15(x
uint32) uint32 {
93 return (x
<< 15) |
(x
>> (32 - 15))