aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--format/commitgraph/bloom/bloom.go3
-rw-r--r--format/commitgraph/bloom/constants.go8
-rw-r--r--format/commitgraph/bloom/contain.go29
-rw-r--r--format/commitgraph/bloom/errors.go5
-rw-r--r--format/commitgraph/bloom/filter.go11
-rw-r--r--format/commitgraph/bloom/key.go106
-rw-r--r--format/commitgraph/bloom/murmur.go127
-rw-r--r--format/commitgraph/bloom/settings.go31
-rw-r--r--internal/intconv/intconv.go9
9 files changed, 329 insertions, 0 deletions
diff --git a/format/commitgraph/bloom/bloom.go b/format/commitgraph/bloom/bloom.go
new file mode 100644
index 00000000..9653d595
--- /dev/null
+++ b/format/commitgraph/bloom/bloom.go
@@ -0,0 +1,3 @@
+// Package bloom provides a bloom filter implementation used for changed-path
+// filters in Git commit graphs.
+package bloom
diff --git a/format/commitgraph/bloom/constants.go b/format/commitgraph/bloom/constants.go
new file mode 100644
index 00000000..958e551e
--- /dev/null
+++ b/format/commitgraph/bloom/constants.go
@@ -0,0 +1,8 @@
+package bloom
+
+const (
+ // DataHeaderSize is the size of the BDAT header in commit-graph files.
+ DataHeaderSize = 3 * 4
+ // DefaultMaxChange matches Git's default max-changed-paths behavior.
+ DefaultMaxChange = 512
+)
diff --git a/format/commitgraph/bloom/contain.go b/format/commitgraph/bloom/contain.go
new file mode 100644
index 00000000..4789b321
--- /dev/null
+++ b/format/commitgraph/bloom/contain.go
@@ -0,0 +1,29 @@
+package bloom
+
+// MightContain reports whether the Bloom filter may contain the given path.
+//
+// Evaluated against the full path and each of its directory prefixes. A true
+// result indicates a possible match; false means the path definitely did not
+// change.
+func (f *Filter) MightContain(path []byte, settings *Settings) (bool, error) {
+ if f == nil || settings == nil {
+ return false, nil
+ }
+
+ if len(f.Data) == 0 {
+ return false, nil
+ }
+
+ keys, err := keyvec(path, settings)
+ if err != nil {
+ return false, err
+ }
+
+ for i := range keys {
+ if filterContainsKey(f, &keys[i], settings) {
+ return true, nil
+ }
+ }
+
+ return false, nil
+}
diff --git a/format/commitgraph/bloom/errors.go b/format/commitgraph/bloom/errors.go
new file mode 100644
index 00000000..fe38d1bc
--- /dev/null
+++ b/format/commitgraph/bloom/errors.go
@@ -0,0 +1,5 @@
+package bloom
+
+import "errors"
+
+var ErrInvalid = errors.New("bloom: invalid data")
diff --git a/format/commitgraph/bloom/filter.go b/format/commitgraph/bloom/filter.go
new file mode 100644
index 00000000..f56e9ba3
--- /dev/null
+++ b/format/commitgraph/bloom/filter.go
@@ -0,0 +1,11 @@
+package bloom
+
+// Filter represents a changed-paths Bloom filter associated with a commit.
+//
+// The filter encodes which paths changed between a commit and its first
+// parent. Paths are expected to be in Git's slash-separated form and
+// are queried using a path and its prefixes (e.g. "a/b/c", "a/b", "a").
+type Filter struct {
+ Data []byte
+ Version uint32
+}
diff --git a/format/commitgraph/bloom/key.go b/format/commitgraph/bloom/key.go
new file mode 100644
index 00000000..6e49959d
--- /dev/null
+++ b/format/commitgraph/bloom/key.go
@@ -0,0 +1,106 @@
+package bloom
+
+type key struct {
+ hashes []uint32
+}
+
+func keyvec(path []byte, settings *Settings) ([]key, error) {
+ if len(path) == 0 {
+ return nil, nil
+ }
+
+ count := 1
+
+ for _, b := range path {
+ if b == '/' {
+ count++
+ }
+ }
+
+ keys := make([]key, 0, count)
+
+ full, err := keyFill(path, settings)
+ if err != nil {
+ return nil, err
+ }
+
+ keys = append(keys, full)
+
+ for i := len(path) - 1; i >= 0; i-- {
+ if path[i] == '/' {
+ k, err := keyFill(path[:i], settings)
+ if err != nil {
+ return nil, err
+ }
+
+ keys = append(keys, k)
+ }
+ }
+
+ return keys, nil
+}
+
+func keyFill(path []byte, settings *Settings) (key, error) {
+ const (
+ seed0 = 0x293ae76f
+ seed1 = 0x7e646e2c
+ )
+
+ var (
+ h0 uint32
+ h1 uint32
+ err error
+ )
+
+ if settings.HashVersion == 2 { //nolint:nestif
+ h0, err = murmur3SeededV2(seed0, path)
+ if err != nil {
+ return key{}, err
+ }
+
+ h1, err = murmur3SeededV2(seed1, path)
+ if err != nil {
+ return key{}, err
+ }
+ } else {
+ h0, err = murmur3SeededV1(seed0, path)
+ if err != nil {
+ return key{}, err
+ }
+
+ h1, err = murmur3SeededV1(seed1, path)
+ if err != nil {
+ return key{}, err
+ }
+ }
+
+ hashes := make([]uint32, settings.NumHashes)
+ for i := range settings.NumHashes {
+ hashes[i] = h0 + i*h1
+ }
+
+ return key{hashes: hashes}, nil
+}
+
+func filterContainsKey(filter *Filter, key *key, settings *Settings) bool {
+ if filter == nil || key == nil || settings == nil {
+ return false
+ }
+
+ if len(filter.Data) == 0 {
+ return false
+ }
+
+ mod := uint64(len(filter.Data)) * 8
+ for _, h := range key.hashes {
+ idx := uint64(h) % mod
+ bytePos := idx / 8
+
+ bit := byte(1 << (idx & 7))
+ if filter.Data[bytePos]&bit == 0 {
+ return false
+ }
+ }
+
+ return true
+}
diff --git a/format/commitgraph/bloom/murmur.go b/format/commitgraph/bloom/murmur.go
new file mode 100644
index 00000000..363b63ae
--- /dev/null
+++ b/format/commitgraph/bloom/murmur.go
@@ -0,0 +1,127 @@
+package bloom
+
+import "codeberg.org/lindenii/furgit/internal/intconv"
+
+func murmur3SeededV2(seed uint32, data []byte) (uint32, error) {
+ const (
+ c1 = 0xcc9e2d51
+ c2 = 0x1b873593
+ r1 = 15
+ r2 = 13
+ m = 5
+ n = 0xe6546b64
+ )
+
+ h := seed
+
+ nblocks := len(data) / 4
+ for i := range nblocks {
+ k := uint32(data[4*i]) |
+ (uint32(data[4*i+1]) << 8) |
+ (uint32(data[4*i+2]) << 16) |
+ (uint32(data[4*i+3]) << 24)
+ k *= c1
+ k = (k << r1) | (k >> (32 - r1))
+ k *= c2
+
+ h ^= k
+ h = (h << r2) | (h >> (32 - r2))
+ h = h*m + n
+ }
+
+ var k1 uint32
+
+ tail := data[nblocks*4:]
+ switch len(tail) & 3 {
+ case 3:
+ k1 ^= uint32(tail[2]) << 16
+
+ fallthrough
+ case 2:
+ k1 ^= uint32(tail[1]) << 8
+
+ fallthrough
+ case 1:
+ k1 ^= uint32(tail[0])
+ k1 *= c1
+ k1 = (k1 << r1) | (k1 >> (32 - r1))
+ k1 *= c2
+ h ^= k1
+ }
+
+ dataLen, err := intconv.IntToUint32(len(data))
+ if err != nil {
+ return 0, err
+ }
+
+ h ^= dataLen
+ h ^= h >> 16
+ h *= 0x85ebca6b
+ h ^= h >> 13
+ h *= 0xc2b2ae35
+ h ^= h >> 16
+
+ return h, nil
+}
+
+func murmur3SeededV1(seed uint32, data []byte) (uint32, error) {
+ const (
+ c1 = 0xcc9e2d51
+ c2 = 0x1b873593
+ r1 = 15
+ r2 = 13
+ m = 5
+ n = 0xe6546b64
+ )
+
+ h := seed
+
+ nblocks := len(data) / 4
+ for i := range nblocks {
+ k := intconv.SignExtendByteToUint32(data[4*i]) |
+ (intconv.SignExtendByteToUint32(data[4*i+1]) << 8) |
+ (intconv.SignExtendByteToUint32(data[4*i+2]) << 16) |
+ (intconv.SignExtendByteToUint32(data[4*i+3]) << 24)
+ k *= c1
+ k = (k << r1) | (k >> (32 - r1))
+ k *= c2
+
+ h ^= k
+ h = (h << r2) | (h >> (32 - r2))
+ h = h*m + n
+ }
+
+ var k1 uint32
+
+ tail := data[nblocks*4:]
+ switch len(tail) & 3 {
+ case 3:
+ k1 ^= intconv.SignExtendByteToUint32(tail[2]) << 16
+
+ fallthrough
+ case 2:
+ k1 ^= intconv.SignExtendByteToUint32(tail[1]) << 8
+
+ fallthrough
+ case 1:
+ k1 ^= intconv.SignExtendByteToUint32(tail[0])
+ k1 *= c1
+ k1 = (k1 << r1) | (k1 >> (32 - r1))
+ k1 *= c2
+ h ^= k1
+ }
+
+ dataLen, err := intconv.IntToUint32(len(data))
+ if err != nil {
+ return 0, err
+ }
+
+ h ^= dataLen
+ h ^= h >> 16
+ h *= 0x85ebca6b
+ h ^= h >> 13
+ h *= 0xc2b2ae35
+ h ^= h >> 16
+
+ return h, nil
+}
diff --git a/format/commitgraph/bloom/settings.go b/format/commitgraph/bloom/settings.go
new file mode 100644
index 00000000..5aa122a9
--- /dev/null
+++ b/format/commitgraph/bloom/settings.go
@@ -0,0 +1,31 @@
+package bloom
+
+import "encoding/binary"
+
+// Settings describe the changed-paths Bloom filter parameters stored in
+// commit-graph BDAT chunks.
+//
+// Obviously, they must match the repository's commit-graph settings to
+// interpret filters correctly.
+type Settings struct {
+ HashVersion uint32
+ NumHashes uint32
+ BitsPerEntry uint32
+ MaxChangePaths uint32
+}
+
+// ParseSettings reads Bloom filter settings from a BDAT chunk header.
+func ParseSettings(bdat []byte) (*Settings, error) {
+ if len(bdat) < DataHeaderSize {
+ return nil, ErrInvalid
+ }
+
+ settings := &Settings{
+ HashVersion: binary.BigEndian.Uint32(bdat[0:4]),
+ NumHashes: binary.BigEndian.Uint32(bdat[4:8]),
+ BitsPerEntry: binary.BigEndian.Uint32(bdat[8:12]),
+ MaxChangePaths: DefaultMaxChange,
+ }
+
+ return settings, nil
+}
diff --git a/internal/intconv/intconv.go b/internal/intconv/intconv.go
index c4b429e3..8d3ac9c6 100644
--- a/internal/intconv/intconv.go
+++ b/internal/intconv/intconv.go
@@ -68,3 +68,12 @@ func Int64ToInt32(v int64) (int32, error) {
return int32(v), nil
}
+
+// SignExtendByteToUint32 sign-extends b as a signed 8-bit integer into uint32.
+func SignExtendByteToUint32(b byte) uint32 {
+ if b&0x80 == 0 {
+ return uint32(b)
+ }
+
+ return 0xFFFFFF00 | uint32(b)
+}
generated by cgit v1.3.1-10-gc9f91 (git 2.54.0) at 2026-05-25 17:38:37 +0000