xxhash.go raw
1 // Package xxhash implements the 64-bit variant of xxHash (XXH64) as described
2 // at http://cyan4973.github.io/xxHash/.
3 // THIS IS VENDORED: Go to github.com/cespare/xxhash for original package.
4
5 package xxhash
6
7 import (
8 "encoding/binary"
9 "errors"
10 "math/bits"
11 )
12
13 const (
14 prime1 uint64 = 11400714785074694791
15 prime2 uint64 = 14029467366897019727
16 prime3 uint64 = 1609587929392839161
17 prime4 uint64 = 9650029242287828579
18 prime5 uint64 = 2870177450012600261
19 )
20
21 // Store the primes in an array as well.
22 //
23 // The consts are used when possible in Go code to avoid MOVs but we need a
24 // contiguous array of the assembly code.
25 var primes = [...]uint64{prime1, prime2, prime3, prime4, prime5}
26
27 // Digest implements hash.Hash64.
28 type Digest struct {
29 v1 uint64
30 v2 uint64
31 v3 uint64
32 v4 uint64
33 total uint64
34 mem [32]byte
35 n int // how much of mem is used
36 }
37
38 // New creates a new Digest that computes the 64-bit xxHash algorithm.
39 func New() *Digest {
40 var d Digest
41 d.Reset()
42 return &d
43 }
44
45 // Reset clears the Digest's state so that it can be reused.
46 func (d *Digest) Reset() {
47 d.v1 = primes[0] + prime2
48 d.v2 = prime2
49 d.v3 = 0
50 d.v4 = -primes[0]
51 d.total = 0
52 d.n = 0
53 }
54
55 // Size always returns 8 bytes.
56 func (d *Digest) Size() int { return 8 }
57
58 // BlockSize always returns 32 bytes.
59 func (d *Digest) BlockSize() int { return 32 }
60
61 // Write adds more data to d. It always returns len(b), nil.
62 func (d *Digest) Write(b []byte) (n int, err error) {
63 n = len(b)
64 d.total += uint64(n)
65
66 memleft := d.mem[d.n&(len(d.mem)-1):]
67
68 if d.n+n < 32 {
69 // This new data doesn't even fill the current block.
70 copy(memleft, b)
71 d.n += n
72 return
73 }
74
75 if d.n > 0 {
76 // Finish off the partial block.
77 c := copy(memleft, b)
78 d.v1 = round(d.v1, u64(d.mem[0:8]))
79 d.v2 = round(d.v2, u64(d.mem[8:16]))
80 d.v3 = round(d.v3, u64(d.mem[16:24]))
81 d.v4 = round(d.v4, u64(d.mem[24:32]))
82 b = b[c:]
83 d.n = 0
84 }
85
86 if len(b) >= 32 {
87 // One or more full blocks left.
88 nw := writeBlocks(d, b)
89 b = b[nw:]
90 }
91
92 // Store any remaining partial block.
93 copy(d.mem[:], b)
94 d.n = len(b)
95
96 return
97 }
98
99 // Sum appends the current hash to b and returns the resulting slice.
100 func (d *Digest) Sum(b []byte) []byte {
101 s := d.Sum64()
102 return append(
103 b,
104 byte(s>>56),
105 byte(s>>48),
106 byte(s>>40),
107 byte(s>>32),
108 byte(s>>24),
109 byte(s>>16),
110 byte(s>>8),
111 byte(s),
112 )
113 }
114
115 // Sum64 returns the current hash.
116 func (d *Digest) Sum64() uint64 {
117 var h uint64
118
119 if d.total >= 32 {
120 v1, v2, v3, v4 := d.v1, d.v2, d.v3, d.v4
121 h = rol1(v1) + rol7(v2) + rol12(v3) + rol18(v4)
122 h = mergeRound(h, v1)
123 h = mergeRound(h, v2)
124 h = mergeRound(h, v3)
125 h = mergeRound(h, v4)
126 } else {
127 h = d.v3 + prime5
128 }
129
130 h += d.total
131
132 b := d.mem[:d.n&(len(d.mem)-1)]
133 for ; len(b) >= 8; b = b[8:] {
134 k1 := round(0, u64(b[:8]))
135 h ^= k1
136 h = rol27(h)*prime1 + prime4
137 }
138 if len(b) >= 4 {
139 h ^= uint64(u32(b[:4])) * prime1
140 h = rol23(h)*prime2 + prime3
141 b = b[4:]
142 }
143 for ; len(b) > 0; b = b[1:] {
144 h ^= uint64(b[0]) * prime5
145 h = rol11(h) * prime1
146 }
147
148 h ^= h >> 33
149 h *= prime2
150 h ^= h >> 29
151 h *= prime3
152 h ^= h >> 32
153
154 return h
155 }
156
157 const (
158 magic = "xxh\x06"
159 marshaledSize = len(magic) + 8*5 + 32
160 )
161
162 // MarshalBinary implements the encoding.BinaryMarshaler interface.
163 func (d *Digest) MarshalBinary() ([]byte, error) {
164 b := make([]byte, 0, marshaledSize)
165 b = append(b, magic...)
166 b = appendUint64(b, d.v1)
167 b = appendUint64(b, d.v2)
168 b = appendUint64(b, d.v3)
169 b = appendUint64(b, d.v4)
170 b = appendUint64(b, d.total)
171 b = append(b, d.mem[:d.n]...)
172 b = b[:len(b)+len(d.mem)-d.n]
173 return b, nil
174 }
175
176 // UnmarshalBinary implements the encoding.BinaryUnmarshaler interface.
177 func (d *Digest) UnmarshalBinary(b []byte) error {
178 if len(b) < len(magic) || string(b[:len(magic)]) != magic {
179 return errors.New("xxhash: invalid hash state identifier")
180 }
181 if len(b) != marshaledSize {
182 return errors.New("xxhash: invalid hash state size")
183 }
184 b = b[len(magic):]
185 b, d.v1 = consumeUint64(b)
186 b, d.v2 = consumeUint64(b)
187 b, d.v3 = consumeUint64(b)
188 b, d.v4 = consumeUint64(b)
189 b, d.total = consumeUint64(b)
190 copy(d.mem[:], b)
191 d.n = int(d.total % uint64(len(d.mem)))
192 return nil
193 }
194
195 func appendUint64(b []byte, x uint64) []byte {
196 var a [8]byte
197 binary.LittleEndian.PutUint64(a[:], x)
198 return append(b, a[:]...)
199 }
200
201 func consumeUint64(b []byte) ([]byte, uint64) {
202 x := u64(b)
203 return b[8:], x
204 }
205
206 func u64(b []byte) uint64 { return binary.LittleEndian.Uint64(b) }
207 func u32(b []byte) uint32 { return binary.LittleEndian.Uint32(b) }
208
209 func round(acc, input uint64) uint64 {
210 acc += input * prime2
211 acc = rol31(acc)
212 acc *= prime1
213 return acc
214 }
215
216 func mergeRound(acc, val uint64) uint64 {
217 val = round(0, val)
218 acc ^= val
219 acc = acc*prime1 + prime4
220 return acc
221 }
222
223 func rol1(x uint64) uint64 { return bits.RotateLeft64(x, 1) }
224 func rol7(x uint64) uint64 { return bits.RotateLeft64(x, 7) }
225 func rol11(x uint64) uint64 { return bits.RotateLeft64(x, 11) }
226 func rol12(x uint64) uint64 { return bits.RotateLeft64(x, 12) }
227 func rol18(x uint64) uint64 { return bits.RotateLeft64(x, 18) }
228 func rol23(x uint64) uint64 { return bits.RotateLeft64(x, 23) }
229 func rol27(x uint64) uint64 { return bits.RotateLeft64(x, 27) }
230 func rol31(x uint64) uint64 { return bits.RotateLeft64(x, 31) }
231