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