1// SPDX-License-Identifier: MIT
2
3package git
4
5import (
6 "bytes"
7 "encoding/binary"
8)
9
10// idxFile is a validated, read-only pack index (version 2) held in memory.
11type idxFile struct {
12 data []byte
13 n uint32
14 fanout [256]uint32
15 names []byte // n*20 sorted object ids
16 offs []byte // n*4 offsets
17 large []byte // 8 byte offsets
18 packHash []byte // 20 bytes: the checksum of the pack file
19}
20
21const (
22 idxHeaderLen = 8
23 idxFanoutLen = 256 * 4
24 idxTrailer = 40
25)
26
27var idxMagic = []byte{0xff, 't', 'O', 'c'}
28
29// parseIdx validates the layout of a v2 index: sizes, fan-out monotony and
30// the large offset table. It does not verify the checksums.
31func parseIdx(data []byte) (*idxFile, error) {
32 if len(data) < idxHeaderLen+idxFanoutLen+idxTrailer {
33 return nil, corrupt("idx: file too short (%d bytes)", len(data))
34 }
35 if !bytes.Equal(data[:4], idxMagic) {
36 return nil, unsupported("idx: version 1 index")
37 }
38 if v := binary.BigEndian.Uint32(data[4:8]); v != 2 {
39 return nil, unsupported("idx: version %d", v)
40 }
41 x := &idxFile{data: data}
42 prev := uint32(0)
43 for i := range x.fanout {
44 v := binary.BigEndian.Uint32(data[idxHeaderLen+4*i:])
45 if v < prev {
46 return nil, corrupt("idx: fan-out decreases at %#02x", i)
47 }
48 x.fanout[i] = v
49 prev = v
50 }
51 x.n = prev
52 n := uint64(x.n)
53 fixed := uint64(idxHeaderLen+idxFanoutLen) + n*28 + idxTrailer
54 if uint64(len(data)) < fixed {
55 return nil, corrupt("idx: %d objects do not fit in %d bytes", n, len(data))
56 }
57 extra := uint64(len(data)) - fixed
58 if extra%8 != 0 {
59 return nil, corrupt("idx: large offset table of %d bytes", extra)
60 }
61 p := uint64(idxHeaderLen + idxFanoutLen)
62 x.names = data[p : p+n*20]
63 p += n * 20
64 p += n * 4 // crc32
65 x.offs = data[p : p+n*4]
66 p += n * 4
67 x.large = data[p : p+extra]
68 p += extra
69 x.packHash = data[p : p+20]
70 return x, nil
71}
72
73// id returns the id at position i.
74func (x *idxFile) id(i uint32) []byte { return x.names[uint64(i)*20 : uint64(i)*20+20] }
75
76// find returns the position of id.
77func (x *idxFile) find(id *ObjectID) (uint32, bool) {
78 lo, hi := x.bounds(id[0])
79 pos := x.lowerBound(id[:], lo, hi)
80 if pos < hi && bytes.Equal(x.id(pos), id[:]) {
81 return pos, true
82 }
83 return 0, false
84}
85
86// bounds returns the range of positions whose first byte is b.
87func (x *idxFile) bounds(b byte) (lo, hi uint32) {
88 if b > 0 {
89 lo = x.fanout[b-1]
90 }
91 return lo, x.fanout[b]
92}
93
94// lowerBound returns the first position in [lo, hi) whose id is not less
95// than key, comparing len(key) bytes.
96func (x *idxFile) lowerBound(key []byte, lo, hi uint32) uint32 {
97 for lo < hi {
98 mid := lo + (hi-lo)/2
99 if bytes.Compare(x.id(mid)[:len(key)], key) < 0 {
100 lo = mid + 1
101 } else {
102 hi = mid
103 }
104 }
105 return lo
106}
107
108// offset returns the offset in the pack of the object at position i.
109func (x *idxFile) offset(i uint32) (uint64, error) {
110 v := binary.BigEndian.Uint32(x.offs[uint64(i)*4:])
111 if v&0x80000000 == 0 {
112 return uint64(v), nil
113 }
114 k := uint64(v & 0x7fffffff)
115 if (k+1)*8 > uint64(len(x.large)) {
116 return 0, corrupt("idx: large offset %d out of %d", k, len(x.large)/8)
117 }
118 return binary.BigEndian.Uint64(x.large[k*8:]), nil
119}
120
121// prefixMatches calls fn with each id that starts with the nibble prefix
122// (nibbles hex digits, packed two per byte in key), stopping when fn returns
123// false.
124func (x *idxFile) prefixMatches(key []byte, nibbles int, fn func(id ObjectID) bool) {
125 var lo, hi uint32
126 var first, last byte
127 whole := nibbles / 2
128 first, last = key[0], key[0]
129 if nibbles == 1 {
130 first, last = key[0]&0xf0, key[0]|0x0f
131 }
132 lo, _ = x.bounds(first)
133 _, hi = x.bounds(last)
134 var pad [20]byte
135 copy(pad[:], key[:(nibbles+1)/2])
136 if nibbles%2 == 1 {
137 pad[whole] &= 0xf0
138 }
139 pos := x.lowerBound(pad[:(nibbles+1)/2], lo, hi)
140 for ; pos < hi; pos++ {
141 id := x.id(pos)
142 if !hasNibblePrefix(id, key, nibbles) {
143 return
144 }
145 var o ObjectID
146 copy(o[:], id)
147 if !fn(o) {
148 return
149 }
150 }
151}
152
153// hasNibblePrefix reports whether id starts with the first n hex digits
154// encoded in key.
155func hasNibblePrefix(id, key []byte, n int) bool {
156 whole := n / 2
157 if !bytes.Equal(id[:whole], key[:whole]) {
158 return false
159 }
160 if n%2 == 1 {
161 return id[whole]&0xf0 == key[whole]&0xf0
162 }
163 return true
164}