10 static const char index_pack_usage
[] =
11 "git-index-pack [-o index-file] pack-file";
16 enum object_type type
;
17 enum object_type real_type
;
18 unsigned char sha1
[20];
22 unsigned char sha1
[20];
27 * Even if sizeof(union delta_base) == 24 on 64-bit archs, we really want
28 * to memcmp() only the first 20 bytes.
30 #define UNION_BASE_SZ 20
34 struct object_entry
*obj
;
35 union delta_base base
;
38 static const char *pack_name
;
39 static unsigned char *pack_base
;
40 static unsigned long pack_size
;
41 static struct object_entry
*objects
;
42 static struct delta_entry
*deltas
;
43 static int nr_objects
;
46 static void open_pack_file(void)
51 fd
= open(pack_name
, O_RDONLY
);
53 die("cannot open packfile '%s': %s", pack_name
,
58 die("cannot fstat packfile '%s': %s", pack_name
,
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
) {
66 die("cannot mmap packfile '%s': %s", pack_name
,
72 static void parse_pack_header(void)
74 const struct pack_header
*hdr
;
75 unsigned char sha1
[20];
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
);
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
);
86 if (!pack_version_ok(hdr
->hdr_version
))
87 die("packfile '%s' version %d unsupported",
88 pack_name
, ntohl(hdr
->hdr_version
));
90 nr_objects
= ntohl(hdr
->hdr_entries
);
92 /* Check packfile integrity */
94 SHA1_Update(&ctx
, pack_base
, pack_size
- 20);
95 SHA1_Final(sha1
, &ctx
);
96 if (hashcmp(sha1
, pack_base
+ pack_size
- 20))
97 die("packfile '%s' SHA1 mismatch", pack_name
);
100 static void bad_object(unsigned long offset
, const char *format
,
101 ...) NORETURN
__attribute__((format (printf
, 2, 3)));
103 static void bad_object(unsigned long offset
, const char *format
, ...)
108 va_start(params
, format
);
109 vsnprintf(buf
, sizeof(buf
), format
, params
);
111 die("packfile '%s': bad object at offset %lu: %s",
112 pack_name
, offset
, buf
);
115 static void *unpack_entry_data(unsigned long offset
,
116 unsigned long *current_pos
, unsigned long size
)
118 unsigned long pack_limit
= pack_size
- 20;
119 unsigned long pos
= *current_pos
;
121 void *buf
= xmalloc(size
);
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
);
131 int ret
= inflate(&stream
, 0);
132 if (ret
== Z_STREAM_END
)
135 bad_object(offset
, "inflate returned %d", ret
);
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
;
145 static void *unpack_raw_entry(unsigned long offset
,
146 enum object_type
*obj_type
,
147 unsigned long *obj_size
,
148 union delta_base
*delta_base
,
149 unsigned long *next_obj_offset
)
151 unsigned long pack_limit
= pack_size
- 20;
152 unsigned long pos
= offset
;
154 unsigned long size
, base_offset
;
156 enum object_type type
;
159 c
= pack_base
[pos
++];
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
;
173 if (pos
+ 20 >= pack_limit
)
174 bad_object(offset
, "object extends past end of pack");
175 hashcpy(delta_base
->sha1
, pack_base
+ pos
);
179 memset(delta_base
, 0, sizeof(*delta_base
));
180 c
= pack_base
[pos
++];
181 base_offset
= c
& 127;
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);
191 delta_base
->offset
= offset
- base_offset
;
192 if (delta_base
->offset
>= offset
)
193 bad_object(offset
, "delta base offset is out of bound");
201 bad_object(offset
, "bad object type %d", type
);
204 data
= unpack_entry_data(offset
, &pos
, size
);
207 *next_obj_offset
= pos
;
211 static int find_delta(const union delta_base
*base
)
213 int first
= 0, last
= nr_deltas
;
215 while (first
< last
) {
216 int next
= (first
+ last
) / 2;
217 struct delta_entry
*delta
= &deltas
[next
];
220 cmp
= memcmp(base
, &delta
->base
, UNION_BASE_SZ
);
232 static int find_delta_childs(const union delta_base
*base
,
233 int *first_index
, int *last_index
)
235 int first
= find_delta(base
);
237 int end
= nr_deltas
- 1;
241 while (first
> 0 && !memcmp(&deltas
[first
- 1].base
, base
, UNION_BASE_SZ
))
243 while (last
< end
&& !memcmp(&deltas
[last
+ 1].base
, base
, UNION_BASE_SZ
))
245 *first_index
= first
;
250 static void sha1_object(const void *data
, unsigned long size
,
251 enum object_type type
, unsigned char *sha1
)
256 const char *type_str
;
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;
264 die("bad type %d", type
);
267 header_size
= sprintf(header
, "%s %lu", type_str
, size
) + 1;
270 SHA1_Update(&ctx
, header
, header_size
);
271 SHA1_Update(&ctx
, data
, size
);
272 SHA1_Final(sha1
, &ctx
);
275 static void resolve_delta(struct delta_entry
*delta
, void *base_data
,
276 unsigned long base_size
, enum object_type type
)
278 struct object_entry
*obj
= delta
->obj
;
280 unsigned long delta_size
;
282 unsigned long result_size
;
283 enum object_type delta_type
;
284 union delta_base delta_base
;
285 unsigned long next_obj_offset
;
288 obj
->real_type
= type
;
289 delta_data
= unpack_raw_entry(obj
->offset
, &delta_type
,
290 &delta_size
, &delta_base
,
292 result
= patch_delta(base_data
, base_size
, delta_data
, delta_size
,
296 bad_object(obj
->offset
, "failed to apply delta");
297 sha1_object(result
, result_size
, type
, obj
->sha1
);
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
);
306 memset(&delta_base
, 0, sizeof(delta_base
));
307 delta_base
.offset
= obj
->offset
;
308 if (!find_delta_childs(&delta_base
, &first
, &last
)) {
309 for (j
= first
; j
<= last
; j
++)
310 if (deltas
[j
].obj
->type
== OBJ_OFS_DELTA
)
311 resolve_delta(&deltas
[j
], result
, result_size
, type
);
317 static int compare_delta_entry(const void *a
, const void *b
)
319 const struct delta_entry
*delta_a
= a
;
320 const struct delta_entry
*delta_b
= b
;
321 return memcmp(&delta_a
->base
, &delta_b
->base
, UNION_BASE_SZ
);
324 static void parse_pack_objects(void)
327 unsigned long offset
= sizeof(struct pack_header
);
328 struct delta_entry
*delta
= deltas
;
330 unsigned long data_size
;
334 * - find locations of all objects;
335 * - calculate SHA1 of all non-delta objects;
336 * - remember base SHA1 for all deltas.
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
,
342 &delta
->base
, &offset
);
343 obj
->real_type
= obj
->type
;
344 if (obj
->type
== OBJ_REF_DELTA
|| obj
->type
== OBJ_OFS_DELTA
) {
349 sha1_object(data
, data_size
, obj
->type
, obj
->sha1
);
352 if (offset
!= pack_size
- 20)
353 die("packfile '%s' has junk at the end", pack_name
);
355 /* Sort deltas by base SHA1/offset for fast searching */
356 qsort(deltas
, nr_deltas
, sizeof(struct delta_entry
),
357 compare_delta_entry
);
361 * - for all non-delta objects, look if it is used as a base for
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.
367 for (i
= 0; i
< nr_objects
; i
++) {
368 struct object_entry
*obj
= &objects
[i
];
369 union delta_base base
;
370 int j
, ref
, ref_first
, ref_last
, ofs
, ofs_first
, ofs_last
;
372 if (obj
->type
== OBJ_REF_DELTA
|| obj
->type
== OBJ_OFS_DELTA
)
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
);
381 data
= unpack_raw_entry(obj
->offset
, &obj
->type
, &data_size
,
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
);
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
);
396 /* Check for unresolved deltas */
397 for (i
= 0; i
< nr_deltas
; i
++) {
398 if (deltas
[i
].obj
->real_type
== OBJ_REF_DELTA
||
399 deltas
[i
].obj
->real_type
== OBJ_OFS_DELTA
)
400 die("packfile '%s' has unresolved deltas", pack_name
);
404 static int sha1_compare(const void *_a
, const void *_b
)
406 struct object_entry
*a
= *(struct object_entry
**)_a
;
407 struct object_entry
*b
= *(struct object_entry
**)_b
;
408 return hashcmp(a
->sha1
, b
->sha1
);
411 static void write_index_file(const char *index_name
, unsigned char *sha1
)
414 struct object_entry
**sorted_by_sha
, **list
, **last
;
415 unsigned int array
[256];
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]),
431 sorted_by_sha
= list
= last
= NULL
;
434 f
= sha1create("%s", index_name
);
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).
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
)
449 array
[i
] = htonl(next
- sorted_by_sha
);
452 sha1write(f
, array
, 256 * sizeof(int));
454 /* recompute the SHA1 hash of sorted object names.
455 * currently pack-objects does not do this, but that
460 * Write the actual SHA1 entries..
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);
468 SHA1_Update(&ctx
, obj
->sha1
, 20);
470 sha1write(f
, pack_base
+ pack_size
- 20, 20);
471 sha1close(f
, NULL
, 1);
473 SHA1_Final(sha1
, &ctx
);
476 int main(int argc
, char **argv
)
479 char *index_name
= NULL
;
480 char *index_name_buf
= NULL
;
481 unsigned char sha1
[20];
483 for (i
= 1; i
< argc
; i
++) {
484 const char *arg
= argv
[i
];
487 if (!strcmp(arg
, "-o")) {
488 if (index_name
|| (i
+1) >= argc
)
489 usage(index_pack_usage
);
490 index_name
= argv
[++i
];
492 usage(index_pack_usage
);
497 usage(index_pack_usage
);
502 usage(index_pack_usage
);
504 int len
= strlen(pack_name
);
505 if (!has_extension(pack_name
, ".pack"))
506 die("packfile name '%s' does not end with '.pack'",
508 index_name_buf
= xmalloc(len
);
509 memcpy(index_name_buf
, pack_name
, len
- 5);
510 strcpy(index_name_buf
+ len
- 5, ".idx");
511 index_name
= index_name_buf
;
516 objects
= xcalloc(nr_objects
, sizeof(struct object_entry
));
517 deltas
= xcalloc(nr_objects
, sizeof(struct delta_entry
));
518 parse_pack_objects();
520 write_index_file(index_name
, sha1
);
522 free(index_name_buf
);
524 printf("%s\n", sha1_to_hex(sha1
));