8 static const char pack_usage
[] = "git-pack-objects [--incremental] [--window=N] [--depth=N] {--stdout | base-name} < object-list";
11 unsigned char sha1
[20];
16 enum object_type type
;
17 unsigned long delta_size
;
18 struct object_entry
*delta
;
21 static int incremental
= 0;
22 static struct object_entry
**sorted_by_sha
, **sorted_by_type
;
23 static struct object_entry
*objects
= NULL
;
24 static int nr_objects
= 0, nr_alloc
= 0;
25 static const char *base_name
;
26 static unsigned char pack_file_sha1
[20];
28 static void *delta_against(void *buf
, unsigned long size
, struct object_entry
*entry
)
30 unsigned long othersize
, delta_size
;
32 void *otherbuf
= read_sha1_file(entry
->delta
->sha1
, type
, &othersize
);
36 die("unable to read %s", sha1_to_hex(entry
->delta
->sha1
));
37 delta_buf
= diff_delta(otherbuf
, othersize
,
38 buf
, size
, &delta_size
, 0);
39 if (!delta_buf
|| delta_size
!= entry
->delta_size
)
40 die("delta size changed");
47 * The per-object header is a pretty dense thing, which is
48 * - first byte: low four bits are "size", then three bits of "type",
49 * and the high bit is "size continues".
50 * - each byte afterwards: low seven bits are size continuation,
51 * with the high bit being "size continues"
53 static int encode_header(enum object_type type
, unsigned long size
, unsigned char *hdr
)
58 if (type
< OBJ_COMMIT
|| type
> OBJ_DELTA
)
59 die("bad type %d", type
);
61 c
= (type
<< 4) | (size
& 15);
73 static unsigned long write_object(struct sha1file
*f
, struct object_entry
*entry
)
77 void *buf
= read_sha1_file(entry
->sha1
, type
, &size
);
78 unsigned char header
[10];
79 unsigned hdrlen
, datalen
;
80 enum object_type obj_type
;
83 die("unable to read %s", sha1_to_hex(entry
->sha1
));
84 if (size
!= entry
->size
)
85 die("object %s size inconsistency (%lu vs %lu)", sha1_to_hex(entry
->sha1
), size
, entry
->size
);
88 * The object header is a byte of 'type' followed by zero or
89 * more bytes of length. For deltas, the 20 bytes of delta sha1
92 obj_type
= entry
->type
;
94 buf
= delta_against(buf
, size
, entry
);
95 size
= entry
->delta_size
;
98 hdrlen
= encode_header(obj_type
, size
, header
);
99 sha1write(f
, header
, hdrlen
);
101 sha1write(f
, entry
->delta
, 20);
104 datalen
= sha1write_compressed(f
, buf
, size
);
106 return hdrlen
+ datalen
;
109 static unsigned long write_one(struct sha1file
*f
,
110 struct object_entry
*e
,
111 unsigned long offset
)
114 /* offset starts from header size and cannot be zero
115 * if it is written already.
119 offset
+= write_object(f
, e
);
120 /* if we are delitified, write out its base object. */
122 offset
= write_one(f
, e
->delta
, offset
);
126 static void write_pack_file(void)
130 unsigned long offset
;
132 struct pack_header hdr
;
135 f
= sha1fd(1, "<stdout>");
137 f
= sha1create("%s.%s", base_name
, "pack");
138 hdr
.hdr_signature
= htonl(PACK_SIGNATURE
);
139 hdr
.hdr_version
= htonl(PACK_VERSION
);
140 hdr
.hdr_entries
= htonl(nr_objects
);
141 sha1write(f
, &hdr
, sizeof(hdr
));
142 offset
= sizeof(hdr
);
143 for (i
= 0; i
< nr_objects
; i
++)
144 offset
= write_one(f
, objects
+ i
, offset
);
146 sha1close(f
, pack_file_sha1
, 1);
151 static void write_index_file(void)
154 struct sha1file
*f
= sha1create("%s.%s", base_name
, "idx");
155 struct object_entry
**list
= sorted_by_sha
;
156 struct object_entry
**last
= list
+ nr_objects
;
157 unsigned int array
[256];
160 * Write the first-level table (the list is sorted,
161 * but we use a 256-entry lookup to be able to avoid
162 * having to do eight extra binary search iterations).
164 for (i
= 0; i
< 256; i
++) {
165 struct object_entry
**next
= list
;
166 while (next
< last
) {
167 struct object_entry
*entry
= *next
;
168 if (entry
->sha1
[0] != i
)
172 array
[i
] = htonl(next
- sorted_by_sha
);
175 sha1write(f
, array
, 256 * sizeof(int));
178 * Write the actual SHA1 entries..
180 list
= sorted_by_sha
;
181 for (i
= 0; i
< nr_objects
; i
++) {
182 struct object_entry
*entry
= *list
++;
183 unsigned int offset
= htonl(entry
->offset
);
184 sha1write(f
, &offset
, 4);
185 sha1write(f
, entry
->sha1
, 20);
187 sha1write(f
, pack_file_sha1
, 20);
188 sha1close(f
, NULL
, 1);
191 static void add_object_entry(unsigned char *sha1
, unsigned int hash
)
193 unsigned int idx
= nr_objects
;
194 struct object_entry
*entry
;
196 if (incremental
&& has_sha1_pack(sha1
))
199 if (idx
>= nr_alloc
) {
200 unsigned int needed
= (idx
+ 1024) * 3 / 2;
201 objects
= xrealloc(objects
, needed
* sizeof(*entry
));
204 entry
= objects
+ idx
;
205 memset(entry
, 0, sizeof(*entry
));
206 memcpy(entry
->sha1
, sha1
, 20);
211 static void check_object(struct object_entry
*entry
)
215 if (!sha1_object_info(entry
->sha1
, type
, &entry
->size
)) {
216 if (!strcmp(type
, "commit")) {
217 entry
->type
= OBJ_COMMIT
;
218 } else if (!strcmp(type
, "tree")) {
219 entry
->type
= OBJ_TREE
;
220 } else if (!strcmp(type
, "blob")) {
221 entry
->type
= OBJ_BLOB
;
222 } else if (!strcmp(type
, "tag")) {
223 entry
->type
= OBJ_TAG
;
225 die("unable to pack object %s of type %s",
226 sha1_to_hex(entry
->sha1
), type
);
229 die("unable to get type of object %s",
230 sha1_to_hex(entry
->sha1
));
233 static void get_object_details(void)
236 struct object_entry
*entry
= objects
;
238 for (i
= 0; i
< nr_objects
; i
++)
239 check_object(entry
++);
242 typedef int (*entry_sort_t
)(const struct object_entry
*, const struct object_entry
*);
244 static entry_sort_t current_sort
;
246 static int sort_comparator(const void *_a
, const void *_b
)
248 struct object_entry
*a
= *(struct object_entry
**)_a
;
249 struct object_entry
*b
= *(struct object_entry
**)_b
;
250 return current_sort(a
,b
);
253 static struct object_entry
**create_sorted_list(entry_sort_t sort
)
255 struct object_entry
**list
= xmalloc(nr_objects
* sizeof(struct object_entry
*));
258 for (i
= 0; i
< nr_objects
; i
++)
259 list
[i
] = objects
+ i
;
261 qsort(list
, nr_objects
, sizeof(struct object_entry
*), sort_comparator
);
265 static int sha1_sort(const struct object_entry
*a
, const struct object_entry
*b
)
267 return memcmp(a
->sha1
, b
->sha1
, 20);
270 static int type_size_sort(const struct object_entry
*a
, const struct object_entry
*b
)
272 if (a
->type
< b
->type
)
274 if (a
->type
> b
->type
)
276 if (a
->hash
< b
->hash
)
278 if (a
->hash
> b
->hash
)
280 if (a
->size
< b
->size
)
282 if (a
->size
> b
->size
)
284 return a
< b
? -1 : (a
> b
);
288 struct object_entry
*entry
;
293 * We search for deltas _backwards_ in a list sorted by type and
294 * by size, so that we see progressively smaller and smaller files.
295 * That's because we prefer deltas to be from the bigger file
296 * to the smaller - deletes are potentially cheaper, but perhaps
297 * more importantly, the bigger file is likely the more recent
300 static int try_delta(struct unpacked
*cur
, struct unpacked
*old
, unsigned max_depth
)
302 struct object_entry
*cur_entry
= cur
->entry
;
303 struct object_entry
*old_entry
= old
->entry
;
304 unsigned long size
, oldsize
, delta_size
, sizediff
;
308 /* Don't bother doing diffs between different types */
309 if (cur_entry
->type
!= old_entry
->type
)
312 size
= cur_entry
->size
;
315 oldsize
= old_entry
->size
;
316 sizediff
= oldsize
> size
? oldsize
- size
: size
- oldsize
;
317 if (sizediff
> size
/ 8)
319 if (old_entry
->depth
>= max_depth
)
325 * We always delta from the bigger to the smaller, since that's
326 * more space-efficient (deletes don't have to say _what_ they
329 max_size
= size
/ 2 - 20;
330 if (cur_entry
->delta
)
331 max_size
= cur_entry
->delta_size
-1;
332 if (sizediff
>= max_size
)
334 delta_buf
= diff_delta(old
->data
, oldsize
,
335 cur
->data
, size
, &delta_size
, max_size
);
338 cur_entry
->delta
= old_entry
;
339 cur_entry
->delta_size
= delta_size
;
340 cur_entry
->depth
= old_entry
->depth
+ 1;
345 static void find_deltas(struct object_entry
**list
, int window
, int depth
)
348 unsigned int array_size
= window
* sizeof(struct unpacked
);
349 struct unpacked
*array
= xmalloc(array_size
);
351 memset(array
, 0, array_size
);
355 struct object_entry
*entry
= list
[i
];
356 struct unpacked
*n
= array
+ idx
;
363 n
->data
= read_sha1_file(entry
->sha1
, type
, &size
);
364 if (size
!= entry
->size
)
365 die("object %s inconsistent object length (%lu vs %lu)", sha1_to_hex(entry
->sha1
), size
, entry
->size
);
368 unsigned int other_idx
= idx
+ j
;
370 if (other_idx
>= window
)
372 m
= array
+ other_idx
;
375 if (try_delta(n
, m
, depth
) < 0)
384 int main(int argc
, char **argv
)
386 char line
[PATH_MAX
+ 20];
387 int window
= 10, depth
= 10, pack_to_stdout
= 0;
390 for (i
= 1; i
< argc
; i
++) {
391 const char *arg
= argv
[i
];
394 if (!strcmp("--incremental", arg
)) {
398 if (!strncmp("--window=", arg
, 9)) {
400 window
= strtoul(arg
+9, &end
, 0);
405 if (!strncmp("--depth=", arg
, 8)) {
407 depth
= strtoul(arg
+8, &end
, 0);
412 if (!strcmp("--stdout", arg
)) {
423 if (pack_to_stdout
!= !base_name
)
426 while (fgets(line
, sizeof(line
), stdin
) != NULL
) {
429 unsigned char sha1
[20];
431 if (get_sha1_hex(line
, sha1
))
432 die("expected sha1, got garbage");
436 unsigned char c
= *p
++;
439 hash
= hash
* 11 + c
;
441 add_object_entry(sha1
, hash
);
443 get_object_details();
445 fprintf(stderr
, "Packing %d objects\n", nr_objects
);
447 sorted_by_sha
= create_sorted_list(sha1_sort
);
448 sorted_by_type
= create_sorted_list(type_size_sort
);
450 find_deltas(sorted_by_type
, window
+1, depth
);