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  }
   372
View as plain text