xxhash.go

Documentation: github.com/cespare/xxhash/v2

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