blob: 7a76a6bce2b58bf771b83cc0717eacb6c8d1e93d [file] [log] [blame]
Takahiro Suzuki241c10e2020-12-17 20:17:57 +09001// Package xxh32 implements the very fast XXH hashing algorithm (32 bits version).
2// (https://github.com/Cyan4973/XXH/)
3package xxh32
4
5import (
6 "encoding/binary"
7)
8
9const (
10 prime1 uint32 = 2654435761
11 prime2 uint32 = 2246822519
12 prime3 uint32 = 3266489917
13 prime4 uint32 = 668265263
14 prime5 uint32 = 374761393
15
16 primeMask = 0xFFFFFFFF
17 prime1plus2 = uint32((uint64(prime1) + uint64(prime2)) & primeMask) // 606290984
18 prime1minus = uint32((-int64(prime1)) & primeMask) // 1640531535
19)
20
21// XXHZero represents an xxhash32 object with seed 0.
22type XXHZero struct {
23 v1 uint32
24 v2 uint32
25 v3 uint32
26 v4 uint32
27 totalLen uint64
28 buf [16]byte
29 bufused int
30}
31
32// Sum appends the current hash to b and returns the resulting slice.
33// It does not change the underlying hash state.
34func (xxh XXHZero) Sum(b []byte) []byte {
35 h32 := xxh.Sum32()
36 return append(b, byte(h32), byte(h32>>8), byte(h32>>16), byte(h32>>24))
37}
38
39// Reset resets the Hash to its initial state.
40func (xxh *XXHZero) Reset() {
41 xxh.v1 = prime1plus2
42 xxh.v2 = prime2
43 xxh.v3 = 0
44 xxh.v4 = prime1minus
45 xxh.totalLen = 0
46 xxh.bufused = 0
47}
48
49// Size returns the number of bytes returned by Sum().
50func (xxh *XXHZero) Size() int {
51 return 4
52}
53
54// BlockSize gives the minimum number of bytes accepted by Write().
55func (xxh *XXHZero) BlockSize() int {
56 return 1
57}
58
59// Write adds input bytes to the Hash.
60// It never returns an error.
61func (xxh *XXHZero) Write(input []byte) (int, error) {
62 if xxh.totalLen == 0 {
63 xxh.Reset()
64 }
65 n := len(input)
66 m := xxh.bufused
67
68 xxh.totalLen += uint64(n)
69
70 r := len(xxh.buf) - m
71 if n < r {
72 copy(xxh.buf[m:], input)
73 xxh.bufused += len(input)
74 return n, nil
75 }
76
77 p := 0
78 // Causes compiler to work directly from registers instead of stack:
79 v1, v2, v3, v4 := xxh.v1, xxh.v2, xxh.v3, xxh.v4
80 if m > 0 {
81 // some data left from previous update
82 copy(xxh.buf[xxh.bufused:], input[:r])
83 xxh.bufused += len(input) - r
84
85 // fast rotl(13)
86 buf := xxh.buf[:16] // BCE hint.
87 v1 = rol13(v1+binary.LittleEndian.Uint32(buf[:])*prime2) * prime1
88 v2 = rol13(v2+binary.LittleEndian.Uint32(buf[4:])*prime2) * prime1
89 v3 = rol13(v3+binary.LittleEndian.Uint32(buf[8:])*prime2) * prime1
90 v4 = rol13(v4+binary.LittleEndian.Uint32(buf[12:])*prime2) * prime1
91 p = r
92 xxh.bufused = 0
93 }
94
95 for n := n - 16; p <= n; p += 16 {
96 sub := input[p:][:16] //BCE hint for compiler
97 v1 = rol13(v1+binary.LittleEndian.Uint32(sub[:])*prime2) * prime1
98 v2 = rol13(v2+binary.LittleEndian.Uint32(sub[4:])*prime2) * prime1
99 v3 = rol13(v3+binary.LittleEndian.Uint32(sub[8:])*prime2) * prime1
100 v4 = rol13(v4+binary.LittleEndian.Uint32(sub[12:])*prime2) * prime1
101 }
102 xxh.v1, xxh.v2, xxh.v3, xxh.v4 = v1, v2, v3, v4
103
104 copy(xxh.buf[xxh.bufused:], input[p:])
105 xxh.bufused += len(input) - p
106
107 return n, nil
108}
109
110// Sum32 returns the 32 bits Hash value.
111func (xxh *XXHZero) Sum32() uint32 {
112 h32 := uint32(xxh.totalLen)
113 if h32 >= 16 {
114 h32 += rol1(xxh.v1) + rol7(xxh.v2) + rol12(xxh.v3) + rol18(xxh.v4)
115 } else {
116 h32 += prime5
117 }
118
119 p := 0
120 n := xxh.bufused
121 buf := xxh.buf
122 for n := n - 4; p <= n; p += 4 {
123 h32 += binary.LittleEndian.Uint32(buf[p:p+4]) * prime3
124 h32 = rol17(h32) * prime4
125 }
126 for ; p < n; p++ {
127 h32 += uint32(buf[p]) * prime5
128 h32 = rol11(h32) * prime1
129 }
130
131 h32 ^= h32 >> 15
132 h32 *= prime2
133 h32 ^= h32 >> 13
134 h32 *= prime3
135 h32 ^= h32 >> 16
136
137 return h32
138}
139
140// ChecksumZero returns the 32bits Hash value.
141func ChecksumZero(input []byte) uint32 {
142 n := len(input)
143 h32 := uint32(n)
144
145 if n < 16 {
146 h32 += prime5
147 } else {
148 v1 := prime1plus2
149 v2 := prime2
150 v3 := uint32(0)
151 v4 := prime1minus
152 p := 0
153 for n := n - 16; p <= n; p += 16 {
154 sub := input[p:][:16] //BCE hint for compiler
155 v1 = rol13(v1+binary.LittleEndian.Uint32(sub[:])*prime2) * prime1
156 v2 = rol13(v2+binary.LittleEndian.Uint32(sub[4:])*prime2) * prime1
157 v3 = rol13(v3+binary.LittleEndian.Uint32(sub[8:])*prime2) * prime1
158 v4 = rol13(v4+binary.LittleEndian.Uint32(sub[12:])*prime2) * prime1
159 }
160 input = input[p:]
161 n -= p
162 h32 += rol1(v1) + rol7(v2) + rol12(v3) + rol18(v4)
163 }
164
165 p := 0
166 for n := n - 4; p <= n; p += 4 {
167 h32 += binary.LittleEndian.Uint32(input[p:p+4]) * prime3
168 h32 = rol17(h32) * prime4
169 }
170 for p < n {
171 h32 += uint32(input[p]) * prime5
172 h32 = rol11(h32) * prime1
173 p++
174 }
175
176 h32 ^= h32 >> 15
177 h32 *= prime2
178 h32 ^= h32 >> 13
179 h32 *= prime3
180 h32 ^= h32 >> 16
181
182 return h32
183}
184
185// Uint32Zero hashes x with seed 0.
186func Uint32Zero(x uint32) uint32 {
187 h := prime5 + 4 + x*prime3
188 h = rol17(h) * prime4
189 h ^= h >> 15
190 h *= prime2
191 h ^= h >> 13
192 h *= prime3
193 h ^= h >> 16
194 return h
195}
196
197func rol1(u uint32) uint32 {
198 return u<<1 | u>>31
199}
200
201func rol7(u uint32) uint32 {
202 return u<<7 | u>>25
203}
204
205func rol11(u uint32) uint32 {
206 return u<<11 | u>>21
207}
208
209func rol12(u uint32) uint32 {
210 return u<<12 | u>>20
211}
212
213func rol13(u uint32) uint32 {
214 return u<<13 | u>>19
215}
216
217func rol17(u uint32) uint32 {
218 return u<<17 | u>>15
219}
220
221func rol18(u uint32) uint32 {
222 return u<<18 | u>>14
223}