[thirdparty/git.git] / pack-objects.c

#include <ctype.h>
#include "cache.h"
#include "object.h"
#include "delta.h"
#include "pack.h"
#include "csum-file.h"

static const char pack_usage[] = "git-pack-objects [--window=N] [--depth=N] {--stdout | base-name} < object-list";

struct object_entry {
	unsigned char sha1[20];
	unsigned long size;
	unsigned long offset;
	unsigned int depth;
	unsigned int hash;
	enum object_type type;
	unsigned long delta_size;
	struct object_entry *delta;
};

static struct object_entry **sorted_by_sha, **sorted_by_type;
static struct object_entry *objects = NULL;
static int nr_objects = 0, nr_alloc = 0;
static const char *base_name;
static unsigned char pack_file_sha1[20];

static void *delta_against(void *buf, unsigned long size, struct object_entry *entry)
{
	unsigned long othersize, delta_size;
	char type[10];
	void *otherbuf = read_sha1_file(entry->delta->sha1, type, &othersize);
	void *delta_buf;

	if (!otherbuf)
		die("unable to read %s", sha1_to_hex(entry->delta->sha1));
        delta_buf = diff_delta(otherbuf, othersize,
			       buf, size, &delta_size, ~0UL);
        if (!delta_buf || delta_size != entry->delta_size)
        	die("delta size changed");
        free(buf);
        free(otherbuf);
	return delta_buf;
}

/*
 * The per-object header is a pretty dense thing, which is
 *  - first byte: low four bits are "size", then three bits of "type",
 *    and the high bit is "size continues".
 *  - each byte afterwards: low seven bits are size continuation,
 *    with the high bit being "size continues"
 */
static int encode_header(enum object_type type, unsigned long size, unsigned char *hdr)
{
	int n = 1, i;
	unsigned char c;

	if (type < OBJ_COMMIT || type > OBJ_DELTA)
		die("bad type %d", type);

	/*
	 * Shift the size up by 7 bits at a time,
	 * until you get bits in the "high four".
	 * That will be our beginning. We'll have
	 * four size bits in 28..31, then groups
	 * of seven in 21..27, 14..20, 7..13 and
	 * finally 0..6.
	 */
	if (size) {
		n = 5;
		while (!(size & 0xfe000000)) {
			size <<= 7;
			n--;
		}
	}
	c = (type << 4) | (size >> 28);
	for (i = 1; i < n; i++) {
		*hdr++ = c | 0x80;
		c = (size >> 21) & 0x7f;
		size <<= 7;
	}
	*hdr = c;
	return n;
}

static unsigned long write_object(struct sha1file *f, struct object_entry *entry)
{
	unsigned long size;
	char type[10];
	void *buf = read_sha1_file(entry->sha1, type, &size);
	unsigned char header[10];
	unsigned hdrlen, datalen;
	enum object_type obj_type;

	if (!buf)
		die("unable to read %s", sha1_to_hex(entry->sha1));
	if (size != entry->size)
		die("object %s size inconsistency (%lu vs %lu)", sha1_to_hex(entry->sha1), size, entry->size);

	/*
	 * The object header is a byte of 'type' followed by four bytes of
	 * length, except for deltas that has the 20 bytes of delta sha
	 * instead.
	 */
	obj_type = entry->type;
	if (entry->delta) {
		buf = delta_against(buf, size, entry);
		size = entry->delta_size;
		obj_type = OBJ_DELTA;
	}
	hdrlen = encode_header(obj_type, size, header);
	sha1write(f, header, hdrlen);
	if (entry->delta) {
		sha1write(f, entry->delta, 20);
		hdrlen += 20;
	}
	datalen = sha1write_compressed(f, buf, size);
	free(buf);
	return hdrlen + datalen;
}

