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	"internal/byteorder"
19	"math/bits"
20)
21
22type (
23	sum32   uint32
24	sum32a  uint32
25	sum64   uint64
26	sum64a  uint64
27	sum128  [2]uint64
28	sum128a [2]uint64
29)
30
31const (
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.
44func 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.
51func 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.
58func 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.
65func 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.
72func 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.
81func New128a() hash.Hash {
82	var s sum128a
83	s[0] = offset128Higher
84	s[1] = offset128Lower
85	return &s
86}
87
88func (s *sum32) Reset()   { *s = offset32 }
89func (s *sum32a) Reset()  { *s = offset32 }
90func (s *sum64) Reset()   { *s = offset64 }
91func (s *sum64a) Reset()  { *s = offset64 }
92func (s *sum128) Reset()  { s[0] = offset128Higher; s[1] = offset128Lower }
93func (s *sum128a) Reset() { s[0] = offset128Higher; s[1] = offset128Lower }
94
95func (s *sum32) Sum32() uint32  { return uint32(*s) }
96func (s *sum32a) Sum32() uint32 { return uint32(*s) }
97func (s *sum64) Sum64() uint64  { return uint64(*s) }
98func (s *sum64a) Sum64() uint64 { return uint64(*s) }
99
100func (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
110func (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
120func (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
130func (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
140func (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
153func (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
166func (s *sum32) Size() int   { return 4 }
167func (s *sum32a) Size() int  { return 4 }
168func (s *sum64) Size() int   { return 8 }
169func (s *sum64a) Size() int  { return 8 }
170func (s *sum128) Size() int  { return 16 }
171func (s *sum128a) Size() int { return 16 }
172
173func (s *sum32) BlockSize() int   { return 1 }
174func (s *sum32a) BlockSize() int  { return 1 }
175func (s *sum64) BlockSize() int   { return 1 }
176func (s *sum64a) BlockSize() int  { return 1 }
177func (s *sum128) BlockSize() int  { return 1 }
178func (s *sum128a) BlockSize() int { return 1 }
179
180func (s *sum32) Sum(in []byte) []byte {
181	v := uint32(*s)
182	return byteorder.BeAppendUint32(in, v)
183}
184
185func (s *sum32a) Sum(in []byte) []byte {
186	v := uint32(*s)
187	return byteorder.BeAppendUint32(in, v)
188}
189
190func (s *sum64) Sum(in []byte) []byte {
191	v := uint64(*s)
192	return byteorder.BeAppendUint64(in, v)
193}
194
195func (s *sum64a) Sum(in []byte) []byte {
196	v := uint64(*s)
197	return byteorder.BeAppendUint64(in, v)
198}
199
200func (s *sum128) Sum(in []byte) []byte {
201	ret := byteorder.BeAppendUint64(in, s[0])
202	return byteorder.BeAppendUint64(ret, s[1])
203}
204
205func (s *sum128a) Sum(in []byte) []byte {
206	ret := byteorder.BeAppendUint64(in, s[0])
207	return byteorder.BeAppendUint64(ret, s[1])
208}
209
210const (
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
222func (s *sum32) MarshalBinary() ([]byte, error) {
223	b := make([]byte, 0, marshaledSize32)
224	b = append(b, magic32...)
225	b = byteorder.BeAppendUint32(b, uint32(*s))
226	return b, nil
227}
228
229func (s *sum32a) MarshalBinary() ([]byte, error) {
230	b := make([]byte, 0, marshaledSize32)
231	b = append(b, magic32a...)
232	b = byteorder.BeAppendUint32(b, uint32(*s))
233	return b, nil
234}
235
236func (s *sum64) MarshalBinary() ([]byte, error) {
237	b := make([]byte, 0, marshaledSize64)
238	b = append(b, magic64...)
239	b = byteorder.BeAppendUint64(b, uint64(*s))
240	return b, nil
241}
242
243func (s *sum64a) MarshalBinary() ([]byte, error) {
244	b := make([]byte, 0, marshaledSize64)
245	b = append(b, magic64a...)
246	b = byteorder.BeAppendUint64(b, uint64(*s))
247	return b, nil
248}
249
250func (s *sum128) MarshalBinary() ([]byte, error) {
251	b := make([]byte, 0, marshaledSize128)
252	b = append(b, magic128...)
253	b = byteorder.BeAppendUint64(b, s[0])
254	b = byteorder.BeAppendUint64(b, s[1])
255	return b, nil
256}
257
258func (s *sum128a) MarshalBinary() ([]byte, error) {
259	b := make([]byte, 0, marshaledSize128)
260	b = append(b, magic128a...)
261	b = byteorder.BeAppendUint64(b, s[0])
262	b = byteorder.BeAppendUint64(b, s[1])
263	return b, nil
264}
265
266func (s *sum32) UnmarshalBinary(b []byte) error {
267	if len(b) < len(magic32) || string(b[:len(magic32)]) != magic32 {
268		return errors.New("hash/fnv: invalid hash state identifier")
269	}
270	if len(b) != marshaledSize32 {
271		return errors.New("hash/fnv: invalid hash state size")
272	}
273	*s = sum32(byteorder.BeUint32(b[4:]))
274	return nil
275}
276
277func (s *sum32a) UnmarshalBinary(b []byte) error {
278	if len(b) < len(magic32a) || string(b[:len(magic32a)]) != magic32a {
279		return errors.New("hash/fnv: invalid hash state identifier")
280	}
281	if len(b) != marshaledSize32 {
282		return errors.New("hash/fnv: invalid hash state size")
283	}
284	*s = sum32a(byteorder.BeUint32(b[4:]))
285	return nil
286}
287
288func (s *sum64) UnmarshalBinary(b []byte) error {
289	if len(b) < len(magic64) || string(b[:len(magic64)]) != magic64 {
290		return errors.New("hash/fnv: invalid hash state identifier")
291	}
292	if len(b) != marshaledSize64 {
293		return errors.New("hash/fnv: invalid hash state size")
294	}
295	*s = sum64(byteorder.BeUint64(b[4:]))
296	return nil
297}
298
299func (s *sum64a) UnmarshalBinary(b []byte) error {
300	if len(b) < len(magic64a) || string(b[:len(magic64a)]) != magic64a {
301		return errors.New("hash/fnv: invalid hash state identifier")
302	}
303	if len(b) != marshaledSize64 {
304		return errors.New("hash/fnv: invalid hash state size")
305	}
306	*s = sum64a(byteorder.BeUint64(b[4:]))
307	return nil
308}
309
310func (s *sum128) UnmarshalBinary(b []byte) error {
311	if len(b) < len(magic128) || string(b[:len(magic128)]) != magic128 {
312		return errors.New("hash/fnv: invalid hash state identifier")
313	}
314	if len(b) != marshaledSize128 {
315		return errors.New("hash/fnv: invalid hash state size")
316	}
317	s[0] = byteorder.BeUint64(b[4:])
318	s[1] = byteorder.BeUint64(b[12:])
319	return nil
320}
321
322func (s *sum128a) UnmarshalBinary(b []byte) error {
323	if len(b) < len(magic128a) || string(b[:len(magic128a)]) != magic128a {
324		return errors.New("hash/fnv: invalid hash state identifier")
325	}
326	if len(b) != marshaledSize128 {
327		return errors.New("hash/fnv: invalid hash state size")
328	}
329	s[0] = byteorder.BeUint64(b[4:])
330	s[1] = byteorder.BeUint64(b[12:])
331	return nil
332}
333