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