static void write_pack_file(void)
{
	int i;
	struct sha1file *f;
	unsigned long offset;
	unsigned long mb;
	struct pack_header hdr;

	if (!base_name)
		f = sha1fd(1, "<stdout>");
	else
		f = sha1create("%s.%s", base_name, "pack");
	hdr.hdr_signature = htonl(PACK_SIGNATURE);
	hdr.hdr_version = htonl(1);
	hdr.hdr_entries = htonl(nr_objects);
	sha1write(f, &hdr, sizeof(hdr));
	offset = sizeof(hdr);
	for (i = 0; i < nr_objects; i++) {
		struct object_entry *entry = objects + i;
		entry->offset = offset;
		offset += write_object(f, entry);
	}
	sha1close(f, pack_file_sha1, 1);
	mb = offset >> 20;
	offset &= 0xfffff;
}

static void write_index_file(void)
{
	int i;
	struct sha1file *f = sha1create("%s.%s", base_name, "idx");
	struct object_entry **list = sorted_by_sha;
	struct object_entry **last = list + nr_objects;
	unsigned int array[256];

	/*
	 * Write the first-level table (the list is sorted,
	 * but we use a 256-entry lookup to be able to avoid
	 * having to do eight extra binary search iterations).
	 */
	for (i = 0; i < 256; i++) {
		struct object_entry **next = list;
		while (next < last) {
			struct object_entry *entry = *next;
			if (entry->sha1[0] != i)
				break;
			next++;
		}
		array[i] = htonl(next - sorted_by_sha);
		list = next;
	}
	sha1write(f, array, 256 * sizeof(int));

	/*
	 * Write the actual SHA1 entries..
	 */
	list = sorted_by_sha;
	for (i = 0; i < nr_objects; i++) {
		struct object_entry *entry = *list++;
		unsigned int offset = htonl(entry->offset);
		sha1write(f, &offset, 4);
		sha1write(f, entry->sha1, 20);
	}
	sha1write(f, pack_file_sha1, 20);
	sha1close(f, NULL, 1);
}

static void add_object_entry(unsigned char *sha1, unsigned int hash)
{
	unsigned int idx = nr_objects;
	struct object_entry *entry;

	if (idx >= nr_alloc) {
		unsigned int needed = (idx + 1024) * 3 / 2;
		objects = xrealloc(objects, needed * sizeof(*entry));
		nr_alloc = needed;
	}
	entry = objects + idx;
	memset(entry, 0, sizeof(*entry));
	memcpy(entry->sha1, sha1, 20);
	entry->hash = hash;
	nr_objects = idx+1;
}

static void check_object(struct object_entry *entry)
{
	char type[20];

	if (!sha1_object_info(entry->sha1, type, &entry->size)) {
		if (!strcmp(type, "commit")) {
			entry->type = OBJ_COMMIT;
		} else if (!strcmp(type, "tree")) {
			entry->type = OBJ_TREE;
		} else if (!strcmp(type, "blob")) {
			entry->type = OBJ_BLOB;
		} else if (!strcmp(type, "tag")) {
			entry->type = OBJ_TAG;
		} else
			die("unable to pack object %s of type %s",
			    sha1_to_hex(entry->sha1), type);
	}
	else
		die("unable to get type of object %s",
		    sha1_to_hex(entry->sha1));
}

static void get_object_details(void)
{
	int i;
	struct object_entry *entry = objects;

	for (i = 0; i < nr_objects; i++)
		check_object(entry++);
}

typedef int (*entry_sort_t)(const struct object_entry *, const struct object_entry *);

static entry_sort_t current_sort;

static int sort_comparator(const void *_a, const void *_b)
{
	struct object_entry *a = *(struct object_entry **)_a;
	struct object_entry *b = *(struct object_entry **)_b;
	return current_sort(a,b);
}

static struct object_entry **create_sorted_list(entry_sort_t sort)
{
	struct object_entry **list = xmalloc(nr_objects * sizeof(struct object_entry *));
	int i;

