internal/format/packidx/bloom: Add

1 files changed, 80 insertions, 0 deletions

diff --git a/internal/format/packidx/bloom/roundtrip_test.go b/internal/format/packidx/bloom/roundtrip_test.go
new file mode 100644
index 00000000..990c83e0
--- /dev/null
+++ b/internal/format/packidx/bloom/roundtrip_test.go
@@ -0,0 +1,80 @@
+package bloom_test
+
+import (
+	"encoding/binary"
+	"testing"
+
+	"lindenii.org/go/furgit/internal/format/packidx/bloom"
+	"lindenii.org/go/furgit/object/id"
+)
+
+func makeOID(size int, seed uint64) []byte {
+	out := make([]byte, size)
+	state := seed
+
+	for i := 0; i < size; i += 8 {
+		state = state*6364136223846793005 + 1442695040888963407
+
+		var word [8]byte
+
+		binary.BigEndian.PutUint64(word[:], state)
+		copy(out[i:], word[:])
+	}
+
+	return out
+}
+
+func TestRoundTrip(t *testing.T) {
+	t.Parallel()
+
+	for _, format := range id.SupportedObjectFormats() {
+		t.Run(format.String(), func(t *testing.T) {
+			t.Parallel()
+
+			const objects = 10000
+
+			bucketCount, k, err := bloom.RecommendParams(format, objects)
+			if err != nil {
+				t.Fatal(err)
+			}
+
+			builder, err := bloom.NewBuilder(format, bucketCount, k)
+			if err != nil {
+				t.Fatal(err)
+			}
+
+			size := format.Size()
+			for i := range objects {
+				builder.Add(makeOID(size, uint64(i)))
+			}
+
+			filter, err := bloom.Parse(builder.Bytes(), format)
+			if err != nil {
+				t.Fatal(err)
+			}
+
+			for i := range objects {
+				if !filter.MayContain(makeOID(size, uint64(i))) {
+					t.Fatalf("false negative for added object %d", i)
+				}
+			}
+
+			const probes = 10000
+
+			falsePositives := 0
+
+			for i := range probes {
+				if filter.MayContain(makeOID(size, uint64(1)<<40+uint64(i))) {
+					falsePositives++
+				}
+			}
+
+			rate := float64(falsePositives) / float64(probes)
+			if rate > 0.05 {
+				t.Errorf("false positive rate %.4f exceeds 0.05", rate)
+			}
+
+			t.Logf("B=%d K=%d false positive rate %.4f", bucketCount, k, rate)
+		})
+	}
+}