xxhash.go

Documentation: github.com/klauspost/compress/zstd/internal/xxhash

     1  // Package xxhash implements the 64-bit variant of xxHash (XXH64) as described
     2  // at http://cyan4973.github.io/xxHash/.
     3  // THIS IS VENDORED: Go to github.com/cespare/xxhash for original package.
     4  
     5  package xxhash
     6  
     7  import (
     8  	"encoding/binary"
     9  	"errors"
    10  	"math/bits"
    11  )
    12  
    13  const (
    14  	prime1 uint64 = 11400714785074694791
    15  	prime2 uint64 = 14029467366897019727
    16  	prime3 uint64 = 1609587929392839161
    17  	prime4 uint64 = 9650029242287828579
    18  	prime5 uint64 = 2870177450012600261
    19  )
    20  
    21  // Store the primes in an array as well.
    22  //
    23  // The consts are used when possible in Go code to avoid MOVs but we need a
    24  // contiguous array of the assembly code.
    25  var primes = [...]uint64{prime1, prime2, prime3, prime4, prime5}
    26  
    27  // Digest implements hash.Hash64.
    28  type Digest struct {
    29  	v1    uint64
    30  	v2    uint64
    31  	v3    uint64
    32  	v4    uint64
    33  	total uint64
    34  	mem   [32]byte
    35  	n     int // how much of mem is used
    36  }
    37  
    38  // New creates a new Digest that computes the 64-bit xxHash algorithm.
    39  func New() *Digest {
    40  	var d Digest
    41  	d.Reset()
    42  	return &d
    43  }
    44  
    45  // Reset clears the Digest's state so that it can be reused.
    46  func (d *Digest) Reset() {
    47  	d.v1 = primes[0] + prime2
    48  	d.v2 = prime2
    49  	d.v3 = 0
    50  	d.v4 = -primes[0]
    51  	d.total = 0
    52  	d.n = 0
    53  }
    54  
    55  // Size always returns 8 bytes.
    56  func (d *Digest) Size() int { return 8 }
    57  
    58  // BlockSize always returns 32 bytes.
    59  func (d *Digest) BlockSize() int { return 32 }
    60  
    61  // Write adds more data to d. It always returns len(b), nil.
    62  func (d *Digest) Write(b []byte) (n int, err error) {
    63  	n = len(b)
    64  	d.total += uint64(n)
    65  
    66  	memleft := d.mem[d.n&(len(d.mem)-1):]
    67  
    68  	if d.n+n < 32 {
    69  		// This new data doesn't even fill the current block.
    70  		copy(memleft, b)
    71  		d.n += n
    72  		return
    73  	}
    74  
    75  	if d.n > 0 {
    76  		// Finish off the partial block.
    77  		c := copy(memleft, b)
    78  		d.v1 = round(d.v1, u64(d.mem[0:8]))
    79  		d.v2 = round(d.v2, u64(d.mem[8:16]))
    80  		d.v3 = round(d.v3, u64(d.mem[16:24]))
    81  		d.v4 = round(d.v4, u64(d.mem[24:32]))
    82  		b = b[c:]
    83  		d.n = 0
    84  	}
    85  
    86  	if len(b) >= 32 {
    87  		// One or more full blocks left.
    88  		nw := writeBlocks(d, b)
    89  		b = b[nw:]
    90  	}
    91  
    92  	// Store any remaining partial block.
    93  	copy(d.mem[:], b)
    94  	d.n = len(b)
    95  
    96  	return
    97  }
    98  
    99  // Sum appends the current hash to b and returns the resulting slice.
   100  func (d *Digest) Sum(b []byte) []byte {
   101  	s := d.Sum64()
   102  	return append(
   103  		b,
   104  		byte(s>>56),
   105  		byte(s>>48),
   106  		byte(s>>40),
   107  		byte(s>>32),
   108  		byte(s>>24),
   109  		byte(s>>16),
   110  		byte(s>>8),
   111  		byte(s),
   112  	)
   113  }
   114  
   115  // Sum64 returns the current hash.
   116  func (d *Digest) Sum64() uint64 {
   117  	var h uint64
   118  
   119  	if d.total >= 32 {
   120  		v1, v2, v3, v4 := d.v1, d.v2, d.v3, d.v4
   121  		h = rol1(v1) + rol7(v2) + rol12(v3) + rol18(v4)
   122  		h = mergeRound(h, v1)
   123  		h = mergeRound(h, v2)
   124  		h = mergeRound(h, v3)
   125  		h = mergeRound(h, v4)
   126  	} else {
   127  		h = d.v3 + prime5
   128  	}
   129  
   130  	h += d.total
   131  
   132  	b := d.mem[:d.n&(len(d.mem)-1)]
   133  	for ; len(b) >= 8; b = b[8:] {
   134  		k1 := round(0, u64(b[:8]))
   135  		h ^= k1
   136  		h = rol27(h)*prime1 + prime4
   137  	}
   138  	if len(b) >= 4 {
   139  		h ^= uint64(u32(b[:4])) * prime1
   140  		h = rol23(h)*prime2 + prime3
   141  		b = b[4:]
   142  	}
   143  	for ; len(b) > 0; b = b[1:] {
   144  		h ^= uint64(b[0]) * prime5
   145  		h = rol11(h) * prime1
   146  	}
   147  
   148  	h ^= h >> 33
   149  	h *= prime2
   150  	h ^= h >> 29
   151  	h *= prime3
   152  	h ^= h >> 32
   153  
   154  	return h
   155  }
   156  
   157  const (
   158  	magic         = "xxh\x06"
   159  	marshaledSize = len(magic) + 8*5 + 32
   160  )
   161  
   162  // MarshalBinary implements the encoding.BinaryMarshaler interface.
   163  func (d *Digest) MarshalBinary() ([]byte, error) {
   164  	b := make([]byte, 0, marshaledSize)
   165  	b = append(b, magic...)
   166  	b = appendUint64(b, d.v1)
   167  	b = appendUint64(b, d.v2)
   168  	b = appendUint64(b, d.v3)
   169  	b = appendUint64(b, d.v4)
   170  	b = appendUint64(b, d.total)
   171  	b = append(b, d.mem[:d.n]...)
   172  	b = b[:len(b)+len(d.mem)-d.n]
   173  	return b, nil
   174  }
   175  
   176  // UnmarshalBinary implements the encoding.BinaryUnmarshaler interface.
   177  func (d *Digest) UnmarshalBinary(b []byte) error {
   178  	if len(b) < len(magic) || string(b[:len(magic)]) != magic {
   179  		return errors.New("xxhash: invalid hash state identifier")
   180  	}
   181  	if len(b) != marshaledSize {
   182  		return errors.New("xxhash: invalid hash state size")
   183  	}
   184  	b = b[len(magic):]
   185  	b, d.v1 = consumeUint64(b)
   186  	b, d.v2 = consumeUint64(b)
   187  	b, d.v3 = consumeUint64(b)
   188  	b, d.v4 = consumeUint64(b)
   189  	b, d.total = consumeUint64(b)
   190  	copy(d.mem[:], b)
   191  	d.n = int(d.total % uint64(len(d.mem)))
   192  	return nil
   193  }
   194  
   195  func appendUint64(b []byte, x uint64) []byte {
   196  	var a [8]byte
   197  	binary.LittleEndian.PutUint64(a[:], x)
   198  	return append(b, a[:]...)
   199  }
   200  
   201  func consumeUint64(b []byte) ([]byte, uint64) {
   202  	x := u64(b)
   203  	return b[8:], x
   204  }
   205  
   206  func u64(b []byte) uint64 { return binary.LittleEndian.Uint64(b) }
   207  func u32(b []byte) uint32 { return binary.LittleEndian.Uint32(b) }
   208  
   209  func round(acc, input uint64) uint64 {
   210  	acc += input * prime2
   211  	acc = rol31(acc)
   212  	acc *= prime1
   213  	return acc
   214  }
   215  
   216  func mergeRound(acc, val uint64) uint64 {
   217  	val = round(0, val)
   218  	acc ^= val
   219  	acc = acc*prime1 + prime4
   220  	return acc
   221  }
   222  
   223  func rol1(x uint64) uint64  { return bits.RotateLeft64(x, 1) }
   224  func rol7(x uint64) uint64  { return bits.RotateLeft64(x, 7) }
   225  func rol11(x uint64) uint64 { return bits.RotateLeft64(x, 11) }
   226  func rol12(x uint64) uint64 { return bits.RotateLeft64(x, 12) }
   227  func rol18(x uint64) uint64 { return bits.RotateLeft64(x, 18) }
   228  func rol23(x uint64) uint64 { return bits.RotateLeft64(x, 23) }
   229  func rol27(x uint64) uint64 { return bits.RotateLeft64(x, 27) }
   230  func rol31(x uint64) uint64 { return bits.RotateLeft64(x, 31) }
   231
View as plain text