fnv.go

Documentation: hash/fnv

     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  func (s *sum64a) MarshalBinary() ([]byte, error) {
   247  	b := make([]byte, 0, marshaledSize64)
   248  	b = append(b, magic64a...)
   249  	b = appendUint64(b, uint64(*s))
   250  	return b, nil
   251  }
   252  
   253  func (s *sum128) MarshalBinary() ([]byte, error) {
   254  	b := make([]byte, 0, marshaledSize128)
   255  	b = append(b, magic128...)
   256  	b = appendUint64(b, s[0])
   257  	b = appendUint64(b, s[1])
   258  	return b, nil
   259  }
   260  
   261  func (s *sum128a) MarshalBinary() ([]byte, error) {
   262  	b := make([]byte, 0, marshaledSize128)
   263  	b = append(b, magic128a...)
   264  	b = appendUint64(b, s[0])
   265  	b = appendUint64(b, s[1])
   266  	return b, nil
   267  }
   268  
   269  func (s *sum32) UnmarshalBinary(b []byte) error {
   270  	if len(b) < len(magic32) || string(b[:len(magic32)]) != magic32 {
   271  		return errors.New("hash/fnv: invalid hash state identifier")
   272  	}
   273  	if len(b) != marshaledSize32 {
   274  		return errors.New("hash/fnv: invalid hash state size")
   275  	}
   276  	*s = sum32(readUint32(b[4:]))
   277  	return nil
   278  }
   279  
   280  func (s *sum32a) UnmarshalBinary(b []byte) error {
   281  	if len(b) < len(magic32a) || string(b[:len(magic32a)]) != magic32a {
   282  		return errors.New("hash/fnv: invalid hash state identifier")
   283  	}
   284  	if len(b) != marshaledSize32 {
   285  		return errors.New("hash/fnv: invalid hash state size")
   286  	}
   287  	*s = sum32a(readUint32(b[4:]))
   288  	return nil
   289  }
   290  
   291  func (s *sum64) UnmarshalBinary(b []byte) error {
   292  	if len(b) < len(magic64) || string(b[:len(magic64)]) != magic64 {
   293  		return errors.New("hash/fnv: invalid hash state identifier")
   294  	}
   295  	if len(b) != marshaledSize64 {
   296  		return errors.New("hash/fnv: invalid hash state size")
   297  	}
   298  	*s = sum64(readUint64(b[4:]))
   299  	return nil
   300  }
   301  
   302  func (s *sum64a) UnmarshalBinary(b []byte) error {
   303  	if len(b) < len(magic64a) || string(b[:len(magic64a)]) != magic64a {
   304  		return errors.New("hash/fnv: invalid hash state identifier")
   305  	}
   306  	if len(b) != marshaledSize64 {
   307  		return errors.New("hash/fnv: invalid hash state size")
   308  	}
   309  	*s = sum64a(readUint64(b[4:]))
   310  	return nil
   311  }
   312  
   313  func (s *sum128) UnmarshalBinary(b []byte) error {
   314  	if len(b) < len(magic128) || string(b[:len(magic128)]) != magic128 {
   315  		return errors.New("hash/fnv: invalid hash state identifier")
   316  	}
   317  	if len(b) != marshaledSize128 {
   318  		return errors.New("hash/fnv: invalid hash state size")
   319  	}
   320  	s[0] = readUint64(b[4:])
   321  	s[1] = readUint64(b[12:])
   322  	return nil
   323  }
   324  
   325  func (s *sum128a) UnmarshalBinary(b []byte) error {
   326  	if len(b) < len(magic128a) || string(b[:len(magic128a)]) != magic128a {
   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  // readUint32 is semantically the same as [binary.BigEndian.Uint32]
   338  // We copied this function because we can not import "encoding/binary" here.
   339  func readUint32(b []byte) uint32 {
   340  	_ = b[3]
   341  	return uint32(b[3]) | uint32(b[2])<<8 | uint32(b[1])<<16 | uint32(b[0])<<24
   342  }
   343  
   344  // appendUint32 is semantically the same as [binary.BigEndian.AppendUint32]
   345  // We copied this function because we can not import "encoding/binary" here.
   346  func appendUint32(b []byte, x uint32) []byte {
   347  	return append(b,
   348  		byte(x>>24),
   349  		byte(x>>16),
   350  		byte(x>>8),
   351  		byte(x),
   352  	)
   353  }
   354  
   355  // appendUint64 is semantically the same as [binary.BigEndian.AppendUint64]
   356  // We copied this function because we can not import "encoding/binary" here.
   357  func appendUint64(b []byte, x uint64) []byte {
   358  	return append(b,
   359  		byte(x>>56),
   360  		byte(x>>48),
   361  		byte(x>>40),
   362  		byte(x>>32),
   363  		byte(x>>24),
   364  		byte(x>>16),
   365  		byte(x>>8),
   366  		byte(x),
   367  	)
   368  }
   369  
   370  // readUint64 is semantically the same as [binary.BigEndian.Uint64]
   371  // We copied this function because we can not import "encoding/binary" here.
   372  func readUint64(b []byte) uint64 {
   373  	_ = b[7]
   374  	return uint64(b[7]) | uint64(b[6])<<8 | uint64(b[5])<<16 | uint64(b[4])<<24 |
   375  		uint64(b[3])<<32 | uint64(b[2])<<40 | uint64(b[1])<<48 | uint64(b[0])<<56
   376  }
   377
View as plain text