teach git-unpack-objects about deltas with offset to base
[git/git.git] / index-pack.c
CommitLineData
9cf6d335
SV
1#include "cache.h"
2#include "delta.h"
3#include "pack.h"
4#include "csum-file.h"
8e440259
PE
5#include "blob.h"
6#include "commit.h"
7#include "tag.h"
8#include "tree.h"
9cf6d335
SV
9
10static const char index_pack_usage[] =
11"git-index-pack [-o index-file] pack-file";
12
13struct object_entry
14{
15 unsigned long offset;
16 enum object_type type;
17 enum object_type real_type;
18 unsigned char sha1[20];
19};
20
21struct delta_entry
22{
23 struct object_entry *obj;
24 unsigned char base_sha1[20];
25};
26
27static const char *pack_name;
28static unsigned char *pack_base;
29static unsigned long pack_size;
30static struct object_entry *objects;
31static struct delta_entry *deltas;
32static int nr_objects;
33static int nr_deltas;
34
35static void open_pack_file(void)
36{
37 int fd;
38 struct stat st;
39
40 fd = open(pack_name, O_RDONLY);
41 if (fd < 0)
42 die("cannot open packfile '%s': %s", pack_name,
43 strerror(errno));
44 if (fstat(fd, &st)) {
45 int err = errno;
46 close(fd);
47 die("cannot fstat packfile '%s': %s", pack_name,
48 strerror(err));
49 }
50 pack_size = st.st_size;
51 pack_base = mmap(NULL, pack_size, PROT_READ, MAP_PRIVATE, fd, 0);
52 if (pack_base == MAP_FAILED) {
53 int err = errno;
54 close(fd);
55 die("cannot mmap packfile '%s': %s", pack_name,
56 strerror(err));
57 }
58 close(fd);
59}
60
61static void parse_pack_header(void)
62{
63 const struct pack_header *hdr;
64 unsigned char sha1[20];
65 SHA_CTX ctx;
66
67 /* Ensure there are enough bytes for the header and final SHA1 */
68 if (pack_size < sizeof(struct pack_header) + 20)
69 die("packfile '%s' is too small", pack_name);
70
71 /* Header consistency check */
72 hdr = (void *)pack_base;
73 if (hdr->hdr_signature != htonl(PACK_SIGNATURE))
74 die("packfile '%s' signature mismatch", pack_name);
d60fc1c8
NP
75 if (!pack_version_ok(hdr->hdr_version))
76 die("packfile '%s' version %d unsupported",
77 pack_name, ntohl(hdr->hdr_version));
9cf6d335
SV
78
79 nr_objects = ntohl(hdr->hdr_entries);
80
81 /* Check packfile integrity */
82 SHA1_Init(&ctx);
83 SHA1_Update(&ctx, pack_base, pack_size - 20);
84 SHA1_Final(sha1, &ctx);
a89fccd2 85 if (hashcmp(sha1, pack_base + pack_size - 20))
9cf6d335
SV
86 die("packfile '%s' SHA1 mismatch", pack_name);
87}
88
89static void bad_object(unsigned long offset, const char *format,
90 ...) NORETURN __attribute__((format (printf, 2, 3)));
91
92static void bad_object(unsigned long offset, const char *format, ...)
93{
94 va_list params;
95 char buf[1024];
96
97 va_start(params, format);
98 vsnprintf(buf, sizeof(buf), format, params);
99 va_end(params);
100 die("packfile '%s': bad object at offset %lu: %s",
101 pack_name, offset, buf);
102}
103
104static void *unpack_entry_data(unsigned long offset,
105 unsigned long *current_pos, unsigned long size)
106{
107 unsigned long pack_limit = pack_size - 20;
108 unsigned long pos = *current_pos;
109 z_stream stream;
110 void *buf = xmalloc(size);
111
112 memset(&stream, 0, sizeof(stream));
113 stream.next_out = buf;
114 stream.avail_out = size;
115 stream.next_in = pack_base + pos;
116 stream.avail_in = pack_limit - pos;
117 inflateInit(&stream);
118
119 for (;;) {
120 int ret = inflate(&stream, 0);
121 if (ret == Z_STREAM_END)
122 break;
123 if (ret != Z_OK)
124 bad_object(offset, "inflate returned %d", ret);
125 }
126 inflateEnd(&stream);
127 if (stream.total_out != size)
128 bad_object(offset, "size mismatch (expected %lu, got %lu)",
129 size, stream.total_out);
130 *current_pos = pack_limit - stream.avail_in;
131 return buf;
132}
133
134static void *unpack_raw_entry(unsigned long offset,
135 enum object_type *obj_type,
136 unsigned long *obj_size,
137 unsigned char *delta_base,
138 unsigned long *next_obj_offset)
139{
140 unsigned long pack_limit = pack_size - 20;
141 unsigned long pos = offset;
142 unsigned char c;
143 unsigned long size;
144 unsigned shift;
145 enum object_type type;
146 void *data;
147
148 c = pack_base[pos++];
149 type = (c >> 4) & 7;
150 size = (c & 15);
151 shift = 4;
152 while (c & 0x80) {
153 if (pos >= pack_limit)
154 bad_object(offset, "object extends past end of pack");
155 c = pack_base[pos++];
156 size += (c & 0x7fUL) << shift;
157 shift += 7;
158 }
159
160 switch (type) {
eb32d236 161 case OBJ_REF_DELTA:
9cf6d335
SV
162 if (pos + 20 >= pack_limit)
163 bad_object(offset, "object extends past end of pack");
e702496e 164 hashcpy(delta_base, pack_base + pos);
9cf6d335
SV
165 pos += 20;
166 /* fallthru */
167 case OBJ_COMMIT:
168 case OBJ_TREE:
169 case OBJ_BLOB:
170 case OBJ_TAG:
171 data = unpack_entry_data(offset, &pos, size);
172 break;
173 default:
174 bad_object(offset, "bad object type %d", type);
175 }
176
177 *obj_type = type;
178 *obj_size = size;
179 *next_obj_offset = pos;
180 return data;
181}
182
183static int find_delta(const unsigned char *base_sha1)
184{
185 int first = 0, last = nr_deltas;
186
187 while (first < last) {
188 int next = (first + last) / 2;
189 struct delta_entry *delta = &deltas[next];
190 int cmp;
191
a89fccd2 192 cmp = hashcmp(base_sha1, delta->base_sha1);
9cf6d335
SV
193 if (!cmp)
194 return next;
195 if (cmp < 0) {
196 last = next;
197 continue;
198 }
199 first = next+1;
200 }
201 return -first-1;
202}
203
204static int find_deltas_based_on_sha1(const unsigned char *base_sha1,
205 int *first_index, int *last_index)
206{
207 int first = find_delta(base_sha1);
208 int last = first;
209 int end = nr_deltas - 1;
210
211 if (first < 0)
212 return -1;
a89fccd2 213 while (first > 0 && !hashcmp(deltas[first - 1].base_sha1, base_sha1))
9cf6d335 214 --first;
a89fccd2 215 while (last < end && !hashcmp(deltas[last + 1].base_sha1, base_sha1))
9cf6d335
SV
216 ++last;
217 *first_index = first;
218 *last_index = last;
219 return 0;
220}
221
222static void sha1_object(const void *data, unsigned long size,
223 enum object_type type, unsigned char *sha1)
224{
225 SHA_CTX ctx;
226 char header[50];
227 int header_size;
228 const char *type_str;
229
230 switch (type) {
8e440259
PE
231 case OBJ_COMMIT: type_str = commit_type; break;
232 case OBJ_TREE: type_str = tree_type; break;
233 case OBJ_BLOB: type_str = blob_type; break;
234 case OBJ_TAG: type_str = tag_type; break;
9cf6d335
SV
235 default:
236 die("bad type %d", type);
237 }
238
239 header_size = sprintf(header, "%s %lu", type_str, size) + 1;
240
241 SHA1_Init(&ctx);
242 SHA1_Update(&ctx, header, header_size);
243 SHA1_Update(&ctx, data, size);
244 SHA1_Final(sha1, &ctx);
245}
246
247static void resolve_delta(struct delta_entry *delta, void *base_data,
248 unsigned long base_size, enum object_type type)
249{
250 struct object_entry *obj = delta->obj;
251 void *delta_data;
252 unsigned long delta_size;
253 void *result;
254 unsigned long result_size;
255 enum object_type delta_type;
256 unsigned char base_sha1[20];
257 unsigned long next_obj_offset;
258 int j, first, last;
259
260 obj->real_type = type;
261 delta_data = unpack_raw_entry(obj->offset, &delta_type,
262 &delta_size, base_sha1,
263 &next_obj_offset);
264 result = patch_delta(base_data, base_size, delta_data, delta_size,
265 &result_size);
266 free(delta_data);
267 if (!result)
268 bad_object(obj->offset, "failed to apply delta");
269 sha1_object(result, result_size, type, obj->sha1);
270 if (!find_deltas_based_on_sha1(obj->sha1, &first, &last)) {
271 for (j = first; j <= last; j++)
272 resolve_delta(&deltas[j], result, result_size, type);
273 }
274 free(result);
275}
276
277static int compare_delta_entry(const void *a, const void *b)
278{
279 const struct delta_entry *delta_a = a;
280 const struct delta_entry *delta_b = b;
a89fccd2 281 return hashcmp(delta_a->base_sha1, delta_b->base_sha1);
9cf6d335
SV
282}
283
284static void parse_pack_objects(void)
285{
286 int i;
287 unsigned long offset = sizeof(struct pack_header);
288 unsigned char base_sha1[20];
289 void *data;
290 unsigned long data_size;
291
292 /*
293 * First pass:
294 * - find locations of all objects;
295 * - calculate SHA1 of all non-delta objects;
296 * - remember base SHA1 for all deltas.
297 */
298 for (i = 0; i < nr_objects; i++) {
299 struct object_entry *obj = &objects[i];
300 obj->offset = offset;
301 data = unpack_raw_entry(offset, &obj->type, &data_size,
302 base_sha1, &offset);
303 obj->real_type = obj->type;
eb32d236 304 if (obj->type == OBJ_REF_DELTA) {
9cf6d335
SV
305 struct delta_entry *delta = &deltas[nr_deltas++];
306 delta->obj = obj;
e702496e 307 hashcpy(delta->base_sha1, base_sha1);
9cf6d335
SV
308 } else
309 sha1_object(data, data_size, obj->type, obj->sha1);
310 free(data);
311 }
312 if (offset != pack_size - 20)
313 die("packfile '%s' has junk at the end", pack_name);
314
315 /* Sort deltas by base SHA1 for fast searching */
316 qsort(deltas, nr_deltas, sizeof(struct delta_entry),
317 compare_delta_entry);
318
319 /*
320 * Second pass:
321 * - for all non-delta objects, look if it is used as a base for
322 * deltas;
323 * - if used as a base, uncompress the object and apply all deltas,
324 * recursively checking if the resulting object is used as a base
325 * for some more deltas.
326 */
327 for (i = 0; i < nr_objects; i++) {
328 struct object_entry *obj = &objects[i];
329 int j, first, last;
330
eb32d236 331 if (obj->type == OBJ_REF_DELTA)
9cf6d335
SV
332 continue;
333 if (find_deltas_based_on_sha1(obj->sha1, &first, &last))
334 continue;
335 data = unpack_raw_entry(obj->offset, &obj->type, &data_size,
336 base_sha1, &offset);
337 for (j = first; j <= last; j++)
338 resolve_delta(&deltas[j], data, data_size, obj->type);
339 free(data);
340 }
341
342 /* Check for unresolved deltas */
343 for (i = 0; i < nr_deltas; i++) {
eb32d236 344 if (deltas[i].obj->real_type == OBJ_REF_DELTA)
9cf6d335
SV
345 die("packfile '%s' has unresolved deltas", pack_name);
346 }
347}
348
349static int sha1_compare(const void *_a, const void *_b)
350{
351 struct object_entry *a = *(struct object_entry **)_a;
352 struct object_entry *b = *(struct object_entry **)_b;
a89fccd2 353 return hashcmp(a->sha1, b->sha1);
9cf6d335
SV
354}
355
84c8d8ae 356static void write_index_file(const char *index_name, unsigned char *sha1)
9cf6d335
SV
357{
358 struct sha1file *f;
7e4a2a84 359 struct object_entry **sorted_by_sha, **list, **last;
9cf6d335
SV
360 unsigned int array[256];
361 int i;
84c8d8ae 362 SHA_CTX ctx;
9cf6d335 363
7e4a2a84
JH
364 if (nr_objects) {
365 sorted_by_sha =
366 xcalloc(nr_objects, sizeof(struct object_entry *));
367 list = sorted_by_sha;
368 last = sorted_by_sha + nr_objects;
369 for (i = 0; i < nr_objects; ++i)
370 sorted_by_sha[i] = &objects[i];
371 qsort(sorted_by_sha, nr_objects, sizeof(sorted_by_sha[0]),
372 sha1_compare);
373
374 }
375 else
376 sorted_by_sha = list = last = NULL;
9cf6d335
SV
377
378 unlink(index_name);
379 f = sha1create("%s", index_name);
380
381 /*
382 * Write the first-level table (the list is sorted,
383 * but we use a 256-entry lookup to be able to avoid
384 * having to do eight extra binary search iterations).
385 */
386 for (i = 0; i < 256; i++) {
387 struct object_entry **next = list;
388 while (next < last) {
389 struct object_entry *obj = *next;
390 if (obj->sha1[0] != i)
391 break;
392 next++;
393 }
394 array[i] = htonl(next - sorted_by_sha);
395 list = next;
396 }
397 sha1write(f, array, 256 * sizeof(int));
398
84c8d8ae
JH
399 /* recompute the SHA1 hash of sorted object names.
400 * currently pack-objects does not do this, but that
401 * can be fixed.
402 */
403 SHA1_Init(&ctx);
9cf6d335
SV
404 /*
405 * Write the actual SHA1 entries..
406 */
407 list = sorted_by_sha;
408 for (i = 0; i < nr_objects; i++) {
409 struct object_entry *obj = *list++;
410 unsigned int offset = htonl(obj->offset);
411 sha1write(f, &offset, 4);
412 sha1write(f, obj->sha1, 20);
84c8d8ae 413 SHA1_Update(&ctx, obj->sha1, 20);
9cf6d335
SV
414 }
415 sha1write(f, pack_base + pack_size - 20, 20);
416 sha1close(f, NULL, 1);
417 free(sorted_by_sha);
84c8d8ae 418 SHA1_Final(sha1, &ctx);
9cf6d335
SV
419}
420
421int main(int argc, char **argv)
422{
423 int i;
424 char *index_name = NULL;
425 char *index_name_buf = NULL;
84c8d8ae 426 unsigned char sha1[20];
9cf6d335
SV
427
428 for (i = 1; i < argc; i++) {
429 const char *arg = argv[i];
430
431 if (*arg == '-') {
432 if (!strcmp(arg, "-o")) {
433 if (index_name || (i+1) >= argc)
434 usage(index_pack_usage);
435 index_name = argv[++i];
436 } else
437 usage(index_pack_usage);
438 continue;
439 }
440
441 if (pack_name)
442 usage(index_pack_usage);
443 pack_name = arg;
444 }
445
446 if (!pack_name)
447 usage(index_pack_usage);
448 if (!index_name) {
449 int len = strlen(pack_name);
5bb1cda5 450 if (!has_extension(pack_name, ".pack"))
9cf6d335
SV
451 die("packfile name '%s' does not end with '.pack'",
452 pack_name);
6689f087 453 index_name_buf = xmalloc(len);
9cf6d335
SV
454 memcpy(index_name_buf, pack_name, len - 5);
455 strcpy(index_name_buf + len - 5, ".idx");
456 index_name = index_name_buf;
457 }
458
459 open_pack_file();
460 parse_pack_header();
461 objects = xcalloc(nr_objects, sizeof(struct object_entry));
462 deltas = xcalloc(nr_objects, sizeof(struct delta_entry));
463 parse_pack_objects();
464 free(deltas);
84c8d8ae 465 write_index_file(index_name, sha1);
9cf6d335
SV
466 free(objects);
467 free(index_name_buf);
468
84c8d8ae
JH
469 printf("%s\n", sha1_to_hex(sha1));
470
9cf6d335
SV
471 return 0;
472}