blob: f57c9cf93e444f111e134bc982be95b0908ed925 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
//go:build runtime_memhash_leveldb || (wasip1 && !runtime_memhash_fnv && !runtime_memhash_tsip)
// This is the default for WASI, but can also be used on other targets with the
// right build tag.
// This is the hash function from Google's leveldb key-value storage system. It
// processes 4 bytes at a time making it faster than the FNV hash for buffer
// lengths > 16 bytes.
// https://github.com/google/leveldb
// https://en.wikipedia.org/wiki/LevelDB
package runtime
import (
"unsafe"
)
func ptrToSlice(ptr unsafe.Pointer, n uintptr) []byte {
var p []byte
type _bslice struct {
ptr *byte
len uintptr
cap uintptr
}
pslice := (*_bslice)(unsafe.Pointer(&p))
pslice.ptr = (*byte)(ptr)
pslice.cap = n
pslice.len = n
return p
}
// leveldb hash
func hash32(ptr unsafe.Pointer, n, seed uintptr) uint32 {
const (
lseed = 0xbc9f1d34
m = 0xc6a4a793
)
b := ptrToSlice(ptr, n)
h := uint32(lseed^seed) ^ uint32(uint(len(b))*uint(m))
for ; len(b) >= 4; b = b[4:] {
h += uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
h *= m
h ^= h >> 16
}
switch len(b) {
case 3:
h += uint32(b[2]) << 16
fallthrough
case 2:
h += uint32(b[1]) << 8
fallthrough
case 1:
h += uint32(b[0])
h *= m
h ^= h >> 24
}
return h
}
// hash64finalizer is a 64-bit integer mixing function from
// https://web.archive.org/web/20120720045250/http://www.cris.com/~Ttwang/tech/inthash.htm
func hash64finalizer(key uint64) uint64 {
key = ^key + (key << 21) // key = (key << 21) - key - 1;
key = key ^ (key >> 24)
key = (key + (key << 3)) + (key << 8) // key * 265
key = key ^ (key >> 14)
key = (key + (key << 2)) + (key << 4) // key * 21
key = key ^ (key >> 28)
key = key + (key << 31)
return key
}
// hash64 turns hash32 into a 64-bit hash, by use hash64finalizer to
// mix the result of hash32 function combined with an xorshifted version of
// the seed.
func hash64(ptr unsafe.Pointer, n, seed uintptr) uint64 {
h32 := hash32(ptr, n, seed)
return hash64finalizer((uint64(h32^xorshift32(uint32(seed))) << 32) | uint64(h32))
}
|
