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  	clear(xh.buf[:])
    45  	xh.cnt = 0
    46  }
    47  
    48  // update adds a buffer to the has.
    49  func (xh *xxhash64) update(b []byte) {
    50  	xh.len += uint64(len(b))
    51  
    52  	if xh.cnt+len(b) < len(xh.buf) {
    53  		copy(xh.buf[xh.cnt:], b)
    54  		xh.cnt += len(b)
    55  		return
    56  	}
    57  
    58  	if xh.cnt > 0 {
    59  		n := copy(xh.buf[xh.cnt:], b)
    60  		b = b[n:]
    61  		xh.v[0] = xh.round(xh.v[0], binary.LittleEndian.Uint64(xh.buf[:]))
    62  		xh.v[1] = xh.round(xh.v[1], binary.LittleEndian.Uint64(xh.buf[8:]))
    63  		xh.v[2] = xh.round(xh.v[2], binary.LittleEndian.Uint64(xh.buf[16:]))
    64  		xh.v[3] = xh.round(xh.v[3], binary.LittleEndian.Uint64(xh.buf[24:]))
    65  		xh.cnt = 0
    66  	}
    67  
    68  	for len(b) >= 32 {
    69  		xh.v[0] = xh.round(xh.v[0], binary.LittleEndian.Uint64(b))
    70  		xh.v[1] = xh.round(xh.v[1], binary.LittleEndian.Uint64(b[8:]))
    71  		xh.v[2] = xh.round(xh.v[2], binary.LittleEndian.Uint64(b[16:]))
    72  		xh.v[3] = xh.round(xh.v[3], binary.LittleEndian.Uint64(b[24:]))
    73  		b = b[32:]
    74  	}
    75  
    76  	if len(b) > 0 {
    77  		copy(xh.buf[:], b)
    78  		xh.cnt = len(b)
    79  	}
    80  }
    81  
    82  // digest returns the final hash value.
    83  func (xh *xxhash64) digest() uint64 {
    84  	var h64 uint64
    85  	if xh.len < 32 {
    86  		h64 = xh.v[2] + xxhPrime64c5
    87  	} else {
    88  		h64 = bits.RotateLeft64(xh.v[0], 1) +
    89  			bits.RotateLeft64(xh.v[1], 7) +
    90  			bits.RotateLeft64(xh.v[2], 12) +
    91  			bits.RotateLeft64(xh.v[3], 18)
    92  		h64 = xh.mergeRound(h64, xh.v[0])
    93  		h64 = xh.mergeRound(h64, xh.v[1])
    94  		h64 = xh.mergeRound(h64, xh.v[2])
    95  		h64 = xh.mergeRound(h64, xh.v[3])
    96  	}
    97  
    98  	h64 += xh.len
    99  
   100  	len := xh.len
   101  	len &= 31
   102  	buf := xh.buf[:]
   103  	for len >= 8 {
   104  		k1 := xh.round(0, binary.LittleEndian.Uint64(buf))
   105  		buf = buf[8:]
   106  		h64 ^= k1
   107  		h64 = bits.RotateLeft64(h64, 27)*xxhPrime64c1 + xxhPrime64c4
   108  		len -= 8
   109  	}
   110  	if len >= 4 {
   111  		h64 ^= uint64(binary.LittleEndian.Uint32(buf)) * xxhPrime64c1
   112  		buf = buf[4:]
   113  		h64 = bits.RotateLeft64(h64, 23)*xxhPrime64c2 + xxhPrime64c3
   114  		len -= 4
   115  	}
   116  	for len > 0 {
   117  		h64 ^= uint64(buf[0]) * xxhPrime64c5
   118  		buf = buf[1:]
   119  		h64 = bits.RotateLeft64(h64, 11) * xxhPrime64c1
   120  		len--
   121  	}
   122  
   123  	h64 ^= h64 >> 33
   124  	h64 *= xxhPrime64c2
   125  	h64 ^= h64 >> 29
   126  	h64 *= xxhPrime64c3
   127  	h64 ^= h64 >> 32
   128  
   129  	return h64
   130  }
   131  
   132  // round updates a value.
   133  func (xh *xxhash64) round(v, n uint64) uint64 {
   134  	v += n * xxhPrime64c2
   135  	v = bits.RotateLeft64(v, 31)
   136  	v *= xxhPrime64c1
   137  	return v
   138  }
   139  
   140  // mergeRound updates a value in the final round.
   141  func (xh *xxhash64) mergeRound(v, n uint64) uint64 {
   142  	n = xh.round(0, n)
   143  	v ^= n
   144  	v = v*xxhPrime64c1 + xxhPrime64c4
   145  	return v
   146  }
   147
View as plain text