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         "math/bits"
  19 )
  20
  21 type (
  22         sum32   uint32
  23         sum32a  uint32
  24         sum64   uint64
  25         sum64a  uint64
  26         sum128  [2]uint64
  27         sum128a [2]uint64
  28 )
  29
  30 const (
  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.
  43 func 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.
  50 func 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.
  57 func 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.
  64 func 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.
  71 func 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.
  80 func New128a() hash.Hash {
  81         var s sum128a
  82         s[0] = offset128Higher
  83         s[1] = offset128Lower
  84         return &s
  85 }
  86
  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 }
  93
  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) }
  98
  99 func (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
 109 func (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
 119 func (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
 129 func (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
 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]
 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
 152 func (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
 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 }
 171
 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 }
 178
 179 func (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
 184 func (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
 189 func (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
 194 func (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
 199 func (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
 206 func (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
 213 const (
 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
 225 func (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
 232 func (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
 239 func (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
 247 func (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
 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])
 259         return b, nil
 260 }
 261
 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])
 267         return b, nil
 268 }
 269
 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")
 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
 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")
 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
 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")
 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
 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")
 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
 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")
 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
 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")
 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
 338 func 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
 343 func 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
 353 func 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
 367 func 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 }