package xxhash
import (
"encoding/binary"
"errors"
"hash"
)
const (
prime32x1 uint32 = 2654435761
prime32x2 uint32 = 2246822519
prime32x3 uint32 = 3266489917
prime32x4 uint32 = 668265263
prime32x5 uint32 = 374761393
prime64x1 uint64 = 11400714785074694791
prime64x2 uint64 = 14029467366897019727
prime64x3 uint64 = 1609587929392839161
prime64x4 uint64 = 9650029242287828579
prime64x5 uint64 = 2870177450012600261
maxInt32 int32 = (1<<31 - 1)
// precomputed zero Vs for seed 0
zero64x1 = 0x60ea27eeadc0b5d6
zero64x2 = 0xc2b2ae3d27d4eb4f
zero64x3 = 0x0
zero64x4 = 0x61c8864e7a143579
)
const (
magic32 = "xxh\x07"
magic64 = "xxh\x08"
marshaled32Size = len(magic32) + 4*7 + 16
marshaled64Size = len(magic64) + 8*6 + 32 + 1
)
func NewHash32() hash.Hash { return New32() }
func NewHash64() hash.Hash { return New64() }
// Checksum32 returns the checksum of the input data with the seed set to 0.
func Checksum32(in []byte) uint32 {
return Checksum32S(in, 0)
}
// ChecksumString32 returns the checksum of the input data, without creating a copy, with the seed set to 0.
func ChecksumString32(s string) uint32 {
return ChecksumString32S(s, 0)
}
type XXHash32 struct {
mem [16]byte
ln, memIdx int32
v1, v2, v3, v4 uint32
seed uint32
}
// Size returns the number of bytes Sum will return.
func (xx *XXHash32) Size() int {
return 4
}
// BlockSize returns the hash's underlying block size.
// The Write method must be able to accept any amount
// of data, but it may operate more efficiently if all writes
// are a multiple of the block size.
func (xx *XXHash32) BlockSize() int {
return 16
}
// NewS32 creates a new hash.Hash32 computing the 32bit xxHash checksum starting with the specific seed.
func NewS32(seed uint32) (xx *XXHash32) {
xx = &XXHash32{
seed: seed,
}
xx.Reset()
return
}
// New32 creates a new hash.Hash32 computing the 32bit xxHash checksum starting with the seed set to 0.
func New32() *XXHash32 {
return NewS32(0)
}
func (xx *XXHash32) Reset() {
xx.v1 = xx.seed + prime32x1 + prime32x2
xx.v2 = xx.seed + prime32x2
xx.v3 = xx.seed
xx.v4 = xx.seed - prime32x1
xx.ln, xx.memIdx = 0, 0
}
// Sum appends the current hash to b and returns the resulting slice.
// It does not change the underlying hash state.
func (xx *XXHash32) Sum(in []byte) []byte {
s := xx.Sum32()
return append(in, byte(s>>24), byte(s>>16), byte(s>>8), byte(s))
}
// MarshalBinary implements the encoding.BinaryMarshaler interface.
func (xx *XXHash32) MarshalBinary() ([]byte, error) {
b := make([]byte, 0, marshaled32Size)
b = append(b, magic32...)
b = appendUint32(b, xx.v1)
b = appendUint32(b, xx.v2)
b = appendUint32(b, xx.v3)
b = appendUint32(b, xx.v4)
b = appendUint32(b, xx.seed)
b = appendInt32(b, xx.ln)
b = appendInt32(b, xx.memIdx)
b = append(b, xx.mem[:]...)
return b, nil
}
// UnmarshalBinary implements the encoding.BinaryUnmarshaler interface.
func (xx *XXHash32) UnmarshalBinary(b []byte) error {
if len(b) < len(magic32) || string(b[:len(magic32)]) != magic32 {
return errors.New("xxhash: invalid hash state identifier")
}
if len(b) != marshaled32Size {
return errors.New("xxhash: invalid hash state size")
}
b = b[len(magic32):]
b, xx.v1 = consumeUint32(b)
b, xx.v2 = consumeUint32(b)
b, xx.v3 = consumeUint32(b)
b, xx.v4 = consumeUint32(b)
b, xx.seed = consumeUint32(b)
b, xx.ln = consumeInt32(b)
b, xx.memIdx = consumeInt32(b)
copy(xx.mem[:], b)
return nil
}
// Checksum64 an alias for Checksum64S(in, 0)
func Checksum64(in []byte) uint64 {
return Checksum64S(in, 0)
}
// ChecksumString64 returns the checksum of the input data, without creating a copy, with the seed set to 0.
func ChecksumString64(s string) uint64 {
return ChecksumString64S(s, 0)
}
type XXHash64 struct {
v1, v2, v3, v4 uint64
seed uint64
ln uint64
mem [32]byte
memIdx int8
}
// Size returns the number of bytes Sum will return.
func (xx *XXHash64) Size() int {
return 8
}
// BlockSize returns the hash's underlying block size.
// The Write method must be able to accept any amount
// of data, but it may operate more efficiently if all writes
// are a multiple of the block size.
func (xx *XXHash64) BlockSize() int {
return 32
}
// NewS64 creates a new hash.Hash64 computing the 64bit xxHash checksum starting with the specific seed.
func NewS64(seed uint64) (xx *XXHash64) {
xx = &XXHash64{
seed: seed,
}
xx.Reset()
return
}
// New64 creates a new hash.Hash64 computing the 64bit xxHash checksum starting with the seed set to 0x0.
func New64() *XXHash64 {
return NewS64(0)
}
func (xx *XXHash64) Reset() {
xx.ln, xx.memIdx = 0, 0
xx.v1, xx.v2, xx.v3, xx.v4 = resetVs64(xx.seed)
}
// Sum appends the current hash to b and returns the resulting slice.
// It does not change the underlying hash state.
func (xx *XXHash64) Sum(in []byte) []byte {
s := xx.Sum64()
return append(in, byte(s>>56), byte(s>>48), byte(s>>40), byte(s>>32), byte(s>>24), byte(s>>16), byte(s>>8), byte(s))
}
// MarshalBinary implements the encoding.BinaryMarshaler interface.
func (xx *XXHash64) MarshalBinary() ([]byte, error) {
b := make([]byte, 0, marshaled64Size)
b = append(b, magic64...)
b = appendUint64(b, xx.v1)
b = appendUint64(b, xx.v2)
b = appendUint64(b, xx.v3)
b = appendUint64(b, xx.v4)
b = appendUint64(b, xx.seed)
b = appendUint64(b, xx.ln)
b = append(b, byte(xx.memIdx))
b = append(b, xx.mem[:]...)
return b, nil
}
// UnmarshalBinary implements the encoding.BinaryUnmarshaler interface.
func (xx *XXHash64) UnmarshalBinary(b []byte) error {
if len(b) < len(magic64) || string(b[:len(magic64)]) != magic64 {
return errors.New("xxhash: invalid hash state identifier")
}
if len(b) != marshaled64Size {
return errors.New("xxhash: invalid hash state size")
}
b = b[len(magic64):]
b, xx.v1 = consumeUint64(b)
b, xx.v2 = consumeUint64(b)
b, xx.v3 = consumeUint64(b)
b, xx.v4 = consumeUint64(b)
b, xx.seed = consumeUint64(b)
b, xx.ln = consumeUint64(b)
xx.memIdx = int8(b[0])
b = b[1:]
copy(xx.mem[:], b)
return nil
}
func appendInt32(b []byte, x int32) []byte { return appendUint32(b, uint32(x)) }
func appendUint32(b []byte, x uint32) []byte {
var a [4]byte
binary.LittleEndian.PutUint32(a[:], x)
return append(b, a[:]...)
}
func appendUint64(b []byte, x uint64) []byte {
var a [8]byte
binary.LittleEndian.PutUint64(a[:], x)
return append(b, a[:]...)
}
func consumeInt32(b []byte) ([]byte, int32) { bn, x := consumeUint32(b); return bn, int32(x) }
func consumeUint32(b []byte) ([]byte, uint32) { x := u32(b); return b[4:], x }
func consumeUint64(b []byte) ([]byte, uint64) { x := u64(b); return b[8:], x }
// force the compiler to use ROTL instructions
func rotl32_1(x uint32) uint32 { return (x << 1) | (x >> (32 - 1)) }
func rotl32_7(x uint32) uint32 { return (x << 7) | (x >> (32 - 7)) }
func rotl32_11(x uint32) uint32 { return (x << 11) | (x >> (32 - 11)) }
func rotl32_12(x uint32) uint32 { return (x << 12) | (x >> (32 - 12)) }
func rotl32_13(x uint32) uint32 { return (x << 13) | (x >> (32 - 13)) }
func rotl32_17(x uint32) uint32 { return (x << 17) | (x >> (32 - 17)) }
func rotl32_18(x uint32) uint32 { return (x << 18) | (x >> (32 - 18)) }
func rotl64_1(x uint64) uint64 { return (x << 1) | (x >> (64 - 1)) }
func rotl64_7(x uint64) uint64 { return (x << 7) | (x >> (64 - 7)) }
func rotl64_11(x uint64) uint64 { return (x << 11) | (x >> (64 - 11)) }
func rotl64_12(x uint64) uint64 { return (x << 12) | (x >> (64 - 12)) }
func rotl64_18(x uint64) uint64 { return (x << 18) | (x >> (64 - 18)) }
func rotl64_23(x uint64) uint64 { return (x << 23) | (x >> (64 - 23)) }
func rotl64_27(x uint64) uint64 { return (x << 27) | (x >> (64 - 27)) }
func rotl64_31(x uint64) uint64 { return (x << 31) | (x >> (64 - 31)) }
func mix64(h uint64) uint64 {
h ^= h >> 33
h *= prime64x2
h ^= h >> 29
h *= prime64x3
h ^= h >> 32
return h
}
func resetVs64(seed uint64) (v1, v2, v3, v4 uint64) {
if seed == 0 {
return zero64x1, zero64x2, zero64x3, zero64x4
}
return (seed + prime64x1 + prime64x2), (seed + prime64x2), (seed), (seed - prime64x1)
}
// borrowed from cespare
func round64(h, v uint64) uint64 {
h += v * prime64x2
h = rotl64_31(h)
h *= prime64x1
return h
}
func mergeRound64(h, v uint64) uint64 {
v = round64(0, v)
h ^= v
h = h*prime64x1 + prime64x4
return h
}