	for (i = 0; i < nr_objects; i++)
		list[i] = objects + i;
	current_sort = sort;
	qsort(list, nr_objects, sizeof(struct object_entry *), sort_comparator);
	return list;
}

static int sha1_sort(const struct object_entry *a, const struct object_entry *b)
{
	return memcmp(a->sha1, b->sha1, 20);
}

static int type_size_sort(const struct object_entry *a, const struct object_entry *b)
{
	if (a->type < b->type)
		return -1;
	if (a->type > b->type)
		return 1;
	if (a->hash < b->hash)
		return -1;
	if (a->hash > b->hash)
		return 1;
	if (a->size < b->size)
		return -1;
	if (a->size > b->size)
		return 1;
	return a < b ? -1 : (a > b);
}

struct unpacked {
	struct object_entry *entry;
	void *data;
};

/*
 * We search for deltas _backwards_ in a list sorted by type and
 * by size, so that we see progressively smaller and smaller files.
 * That's because we prefer deltas to be from the bigger file
 * to the smaller - deletes are potentially cheaper, but perhaps
 * more importantly, the bigger file is likely the more recent
 * one.
 */
static int try_delta(struct unpacked *cur, struct unpacked *old, unsigned max_depth)
{
	struct object_entry *cur_entry = cur->entry;
	struct object_entry *old_entry = old->entry;
	unsigned long size, oldsize, delta_size, sizediff;
	long max_size;
	void *delta_buf;

	/* Don't bother doing diffs between different types */
	if (cur_entry->type != old_entry->type)
		return -1;

	size = cur_entry->size;
	if (size < 50)
		return -1;
	oldsize = old_entry->size;
	sizediff = oldsize > size ? oldsize - size : size - oldsize;
	if (sizediff > size / 8)
		return -1;
	if (old_entry->depth >= max_depth)
		return 0;

	/*
	 * NOTE!
	 *
	 * We always delta from the bigger to the smaller, since that's
	 * more space-efficient (deletes don't have to say _what_ they
	 * delete).
	 */
	max_size = size / 2 - 20;
	if (cur_entry->delta)
		max_size = cur_entry->delta_size-1;
	if (sizediff >= max_size)
		return -1;
	delta_buf = diff_delta(old->data, oldsize,
			       cur->data, size, &delta_size, max_size);
	if (!delta_buf)
		return 0;
	cur_entry->delta = old_entry;
	cur_entry->delta_size = delta_size;
	cur_entry->depth = old_entry->depth + 1;
	free(delta_buf);
	return 0;
}

static void find_deltas(struct object_entry **list, int window, int depth)
{
	int i, idx;
	unsigned int array_size = window * sizeof(struct unpacked);
	struct unpacked *array = xmalloc(array_size);

	memset(array, 0, array_size);
	i = nr_objects;
	idx = 0;
	while (--i >= 0) {
		struct object_entry *entry = list[i];
		struct unpacked *n = array + idx;
		unsigned long size;
		char type[10];
		int j;

		free(n->data);
		n->entry = entry;
		n->data = read_sha1_file(entry->sha1, type, &size);
		if (size != entry->size)
			die("object %s inconsistent object length (%lu vs %lu)", sha1_to_hex(entry->sha1), size, entry->size);
		j = window;
		while (--j > 0) {
			unsigned int other_idx = idx + j;
			struct unpacked *m;
			if (other_idx >= window)
				other_idx -= window;
			m = array + other_idx;
			if (!m->entry)
				break;
			if (try_delta(n, m, depth) < 0)
				break;
		}
		idx++;
		if (idx >= window)
			idx = 0;
	}
}

