xxhash.mx raw
1 // Copyright 2023 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 package zstd
6
7 import (
8 "encoding/binary"
9 "math/bits"
10 )
11
12 const (
13 xxhPrime64c1 = 0x9e3779b185ebca87
14 xxhPrime64c2 = 0xc2b2ae3d27d4eb4f
15 xxhPrime64c3 = 0x165667b19e3779f9
16 xxhPrime64c4 = 0x85ebca77c2b2ae63
17 xxhPrime64c5 = 0x27d4eb2f165667c5
18 )
19
20 // xxhash64 is the state of a xxHash-64 checksum.
21 type xxhash64 struct {
22 len uint64 // total length hashed
23 v [4]uint64 // accumulators
24 buf [32]byte // buffer
25 cnt int // number of bytes in buffer
26 }
27
28 // reset discards the current state and prepares to compute a new hash.
29 // We assume a seed of 0 since that is what zstd uses.
30 func (xh *xxhash64) reset() {
31 xh.len = 0
32
33 // Separate addition for awkward constant overflow.
34 xh.v[0] = xxhPrime64c1
35 xh.v[0] += xxhPrime64c2
36
37 xh.v[1] = xxhPrime64c2
38 xh.v[2] = 0
39
40 // Separate negation for awkward constant overflow.
41 xh.v[3] = xxhPrime64c1
42 xh.v[3] = -xh.v[3]
43
44 clear(xh.buf[:])
45 xh.cnt = 0
46 }
47
48 // update adds a buffer to the has.
49 func (xh *xxhash64) update(b []byte) {
50 xh.len += uint64(len(b))
51
52 if xh.cnt+len(b) < len(xh.buf) {
53 copy(xh.buf[xh.cnt:], b)
54 xh.cnt += len(b)
55 return
56 }
57
58 if xh.cnt > 0 {
59 n := copy(xh.buf[xh.cnt:], b)
60 b = b[n:]
61 xh.v[0] = xh.round(xh.v[0], binary.LittleEndian.Uint64(xh.buf[:]))
62 xh.v[1] = xh.round(xh.v[1], binary.LittleEndian.Uint64(xh.buf[8:]))
63 xh.v[2] = xh.round(xh.v[2], binary.LittleEndian.Uint64(xh.buf[16:]))
64 xh.v[3] = xh.round(xh.v[3], binary.LittleEndian.Uint64(xh.buf[24:]))
65 xh.cnt = 0
66 }
67
68 for len(b) >= 32 {
69 xh.v[0] = xh.round(xh.v[0], binary.LittleEndian.Uint64(b))
70 xh.v[1] = xh.round(xh.v[1], binary.LittleEndian.Uint64(b[8:]))
71 xh.v[2] = xh.round(xh.v[2], binary.LittleEndian.Uint64(b[16:]))
72 xh.v[3] = xh.round(xh.v[3], binary.LittleEndian.Uint64(b[24:]))
73 b = b[32:]
74 }
75
76 if len(b) > 0 {
77 copy(xh.buf[:], b)
78 xh.cnt = len(b)
79 }
80 }
81
82 // digest returns the final hash value.
83 func (xh *xxhash64) digest() uint64 {
84 var h64 uint64
85 if xh.len < 32 {
86 h64 = xh.v[2] + xxhPrime64c5
87 } else {
88 h64 = bits.RotateLeft64(xh.v[0], 1) +
89 bits.RotateLeft64(xh.v[1], 7) +
90 bits.RotateLeft64(xh.v[2], 12) +
91 bits.RotateLeft64(xh.v[3], 18)
92 h64 = xh.mergeRound(h64, xh.v[0])
93 h64 = xh.mergeRound(h64, xh.v[1])
94 h64 = xh.mergeRound(h64, xh.v[2])
95 h64 = xh.mergeRound(h64, xh.v[3])
96 }
97
98 h64 += xh.len
99
100 len := xh.len
101 len &= 31
102 buf := xh.buf[:]
103 for len >= 8 {
104 k1 := xh.round(0, binary.LittleEndian.Uint64(buf))
105 buf = buf[8:]
106 h64 ^= k1
107 h64 = bits.RotateLeft64(h64, 27)*xxhPrime64c1 + xxhPrime64c4
108 len -= 8
109 }
110 if len >= 4 {
111 h64 ^= uint64(binary.LittleEndian.Uint32(buf)) * xxhPrime64c1
112 buf = buf[4:]
113 h64 = bits.RotateLeft64(h64, 23)*xxhPrime64c2 + xxhPrime64c3
114 len -= 4
115 }
116 for len > 0 {
117 h64 ^= uint64(buf[0]) * xxhPrime64c5
118 buf = buf[1:]
119 h64 = bits.RotateLeft64(h64, 11) * xxhPrime64c1
120 len--
121 }
122
123 h64 ^= h64 >> 33
124 h64 *= xxhPrime64c2
125 h64 ^= h64 >> 29
126 h64 *= xxhPrime64c3
127 h64 ^= h64 >> 32
128
129 return h64
130 }
131
132 // round updates a value.
133 func (xh *xxhash64) round(v, n uint64) uint64 {
134 v += n * xxhPrime64c2
135 v = bits.RotateLeft64(v, 31)
136 v *= xxhPrime64c1
137 return v
138 }
139
140 // mergeRound updates a value in the final round.
141 func (xh *xxhash64) mergeRound(v, n uint64) uint64 {
142 n = xh.round(0, n)
143 v ^= n
144 v = v*xxhPrime64c1 + xxhPrime64c4
145 return v
146 }
147