Go implementation of SipHash-2-4, a fast short-input PRF created by Jean-Philippe Aumasson and Daniel J. Bernstein.

Overview

SipHash (Go)

Build Status

Go implementation of SipHash-2-4, a fast short-input PRF created by Jean-Philippe Aumasson and Daniel J. Bernstein (http://131002.net/siphash/).

Installation

$ go get github.com/dchest/siphash

Usage

import "github.com/dchest/siphash"

There are two ways to use this package. The slower one is to use the standard hash.Hash64 interface:

h := siphash.New(key)
h.Write([]byte("Hello"))
sum := h.Sum(nil) // returns 8-byte []byte

or

sum64 := h.Sum64() // returns uint64

The faster one is to use Hash() function, which takes two uint64 parts of 16-byte key and a byte slice, and returns uint64 hash:

sum64 := siphash.Hash(key0, key1, []byte("Hello"))

The keys and output are little-endian.

Functions

func Hash(k0, k1 uint64, p []byte) uint64

Hash returns the 64-bit SipHash-2-4 of the given byte slice with two 64-bit parts of 128-bit key: k0 and k1.

func Hash128(k0, k1 uint64, p []byte) (uint64, uint64)

Hash128 returns the 128-bit SipHash-2-4 of the given byte slice with two 64-bit parts of 128-bit key: k0 and k1.

Note that 128-bit SipHash is considered experimental by SipHash authors at this time.

func New(key []byte) hash.Hash64

New returns a new hash.Hash64 computing SipHash-2-4 with 16-byte key.

func New128(key []byte) hash.Hash

New128 returns a new hash.Hash computing SipHash-2-4 with 16-byte key and 16-byte output.

Note that 16-byte output is considered experimental by SipHash authors at this time.

Public domain dedication

Written by Dmitry Chestnykh and Damian Gryski.

To the extent possible under law, the authors have dedicated all copyright and related and neighboring rights to this software to the public domain worldwide. This software is distributed without any warranty. http://creativecommons.org/publicdomain/zero/1.0/

Comments
  • ARM assembler performance improvements

    ARM assembler performance improvements

    This patch improves the throughput of the ARM assembler version of siphash by up to 12.46% (on a Raspberry Pi 4B):

    name               old time/op    new time/op     delta
    Hash8-4               194ns ± 3%      192ns ± 1%     ~     (p=0.017 n=20+17)
    Hash16-4              213ns ± 1%      216ns ± 2%   +1.10%  (p=0.008 n=16+18)
    Hash40-4              286ns ± 2%      285ns ± 2%     ~     (p=0.482 n=20+20)
    Hash64-4              354ns ± 3%      355ns ± 2%     ~     (p=0.637 n=20+19)
    Hash128-4             538ns ± 3%      536ns ± 2%     ~     (p=0.333 n=20+17)
    Hash1K-4             3.12µs ± 2%     3.13µs ± 3%     ~     (p=0.913 n=20+18)
    Hash1Kunaligned-4    3.79µs ± 1%     3.70µs ± 1%   -2.51%  (p=0.000 n=18+18)
    Hash8K-4             23.5µs ± 1%     23.8µs ± 4%     ~     (p=0.045 n=18+20)
    Hash128_8-4           280ns ± 4%      272ns ± 2%   -2.75%  (p=0.000 n=20+18)
    Hash128_16-4          304ns ± 3%      298ns ± 3%   -2.15%  (p=0.000 n=20+20)
    Hash128_40-4          370ns ± 2%      364ns ± 3%   -1.53%  (p=0.001 n=19+20)
    Hash128_64-4          438ns ± 1%      436ns ± 2%     ~     (p=0.027 n=17+20)
    Hash128_128-4         624ns ± 2%      619ns ± 2%     ~     (p=0.026 n=20+20)
    Hash128_1K-4         3.26µs ± 3%     3.20µs ± 1%   -1.85%  (p=0.000 n=20+20)
    Hash128_8K-4         23.9µs ± 2%     23.8µs ± 3%     ~     (p=0.160 n=20+19)
    Full8-4               180ns ± 6%      176ns ± 3%   -2.28%  (p=0.000 n=20+20)
    Full16-4              203ns ± 3%      198ns ± 2%   -2.26%  (p=0.000 n=19+20)
    Full40-4              202ns ± 3%      197ns ± 2%   -2.50%  (p=0.000 n=19+19)
    Full64-4              346ns ± 3%      337ns ± 2%   -2.58%  (p=0.000 n=17+20)
    Full128-4             346ns ± 6%      336ns ± 1%   -2.70%  (p=0.000 n=19+20)
    Full1K-4             3.14µs ± 2%     3.09µs ± 2%   -1.40%  (p=0.003 n=17+18)
    Full1Kunaligned-4    3.84µs ± 3%     3.72µs ± 2%   -3.18%  (p=0.000 n=20+20)
    Full8K-4             24.3µs ± 5%     23.7µs ± 2%   -2.17%  (p=0.001 n=19+20)
    Full128_8-4           503ns ± 8%      462ns ± 5%   -8.07%  (p=0.000 n=20+20)
    Full128_16-4          534ns ± 7%      484ns ± 3%   -9.44%  (p=0.000 n=19+20)
    Full128_40-4          545ns ±11%      484ns ± 3%  -11.21%  (p=0.000 n=20+20)
    Full128_64-4          692ns ±10%      621ns ± 3%  -10.24%  (p=0.000 n=20+18)
    Full128_128-4         685ns ± 7%      623ns ± 4%   -9.09%  (p=0.000 n=19+20)
    Full128_1K-4         3.61µs ± 6%     3.40µs ± 2%   -5.75%  (p=0.000 n=19+20)
    Full128_8K-4         25.6µs ± 9%     24.3µs ± 2%   -4.97%  (p=0.000 n=20+20)
    
    name               old speed      new speed       delta
    Hash8-4            41.2MB/s ± 3%   41.7MB/s ± 1%     ~     (p=0.025 n=20+17)
    Hash16-4           74.9MB/s ± 1%   74.2MB/s ± 1%   -1.03%  (p=0.005 n=16+18)
    Hash40-4            140MB/s ± 2%    140MB/s ± 2%     ~     (p=0.482 n=20+20)
    Hash64-4            181MB/s ± 3%    181MB/s ± 2%     ~     (p=0.873 n=20+19)
    Hash128-4           238MB/s ± 3%    239MB/s ± 2%     ~     (p=0.464 n=20+17)
    Hash1K-4            328MB/s ± 2%    327MB/s ± 3%     ~     (p=0.937 n=20+18)
    Hash1Kunaligned-4   270MB/s ± 1%    277MB/s ± 1%   +2.57%  (p=0.000 n=18+18)
    Hash8K-4            348MB/s ± 1%    345MB/s ± 4%     ~     (p=0.045 n=18+20)
    Hash128_8-4        28.7MB/s ± 2%   29.4MB/s ± 2%   +2.41%  (p=0.000 n=18+18)
    Hash128_16-4       52.6MB/s ± 3%   53.8MB/s ± 3%   +2.24%  (p=0.000 n=20+20)
    Hash128_40-4        108MB/s ± 2%    110MB/s ± 3%   +1.57%  (p=0.001 n=19+20)
    Hash128_64-4        146MB/s ± 2%    147MB/s ± 2%     ~     (p=0.013 n=18+20)
    Hash128_128-4       205MB/s ± 2%    207MB/s ± 2%     ~     (p=0.028 n=20+20)
    Hash128_1K-4        314MB/s ± 3%    320MB/s ± 1%   +1.87%  (p=0.000 n=20+20)
    Hash128_8K-4        343MB/s ± 2%    345MB/s ± 3%     ~     (p=0.159 n=20+19)
    Full8-4            44.5MB/s ± 6%   45.6MB/s ± 2%   +2.41%  (p=0.000 n=20+20)
    Full16-4           79.0MB/s ± 3%   80.7MB/s ± 2%   +2.20%  (p=0.000 n=19+20)
    Full40-4            118MB/s ± 6%    122MB/s ± 1%   +3.09%  (p=0.000 n=20+16)
    Full64-4            185MB/s ± 3%    190MB/s ± 2%   +2.45%  (p=0.000 n=18+20)
    Full128-4           369MB/s ± 8%    381MB/s ± 1%   +3.20%  (p=0.000 n=20+20)
    Full1K-4            326MB/s ± 2%    331MB/s ± 2%   +1.42%  (p=0.003 n=17+18)
    Full1Kunaligned-4   267MB/s ± 3%    276MB/s ± 2%   +3.28%  (p=0.000 n=20+20)
    Full8K-4            338MB/s ± 5%    345MB/s ± 2%   +2.19%  (p=0.001 n=19+20)
    Full128_8-4        15.9MB/s ± 9%   17.3MB/s ± 5%   +8.61%  (p=0.000 n=20+20)
    Full128_16-4       30.0MB/s ± 7%   33.1MB/s ± 3%  +10.31%  (p=0.000 n=19+20)
    Full128_40-4       44.1MB/s ±10%   49.6MB/s ± 2%  +12.46%  (p=0.000 n=20+20)
    Full128_64-4       92.7MB/s ±10%  103.1MB/s ± 3%  +11.17%  (p=0.000 n=20+18)
    Full128_128-4       187MB/s ± 6%    206MB/s ± 4%   +9.96%  (p=0.000 n=19+20)
    Full128_1K-4        282MB/s ±10%    301MB/s ± 2%   +6.56%  (p=0.000 n=20+20)
    Full128_8K-4        320MB/s ± 8%    336MB/s ± 2%   +5.03%  (p=0.000 n=20+20)
    
    opened by greatroar 8
  • amd64 implementation of block digest

    amd64 implementation of block digest

    I have an application that leans pretty heavily on incremental hashing, so this change was a big perf win.

    This brings the implementation of hash.Hash64 up to performance parity with Hash(...).

    Also, I marked the slices passed to Hash and Hash128 as noescape.

    Review on Reviewable

    opened by philhofer 6
  • [WIP] Add generic versions of Hash and Hash128

    [WIP] Add generic versions of Hash and Hash128

    New functions can accept []byte or string. Backwards compatibility saved by wrapping new functions. Assembly functions signature changed a bit to allow simple unsafe cast []byte|string to string.

    opened by xakep666 4
  • Use asm Hash() on amd64 from github.com/dgryski/go-siphasm

    Use asm Hash() on amd64 from github.com/dgryski/go-siphasm

    It's quite a nice speedup, and it's just a drop-in file and fix up the build tags.

    I might try to figure out how to add the asm core to digest.blocks() and digest.Sum64()

    benchmark            old ns/op     new ns/op     delta       
    BenchmarkHash8       34.4          26.9          -21.80%     
    BenchmarkHash16      43.8          32.0          -26.94%     
    BenchmarkHash40      75.2          50.4          -32.98%     
    BenchmarkHash64      105           67.9          -35.33%     
    BenchmarkHash128     189           113           -40.21%     
    BenchmarkHash1K      1374          745           -45.78%     
    BenchmarkHash8K      10431         5743          -44.94%     
    
    benchmark            old MB/s     new MB/s     speedup     
    BenchmarkHash8       232.89       297.67       1.28x       
    BenchmarkHash16      365.48       499.44       1.37x       
    BenchmarkHash40      532.24       793.97       1.49x       
    BenchmarkHash64      604.65       942.48       1.56x       
    BenchmarkHash128     677.13       1125.25      1.66x       
    BenchmarkHash1K      744.90       1372.96      1.84x       
    BenchmarkHash8K      785.30       1426.24      1.82x       
    
    opened by dgryski 4
  • fixes for issue #15 -- ARM assembly alignment bug

    fixes for issue #15 -- ARM assembly alignment bug

    This change reintroduces ARM assembly for the streaming hash with a fix for unaligned accesses. The HashXXX() functions for ARM are implemented with calls to the underlying blocks() assembler routine, and so are not performant for tiny input sizes (crossover is at around 16 bytes). Performance benchmarking from a Marvell Armada 3720 here:

    Before:

    goos: linux
    goarch: arm
    pkg: github.com/dchest/siphash
    BenchmarkHash8           	 2000000	       607 ns/op	  13.17 MB/s
    BenchmarkHash16          	 2000000	       768 ns/op	  20.82 MB/s
    BenchmarkHash40          	 1000000	      1208 ns/op	  33.09 MB/s
    BenchmarkHash64          	 1000000	      1658 ns/op	  38.60 MB/s
    BenchmarkHash128         	  500000	      2844 ns/op	  45.00 MB/s
    BenchmarkHash1K          	  100000	     19368 ns/op	  52.87 MB/s
    BenchmarkHash1Kunaligned 	  100000	     19348 ns/op	  52.93 MB/s
    BenchmarkHash8K          	   10000	    151758 ns/op	  53.98 MB/s
    BenchmarkHash128_8       	 2000000	       863 ns/op	   9.27 MB/s
    BenchmarkHash128_16      	 1000000	      1029 ns/op	  15.55 MB/s
    BenchmarkHash128_40      	 1000000	      1469 ns/op	  27.22 MB/s
    BenchmarkHash128_64      	 1000000	      1909 ns/op	  33.52 MB/s
    BenchmarkHash128_128     	  500000	      3084 ns/op	  41.50 MB/s
    BenchmarkHash128_1K      	  100000	     19458 ns/op	  52.62 MB/s
    BenchmarkHash128_8K      	   10000	    150805 ns/op	  54.32 MB/s
    BenchmarkFull8           	 1000000	      1128 ns/op	   7.09 MB/s
    BenchmarkFull16          	 1000000	      1282 ns/op	  12.48 MB/s
    BenchmarkFull40          	 1000000	      1281 ns/op	  18.73 MB/s
    BenchmarkFull64          	 1000000	      2236 ns/op	  28.62 MB/s
    BenchmarkFull128         	 1000000	      2237 ns/op	  57.20 MB/s
    BenchmarkFull1K          	  100000	     21799 ns/op	  46.97 MB/s
    BenchmarkFull1Kunaligned 	  100000	     21479 ns/op	  47.67 MB/s
    BenchmarkFull8K          	   10000	    164920 ns/op	  49.67 MB/s
    BenchmarkFull128_8       	 1000000	      2120 ns/op	   3.77 MB/s
    BenchmarkFull128_16      	 1000000	      2271 ns/op	   7.04 MB/s
    BenchmarkFull128_40      	 1000000	      2266 ns/op	  10.59 MB/s
    BenchmarkFull128_64      	  500000	      3251 ns/op	  19.68 MB/s
    BenchmarkFull128_128     	  500000	      3238 ns/op	  39.53 MB/s
    BenchmarkFull128_1K      	  100000	     22546 ns/op	  45.42 MB/s
    BenchmarkFull128_8K      	   10000	    166300 ns/op	  49.26 MB/s
    PASS
    

    After:

    goos: linux
    goarch: arm
    pkg: github.com/dchest/siphash
    BenchmarkHash8                   2000000               677 ns/op          11.81 MB/s
    BenchmarkHash16                  2000000               737 ns/op          21.71 MB/s
    BenchmarkHash40                  2000000               963 ns/op          41.54 MB/s
    BenchmarkHash64                  1000000              1167 ns/op          54.82 MB/s
    BenchmarkHash128                 1000000              1719 ns/op          74.45 MB/s
    BenchmarkHash1K                   200000              9349 ns/op         109.52 MB/s
    BenchmarkHash1Kunaligned          200000             11115 ns/op          92.12 MB/s
    BenchmarkHash8K                    20000             70468 ns/op         116.25 MB/s
    BenchmarkHash128_8               1000000              1133 ns/op           7.06 MB/s
    BenchmarkHash128_16              1000000              1202 ns/op          13.31 MB/s
    BenchmarkHash128_40              1000000              1437 ns/op          27.83 MB/s
    BenchmarkHash128_64              1000000              1631 ns/op          39.23 MB/s
    BenchmarkHash128_128             1000000              2183 ns/op          58.62 MB/s
    BenchmarkHash128_1K               200000              9795 ns/op         104.54 MB/s
    BenchmarkHash128_8K                20000             70894 ns/op         115.55 MB/s
    BenchmarkFull8                   2000000               694 ns/op          11.52 MB/s
    BenchmarkFull16                  2000000               760 ns/op          21.03 MB/s
    BenchmarkFull40                  2000000               764 ns/op          31.40 MB/s
    BenchmarkFull64                  1000000              1186 ns/op          53.96 MB/s
    BenchmarkFull128                 1000000              1181 ns/op         108.35 MB/s
    BenchmarkFull1K                   200000              9399 ns/op         108.94 MB/s
    BenchmarkFull1Kunaligned          200000             11186 ns/op          91.54 MB/s
    BenchmarkFull8K                    20000             70458 ns/op         116.27 MB/s
    BenchmarkFull128_8               1000000              2005 ns/op           3.99 MB/s
    BenchmarkFull128_16              1000000              2066 ns/op           7.74 MB/s
    BenchmarkFull128_40              1000000              2076 ns/op          11.56 MB/s
    BenchmarkFull128_64               500000              2495 ns/op          25.64 MB/s
    BenchmarkFull128_128              500000              2492 ns/op          51.36 MB/s
    BenchmarkFull128_1K               200000             10705 ns/op          95.65 MB/s
    BenchmarkFull128_8K                20000             71909 ns/op         113.92 MB/s
    PASS
    
    opened by rakitzis 2
  • fix vet warnings about names of stack variables referenced from asm

    fix vet warnings about names of stack variables referenced from asm

    In blocks_amd64.s the change from data_len to p_len is because the function is declared as:

    func blocks(d *digest, p []uint8)
    

    In hash_asm.go.

    After these changes, go vet has nothing left to complain about :)

    opened by bpowers 2
  • Add ARM assembly for once(), finalize(), blocks(), Hash() and Hash128()

    Add ARM assembly for once(), finalize(), blocks(), Hash() and Hash128()

    Approx 2-4x improvement depending on the buffer size.

    Tested on ARMv7:

    Processor   : Marvell PJ4Bv7 Processor rev 2 (v7l)
    processor   : 0
    BogoMIPS    : 1332.01
    
    opened by rakitzis 2
  • GCC generated assembly prevents people compile it with real GCC

    GCC generated assembly prevents people compile it with real GCC

    The GCC generated code is pretty useful for people with official gc compiler, but it prevents to build this project with a real gccgo because the assembly generated by gcc conflicts with the hardcoded asm files.

    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s: Assembler messages:
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:14: Error: no such instruction: `text ·Hash128(SB),4,$0-56'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:15: Error: junk `(FP)' after expression
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:15: Error: too many memory references for `movq'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:16: Error: operand size mismatch for `movq'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:17: Error: junk `(FP)' after expression
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:17: Error: too many memory references for `movq'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:18: Error: operand size mismatch for `movq'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:19: Error: operand size mismatch for `movq'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:20: Error: junk `(FP)' after expression
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:20: Error: too many memory references for `movq'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:22: Error: too many memory references for `movq'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:23: Error: too many memory references for `movq'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:24: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:25: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:26: Error: operand size mismatch for `movq'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:27: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:28: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:30: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:31: Error: junk `(FP)' after expression
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:31: Error: too many memory references for `movq'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:34: Error: too many memory references for `xchg'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:36: Error: junk `(SI)(DI*1)' after expression
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:36: Error: too many memory references for `movq'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:37: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:39: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:42: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:43: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:45: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:46: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:48: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:50: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:51: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:53: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:54: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:57: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:58: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:60: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:61: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:64: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:66: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:67: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:68: Error: too many memory references for `cmp'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:71: Error: too many memory references for `sub'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:73: Error: operand size mismatch for `cmp'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:78: Error: operand size mismatch for `cmp'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:81: Error: operand size mismatch for `cmp'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:84: Error: operand size mismatch for `cmp'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:87: Error: operand size mismatch for `cmp'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:90: Error: operand size mismatch for `cmp'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:93: Error: operand size mismatch for `cmp'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:96: Error: operand size mismatch for `cmp'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:101: Error: no such instruction: `movbqzx 6(SI)(DI*1),DX'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:103: Error: too many memory references for `or'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:104: Error: no such instruction: `movbqzx 0x5(SI)(DI*1),DX'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:106: Error: too many memory references for `or'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:107: Error: no such instruction: `movbqzx 0x4(SI)(DI*1),DX'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:109: Error: too many memory references for `or'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:110: Error: no such instruction: `movbqzx 0x3(SI)(DI*1),DX'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:112: Error: too many memory references for `or'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:113: Error: no such instruction: `movbqzx 0x2(SI)(DI*1),DX'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:115: Error: too many memory references for `or'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:116: Error: no such instruction: `movbqzx 0x1(SI)(DI*1),DX'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:118: Error: too many memory references for `or'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:119: Error: no such instruction: `movbqzx 0(SI)(DI*1),DX'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:120: Error: too many memory references for `or'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:122: Error: junk `(R9*1)' after expression
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:122: Error: too many memory references for `lea'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:123: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:125: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:126: Error: too many memory references for `movq'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:127: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:130: Error: junk `(BX)(AX*1)' after expression
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:130: Error: too many memory references for `lea'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:131: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:133: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:135: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:136: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:138: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:140: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:141: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:144: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:145: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:147: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:148: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:151: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:152: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:154: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:156: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:158: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:159: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:161: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:162: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:165: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:166: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:168: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:169: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:172: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:174: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:175: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:177: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:179: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:180: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:182: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:183: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:186: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:187: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:189: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:190: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:192: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:195: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:202: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:204: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:206: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:207: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:209: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:210: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:213: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:214: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:219: Error: too many memory references for `movq'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:220: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:221: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:222: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:223: Error: too many memory references for `movq'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:228: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:230: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:232: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:233: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:235: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:236: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:239: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:240: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:242: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:243: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:246: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:248: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:249: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:251: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:253: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:254: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:256: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:257: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:260: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:261: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:263: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:264: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:266: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:269: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:271: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:273: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:275: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:276: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:278: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:279: Error: too many memory references for `add'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:282: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:283: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:286: Error: too many memory references for `movq'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:287: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:288: Error: too many memory references for `xor'
    Projects/go/src/github.com/dchest/siphash/hash128_amd64.s:289: Error: too many memory references for `xor'
    

    After remove all assembly from the code, it compiles and runs fine with gccgo. Is there a possible solution to allow both gc and gccgo work flawlessly?

    opened by biergaizi 2
  • Incorrect hash values depending on how the data is written

    Incorrect hash values depending on how the data is written

    The same string of bytes results in different hash values depending on how you write it. The test below writes a message in chunks sized from one to the length of the message, and calls Sum() with any remaining bytes that don't completely fill a chunk. It succeeds for chunk sizes of 1, 3, 5, and 15 (the entire message) but fails for the others. Also interesting: the incorrect values are all longer than the expected 8 bytes.

    package siphash
    
    import (
        "bytes"
        "encoding/hex"
        "testing"
    
        "github.com/dchest/siphash"
    )
    
    func TestChunking(t *testing.T) {
        key, _ := hex.DecodeString("000102030405060708090a0b0c0d0e0f")
        m, _ := hex.DecodeString("000102030405060708090a0b0c0d0e")
        expected, _ := hex.DecodeString("e545be4961ca29a1")
    
        for step := 1; step <= len(m); step++ {
            s := siphash.New(key)
            c := m
            for len(c) >= step {
                s.Write(c[:step])
                c = c[step:]
            }
    
            if h := s.Sum(c); !bytes.Equal(expected, h) {
                t.Errorf("Incorrect hash: step=%d length=%d hash=%v", step, len(h), h)
            }
        }
    }
    
    
    invalid 
    opened by pcekm 2
  • Simplify switch in amd64 assembler

    Simplify switch in amd64 assembler

    After the main loop, Hash has to process the remaining 0-7 bytes. The amd64 versions of Hash and Hash128 check whether they have >=8 bytes left. They never do, so they can instead check whether they have zero bytes left by AND'ing len(p) with 7, and skip the whole switch if the result is zero. Then, the check for 1 byte left at the end of the switch can also be skipped.

    This gives a tiny performance gain for short inputs. Benchmark results on Linux/Go 1.16:

    name               old speed      new speed      delta
    Hash8-8             511MB/s ± 1%   524MB/s ± 0%  +2.57%  (p=0.000 n=10+10)
    Hash16-8            842MB/s ± 0%   853MB/s ± 0%  +1.31%  (p=0.000 n=9+10)
    Hash40-8           1.36GB/s ± 1%  1.37GB/s ± 1%  +0.81%  (p=0.000 n=10+10)
    Hash64-8           1.59GB/s ± 1%  1.60GB/s ± 0%  +0.63%  (p=0.006 n=10+9)
    Hash128-8          1.87GB/s ± 1%  1.89GB/s ± 0%  +0.75%  (p=0.000 n=9+10)
    Hash1K-8           2.25GB/s ± 0%  2.24GB/s ± 1%    ~     (p=0.447 n=9+10)
    Hash1Kunaligned-8  2.25GB/s ± 1%  2.26GB/s ± 1%  +0.50%  (p=0.003 n=10+10)
    Hash8K-8           2.32GB/s ± 1%  2.32GB/s ± 1%    ~     (p=0.631 n=10+10)
    Hash128_8-8         347MB/s ± 0%   351MB/s ± 0%  +1.39%  (p=0.000 n=9+10)
    Hash128_16-8        599MB/s ± 1%   613MB/s ± 1%  +2.30%  (p=0.000 n=10+10)
    Hash128_40-8       1.07GB/s ± 1%  1.09GB/s ± 1%  +1.11%  (p=0.000 n=9+10)
    Hash128_64-8       1.34GB/s ± 0%  1.35GB/s ± 0%  +0.30%  (p=0.006 n=8+9)
    Hash128_128-8      1.67GB/s ± 1%  1.69GB/s ± 1%  +1.06%  (p=0.000 n=10+10)
    Hash128_1K-8       2.21GB/s ± 1%  2.21GB/s ± 1%    ~     (p=0.356 n=9+10)
    Hash128_8K-8       2.32GB/s ± 1%  2.30GB/s ± 0%  -0.65%  (p=0.004 n=9+9)
    
    opened by greatroar 1
  • Add a go.mod to enable build without $GO111MODULE

    Add a go.mod to enable build without $GO111MODULE

    Go 1.16 refuses to go build siphash when freshly cloned, because there is no go.mod:

    $ git clone https://github.com/dchest/siphash.git
    Cloning into 'siphash'...
    remote: Enumerating objects: 8, done.
    remote: Counting objects: 100% (8/8), done.
    remote: Compressing objects: 100% (8/8), done.
    remote: Total 199 (delta 1), reused 2 (delta 0), pack-reused 191
    Receiving objects: 100% (199/199), 53.08 KiB | 2.12 MiB/s, done.
    Resolving deltas: 100% (93/93), done.
    
    $ cd siphash
    
    $ go build
    go: cannot find main module, but found .git/config in /tmp/siphash
    	to create a module there, run:
    	go mod init
    

    This adds the go.mod that go mod init produces.

    opened by greatroar 1
Releases(v1.2.3)
Owner
Dmitry Chestnykh
Founder of @coding-robots. Invented "I Write Like". Previously created BlogJet (acquired) and StableLib. Interested in cryptography and perfect code.
Dmitry Chestnykh
Implementation of Boyer-Moore fast string search algorithm in Go

boyermoore Implementation of Boyer-Moore fast string search algorithm in Go

sarp dağ demirel 52 Oct 7, 2022
Go native library for fast point tracking and K-Nearest queries

Geo Index Geo Index library Overview Splits the earth surface in a grid. At each cell we can store data, such as list of points, count of points, etc.

Hailo Network IP Ltd 342 Nov 19, 2022
Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching.

Trie Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching. Usage Create a Trie with: t := trie.New() Add Keys with:

Derek Parker 614 Nov 22, 2022
Fast and easy-to-use skip list for Go.

Skip List in Golang Skip list is an ordered map. See wikipedia page skip list to learn algorithm details about this data structure. Highlights in this

Huan Du 303 Nov 7, 2022
An app with Trie tree and Breve search Implementation CLI and HTTP both 🥳

Introduction LifeLongLearner project consists of two different parts. My English Vocabulary My Technical Book Notes All of them provided by me within

A.Samet İleri 15 Jul 1, 2022
Fast ring-buffer deque (double-ended queue)

deque Fast ring-buffer deque (double-ended queue) implementation. For a pictorial description, see the Deque diagram Installation $ go get github.com/

Andrew Gillis 400 Nov 11, 2022
Fast in-memory key:value store/cache with TTL

MCache library go-mcache - this is a fast key:value storage. Its major advantage is that, being essentially a thread-safe . map[string]interface{} wit

O.J 86 Nov 11, 2022
A fast little LRU cache for Go

tinylru A fast little LRU cache. Getting Started Installing To start using tinylru, install Go and run go get: $ go get -u github.com/tidwall/tinylru

Josh Baker 126 Oct 14, 2022
Fast Raft framework using the Redis protocol for Go

This project has been archived. Please check out Uhaha for a fitter, happier, more productive Raft framework. Finn is a fast and simple framework for

Josh Baker 543 Oct 10, 2022
Fast golang queue using ring-buffer

Queue A fast Golang queue using a ring-buffer, based on the version suggested by Dariusz Górecki. Using this instead of other, simpler, queue implemen

Evan Huus 475 Nov 20, 2022
go/golang: fast bit set Bloom filter

package implements a fast bloom filter with real 'bitset' and JSONMarshal/JSONUnmarshal to store/reload the Bloom filter.

Andreas Briese 125 Nov 3, 2022
dagger is a fast, concurrency safe, mutable, in-memory directed graph library with zero dependencies

dagger is a blazing fast, concurrency safe, mutable, in-memory directed graph implementation with zero dependencies

Coleman Word 266 Nov 11, 2022
A fast (5x) string keyed read-only map for Go - particularly good for keys using a small set of nearby runes.

faststringmap faststringmap is a fast read-only string keyed map for Go (golang). For our use case it is approximately 5 times faster than using Go's

The Sensible Code Company 29 Nov 11, 2022
A fast, threadsafe skip list in Go

fast-skiplist Purpose As the basic building block of an in-memory data structure store, I needed an implementation of skip lists in Go. It needed to b

sean 240 Nov 10, 2022
Go implementation of C++ STL iterators and algorithms.

iter Go implementation of C++ STL iterators and algorithms. Less hand-written loops, more expressive code. README translations: 简体中文 Motivation Althou

disksing 172 Nov 16, 2022
Package ring provides a high performance and thread safe Go implementation of a bloom filter.

ring - high performance bloom filter Package ring provides a high performance and thread safe Go implementation of a bloom filter. Usage Please see th

Tanner Ryan 130 Nov 20, 2022
HyperLogLog and HyperLogLog++ implementation in Go/Golang.

HyperLogLog and HyperLogLog++ Implements the HyperLogLog and HyperLogLog++ algorithms. HyperLogLog paper: http://algo.inria.fr/flajolet/Publications/F

Clark DuVall 424 Nov 24, 2022
Data Structure Libraries and Algorithms implementation

Algorithms Data Structure Libraries and Algorithms implementation in C++ Disclaimer This repository is meant to be used as a reference to learn data s

Priyank Chheda 641 Nov 12, 2022
Data structures and algorithms implementation from ZeroToMastery course

ZeroToMastery Data Structures & Algorithms course This repo includes all the data structure and algorithm exercises solutions and implementations. Ins

Fabio Bozzo 3 Jul 4, 2022