siphash.go raw

   1  package filter
   2  
   3  import "encoding/binary"
   4  
   5  // SipHash-2-4 constants.
   6  const (
   7  	sipC = 2 // compression rounds per message block
   8  	sipD = 4 // finalization rounds
   9  )
  10  
  11  // siphash24 computes the SipHash-2-4 MAC of msg under key and returns the
  12  // 64-bit tag. The key is interpreted as two little-endian uint64s, as required
  13  // by the reference implementation and BIP158.
  14  func siphash24(key [16]byte, msg []byte) uint64 {
  15  	k0 := binary.LittleEndian.Uint64(key[0:8])
  16  	k1 := binary.LittleEndian.Uint64(key[8:16])
  17  
  18  	v0 := k0 ^ 0x736f6d6570736575
  19  	v1 := k1 ^ 0x646f72616e646f6d
  20  	v2 := k0 ^ 0x6c7967656e657261
  21  	v3 := k1 ^ 0x7465646279746573
  22  
  23  	length := len(msg)
  24  
  25  	// Process all complete 8-byte little-endian words.
  26  	for len(msg) >= 8 {
  27  		m := binary.LittleEndian.Uint64(msg[:8])
  28  		msg = msg[8:]
  29  
  30  		v3 ^= m
  31  		for i := 0; i < sipC; i++ {
  32  			v0, v1, v2, v3 = sipRound(v0, v1, v2, v3)
  33  		}
  34  		v0 ^= m
  35  	}
  36  
  37  	// The last block contains the remaining 0..7 bytes followed by the total
  38  	// message length modulo 256 in the top byte.
  39  	var b uint64
  40  	for i, c := range msg {
  41  		b |= uint64(c) << (8 * uint(i))
  42  	}
  43  	b |= uint64(length) << 56
  44  
  45  	v3 ^= b
  46  	for i := 0; i < sipC; i++ {
  47  		v0, v1, v2, v3 = sipRound(v0, v1, v2, v3)
  48  	}
  49  	v0 ^= b
  50  
  51  	v2 ^= 0xff
  52  	for i := 0; i < sipD; i++ {
  53  		v0, v1, v2, v3 = sipRound(v0, v1, v2, v3)
  54  	}
  55  
  56  	return v0 ^ v1 ^ v2 ^ v3
  57  }
  58  
  59  // sipRound performs one SipHash round. The four state words are passed and
  60  // returned by value so the round can be inlined by the compiler.
  61  func sipRound(v0, v1, v2, v3 uint64) (uint64, uint64, uint64, uint64) {
  62  	v0 += v1
  63  	v1 = v1<<13 | v1>>(64-13)
  64  	v1 ^= v0
  65  	v0 = v0<<32 | v0>>(64-32)
  66  
  67  	v2 += v3
  68  	v3 = v3<<16 | v3>>(64-16)
  69  	v3 ^= v2
  70  
  71  	v0 += v3
  72  	v3 = v3<<21 | v3>>(64-21)
  73  	v3 ^= v0
  74  
  75  	v2 += v1
  76  	v1 = v1<<17 | v1>>(64-17)
  77  	v1 ^= v2
  78  	v2 = v2<<32 | v2>>(64-32)
  79  
  80  	return v0, v1, v2, v3
  81  }
  82