mirror of https://go.googlesource.com/go
149 lines
3.3 KiB
Go
149 lines
3.3 KiB
Go
// 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
|
|
}
|