int main(int argc, char **argv)
{
	char line[PATH_MAX + 20];
	int window = 10, depth = 10, pack_to_stdout = 0;
	int i;

	for (i = 1; i < argc; i++) {
		const char *arg = argv[i];

		if (*arg == '-') {
			if (!strncmp("--window=", arg, 9)) {
				char *end;
				window = strtoul(arg+9, &end, 0);
				if (!arg[9] || *end)
					usage(pack_usage);
				continue;
			}
			if (!strncmp("--depth=", arg, 8)) {
				char *end;
				depth = strtoul(arg+8, &end, 0);
				if (!arg[8] || *end)
					usage(pack_usage);
				continue;
			}
			if (!strcmp("--stdout", arg)) {
				pack_to_stdout = 1;
				continue;
			}
			usage(pack_usage);
		}
		if (base_name)
			usage(pack_usage);
		base_name = arg;
	}

	if (pack_to_stdout != !base_name)
		usage(pack_usage);

	while (fgets(line, sizeof(line), stdin) != NULL) {
		unsigned int hash;
		char *p;
		unsigned char sha1[20];

		if (get_sha1_hex(line, sha1))
			die("expected sha1, got garbage");
		hash = 0;
		p = line+40;
		while (*p) {
			unsigned char c = *p++;
			if (isspace(c))
				continue;
			hash = hash * 11 + c;
		}
		add_object_entry(sha1, hash);
	}
	get_object_details();

	fprintf(stderr, "Packing %d objects\n", nr_objects);

	sorted_by_sha = create_sorted_list(sha1_sort);
	sorted_by_type = create_sorted_list(type_size_sort);
	if (window && depth)
		find_deltas(sorted_by_type, window+1, depth);

	write_pack_file();
	if (!pack_to_stdout)
		write_index_file();
	return 0;
}
Commit	Line	Data
27225f2e	1	#include <ctype.h>
c323ac7d LT	2	#include "cache.h"
	3	#include "object.h"
	4	#include "delta.h"
a733cb60	5	#include "pack.h"
c38138cd	6	#include "csum-file.h"
c323ac7d	7
d22b9290	8	static const char pack_usage[] = "git-pack-objects [--window=N] [--depth=N] {--stdout \| base-name} < object-list";
c323ac7d	9
c323ac7d LT	10	struct object_entry {
	11	unsigned char sha1[20];
	12	unsigned long size;
	13	unsigned long offset;
	14	unsigned int depth;
27225f2e	15	unsigned int hash;
a733cb60	16	enum object_type type;
c323ac7d LT	17	unsigned long delta_size;
	18	struct object_entry *delta;
	19	};
	20
	21	static struct object_entry sorted_by_sha, sorted_by_type;
	22	static struct object_entry *objects = NULL;
	23	static int nr_objects = 0, nr_alloc = 0;
c323ac7d	24	static const char *base_name;
e1808845	25	static unsigned char pack_file_sha1[20];
c323ac7d	26
c323ac7d LT	27	static void delta_against(void buf, unsigned long size, struct object_entry *entry)
	28	{
	29	unsigned long othersize, delta_size;
	30	char type[10];
	31	void *otherbuf = read_sha1_file(entry->delta->sha1, type, &othersize);
	32	void *delta_buf;
	33
	34	if (!otherbuf)
	35	die("unable to read %s", sha1_to_hex(entry->delta->sha1));
8ee378a0 JH	36	delta_buf = diff_delta(otherbuf, othersize,
8ee378a0 JH	37	buf, size, &delta_size, ~0UL);
75c42d8c	38	if (!delta_buf \|\| delta_size != entry->delta_size)
c323ac7d LT	39	die("delta size changed");
	40	free(buf);
	41	free(otherbuf);
	42	return delta_buf;
	43	}
	44
