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.
5 // Package fnv implements FNV-1 and FNV-1a, non-cryptographic hash functions
6 // created by Glenn Fowler, Landon Curt Noll, and Phong Vo.
8 // https://en.wikipedia.org/wiki/Fowler-Noll-Vo_hash_function.
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.
32 offset64
= 14695981039346656037
33 offset128Lower
= 0x62b821756295c58d
34 offset128Higher
= 0x6c62272e07bb0142
36 prime64
= 1099511628211
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.
43 func New32() hash
.Hash32
{
44 var s sum32
= offset32
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.
50 func New32a() hash
.Hash32
{
51 var s sum32a
= offset32
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.
57 func New64() hash
.Hash64
{
58 var s sum64
= offset64
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.
64 func New64a() hash
.Hash64
{
65 var s sum64a
= offset64
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.
71 func New128() hash
.Hash
{
73 s
[0] = offset128Higher
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.
80 func New128a() hash
.Hash
{
82 s
[0] = offset128Higher
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
}
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
) }
99 func (s
*sum32
) Write(data
[]byte) (int, error
) {
101 for _
, c
:= range data
{
106 return len(data
), nil
109 func (s
*sum32a
) Write(data
[]byte) (int, error
) {
111 for _
, c
:= range data
{
116 return len(data
), nil
119 func (s
*sum64
) Write(data
[]byte) (int, error
) {
121 for _
, c
:= range data
{
126 return len(data
), nil
129 func (s
*sum64a
) Write(data
[]byte) (int, error
) {
131 for _
, c
:= range data
{
136 return len(data
), nil
139 func (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]
149 return len(data
), nil
152 func (s
*sum128a
) Write(data
[]byte) (int, error
) {
153 for _
, c
:= range data
{
155 // Compute the multiplication
156 s0
, s1
:= bits
.Mul64(prime128Lower
, s
[1])
157 s0
+= s
[1]<<prime128Shift
+ prime128Lower
*s
[0]
162 return len(data
), nil
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 }
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 }
179 func (s
*sum32
) Sum(in
[]byte) []byte {
181 return append(in
, byte(v
>>24), byte(v
>>16), byte(v
>>8), byte(v
))
184 func (s
*sum32a
) Sum(in
[]byte) []byte {
186 return append(in
, byte(v
>>24), byte(v
>>16), byte(v
>>8), byte(v
))
189 func (s
*sum64
) Sum(in
[]byte) []byte {
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
))
194 func (s
*sum64a
) Sum(in
[]byte) []byte {
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
))
199 func (s
*sum128
) Sum(in
[]byte) []byte {
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]),
206 func (s
*sum128a
) Sum(in
[]byte) []byte {
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]),
219 magic128a
= "fnv\x06"
220 marshaledSize32
= len(magic32
) + 4
221 marshaledSize64
= len(magic64
) + 8
222 marshaledSize128
= len(magic128
) + 8*2
225 func (s
*sum32
) MarshalBinary() ([]byte, error
) {
226 b
:= make([]byte, 0, marshaledSize32
)
227 b
= append(b
, magic32
...)
228 b
= appendUint32(b
, uint32(*s
))
232 func (s
*sum32a
) MarshalBinary() ([]byte, error
) {
233 b
:= make([]byte, 0, marshaledSize32
)
234 b
= append(b
, magic32a
...)
235 b
= appendUint32(b
, uint32(*s
))
239 func (s
*sum64
) MarshalBinary() ([]byte, error
) {
240 b
:= make([]byte, 0, marshaledSize64
)
241 b
= append(b
, magic64
...)
242 b
= appendUint64(b
, uint64(*s
))
247 func (s
*sum64a
) MarshalBinary() ([]byte, error
) {
248 b
:= make([]byte, 0, marshaledSize64
)
249 b
= append(b
, magic64a
...)
250 b
= appendUint64(b
, uint64(*s
))
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])
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])
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")
274 if len(b
) != marshaledSize32
{
275 return errors
.New("hash/fnv: invalid hash state size")
277 *s
= sum32(readUint32(b
[4:]))
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")
285 if len(b
) != marshaledSize32
{
286 return errors
.New("hash/fnv: invalid hash state size")
288 *s
= sum32a(readUint32(b
[4:]))
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")
296 if len(b
) != marshaledSize64
{
297 return errors
.New("hash/fnv: invalid hash state size")
299 *s
= sum64(readUint64(b
[4:]))
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")
307 if len(b
) != marshaledSize64
{
308 return errors
.New("hash/fnv: invalid hash state size")
310 *s
= sum64a(readUint64(b
[4:]))
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")
318 if len(b
) != marshaledSize128
{
319 return errors
.New("hash/fnv: invalid hash state size")
321 s
[0] = readUint64(b
[4:])
322 s
[1] = readUint64(b
[12:])
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")
330 if len(b
) != marshaledSize128
{
331 return errors
.New("hash/fnv: invalid hash state size")
333 s
[0] = readUint64(b
[4:])
334 s
[1] = readUint64(b
[12:])
338 func readUint32(b
[]byte) uint32 {
340 return uint32(b
[3]) |
uint32(b
[2])<<8 |
uint32(b
[1])<<16 |
uint32(b
[0])<<24
343 func appendUint32(b
[]byte, x
uint32) []byte {
350 return append(b
, a
[:]...)
353 func appendUint64(b
[]byte, x
uint64) []byte {
364 return append(b
, a
[:]...)
367 func readUint64(b
[]byte) uint64 {
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