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.
13package fnv
14
15import (
16	"errors"
17	"hash"
18	"math/bits"
19)
20
21type (
22	sum32   uint32
23	sum32a  uint32
24	sum64   uint64
25	sum64a  uint64
26	sum128  [2]uint64
27	sum128a [2]uint64
28)
29
30const (
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// New32 returns a new 32-bit FNV-1 hash.Hash.
42// Its Sum method will lay the value out in big-endian byte order.
43func New32() hash.Hash32 {
44	var s sum32 = offset32
45	return &s
46}
47
48// New32a returns a new 32-bit FNV-1a hash.Hash.
49// Its Sum method will lay the value out in big-endian byte order.
50func New32a() hash.Hash32 {
51	var s sum32a = offset32
52	return &s
53}
54
55// New64 returns a new 64-bit FNV-1 hash.Hash.
56// Its Sum method will lay the value out in big-endian byte order.
57func New64() hash.Hash64 {
58	var s sum64 = offset64
59	return &s
60}
61
62// New64a returns a new 64-bit FNV-1a hash.Hash.
63// Its Sum method will lay the value out in big-endian byte order.
64func New64a() hash.Hash64 {
65	var s sum64a = offset64
66	return &s
67}
68
69// New128 returns a new 128-bit FNV-1 hash.Hash.
70// Its Sum method will lay the value out in big-endian byte order.
71func New128() hash.Hash {
72	var s sum128
73	s[0] = offset128Higher
74	s[1] = offset128Lower
75	return &s
76}
77
78// New128a returns a new 128-bit FNV-1a hash.Hash.
79// Its Sum method will lay the value out in big-endian byte order.
80func New128a() hash.Hash {
81	var s sum128a
82	s[0] = offset128Higher
83	s[1] = offset128Lower
84	return &s
85}
86
87func (s *sum32) Reset()   { *s = offset32 }
88func (s *sum32a) Reset()  { *s = offset32 }
89func (s *sum64) Reset()   { *s = offset64 }
90func (s *sum64a) Reset()  { *s = offset64 }
91func (s *sum128) Reset()  { s[0] = offset128Higher; s[1] = offset128Lower }
92func (s *sum128a) Reset() { s[0] = offset128Higher; s[1] = offset128Lower }
93
94func (s *sum32) Sum32() uint32  { return uint32(*s) }
95func (s *sum32a) Sum32() uint32 { return uint32(*s) }
96func (s *sum64) Sum64() uint64  { return uint64(*s) }
97func (s *sum64a) Sum64() uint64 { return uint64(*s) }
98
99func (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
109func (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
119func (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
129func (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
139func (s *sum128) Write(data []byte) (int, error) {
140	for _, c := range data {
141		// Compute the multiplication
142		s0, s1 := bits.Mul64(prime128Lower, s[1])
143		s0 += s[1]<<prime128Shift + prime128Lower*s[0]
144		// Update the values
145		s[1] = s1
146		s[0] = s0
147		s[1] ^= uint64(c)
148	}
149	return len(data), nil
150}
151
152func (s *sum128a) Write(data []byte) (int, error) {
153	for _, c := range data {
154		s[1] ^= uint64(c)
155		// Compute the multiplication
156		s0, s1 := bits.Mul64(prime128Lower, s[1])
157		s0 += s[1]<<prime128Shift + prime128Lower*s[0]
158		// Update the values
159		s[1] = s1
160		s[0] = s0
161	}
162	return len(data), nil
163}
164
165func (s *sum32) Size() int   { return 4 }
166func (s *sum32a) Size() int  { return 4 }
167func (s *sum64) Size() int   { return 8 }
168func (s *sum64a) Size() int  { return 8 }
169func (s *sum128) Size() int  { return 16 }
170func (s *sum128a) Size() int { return 16 }
171
172func (s *sum32) BlockSize() int   { return 1 }
173func (s *sum32a) BlockSize() int  { return 1 }
174func (s *sum64) BlockSize() int   { return 1 }
175func (s *sum64a) BlockSize() int  { return 1 }
176func (s *sum128) BlockSize() int  { return 1 }
177func (s *sum128a) BlockSize() int { return 1 }
178
179func (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
184func (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
189func (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
194func (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
199func (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
206func (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
213const (
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
225func (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
232func (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
239func (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
247func (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
254func (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
262func (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
270func (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
281func (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
292func (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
303func (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
314func (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
326func (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
338func 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
343func 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
353func 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
367func 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