blob: 4d579ee2d5c0d61e621cdfb37f2aada82336d897 [file] [log] [blame]
// Copyright 2023 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package zstd
import (
"encoding/binary"
"math/bits"
)
const (
xxhPrime64c1 = 0x9e3779b185ebca87
xxhPrime64c2 = 0xc2b2ae3d27d4eb4f
xxhPrime64c3 = 0x165667b19e3779f9
xxhPrime64c4 = 0x85ebca77c2b2ae63
xxhPrime64c5 = 0x27d4eb2f165667c5
)
// xxhash64 is the state of a xxHash-64 checksum.
type xxhash64 struct {
len uint64 // total length hashed
v [4]uint64 // accumulators
buf [32]byte // buffer
cnt int // number of bytes in buffer
}
// reset discards the current state and prepares to compute a new hash.
// We assume a seed of 0 since that is what zstd uses.
func (xh *xxhash64) reset() {
xh.len = 0
// Separate addition for awkward constant overflow.
xh.v[0] = xxhPrime64c1
xh.v[0] += xxhPrime64c2
xh.v[1] = xxhPrime64c2
xh.v[2] = 0
// Separate negation for awkward constant overflow.
xh.v[3] = xxhPrime64c1
xh.v[3] = -xh.v[3]
for i := range xh.buf {
xh.buf[i] = 0
}
xh.cnt = 0
}
// update adds a buffer to the has.
func (xh *xxhash64) update(b []byte) {
xh.len += uint64(len(b))
if xh.cnt+len(b) < len(xh.buf) {
copy(xh.buf[xh.cnt:], b)
xh.cnt += len(b)
return
}
if xh.cnt > 0 {
n := copy(xh.buf[xh.cnt:], b)
b = b[n:]
xh.v[0] = xh.round(xh.v[0], binary.LittleEndian.Uint64(xh.buf[:]))
xh.v[1] = xh.round(xh.v[1], binary.LittleEndian.Uint64(xh.buf[8:]))
xh.v[2] = xh.round(xh.v[2], binary.LittleEndian.Uint64(xh.buf[16:]))
xh.v[3] = xh.round(xh.v[3], binary.LittleEndian.Uint64(xh.buf[24:]))
xh.cnt = 0
}
for len(b) >= 32 {
xh.v[0] = xh.round(xh.v[0], binary.LittleEndian.Uint64(b))
xh.v[1] = xh.round(xh.v[1], binary.LittleEndian.Uint64(b[8:]))
xh.v[2] = xh.round(xh.v[2], binary.LittleEndian.Uint64(b[16:]))
xh.v[3] = xh.round(xh.v[3], binary.LittleEndian.Uint64(b[24:]))
b = b[32:]
}
if len(b) > 0 {
copy(xh.buf[:], b)
xh.cnt = len(b)
}
}
// digest returns the final hash value.
func (xh *xxhash64) digest() uint64 {
var h64 uint64
if xh.len < 32 {
h64 = xh.v[2] + xxhPrime64c5
} else {
h64 = bits.RotateLeft64(xh.v[0], 1) +
bits.RotateLeft64(xh.v[1], 7) +
bits.RotateLeft64(xh.v[2], 12) +
bits.RotateLeft64(xh.v[3], 18)
h64 = xh.mergeRound(h64, xh.v[0])
h64 = xh.mergeRound(h64, xh.v[1])
h64 = xh.mergeRound(h64, xh.v[2])
h64 = xh.mergeRound(h64, xh.v[3])
}
h64 += xh.len
len := xh.len
len &= 31
buf := xh.buf[:]
for len >= 8 {
k1 := xh.round(0, binary.LittleEndian.Uint64(buf))
buf = buf[8:]
h64 ^= k1
h64 = bits.RotateLeft64(h64, 27)*xxhPrime64c1 + xxhPrime64c4
len -= 8
}
if len >= 4 {
h64 ^= uint64(binary.LittleEndian.Uint32(buf)) * xxhPrime64c1
buf = buf[4:]
h64 = bits.RotateLeft64(h64, 23)*xxhPrime64c2 + xxhPrime64c3
len -= 4
}
for len > 0 {
h64 ^= uint64(buf[0]) * xxhPrime64c5
buf = buf[1:]
h64 = bits.RotateLeft64(h64, 11) * xxhPrime64c1
len--
}
h64 ^= h64 >> 33
h64 *= xxhPrime64c2
h64 ^= h64 >> 29
h64 *= xxhPrime64c3
h64 ^= h64 >> 32
return h64
}
// round updates a value.
func (xh *xxhash64) round(v, n uint64) uint64 {
v += n * xxhPrime64c2
v = bits.RotateLeft64(v, 31)
v *= xxhPrime64c1
return v
}
// mergeRound updates a value in the final round.
func (xh *xxhash64) mergeRound(v, n uint64) uint64 {
n = xh.round(0, n)
v ^= n
v = v*xxhPrime64c1 + xxhPrime64c4
return v
}