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
142
143
144
145
146
147
148
|
// Copyright 2023 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package zstd
import (
"encoding/binary"
"math/bits"
)
const (
xxhPrime64c1 = 0x9e3779b185ebca87
xxhPrime64c2 = 0xc2b2ae3d27d4eb4f
xxhPrime64c3 = 0x165667b19e3779f9
xxhPrime64c4 = 0x85ebca77c2b2ae63
xxhPrime64c5 = 0x27d4eb2f165667c5
)
// xxhash64 is the state of a xxHash-64 checksum.
type xxhash64 struct {
len uint64 // total length hashed
v [4]uint64 // accumulators
buf [32]byte // buffer
cnt int // number of bytes in buffer
}
// reset discards the current state and prepares to compute a new hash.
// We assume a seed of 0 since that is what zstd uses.
func (xh *xxhash64) reset() {
xh.len = 0
// Separate addition for awkward constant overflow.
xh.v[0] = xxhPrime64c1
xh.v[0] += xxhPrime64c2
xh.v[1] = xxhPrime64c2
xh.v[2] = 0
// Separate negation for awkward constant overflow.
xh.v[3] = xxhPrime64c1
xh.v[3] = -xh.v[3]
for i := range xh.buf {
xh.buf[i] = 0
}
xh.cnt = 0
}
// update adds a buffer to the has.
func (xh *xxhash64) update(b []byte) {
xh.len += uint64(len(b))
if xh.cnt+len(b) < len(xh.buf) {
copy(xh.buf[xh.cnt:], b)
xh.cnt += len(b)
return
}
if xh.cnt > 0 {
n := copy(xh.buf[xh.cnt:], b)
b = b[n:]
xh.v[0] = xh.round(xh.v[0], binary.LittleEndian.Uint64(xh.buf[:]))
xh.v[1] = xh.round(xh.v[1], binary.LittleEndian.Uint64(xh.buf[8:]))
xh.v[2] = xh.round(xh.v[2], binary.LittleEndian.Uint64(xh.buf[16:]))
xh.v[3] = xh.round(xh.v[3], binary.LittleEndian.Uint64(xh.buf[24:]))
xh.cnt = 0
}
for len(b) >= 32 {
xh.v[0] = xh.round(xh.v[0], binary.LittleEndian.Uint64(b))
xh.v[1] = xh.round(xh.v[1], binary.LittleEndian.Uint64(b[8:]))
xh.v[2] = xh.round(xh.v[2], binary.LittleEndian.Uint64(b[16:]))
xh.v[3] = xh.round(xh.v[3], binary.LittleEndian.Uint64(b[24:]))
b = b[32:]
}
if len(b) > 0 {
copy(xh.buf[:], b)
xh.cnt = len(b)
}
}
// digest returns the final hash value.
func (xh *xxhash64) digest() uint64 {
var h64 uint64
if xh.len < 32 {
h64 = xh.v[2] + xxhPrime64c5
} else {
h64 = bits.RotateLeft64(xh.v[0], 1) +
bits.RotateLeft64(xh.v[1], 7) +
bits.RotateLeft64(xh.v[2], 12) +
bits.RotateLeft64(xh.v[3], 18)
h64 = xh.mergeRound(h64, xh.v[0])
h64 = xh.mergeRound(h64, xh.v[1])
h64 = xh.mergeRound(h64, xh.v[2])
h64 = xh.mergeRound(h64, xh.v[3])
}
h64 += xh.len
len := xh.len
len &= 31
buf := xh.buf[:]
for len >= 8 {
k1 := xh.round(0, binary.LittleEndian.Uint64(buf))
buf = buf[8:]
h64 ^= k1
h64 = bits.RotateLeft64(h64, 27)*xxhPrime64c1 + xxhPrime64c4
len -= 8
}
if len >= 4 {
h64 ^= uint64(binary.LittleEndian.Uint32(buf)) * xxhPrime64c1
buf = buf[4:]
h64 = bits.RotateLeft64(h64, 23)*xxhPrime64c2 + xxhPrime64c3
len -= 4
}
for len > 0 {
h64 ^= uint64(buf[0]) * xxhPrime64c5
buf = buf[1:]
h64 = bits.RotateLeft64(h64, 11) * xxhPrime64c1
len--
}
h64 ^= h64 >> 33
h64 *= xxhPrime64c2
h64 ^= h64 >> 29
h64 *= xxhPrime64c3
h64 ^= h64 >> 32
return h64
}
// round updates a value.
func (xh *xxhash64) round(v, n uint64) uint64 {
v += n * xxhPrime64c2
v = bits.RotateLeft64(v, 31)
v *= xxhPrime64c1
return v
}
// mergeRound updates a value in the final round.
func (xh *xxhash64) mergeRound(v, n uint64) uint64 {
n = xh.round(0, n)
v ^= n
v = v*xxhPrime64c1 + xxhPrime64c4
return v
}
|
