xxhash.go

     1  // Copyright 2023 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 zstd
     6  
     7  import (
     8  	"encoding/binary"
     9  	"math/bits"
    10  )
    11  
    12  const (
    13  	xxhPrime64c1 = 0x9e3779b185ebca87
    14  	xxhPrime64c2 = 0xc2b2ae3d27d4eb4f
    15  	xxhPrime64c3 = 0x165667b19e3779f9
    16  	xxhPrime64c4 = 0x85ebca77c2b2ae63
    17  	xxhPrime64c5 = 0x27d4eb2f165667c5
    18  )
    19  
    20  // xxhash64 is the state of a xxHash-64 checksum.
    21  type xxhash64 struct {
    22  	len uint64    // total length hashed
    23  	v   [4]uint64 // accumulators
    24  	buf [32]byte  // buffer
    25  	cnt int       // number of bytes in buffer
    26  }
    27  
    28  // reset discards the current state and prepares to compute a new hash.
    29  // We assume a seed of 0 since that is what zstd uses.
    30  func (xh *xxhash64) reset() {
    31  	xh.len = 0
    32  
    33  	// Separate addition for awkward constant overflow.
    34  	xh.v[0] = xxhPrime64c1
    35  	xh.v[0] += xxhPrime64c2
    36  
    37  	xh.v[1] = xxhPrime64c2
    38  	xh.v[2] = 0
    39  
    40  	// Separate negation for awkward constant overflow.
    41  	xh.v[3] = xxhPrime64c1
    42  	xh.v[3] = -xh.v[3]
    43  
    44  	for i := range xh.buf {
    45  		xh.buf[i] = 0
    46  	}
    47  	xh.cnt = 0
    48  }
    49  
    50  // update adds a buffer to the has.
    51  func (xh *xxhash64) update(b []byte) {
    52  	xh.len += uint64(len(b))
    53  
    54  	if xh.cnt+len(b) < len(xh.buf) {
    55  		copy(xh.buf[xh.cnt:], b)
    56  		xh.cnt += len(b)
    57  		return
    58  	}
    59  
    60  	if xh.cnt > 0 {
    61  		n := copy(xh.buf[xh.cnt:], b)
    62  		b = b[n:]
    63  		xh.v[0] = xh.round(xh.v[0], binary.LittleEndian.Uint64(xh.buf[:]))
    64  		xh.v[1] = xh.round(xh.v[1], binary.LittleEndian.Uint64(xh.buf[8:]))
    65  		xh.v[2] = xh.round(xh.v[2], binary.LittleEndian.Uint64(xh.buf[16:]))
    66  		xh.v[3] = xh.round(xh.v[3], binary.LittleEndian.Uint64(xh.buf[24:]))
    67  		xh.cnt = 0
    68  	}
    69  
    70  	for len(b) >= 32 {
    71  		xh.v[0] = xh.round(xh.v[0], binary.LittleEndian.Uint64(b))
    72  		xh.v[1] = xh.round(xh.v[1], binary.LittleEndian.Uint64(b[8:]))
    73  		xh.v[2] = xh.round(xh.v[2], binary.LittleEndian.Uint64(b[16:]))
    74  		xh.v[3] = xh.round(xh.v[3], binary.LittleEndian.Uint64(b[24:]))
    75  		b = b[32:]
    76  	}
    77  
    78  	if len(b) > 0 {
    79  		copy(xh.buf[:], b)
    80  		xh.cnt = len(b)
    81  	}
    82  }
    83  
    84  // digest returns the final hash value.
    85  func (xh *xxhash64) digest() uint64 {
    86  	var h64 uint64
    87  	if xh.len < 32 {
    88  		h64 = xh.v[2] + xxhPrime64c5
    89  	} else {
    90  		h64 = bits.RotateLeft64(xh.v[0], 1) +
    91  			bits.RotateLeft64(xh.v[1], 7) +
    92  			bits.RotateLeft64(xh.v[2], 12) +
    93  			bits.RotateLeft64(xh.v[3], 18)
    94  		h64 = xh.mergeRound(h64, xh.v[0])
    95  		h64 = xh.mergeRound(h64, xh.v[1])
    96  		h64 = xh.mergeRound(h64, xh.v[2])
    97  		h64 = xh.mergeRound(h64, xh.v[3])
    98  	}
    99  
   100  	h64 += xh.len
   101  
   102  	len := xh.len
   103  	len &= 31
   104  	buf := xh.buf[:]
   105  	for len >= 8 {
   106  		k1 := xh.round(0, binary.LittleEndian.Uint64(buf))
   107  		buf = buf[8:]
   108  		h64 ^= k1
   109  		h64 = bits.RotateLeft64(h64, 27)*xxhPrime64c1 + xxhPrime64c4
   110  		len -= 8
   111  	}
   112  	if len >= 4 {
   113  		h64 ^= uint64(binary.LittleEndian.Uint32(buf)) * xxhPrime64c1
   114  		buf = buf[4:]
   115  		h64 = bits.RotateLeft64(h64, 23)*xxhPrime64c2 + xxhPrime64c3
   116  		len -= 4
   117  	}
   118  	for len > 0 {
   119  		h64 ^= uint64(buf[0]) * xxhPrime64c5
   120  		buf = buf[1:]
   121  		h64 = bits.RotateLeft64(h64, 11) * xxhPrime64c1
   122  		len--
   123  	}
   124  
   125  	h64 ^= h64 >> 33
   126  	h64 *= xxhPrime64c2
   127  	h64 ^= h64 >> 29
   128  	h64 *= xxhPrime64c3
   129  	h64 ^= h64 >> 32
   130  
   131  	return h64
   132  }
   133  
   134  // round updates a value.
   135  func (xh *xxhash64) round(v, n uint64) uint64 {
   136  	v += n * xxhPrime64c2
   137  	v = bits.RotateLeft64(v, 31)
   138  	v *= xxhPrime64c1
   139  	return v
   140  }
   141  
   142  // mergeRound updates a value in the final round.
   143  func (xh *xxhash64) mergeRound(v, n uint64) uint64 {
   144  	n = xh.round(0, n)
   145  	v ^= n
   146  	v = v*xxhPrime64c1 + xxhPrime64c4
   147  	return v
   148  }
   149
View as plain text