a733cb60 LT	45	/*
	46	* The per-object header is a pretty dense thing, which is
	47	* - first byte: low four bits are "size", then three bits of "type",
	48	* and the high bit is "size continues".
	49	* - each byte afterwards: low seven bits are size continuation,
	50	* with the high bit being "size continues"
	51	*/
	52	static int encode_header(enum object_type type, unsigned long size, unsigned char *hdr)
	53	{
	54	int n = 1, i;
	55	unsigned char c;
	56
	57	if (type < OBJ_COMMIT \|\| type > OBJ_DELTA)
	58	die("bad type %d", type);
	59
	60	/*
	61	* Shift the size up by 7 bits at a time,
	62	* until you get bits in the "high four".
	63	* That will be our beginning. We'll have
	64	* four size bits in 28..31, then groups
	65	* of seven in 21..27, 14..20, 7..13 and
	66	* finally 0..6.
	67	*/
	68	if (size) {
	69	n = 5;
	70	while (!(size & 0xfe000000)) {
	71	size <<= 7;
	72	n--;
	73	}
	74	}
	75	c = (type << 4) \| (size >> 28);
	76	for (i = 1; i < n; i++) {
	77	*hdr++ = c \| 0x80;
	78	c = (size >> 21) & 0x7f;
	79	size <<= 7;
	80	}
	81	*hdr = c;
	82	return n;
	83	}
	84
