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