| blob | 7d9ec63e73c50c8413c2fdc7025265e9ab99241c |
1 require 'zlib'
2 require 'git/internal/mmap'
4 module Git module Internal
5 class PackFormatError < StandardError
6 end
8 class PackStorage
9 OBJ_OFS_DELTA = 6
10 OBJ_REF_DELTA = 7
12 FanOutCount = 256
13 SHA1Size = 20
14 IdxOffsetSize = 4
15 OffsetSize = 4
16 OffsetStart = FanOutCount * IdxOffsetSize
17 SHA1Start = OffsetStart + OffsetSize
18 EntrySize = OffsetSize + SHA1Size
20 def initialize(file)
21 if file =~ /\.idx$/
22 file = file[0...-3] + 'pack'
23 end
25 @name = file
26 @packfile = File.open(file)
27 @idxfile = File.open(file[0...-4]+'idx')
28 @idx = Mmap.new(@idxfile)
30 @offsets = [0]
31 FanOutCount.times do |i|
32 pos = @idx[i * IdxOffsetSize,IdxOffsetSize].unpack('N')[0]
33 if pos < @offsets[i]
34 raise PackFormatError, "pack #@name has discontinuous index #{i}"
35 end
36 @offsets << pos
37 end
39 @size = @offsets[-1]
40 end
42 def [](sha1)
43 offset = find_object(sha1)
44 return nil if !offset
45 return parse_object(offset)
46 end
48 def each_entry
49 pos = OffsetStart
50 @size.times do
51 offset = @idx[pos,OffsetSize].unpack('N')[0]
52 sha1 = @idx[pos+OffsetSize,SHA1Size]
53 pos += EntrySize
54 yield sha1, offset
55 end
56 end
58 def each_sha1
59 # unpacking the offset is quite expensive, so
60 # we avoid using #each
61 pos = SHA1Start
62 @size.times do
63 sha1 = @idx[pos,SHA1Size]
64 pos += EntrySize
65 yield sha1
66 end
67 end
69 def find_object(sha1)
70 slot = sha1[0]
71 first, last = @offsets[slot,2]
72 while first < last
73 mid = (first + last) / 2
74 midsha1 = @idx[SHA1Start + mid * EntrySize,SHA1Size]
75 cmp = midsha1 <=> sha1
77 if cmp < 0
78 first = mid + 1
79 elsif cmp > 0
80 last = mid
81 else
82 pos = OffsetStart + mid * EntrySize
83 offset = @idx[pos,OffsetSize].unpack('N')[0]
84 return offset
85 end
86 end
88 nil
89 end
90 private :find_object
92 def parse_object(offset)
93 data, type = unpack_object(offset)
94 RawObject.new(OBJ_TYPES[type], data)
95 end
96 protected :parse_object
98 def unpack_object(offset)
99 obj_offset = offset
100 @packfile.seek(offset)
102 c = @packfile.read(1)[0]
103 size = c & 0xf
104 type = (c >> 4) & 7
105 shift = 4
106 offset += 1
107 while c & 0x80 != 0
108 c = @packfile.read(1)[0]
109 size |= ((c & 0x7f) << shift)
110 shift += 7
111 offset += 1
112 end
114 case type
115 when OBJ_OFS_DELTA, OBJ_REF_DELTA
116 data, type = unpack_deltified(type, offset, obj_offset, size)
117 when OBJ_COMMIT, OBJ_TREE, OBJ_BLOB, OBJ_TAG
118 data = unpack_compressed(offset, size)
119 else
120 raise PackFormatError, "invalid type #{type}"
121 end
122 [data, type]
123 end
124 private :unpack_object
126 def unpack_deltified(type, offset, obj_offset, size)
127 @packfile.seek(offset)
128 data = @packfile.read(SHA1Size)
130 if type == OBJ_OFS_DELTA
131 i = 0
132 c = data[i]
133 base_offset = c & 0x7f
134 while c & 0x80 != 0
135 c = data[i += 1]
136 base_offset += 1
137 base_offset <<= 7
138 base_offset |= c & 0x7f
139 end
140 base_offset = obj_offset - base_offset
141 offset += i + 1
142 else
143 base_offset = find_object(data)
144 offset += SHA1Size
145 end
147 base, type = unpack_object(base_offset)
148 delta = unpack_compressed(offset, size)
149 [patch_delta(base, delta), type]
150 end
151 private :unpack_deltified
153 def unpack_compressed(offset, destsize)
154 outdata = ""
155 @packfile.seek(offset)
156 zstr = Zlib::Inflate.new
157 while outdata.size < destsize
158 indata = @packfile.read(4096)
159 if indata.size == 0
160 raise PackFormatError, 'error reading pack data'
161 end
162 outdata += zstr.inflate(indata)
163 end
164 if outdata.size > destsize
165 raise PackFormatError, 'error reading pack data'
166 end
167 zstr.close
168 outdata
169 end
170 private :unpack_compressed
172 def patch_delta(base, delta)
173 src_size, pos = patch_delta_header_size(delta, 0)
174 if src_size != base.size
175 raise PackFormatError, 'invalid delta data'
176 end
178 dest_size, pos = patch_delta_header_size(delta, pos)
179 dest = ""
180 while pos < delta.size
181 c = delta[pos]
182 pos += 1
183 if c & 0x80 != 0
184 pos -= 1
185 cp_off = cp_size = 0
186 cp_off = delta[pos += 1] if c & 0x01 != 0
187 cp_off |= delta[pos += 1] << 8 if c & 0x02 != 0
188 cp_off |= delta[pos += 1] << 16 if c & 0x04 != 0
189 cp_off |= delta[pos += 1] << 24 if c & 0x08 != 0
190 cp_size = delta[pos += 1] if c & 0x10 != 0
191 cp_size |= delta[pos += 1] << 8 if c & 0x20 != 0
192 cp_size |= delta[pos += 1] << 16 if c & 0x40 != 0
193 cp_size = 0x10000 if cp_size == 0
194 pos += 1
195 dest += base[cp_off,cp_size]
196 elsif c != 0
197 dest += delta[pos,c]
198 pos += c
199 else
200 raise PackFormatError, 'invalid delta data'
201 end
202 end
203 dest
204 end
205 private :patch_delta
207 def patch_delta_header_size(delta, pos)
208 size = 0
209 shift = 0
210 begin
211 c = delta[pos]
212 if c == nil
213 raise PackFormatError, 'invalid delta header'
214 end
215 pos += 1
216 size |= (c & 0x7f) << shift
217 shift += 7
218 end while c & 0x80 != 0
219 [size, pos]
220 end
221 private :patch_delta_header_size
222 end
223 end end
225 if $0 == __FILE__
226 p = Git::Internal::PackStorage.new(ARGV[0])
228 if ARGV.length == 1
229 p.each_sha1 do |sha1|
230 puts sha1.unpack('H*')
231 end
232 end
234 ARGV[1..-1].each do |sha1|
235 sha1 = [sha1].pack('H*')
236 puts p[sha1]
237 end
238 end