1// SPDX-License-Identifier: MIT
2
3package git
4
5import (
6 "encoding/binary"
7)
8
9// Changed-path Bloom filters (BIDX and BDAT chunks of the commit-graph).
10//
11// For each commit the filter holds the paths that differ between the commit
12// and its first parent (or the empty tree for a root commit). Git inserts
13// every changed path together with each of its leading directories, without
14// a trailing slash: changing "a/b/c" adds "a/b/c", "a/b" and "a". Looking
15// up a path therefore only needs the key of that path, whether it is a file
16// or a directory.
17//
18// Hashing mirrors git's bloom.c. A key is two 32-bit murmur3 hashes of the
19// path with fixed seeds, h0 and h1; the i-th probe is h0 + i*h1 (mod 2^32),
20// taken modulo the number of bits of the filter. Bit n of the filter is
21// bit (n & 7) of byte n/8.
22//
23// BDAT header version 1 is the original hash, which uses plain char: it
24// sign-extends bytes >= 0x80 when git was built with a signed char (x86) but
25// not where char is unsigned (Linux arm64, ppc64, s390x), where it equals the
26// version 2 hash. The file does not say which one wrote it, so on a version 1
27// layer a key holding a byte >= 0x80 is tested with both hashes and the
28// answer is "maybe" if either matches; trying both can only add false
29// positives, never false negatives. Version 2 always uses unsigned
30// arithmetic. The version is read per layer from BDAT. For paths made of
31// bytes < 0x80 all hashes are identical.
32//
33// Only paths git inserts can be answered: see newBloomKey for the paths that
34// are reported as unknown.
35//
36// A filter of one byte 0x00 means "no changed path" and one byte 0xff means
37// "too many changed paths (more than 512)": the latter is reported as
38// unknown. An empty or out-of-bounds filter is unknown as well.
39
40const (
41 bloomHeaderSize = 12 // version, number of hashes, bits per entry
42 bloomMaxHashes = 256 // sanity bound on the probe count read from disk
43 bloomSeed0 = 0x293ae76f
44 bloomSeed1 = 0x7e646e2c
45)
46
47// bloomKey holds the precomputed hashes of a path for both hash versions. It
48// is a small value; build it once per path and reuse it for many commits. The
49// zero value is not usable and always yields an unknown answer.
50type bloomKey struct {
51 v1, v2 [2]uint32 // signed-char (version 1) and unsigned (version 2) hashes
52 high bool // the path has a byte >= 0x80, so v1 and v2 differ
53 usable bool // git can have inserted this key
54}
55
56// newBloomKey computes the key of path. It does not allocate.
57//
58// One trailing slash is stripped, as git does for pathspecs, so "dir/" and
59// "dir" give the same key. A path git never inserts yields an unusable key,
60// for which every lookup is unknown (the caller must diff the trees): the
61// empty path, a path starting with "/", with an empty segment ("a//b", or a
62// second trailing slash), with a "." or ".." segment, or holding a NUL byte.
63func newBloomKey(path []byte) bloomKey {
64 if n := len(path); n > 0 && path[n-1] == '/' {
65 path = path[:n-1]
66 }
67 if !bloomPathUsable(path) {
68 return bloomKey{}
69 }
70 k := bloomKey{usable: true, v2: [2]uint32{
71 murmur3Seeded(bloomSeed0, path, false),
72 murmur3Seeded(bloomSeed1, path, false),
73 }}
74 k.v1 = k.v2
75 for _, b := range path {
76 if b >= 0x80 {
77 k.high = true
78 k.v1 = [2]uint32{
79 murmur3Seeded(bloomSeed0, path, true),
80 murmur3Seeded(bloomSeed1, path, true),
81 }
82 break
83 }
84 }
85 return k
86}
87
88// bloomPathUsable reports whether path is a normalised, repository-relative
89// path whose segments are all non-empty and not "." or "..".
90func bloomPathUsable(path []byte) bool {
91 if len(path) == 0 {
92 return false
93 }
94 start := 0
95 for i := 0; i <= len(path); i++ {
96 if i < len(path) && path[i] != '/' {
97 if path[i] == 0 {
98 return false
99 }
100 continue
101 }
102 switch seg := path[start:i]; {
103 case len(seg) == 0:
104 return false
105 case len(seg) == 1 && seg[0] == '.':
106 return false
107 case len(seg) == 2 && seg[0] == '.' && seg[1] == '.':
108 return false
109 }
110 start = i + 1
111 }
112 return true
113}
114
115// newBloomKeyString is newBloomKey for a string path.
116func newBloomKeyString(path string) bloomKey {
117 return newBloomKey([]byte(path))
118}
119
120func rotl32(x uint32, r uint) uint32 { return x<<r | x>>(32-r) }
121
122// murmur3Seeded is MurmurHash3 x86 32-bit as implemented by git. With
123// signedChars it reproduces git's version 1 behaviour on platforms where
124// char is signed (x86): every byte >= 0x80, in full blocks and in the tail, is
125// sign-extended before being shifted and OR-ed, which corrupts the bits of
126// the neighbouring bytes of the block.
127func murmur3Seeded(seed uint32, data []byte, signedChars bool) uint32 {
128 const (
129 c1 = 0xcc9e2d51
130 c2 = 0x1b873593
131 )
132 ext := func(b byte) uint32 {
133 if signedChars {
134 return uint32(int32(int8(b)))
135 }
136 return uint32(b)
137 }
138 n4 := len(data) / 4
139 for i := 0; i < n4; i++ {
140 d := data[4*i : 4*i+4]
141 k := ext(d[0]) | ext(d[1])<<8 | ext(d[2])<<16 | ext(d[3])<<24
142 k *= c1
143 k = rotl32(k, 15)
144 k *= c2
145 seed ^= k
146 seed = rotl32(seed, 13)*5 + 0xe6546b64
147 }
148 tail := data[4*n4:]
149 var k uint32
150 switch len(tail) {
151 case 3:
152 k ^= ext(tail[2]) << 16
153 fallthrough
154 case 2:
155 k ^= ext(tail[1]) << 8
156 fallthrough
157 case 1:
158 k ^= ext(tail[0])
159 k *= c1
160 k = rotl32(k, 15)
161 k *= c2
162 seed ^= k
163 }
164 seed ^= uint32(len(data))
165 seed ^= seed >> 16
166 seed *= 0x85ebca6b
167 seed ^= seed >> 13
168 seed *= 0xc2b2ae35
169 seed ^= seed >> 16
170 return seed
171}
172
173// bloomFilter returns the filter bytes of the commit at pos. ok is false when
174// the layer has no usable Bloom data, or the filter is empty, truncated or
175// the "too many changes" marker.
176func (g *commitGraph) bloomFilter(pos uint32) (l *graphLayer, filter []byte, ok bool) {
177 l, idx := g.layerOf(pos)
178 if l == nil || !l.hasBloom {
179 return nil, nil, false
180 }
181 var start uint32
182 if idx > 0 {
183 start = binary.BigEndian.Uint32(l.bidx[(idx-1)*4:])
184 }
185 end := binary.BigEndian.Uint32(l.bidx[idx*4:])
186 data := l.bdat[bloomHeaderSize:]
187 if end <= start || uint64(end) > uint64(len(data)) {
188 return l, nil, false
189 }
190 filter = data[start:end]
191 if len(filter) == 1 && filter[0] == 0xff {
192 return l, nil, false
193 }
194 return l, filter, true
195}
196
197// maybeChangedKey reports whether the path of k may have changed in the
198// commit at pos relative to its first parent. maybe=false is definitive (the
199// path did not change); maybe=true may be a false positive. ok=false means
200// the answer is unknown (unusable key, no filter, too large, truncated, bad
201// position) and the caller must diff the trees.
202func (g *commitGraph) maybeChangedKey(pos uint32, k *bloomKey) (maybe, ok bool) {
203 if !k.usable {
204 return false, false
205 }
206 l, f, ok := g.bloomFilter(pos)
207 if !ok {
208 return false, false
209 }
210 if l.bloomVersion != 1 {
211 return bloomContains(f, l.bloomHashes, &k.v2), true
212 }
213 // Version 1: written with signed or unsigned chars depending on the
214 // platform of the writer; accept either when they differ.
215 if bloomContains(f, l.bloomHashes, &k.v1) {
216 return true, true
217 }
218 return k.high && bloomContains(f, l.bloomHashes, &k.v2), true
219}
220
221// bloomContains tests the probes of hash pair h against filter f.
222func bloomContains(f []byte, hashes uint32, h *[2]uint32) bool {
223 mod := uint64(len(f)) * 8
224 h0, h1 := h[0], h[1]
225 for i := uint32(0); i < hashes; i++ {
226 bit := uint64(h0+i*h1) % mod
227 if f[bit>>3]&(1<<(bit&7)) == 0 {
228 return false
229 }
230 }
231 return true
232}
233
234// maybeChanged is maybeChangedKey for a path given as bytes, without a
235// trailing slash (one is tolerated), relative to the repository root. Use newBloomKey when
236// testing the same path against many commits.
237func (g *commitGraph) maybeChanged(pos uint32, path []byte) (maybe, ok bool) {
238 k := newBloomKey(path)
239 return g.maybeChangedKey(pos, &k)
240}
241
242// hasBloom reports whether the commit at pos has a usable changed-path
243// filter.
244func (g *commitGraph) hasBloom(pos uint32) bool {
245 _, _, ok := g.bloomFilter(pos)
246 return ok
247}