...
Run Format

Source file src/hash/fnv/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  )
    19  
    20  type (
    21  	sum32   uint32
    22  	sum32a  uint32
    23  	sum64   uint64
    24  	sum64a  uint64
    25  	sum128  [2]uint64
    26  	sum128a [2]uint64
    27  )
    28  
    29  const (
    30  	offset32        = 2166136261
    31  	offset64        = 14695981039346656037
    32  	offset128Lower  = 0x62b821756295c58d
    33  	offset128Higher = 0x6c62272e07bb0142
    34  	prime32         = 16777619
    35  	prime64         = 1099511628211
    36  	prime128Lower   = 0x13b
    37  	prime128Shift   = 24
    38  )
    39  
    40  // New32 returns a new 32-bit FNV-1 hash.Hash.
    41  // Its Sum method will lay the value out in big-endian byte order.
    42  func New32() hash.Hash32 {
    43  	var s sum32 = offset32
    44  	return &s
    45  }
    46  
    47  // New32a returns a new 32-bit FNV-1a hash.Hash.
    48  // Its Sum method will lay the value out in big-endian byte order.
    49  func New32a() hash.Hash32 {
    50  	var s sum32a = offset32
    51  	return &s
    52  }
    53  
    54  // New64 returns a new 64-bit FNV-1 hash.Hash.
    55  // Its Sum method will lay the value out in big-endian byte order.
    56  func New64() hash.Hash64 {
    57  	var s sum64 = offset64
    58  	return &s
    59  }
    60  
    61  // New64a returns a new 64-bit FNV-1a hash.Hash.
    62  // Its Sum method will lay the value out in big-endian byte order.
    63  func New64a() hash.Hash64 {
    64  	var s sum64a = offset64
    65  	return &s
    66  }
    67  
    68  // New128 returns a new 128-bit FNV-1 hash.Hash.
    69  // Its Sum method will lay the value out in big-endian byte order.
    70  func New128() hash.Hash {
    71  	var s sum128
    72  	s[0] = offset128Higher
    73  	s[1] = offset128Lower
    74  	return &s
    75  }
    76  
    77  // New128a returns a new 128-bit FNV-1a hash.Hash.
    78  // Its Sum method will lay the value out in big-endian byte order.
    79  func New128a() hash.Hash {
    80  	var s sum128a
    81  	s[0] = offset128Higher
    82  	s[1] = offset128Lower
    83  	return &s
    84  }
    85  
    86  func (s *sum32) Reset()   { *s = offset32 }
    87  func (s *sum32a) Reset()  { *s = offset32 }
    88  func (s *sum64) Reset()   { *s = offset64 }
    89  func (s *sum64a) Reset()  { *s = offset64 }
    90  func (s *sum128) Reset()  { s[0] = offset128Higher; s[1] = offset128Lower }
    91  func (s *sum128a) Reset() { s[0] = offset128Higher; s[1] = offset128Lower }
    92  
    93  func (s *sum32) Sum32() uint32  { return uint32(*s) }
    94  func (s *sum32a) Sum32() uint32 { return uint32(*s) }
    95  func (s *sum64) Sum64() uint64  { return uint64(*s) }
    96  func (s *sum64a) Sum64() uint64 { return uint64(*s) }
    97  
    98  func (s *sum32) Write(data []byte) (int, error) {
    99  	hash := *s
   100  	for _, c := range data {
   101  		hash *= prime32
   102  		hash ^= sum32(c)
   103  	}
   104  	*s = hash
   105  	return len(data), nil
   106  }
   107  
   108  func (s *sum32a) Write(data []byte) (int, error) {
   109  	hash := *s
   110  	for _, c := range data {
   111  		hash ^= sum32a(c)
   112  		hash *= prime32
   113  	}
   114  	*s = hash
   115  	return len(data), nil
   116  }
   117  
   118  func (s *sum64) Write(data []byte) (int, error) {
   119  	hash := *s
   120  	for _, c := range data {
   121  		hash *= prime64
   122  		hash ^= sum64(c)
   123  	}
   124  	*s = hash
   125  	return len(data), nil
   126  }
   127  
   128  func (s *sum64a) Write(data []byte) (int, error) {
   129  	hash := *s
   130  	for _, c := range data {
   131  		hash ^= sum64a(c)
   132  		hash *= prime64
   133  	}
   134  	*s = hash
   135  	return len(data), nil
   136  }
   137  
   138  func (s *sum128) Write(data []byte) (int, error) {
   139  	for _, c := range data {
   140  		// Compute the multiplication in 4 parts to simplify carrying
   141  		s1l := (s[1] & 0xffffffff) * prime128Lower
   142  		s1h := (s[1] >> 32) * prime128Lower
   143  		s0l := (s[0]&0xffffffff)*prime128Lower + (s[1]&0xffffffff)<<prime128Shift
   144  		s0h := (s[0]>>32)*prime128Lower + (s[1]>>32)<<prime128Shift
   145  		// Carries
   146  		s1h += s1l >> 32
   147  		s0l += s1h >> 32
   148  		s0h += s0l >> 32
   149  		// Update the values
   150  		s[1] = (s1l & 0xffffffff) + (s1h << 32)
   151  		s[0] = (s0l & 0xffffffff) + (s0h << 32)
   152  		s[1] ^= uint64(c)
   153  	}
   154  	return len(data), nil
   155  }
   156  
   157  func (s *sum128a) Write(data []byte) (int, error) {
   158  	for _, c := range data {
   159  		s[1] ^= uint64(c)
   160  		// Compute the multiplication in 4 parts to simplify carrying
   161  		s1l := (s[1] & 0xffffffff) * prime128Lower
   162  		s1h := (s[1] >> 32) * prime128Lower
   163  		s0l := (s[0]&0xffffffff)*prime128Lower + (s[1]&0xffffffff)<<prime128Shift
   164  		s0h := (s[0]>>32)*prime128Lower + (s[1]>>32)<<prime128Shift
   165  		// Carries
   166  		s1h += s1l >> 32
   167  		s0l += s1h >> 32
   168  		s0h += s0l >> 32
   169  		// Update the values
   170  		s[1] = (s1l & 0xffffffff) + (s1h << 32)
   171  		s[0] = (s0l & 0xffffffff) + (s0h << 32)
   172  	}
   173  	return len(data), nil
   174  }
   175  
   176  func (s *sum32) Size() int   { return 4 }
   177  func (s *sum32a) Size() int  { return 4 }
   178  func (s *sum64) Size() int   { return 8 }
   179  func (s *sum64a) Size() int  { return 8 }
   180  func (s *sum128) Size() int  { return 16 }
   181  func (s *sum128a) Size() int { return 16 }
   182  
   183  func (s *sum32) BlockSize() int   { return 1 }
   184  func (s *sum32a) BlockSize() int  { return 1 }
   185  func (s *sum64) BlockSize() int   { return 1 }
   186  func (s *sum64a) BlockSize() int  { return 1 }
   187  func (s *sum128) BlockSize() int  { return 1 }
   188  func (s *sum128a) BlockSize() int { return 1 }
   189  
   190  func (s *sum32) Sum(in []byte) []byte {
   191  	v := uint32(*s)
   192  	return append(in, byte(v>>24), byte(v>>16), byte(v>>8), byte(v))
   193  }
   194  
   195  func (s *sum32a) Sum(in []byte) []byte {
   196  	v := uint32(*s)
   197  	return append(in, byte(v>>24), byte(v>>16), byte(v>>8), byte(v))
   198  }
   199  
   200  func (s *sum64) Sum(in []byte) []byte {
   201  	v := uint64(*s)
   202  	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))
   203  }
   204  
   205  func (s *sum64a) Sum(in []byte) []byte {
   206  	v := uint64(*s)
   207  	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))
   208  }
   209  
   210  func (s *sum128) Sum(in []byte) []byte {
   211  	return append(in,
   212  		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]),
   213  		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]),
   214  	)
   215  }
   216  
   217  func (s *sum128a) Sum(in []byte) []byte {
   218  	return append(in,
   219  		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]),
   220  		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]),
   221  	)
   222  }
   223  
   224  const (
   225  	magic32          = "fnv\x01"
   226  	magic32a         = "fnv\x02"
   227  	magic64          = "fnv\x03"
   228  	magic64a         = "fnv\x04"
   229  	magic128         = "fnv\x05"
   230  	magic128a        = "fnv\x06"
   231  	marshaledSize32  = len(magic32) + 4
   232  	marshaledSize64  = len(magic64) + 8
   233  	marshaledSize128 = len(magic128) + 8*2
   234  )
   235  
   236  func (s *sum32) MarshalBinary() ([]byte, error) {
   237  	b := make([]byte, 0, marshaledSize32)
   238  	b = append(b, magic32...)
   239  	b = appendUint32(b, uint32(*s))
   240  	return b, nil
   241  }
   242  
   243  func (s *sum32a) MarshalBinary() ([]byte, error) {
   244  	b := make([]byte, 0, marshaledSize32)
   245  	b = append(b, magic32a...)
   246  	b = appendUint32(b, uint32(*s))
   247  	return b, nil
   248  }
   249  
   250  func (s *sum64) MarshalBinary() ([]byte, error) {
   251  	b := make([]byte, 0, marshaledSize64)
   252  	b = append(b, magic64...)
   253  	b = appendUint64(b, uint64(*s))
   254  	return b, nil
   255  
   256  }
   257  
   258  func (s *sum64a) MarshalBinary() ([]byte, error) {
   259  	b := make([]byte, 0, marshaledSize64)
   260  	b = append(b, magic64a...)
   261  	b = appendUint64(b, uint64(*s))
   262  	return b, nil
   263  }
   264  
   265  func (s *sum128) MarshalBinary() ([]byte, error) {
   266  	b := make([]byte, 0, marshaledSize128)
   267  	b = append(b, magic128...)
   268  	b = appendUint64(b, s[0])
   269  	b = appendUint64(b, s[1])
   270  	return b, nil
   271  }
   272  
   273  func (s *sum128a) MarshalBinary() ([]byte, error) {
   274  	b := make([]byte, 0, marshaledSize128)
   275  	b = append(b, magic128a...)
   276  	b = appendUint64(b, s[0])
   277  	b = appendUint64(b, s[1])
   278  	return b, nil
   279  }
   280  
   281  func (s *sum32) UnmarshalBinary(b []byte) error {
   282  	if len(b) < len(magic32) || string(b[:len(magic32)]) != magic32 {
   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 = sum32(readUint32(b[4:]))
   289  	return nil
   290  }
   291  
   292  func (s *sum32a) UnmarshalBinary(b []byte) error {
   293  	if len(b) < len(magic32a) || string(b[:len(magic32a)]) != magic32a {
   294  		return errors.New("hash/fnv: invalid hash state identifier")
   295  	}
   296  	if len(b) != marshaledSize32 {
   297  		return errors.New("hash/fnv: invalid hash state size")
   298  	}
   299  	*s = sum32a(readUint32(b[4:]))
   300  	return nil
   301  }
   302  
   303  func (s *sum64) UnmarshalBinary(b []byte) error {
   304  	if len(b) < len(magic64) || string(b[:len(magic64)]) != magic64 {
   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 = sum64(readUint64(b[4:]))
   311  	return nil
   312  }
   313  
   314  func (s *sum64a) UnmarshalBinary(b []byte) error {
   315  	if len(b) < len(magic64a) || string(b[:len(magic64a)]) != magic64a {
   316  		return errors.New("hash/fnv: invalid hash state identifier")
   317  	}
   318  	if len(b) != marshaledSize64 {
   319  		return errors.New("hash/fnv: invalid hash state size")
   320  	}
   321  	*s = sum64a(readUint64(b[4:]))
   322  	return nil
   323  }
   324  
   325  func (s *sum128) UnmarshalBinary(b []byte) error {
   326  	if len(b) < len(magic128) || string(b[:len(magic128)]) != magic128 {
   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  func (s *sum128a) UnmarshalBinary(b []byte) error {
   338  	if len(b) < len(magic128a) || string(b[:len(magic128a)]) != magic128a {
   339  		return errors.New("hash/fnv: invalid hash state identifier")
   340  	}
   341  	if len(b) != marshaledSize128 {
   342  		return errors.New("hash/fnv: invalid hash state size")
   343  	}
   344  	s[0] = readUint64(b[4:])
   345  	s[1] = readUint64(b[12:])
   346  	return nil
   347  }
   348  
   349  func readUint32(b []byte) uint32 {
   350  	_ = b[3]
   351  	return uint32(b[3]) | uint32(b[2])<<8 | uint32(b[1])<<16 | uint32(b[0])<<24
   352  }
   353  
   354  func appendUint32(b []byte, x uint32) []byte {
   355  	a := [4]byte{
   356  		byte(x >> 24),
   357  		byte(x >> 16),
   358  		byte(x >> 8),
   359  		byte(x),
   360  	}
   361  	return append(b, a[:]...)
   362  }
   363  
   364  func appendUint64(b []byte, x uint64) []byte {
   365  	a := [8]byte{
   366  		byte(x >> 56),
   367  		byte(x >> 48),
   368  		byte(x >> 40),
   369  		byte(x >> 32),
   370  		byte(x >> 24),
   371  		byte(x >> 16),
   372  		byte(x >> 8),
   373  		byte(x),
   374  	}
   375  	return append(b, a[:]...)
   376  }
   377  
   378  func readUint64(b []byte) uint64 {
   379  	_ = b[7]
   380  	return uint64(b[7]) | uint64(b[6])<<8 | uint64(b[5])<<16 | uint64(b[4])<<24 |
   381  		uint64(b[3])<<32 | uint64(b[2])<<40 | uint64(b[1])<<48 | uint64(b[0])<<56
   382  }
   383  

View as plain text