Source file src/pkg/hash/fnv/fnv.go
1
2
3
4
5
6
7
8
9
10
11
12
13 package fnv
14
15 import (
16 "errors"
17 "hash"
18 "math/bits"
19 )
20
21 type (
22 sum32 uint32
23 sum32a uint32
24 sum64 uint64
25 sum64a uint64
26 sum128 [2]uint64
27 sum128a [2]uint64
28 )
29
30 const (
31 offset32 = 2166136261
32 offset64 = 14695981039346656037
33 offset128Lower = 0x62b821756295c58d
34 offset128Higher = 0x6c62272e07bb0142
35 prime32 = 16777619
36 prime64 = 1099511628211
37 prime128Lower = 0x13b
38 prime128Shift = 24
39 )
40
41
42
43 func New32() hash.Hash32 {
44 var s sum32 = offset32
45 return &s
46 }
47
48
49
50 func New32a() hash.Hash32 {
51 var s sum32a = offset32
52 return &s
53 }
54
55
56
57 func New64() hash.Hash64 {
58 var s sum64 = offset64
59 return &s
60 }
61
62
63
64 func New64a() hash.Hash64 {
65 var s sum64a = offset64
66 return &s
67 }
68
69
70
71 func New128() hash.Hash {
72 var s sum128
73 s[0] = offset128Higher
74 s[1] = offset128Lower
75 return &s
76 }
77
78
79
80 func New128a() hash.Hash {
81 var s sum128a
82 s[0] = offset128Higher
83 s[1] = offset128Lower
84 return &s
85 }
86
87 func (s *sum32) Reset() { *s = offset32 }
88 func (s *sum32a) Reset() { *s = offset32 }
89 func (s *sum64) Reset() { *s = offset64 }
90 func (s *sum64a) Reset() { *s = offset64 }
91 func (s *sum128) Reset() { s[0] = offset128Higher; s[1] = offset128Lower }
92 func (s *sum128a) Reset() { s[0] = offset128Higher; s[1] = offset128Lower }
93
94 func (s *sum32) Sum32() uint32 { return uint32(*s) }
95 func (s *sum32a) Sum32() uint32 { return uint32(*s) }
96 func (s *sum64) Sum64() uint64 { return uint64(*s) }
97 func (s *sum64a) Sum64() uint64 { return uint64(*s) }
98
99 func (s *sum32) Write(data []byte) (int, error) {
100 hash := *s
101 for _, c := range data {
102 hash *= prime32
103 hash ^= sum32(c)
104 }
105 *s = hash
106 return len(data), nil
107 }
108
109 func (s *sum32a) Write(data []byte) (int, error) {
110 hash := *s
111 for _, c := range data {
112 hash ^= sum32a(c)
113 hash *= prime32
114 }
115 *s = hash
116 return len(data), nil
117 }
118
119 func (s *sum64) Write(data []byte) (int, error) {
120 hash := *s
121 for _, c := range data {
122 hash *= prime64
123 hash ^= sum64(c)
124 }
125 *s = hash
126 return len(data), nil
127 }
128
129 func (s *sum64a) Write(data []byte) (int, error) {
130 hash := *s
131 for _, c := range data {
132 hash ^= sum64a(c)
133 hash *= prime64
134 }
135 *s = hash
136 return len(data), nil
137 }
138
139 func (s *sum128) Write(data []byte) (int, error) {
140 for _, c := range data {
141
142 s0, s1 := bits.Mul64(prime128Lower, s[1])
143 s0 += s[1]<<prime128Shift + prime128Lower*s[0]
144
145 s[1] = s1
146 s[0] = s0
147 s[1] ^= uint64(c)
148 }
149 return len(data), nil
150 }
151
152 func (s *sum128a) Write(data []byte) (int, error) {
153 for _, c := range data {
154 s[1] ^= uint64(c)
155
156 s0, s1 := bits.Mul64(prime128Lower, s[1])
157 s0 += s[1]<<prime128Shift + prime128Lower*s[0]
158
159 s[1] = s1
160 s[0] = s0
161 }
162 return len(data), nil
163 }
164
165 func (s *sum32) Size() int { return 4 }
166 func (s *sum32a) Size() int { return 4 }
167 func (s *sum64) Size() int { return 8 }
168 func (s *sum64a) Size() int { return 8 }
169 func (s *sum128) Size() int { return 16 }
170 func (s *sum128a) Size() int { return 16 }
171
172 func (s *sum32) BlockSize() int { return 1 }
173 func (s *sum32a) BlockSize() int { return 1 }
174 func (s *sum64) BlockSize() int { return 1 }
175 func (s *sum64a) BlockSize() int { return 1 }
176 func (s *sum128) BlockSize() int { return 1 }
177 func (s *sum128a) BlockSize() int { return 1 }
178
179 func (s *sum32) Sum(in []byte) []byte {
180 v := uint32(*s)
181 return append(in, byte(v>>24), byte(v>>16), byte(v>>8), byte(v))
182 }
183
184 func (s *sum32a) Sum(in []byte) []byte {
185 v := uint32(*s)
186 return append(in, byte(v>>24), byte(v>>16), byte(v>>8), byte(v))
187 }
188
189 func (s *sum64) Sum(in []byte) []byte {
190 v := uint64(*s)
191 return append(in, byte(v>>56), byte(v>>48), byte(v>>40), byte(v>>32), byte(v>>24), byte(v>>16), byte(v>>8), byte(v))
192 }
193
194 func (s *sum64a) Sum(in []byte) []byte {
195 v := uint64(*s)
196 return append(in, byte(v>>56), byte(v>>48), byte(v>>40), byte(v>>32), byte(v>>24), byte(v>>16), byte(v>>8), byte(v))
197 }
198
199 func (s *sum128) Sum(in []byte) []byte {
200 return append(in,
201 byte(s[0]>>56), byte(s[0]>>48), byte(s[0]>>40), byte(s[0]>>32), byte(s[0]>>24), byte(s[0]>>16), byte(s[0]>>8), byte(s[0]),
202 byte(s[1]>>56), byte(s[1]>>48), byte(s[1]>>40), byte(s[1]>>32), byte(s[1]>>24), byte(s[1]>>16), byte(s[1]>>8), byte(s[1]),
203 )
204 }
205
206 func (s *sum128a) Sum(in []byte) []byte {
207 return append(in,
208 byte(s[0]>>56), byte(s[0]>>48), byte(s[0]>>40), byte(s[0]>>32), byte(s[0]>>24), byte(s[0]>>16), byte(s[0]>>8), byte(s[0]),
209 byte(s[1]>>56), byte(s[1]>>48), byte(s[1]>>40), byte(s[1]>>32), byte(s[1]>>24), byte(s[1]>>16), byte(s[1]>>8), byte(s[1]),
210 )
211 }
212
213 const (
214 magic32 = "fnv\x01"
215 magic32a = "fnv\x02"
216 magic64 = "fnv\x03"
217 magic64a = "fnv\x04"
218 magic128 = "fnv\x05"
219 magic128a = "fnv\x06"
220 marshaledSize32 = len(magic32) + 4
221 marshaledSize64 = len(magic64) + 8
222 marshaledSize128 = len(magic128) + 8*2
223 )
224
225 func (s *sum32) MarshalBinary() ([]byte, error) {
226 b := make([]byte, 0, marshaledSize32)
227 b = append(b, magic32...)
228 b = appendUint32(b, uint32(*s))
229 return b, nil
230 }
231
232 func (s *sum32a) MarshalBinary() ([]byte, error) {
233 b := make([]byte, 0, marshaledSize32)
234 b = append(b, magic32a...)
235 b = appendUint32(b, uint32(*s))
236 return b, nil
237 }
238
239 func (s *sum64) MarshalBinary() ([]byte, error) {
240 b := make([]byte, 0, marshaledSize64)
241 b = append(b, magic64...)
242 b = appendUint64(b, uint64(*s))
243 return b, nil
244
245 }
246
247 func (s *sum64a) MarshalBinary() ([]byte, error) {
248 b := make([]byte, 0, marshaledSize64)
249 b = append(b, magic64a...)
250 b = appendUint64(b, uint64(*s))
251 return b, nil
252 }
253
254 func (s *sum128) MarshalBinary() ([]byte, error) {
255 b := make([]byte, 0, marshaledSize128)
256 b = append(b, magic128...)
257 b = appendUint64(b, s[0])
258 b = appendUint64(b, s[1])
259 return b, nil
260 }
261
262 func (s *sum128a) MarshalBinary() ([]byte, error) {
263 b := make([]byte, 0, marshaledSize128)
264 b = append(b, magic128a...)
265 b = appendUint64(b, s[0])
266 b = appendUint64(b, s[1])
267 return b, nil
268 }
269
270 func (s *sum32) UnmarshalBinary(b []byte) error {
271 if len(b) < len(magic32) || string(b[:len(magic32)]) != magic32 {
272 return errors.New("hash/fnv: invalid hash state identifier")
273 }
274 if len(b) != marshaledSize32 {
275 return errors.New("hash/fnv: invalid hash state size")
276 }
277 *s = sum32(readUint32(b[4:]))
278 return nil
279 }
280
281 func (s *sum32a) UnmarshalBinary(b []byte) error {
282 if len(b) < len(magic32a) || string(b[:len(magic32a)]) != magic32a {
283 return errors.New("hash/fnv: invalid hash state identifier")
284 }
285 if len(b) != marshaledSize32 {
286 return errors.New("hash/fnv: invalid hash state size")
287 }
288 *s = sum32a(readUint32(b[4:]))
289 return nil
290 }
291
292 func (s *sum64) UnmarshalBinary(b []byte) error {
293 if len(b) < len(magic64) || string(b[:len(magic64)]) != magic64 {
294 return errors.New("hash/fnv: invalid hash state identifier")
295 }
296 if len(b) != marshaledSize64 {
297 return errors.New("hash/fnv: invalid hash state size")
298 }
299 *s = sum64(readUint64(b[4:]))
300 return nil
301 }
302
303 func (s *sum64a) UnmarshalBinary(b []byte) error {
304 if len(b) < len(magic64a) || string(b[:len(magic64a)]) != magic64a {
305 return errors.New("hash/fnv: invalid hash state identifier")
306 }
307 if len(b) != marshaledSize64 {
308 return errors.New("hash/fnv: invalid hash state size")
309 }
310 *s = sum64a(readUint64(b[4:]))
311 return nil
312 }
313
314 func (s *sum128) UnmarshalBinary(b []byte) error {
315 if len(b) < len(magic128) || string(b[:len(magic128)]) != magic128 {
316 return errors.New("hash/fnv: invalid hash state identifier")
317 }
318 if len(b) != marshaledSize128 {
319 return errors.New("hash/fnv: invalid hash state size")
320 }
321 s[0] = readUint64(b[4:])
322 s[1] = readUint64(b[12:])
323 return nil
324 }
325
326 func (s *sum128a) UnmarshalBinary(b []byte) error {
327 if len(b) < len(magic128a) || string(b[:len(magic128a)]) != magic128a {
328 return errors.New("hash/fnv: invalid hash state identifier")
329 }
330 if len(b) != marshaledSize128 {
331 return errors.New("hash/fnv: invalid hash state size")
332 }
333 s[0] = readUint64(b[4:])
334 s[1] = readUint64(b[12:])
335 return nil
336 }
337
338 func readUint32(b []byte) uint32 {
339 _ = b[3]
340 return uint32(b[3]) | uint32(b[2])<<8 | uint32(b[1])<<16 | uint32(b[0])<<24
341 }
342
343 func appendUint32(b []byte, x uint32) []byte {
344 a := [4]byte{
345 byte(x >> 24),
346 byte(x >> 16),
347 byte(x >> 8),
348 byte(x),
349 }
350 return append(b, a[:]...)
351 }
352
353 func appendUint64(b []byte, x uint64) []byte {
354 a := [8]byte{
355 byte(x >> 56),
356 byte(x >> 48),
357 byte(x >> 40),
358 byte(x >> 32),
359 byte(x >> 24),
360 byte(x >> 16),
361 byte(x >> 8),
362 byte(x),
363 }
364 return append(b, a[:]...)
365 }
366
367 func readUint64(b []byte) uint64 {
368 _ = b[7]
369 return uint64(b[7]) | uint64(b[6])<<8 | uint64(b[5])<<16 | uint64(b[4])<<24 |
370 uint64(b[3])<<32 | uint64(b[2])<<40 | uint64(b[1])<<48 | uint64(b[0])<<56
371 }
372
View as plain text