aboutsummaryrefslogtreecommitdiff
path: root/format/commitgraph/bloom
diff options
context:
space:
mode:
Diffstat (limited to 'format/commitgraph/bloom')
-rw-r--r--format/commitgraph/bloom/contain.go10
-rw-r--r--format/commitgraph/bloom/filter.go21
-rw-r--r--format/commitgraph/bloom/key.go39
-rw-r--r--format/commitgraph/bloom/settings.go21
4 files changed, 67 insertions, 24 deletions
diff --git a/format/commitgraph/bloom/contain.go b/format/commitgraph/bloom/contain.go
index 4789b321..331b7687 100644
--- a/format/commitgraph/bloom/contain.go
+++ b/format/commitgraph/bloom/contain.go
@@ -5,22 +5,18 @@ package bloom
// 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
- }
-
+func (f *Filter) MightContain(path []byte) (bool, error) {
if len(f.Data) == 0 {
return false, nil
}
- keys, err := keyvec(path, settings)
+ keys, err := keyvec(path, f)
if err != nil {
return false, err
}
for i := range keys {
- if filterContainsKey(f, &keys[i], settings) {
+ if filterContainsKey(f, keys[i]) {
return true, nil
}
}
diff --git a/format/commitgraph/bloom/filter.go b/format/commitgraph/bloom/filter.go
index f56e9ba3..7c4aa1b8 100644
--- a/format/commitgraph/bloom/filter.go
+++ b/format/commitgraph/bloom/filter.go
@@ -6,6 +6,23 @@ package bloom
// 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
+ Data []byte
+
+ HashVersion uint32
+ NumHashes uint32
+ BitsPerEntry uint32
+ MaxChangePaths uint32
+}
+
+// NewFilter constructs one query-ready bloom filter from raw data/settings.
+func NewFilter(data []byte, settings Settings) *Filter {
+ out := &Filter{
+ Data: data,
+ HashVersion: settings.HashVersion,
+ NumHashes: settings.NumHashes,
+ BitsPerEntry: settings.BitsPerEntry,
+ MaxChangePaths: settings.MaxChangePaths,
+ }
+
+ return out
}
diff --git a/format/commitgraph/bloom/key.go b/format/commitgraph/bloom/key.go
index 6e49959d..a15df904 100644
--- a/format/commitgraph/bloom/key.go
+++ b/format/commitgraph/bloom/key.go
@@ -1,10 +1,12 @@
package bloom
+import "codeberg.org/lindenii/furgit/internal/intconv"
+
type key struct {
hashes []uint32
}
-func keyvec(path []byte, settings *Settings) ([]key, error) {
+func keyvec(path []byte, filter *Filter) ([]key, error) {
if len(path) == 0 {
return nil, nil
}
@@ -19,7 +21,7 @@ func keyvec(path []byte, settings *Settings) ([]key, error) {
keys := make([]key, 0, count)
- full, err := keyFill(path, settings)
+ full, err := keyFill(path, filter)
if err != nil {
return nil, err
}
@@ -28,7 +30,7 @@ func keyvec(path []byte, settings *Settings) ([]key, error) {
for i := len(path) - 1; i >= 0; i-- {
if path[i] == '/' {
- k, err := keyFill(path[:i], settings)
+ k, err := keyFill(path[:i], filter)
if err != nil {
return nil, err
}
@@ -40,7 +42,7 @@ func keyvec(path []byte, settings *Settings) ([]key, error) {
return keys, nil
}
-func keyFill(path []byte, settings *Settings) (key, error) {
+func keyFill(path []byte, filter *Filter) (key, error) {
const (
seed0 = 0x293ae76f
seed1 = 0x7e646e2c
@@ -52,7 +54,8 @@ func keyFill(path []byte, settings *Settings) (key, error) {
err error
)
- if settings.HashVersion == 2 { //nolint:nestif
+ switch filter.HashVersion {
+ case 2:
h0, err = murmur3SeededV2(seed0, path)
if err != nil {
return key{}, err
@@ -62,7 +65,7 @@ func keyFill(path []byte, settings *Settings) (key, error) {
if err != nil {
return key{}, err
}
- } else {
+ case 1:
h0, err = murmur3SeededV1(seed0, path)
if err != nil {
return key{}, err
@@ -72,21 +75,29 @@ func keyFill(path []byte, settings *Settings) (key, error) {
if err != nil {
return key{}, err
}
+ default:
+ return key{}, ErrInvalid
}
- hashes := make([]uint32, settings.NumHashes)
- for i := range settings.NumHashes {
- hashes[i] = h0 + i*h1
+ hashCount, err := intconv.Uint32ToInt(filter.NumHashes)
+ if err != nil {
+ return key{}, ErrInvalid
}
- return key{hashes: hashes}, nil
-}
+ hashes := make([]uint32, hashCount)
+ for i := range hashCount {
+ iU32, err := intconv.IntToUint32(i)
+ if err != nil {
+ return key{}, ErrInvalid
+ }
-func filterContainsKey(filter *Filter, key *key, settings *Settings) bool {
- if filter == nil || key == nil || settings == nil {
- return false
+ hashes[i] = h0 + iU32*h1
}
+ return key{hashes: hashes}, nil
+}
+
+func filterContainsKey(filter *Filter, key key) bool {
if len(filter.Data) == 0 {
return false
}
diff --git a/format/commitgraph/bloom/settings.go b/format/commitgraph/bloom/settings.go
index 5aa122a9..764653bd 100644
--- a/format/commitgraph/bloom/settings.go
+++ b/format/commitgraph/bloom/settings.go
@@ -1,6 +1,10 @@
package bloom
-import "encoding/binary"
+import (
+ "encoding/binary"
+
+ "codeberg.org/lindenii/furgit/internal/intconv"
+)
// Settings describe the changed-paths Bloom filter parameters stored in
// commit-graph BDAT chunks.
@@ -27,5 +31,20 @@ func ParseSettings(bdat []byte) (*Settings, error) {
MaxChangePaths: DefaultMaxChange,
}
+ switch settings.HashVersion {
+ case 1, 2:
+ default:
+ return nil, ErrInvalid
+ }
+
+ if settings.NumHashes == 0 {
+ return nil, ErrInvalid
+ }
+
+ _, err := intconv.Uint32ToInt(settings.NumHashes)
+ if err != nil {
+ return nil, ErrInvalid
+ }
+
return settings, nil
}