Add git-index-pack utility
[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"
5
6static const char index_pack_usage[] =
7"git-index-pack [-o index-file] pack-file";
8
9struct 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
17struct delta_entry
18{
19 struct object_entry *obj;
20 unsigned char base_sha1[20];
21};
22
23static const char *pack_name;
24static unsigned char *pack_base;
25static unsigned long pack_size;
26static struct object_entry *objects;
27static struct delta_entry *deltas;
28static int nr_objects;
29static int nr_deltas;
30
31static 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
57static 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 (hdr->hdr_version != htonl(PACK_VERSION))
72 die("packfile '%s' version %d different from ours %d",
73 pack_name, ntohl(hdr->hdr_version), PACK_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
85static void bad_object(unsigned long offset, const char *format,
86 ...) NORETURN __attribute__((format (printf, 2, 3)));
87
88static 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
100static 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
130static 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
179static 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
200static 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
218static 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
243static 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
273static 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
280static 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
345static 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
352static void write_index_file(const char *index_name)
353{
354 struct sha1file *f;
355 struct object_entry **sorted_by_sha =
356 xcalloc(nr_objects, sizeof(struct object_entry *));
357 struct object_entry **list = sorted_by_sha;
358 struct object_entry **last = sorted_by_sha + nr_objects;
359 unsigned int array[256];
360 int i;
361
362 for (i = 0; i < nr_objects; ++i)
363 sorted_by_sha[i] = &objects[i];
364 qsort(sorted_by_sha, nr_objects, sizeof(sorted_by_sha[0]),
365 sha1_compare);
366
367 unlink(index_name);
368 f = sha1create("%s", index_name);
369
370 /*
371 * Write the first-level table (the list is sorted,
372 * but we use a 256-entry lookup to be able to avoid
373 * having to do eight extra binary search iterations).
374 */
375 for (i = 0; i < 256; i++) {
376 struct object_entry **next = list;
377 while (next < last) {
378 struct object_entry *obj = *next;
379 if (obj->sha1[0] != i)
380 break;
381 next++;
382 }
383 array[i] = htonl(next - sorted_by_sha);
384 list = next;
385 }
386 sha1write(f, array, 256 * sizeof(int));
387
388 /*
389 * Write the actual SHA1 entries..
390 */
391 list = sorted_by_sha;
392 for (i = 0; i < nr_objects; i++) {
393 struct object_entry *obj = *list++;
394 unsigned int offset = htonl(obj->offset);
395 sha1write(f, &offset, 4);
396 sha1write(f, obj->sha1, 20);
397 }
398 sha1write(f, pack_base + pack_size - 20, 20);
399 sha1close(f, NULL, 1);
400 free(sorted_by_sha);
401}
402
403int main(int argc, char **argv)
404{
405 int i;
406 char *index_name = NULL;
407 char *index_name_buf = NULL;
408
409 for (i = 1; i < argc; i++) {
410 const char *arg = argv[i];
411
412 if (*arg == '-') {
413 if (!strcmp(arg, "-o")) {
414 if (index_name || (i+1) >= argc)
415 usage(index_pack_usage);
416 index_name = argv[++i];
417 } else
418 usage(index_pack_usage);
419 continue;
420 }
421
422 if (pack_name)
423 usage(index_pack_usage);
424 pack_name = arg;
425 }
426
427 if (!pack_name)
428 usage(index_pack_usage);
429 if (!index_name) {
430 int len = strlen(pack_name);
431 if (len < 5 || strcmp(pack_name + len - 5, ".pack"))
432 die("packfile name '%s' does not end with '.pack'",
433 pack_name);
434 index_name_buf = xmalloc(len - 1);
435 memcpy(index_name_buf, pack_name, len - 5);
436 strcpy(index_name_buf + len - 5, ".idx");
437 index_name = index_name_buf;
438 }
439
440 open_pack_file();
441 parse_pack_header();
442 objects = xcalloc(nr_objects, sizeof(struct object_entry));
443 deltas = xcalloc(nr_objects, sizeof(struct delta_entry));
444 parse_pack_objects();
445 free(deltas);
446 write_index_file(index_name);
447 free(objects);
448 free(index_name_buf);
449
450 return 0;
451}