6 static const char pack_usage
[] = "git-pack-objects [--window=N] [--depth=N] base-name < object-list";
13 OBJ_DELTA
// NOTE! This is _not_ the same as a "delta" object in the filesystem
17 unsigned char sha1
[20];
22 enum object_type type
;
23 unsigned long delta_size
;
24 struct object_entry
*delta
;
27 static struct object_entry
**sorted_by_sha
, **sorted_by_type
;
28 static struct object_entry
*objects
= NULL
;
29 static int nr_objects
= 0, nr_alloc
= 0;
30 static const char *base_name
;
35 unsigned char buffer
[8192];
38 static FILE *create_file(const char *suffix
)
40 static char filename
[PATH_MAX
];
43 len
= snprintf(filename
, PATH_MAX
, "%s.%s", base_name
, suffix
);
45 die("you wascally wabbit, you");
46 return fopen(filename
, "w");
49 static unsigned long fwrite_compressed(void *in
, unsigned long size
, FILE *f
)
52 unsigned long maxsize
;
55 memset(&stream
, 0, sizeof(stream
));
56 deflateInit(&stream
, Z_DEFAULT_COMPRESSION
);
57 maxsize
= deflateBound(&stream
, size
);
58 out
= xmalloc(maxsize
);
62 stream
.avail_in
= size
;
64 stream
.next_out
= out
;
65 stream
.avail_out
= maxsize
;
67 while (deflate(&stream
, Z_FINISH
) == Z_OK
)
71 size
= stream
.total_out
;
72 fwrite(out
, size
, 1, f
);
77 static void *delta_against(void *buf
, unsigned long size
, struct object_entry
*entry
)
79 unsigned long othersize
, delta_size
;
81 void *otherbuf
= read_sha1_file(entry
->delta
->sha1
, type
, &othersize
);
85 die("unable to read %s", sha1_to_hex(entry
->delta
->sha1
));
86 delta_buf
= diff_delta(otherbuf
, othersize
,
87 buf
, size
, &delta_size
, ~0UL);
88 if (!delta_buf
|| delta_size
!= entry
->delta_size
)
89 die("delta size changed");
95 static unsigned long write_object(FILE *f
, struct object_entry
*entry
)
99 void *buf
= read_sha1_file(entry
->sha1
, type
, &size
);
101 unsigned hdrlen
, datalen
;
104 die("unable to read %s", sha1_to_hex(entry
->sha1
));
105 if (size
!= entry
->size
)
106 die("object %s size inconsistency (%lu vs %lu)", sha1_to_hex(entry
->sha1
), size
, entry
->size
);
109 * The object header is a byte of 'type' followed by four bytes of
110 * length, except for deltas that has the 20 bytes of delta sha
113 header
[0] = ".CTB"[entry
->type
];
117 memcpy(header
+5, entry
->delta
, 20);
118 buf
= delta_against(buf
, size
, entry
);
119 size
= entry
->delta_size
;
122 datalen
= htonl(size
);
123 memcpy(header
+1, &datalen
, 4);
124 fwrite(header
, hdrlen
, 1, f
);
125 datalen
= fwrite_compressed(buf
, size
, f
);
127 return hdrlen
+ datalen
;
130 static void write_pack_file(void)
133 FILE *f
= create_file("pack");
134 unsigned long offset
= 0;
137 for (i
= 0; i
< nr_objects
; i
++) {
138 struct object_entry
*entry
= objects
+ i
;
139 entry
->offset
= offset
;
140 offset
+= write_object(f
, entry
);
147 static void write_index_file(void)
150 FILE *f
= create_file("idx");
151 struct object_entry
**list
= sorted_by_sha
;
152 struct object_entry
**last
= list
+ nr_objects
;
153 unsigned int array
[256];
156 * Write the first-level table (the list is sorted,
157 * but we use a 256-entry lookup to be able to avoid
158 * having to do eight extra binary search iterations)
160 for (i
= 0; i
< 256; i
++) {
161 struct object_entry
**next
= list
;
162 while (next
< last
) {
163 struct object_entry
*entry
= *next
;
164 if (entry
->sha1
[0] != i
)
168 array
[i
] = htonl(next
- sorted_by_sha
);
171 fwrite(array
, 256, sizeof(int), f
);
174 * Write the actual SHA1 entries..
176 list
= sorted_by_sha
;
177 for (i
= 0; i
< nr_objects
; i
++) {
178 struct object_entry
*entry
= *list
++;
179 unsigned int offset
= htonl(entry
->offset
);
180 fwrite(&offset
, 4, 1, f
);
181 fwrite(entry
->sha1
, 20, 1, f
);
186 static void add_object_entry(unsigned char *sha1
, unsigned int hash
)
188 unsigned int idx
= nr_objects
;
189 struct object_entry
*entry
;
191 if (idx
>= nr_alloc
) {
192 unsigned int needed
= (idx
+ 1024) * 3 / 2;
193 objects
= xrealloc(objects
, needed
* sizeof(*entry
));
196 entry
= objects
+ idx
;
197 memset(entry
, 0, sizeof(*entry
));
198 memcpy(entry
->sha1
, sha1
, 20);
203 static void check_object(struct object_entry
*entry
)
207 unsigned long mapsize
;
211 map
= map_sha1_file(entry
->sha1
, &mapsize
);
213 die("unable to map %s", sha1_to_hex(entry
->sha1
));
214 if (unpack_sha1_header(&stream
, map
, mapsize
, buffer
, sizeof(buffer
)) < 0)
215 die("unable to unpack %s header", sha1_to_hex(entry
->sha1
));
216 munmap(map
, mapsize
);
217 if (parse_sha1_header(buffer
, type
, &entry
->size
) < 0)
218 die("unable to parse %s header", sha1_to_hex(entry
->sha1
));
219 if (!strcmp(type
, "commit")) {
220 entry
->type
= OBJ_COMMIT
;
221 } else if (!strcmp(type
, "tree")) {
222 entry
->type
= OBJ_TREE
;
223 } else if (!strcmp(type
, "blob")) {
224 entry
->type
= OBJ_BLOB
;
226 die("unable to pack object %s of type %s", sha1_to_hex(entry
->sha1
), type
);
229 static void get_object_details(void)
232 struct object_entry
*entry
= objects
;
234 for (i
= 0; i
< nr_objects
; i
++)
235 check_object(entry
++);
238 typedef int (*entry_sort_t
)(const struct object_entry
*, const struct object_entry
*);
240 static entry_sort_t current_sort
;
242 static int sort_comparator(const void *_a
, const void *_b
)
244 struct object_entry
*a
= *(struct object_entry
**)_a
;
245 struct object_entry
*b
= *(struct object_entry
**)_b
;
246 return current_sort(a
,b
);
249 static struct object_entry
**create_sorted_list(entry_sort_t sort
)
251 struct object_entry
**list
= xmalloc(nr_objects
* sizeof(struct object_entry
*));
254 for (i
= 0; i
< nr_objects
; i
++)
255 list
[i
] = objects
+ i
;
257 qsort(list
, nr_objects
, sizeof(struct object_entry
*), sort_comparator
);
261 static int sha1_sort(const struct object_entry
*a
, const struct object_entry
*b
)
263 return memcmp(a
->sha1
, b
->sha1
, 20);
266 static int type_size_sort(const struct object_entry
*a
, const struct object_entry
*b
)
268 if (a
->type
< b
->type
)
270 if (a
->type
> b
->type
)
272 if (a
->hash
< b
->hash
)
274 if (a
->hash
> b
->hash
)
276 if (a
->size
< b
->size
)
278 if (a
->size
> b
->size
)
280 return a
< b
? -1 : (a
> b
);
284 struct object_entry
*entry
;
289 * We search for deltas _backwards_ in a list sorted by type and
290 * by size, so that we see progressively smaller and smaller files.
291 * That's because we prefer deltas to be from the bigger file
292 * to the smaller - deletes are potentially cheaper, but perhaps
293 * more importantly, the bigger file is likely the more recent
296 static int try_delta(struct unpacked
*cur
, struct unpacked
*old
, unsigned max_depth
)
298 struct object_entry
*cur_entry
= cur
->entry
;
299 struct object_entry
*old_entry
= old
->entry
;
300 unsigned long size
, oldsize
, delta_size
, sizediff
;
304 /* Don't bother doing diffs between different types */
305 if (cur_entry
->type
!= old_entry
->type
)
308 size
= cur_entry
->size
;
311 oldsize
= old_entry
->size
;
312 sizediff
= oldsize
> size
? oldsize
- size
: size
- oldsize
;
313 if (sizediff
> size
/ 8)
315 if (old_entry
->depth
>= max_depth
)
321 * We always delta from the bigger to the smaller, since that's
322 * more space-efficient (deletes don't have to say _what_ they
325 max_size
= size
/ 2 - 20;
326 if (cur_entry
->delta
)
327 max_size
= cur_entry
->delta_size
-1;
328 if (sizediff
>= max_size
)
330 delta_buf
= diff_delta(old
->data
, oldsize
,
331 cur
->data
, size
, &delta_size
, max_size
);
334 cur_entry
->delta
= old_entry
;
335 cur_entry
->delta_size
= delta_size
;
336 cur_entry
->depth
= old_entry
->depth
+ 1;
341 static void find_deltas(struct object_entry
**list
, int window
, int depth
)
344 unsigned int array_size
= window
* sizeof(struct unpacked
);
345 struct unpacked
*array
= xmalloc(array_size
);
347 memset(array
, 0, array_size
);
351 struct object_entry
*entry
= list
[i
];
352 struct unpacked
*n
= array
+ idx
;
359 n
->data
= read_sha1_file(entry
->sha1
, type
, &size
);
360 if (size
!= entry
->size
)
361 die("object %s inconsistent object length (%lu vs %lu)", sha1_to_hex(entry
->sha1
), size
, entry
->size
);
364 unsigned int other_idx
= idx
+ j
;
366 if (other_idx
>= window
)
368 m
= array
+ other_idx
;
371 if (try_delta(n
, m
, depth
) < 0)
380 int main(int argc
, char **argv
)
382 char line
[PATH_MAX
+ 20];
383 int window
= 10, depth
= 10;
386 for (i
= 1; i
< argc
; i
++) {
387 const char *arg
= argv
[i
];
390 if (!strncmp("--window=", arg
, 9)) {
392 window
= strtoul(arg
+9, &end
, 0);
397 if (!strncmp("--depth=", arg
, 8)) {
399 depth
= strtoul(arg
+8, &end
, 0);
414 while (fgets(line
, sizeof(line
), stdin
) != NULL
) {
417 unsigned char sha1
[20];
419 if (get_sha1_hex(line
, sha1
))
420 die("expected sha1, got garbage");
424 unsigned char c
= *p
++;
427 hash
= hash
* 11 + c
;
429 add_object_entry(sha1
, hash
);
431 get_object_details();
433 printf("Packing %d objects\n", nr_objects
);
435 sorted_by_sha
= create_sorted_list(sha1_sort
);
436 sorted_by_type
= create_sorted_list(type_size_sort
);
438 find_deltas(sorted_by_type
, window
+1, depth
);