xxhash.go

Documentation: github.com/cespare/xxhash

     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  	"hash"
     8  )
     9  
    10  const (
    11  	prime1 uint64 = 11400714785074694791
    12  	prime2 uint64 = 14029467366897019727
    13  	prime3 uint64 = 1609587929392839161
    14  	prime4 uint64 = 9650029242287828579
    15  	prime5 uint64 = 2870177450012600261
    16  )
    17  
    18  // NOTE(caleb): I'm using both consts and vars of the primes. Using consts where
    19  // possible in the Go code is worth a small (but measurable) performance boost
    20  // by avoiding some MOVQs. Vars are needed for the asm and also are useful for
    21  // convenience in the Go code in a few places where we need to intentionally
    22  // avoid constant arithmetic (e.g., v1 := prime1 + prime2 fails because the
    23  // result overflows a uint64).
    24  var (
    25  	prime1v = prime1
    26  	prime2v = prime2
    27  	prime3v = prime3
    28  	prime4v = prime4
    29  	prime5v = prime5
    30  )
    31  
    32  type xxh struct {
    33  	v1    uint64
    34  	v2    uint64
    35  	v3    uint64
    36  	v4    uint64
    37  	total int
    38  	mem   [32]byte
    39  	n     int // how much of mem is used
    40  }
    41  
    42  // New creates a new hash.Hash64 that implements the 64-bit xxHash algorithm.
    43  func New() hash.Hash64 {
    44  	var x xxh
    45  	x.Reset()
    46  	return &x
    47  }
    48  
    49  func (x *xxh) Reset() {
    50  	x.n = 0
    51  	x.total = 0
    52  	x.v1 = prime1v + prime2
    53  	x.v2 = prime2
    54  	x.v3 = 0
    55  	x.v4 = -prime1v
    56  }
    57  
    58  func (x *xxh) Size() int      { return 8 }
    59  func (x *xxh) BlockSize() int { return 32 }
    60  
    61  // Write adds more data to x. It always returns len(b), nil.
    62  func (x *xxh) Write(b []byte) (n int, err error) {
    63  	n = len(b)
    64  	x.total += len(b)
    65  
    66  	if x.n+len(b) < 32 {
    67  		// This new data doesn't even fill the current block.
    68  		copy(x.mem[x.n:], b)
    69  		x.n += len(b)
    70  		return
    71  	}
    72  
    73  	if x.n > 0 {
    74  		// Finish off the partial block.
    75  		copy(x.mem[x.n:], b)
    76  		x.v1 = round(x.v1, u64(x.mem[0:8]))
    77  		x.v2 = round(x.v2, u64(x.mem[8:16]))
    78  		x.v3 = round(x.v3, u64(x.mem[16:24]))
    79  		x.v4 = round(x.v4, u64(x.mem[24:32]))
    80  		b = b[32-x.n:]
    81  		x.n = 0
    82  	}
    83  
    84  	if len(b) >= 32 {
    85  		// One or more full blocks left.
    86  		b = writeBlocks(x, b)
    87  	}
    88  
    89  	// Store any remaining partial block.
    90  	copy(x.mem[:], b)
    91  	x.n = len(b)
    92  
    93  	return
    94  }
    95  
    96  func (x *xxh) Sum(b []byte) []byte {
    97  	s := x.Sum64()
    98  	return append(
    99  		b,
   100  		byte(s>>56),
   101  		byte(s>>48),
   102  		byte(s>>40),
   103  		byte(s>>32),
   104  		byte(s>>24),
   105  		byte(s>>16),
   106  		byte(s>>8),
   107  		byte(s),
   108  	)
   109  }
   110  
   111  func (x *xxh) Sum64() uint64 {
   112  	var h uint64
   113  
   114  	if x.total >= 32 {
   115  		v1, v2, v3, v4 := x.v1, x.v2, x.v3, x.v4
   116  		h = rol1(v1) + rol7(v2) + rol12(v3) + rol18(v4)
   117  		h = mergeRound(h, v1)
   118  		h = mergeRound(h, v2)
   119  		h = mergeRound(h, v3)
   120  		h = mergeRound(h, v4)
   121  	} else {
   122  		h = x.v3 + prime5
   123  	}
   124  
   125  	h += uint64(x.total)
   126  
   127  	i, end := 0, x.n
   128  	for ; i+8 <= end; i += 8 {
   129  		k1 := round(0, u64(x.mem[i:i+8]))
   130  		h ^= k1
   131  		h = rol27(h)*prime1 + prime4
   132  	}
   133  	if i+4 <= end {
   134  		h ^= uint64(u32(x.mem[i:i+4])) * prime1
   135  		h = rol23(h)*prime2 + prime3
   136  		i += 4
   137  	}
   138  	for i < end {
   139  		h ^= uint64(x.mem[i]) * prime5
   140  		h = rol11(h) * prime1
   141  		i++
   142  	}
   143  
   144  	h ^= h >> 33
   145  	h *= prime2
   146  	h ^= h >> 29
   147  	h *= prime3
   148  	h ^= h >> 32
   149  
   150  	return h
   151  }
   152  
   153  func u64(b []byte) uint64 { return binary.LittleEndian.Uint64(b) }
   154  func u32(b []byte) uint32 { return binary.LittleEndian.Uint32(b) }
   155  
   156  func round(acc, input uint64) uint64 {
   157  	acc += input * prime2
   158  	acc = rol31(acc)
   159  	acc *= prime1
   160  	return acc
   161  }
   162  
   163  func mergeRound(acc, val uint64) uint64 {
   164  	val = round(0, val)
   165  	acc ^= val
   166  	acc = acc*prime1 + prime4
   167  	return acc
   168  }
   169
View as plain text