104 lines
2.1 KiB
Go
104 lines
2.1 KiB
Go
package hash_test
|
|
|
|
import (
|
|
"bytes"
|
|
"math"
|
|
"testing"
|
|
|
|
"git.akyoto.dev/go/hash"
|
|
)
|
|
|
|
// Hashes generated in tests will be saved to check for collisions.
|
|
var hashes = map[uint64][]byte{}
|
|
|
|
// addHash adds a new hash and checks for collisions.
|
|
func addHash(t *testing.T, sum uint64, data []byte) {
|
|
saved, found := hashes[sum]
|
|
|
|
if found && !bytes.Equal(saved, data) {
|
|
t.Fatalf("collision between %v and %v:\nhash %064b", saved, data, sum)
|
|
}
|
|
|
|
save := make([]byte, len(data))
|
|
copy(save, data)
|
|
hashes[sum] = save
|
|
}
|
|
|
|
// TestTiny hashes every single permutation that is 1-32 bytes long.
|
|
func TestTiny(t *testing.T) {
|
|
for size := 1; size <= 32; size++ {
|
|
data := make([]byte, size)
|
|
|
|
for i := 0; i <= 255*size; i++ {
|
|
sum := hash.Bytes(data)
|
|
addHash(t, sum, data)
|
|
data[i%size] += 1
|
|
}
|
|
}
|
|
}
|
|
|
|
// TestZeroed hashes completely zeroed buffers that are 1-8192 bytes long.
|
|
func TestZeroed(t *testing.T) {
|
|
zero := make([]byte, 8192)
|
|
|
|
for size := 1; size <= len(zero); size++ {
|
|
data := zero[:size]
|
|
sum := hash.Bytes(data)
|
|
addHash(t, sum, data)
|
|
}
|
|
}
|
|
|
|
// TestSameByte hashes every byte repetition that is 1-512 bytes long.
|
|
func TestSameByte(t *testing.T) {
|
|
for b := 1; b < 256; b++ {
|
|
for size := 1; size <= 512; size++ {
|
|
data := bytes.Repeat([]byte{byte(b)}, size)
|
|
sum := hash.Bytes(data)
|
|
addHash(t, sum, data)
|
|
}
|
|
}
|
|
}
|
|
|
|
func TestDistribution(t *testing.T) {
|
|
const (
|
|
maxSingleDiff = 0.03
|
|
maxAverageDiff = 0.01
|
|
)
|
|
|
|
totalDiff := 0.0
|
|
on := [64]int{}
|
|
off := [64]int{}
|
|
|
|
for sum := range hashes {
|
|
for bit := 0; bit < 64; bit++ {
|
|
if (sum & (1 << bit)) != 0 {
|
|
on[bit]++
|
|
} else {
|
|
off[bit]++
|
|
}
|
|
}
|
|
}
|
|
|
|
for bit := 0; bit < 64; bit++ {
|
|
total := on[bit] + off[bit]
|
|
|
|
if total == 0 {
|
|
continue
|
|
}
|
|
|
|
probability := float64(on[bit]) / float64(total)
|
|
diff := probability - 0.5
|
|
totalDiff += math.Abs(diff)
|
|
|
|
if math.Abs(diff) > maxSingleDiff {
|
|
t.Logf("Bit %d: %.1f%% (should be closer to 50%%)", bit+1, probability*100)
|
|
}
|
|
}
|
|
|
|
averageDiff := totalDiff / 64
|
|
|
|
if averageDiff > maxAverageDiff {
|
|
t.Fatalf("Average difference too high (> %.2f): %f", maxAverageDiff, averageDiff)
|
|
}
|
|
}
|