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