18 files changed, 1089 insertions, 69 deletions

diff --git a/internal/adler32/adler32_generic.go b/internal/adler32/adler32_generic.go
index 08ab483f..f6d53f5c 100644
--- a/internal/adler32/adler32_generic.go
+++ b/internal/adler32/adler32_generic.go
@@ -5,19 +5,19 @@ const (
 	Size = 4
 
 	// mod is the largest prime that is less than 65536.
-	mod = 65521
+	mod = 65521 //nolint:unused
 	// nmax is the largest n such that
 	// 255 * n * (n+1) / 2 + (n+1) * (mod-1) <= 2^32-1.
 	// It is mentioned in RFC 1950 (search for "5552").
-	nmax = 5552
+	nmax = 5552 //nolint:unused
 
 	// binary representation compatible with standard library.
-	magic         = "adl\x01"
-	marshaledSize = len(magic) + 4
+	magic         = "adl\x01"      //nolint:unused
+	marshaledSize = len(magic) + 4 //nolint:unused
 )
 
 // Add p to the running checksum d.
-func update(d uint32, p []byte) uint32 {
+func update(d uint32, p []byte) uint32 { //nolint:unused
 	s1, s2 := d&0xffff, d>>16
 
 	for len(p) > 0 {
diff --git a/internal/cache/clock/clock_ops.go b/internal/cache/clock/clock_ops.go
index a21f44c3..6d4785f4 100644
--- a/internal/cache/clock/clock_ops.go
+++ b/internal/cache/clock/clock_ops.go
@@ -10,15 +10,11 @@ func (clock *Clock[K, V]) Add(key K, value V) bool {
 }
 
 // Get returns the value for key and marks it recently used.
-//
-//nolint:ireturn
 func (clock *Clock[K, V]) Get(key K) (V, bool) {
 	return clock.shardFor(key).get(key)
 }
 
 // Peek returns the value for key without changing its recency.
-//
-//nolint:ireturn
 func (clock *Clock[K, V]) Peek(key K) (V, bool) {
 	return clock.shardFor(key).peek(key)
 }
diff --git a/internal/cache/clock/shard_read.go b/internal/cache/clock/shard_read.go
index 624e3409..279f9725 100644
--- a/internal/cache/clock/shard_read.go
+++ b/internal/cache/clock/shard_read.go
@@ -1,8 +1,6 @@
 package clock
 
 // get returns the value for key and marks it referenced.
-//
-//nolint:ireturn
 func (shard *shard[K, V]) get(key K) (V, bool) {
 	e, ok := shard.items.Load(key)
 	if !ok {
@@ -19,8 +17,6 @@ func (shard *shard[K, V]) get(key K) (V, bool) {
 }
 
 // peek returns the value for key without affecting eviction.
-//
-//nolint:ireturn
 func (shard *shard[K, V]) peek(key K) (V, bool) {
 	e, ok := shard.items.Load(key)
 	if !ok {
diff --git a/internal/format/packfile/delta/apply.go b/internal/format/packfile/delta/apply.go
index 4210d1b3..656a69d0 100644
--- a/internal/format/packfile/delta/apply.go
+++ b/internal/format/packfile/delta/apply.go
@@ -106,7 +106,7 @@ func parseCopyOperand(delta []byte, pos *int, op byte, firstBit uint, count int)
 	value := 0
 
 	for i := range count {
-		if op&(1<<(firstBit+uint(i))) == 0 {
+		if op&(1<<(firstBit+uint(i))) == 0 { //nolint:gosec
 			continue
 		}
 
diff --git a/internal/format/packidx/bloom/bloom.go b/internal/format/packidx/bloom/bloom.go
new file mode 100644
index 00000000..b3fc2f7c
--- /dev/null
+++ b/internal/format/packidx/bloom/bloom.go
@@ -0,0 +1,180 @@
+package bloom
+
+import (
+	"bytes"
+	"encoding/binary"
+	"errors"
+	"fmt"
+	"math/bits"
+
+	"lindenii.org/go/furgit/object/id"
+)
+
+// ErrMalformedBloomFilter reports that
+// a Bloom filter is truncated,
+// has a bad signature, version, or hash function,
+// or has inconsistent parameters.
+var ErrMalformedBloomFilter = errors.New("internal/format/packidx/bloom: malformed bloom filter")
+
+const (
+	signature = 0x4944424c // "IDBL"
+	version   = 1
+
+	// HeaderLen is the fixed header length in octets,
+	// i.e., the signature, version, hash function identifier,
+	// B, K, and the trailing zero padding.
+	HeaderLen = 64
+
+	// BucketLen is the length of one bucket in octets,
+	// chosen to match the most common cache-line size.
+	BucketLen = 64
+
+	// wordBits is the bit width of one bucket word.
+	wordBits = 64
+
+	// fieldBits is the width of one in-bucket position field.
+	fieldBits = 9
+)
+
+// checkParams validates the filter parameters
+// against one object hash size,
+// returning log2(bucketCount) on success.
+func checkParams(bucketCount uint32, k uint16, hashSize int) (uint, error) {
+	switch {
+	case bucketCount == 0 || bucketCount&(bucketCount-1) != 0:
+		return 0, errors.New("bucket count not a nonzero power of two") //nolint:err113
+	case k == 0:
+		return 0, errors.New("zero probe count") //nolint:err113
+	}
+
+	log2B := uint(bits.TrailingZeros32(bucketCount)) //nolint:gosec
+	if log2B+fieldBits*uint(k) > uint(hashSize)*8 {  //nolint:gosec
+		return 0, errors.New("parameters exceed hash length") //nolint:err113
+	}
+
+	return log2B, nil
+}
+
+// hashFunctionID returns the on-disk hash function identifier
+// for one object format.
+func hashFunctionID(objectFormat id.ObjectFormat) (uint32, error) {
+	switch objectFormat {
+	case id.ObjectFormatSHA1:
+		return 1, nil
+	case id.ObjectFormatSHA256:
+		return 2, nil
+	case id.ObjectFormatUnknown:
+	}
+
+	return 0, id.ErrInvalidObjectFormat
+}
+
+// Bloom is a parsed blocked Bloom filter view over borrowed bytes.
+//
+// Labels: Deps-Borrowed, Life-Parent, MT-Safe.
+type Bloom struct {
+	// data is the entire filter payload.
+	data []byte
+
+	// buckets is the bucket region, between the header and the trailer.
+	buckets []byte
+
+	// objectFormat is the filter's object format.
+	objectFormat id.ObjectFormat
+
+	// log2B is the base-2 logarithm of the bucket count,
+	// i.e. the number of leading object ID bits that select a bucket.
+	log2B uint
+
+	// k is the number of bits set and tested per object ID.
+	k int
+}
+
+// Parse parses one Bloom filter from data.
+//
+// Labels: Deps-Borrowed, Life-Parent.
+func Parse(data []byte, objectFormat id.ObjectFormat) (Bloom, error) {
+	var zero Bloom
+
+	wantHashID, err := hashFunctionID(objectFormat)
+	if err != nil {
+		return zero, err
+	}
+
+	hashSize := objectFormat.Size()
+
+	if len(data) < HeaderLen {
+		return zero, fmt.Errorf("%w: truncated", ErrMalformedBloomFilter)
+	}
+
+	if binary.BigEndian.Uint32(data) != signature {
+		return zero, fmt.Errorf("%w: bad signature", ErrMalformedBloomFilter)
+	}
+
+	if binary.BigEndian.Uint32(data[4:]) != version {
+		return zero, fmt.Errorf("%w: unsupported version", ErrMalformedBloomFilter)
+	}
+
+	if binary.BigEndian.Uint32(data[8:]) != wantHashID {
+		return zero, fmt.Errorf("%w: hash function mismatch", ErrMalformedBloomFilter)
+	}
+
+	bucketCount := binary.BigEndian.Uint32(data[12:])
+	k := binary.BigEndian.Uint16(data[16:])
+
+	for _, octet := range data[18:HeaderLen] {
+		if octet != 0 {
+			return zero, fmt.Errorf("%w: nonzero padding", ErrMalformedBloomFilter)
+		}
+	}
+
+	log2B, err := checkParams(bucketCount, k, hashSize)
+	if err != nil {
+		return zero, fmt.Errorf("%w: %w", ErrMalformedBloomFilter, err)
+	}
+
+	want := uint64(HeaderLen) + uint64(BucketLen)*uint64(bucketCount) + 2*uint64(hashSize) //#nosec G115
+	if uint64(len(data)) != want {
+		return zero, fmt.Errorf("%w: file size disagrees with bucket count", ErrMalformedBloomFilter)
+	}
+
+	return Bloom{
+		data:         data,
+		buckets:      data[HeaderLen : len(data)-2*hashSize],
+		objectFormat: objectFormat,
+		log2B:        log2B,
+		k:            int(k),
+	}, nil
+}
+
+// PackHash returns the pack hash recorded in the filter trailer.
+//
+// Labels: Life-Parent, Mut-No.
+func (f *Bloom) PackHash() []byte {
+	hashSize := f.objectFormat.Size()
+	end := len(f.data) - hashSize
+
+	return f.data[end-hashSize : end]
+}
+
+// Verify recomputes the filter's trailing checksum and reports any mismatch.
+//
+// Verify reads the whole filter,
+// so callers should treat it as a deliberate integrity check
+// rather than part of the open path.
+func (f *Bloom) Verify() error {
+	hashImpl, err := f.objectFormat.New()
+	if err != nil {
+		return fmt.Errorf("internal/format/packidx/bloom: %w", err)
+	}
+
+	checksumOff := len(f.data) - f.objectFormat.Size()
+
+	_, _ = hashImpl.Write(f.data[:checksumOff])
+
+	if !bytes.Equal(hashImpl.Sum(nil), f.data[checksumOff:]) {
+		return fmt.Errorf("%w: checksum mismatch", ErrMalformedBloomFilter)
+	}
+
+	return nil
+}
diff --git a/internal/format/packidx/bloom/bloom_test.go b/internal/format/packidx/bloom/bloom_test.go
new file mode 100644
index 00000000..bcfb4419
--- /dev/null
+++ b/internal/format/packidx/bloom/bloom_test.go
@@ -0,0 +1,159 @@
+package bloom_test
+
+import (
+	"encoding/binary"
+	"errors"
+	"testing"
+
+	"lindenii.org/go/furgit/internal/format/packidx/bloom"
+	"lindenii.org/go/furgit/object/id"
+)
+
+func validFilter(t *testing.T, format id.ObjectFormat) []byte {
+	// TODO: maybe testgit should have something like this?
+	t.Helper()
+
+	builder, err := bloom.NewBuilder(format, 4, 2, make([]byte, format.Size()))
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	return builder.Bytes()
+}
+
+func otherFormat(t *testing.T, format id.ObjectFormat) id.ObjectFormat {
+	t.Helper()
+
+	for _, candidate := range id.SupportedObjectFormats() {
+		if candidate != format {
+			return candidate
+		}
+	}
+
+	t.Skip("only one supported object format")
+
+	return id.ObjectFormatUnknown
+}
+
+func TestParseValid(t *testing.T) {
+	t.Parallel()
+
+	for _, format := range id.SupportedObjectFormats() {
+		t.Run(format.String(), func(t *testing.T) {
+			t.Parallel()
+
+			_, err := bloom.Parse(validFilter(t, format), format)
+			if err != nil {
+				t.Fatalf("Parse rejected a valid filter: %v", err)
+			}
+		})
+	}
+}
+
+func TestParseMalformed(t *testing.T) {
+	t.Parallel()
+
+	cases := []struct {
+		name   string
+		mangle func(data []byte) []byte
+	}{
+		{"truncated", func(data []byte) []byte { return data[:bloom.HeaderLen-1] }},
+		{"bad signature", func(data []byte) []byte {
+			data[0] ^= 0xff
+
+			return data
+		}},
+		{"bad version", func(data []byte) []byte {
+			binary.BigEndian.PutUint32(data[4:], 99)
+
+			return data
+		}},
+		{"non power of two", func(data []byte) []byte {
+			binary.BigEndian.PutUint32(data[12:], 3)
+
+			return data
+		}},
+		{"zero probe count", func(data []byte) []byte {
+			binary.BigEndian.PutUint16(data[16:], 0)
+
+			return data
+		}},
+		{"parameters exceed hash", func(data []byte) []byte {
+			binary.BigEndian.PutUint32(data[12:], 1<<31)
+			binary.BigEndian.PutUint16(data[16:], 30)
+
+			return data
+		}},
+		{"nonzero padding", func(data []byte) []byte {
+			data[20] = 1
+
+			return data
+		}},
+		{"size disagrees", func(data []byte) []byte { return data[:len(data)-1] }},
+	}
+
+	for _, format := range id.SupportedObjectFormats() {
+		t.Run(format.String(), func(t *testing.T) {
+			t.Parallel()
+
+			for _, tc := range cases {
+				t.Run(tc.name, func(t *testing.T) {
+					t.Parallel()
+
+					data := tc.mangle(append([]byte(nil), validFilter(t, format)...))
+
+					_, err := bloom.Parse(data, format)
+					if !errors.Is(err, bloom.ErrMalformedBloomFilter) {
+						t.Fatalf("Parse error = %v, want ErrMalformedBloomFilter", err)
+					}
+				})
+			}
+		})
+	}
+}
+
+// TestVerifyDetectsCorruption checks that Verify accepts a sound filter
+// and rejects one whose bucket bytes have been altered.
+func TestVerifyDetectsCorruption(t *testing.T) {
+	t.Parallel()
+
+	for _, format := range id.SupportedObjectFormats() {
+		t.Run(format.String(), func(t *testing.T) {
+			t.Parallel()
+
+			data := validFilter(t, format)
+
+			filter, err := bloom.Parse(data, format)
+			if err != nil {
+				t.Fatal(err)
+			}
+
+			err = filter.Verify()
+			if err != nil {
+				t.Fatalf("Verify on a sound filter: %v", err)
+			}
+
+			data[bloom.HeaderLen] ^= 0xff
+
+			err = filter.Verify()
+			if !errors.Is(err, bloom.ErrMalformedBloomFilter) {
+				t.Fatalf("Verify error = %v, want ErrMalformedBloomFilter", err)
+			}
+		})
+	}
+}
+
+func TestParseHashMismatch(t *testing.T) {
+	t.Parallel()
+
+	for _, format := range id.SupportedObjectFormats() {
+		t.Run(format.String(), func(t *testing.T) {
+			t.Parallel()
+
+			_, err := bloom.Parse(validFilter(t, format), otherFormat(t, format))
+			if !errors.Is(err, bloom.ErrMalformedBloomFilter) {
+				t.Fatalf("Parse error = %v, want ErrMalformedBloomFilter", err)
+			}
+		})
+	}
+}
diff --git a/internal/format/packidx/bloom/doc.go b/internal/format/packidx/bloom/doc.go
new file mode 100644
index 00000000..06ca57cd
--- /dev/null
+++ b/internal/format/packidx/bloom/doc.go
@@ -0,0 +1,138 @@
+// Package bloom provides a blocked Bloom filter
+// for pack indexes.
+//
+// A filter answers, from a single cache-line-sized read,
+// whether an object ID is definitely absent from the index it covers.
+// A lookup that must consult many packs
+// can then skip the full binary search
+// in every pack whose filter rejects the object,
+// decreasing the cost of misses.
+//
+// # Rationale
+//
+// Especially for server-side usage,
+// repacking is expensive,
+// and creating multi-pack-indexes is still rather expensive.
+// Incremental multi-pack-indexes partially solve this,
+// but having too many of them defeats the purpose,
+// since the indexes must still be walked in order
+// while performing expensive lookups.
+//
+// Instead, each multi-pack-index layer,
+// and each ordinary pack index,
+// may carry its own filter.
+// The indexes are still traversed in their usual order,
+// but the first step when traversing one
+// is to check whether it could possibly hold the wanted object.
+//
+// The filter is split into 64-octet buckets,
+// matching the most common cache-line size.
+// Some bits of the object ID choose the bucket,
+// and the rest choose several bit positions inside it,
+// so a lookup reads one 64-octet bucket
+// and checks whether all required bits are set.
+//
+// # Parameters
+//
+// A filter is parameterized by
+// the number of buckets B
+// and the number of bits set and tested per object ID, K.
+// All integers in the format are big endian.
+// The object ID is interpreted as a big-endian bitstring,
+// where bit offset 0 is the most significant bit of octet 0.
+// B must be a nonzero power of two,
+// K must be nonzero,
+// and log2(B) + 9*K must not exceed the hash length in bits.
+//
+// # File format
+//
+// A filter file is a 64-octet header,
+// then B buckets of 64 octets each,
+// then a two-hash trailer:
+//
+//   - 4-octet signature: {'I', 'D', 'B', 'L'}.
+//   - 4-octet version identifier (= 1).
+//   - 4-octet object hash algorithm identifier
+//     (= 1 for SHA-1, 2 for SHA-256).
+//   - 4-octet B, the number of buckets.
+//   - 2-octet K, the number of bits set and tested per object ID.
+//   - 46-octet padding, which must be all zero.
+//   - B buckets of 64 octets each.
+//   - the pack trailer hash, which binds the filter to its pack.
+//   - the checksum of everything before it, over the filter's hash function.
+//
+// The hash length is that of the object format,
+// so the trailer is 2 hashes wide
+// and the file size is exactly 64 + 64*B + 2*hashlen octets.
+//
+// A reader must validate that
+// the signature matches,
+// the version is supported,
+// the hash function identifier is recognized,
+// B is nonzero and a power of two,
+// K is nonzero,
+// log2(B) + 9*K does not exceed the hash length in bits,
+// the padding is all zero,
+// and the file size is exactly 64 + 64*B + 2*hashlen octets.
+//
+// # Binding and integrity
+//
+// The pack hash binds a filter to one pack;
+// a reader trusts a filter only when the recorded pack hash
+// matches the pack it accompanies.
+//
+// The checksum guards against corruption of the filter itself.
+// Recomputing it reads the whole file and rehashes it as fsck.
+//
+// # Lookup
+//
+// A lookup against one filter proceeds as follows:
+//
+//  1. Let b be the unsigned integer encoded
+//     by the most significant log2(B) bits of the object ID.
+//     B is a power of two, so 0 <= b < B.
+//  2. Select and read bucket b.
+//  3. For each 0 <= i < K,
+//     take the i-th 9-bit field
+//     from the 9*K bits that follow the bucket-selecting bits,
+//     and let pi be the unsigned integer it encodes,
+//     so 0 <= pi < 512.
+//     Compute wi = pi >> 6 and bi = pi & 63,
+//     so wi identifies one of the eight 64-bit words in bucket b
+//     and bi identifies one bit within that word.
+//     Within each 64-bit word,
+//     bit index 0 is the most significant bit
+//     and bit index 63 is the least significant bit.
+//     Test whether bit bi is set in word wi of bucket b.
+//
+// If any test fails,
+// the object ID is definitely not in the covered index.
+// If all tests succeed,
+// the object ID may be in it.
+// Two of the K 9-bit fields can decode to the same pi,
+// so an insertion may set fewer than K distinct bits;
+// this only raises the false positive rate
+// and never causes a false negative.
+//
+// # Worked example
+//
+// Let B = 1 << 15 = 32768 and K = 8.
+// Then log2(B) = 15,
+// so each lookup uses 15 bits to choose the bucket
+// and 8*9 = 72 bits to choose the in-bucket positions,
+// for a total of 87 bits taken from the object ID.
+// A SHA-1 has 160 bits and a SHA-256 has 256 bits,
+// so both leave ample headroom.
+//
+// # Security considerations
+//
+// Object IDs are public unkeyed hashes,
+// so an adversary can mine packs
+// whose object IDs share a chosen prefix
+// to crowd objects into one bucket
+// and fill its bits.
+// In the worst case this renders some buckets useless,
+// making the filter degrade to "may contain" for those buckets,
+// but it never produces a false negative
+// and is not a significant denial-of-service vector.
+package bloom
diff --git a/internal/format/packidx/bloom/lookup.go b/internal/format/packidx/bloom/lookup.go
new file mode 100644
index 00000000..4ca32913
--- /dev/null
+++ b/internal/format/packidx/bloom/lookup.go
@@ -0,0 +1,42 @@
+package bloom
+
+import (
+	"encoding/binary"
+)
+
+// MayContain reports whether oid may be present
+// in the index covered by the filter.
+//
+// oid must be exactly the filter's hash size;
+// MayContain panics otherwise.
+//
+// Labels: Mut-No.
+func (f *Bloom) MayContain(oid []byte) bool {
+	if len(oid) != f.objectFormat.Size() {
+		panic("internal/format/packidx/bloom: invalid object ID length")
+	}
+
+	base := int(binary.BigEndian.Uint32(oid[:4])>>(32-f.log2B)) * BucketLen
+
+	for i := range f.k {
+		word, mask := probe(oid, f.log2B, i)
+		if binary.BigEndian.Uint64(f.buckets[base+word*8:])&mask == 0 {
+			return false
+		}
+	}
+
+	return true
+}
+
+// probe returns the bucket word index and single-bit mask
+// addressed by the i-th probe of oid.
+func probe(oid []byte, log2B uint, i int) (word int, mask uint64) {
+	bitOff := log2B + fieldBits*uint(i) //#nosec G115
+	byteOff := bitOff >> 3
+	bitInByte := bitOff & 7
+
+	window := uint32(oid[byteOff])<<8 | uint32(oid[byteOff+1])
+	pi := (window >> (16 - bitInByte - fieldBits)) & 0x1ff
+
+	return int(pi >> 6), 1 << (wordBits - 1 - (pi & 63))
+}
diff --git a/internal/format/packidx/bloom/lookup_test.go b/internal/format/packidx/bloom/lookup_test.go
new file mode 100644
index 00000000..e6264f9a
--- /dev/null
+++ b/internal/format/packidx/bloom/lookup_test.go
@@ -0,0 +1,32 @@
+package bloom_test
+
+import (
+	"testing"
+
+	"lindenii.org/go/furgit/internal/format/packidx/bloom"
+	"lindenii.org/go/furgit/object/id"
+)
+
+func TestMayContainBadLength(t *testing.T) {
+	t.Parallel()
+
+	format := id.ObjectFormatSHA256
+
+	builder, err := bloom.NewBuilder(format, 4, 2, make([]byte, format.Size()))
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	filter, err := bloom.Parse(builder.Bytes(), format)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	defer func() {
+		if recover() == nil {
+			t.Fatal("MayContain did not panic on a short object ID")
+		}
+	}()
+
+	filter.MayContain(make([]byte, format.Size()-1))
+}
diff --git a/internal/format/packidx/bloom/roundtrip_test.go b/internal/format/packidx/bloom/roundtrip_test.go
new file mode 100644
index 00000000..9f831538
--- /dev/null
+++ b/internal/format/packidx/bloom/roundtrip_test.go
@@ -0,0 +1,92 @@
+package bloom_test
+
+import (
+	"bytes"
+	"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)
+			}
+
+			size := format.Size()
+			packHash := makeOID(size, 0xC0FFEE)
+
+			builder, err := bloom.NewBuilder(format, bucketCount, k, packHash)
+			if err != nil {
+				t.Fatal(err)
+			}
+
+			for i := range objects {
+				builder.Add(makeOID(size, uint64(i))) //nolint:gosec
+			}
+
+			filter, err := bloom.Parse(builder.Bytes(), format)
+			if err != nil {
+				t.Fatal(err)
+			}
+
+			if !bytes.Equal(filter.PackHash(), packHash) {
+				t.Fatalf("PackHash = %x, want %x", filter.PackHash(), packHash)
+			}
+
+			err = filter.Verify()
+			if err != nil {
+				t.Fatalf("Verify on a freshly built filter: %v", err)
+			}
+
+			for i := range objects {
+				if !filter.MayContain(makeOID(size, uint64(i))) { //nolint:gosec
+					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))) { //nolint:gosec
+					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)
+		})
+	}
+}
diff --git a/internal/format/packidx/bloom/write.go b/internal/format/packidx/bloom/write.go
new file mode 100644
index 00000000..e6213a2c
--- /dev/null
+++ b/internal/format/packidx/bloom/write.go
@@ -0,0 +1,164 @@
+package bloom
+
+import (
+	"encoding/binary"
+	"errors"
+	"fmt"
+	"hash"
+	"math/bits"
+
+	"lindenii.org/go/furgit/object/id"
+	"lindenii.org/go/lgo/intconv"
+)
+
+// ErrInvalidParameters reports that
+// the parameters supplied for a filter build
+// are not representable in the format.
+var ErrInvalidParameters = errors.New("internal/format/packidx/bloom: invalid parameters")
+
+// defaultK is the probe count used by [RecommendParams].
+//
+// With 512-bit buckets it keeps the false positive rate near one percent
+// at the target bucket load.
+const defaultK = 8
+
+// targetLoad is the object count per bucket that [RecommendParams] aims for.
+const targetLoad = 48
+
+// Builder accumulates object IDs into an in-memory Bloom filter
+// and serializes it.
+//
+// Labels: MT-Unsafe.
+type Builder struct {
+	// data is the full filter file, header and trailer included.
+	data []byte
+
+	// buckets aliases the bucket region of data, between header and trailer.
+	buckets []byte
+
+	// hashImpl computes the trailing checksum and gives the hash size.
+	hashImpl hash.Hash
+
+	log2B uint
+	k     int
+}
+
+// NewBuilder creates a filter builder
+// for bucketCount buckets and k probes per object ID,
+// binding the filter to packHash.
+//
+// bucketCount must be a nonzero power of two,
+// k must be nonzero,
+// and log2(bucketCount) + 9*k must not exceed the hash length in bits.
+// packHash must be the pack's trailer hash;
+// NewBuilder panics when its length does not match the object format.
+func NewBuilder(objectFormat id.ObjectFormat, bucketCount uint32, k uint16, packHash []byte) (*Builder, error) {
+	hashID, err := hashFunctionID(objectFormat)
+	if err != nil {
+		return nil, err
+	}
+
+	hashImpl, err := objectFormat.New()
+	if err != nil {
+		return nil, fmt.Errorf("internal/format/packidx/bloom: %w", err)
+	}
+
+	hashSize := objectFormat.Size()
+
+	if len(packHash) != hashSize {
+		panic("internal/format/packidx/bloom: invalid pack hash length")
+	}
+
+	log2B, err := checkParams(bucketCount, k, hashSize)
+	if err != nil {
+		return nil, fmt.Errorf("%w: %w", ErrInvalidParameters, err)
+	}
+
+	total, err := intconv.Uint64ToInt(uint64(HeaderLen) + uint64(BucketLen)*uint64(bucketCount) + 2*uint64(hashSize)) //#nosec G115
+	if err != nil {
+		return nil, fmt.Errorf("%w: %w", ErrInvalidParameters, err)
+	}
+
+	data := make([]byte, total)
+	binary.BigEndian.PutUint32(data[0:], signature)
+	binary.BigEndian.PutUint32(data[4:], version)
+	binary.BigEndian.PutUint32(data[8:], hashID)
+	binary.BigEndian.PutUint32(data[12:], bucketCount)
+	binary.BigEndian.PutUint16(data[16:], k)
+
+	bucketsEnd := total - 2*hashSize
+	copy(data[bucketsEnd:], packHash)
+
+	return &Builder{
+		data:     data,
+		buckets:  data[HeaderLen:bucketsEnd],
+		hashImpl: hashImpl,
+		log2B:    log2B,
+		k:        int(k),
+	}, nil
+}
+
+// Add records oid in the filter.
+//
+// oid must be exactly the filter's hash size;
+// Add panics otherwise.
+func (b *Builder) Add(oid []byte) {
+	if len(oid) != b.hashImpl.Size() {
+		panic("internal/format/packidx/bloom: invalid object ID length")
+	}
+
+	base := int(binary.BigEndian.Uint32(oid[:4])>>(32-b.log2B)) * BucketLen
+
+	for i := range b.k {
+		word, mask := probe(oid, b.log2B, i)
+
+		off := base + word*8
+		set := binary.BigEndian.Uint64(b.buckets[off:]) | mask
+		binary.BigEndian.PutUint64(b.buckets[off:], set)
+	}
+}
+
+// Bytes returns the serialized filter, including its trailing checksum.
+//
+// Labels: Life-Parent, Mut-No.
+func (b *Builder) Bytes() []byte {
+	checksumOff := len(b.data) - b.hashImpl.Size()
+
+	b.hashImpl.Reset()
+	_, _ = b.hashImpl.Write(b.data[:checksumOff])
+	b.hashImpl.Sum(b.data[checksumOff:checksumOff])
+
+	return b.data
+}
+
+// RecommendParams returns filter parameters for an index of n objects,
+// targeting a false positive rate near one percent.
+func RecommendParams(objectFormat id.ObjectFormat, n int) (bucketCount uint32, k uint16, err error) {
+	hashSize := objectFormat.Size()
+	if hashSize == 0 {
+		return 0, 0, id.ErrInvalidObjectFormat
+	}
+
+	const maxPow2 = uint32(1) << 31
+
+	wanted := uint64(0)
+	if n > 0 {
+		wanted = (uint64(n) + targetLoad - 1) / targetLoad
+	}
+
+	switch {
+	case wanted <= 1:
+		bucketCount = 1
+	case wanted > uint64(maxPow2):
+		bucketCount = maxPow2
+	default:
+		bucketCount = uint32(1) << bits.Len64(wanted-1)
+	}
+
+	_, err = checkParams(bucketCount, defaultK, hashSize)
+	if err != nil {
+		return 0, 0, fmt.Errorf("%w: %w", ErrInvalidParameters, err)
+	}
+
+	return bucketCount, defaultK, nil
+}
diff --git a/internal/format/packidx/bloom/write_test.go b/internal/format/packidx/bloom/write_test.go
new file mode 100644
index 00000000..74173921
--- /dev/null
+++ b/internal/format/packidx/bloom/write_test.go
@@ -0,0 +1,95 @@
+package bloom_test
+
+import (
+	"errors"
+	"testing"
+
+	"lindenii.org/go/furgit/internal/format/packidx/bloom"
+	"lindenii.org/go/furgit/object/id"
+)
+
+func TestRecommendParams(t *testing.T) {
+	t.Parallel()
+
+	for _, format := range id.SupportedObjectFormats() {
+		t.Run(format.String(), func(t *testing.T) {
+			t.Parallel()
+
+			for _, n := range []int{0, 1, 1000, 10000, 1000000} {
+				bucketCount, k, err := bloom.RecommendParams(format, n)
+				if err != nil {
+					t.Fatalf("n=%d: %v", n, err)
+				}
+
+				if bucketCount == 0 || bucketCount&(bucketCount-1) != 0 {
+					t.Errorf("n=%d: bucket count %d not a power of two", n, bucketCount)
+				}
+
+				_, err = bloom.NewBuilder(format, bucketCount, k, make([]byte, format.Size()))
+				if err != nil {
+					t.Errorf("n=%d: recommended parameters rejected: %v", n, err)
+				}
+			}
+		})
+	}
+}
+
+func TestNewBuilderRejects(t *testing.T) {
+	t.Parallel()
+
+	cases := []struct {
+		name        string
+		bucketCount uint32
+		k           uint16
+	}{
+		{"zero buckets", 0, 8},
+		{"non power of two", 3, 8},
+		{"zero probe count", 4, 0},
+	}
+
+	for _, format := range id.SupportedObjectFormats() {
+		t.Run(format.String(), func(t *testing.T) {
+			t.Parallel()
+
+			for _, tc := range cases {
+				t.Run(tc.name, func(t *testing.T) {
+					t.Parallel()
+
+					_, err := bloom.NewBuilder(format, tc.bucketCount, tc.k, make([]byte, format.Size()))
+					if !errors.Is(err, bloom.ErrInvalidParameters) {
+						t.Fatalf("error = %v, want ErrInvalidParameters", err)
+					}
+				})
+			}
+		})
+	}
+}
+
+func TestNewBuilderBadPackHash(t *testing.T) {
+	t.Parallel()
+
+	defer func() {
+		if recover() == nil {
+			t.Fatal("NewBuilder did not panic on a short pack hash")
+		}
+	}()
+
+	_, _ = bloom.NewBuilder(id.ObjectFormatSHA256, 4, 2, make([]byte, id.ObjectFormatSHA256.Size()-1))
+}
+
+func TestAddBadLength(t *testing.T) {
+	t.Parallel()
+
+	builder, err := bloom.NewBuilder(id.ObjectFormatSHA256, 4, 2, make([]byte, id.ObjectFormatSHA256.Size()))
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	defer func() {
+		if recover() == nil {
+			t.Fatal("Add did not panic on a short object ID")
+		}
+	}()
+
+	builder.Add(make([]byte, id.ObjectFormatSHA256.Size()-1))
+}
diff --git a/internal/format/packidx/lookup.go b/internal/format/packidx/lookup.go
index d1293f47..71847f21 100644
--- a/internal/format/packidx/lookup.go
+++ b/internal/format/packidx/lookup.go
@@ -4,6 +4,7 @@ import (
 	"bytes"
 	"encoding/binary"
 	"fmt"
+	"math/bits"
 )
 
 // Lookup searches the index for one object ID
@@ -18,6 +19,53 @@ func (idx *Packidx) Lookup(oid []byte) (offset uint64, found bool, err error) {
 
 	lo, hi := idx.fanoutRange(oid[0])
 
+	// Object IDs are uniform for honest inputs,
+	// interp on next 8 octets converges in O(log log n).
+	//
+	// OIDs are public unkeyed hashes,
+	// so an attacker may sample/filter/mine prefix clusters,
+	// making interpolation mis-estimate every probe.
+	// See https://runxiyu.org/comp/ch4ht/
+	// for why cryptographic hash algorithms are insufficient.
+	//
+	// Cap the interp at bisect's probe count and finish by bisect;
+	// adversarial at O(log n) plus small interpolation overhead,
+	// honest exit well under the cap.
+	target := binary.BigEndian.Uint64(oid[1:9])
+
+	for budget := bits.Len(uint(hi - lo)); hi-lo > 8 && budget > 0; budget-- { //nolint:gosec
+		loKey := binary.BigEndian.Uint64(idx.OIDAt(lo)[1:9])
+		hiKey := binary.BigEndian.Uint64(idx.OIDAt(hi - 1)[1:9])
+
+		var mid int
+
+		switch {
+		case target <= loKey:
+			mid = lo
+		case target >= hiKey:
+			mid = hi - 1
+		default:
+			hi128, lo128 := bits.Mul64(target-loKey, uint64(hi-lo-1)) //#nosec G115
+			q, _ := bits.Div64(hi128, lo128, hiKey-loKey)
+			mid = lo + int(q) //#nosec G115
+		}
+
+		switch cmp := bytes.Compare(oid, idx.OIDAt(mid)); {
+		case cmp == 0:
+			offset, err = idx.OffsetAt(mid)
+			if err != nil {
+				return 0, false, err
+			}
+
+			return offset, true, nil
+		case cmp < 0:
+			hi = mid
+		default:
+			lo = mid + 1
+		}
+	}
+
+	// Interpolation narrowed or capped; bisect to finish.
 	for lo < hi {
 		mid := lo + (hi-lo)/2
 
diff --git a/internal/format/packidx/write_test.go b/internal/format/packidx/write_test.go
index 68df3ece..866fa274 100644
--- a/internal/format/packidx/write_test.go
+++ b/internal/format/packidx/write_test.go
@@ -16,8 +16,8 @@ func syntheticEntries(n int) []packidx.Entry {
 	for i := range entries {
 		entries[i].OID[0] = byte(i * 7)
 		entries[i].OID[1] = byte(i + 1)
-		entries[i].Offset = uint64(i+1) * 100
-		entries[i].CRC32 = uint32(i+1) * 0x01010101
+		entries[i].Offset = uint64(i+1) * 100       //#nosec G115
+		entries[i].CRC32 = uint32(i+1) * 0x01010101 //#nosec G115
 	}
 
 	return entries
diff --git a/internal/progress/meter.go b/internal/progress/meter.go
index e5e64fb4..9d4f1155 100644
--- a/internal/progress/meter.go
+++ b/internal/progress/meter.go
@@ -1,17 +1,22 @@
 package progress
 
 import (
+	"sync/atomic"
 	"time"
 
 	"lindenii.org/go/lgo/iowrap"
 )
 
 const (
-	updateInterval     = time.Second
+	renderInterval     = 100 * time.Millisecond
+	forceInterval      = time.Second
 	throughputInterval = 500 * time.Millisecond
 )
 
 // Meter renders one in-place progress line.
+//
+// Add is safe for concurrent use; a single background goroutine renders.
+// Stop must be called exactly once to flush the final line and release it.
 type Meter struct {
 	writer iowrap.WriteFlusher
 
@@ -21,24 +26,29 @@ type Meter struct {
 	sparse     bool
 	throughput bool
 
-	startedAt      time.Time
-	nextUpdateAt   time.Time
-	nextThroughput time.Time
+	done     atomic.Int64
+	bytes    atomic.Int64
+	sawValue atomic.Bool
 
-	lastDone     int
-	lastBytes    int
-	lastPercent  int
-	lastCounterW int
-	sawValue     bool
+	startedAt time.Time
 
+	stop   chan struct{}
+	exited chan struct{}
+
+	// The following are owned by the render goroutine while it runs,
+	// then by Stop once exited is closed.
+	nextForceAt      time.Time
+	nextThroughput   time.Time
+	lastPercent      int
+	lastCounterW     int
 	throughputSuffix string
 }
 
-// New creates one progress meter.
+// New creates one progress meter and starts its render goroutine.
 func New(opts Options) *Meter {
 	now := time.Now()
 
-	return &Meter{
+	meter := &Meter{
 		writer:         opts.Writer,
 		title:          opts.Title,
 		total:          opts.Total,
@@ -46,10 +56,20 @@ func New(opts Options) *Meter {
 		sparse:         opts.Sparse,
 		throughput:     opts.Throughput,
 		startedAt:      now,
-		nextUpdateAt:   now.Add(updateInterval),
+		stop:           make(chan struct{}),
+		exited:         make(chan struct{}),
+		nextForceAt:    now.Add(forceInterval),
 		nextThroughput: now.Add(throughputInterval),
 		lastPercent:    -1,
 	}
+
+	if meter.writer != nil {
+		go meter.loop()
+	} else {
+		close(meter.exited)
+	}
+
+	return meter
 }
 
 // Options configures one progress meter.
@@ -67,59 +87,71 @@ type Options struct {
 	Throughput bool
 }
 
-// Set records current progress
-// and renders when percent changed or the 1s tick elapsed.
-func (meter *Meter) Set(done int, bytes int) {
-	meter.lastDone = done
-	meter.lastBytes = bytes
-	meter.sawValue = true
+// Add increments the done and byte counters.
+//
+// Labels: MT-Safe.
+func (meter *Meter) Add(done, bytes int64) {
+	meter.done.Add(done)
+	meter.bytes.Add(bytes)
+	meter.sawValue.Store(true)
+}
+
+// Stop ends the render goroutine, forces the final line, and appends ", <msg>.".
+func (meter *Meter) Stop(msg string) {
+	close(meter.stop)
+	<-meter.exited
 
-	if meter.writer == nil {
+	if !meter.sawValue.Load() || meter.writer == nil {
 		return
 	}
 
-	now := time.Now()
-	forced := meter.consumeUpdateTick(now)
-
-	percentChanged := false
-
-	if meter.total > 0 {
-		percent := int(int64(done) * 100 / int64(meter.total))
-		percentChanged = percent != meter.lastPercent
+	if msg == "" {
+		msg = "done"
 	}
 
-	if !percentChanged && !forced {
-		return
+	if meter.sparse && meter.total > 0 && int(meter.done.Load()) != meter.total {
+		meter.done.Store(int64(meter.total))
 	}
 
-	meter.render(now, "\r")
+	meter.render(time.Now(), ", "+msg+".\n")
 }
 
-// Stop forces the final progress line and appends ", <msg>.".
-func (meter *Meter) Stop(msg string) {
-	if !meter.sawValue || meter.writer == nil {
-		return
-	}
+func (meter *Meter) loop() {
+	defer close(meter.exited)
 
-	if msg == "" {
-		msg = "done"
+	ticker := time.NewTicker(renderInterval)
+	defer ticker.Stop()
+
+	for {
+		select {
+		case <-meter.stop:
+			return
+		case now := <-ticker.C:
+			meter.maybeRender(now)
+		}
 	}
+}
 
-	if meter.sparse && meter.total > 0 && meter.lastDone != meter.total {
-		meter.lastDone = meter.total
+func (meter *Meter) maybeRender(now time.Time) {
+	if !meter.sawValue.Load() {
+		return
 	}
 
-	meter.render(time.Now(), ", "+msg+".\n")
-}
+	forced := false
 
-func (meter *Meter) consumeUpdateTick(now time.Time) bool {
-	if now.Before(meter.nextUpdateAt) {
-		return false
+	for !now.Before(meter.nextForceAt) {
+		meter.nextForceAt = meter.nextForceAt.Add(forceInterval)
+		forced = true
 	}
 
-	for !now.Before(meter.nextUpdateAt) {
-		meter.nextUpdateAt = meter.nextUpdateAt.Add(updateInterval)
+	percentChanged := false
+
+	if meter.total > 0 {
+		percent := int(meter.done.Load() * 100 / int64(meter.total))
+		percentChanged = percent != meter.lastPercent
 	}
 
-	return true
+	if percentChanged || forced {
+		meter.render(now, "\r")
+	}
 }
diff --git a/internal/progress/meter_test.go b/internal/progress/meter_test.go
new file mode 100644
index 00000000..8fa09973
--- /dev/null
+++ b/internal/progress/meter_test.go
@@ -0,0 +1,43 @@
+package progress_test
+
+import (
+	"bytes"
+	"strings"
+	"sync"
+	"testing"
+	"time"
+
+	"lindenii.org/go/furgit/internal/progress"
+	"lindenii.org/go/lgo/iowrap"
+)
+
+func TestMeterConcurrentAdd(t *testing.T) {
+	t.Parallel()
+
+	var buf bytes.Buffer
+
+	meter := progress.New(progress.Options{
+		Writer: iowrap.NopFlush(&buf),
+		Title:  "test",
+		Total:  1000,
+	})
+
+	var wg sync.WaitGroup
+
+	for range 10 {
+		wg.Go(func() {
+			for range 100 {
+				meter.Add(1, 0)
+				time.Sleep(time.Millisecond)
+			}
+		})
+	}
+
+	wg.Wait()
+
+	meter.Stop("done")
+
+	if got := buf.String(); !strings.Contains(got, "100% (1000/1000)") {
+		t.Fatalf("final line = %q, want it to contain %q", got, "100% (1000/1000)")
+	}
+}
diff --git a/internal/progress/render.go b/internal/progress/render.go
index 814ced98..a67d40ff 100644
--- a/internal/progress/render.go
+++ b/internal/progress/render.go
@@ -40,13 +40,15 @@ func (meter *Meter) render(now time.Time, eol string) {
 }
 
 func (meter *Meter) renderCounters() string {
+	done := meter.done.Load()
+
 	if meter.total > 0 {
-		meter.lastPercent = int(int64(meter.lastDone) * 100 / int64(meter.total))
+		meter.lastPercent = int(done * 100 / int64(meter.total))
 
-		return fmt.Sprintf("%3d%% (%d/%d)%s", meter.lastPercent, meter.lastDone, meter.total, meter.throughputSuffix)
+		return fmt.Sprintf("%3d%% (%d/%d)%s", meter.lastPercent, done, meter.total, meter.throughputSuffix)
 	}
 
-	return fmt.Sprintf("%d%s", meter.lastDone, meter.throughputSuffix)
+	return fmt.Sprintf("%d%s", done, meter.throughputSuffix)
 }
 
 func (meter *Meter) refreshThroughput(now time.Time) {
@@ -67,6 +69,7 @@ func (meter *Meter) refreshThroughput(now time.Time) {
 		return
 	}
 
-	rate := uint64(float64(meter.lastBytes) / elapsed.Seconds())
-	meter.throughputSuffix = ", " + humanize.Bytes(uint64(meter.lastBytes)) + " | " + humanize.Bytes(rate) + "/s" //nolint:gosec
+	bytes := meter.bytes.Load()
+	rate := uint64(float64(bytes) / elapsed.Seconds())
+	meter.throughputSuffix = ", " + humanize.Bytes(uint64(bytes)) + " | " + humanize.Bytes(rate) + "/s" //#nosec G115
 }
diff --git a/internal/testgit/command.go b/internal/testgit/command.go
index 4e696ece..4fc8ab17 100644
--- a/internal/testgit/command.go
+++ b/internal/testgit/command.go
@@ -15,7 +15,7 @@ func (repo *Repo) command(
 ) *exec.Cmd {
 	tb.Helper()
 
-	cmd := exec.CommandContext(tb.Context(), command, args...) //nolint:gosec
+	cmd := exec.CommandContext(tb.Context(), command, args...)
 	cmd.Dir = repo.path
 	cmd.Env = repo.env