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  	"internal/byteorder"
    19  	"math/bits"
    20  )
    21  
    22  type (
    23  	sum32   uint32
    24  	sum32a  uint32
    25  	sum64   uint64
    26  	sum64a  uint64
    27  	sum128  [2]uint64
    28  	sum128a [2]uint64
    29  )
    30  
    31  const (
    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.
    44  func 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.
    51  func 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.
    58  func 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.
    65  func 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.
    72  func 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.
    81  func New128a() hash.Hash {
    82  	var s sum128a
    83  	s[0] = offset128Higher
    84  	s[1] = offset128Lower
    85  	return &s
    86  }
    87  
    88  func (s *sum32) Reset()   { *s = offset32 }
    89  func (s *sum32a) Reset()  { *s = offset32 }
    90  func (s *sum64) Reset()   { *s = offset64 }
    91  func (s *sum64a) Reset()  { *s = offset64 }
    92  func (s *sum128) Reset()  { s[0] = offset128Higher; s[1] = offset128Lower }
    93  func (s *sum128a) Reset() { s[0] = offset128Higher; s[1] = offset128Lower }
    94  
    95  func (s *sum32) Sum32() uint32  { return uint32(*s) }
    96  func (s *sum32a) Sum32() uint32 { return uint32(*s) }
    97  func (s *sum64) Sum64() uint64  { return uint64(*s) }
    98  func (s *sum64a) Sum64() uint64 { return uint64(*s) }
    99  
   100  func (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  
   110  func (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  
   120  func (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  
   130  func (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  
   140  func (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  
   153  func (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  
   166  func (s *sum32) Size() int   { return 4 }
   167  func (s *sum32a) Size() int  { return 4 }
   168  func (s *sum64) Size() int   { return 8 }
   169  func (s *sum64a) Size() int  { return 8 }
   170  func (s *sum128) Size() int  { return 16 }
   171  func (s *sum128a) Size() int { return 16 }
   172  
   173  func (s *sum32) BlockSize() int   { return 1 }
   174  func (s *sum32a) BlockSize() int  { return 1 }
   175  func (s *sum64) BlockSize() int   { return 1 }
   176  func (s *sum64a) BlockSize() int  { return 1 }
   177  func (s *sum128) BlockSize() int  { return 1 }
   178  func (s *sum128a) BlockSize() int { return 1 }
   179  
   180  func (s *sum32) Sum(in []byte) []byte {
   181  	v := uint32(*s)
   182  	return byteorder.BeAppendUint32(in, v)
   183  }
   184  
   185  func (s *sum32a) Sum(in []byte) []byte {
   186  	v := uint32(*s)
   187  	return byteorder.BeAppendUint32(in, v)
   188  }
   189  
   190  func (s *sum64) Sum(in []byte) []byte {
   191  	v := uint64(*s)
   192  	return byteorder.BeAppendUint64(in, v)
   193  }
   194  
   195  func (s *sum64a) Sum(in []byte) []byte {
   196  	v := uint64(*s)
   197  	return byteorder.BeAppendUint64(in, v)
   198  }
   199  
   200  func (s *sum128) Sum(in []byte) []byte {
   201  	ret := byteorder.BeAppendUint64(in, s[0])
   202  	return byteorder.BeAppendUint64(ret, s[1])
   203  }
   204  
   205  func (s *sum128a) Sum(in []byte) []byte {
   206  	ret := byteorder.BeAppendUint64(in, s[0])
   207  	return byteorder.BeAppendUint64(ret, s[1])
   208  }
   209  
   210  const (
   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  
   222  func (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  
   229  func (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  
   236  func (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  
   243  func (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  
   250  func (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  
   258  func (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  
   266  func (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  
   277  func (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  
   288  func (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  
   299  func (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  
   310  func (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  
   322  func (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
View as plain text