libgo/go/hash/fnv/fnv.go

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