diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-28 12:36:04 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-28 12:36:04 +0000 |
commit | b09c6d56832eb1718c07d74abf3bc6ae3fe4e030 (patch) | |
tree | d2caec2610d4ea887803ec9e9c3cd77136c448ba /dependencies/pkg/mod/github.com/cespare | |
parent | Initial commit. (diff) | |
download | icingadb-b09c6d56832eb1718c07d74abf3bc6ae3fe4e030.tar.xz icingadb-b09c6d56832eb1718c07d74abf3bc6ae3fe4e030.zip |
Adding upstream version 1.1.0.upstream/1.1.0upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'dependencies/pkg/mod/github.com/cespare')
19 files changed, 1182 insertions, 0 deletions
diff --git a/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/.github/workflows/test.yml b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/.github/workflows/test.yml new file mode 100644 index 0000000..606cf83 --- /dev/null +++ b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/.github/workflows/test.yml @@ -0,0 +1,32 @@ +name: Test + +on: + push: + branches: [main] + pull_request: + +jobs: + test: + strategy: + matrix: + go-version: [1.16.x, 1.17.x] + os: [ubuntu-latest, macos-latest, windows-latest] + runs-on: ${{ matrix.os }} + + steps: + - name: Install go + uses: actions/setup-go@v2 + with: + go-version: ${{ matrix.go-version }} + + - name: Check out code + uses: actions/checkout@v2 + + - name: Test + run: go test -count 1 -bench . -benchtime 1x ./... + + - name: Test with -tags purego + run: go test -count 1 -bench . -benchtime 1x -tags purego ./... + +# TODO: Test on other architectures. Unfortunately only amd64 is supported +# by GH Actions. We could use QEMU in the meantime. diff --git a/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/LICENSE.txt b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/LICENSE.txt new file mode 100644 index 0000000..24b5306 --- /dev/null +++ b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/LICENSE.txt @@ -0,0 +1,22 @@ +Copyright (c) 2016 Caleb Spare + +MIT License + +Permission is hereby granted, free of charge, to any person obtaining +a copy of this software and associated documentation files (the +"Software"), to deal in the Software without restriction, including +without limitation the rights to use, copy, modify, merge, publish, +distribute, sublicense, and/or sell copies of the Software, and to +permit persons to whom the Software is furnished to do so, subject to +the following conditions: + +The above copyright notice and this permission notice shall be +included in all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE +LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION +OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION +WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. diff --git a/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/README.md b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/README.md new file mode 100644 index 0000000..792b4a6 --- /dev/null +++ b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/README.md @@ -0,0 +1,69 @@ +# xxhash + +[![Go Reference](https://pkg.go.dev/badge/github.com/cespare/xxhash/v2.svg)](https://pkg.go.dev/github.com/cespare/xxhash/v2) +[![Test](https://github.com/cespare/xxhash/actions/workflows/test.yml/badge.svg)](https://github.com/cespare/xxhash/actions/workflows/test.yml) + +xxhash is a Go implementation of the 64-bit +[xxHash](http://cyan4973.github.io/xxHash/) algorithm, XXH64. This is a +high-quality hashing algorithm that is much faster than anything in the Go +standard library. + +This package provides a straightforward API: + +``` +func Sum64(b []byte) uint64 +func Sum64String(s string) uint64 +type Digest struct{ ... } + func New() *Digest +``` + +The `Digest` type implements hash.Hash64. Its key methods are: + +``` +func (*Digest) Write([]byte) (int, error) +func (*Digest) WriteString(string) (int, error) +func (*Digest) Sum64() uint64 +``` + +This implementation provides a fast pure-Go implementation and an even faster +assembly implementation for amd64. + +## Compatibility + +This package is in a module and the latest code is in version 2 of the module. +You need a version of Go with at least "minimal module compatibility" to use +github.com/cespare/xxhash/v2: + +* 1.9.7+ for Go 1.9 +* 1.10.3+ for Go 1.10 +* Go 1.11 or later + +I recommend using the latest release of Go. + +## Benchmarks + +Here are some quick benchmarks comparing the pure-Go and assembly +implementations of Sum64. + +| input size | purego | asm | +| --- | --- | --- | +| 5 B | 979.66 MB/s | 1291.17 MB/s | +| 100 B | 7475.26 MB/s | 7973.40 MB/s | +| 4 KB | 17573.46 MB/s | 17602.65 MB/s | +| 10 MB | 17131.46 MB/s | 17142.16 MB/s | + +These numbers were generated on Ubuntu 18.04 with an Intel i7-8700K CPU using +the following commands under Go 1.11.2: + +``` +$ go test -tags purego -benchtime 10s -bench '/xxhash,direct,bytes' +$ go test -benchtime 10s -bench '/xxhash,direct,bytes' +``` + +## Projects using this package + +- [InfluxDB](https://github.com/influxdata/influxdb) +- [Prometheus](https://github.com/prometheus/prometheus) +- [VictoriaMetrics](https://github.com/VictoriaMetrics/VictoriaMetrics) +- [FreeCache](https://github.com/coocood/freecache) +- [FastCache](https://github.com/VictoriaMetrics/fastcache) diff --git a/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/bench_test.go b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/bench_test.go new file mode 100644 index 0000000..4dfeb91 --- /dev/null +++ b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/bench_test.go @@ -0,0 +1,74 @@ +package xxhash + +import ( + "strings" + "testing" +) + +var benchmarks = []struct { + name string + n int64 +}{ + {"4B", 4}, + {"100B", 100}, + {"4KB", 4e3}, + {"10MB", 10e6}, +} + +func BenchmarkSum64(b *testing.B) { + for _, bb := range benchmarks { + in := make([]byte, bb.n) + for i := range in { + in[i] = byte(i) + } + b.Run(bb.name, func(b *testing.B) { + b.SetBytes(bb.n) + for i := 0; i < b.N; i++ { + _ = Sum64(in) + } + }) + } +} + +func BenchmarkSum64String(b *testing.B) { + for _, bb := range benchmarks { + s := strings.Repeat("a", int(bb.n)) + b.Run(bb.name, func(b *testing.B) { + b.SetBytes(bb.n) + for i := 0; i < b.N; i++ { + _ = Sum64String(s) + } + }) + } +} + +func BenchmarkDigestBytes(b *testing.B) { + for _, bb := range benchmarks { + in := make([]byte, bb.n) + for i := range in { + in[i] = byte(i) + } + b.Run(bb.name, func(b *testing.B) { + b.SetBytes(bb.n) + for i := 0; i < b.N; i++ { + h := New() + h.Write(in) + _ = h.Sum64() + } + }) + } +} + +func BenchmarkDigestString(b *testing.B) { + for _, bb := range benchmarks { + s := strings.Repeat("a", int(bb.n)) + b.Run(bb.name, func(b *testing.B) { + b.SetBytes(bb.n) + for i := 0; i < b.N; i++ { + h := New() + h.WriteString(s) + _ = h.Sum64() + } + }) + } +} diff --git a/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/dynamic/.gitignore b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/dynamic/.gitignore new file mode 100644 index 0000000..8a84f19 --- /dev/null +++ b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/dynamic/.gitignore @@ -0,0 +1 @@ +/plugin.so diff --git a/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/dynamic/dynamic_test.go b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/dynamic/dynamic_test.go new file mode 100644 index 0000000..c86bc93 --- /dev/null +++ b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/dynamic/dynamic_test.go @@ -0,0 +1,46 @@ +// +build linux darwin + +package main + +import ( + "bytes" + "log" + "os/exec" + "plugin" + "testing" +) + +// This is a cursory test that checks whether things work under dynamic linking. + +func TestMain(m *testing.M) { + cmd := exec.Command( + "go", "build", + "-buildmode", "plugin", + "-o", "plugin.so", + "plugin.go", + ) + var out bytes.Buffer + cmd.Stdout = &out + cmd.Stderr = &out + if err := cmd.Run(); err != nil { + log.Fatalf("Error building plugin: %s\nOutput:\n%s", err, out.String()) + } + m.Run() +} + +func TestDynamic(t *testing.T) { + plug, err := plugin.Open("plugin.so") + if err != nil { + t.Fatal(err) + } + for _, test := range []string{ + "TestSum", + "TestDigest", + } { + f, err := plug.Lookup(test) + if err != nil { + t.Fatalf("cannot find func %s: %s", test, err) + } + f.(func(*testing.T))(t) + } +} diff --git a/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/dynamic/plugin.go b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/dynamic/plugin.go new file mode 100644 index 0000000..319ed71 --- /dev/null +++ b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/dynamic/plugin.go @@ -0,0 +1,46 @@ +// +build ignore + +package main + +import ( + "fmt" + "log" + "testing" + + "github.com/cespare/xxhash/v2" +) + +const ( + in = "Call me Ishmael. Some years ago--never mind how long precisely-" + want = 0x02a2e85470d6fd96 +) + +func TestSum(t *testing.T) { + got := xxhash.Sum64String(in) + if got != want { + t.Fatalf("Sum64String: got 0x%x; want 0x%x", got, want) + } +} + +func TestDigest(t *testing.T) { + for chunkSize := 1; chunkSize <= len(in); chunkSize++ { + name := fmt.Sprintf("[chunkSize=%d]", chunkSize) + t.Run(name, func(t *testing.T) { + d := xxhash.New() + for i := 0; i < len(in); i += chunkSize { + chunk := in[i:] + if len(chunk) > chunkSize { + chunk = chunk[:chunkSize] + } + n, err := d.WriteString(chunk) + if err != nil || n != len(chunk) { + t.Fatalf("Digest.WriteString: got (%d, %v); want (%d, nil)", + n, err, len(chunk)) + } + } + if got := d.Sum64(); got != want { + log.Fatalf("Digest.Sum64: got 0x%x; want 0x%x", got, want) + } + }) + } +} diff --git a/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/go.mod b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/go.mod new file mode 100644 index 0000000..49f6760 --- /dev/null +++ b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/go.mod @@ -0,0 +1,3 @@ +module github.com/cespare/xxhash/v2 + +go 1.11 diff --git a/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/go.sum b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/go.sum new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/go.sum diff --git a/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash.go b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash.go new file mode 100644 index 0000000..15c835d --- /dev/null +++ b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash.go @@ -0,0 +1,235 @@ +// Package xxhash implements the 64-bit variant of xxHash (XXH64) as described +// at http://cyan4973.github.io/xxHash/. +package xxhash + +import ( + "encoding/binary" + "errors" + "math/bits" +) + +const ( + prime1 uint64 = 11400714785074694791 + prime2 uint64 = 14029467366897019727 + prime3 uint64 = 1609587929392839161 + prime4 uint64 = 9650029242287828579 + prime5 uint64 = 2870177450012600261 +) + +// NOTE(caleb): I'm using both consts and vars of the primes. Using consts where +// possible in the Go code is worth a small (but measurable) performance boost +// by avoiding some MOVQs. Vars are needed for the asm and also are useful for +// convenience in the Go code in a few places where we need to intentionally +// avoid constant arithmetic (e.g., v1 := prime1 + prime2 fails because the +// result overflows a uint64). +var ( + prime1v = prime1 + prime2v = prime2 + prime3v = prime3 + prime4v = prime4 + prime5v = prime5 +) + +// Digest implements hash.Hash64. +type Digest struct { + v1 uint64 + v2 uint64 + v3 uint64 + v4 uint64 + total uint64 + mem [32]byte + n int // how much of mem is used +} + +// New creates a new Digest that computes the 64-bit xxHash algorithm. +func New() *Digest { + var d Digest + d.Reset() + return &d +} + +// Reset clears the Digest's state so that it can be reused. +func (d *Digest) Reset() { + d.v1 = prime1v + prime2 + d.v2 = prime2 + d.v3 = 0 + d.v4 = -prime1v + d.total = 0 + d.n = 0 +} + +// Size always returns 8 bytes. +func (d *Digest) Size() int { return 8 } + +// BlockSize always returns 32 bytes. +func (d *Digest) BlockSize() int { return 32 } + +// Write adds more data to d. It always returns len(b), nil. +func (d *Digest) Write(b []byte) (n int, err error) { + n = len(b) + d.total += uint64(n) + + if d.n+n < 32 { + // This new data doesn't even fill the current block. + copy(d.mem[d.n:], b) + d.n += n + return + } + + if d.n > 0 { + // Finish off the partial block. + copy(d.mem[d.n:], b) + d.v1 = round(d.v1, u64(d.mem[0:8])) + d.v2 = round(d.v2, u64(d.mem[8:16])) + d.v3 = round(d.v3, u64(d.mem[16:24])) + d.v4 = round(d.v4, u64(d.mem[24:32])) + b = b[32-d.n:] + d.n = 0 + } + + if len(b) >= 32 { + // One or more full blocks left. + nw := writeBlocks(d, b) + b = b[nw:] + } + + // Store any remaining partial block. + copy(d.mem[:], b) + d.n = len(b) + + return +} + +// Sum appends the current hash to b and returns the resulting slice. +func (d *Digest) Sum(b []byte) []byte { + s := d.Sum64() + return append( + b, + byte(s>>56), + byte(s>>48), + byte(s>>40), + byte(s>>32), + byte(s>>24), + byte(s>>16), + byte(s>>8), + byte(s), + ) +} + +// Sum64 returns the current hash. +func (d *Digest) Sum64() uint64 { + var h uint64 + + if d.total >= 32 { + v1, v2, v3, v4 := d.v1, d.v2, d.v3, d.v4 + h = rol1(v1) + rol7(v2) + rol12(v3) + rol18(v4) + h = mergeRound(h, v1) + h = mergeRound(h, v2) + h = mergeRound(h, v3) + h = mergeRound(h, v4) + } else { + h = d.v3 + prime5 + } + + h += d.total + + i, end := 0, d.n + for ; i+8 <= end; i += 8 { + k1 := round(0, u64(d.mem[i:i+8])) + h ^= k1 + h = rol27(h)*prime1 + prime4 + } + if i+4 <= end { + h ^= uint64(u32(d.mem[i:i+4])) * prime1 + h = rol23(h)*prime2 + prime3 + i += 4 + } + for i < end { + h ^= uint64(d.mem[i]) * prime5 + h = rol11(h) * prime1 + i++ + } + + h ^= h >> 33 + h *= prime2 + h ^= h >> 29 + h *= prime3 + h ^= h >> 32 + + return h +} + +const ( + magic = "xxh\x06" + marshaledSize = len(magic) + 8*5 + 32 +) + +// MarshalBinary implements the encoding.BinaryMarshaler interface. +func (d *Digest) MarshalBinary() ([]byte, error) { + b := make([]byte, 0, marshaledSize) + b = append(b, magic...) + b = appendUint64(b, d.v1) + b = appendUint64(b, d.v2) + b = appendUint64(b, d.v3) + b = appendUint64(b, d.v4) + b = appendUint64(b, d.total) + b = append(b, d.mem[:d.n]...) + b = b[:len(b)+len(d.mem)-d.n] + return b, nil +} + +// UnmarshalBinary implements the encoding.BinaryUnmarshaler interface. +func (d *Digest) UnmarshalBinary(b []byte) error { + if len(b) < len(magic) || string(b[:len(magic)]) != magic { + return errors.New("xxhash: invalid hash state identifier") + } + if len(b) != marshaledSize { + return errors.New("xxhash: invalid hash state size") + } + b = b[len(magic):] + b, d.v1 = consumeUint64(b) + b, d.v2 = consumeUint64(b) + b, d.v3 = consumeUint64(b) + b, d.v4 = consumeUint64(b) + b, d.total = consumeUint64(b) + copy(d.mem[:], b) + d.n = int(d.total % uint64(len(d.mem))) + return nil +} + +func appendUint64(b []byte, x uint64) []byte { + var a [8]byte + binary.LittleEndian.PutUint64(a[:], x) + return append(b, a[:]...) +} + +func consumeUint64(b []byte) ([]byte, uint64) { + x := u64(b) + return b[8:], x +} + +func u64(b []byte) uint64 { return binary.LittleEndian.Uint64(b) } +func u32(b []byte) uint32 { return binary.LittleEndian.Uint32(b) } + +func round(acc, input uint64) uint64 { + acc += input * prime2 + acc = rol31(acc) + acc *= prime1 + return acc +} + +func mergeRound(acc, val uint64) uint64 { + val = round(0, val) + acc ^= val + acc = acc*prime1 + prime4 + return acc +} + +func rol1(x uint64) uint64 { return bits.RotateLeft64(x, 1) } +func rol7(x uint64) uint64 { return bits.RotateLeft64(x, 7) } +func rol11(x uint64) uint64 { return bits.RotateLeft64(x, 11) } +func rol12(x uint64) uint64 { return bits.RotateLeft64(x, 12) } +func rol18(x uint64) uint64 { return bits.RotateLeft64(x, 18) } +func rol23(x uint64) uint64 { return bits.RotateLeft64(x, 23) } +func rol27(x uint64) uint64 { return bits.RotateLeft64(x, 27) } +func rol31(x uint64) uint64 { return bits.RotateLeft64(x, 31) } diff --git a/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash_amd64.go b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash_amd64.go new file mode 100644 index 0000000..ad14b80 --- /dev/null +++ b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash_amd64.go @@ -0,0 +1,13 @@ +// +build !appengine +// +build gc +// +build !purego + +package xxhash + +// Sum64 computes the 64-bit xxHash digest of b. +// +//go:noescape +func Sum64(b []byte) uint64 + +//go:noescape +func writeBlocks(d *Digest, b []byte) int diff --git a/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash_amd64.s b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash_amd64.s new file mode 100644 index 0000000..be8db5b --- /dev/null +++ b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash_amd64.s @@ -0,0 +1,215 @@ +// +build !appengine +// +build gc +// +build !purego + +#include "textflag.h" + +// Register allocation: +// AX h +// SI pointer to advance through b +// DX n +// BX loop end +// R8 v1, k1 +// R9 v2 +// R10 v3 +// R11 v4 +// R12 tmp +// R13 prime1v +// R14 prime2v +// DI prime4v + +// round reads from and advances the buffer pointer in SI. +// It assumes that R13 has prime1v and R14 has prime2v. +#define round(r) \ + MOVQ (SI), R12 \ + ADDQ $8, SI \ + IMULQ R14, R12 \ + ADDQ R12, r \ + ROLQ $31, r \ + IMULQ R13, r + +// mergeRound applies a merge round on the two registers acc and val. +// It assumes that R13 has prime1v, R14 has prime2v, and DI has prime4v. +#define mergeRound(acc, val) \ + IMULQ R14, val \ + ROLQ $31, val \ + IMULQ R13, val \ + XORQ val, acc \ + IMULQ R13, acc \ + ADDQ DI, acc + +// func Sum64(b []byte) uint64 +TEXT ·Sum64(SB), NOSPLIT, $0-32 + // Load fixed primes. + MOVQ ·prime1v(SB), R13 + MOVQ ·prime2v(SB), R14 + MOVQ ·prime4v(SB), DI + + // Load slice. + MOVQ b_base+0(FP), SI + MOVQ b_len+8(FP), DX + LEAQ (SI)(DX*1), BX + + // The first loop limit will be len(b)-32. + SUBQ $32, BX + + // Check whether we have at least one block. + CMPQ DX, $32 + JLT noBlocks + + // Set up initial state (v1, v2, v3, v4). + MOVQ R13, R8 + ADDQ R14, R8 + MOVQ R14, R9 + XORQ R10, R10 + XORQ R11, R11 + SUBQ R13, R11 + + // Loop until SI > BX. +blockLoop: + round(R8) + round(R9) + round(R10) + round(R11) + + CMPQ SI, BX + JLE blockLoop + + MOVQ R8, AX + ROLQ $1, AX + MOVQ R9, R12 + ROLQ $7, R12 + ADDQ R12, AX + MOVQ R10, R12 + ROLQ $12, R12 + ADDQ R12, AX + MOVQ R11, R12 + ROLQ $18, R12 + ADDQ R12, AX + + mergeRound(AX, R8) + mergeRound(AX, R9) + mergeRound(AX, R10) + mergeRound(AX, R11) + + JMP afterBlocks + +noBlocks: + MOVQ ·prime5v(SB), AX + +afterBlocks: + ADDQ DX, AX + + // Right now BX has len(b)-32, and we want to loop until SI > len(b)-8. + ADDQ $24, BX + + CMPQ SI, BX + JG fourByte + +wordLoop: + // Calculate k1. + MOVQ (SI), R8 + ADDQ $8, SI + IMULQ R14, R8 + ROLQ $31, R8 + IMULQ R13, R8 + + XORQ R8, AX + ROLQ $27, AX + IMULQ R13, AX + ADDQ DI, AX + + CMPQ SI, BX + JLE wordLoop + +fourByte: + ADDQ $4, BX + CMPQ SI, BX + JG singles + + MOVL (SI), R8 + ADDQ $4, SI + IMULQ R13, R8 + XORQ R8, AX + + ROLQ $23, AX + IMULQ R14, AX + ADDQ ·prime3v(SB), AX + +singles: + ADDQ $4, BX + CMPQ SI, BX + JGE finalize + +singlesLoop: + MOVBQZX (SI), R12 + ADDQ $1, SI + IMULQ ·prime5v(SB), R12 + XORQ R12, AX + + ROLQ $11, AX + IMULQ R13, AX + + CMPQ SI, BX + JL singlesLoop + +finalize: + MOVQ AX, R12 + SHRQ $33, R12 + XORQ R12, AX + IMULQ R14, AX + MOVQ AX, R12 + SHRQ $29, R12 + XORQ R12, AX + IMULQ ·prime3v(SB), AX + MOVQ AX, R12 + SHRQ $32, R12 + XORQ R12, AX + + MOVQ AX, ret+24(FP) + RET + +// writeBlocks uses the same registers as above except that it uses AX to store +// the d pointer. + +// func writeBlocks(d *Digest, b []byte) int +TEXT ·writeBlocks(SB), NOSPLIT, $0-40 + // Load fixed primes needed for round. + MOVQ ·prime1v(SB), R13 + MOVQ ·prime2v(SB), R14 + + // Load slice. + MOVQ b_base+8(FP), SI + MOVQ b_len+16(FP), DX + LEAQ (SI)(DX*1), BX + SUBQ $32, BX + + // Load vN from d. + MOVQ d+0(FP), AX + MOVQ 0(AX), R8 // v1 + MOVQ 8(AX), R9 // v2 + MOVQ 16(AX), R10 // v3 + MOVQ 24(AX), R11 // v4 + + // We don't need to check the loop condition here; this function is + // always called with at least one block of data to process. +blockLoop: + round(R8) + round(R9) + round(R10) + round(R11) + + CMPQ SI, BX + JLE blockLoop + + // Copy vN back to d. + MOVQ R8, 0(AX) + MOVQ R9, 8(AX) + MOVQ R10, 16(AX) + MOVQ R11, 24(AX) + + // The number of bytes written is SI minus the old base pointer. + SUBQ b_base+8(FP), SI + MOVQ SI, ret+32(FP) + + RET diff --git a/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash_other.go b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash_other.go new file mode 100644 index 0000000..4a5a821 --- /dev/null +++ b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash_other.go @@ -0,0 +1,76 @@ +// +build !amd64 appengine !gc purego + +package xxhash + +// Sum64 computes the 64-bit xxHash digest of b. +func Sum64(b []byte) uint64 { + // A simpler version would be + // d := New() + // d.Write(b) + // return d.Sum64() + // but this is faster, particularly for small inputs. + + n := len(b) + var h uint64 + + if n >= 32 { + v1 := prime1v + prime2 + v2 := prime2 + v3 := uint64(0) + v4 := -prime1v + for len(b) >= 32 { + v1 = round(v1, u64(b[0:8:len(b)])) + v2 = round(v2, u64(b[8:16:len(b)])) + v3 = round(v3, u64(b[16:24:len(b)])) + v4 = round(v4, u64(b[24:32:len(b)])) + b = b[32:len(b):len(b)] + } + h = rol1(v1) + rol7(v2) + rol12(v3) + rol18(v4) + h = mergeRound(h, v1) + h = mergeRound(h, v2) + h = mergeRound(h, v3) + h = mergeRound(h, v4) + } else { + h = prime5 + } + + h += uint64(n) + + i, end := 0, len(b) + for ; i+8 <= end; i += 8 { + k1 := round(0, u64(b[i:i+8:len(b)])) + h ^= k1 + h = rol27(h)*prime1 + prime4 + } + if i+4 <= end { + h ^= uint64(u32(b[i:i+4:len(b)])) * prime1 + h = rol23(h)*prime2 + prime3 + i += 4 + } + for ; i < end; i++ { + h ^= uint64(b[i]) * prime5 + h = rol11(h) * prime1 + } + + h ^= h >> 33 + h *= prime2 + h ^= h >> 29 + h *= prime3 + h ^= h >> 32 + + return h +} + +func writeBlocks(d *Digest, b []byte) int { + v1, v2, v3, v4 := d.v1, d.v2, d.v3, d.v4 + n := len(b) + for len(b) >= 32 { + v1 = round(v1, u64(b[0:8:len(b)])) + v2 = round(v2, u64(b[8:16:len(b)])) + v3 = round(v3, u64(b[16:24:len(b)])) + v4 = round(v4, u64(b[24:32:len(b)])) + b = b[32:len(b):len(b)] + } + d.v1, d.v2, d.v3, d.v4 = v1, v2, v3, v4 + return n - len(b) +} diff --git a/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash_safe.go b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash_safe.go new file mode 100644 index 0000000..fc9bea7 --- /dev/null +++ b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash_safe.go @@ -0,0 +1,15 @@ +// +build appengine + +// This file contains the safe implementations of otherwise unsafe-using code. + +package xxhash + +// Sum64String computes the 64-bit xxHash digest of s. +func Sum64String(s string) uint64 { + return Sum64([]byte(s)) +} + +// WriteString adds more data to d. It always returns len(s), nil. +func (d *Digest) WriteString(s string) (n int, err error) { + return d.Write([]byte(s)) +} diff --git a/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash_test.go b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash_test.go new file mode 100644 index 0000000..6330f19 --- /dev/null +++ b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash_test.go @@ -0,0 +1,166 @@ +package xxhash + +import ( + "bytes" + "encoding/binary" + "fmt" + "strings" + "testing" +) + +func TestAll(t *testing.T) { + for _, tt := range []struct { + name string + input string + want uint64 + }{ + {"empty", "", 0xef46db3751d8e999}, + {"a", "a", 0xd24ec4f1a98c6e5b}, + {"as", "as", 0x1c330fb2d66be179}, + {"asd", "asd", 0x631c37ce72a97393}, + {"asdf", "asdf", 0x415872f599cea71e}, + { + "len=63", + // Exactly 63 characters, which exercises all code paths. + "Call me Ishmael. Some years ago--never mind how long precisely-", + 0x02a2e85470d6fd96, + }, + } { + lastChunkSize := len(tt.input) + if lastChunkSize == 0 { + lastChunkSize = 1 + } + for chunkSize := 1; chunkSize <= lastChunkSize; chunkSize++ { + name := fmt.Sprintf("%s,chunkSize=%d", tt.name, chunkSize) + t.Run(name, func(t *testing.T) { + testDigest(t, tt.input, chunkSize, tt.want) + }) + } + t.Run(tt.name, func(t *testing.T) { testSum(t, tt.input, tt.want) }) + } +} + +func testDigest(t *testing.T, input string, chunkSize int, want uint64) { + d := New() + ds := New() // uses WriteString + for i := 0; i < len(input); i += chunkSize { + chunk := input[i:] + if len(chunk) > chunkSize { + chunk = chunk[:chunkSize] + } + n, err := d.Write([]byte(chunk)) + if err != nil || n != len(chunk) { + t.Fatalf("Digest.Write: got (%d, %v); want (%d, nil)", n, err, len(chunk)) + } + n, err = ds.WriteString(chunk) + if err != nil || n != len(chunk) { + t.Fatalf("Digest.WriteString: got (%d, %v); want (%d, nil)", n, err, len(chunk)) + } + } + if got := d.Sum64(); got != want { + t.Fatalf("Digest.Sum64: got 0x%x; want 0x%x", got, want) + } + if got := ds.Sum64(); got != want { + t.Fatalf("Digest.Sum64 (WriteString): got 0x%x; want 0x%x", got, want) + } + var b [8]byte + binary.BigEndian.PutUint64(b[:], want) + if got := d.Sum(nil); !bytes.Equal(got, b[:]) { + t.Fatalf("Sum: got %v; want %v", got, b[:]) + } +} + +func testSum(t *testing.T, input string, want uint64) { + if got := Sum64([]byte(input)); got != want { + t.Fatalf("Sum64: got 0x%x; want 0x%x", got, want) + } + if got := Sum64String(input); got != want { + t.Fatalf("Sum64String: got 0x%x; want 0x%x", got, want) + } +} + +func TestReset(t *testing.T) { + parts := []string{"The quic", "k br", "o", "wn fox jumps", " ov", "er the lazy ", "dog."} + d := New() + for _, part := range parts { + d.Write([]byte(part)) + } + h0 := d.Sum64() + + d.Reset() + d.Write([]byte(strings.Join(parts, ""))) + h1 := d.Sum64() + + if h0 != h1 { + t.Errorf("0x%x != 0x%x", h0, h1) + } +} + +func TestBinaryMarshaling(t *testing.T) { + d := New() + d.WriteString("abc") + b, err := d.MarshalBinary() + if err != nil { + t.Fatal(err) + } + d = New() + d.WriteString("junk") + if err := d.UnmarshalBinary(b); err != nil { + t.Fatal(err) + } + d.WriteString("def") + if got, want := d.Sum64(), Sum64String("abcdef"); got != want { + t.Fatalf("after MarshalBinary+UnmarshalBinary, got 0x%x; want 0x%x", got, want) + } + + d0 := New() + d1 := New() + for i := 0; i < 64; i++ { + b, err := d0.MarshalBinary() + if err != nil { + t.Fatal(err) + } + d0 = new(Digest) + if err := d0.UnmarshalBinary(b); err != nil { + t.Fatal(err) + } + if got, want := d0.Sum64(), d1.Sum64(); got != want { + t.Fatalf("after %d Writes, unmarshaled Digest gave sum 0x%x; want 0x%x", i, got, want) + } + + d0.Write([]byte{'a'}) + d1.Write([]byte{'a'}) + } +} + +var sink uint64 + +func TestAllocs(t *testing.T) { + const shortStr = "abcdefghijklmnop" + // Sum64([]byte(shortString)) shouldn't allocate because the + // intermediate []byte ought not to escape. + // (See https://github.com/cespare/xxhash/pull/2.) + t.Run("Sum64", func(t *testing.T) { + testAllocs(t, func() { + sink = Sum64([]byte(shortStr)) + }) + }) + // Creating and using a Digest shouldn't allocate because its methods + // shouldn't make it escape. (A previous version of New returned a + // hash.Hash64 which forces an allocation.) + t.Run("Digest", func(t *testing.T) { + b := []byte("asdf") + testAllocs(t, func() { + d := New() + d.Write(b) + sink = d.Sum64() + }) + }) +} + +func testAllocs(t *testing.T, fn func()) { + t.Helper() + if allocs := int(testing.AllocsPerRun(10, fn)); allocs > 0 { + t.Fatalf("got %d allocation(s) (want zero)", allocs) + } +} diff --git a/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash_unsafe.go b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash_unsafe.go new file mode 100644 index 0000000..376e0ca --- /dev/null +++ b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash_unsafe.go @@ -0,0 +1,57 @@ +// +build !appengine + +// This file encapsulates usage of unsafe. +// xxhash_safe.go contains the safe implementations. + +package xxhash + +import ( + "unsafe" +) + +// In the future it's possible that compiler optimizations will make these +// XxxString functions unnecessary by realizing that calls such as +// Sum64([]byte(s)) don't need to copy s. See https://golang.org/issue/2205. +// If that happens, even if we keep these functions they can be replaced with +// the trivial safe code. + +// NOTE: The usual way of doing an unsafe string-to-[]byte conversion is: +// +// var b []byte +// bh := (*reflect.SliceHeader)(unsafe.Pointer(&b)) +// bh.Data = (*reflect.StringHeader)(unsafe.Pointer(&s)).Data +// bh.Len = len(s) +// bh.Cap = len(s) +// +// Unfortunately, as of Go 1.15.3 the inliner's cost model assigns a high enough +// weight to this sequence of expressions that any function that uses it will +// not be inlined. Instead, the functions below use a different unsafe +// conversion designed to minimize the inliner weight and allow both to be +// inlined. There is also a test (TestInlining) which verifies that these are +// inlined. +// +// See https://github.com/golang/go/issues/42739 for discussion. + +// Sum64String computes the 64-bit xxHash digest of s. +// It may be faster than Sum64([]byte(s)) by avoiding a copy. +func Sum64String(s string) uint64 { + b := *(*[]byte)(unsafe.Pointer(&sliceHeader{s, len(s)})) + return Sum64(b) +} + +// WriteString adds more data to d. It always returns len(s), nil. +// It may be faster than Write([]byte(s)) by avoiding a copy. +func (d *Digest) WriteString(s string) (n int, err error) { + d.Write(*(*[]byte)(unsafe.Pointer(&sliceHeader{s, len(s)}))) + // d.Write always returns len(s), nil. + // Ignoring the return output and returning these fixed values buys a + // savings of 6 in the inliner's cost model. + return len(s), nil +} + +// sliceHeader is similar to reflect.SliceHeader, but it assumes that the layout +// of the first two words is the same as the layout of a string. +type sliceHeader struct { + s string + cap int +} diff --git a/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash_unsafe_test.go b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash_unsafe_test.go new file mode 100644 index 0000000..6598267 --- /dev/null +++ b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhash_unsafe_test.go @@ -0,0 +1,61 @@ +// +build !appengine + +package xxhash + +import ( + "os/exec" + "sort" + "strings" + "testing" +) + +func TestStringAllocs(t *testing.T) { + longStr := strings.Repeat("a", 1000) + t.Run("Sum64String", func(t *testing.T) { + testAllocs(t, func() { + sink = Sum64String(longStr) + }) + }) + t.Run("Digest.WriteString", func(t *testing.T) { + testAllocs(t, func() { + d := New() + d.WriteString(longStr) + sink = d.Sum64() + }) + }) +} + +// This test is inspired by the Go runtime tests in https://golang.org/cl/57410. +// It asserts that certain important functions may be inlined. +func TestInlining(t *testing.T) { + funcs := map[string]struct{}{ + "Sum64String": {}, + "(*Digest).WriteString": {}, + } + + // TODO: it would be better to use the go binary that is running + // 'go test' (if we are running under 'go test'). + cmd := exec.Command("go", "test", "-gcflags=-m", "-run", "xxxx") + out, err := cmd.CombinedOutput() + if err != nil { + t.Log(string(out)) + t.Fatal(err) + } + + for _, line := range strings.Split(string(out), "\n") { + parts := strings.Split(line, ": can inline") + if len(parts) < 2 { + continue + } + delete(funcs, strings.TrimSpace(parts[1])) + } + + var failed []string + for fn := range funcs { + failed = append(failed, fn) + } + sort.Strings(failed) + for _, fn := range failed { + t.Errorf("function %s not inlined", fn) + } +} diff --git a/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhsum/.gitignore b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhsum/.gitignore new file mode 100644 index 0000000..2c88f1d --- /dev/null +++ b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhsum/.gitignore @@ -0,0 +1 @@ +/xxhsum diff --git a/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhsum/xxhsum.go b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhsum/xxhsum.go new file mode 100644 index 0000000..9b1d035 --- /dev/null +++ b/dependencies/pkg/mod/github.com/cespare/xxhash/v2@v2.1.2/xxhsum/xxhsum.go @@ -0,0 +1,50 @@ +package main + +import ( + "fmt" + "io" + "os" + + "github.com/cespare/xxhash/v2" +) + +func main() { + if contains(os.Args[1:], "-h") { + fmt.Fprintf(os.Stderr, `Usage: + %s [filenames] +If no filenames are provided or only - is given, input is read from stdin. +`, os.Args[0]) + os.Exit(1) + } + if len(os.Args) < 2 || len(os.Args) == 2 && os.Args[1] == "-" { + printHash(os.Stdin, "-") + return + } + for _, path := range os.Args[1:] { + f, err := os.Open(path) + if err != nil { + fmt.Fprintln(os.Stderr, err) + continue + } + printHash(f, path) + f.Close() + } +} + +func contains(ss []string, s string) bool { + for _, s1 := range ss { + if s1 == s { + return true + } + } + return false +} + +func printHash(r io.Reader, name string) { + h := xxhash.New() + if _, err := io.Copy(h, r); err != nil { + fmt.Fprintln(os.Stderr, err) + return + } + fmt.Printf("%016x %s\n", h.Sum64(), name) +} |