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 non_empty
= 0;
22 static int incremental
= 0;
23 static struct object_entry
**sorted_by_sha
, **sorted_by_type
;
24 static struct object_entry
*objects
= NULL
;
25 static int nr_objects
= 0, nr_alloc
= 0;
26 static const char *base_name
;
27 static unsigned char pack_file_sha1
[20];
29 static void *delta_against(void *buf
, unsigned long size
, struct object_entry
*entry
)
31 unsigned long othersize
, delta_size
;
33 void *otherbuf
= read_sha1_file(entry
->delta
->sha1
, type
, &othersize
);
37 die("unable to read %s", sha1_to_hex(entry
->delta
->sha1
));
38 delta_buf
= diff_delta(otherbuf
, othersize
,
39 buf
, size
, &delta_size
, 0);
40 if (!delta_buf
|| delta_size
!= entry
->delta_size
)
41 die("delta size changed");
48 * The per-object header is a pretty dense thing, which is
49 * - first byte: low four bits are "size", then three bits of "type",
50 * and the high bit is "size continues".
51 * - each byte afterwards: low seven bits are size continuation,
52 * with the high bit being "size continues"
54 static int encode_header(enum object_type type
, unsigned long size
, unsigned char *hdr
)
59 if (type
< OBJ_COMMIT
|| type
> OBJ_DELTA
)
60 die("bad type %d", type
);
62 c
= (type
<< 4) | (size
& 15);
74 static unsigned long write_object(struct sha1file
*f
, struct object_entry
*entry
)
78 void *buf
= read_sha1_file(entry
->sha1
, type
, &size
);
79 unsigned char header
[10];
80 unsigned hdrlen
, datalen
;
81 enum object_type obj_type
;
84 die("unable to read %s", sha1_to_hex(entry
->sha1
));
85 if (size
!= entry
->size
)
86 die("object %s size inconsistency (%lu vs %lu)", sha1_to_hex(entry
->sha1
), size
, entry
->size
);
89 * The object header is a byte of 'type' followed by zero or
90 * more bytes of length. For deltas, the 20 bytes of delta sha1
93 obj_type
= entry
->type
;
95 buf
= delta_against(buf
, size
, entry
);
96 size
= entry
->delta_size
;
99 hdrlen
= encode_header(obj_type
, size
, header
);
100 sha1write(f
, header
, hdrlen
);
102 sha1write(f
, entry
->delta
, 20);
105 datalen
= sha1write_compressed(f
, buf
, size
);
107 return hdrlen
+ datalen
;
110 static unsigned long write_one(struct sha1file
*f
,
111 struct object_entry
*e
,
112 unsigned long offset
)
115 /* offset starts from header size and cannot be zero
116 * if it is written already.
120 offset
+= write_object(f
, e
);
121 /* if we are delitified, write out its base object. */
123 offset
= write_one(f
, e
->delta
, offset
);
127 static void write_pack_file(void)
131 unsigned long offset
;
133 struct pack_header hdr
;
136 f
= sha1fd(1, "<stdout>");
138 f
= sha1create("%s.%s", base_name
, "pack");
139 hdr
.hdr_signature
= htonl(PACK_SIGNATURE
);
140 hdr
.hdr_version
= htonl(PACK_VERSION
);
141 hdr
.hdr_entries
= htonl(nr_objects
);
142 sha1write(f
, &hdr
, sizeof(hdr
));
143 offset
= sizeof(hdr
);
144 for (i
= 0; i
< nr_objects
; i
++)
145 offset
= write_one(f
, objects
+ i
, offset
);
147 sha1close(f
, pack_file_sha1
, 1);
152 static void write_index_file(void)
155 struct sha1file
*f
= sha1create("%s.%s", base_name
, "idx");
156 struct object_entry
**list
= sorted_by_sha
;
157 struct object_entry
**last
= list
+ nr_objects
;
158 unsigned int array
[256];
161 * Write the first-level table (the list is sorted,
162 * but we use a 256-entry lookup to be able to avoid
163 * having to do eight extra binary search iterations).
165 for (i
= 0; i
< 256; i
++) {
166 struct object_entry
**next
= list
;
167 while (next
< last
) {
168 struct object_entry
*entry
= *next
;
169 if (entry
->sha1
[0] != i
)
173 array
[i
] = htonl(next
- sorted_by_sha
);
176 sha1write(f
, array
, 256 * sizeof(int));
179 * Write the actual SHA1 entries..
181 list
= sorted_by_sha
;
182 for (i
= 0; i
< nr_objects
; i
++) {
183 struct object_entry
*entry
= *list
++;
184 unsigned int offset
= htonl(entry
->offset
);
185 sha1write(f
, &offset
, 4);
186 sha1write(f
, entry
->sha1
, 20);
188 sha1write(f
, pack_file_sha1
, 20);
189 sha1close(f
, NULL
, 1);
192 static void add_object_entry(unsigned char *sha1
, unsigned int hash
)
194 unsigned int idx
= nr_objects
;
195 struct object_entry
*entry
;
197 if (incremental
&& has_sha1_pack(sha1
))
200 if (idx
>= nr_alloc
) {
201 unsigned int needed
= (idx
+ 1024) * 3 / 2;
202 objects
= xrealloc(objects
, needed
* sizeof(*entry
));
205 entry
= objects
+ idx
;
206 memset(entry
, 0, sizeof(*entry
));
207 memcpy(entry
->sha1
, sha1
, 20);
212 static void check_object(struct object_entry
*entry
)
216 if (!sha1_object_info(entry
->sha1
, type
, &entry
->size
)) {
217 if (!strcmp(type
, "commit")) {
218 entry
->type
= OBJ_COMMIT
;
219 } else if (!strcmp(type
, "tree")) {
220 entry
->type
= OBJ_TREE
;
221 } else if (!strcmp(type
, "blob")) {
222 entry
->type
= OBJ_BLOB
;
223 } else if (!strcmp(type
, "tag")) {
224 entry
->type
= OBJ_TAG
;
226 die("unable to pack object %s of type %s",
227 sha1_to_hex(entry
->sha1
), type
);
230 die("unable to get type of object %s",
231 sha1_to_hex(entry
->sha1
));
234 static void get_object_details(void)
237 struct object_entry
*entry
= objects
;
239 for (i
= 0; i
< nr_objects
; i
++)
240 check_object(entry
++);
243 typedef int (*entry_sort_t
)(const struct object_entry
*, const struct object_entry
*);
245 static entry_sort_t current_sort
;
247 static int sort_comparator(const void *_a
, const void *_b
)
249 struct object_entry
*a
= *(struct object_entry
**)_a
;
250 struct object_entry
*b
= *(struct object_entry
**)_b
;
251 return current_sort(a
,b
);
254 static struct object_entry
**create_sorted_list(entry_sort_t sort
)
256 struct object_entry
**list
= xmalloc(nr_objects
* sizeof(struct object_entry
*));
259 for (i
= 0; i
< nr_objects
; i
++)
260 list
[i
] = objects
+ i
;
262 qsort(list
, nr_objects
, sizeof(struct object_entry
*), sort_comparator
);
266 static int sha1_sort(const struct object_entry
*a
, const struct object_entry
*b
)
268 return memcmp(a
->sha1
, b
->sha1
, 20);
271 static int type_size_sort(const struct object_entry
*a
, const struct object_entry
*b
)
273 if (a
->type
< b
->type
)
275 if (a
->type
> b
->type
)
277 if (a
->hash
< b
->hash
)
279 if (a
->hash
> b
->hash
)
281 if (a
->size
< b
->size
)
283 if (a
->size
> b
->size
)
285 return a
< b
? -1 : (a
> b
);
289 struct object_entry
*entry
;
294 * We search for deltas _backwards_ in a list sorted by type and
295 * by size, so that we see progressively smaller and smaller files.
296 * That's because we prefer deltas to be from the bigger file
297 * to the smaller - deletes are potentially cheaper, but perhaps
298 * more importantly, the bigger file is likely the more recent
301 static int try_delta(struct unpacked
*cur
, struct unpacked
*old
, unsigned max_depth
)
303 struct object_entry
*cur_entry
= cur
->entry
;
304 struct object_entry
*old_entry
= old
->entry
;
305 unsigned long size
, oldsize
, delta_size
, sizediff
;
309 /* Don't bother doing diffs between different types */
310 if (cur_entry
->type
!= old_entry
->type
)
313 size
= cur_entry
->size
;
316 oldsize
= old_entry
->size
;
317 sizediff
= oldsize
> size
? oldsize
- size
: size
- oldsize
;
318 if (sizediff
> size
/ 8)
320 if (old_entry
->depth
>= max_depth
)
326 * We always delta from the bigger to the smaller, since that's
327 * more space-efficient (deletes don't have to say _what_ they
330 max_size
= size
/ 2 - 20;
331 if (cur_entry
->delta
)
332 max_size
= cur_entry
->delta_size
-1;
333 if (sizediff
>= max_size
)
335 delta_buf
= diff_delta(old
->data
, oldsize
,
336 cur
->data
, size
, &delta_size
, max_size
);
339 cur_entry
->delta
= old_entry
;
340 cur_entry
->delta_size
= delta_size
;
341 cur_entry
->depth
= old_entry
->depth
+ 1;
346 static void find_deltas(struct object_entry
**list
, int window
, int depth
)
349 unsigned int array_size
= window
* sizeof(struct unpacked
);
350 struct unpacked
*array
= xmalloc(array_size
);
352 memset(array
, 0, array_size
);
356 struct object_entry
*entry
= list
[i
];
357 struct unpacked
*n
= array
+ idx
;
364 n
->data
= read_sha1_file(entry
->sha1
, type
, &size
);
365 if (size
!= entry
->size
)
366 die("object %s inconsistent object length (%lu vs %lu)", sha1_to_hex(entry
->sha1
), size
, entry
->size
);
369 unsigned int other_idx
= idx
+ j
;
371 if (other_idx
>= window
)
373 m
= array
+ other_idx
;
376 if (try_delta(n
, m
, depth
) < 0)
385 int main(int argc
, char **argv
)
387 char line
[PATH_MAX
+ 20];
388 int window
= 10, depth
= 10, pack_to_stdout
= 0;
391 for (i
= 1; i
< argc
; i
++) {
392 const char *arg
= argv
[i
];
395 if (!strcmp("--non-empty", arg
)) {
399 if (!strcmp("--incremental", arg
)) {
403 if (!strncmp("--window=", arg
, 9)) {
405 window
= strtoul(arg
+9, &end
, 0);
410 if (!strncmp("--depth=", arg
, 8)) {
412 depth
= strtoul(arg
+8, &end
, 0);
417 if (!strcmp("--stdout", arg
)) {
428 if (pack_to_stdout
!= !base_name
)
431 while (fgets(line
, sizeof(line
), stdin
) != NULL
) {
434 unsigned char sha1
[20];
436 if (get_sha1_hex(line
, sha1
))
437 die("expected sha1, got garbage");
441 unsigned char c
= *p
++;
444 hash
= hash
* 11 + c
;
446 add_object_entry(sha1
, hash
);
448 if (non_empty
&& !nr_objects
)
450 get_object_details();
452 fprintf(stderr
, "Packing %d objects\n", nr_objects
);
454 sorted_by_sha
= create_sorted_list(sha1_sort
);
455 sorted_by_type
= create_sorted_list(type_size_sort
);
457 find_deltas(sorted_by_type
, window
+1, depth
);