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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
package jody
import (
"reflect"
"unsafe"
)
const (
shift = 11
constant = 0x1f3d5b79
// Init64 is what 64 bits hash values should be initialized with.
Init64 = uint64(0)
)
var mask64 = [...]uint64{
0x0000000000000000,
0x00000000000000ff,
0x000000000000ffff,
0x0000000000ffffff,
0x00000000ffffffff,
0x000000ffffffffff,
0x0000ffffffffffff,
0x00ffffffffffffff,
0xffffffffffffffff,
}
// HashString64 returns the hash of s.
func HashString64(s string) uint64 {
return AddString64(Init64, s)
}
// HashBytes64 returns the hash of u.
func HashBytes64(b []byte) uint64 {
return AddBytes64(Init64, b)
}
// HashUint64 returns the hash of u.
func HashUint64(u uint64) uint64 {
return AddUint64(Init64, u)
}
// AddString64 adds the hash of s to the precomputed hash value h.
func AddString64(h uint64, s string) uint64 {
/*
This is an implementation of the jody hashing algorithm as found here:
- https://github.com/jbruchon/jodyhash
It was revisited a bit and only the 64 bit version is available for now,
but it's indeed really fast:
- BenchmarkHash64/jody/algorithm-4 100000000 11.8 ns/op 3050.83 MB/s 0 B/op 0 allocs/op
Here's what the reference implementation looks like:
hash_t hash = start_hash;
hash_t element;
hash_t partial_salt;
size_t len;
len = count / sizeof(hash_t);
for (; len > 0; len--) {
element = *data;
hash += element;
hash += constant;
hash = (hash << shift) | hash >> (sizeof(hash_t) * 8 - shift);
hash ^= element;
hash = (hash << shift) | hash >> (sizeof(hash_t) * 8 - shift);
hash ^= constant;
hash += element;
data++;
}
len = count & (sizeof(hash_t) - 1);
if (len) {
partial_salt = constant & tail_mask[len];
element = *data & tail_mask[len];
hash += element;
hash += partial_salt;
hash = (hash << shift) | hash >> (sizeof(hash_t) * 8 - shift);
hash ^= element;
hash = (hash << shift) | hash >> (sizeof(hash_t) * 8 - shift);
hash ^= partial_salt;
hash += element;
}
return hash;
*/
r := *(*reflect.StringHeader)(unsafe.Pointer(&s))
p := unsafe.Pointer((*reflect.StringHeader)(unsafe.Pointer(&s)).Data)
for n := r.Len / 8; n != 0; n-- {
v := *(*uint64)(p)
h = h + v + constant
h = (h<<shift | h>>(64-shift)) ^ v
h = ((h<<shift | h>>(64-shift)) ^ constant) + v
p = unsafe.Pointer(uintptr(p) + 8)
}
if n := (r.Len & 7); n != 0 {
c := constant & mask64[n]
v := uint64(0)
off := uint(0)
if 0 != (n & 4) {
v += uint64(*(*uint32)(p))
off += 32
p = unsafe.Pointer(uintptr(p) + 4)
}
if 0 != (n & 2) {
v += uint64(*(*uint16)(p)) << off
off += 16
p = unsafe.Pointer(uintptr(p) + 2)
}
if 0 != (n & 1) {
v += uint64(*(*uint8)(p)) << off
}
h = h + v + c
h = (h<<shift | h>>(64-shift)) ^ v
h = ((h<<shift | h>>(64-shift)) ^ c) + v
}
return h
}
// AddBytes64 adds the hash of b to the precomputed hash value h.
func AddBytes64(h uint64, b []byte) uint64 {
return AddString64(h, *(*string)(unsafe.Pointer(&b)))
}
// AddUint64 adds the hash value of the 8 bytes of u to h.
func AddUint64(h uint64, u uint64) uint64 {
h = h + u + constant
h = (h<<shift | h>>(64-shift)) ^ u
h = ((h<<shift | h>>(64-shift)) ^ constant) + u
return h
}
|
