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) AppendBinary(b []byte) ([]byte, error) {
   223  	b = append(b, magic32...)
   224  	b = byteorder.BeAppendUint32(b, uint32(*s))
   225  	return b, nil
   226  }
   227  
   228  func (s *sum32) MarshalBinary() ([]byte, error) {
   229  	return s.AppendBinary(make([]byte, 0, marshaledSize32))
   230  }
   231  
   232  func (s *sum32a) AppendBinary(b []byte) ([]byte, error) {
   233  	b = append(b, magic32a...)
   234  	b = byteorder.BeAppendUint32(b, uint32(*s))
   235  	return b, nil
   236  }
   237  
   238  func (s *sum32a) MarshalBinary() ([]byte, error) {
   239  	return s.AppendBinary(make([]byte, 0, marshaledSize32))
   240  }
   241  
   242  func (s *sum64) AppendBinary(b []byte) ([]byte, error) {
   243  	b = append(b, magic64...)
   244  	b = byteorder.BeAppendUint64(b, uint64(*s))
   245  	return b, nil
   246  }
   247  
   248  func (s *sum64) MarshalBinary() ([]byte, error) {
   249  	return s.AppendBinary(make([]byte, 0, marshaledSize64))
   250  }
   251  
   252  func (s *sum64a) AppendBinary(b []byte) ([]byte, error) {
   253  	b = append(b, magic64a...)
   254  	b = byteorder.BeAppendUint64(b, uint64(*s))
   255  	return b, nil
   256  }
   257  
   258  func (s *sum64a) MarshalBinary() ([]byte, error) {
   259  	return s.AppendBinary(make([]byte, 0, marshaledSize64))
   260  }
   261  
   262  func (s *sum128) AppendBinary(b []byte) ([]byte, error) {
   263  	b = append(b, magic128...)
   264  	b = byteorder.BeAppendUint64(b, s[0])
   265  	b = byteorder.BeAppendUint64(b, s[1])
   266  	return b, nil
   267  }
   268  
   269  func (s *sum128) MarshalBinary() ([]byte, error) {
   270  	return s.AppendBinary(make([]byte, 0, marshaledSize128))
   271  }
   272  
   273  func (s *sum128a) AppendBinary(b []byte) ([]byte, error) {
   274  	b = append(b, magic128a...)
   275  	b = byteorder.BeAppendUint64(b, s[0])
   276  	b = byteorder.BeAppendUint64(b, s[1])
   277  	return b, nil
   278  }
   279  
   280  func (s *sum128a) MarshalBinary() ([]byte, error) {
   281  	return s.AppendBinary(make([]byte, 0, marshaledSize128))
   282  }
   283  
   284  func (s *sum32) UnmarshalBinary(b []byte) error {
   285  	if len(b) < len(magic32) || string(b[:len(magic32)]) != magic32 {
   286  		return errors.New("hash/fnv: invalid hash state identifier")
   287  	}
   288  	if len(b) != marshaledSize32 {
   289  		return errors.New("hash/fnv: invalid hash state size")
   290  	}
   291  	*s = sum32(byteorder.BeUint32(b[4:]))
   292  	return nil
   293  }
   294  
   295  func (s *sum32a) UnmarshalBinary(b []byte) error {
   296  	if len(b) < len(magic32a) || string(b[:len(magic32a)]) != magic32a {
   297  		return errors.New("hash/fnv: invalid hash state identifier")
   298  	}
   299  	if len(b) != marshaledSize32 {
   300  		return errors.New("hash/fnv: invalid hash state size")
   301  	}
   302  	*s = sum32a(byteorder.BeUint32(b[4:]))
   303  	return nil
   304  }
   305  
   306  func (s *sum64) UnmarshalBinary(b []byte) error {
   307  	if len(b) < len(magic64) || string(b[:len(magic64)]) != magic64 {
   308  		return errors.New("hash/fnv: invalid hash state identifier")
   309  	}
   310  	if len(b) != marshaledSize64 {
   311  		return errors.New("hash/fnv: invalid hash state size")
   312  	}
   313  	*s = sum64(byteorder.BeUint64(b[4:]))
   314  	return nil
   315  }
   316  
   317  func (s *sum64a) UnmarshalBinary(b []byte) error {
   318  	if len(b) < len(magic64a) || string(b[:len(magic64a)]) != magic64a {
   319  		return errors.New("hash/fnv: invalid hash state identifier")
   320  	}
   321  	if len(b) != marshaledSize64 {
   322  		return errors.New("hash/fnv: invalid hash state size")
   323  	}
   324  	*s = sum64a(byteorder.BeUint64(b[4:]))
   325  	return nil
   326  }
   327  
   328  func (s *sum128) UnmarshalBinary(b []byte) error {
   329  	if len(b) < len(magic128) || string(b[:len(magic128)]) != magic128 {
   330  		return errors.New("hash/fnv: invalid hash state identifier")
   331  	}
   332  	if len(b) != marshaledSize128 {
   333  		return errors.New("hash/fnv: invalid hash state size")
   334  	}
   335  	s[0] = byteorder.BeUint64(b[4:])
   336  	s[1] = byteorder.BeUint64(b[12:])
   337  	return nil
   338  }
   339  
   340  func (s *sum128a) UnmarshalBinary(b []byte) error {
   341  	if len(b) < len(magic128a) || string(b[:len(magic128a)]) != magic128a {
   342  		return errors.New("hash/fnv: invalid hash state identifier")
   343  	}
   344  	if len(b) != marshaledSize128 {
   345  		return errors.New("hash/fnv: invalid hash state size")
   346  	}
   347  	s[0] = byteorder.BeUint64(b[4:])
   348  	s[1] = byteorder.BeUint64(b[12:])
   349  	return nil
   350  }
   351
View as plain text