Merge branch 'jc/bindiff' into next
[git] / index-pack.c
1 #include "cache.h"
2 #include "delta.h"
3 #include "pack.h"
4 #include "csum-file.h"
5 #include "blob.h"
6 #include "commit.h"
7 #include "tag.h"
8 #include "tree.h"
9
10 static const char index_pack_usage[] =
11 "git-index-pack [-o index-file] pack-file";
12
13 struct 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
21 struct delta_entry
22 {
23         struct object_entry *obj;
24         unsigned char base_sha1[20];
25 };
26
27 static const char *pack_name;
28 static unsigned char *pack_base;
29 static unsigned long pack_size;
30 static struct object_entry *objects;
31 static struct delta_entry *deltas;
32 static int nr_objects;
33 static int nr_deltas;
34
35 static 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
61 static 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);
75         if (!pack_version_ok(hdr->hdr_version))
76                 die("packfile '%s' version %d unsupported",
77                     pack_name, ntohl(hdr->hdr_version));
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);
85         if (memcmp(sha1, pack_base + pack_size - 20, 20))
86                 die("packfile '%s' SHA1 mismatch", pack_name);
87 }
88
89 static void bad_object(unsigned long offset, const char *format,
90                        ...) NORETURN __attribute__((format (printf, 2, 3)));
91
92 static 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
104 static 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
134 static 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) {
161         case OBJ_DELTA:
162                 if (pos + 20 >= pack_limit)
163                         bad_object(offset, "object extends past end of pack");
164                 memcpy(delta_base, pack_base + pos, 20);
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
183 static 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
192                 cmp = memcmp(base_sha1, delta->base_sha1, 20);
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
204 static 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;
213         while (first > 0 && !memcmp(deltas[first-1].base_sha1, base_sha1, 20))
214                 --first;
215         while (last < end && !memcmp(deltas[last+1].base_sha1, base_sha1, 20))
216                 ++last;
217         *first_index = first;
218         *last_index = last;
219         return 0;
220 }
221
222 static 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) {
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;
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
247 static 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
277 static 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;
281         return memcmp(delta_a->base_sha1, delta_b->base_sha1, 20);
282 }
283
284 static 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;
304                 if (obj->type == OBJ_DELTA) {
305                         struct delta_entry *delta = &deltas[nr_deltas++];
306                         delta->obj = obj;
307                         memcpy(delta->base_sha1, base_sha1, 20);
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
331                 if (obj->type == OBJ_DELTA)
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++) {
344                 if (deltas[i].obj->real_type == OBJ_DELTA)
345                         die("packfile '%s' has unresolved deltas",  pack_name);
346         }
347 }
348
349 static 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;
353         return memcmp(a->sha1, b->sha1, 20);
354 }
355
356 static void write_index_file(const char *index_name, unsigned char *sha1)
357 {
358         struct sha1file *f;
359         struct object_entry **sorted_by_sha, **list, **last;
360         unsigned int array[256];
361         int i;
362         SHA_CTX ctx;
363
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;
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
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);
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);
413                 SHA1_Update(&ctx, obj->sha1, 20);
414         }
415         sha1write(f, pack_base + pack_size - 20, 20);
416         sha1close(f, NULL, 1);
417         free(sorted_by_sha);
418         SHA1_Final(sha1, &ctx);
419 }
420
421 int main(int argc, char **argv)
422 {
423         int i;
424         char *index_name = NULL;
425         char *index_name_buf = NULL;
426         unsigned char sha1[20];
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);
450                 if (len < 5 || strcmp(pack_name + len - 5, ".pack"))
451                         die("packfile name '%s' does not end with '.pack'",
452                             pack_name);
453                 index_name_buf = xmalloc(len);
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);
465         write_index_file(index_name, sha1);
466         free(objects);
467         free(index_name_buf);
468
469         printf("%s\n", sha1_to_hex(sha1));
470
471         return 0;
472 }