c38138cd	85	static unsigned long write_object(struct sha1file f, struct object_entry entry)
c323ac7d LT	86	{
	87	unsigned long size;
	88	char type[10];
	89	void *buf = read_sha1_file(entry->sha1, type, &size);
a733cb60	90	unsigned char header[10];
c323ac7d	91	unsigned hdrlen, datalen;
a733cb60	92	enum object_type obj_type;
c323ac7d LT	93
	94	if (!buf)
	95	die("unable to read %s", sha1_to_hex(entry->sha1));
	96	if (size != entry->size)
	97	die("object %s size inconsistency (%lu vs %lu)", sha1_to_hex(entry->sha1), size, entry->size);
	98
	99	/*
	100	* The object header is a byte of 'type' followed by four bytes of
	101	* length, except for deltas that has the 20 bytes of delta sha
	102	* instead.
	103	*/
a733cb60	104	obj_type = entry->type;
c323ac7d	105	if (entry->delta) {
c323ac7d LT	106	buf = delta_against(buf, size, entry);
c323ac7d LT	107	size = entry->delta_size;
a733cb60	108	obj_type = OBJ_DELTA;
c323ac7d	109	}
a733cb60	110	hdrlen = encode_header(obj_type, size, header);
c38138cd	111	sha1write(f, header, hdrlen);
a733cb60 LT	112	if (entry->delta) {
	113	sha1write(f, entry->delta, 20);
	114	hdrlen += 20;
	115	}
c38138cd	116	datalen = sha1write_compressed(f, buf, size);
c323ac7d LT	117	free(buf);
	118	return hdrlen + datalen;
	119	}
	120
	121	static void write_pack_file(void)
	122	{
	123	int i;
d22b9290	124	struct sha1file *f;
a733cb60	125	unsigned long offset;
c323ac7d	126	unsigned long mb;
a733cb60	127	struct pack_header hdr;
c323ac7d	128
d22b9290 LT	129	if (!base_name)
	130	f = sha1fd(1, "<stdout>");
	131	else
	132	f = sha1create("%s.%s", base_name, "pack");
a733cb60 LT	133	hdr.hdr_signature = htonl(PACK_SIGNATURE);
	134	hdr.hdr_version = htonl(1);
	135	hdr.hdr_entries = htonl(nr_objects);
	136	sha1write(f, &hdr, sizeof(hdr));
	137	offset = sizeof(hdr);
c323ac7d LT	138	for (i = 0; i < nr_objects; i++) {
	139	struct object_entry *entry = objects + i;
	140	entry->offset = offset;
	141	offset += write_object(f, entry);
	142	}
e1808845	143	sha1close(f, pack_file_sha1, 1);
c323ac7d LT	144	mb = offset >> 20;
	145	offset &= 0xfffff;
	146	}
	147
	148	static void write_index_file(void)
	149	{
	150	int i;
c38138cd	151	struct sha1file *f = sha1create("%s.%s", base_name, "idx");
c323ac7d LT	152	struct object_entry **list = sorted_by_sha;
	153	struct object_entry **last = list + nr_objects;
	154	unsigned int array[256];
	155
	156	/*
	157	* Write the first-level table (the list is sorted,
	158	* but we use a 256-entry lookup to be able to avoid
e1808845	159	* having to do eight extra binary search iterations).
c323ac7d LT	160	*/
	161	for (i = 0; i < 256; i++) {
	162	struct object_entry **next = list;
	163	while (next < last) {
	164	struct object_entry entry = next;
	165	if (entry->sha1[0] != i)
	166	break;
	167	next++;
	168	}
	169	array[i] = htonl(next - sorted_by_sha);
	170	list = next;
	171	}
c38138cd	172	sha1write(f, array, 256 * sizeof(int));
c323ac7d LT	173
	174	/*
	175	* Write the actual SHA1 entries..
	176	*/
	177	list = sorted_by_sha;
49397104	178	for (i = 0; i < nr_objects; i++) {
c323ac7d LT	179	struct object_entry entry = list++;
c323ac7d LT	180	unsigned int offset = htonl(entry->offset);
c38138cd LT	181	sha1write(f, &offset, 4);
c38138cd LT	182	sha1write(f, entry->sha1, 20);
c323ac7d	183	}
e1808845 LT	184	sha1write(f, pack_file_sha1, 20);
e1808845 LT	185	sha1close(f, NULL, 1);
c323ac7d LT	186	}
c323ac7d LT	187
27225f2e	188	static void add_object_entry(unsigned char *sha1, unsigned int hash)
c323ac7d LT	189	{
	190	unsigned int idx = nr_objects;
	191	struct object_entry *entry;
	192
	193	if (idx >= nr_alloc) {
	194	unsigned int needed = (idx + 1024) * 3 / 2;
	195	objects = xrealloc(objects, needed * sizeof(*entry));
	196	nr_alloc = needed;
	197	}
	198	entry = objects + idx;
	199	memset(entry, 0, sizeof(*entry));
	200	memcpy(entry->sha1, sha1, 20);
27225f2e	201	entry->hash = hash;
c323ac7d LT	202	nr_objects = idx+1;
	203	}
	204
	205	static void check_object(struct object_entry *entry)
	206	{
36e4d74a JH	207	char type[20];
	208
	209	if (!sha1_object_info(entry->sha1, type, &entry->size)) {
	210	if (!strcmp(type, "commit")) {
a733cb60	211	entry->type = OBJ_COMMIT;
36e4d74a	212	} else if (!strcmp(type, "tree")) {
a733cb60	213	entry->type = OBJ_TREE;
36e4d74a	214	} else if (!strcmp(type, "blob")) {
a733cb60	215	entry->type = OBJ_BLOB;
a69d0943	216	} else if (!strcmp(type, "tag")) {
a733cb60	217	entry->type = OBJ_TAG;
36e4d74a JH	218	} else
	219	die("unable to pack object %s of type %s",
	220	sha1_to_hex(entry->sha1), type);
	221	}
	222	else
	223	die("unable to get type of object %s",
	224	sha1_to_hex(entry->sha1));
c323ac7d LT	225	}
	226
	227	static void get_object_details(void)
	228	{
	229	int i;
	230	struct object_entry *entry = objects;
	231
	232	for (i = 0; i < nr_objects; i++)
	233	check_object(entry++);
	234	}
	235
	236	typedef int (entry_sort_t)(const struct object_entry , const struct object_entry *);
	237
	238	static entry_sort_t current_sort;
	239
	240	static int sort_comparator(const void _a, const void _b)
	241	{
	242	struct object_entry a = (struct object_entry **)_a;
	243	struct object_entry b = (struct object_entry **)_b;
	244	return current_sort(a,b);
	245	}
	246
	247	static struct object_entry **create_sorted_list(entry_sort_t sort)
	248	{
	249	struct object_entry *list = xmalloc(nr_objects sizeof(struct object_entry *));
	250	int i;
	251
	252	for (i = 0; i < nr_objects; i++)
	253	list[i] = objects + i;
	254	current_sort = sort;
	255	qsort(list, nr_objects, sizeof(struct object_entry *), sort_comparator);
	256	return list;
	257	}
	258
	259	static int sha1_sort(const struct object_entry a, const struct object_entry b)
	260	{
	261	return memcmp(a->sha1, b->sha1, 20);
	262	}
	263
	264	static int type_size_sort(const struct object_entry a, const struct object_entry b)
	265	{
	266	if (a->type < b->type)
	267	return -1;
	268	if (a->type > b->type)
	269	return 1;
27225f2e LT	270	if (a->hash < b->hash)
	271	return -1;
	272	if (a->hash > b->hash)
	273	return 1;
c323ac7d LT	274	if (a->size < b->size)
	275	return -1;
	276	if (a->size > b->size)
	277	return 1;
	278	return a < b ? -1 : (a > b);
	279	}
	280
	281	struct unpacked {
	282	struct object_entry *entry;
	283	void *data;
	284	};
	285
	286	/*
521a4f4c LT	287	* We search for deltas _backwards_ in a list sorted by type and
	288	* by size, so that we see progressively smaller and smaller files.
	289	* That's because we prefer deltas to be from the bigger file
	290	* to the smaller - deletes are potentially cheaper, but perhaps
	291	* more importantly, the bigger file is likely the more recent
	292	* one.
c323ac7d	293	*/
d116a45a	294	static int try_delta(struct unpacked cur, struct unpacked old, unsigned max_depth)
c323ac7d LT	295	{
	296	struct object_entry *cur_entry = cur->entry;
	297	struct object_entry *old_entry = old->entry;
521a4f4c	298	unsigned long size, oldsize, delta_size, sizediff;
75c42d8c	299	long max_size;
c323ac7d LT	300	void *delta_buf;
	301
	302	/* Don't bother doing diffs between different types */
	303	if (cur_entry->type != old_entry->type)
	304	return -1;
	305
c323ac7d	306	size = cur_entry->size;
75c42d8c LT	307	if (size < 50)
75c42d8c LT	308	return -1;
c323ac7d	309	oldsize = old_entry->size;
521a4f4c LT	310	sizediff = oldsize > size ? oldsize - size : size - oldsize;
521a4f4c LT	311	if (sizediff > size / 8)
c323ac7d	312	return -1;
d116a45a LT	313	if (old_entry->depth >= max_depth)
d116a45a LT	314	return 0;
c323ac7d LT	315
	316	/*
	317	* NOTE!
	318	*
	319	* We always delta from the bigger to the smaller, since that's
	320	* more space-efficient (deletes don't have to say _what_ they
	321	* delete).
	322	*/
75c42d8c LT	323	max_size = size / 2 - 20;
	324	if (cur_entry->delta)
	325	max_size = cur_entry->delta_size-1;
27225f2e LT	326	if (sizediff >= max_size)
27225f2e LT	327	return -1;
8ee378a0 JH	328	delta_buf = diff_delta(old->data, oldsize,
8ee378a0 JH	329	cur->data, size, &delta_size, max_size);
c323ac7d	330	if (!delta_buf)
75c42d8c LT	331	return 0;
	332	cur_entry->delta = old_entry;
	333	cur_entry->delta_size = delta_size;
d116a45a	334	cur_entry->depth = old_entry->depth + 1;
c323ac7d	335	free(delta_buf);
eb41ab11	336	return 0;
c323ac7d LT	337	}
c323ac7d LT	338
d116a45a	339	static void find_deltas(struct object_entry **list, int window, int depth)
c323ac7d	340	{
521a4f4c	341	int i, idx;
c323ac7d LT	342	unsigned int array_size = window * sizeof(struct unpacked);
	343	struct unpacked *array = xmalloc(array_size);
	344
	345	memset(array, 0, array_size);
521a4f4c LT	346	i = nr_objects;
	347	idx = 0;
	348	while (--i >= 0) {
c323ac7d LT	349	struct object_entry *entry = list[i];
	350	struct unpacked *n = array + idx;
	351	unsigned long size;
	352	char type[10];
	353	int j;
	354
	355	free(n->data);
	356	n->entry = entry;
	357	n->data = read_sha1_file(entry->sha1, type, &size);
	358	if (size != entry->size)
	359	die("object %s inconsistent object length (%lu vs %lu)", sha1_to_hex(entry->sha1), size, entry->size);
78817c15 LT	360	j = window;
	361	while (--j > 0) {
	362	unsigned int other_idx = idx + j;
c323ac7d	363	struct unpacked *m;
78817c15 LT	364	if (other_idx >= window)
78817c15 LT	365	other_idx -= window;
c323ac7d LT	366	m = array + other_idx;
	367	if (!m->entry)
	368	break;
d116a45a	369	if (try_delta(n, m, depth) < 0)
c323ac7d LT	370	break;
c323ac7d LT	371	}
521a4f4c LT	372	idx++;
	373	if (idx >= window)
	374	idx = 0;
c323ac7d LT	375	}
	376	}
	377
	378	int main(int argc, char **argv)
	379	{
27225f2e	380	char line[PATH_MAX + 20];
d22b9290	381	int window = 10, depth = 10, pack_to_stdout = 0;
c323ac7d LT	382	int i;
	383
	384	for (i = 1; i < argc; i++) {
	385	const char *arg = argv[i];
	386
	387	if (*arg == '-') {
	388	if (!strncmp("--window=", arg, 9)) {
	389	char *end;
f846bbff	390	window = strtoul(arg+9, &end, 0);
c323ac7d LT	391	if (!arg[9] \|\| *end)
	392	usage(pack_usage);
	393	continue;
	394	}
d116a45a LT	395	if (!strncmp("--depth=", arg, 8)) {
	396	char *end;
	397	depth = strtoul(arg+8, &end, 0);
	398	if (!arg[8] \|\| *end)
	399	usage(pack_usage);
	400	continue;
	401	}
d22b9290 LT	402	if (!strcmp("--stdout", arg)) {
	403	pack_to_stdout = 1;
	404	continue;
	405	}
c323ac7d LT	406	usage(pack_usage);
	407	}
	408	if (base_name)
	409	usage(pack_usage);
	410	base_name = arg;
	411	}
	412
d22b9290	413	if (pack_to_stdout != !base_name)
c323ac7d LT	414	usage(pack_usage);
	415
	416	while (fgets(line, sizeof(line), stdin) != NULL) {
27225f2e LT	417	unsigned int hash;
27225f2e LT	418	char *p;
c323ac7d	419	unsigned char sha1[20];
27225f2e	420
c323ac7d LT	421	if (get_sha1_hex(line, sha1))
c323ac7d LT	422	die("expected sha1, got garbage");
27225f2e LT	423	hash = 0;
	424	p = line+40;
	425	while (*p) {
	426	unsigned char c = *p++;
	427	if (isspace(c))
	428	continue;
	429	hash = hash * 11 + c;
	430	}
	431	add_object_entry(sha1, hash);
c323ac7d LT	432	}
	433	get_object_details();
	434
d22b9290	435	fprintf(stderr, "Packing %d objects\n", nr_objects);
c323ac7d LT	436
	437	sorted_by_sha = create_sorted_list(sha1_sort);
	438	sorted_by_type = create_sorted_list(type_size_sort);
d116a45a LT	439	if (window && depth)
d116a45a LT	440	find_deltas(sorted_by_type, window+1, depth);
c323ac7d LT	441
c323ac7d LT	442	write_pack_file();
d22b9290 LT	443	if (!pack_to_stdout)
d22b9290 LT	444	write_index_file();
c323ac7d LT	445	return 0;
c323ac7d LT	446	}