blob: f896bd28f058a6fe691c3e6e5e1a10ae79a0f413 [file] [log] [blame]
Takahiro Suzuki241c10e2020-12-17 20:17:57 +09001// Package xxhash implements the 64-bit variant of xxHash (XXH64) as described
2// at http://cyan4973.github.io/xxHash/.
3package xxhash
4
5import (
6 "encoding/binary"
7 "hash"
8)
9
10const (
11 prime1 uint64 = 11400714785074694791
12 prime2 uint64 = 14029467366897019727
13 prime3 uint64 = 1609587929392839161
14 prime4 uint64 = 9650029242287828579
15 prime5 uint64 = 2870177450012600261
16)
17
18// NOTE(caleb): I'm using both consts and vars of the primes. Using consts where
19// possible in the Go code is worth a small (but measurable) performance boost
20// by avoiding some MOVQs. Vars are needed for the asm and also are useful for
21// convenience in the Go code in a few places where we need to intentionally
22// avoid constant arithmetic (e.g., v1 := prime1 + prime2 fails because the
23// result overflows a uint64).
24var (
25 prime1v = prime1
26 prime2v = prime2
27 prime3v = prime3
28 prime4v = prime4
29 prime5v = prime5
30)
31
32type xxh struct {
33 v1 uint64
34 v2 uint64
35 v3 uint64
36 v4 uint64
37 total int
38 mem [32]byte
39 n int // how much of mem is used
40}
41
42// New creates a new hash.Hash64 that implements the 64-bit xxHash algorithm.
43func New() hash.Hash64 {
44 var x xxh
45 x.Reset()
46 return &x
47}
48
49func (x *xxh) Reset() {
50 x.n = 0
51 x.total = 0
52 x.v1 = prime1v + prime2
53 x.v2 = prime2
54 x.v3 = 0
55 x.v4 = -prime1v
56}
57
58func (x *xxh) Size() int { return 8 }
59func (x *xxh) BlockSize() int { return 32 }
60
61// Write adds more data to x. It always returns len(b), nil.
62func (x *xxh) Write(b []byte) (n int, err error) {
63 n = len(b)
64 x.total += len(b)
65
66 if x.n+len(b) < 32 {
67 // This new data doesn't even fill the current block.
68 copy(x.mem[x.n:], b)
69 x.n += len(b)
70 return
71 }
72
73 if x.n > 0 {
74 // Finish off the partial block.
75 copy(x.mem[x.n:], b)
76 x.v1 = round(x.v1, u64(x.mem[0:8]))
77 x.v2 = round(x.v2, u64(x.mem[8:16]))
78 x.v3 = round(x.v3, u64(x.mem[16:24]))
79 x.v4 = round(x.v4, u64(x.mem[24:32]))
80 b = b[32-x.n:]
81 x.n = 0
82 }
83
84 if len(b) >= 32 {
85 // One or more full blocks left.
86 b = writeBlocks(x, b)
87 }
88
89 // Store any remaining partial block.
90 copy(x.mem[:], b)
91 x.n = len(b)
92
93 return
94}
95
96func (x *xxh) Sum(b []byte) []byte {
97 s := x.Sum64()
98 return append(
99 b,
100 byte(s>>56),
101 byte(s>>48),
102 byte(s>>40),
103 byte(s>>32),
104 byte(s>>24),
105 byte(s>>16),
106 byte(s>>8),
107 byte(s),
108 )
109}
110
111func (x *xxh) Sum64() uint64 {
112 var h uint64
113
114 if x.total >= 32 {
115 v1, v2, v3, v4 := x.v1, x.v2, x.v3, x.v4
116 h = rol1(v1) + rol7(v2) + rol12(v3) + rol18(v4)
117 h = mergeRound(h, v1)
118 h = mergeRound(h, v2)
119 h = mergeRound(h, v3)
120 h = mergeRound(h, v4)
121 } else {
122 h = x.v3 + prime5
123 }
124
125 h += uint64(x.total)
126
127 i, end := 0, x.n
128 for ; i+8 <= end; i += 8 {
129 k1 := round(0, u64(x.mem[i:i+8]))
130 h ^= k1
131 h = rol27(h)*prime1 + prime4
132 }
133 if i+4 <= end {
134 h ^= uint64(u32(x.mem[i:i+4])) * prime1
135 h = rol23(h)*prime2 + prime3
136 i += 4
137 }
138 for i < end {
139 h ^= uint64(x.mem[i]) * prime5
140 h = rol11(h) * prime1
141 i++
142 }
143
144 h ^= h >> 33
145 h *= prime2
146 h ^= h >> 29
147 h *= prime3
148 h ^= h >> 32
149
150 return h
151}
152
153func u64(b []byte) uint64 { return binary.LittleEndian.Uint64(b) }
154func u32(b []byte) uint32 { return binary.LittleEndian.Uint32(b) }
155
156func round(acc, input uint64) uint64 {
157 acc += input * prime2
158 acc = rol31(acc)
159 acc *= prime1
160 return acc
161}
162
163func mergeRound(acc, val uint64) uint64 {
164 val = round(0, val)
165 acc ^= val
166 acc = acc*prime1 + prime4
167 return acc
168}