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

#include "cache.h"
#include "delta.h"
#include "pack.h"
#include "csum-file.h"
#include "blob.h"
#include "commit.h"
#include "tag.h"
#include "tree.h"

static const char index_pack_usage[] =
"git-index-pack [-o index-file] pack-file";

struct object_entry
{
	unsigned long offset;
	enum object_type type;
	enum object_type real_type;
	unsigned char sha1[20];
};

struct delta_entry
{
	struct object_entry *obj;
	unsigned char base_sha1[20];
};

static const char *pack_name;
static unsigned char *pack_base;
static unsigned long pack_size;
static struct object_entry *objects;
static struct delta_entry *deltas;
static int nr_objects;
static int nr_deltas;

static void open_pack_file(void)
{
	int fd;
	struct stat st;

	fd = open(pack_name, O_RDONLY);
	if (fd < 0)
		die("cannot open packfile '%s': %s", pack_name,
		    strerror(errno));
	if (fstat(fd, &st)) {
		int err = errno;
		close(fd);
		die("cannot fstat packfile '%s': %s", pack_name,
		    strerror(err));
	}
	pack_size = st.st_size;
	pack_base = mmap(NULL, pack_size, PROT_READ, MAP_PRIVATE, fd, 0);
	if (pack_base == MAP_FAILED) {
		int err = errno;
		close(fd);
		die("cannot mmap packfile '%s': %s", pack_name,
		    strerror(err));
	}
	close(fd);
}

static void parse_pack_header(void)
{
	const struct pack_header *hdr;
	unsigned char sha1[20];
	SHA_CTX ctx;

	/* Ensure there are enough bytes for the header and final SHA1 */
	if (pack_size < sizeof(struct pack_header) + 20)
		die("packfile '%s' is too small", pack_name);

	/* Header consistency check */
	hdr = (void *)pack_base;
	if (hdr->hdr_signature != htonl(PACK_SIGNATURE))
		die("packfile '%s' signature mismatch", pack_name);
	if (!pack_version_ok(hdr->hdr_version))
		die("packfile '%s' version %d unsupported",
		    pack_name, ntohl(hdr->hdr_version));

	nr_objects = ntohl(hdr->hdr_entries);

	/* Check packfile integrity */
	SHA1_Init(&ctx);
	SHA1_Update(&ctx, pack_base, pack_size - 20);
	SHA1_Final(sha1, &ctx);
	if (hashcmp(sha1, pack_base + pack_size - 20))
		die("packfile '%s' SHA1 mismatch", pack_name);
}

static void bad_object(unsigned long offset, const char *format,
		       ...) NORETURN __attribute__((format (printf, 2, 3)));

static void bad_object(unsigned long offset, const char *format, ...)
{
	va_list params;
	char buf[1024];

	va_start(params, format);
	vsnprintf(buf, sizeof(buf), format, params);
	va_end(params);
	die("packfile '%s': bad object at offset %lu: %s",
	    pack_name, offset, buf);
}

static void *unpack_entry_data(unsigned long offset,
			       unsigned long *current_pos, unsigned long size)
{
	unsigned long pack_limit = pack_size - 20;
	unsigned long pos = *current_pos;
	z_stream stream;
	void *buf = xmalloc(size);

	memset(&stream, 0, sizeof(stream));
	stream.next_out = buf;
	stream.avail_out = size;
	stream.next_in = pack_base + pos;
	stream.avail_in = pack_limit - pos;
	inflateInit(&stream);

	for (;;) {
		int ret = inflate(&stream, 0);
		if (ret == Z_STREAM_END)
			break;
		if (ret != Z_OK)
			bad_object(offset, "inflate returned %d", ret);
	}
	inflateEnd(&stream);
	if (stream.total_out != size)
		bad_object(offset, "size mismatch (expected %lu, got %lu)",
			   size, stream.total_out);
	*current_pos = pack_limit - stream.avail_in;
	return buf;
}

static void *unpack_raw_entry(unsigned long offset,
			      enum object_type *obj_type,
			      unsigned long *obj_size,
			      unsigned char *delta_base,
			      unsigned long *next_obj_offset)
{
	unsigned long pack_limit = pack_size - 20;
	unsigned long pos = offset;
	unsigned char c;
	unsigned long size;
	unsigned shift;
	enum object_type type;
	void *data;

	c = pack_base[pos++];
	type = (c >> 4) & 7;
	size = (c & 15);
	shift = 4;
	while (c & 0x80) {
		if (pos >= pack_limit)
			bad_object(offset, "object extends past end of pack");
		c = pack_base[pos++];
		size += (c & 0x7fUL) << shift;
		shift += 7;
	}

	switch (type) {
	case OBJ_REF_DELTA:
		if (pos + 20 >= pack_limit)
			bad_object(offset, "object extends past end of pack");
		hashcpy(delta_base, pack_base + pos);
		pos += 20;
		/* fallthru */
	case OBJ_COMMIT:
	case OBJ_TREE:
	case OBJ_BLOB:
	case OBJ_TAG:
		data = unpack_entry_data(offset, &pos, size);
		break;
	default:
		bad_object(offset, "bad object type %d", type);
	}

	*obj_type = type;
	*obj_size = size;
	*next_obj_offset = pos;
	return data;
}

static int find_delta(const unsigned char *base_sha1)
{
	int first = 0, last = nr_deltas;

        while (first < last) {
                int next = (first + last) / 2;
                struct delta_entry *delta = &deltas[next];
                int cmp;

                cmp = hashcmp(base_sha1, delta->base_sha1);
                if (!cmp)
                        return next;
                if (cmp < 0) {
                        last = next;
                        continue;
                }
                first = next+1;
        }
        return -first-1;
}

static int find_deltas_based_on_sha1(const unsigned char *base_sha1,
				     int *first_index, int *last_index)
{
	int first = find_delta(base_sha1);
	int last = first;
	int end = nr_deltas - 1;

	if (first < 0)
		return -1;
	while (first > 0 && !hashcmp(deltas[first - 1].base_sha1, base_sha1))
		--first;
	while (last < end && !hashcmp(deltas[last + 1].base_sha1, base_sha1))
		++last;
	*first_index = first;
	*last_index = last;
	return 0;
}

static void sha1_object(const void *data, unsigned long size,
			enum object_type type, unsigned char *sha1)
{
	SHA_CTX ctx;
	char header[50];
	int header_size;
	const char *type_str;

	switch (type) {
	case OBJ_COMMIT: type_str = commit_type; break;
	case OBJ_TREE:   type_str = tree_type; break;
	case OBJ_BLOB:   type_str = blob_type; break;
	case OBJ_TAG:    type_str = tag_type; break;
	default:
		die("bad type %d", type);
	}

	header_size = sprintf(header, "%s %lu", type_str, size) + 1;

	SHA1_Init(&ctx);
	SHA1_Update(&ctx, header, header_size);
	SHA1_Update(&ctx, data, size);
	SHA1_Final(sha1, &ctx);
}

static void resolve_delta(struct delta_entry *delta, void *base_data,
			  unsigned long base_size, enum object_type type)
{
	struct object_entry *obj = delta->obj;
	void *delta_data;
	unsigned long delta_size;
	void *result;
	unsigned long result_size;
	enum object_type delta_type;
	unsigned char base_sha1[20];
	unsigned long next_obj_offset;
	int j, first, last;

	obj->real_type = type;
	delta_data = unpack_raw_entry(obj->offset, &delta_type,
				      &delta_size, base_sha1,
				      &next_obj_offset);
	result = patch_delta(base_data, base_size, delta_data, delta_size,
			     &result_size);
	free(delta_data);
	if (!result)
		bad_object(obj->offset, "failed to apply delta");
	sha1_object(result, result_size, type, obj->sha1);
	if (!find_deltas_based_on_sha1(obj->sha1, &first, &last)) {
		for (j = first; j <= last; j++)
			resolve_delta(&deltas[j], result, result_size, type);
	}
	free(result);
}

static int compare_delta_entry(const void *a, const void *b)
{
	const struct delta_entry *delta_a = a;
	const struct delta_entry *delta_b = b;
	return hashcmp(delta_a->base_sha1, delta_b->base_sha1);
}

static void parse_pack_objects(void)
{
	int i;
	unsigned long offset = sizeof(struct pack_header);
	unsigned char base_sha1[20];
	void *data;
	unsigned long data_size;

	/*
	 * First pass:
	 * - find locations of all objects;
	 * - calculate SHA1 of all non-delta objects;
	 * - remember base SHA1 for all deltas.
	 */
	for (i = 0; i < nr_objects; i++) {
		struct object_entry *obj = &objects[i];
		obj->offset = offset;
		data = unpack_raw_entry(offset, &obj->type, &data_size,
					base_sha1, &offset);
		obj->real_type = obj->type;
		if (obj->type == OBJ_REF_DELTA) {
			struct delta_entry *delta = &deltas[nr_deltas++];
			delta->obj = obj;
			hashcpy(delta->base_sha1, base_sha1);
		} else
			sha1_object(data, data_size, obj->type, obj->sha1);
		free(data);
	}
	if (offset != pack_size - 20)
		die("packfile '%s' has junk at the end", pack_name);

	/* Sort deltas by base SHA1 for fast searching */
	qsort(deltas, nr_deltas, sizeof(struct delta_entry),
	      compare_delta_entry);

	/*
	 * Second pass:
	 * - for all non-delta objects, look if it is used as a base for
	 *   deltas;
	 * - if used as a base, uncompress the object and apply all deltas,
	 *   recursively checking if the resulting object is used as a base
	 *   for some more deltas.
	 */
	for (i = 0; i < nr_objects; i++) {
		struct object_entry *obj = &objects[i];
		int j, first, last;

		if (obj->type == OBJ_REF_DELTA)
			continue;
		if (find_deltas_based_on_sha1(obj->sha1, &first, &last))
			continue;
		data = unpack_raw_entry(obj->offset, &obj->type, &data_size,
					base_sha1, &offset);
		for (j = first; j <= last; j++)
			resolve_delta(&deltas[j], data, data_size, obj->type);
		free(data);
	}

	/* Check for unresolved deltas */
	for (i = 0; i < nr_deltas; i++) {
		if (deltas[i].obj->real_type == OBJ_REF_DELTA)
			die("packfile '%s' has unresolved deltas",  pack_name);
	}
}

static int sha1_compare(const void *_a, const void *_b)
{
	struct object_entry *a = *(struct object_entry **)_a;
	struct object_entry *b = *(struct object_entry **)_b;
	return hashcmp(a->sha1, b->sha1);
}

static void write_index_file(const char *index_name, unsigned char *sha1)
{
	struct sha1file *f;
	struct object_entry **sorted_by_sha, **list, **last;
	unsigned int array[256];
	int i;
	SHA_CTX ctx;

	if (nr_objects) {
		sorted_by_sha =
			xcalloc(nr_objects, sizeof(struct object_entry *));
		list = sorted_by_sha;
		last = sorted_by_sha + nr_objects;
		for (i = 0; i < nr_objects; ++i)
			sorted_by_sha[i] = &objects[i];
		qsort(sorted_by_sha, nr_objects, sizeof(sorted_by_sha[0]),
		      sha1_compare);

	}
	else
		sorted_by_sha = list = last = NULL;

	unlink(index_name);
	f = sha1create("%s", index_name);

	/*
	 * 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 *obj = *next;
			if (obj->sha1[0] != i)
				break;
			next++;
		}
		array[i] = htonl(next - sorted_by_sha);
		list = next;
	}
	sha1write(f, array, 256 * sizeof(int));

	/* recompute the SHA1 hash of sorted object names.
	 * currently pack-objects does not do this, but that
	 * can be fixed.
	 */
	SHA1_Init(&ctx);
	/*
	 * Write the actual SHA1 entries..
	 */
	list = sorted_by_sha;
	for (i = 0; i < nr_objects; i++) {
		struct object_entry *obj = *list++;
		unsigned int offset = htonl(obj->offset);
		sha1write(f, &offset, 4);
		sha1write(f, obj->sha1, 20);
		SHA1_Update(&ctx, obj->sha1, 20);
	}
	sha1write(f, pack_base + pack_size - 20, 20);
	sha1close(f, NULL, 1);
	free(sorted_by_sha);
	SHA1_Final(sha1, &ctx);
}

int main(int argc, char **argv)
{
	int i;
	char *index_name = NULL;
	char *index_name_buf = NULL;
	unsigned char sha1[20];

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

		if (*arg == '-') {
			if (!strcmp(arg, "-o")) {
				if (index_name || (i+1) >= argc)
					usage(index_pack_usage);
				index_name = argv[++i];
			} else
				usage(index_pack_usage);
			continue;
		}

		if (pack_name)
			usage(index_pack_usage);
		pack_name = arg;
	}

	if (!pack_name)
		usage(index_pack_usage);
	if (!index_name) {
		int len = strlen(pack_name);
		if (!has_extension(pack_name, ".pack"))
			die("packfile name '%s' does not end with '.pack'",
			    pack_name);
		index_name_buf = xmalloc(len);
		memcpy(index_name_buf, pack_name, len - 5);
		strcpy(index_name_buf + len - 5, ".idx");
		index_name = index_name_buf;
	}

	open_pack_file();
	parse_pack_header();
	objects = xcalloc(nr_objects, sizeof(struct object_entry));
	deltas = xcalloc(nr_objects, sizeof(struct delta_entry));
	parse_pack_objects();
	free(deltas);
	write_index_file(index_name, sha1);
	free(objects);
	free(index_name_buf);

	printf("%s\n", sha1_to_hex(sha1));

	return 0;
}
Commit	Line	Data
9cf6d335 SV	1	#include "cache.h"
	2	#include "delta.h"
	3	#include "pack.h"
	4	#include "csum-file.h"
8e440259 PE	5	#include "blob.h"
	6	#include "commit.h"
	7	#include "tag.h"
	8	#include "tree.h"
9cf6d335 SV	9
	10	static const char index_pack_usage[] =
	11	"git-index-pack [-o index-file] pack-file";
	12
	13	struct object_entry
	14	{
	15	unsigned long offset;
	16	enum object_type type;
	17	enum object_type real_type;
	18	unsigned char sha1[20];
	19	};
	20
	21	struct delta_entry
	22	{
	23	struct object_entry *obj;
	24	unsigned char base_sha1[20];
	25	};
	26
	27	static const char *pack_name;
	28	static unsigned char *pack_base;
	29	static unsigned long pack_size;
	30	static struct object_entry *objects;
	31	static struct delta_entry *deltas;
	32	static int nr_objects;
	33	static int nr_deltas;
	34
	35	static void open_pack_file(void)
	36	{
	37	int fd;
	38	struct stat st;
	39
	40	fd = open(pack_name, O_RDONLY);
	41	if (fd < 0)
	42	die("cannot open packfile '%s': %s", pack_name,
	43	strerror(errno));
	44	if (fstat(fd, &st)) {
	45	int err = errno;
	46	close(fd);
	47	die("cannot fstat packfile '%s': %s", pack_name,
	48	strerror(err));
	49	}
	50	pack_size = st.st_size;
	51	pack_base = mmap(NULL, pack_size, PROT_READ, MAP_PRIVATE, fd, 0);
	52	if (pack_base == MAP_FAILED) {
	53	int err = errno;
	54	close(fd);
	55	die("cannot mmap packfile '%s': %s", pack_name,
	56	strerror(err));
	57	}
	58	close(fd);
	59	}
	60
	61	static void parse_pack_header(void)
	62	{
	63	const struct pack_header *hdr;
	64	unsigned char sha1[20];
	65	SHA_CTX ctx;
	66
	67	/* Ensure there are enough bytes for the header and final SHA1 */
	68	if (pack_size < sizeof(struct pack_header) + 20)
	69	die("packfile '%s' is too small", pack_name);
	70
	71	/* Header consistency check */
	72	hdr = (void *)pack_base;
73	if (hdr->hdr_signature != htonl(PACK_SIGNATURE))
74	die("packfile '%s' signature mismatch", pack_name);
d60fc1c8 NP	75	if (!pack_version_ok(hdr->hdr_version))
	76	die("packfile '%s' version %d unsupported",
	77	pack_name, ntohl(hdr->hdr_version));
9cf6d335 SV	78
	79	nr_objects = ntohl(hdr->hdr_entries);
	80
	81	/* Check packfile integrity */
	82	SHA1_Init(&ctx);
	83	SHA1_Update(&ctx, pack_base, pack_size - 20);
	84	SHA1_Final(sha1, &ctx);
a89fccd2	85	if (hashcmp(sha1, pack_base + pack_size - 20))
9cf6d335 SV	86	die("packfile '%s' SHA1 mismatch", pack_name);
	87	}
	88
	89	static void bad_object(unsigned long offset, const char *format,
	90	...) NORETURN __attribute__((format (printf, 2, 3)));
	91
	92	static void bad_object(unsigned long offset, const char *format, ...)
	93	{
	94	va_list params;
	95	char buf[1024];
	96
	97	va_start(params, format);
	98	vsnprintf(buf, sizeof(buf), format, params);
	99	va_end(params);
	100	die("packfile '%s': bad object at offset %lu: %s",
	101	pack_name, offset, buf);
	102	}
	103
	104	static void *unpack_entry_data(unsigned long offset,
	105	unsigned long *current_pos, unsigned long size)
	106	{
	107	unsigned long pack_limit = pack_size - 20;
	108	unsigned long pos = *current_pos;
	109	z_stream stream;
	110	void *buf = xmalloc(size);
	111
	112	memset(&stream, 0, sizeof(stream));
	113	stream.next_out = buf;
	114	stream.avail_out = size;
	115	stream.next_in = pack_base + pos;
	116	stream.avail_in = pack_limit - pos;
	117	inflateInit(&stream);
	118
	119	for (;;) {
	120	int ret = inflate(&stream, 0);
	121	if (ret == Z_STREAM_END)
	122	break;
	123	if (ret != Z_OK)
	124	bad_object(offset, "inflate returned %d", ret);
	125	}
	126	inflateEnd(&stream);
	127	if (stream.total_out != size)
	128	bad_object(offset, "size mismatch (expected %lu, got %lu)",
	129	size, stream.total_out);
	130	*current_pos = pack_limit - stream.avail_in;
	131	return buf;
	132	}
	133
	134	static void *unpack_raw_entry(unsigned long offset,
	135	enum object_type *obj_type,
	136	unsigned long *obj_size,
	137	unsigned char *delta_base,
	138	unsigned long *next_obj_offset)
	139	{
	140	unsigned long pack_limit = pack_size - 20;
	141	unsigned long pos = offset;
	142	unsigned char c;
	143	unsigned long size;
	144	unsigned shift;
	145	enum object_type type;
	146	void *data;
	147
	148	c = pack_base[pos++];
	149	type = (c >> 4) & 7;
150	size = (c & 15);
151	shift = 4;
152	while (c & 0x80) {
153	if (pos >= pack_limit)
154	bad_object(offset, "object extends past end of pack");
155	c = pack_base[pos++];
156	size += (c & 0x7fUL) << shift;
157	shift += 7;
158	}
159
160	switch (type) {
eb32d236	161	case OBJ_REF_DELTA:
9cf6d335 SV	162	if (pos + 20 >= pack_limit)
9cf6d335 SV	163	bad_object(offset, "object extends past end of pack");
e702496e	164	hashcpy(delta_base, pack_base + pos);
9cf6d335 SV	165	pos += 20;
	166	/* fallthru */
	167	case OBJ_COMMIT:
	168	case OBJ_TREE:
	169	case OBJ_BLOB:
	170	case OBJ_TAG:
	171	data = unpack_entry_data(offset, &pos, size);
	172	break;
	173	default:
	174	bad_object(offset, "bad object type %d", type);
	175	}
	176
	177	*obj_type = type;
	178	*obj_size = size;
	179	*next_obj_offset = pos;
	180	return data;
	181	}
	182
	183	static int find_delta(const unsigned char *base_sha1)
	184	{
	185	int first = 0, last = nr_deltas;
	186
	187	while (first < last) {
	188	int next = (first + last) / 2;
	189	struct delta_entry *delta = &deltas[next];
	190	int cmp;
	191
a89fccd2	192	cmp = hashcmp(base_sha1, delta->base_sha1);
9cf6d335 SV	193	if (!cmp)
	194	return next;
	195	if (cmp < 0) {
	196	last = next;
	197	continue;
	198	}
	199	first = next+1;
	200	}
	201	return -first-1;
	202	}
	203
	204	static int find_deltas_based_on_sha1(const unsigned char *base_sha1,
	205	int first_index, int last_index)
	206	{
	207	int first = find_delta(base_sha1);
	208	int last = first;
	209	int end = nr_deltas - 1;
	210
	211	if (first < 0)
	212	return -1;
a89fccd2	213	while (first > 0 && !hashcmp(deltas[first - 1].base_sha1, base_sha1))
9cf6d335	214	--first;
a89fccd2	215	while (last < end && !hashcmp(deltas[last + 1].base_sha1, base_sha1))
9cf6d335 SV	216	++last;
	217	*first_index = first;
	218	*last_index = last;
	219	return 0;
	220	}
	221
	222	static void sha1_object(const void *data, unsigned long size,
	223	enum object_type type, unsigned char *sha1)
	224	{
	225	SHA_CTX ctx;
	226	char header[50];
	227	int header_size;
	228	const char *type_str;
	229
	230	switch (type) {
8e440259 PE	231	case OBJ_COMMIT: type_str = commit_type; break;
	232	case OBJ_TREE: type_str = tree_type; break;
	233	case OBJ_BLOB: type_str = blob_type; break;
	234	case OBJ_TAG: type_str = tag_type; break;
9cf6d335 SV	235	default:
	236	die("bad type %d", type);
	237	}
	238
	239	header_size = sprintf(header, "%s %lu", type_str, size) + 1;
	240
	241	SHA1_Init(&ctx);
	242	SHA1_Update(&ctx, header, header_size);
	243	SHA1_Update(&ctx, data, size);
	244	SHA1_Final(sha1, &ctx);
	245	}
	246
	247	static void resolve_delta(struct delta_entry delta, void base_data,
	248	unsigned long base_size, enum object_type type)
	249	{
	250	struct object_entry *obj = delta->obj;
	251	void *delta_data;
	252	unsigned long delta_size;
	253	void *result;
	254	unsigned long result_size;
	255	enum object_type delta_type;
	256	unsigned char base_sha1[20];
	257	unsigned long next_obj_offset;
	258	int j, first, last;
	259
	260	obj->real_type = type;
	261	delta_data = unpack_raw_entry(obj->offset, &delta_type,
	262	&delta_size, base_sha1,
	263	&next_obj_offset);
	264	result = patch_delta(base_data, base_size, delta_data, delta_size,
	265	&result_size);
	266	free(delta_data);
	267	if (!result)
	268	bad_object(obj->offset, "failed to apply delta");
	269	sha1_object(result, result_size, type, obj->sha1);
	270	if (!find_deltas_based_on_sha1(obj->sha1, &first, &last)) {
	271	for (j = first; j <= last; j++)
	272	resolve_delta(&deltas[j], result, result_size, type);
	273	}
	274	free(result);
	275	}
	276
	277	static int compare_delta_entry(const void a, const void b)
	278	{
	279	const struct delta_entry *delta_a = a;
	280	const struct delta_entry *delta_b = b;
a89fccd2	281	return hashcmp(delta_a->base_sha1, delta_b->base_sha1);
9cf6d335 SV	282	}
	283
	284	static void parse_pack_objects(void)
	285	{
	286	int i;
	287	unsigned long offset = sizeof(struct pack_header);
	288	unsigned char base_sha1[20];
	289	void *data;
	290	unsigned long data_size;
	291
	292	/*
	293	* First pass:
	294	* - find locations of all objects;
	295	* - calculate SHA1 of all non-delta objects;
	296	* - remember base SHA1 for all deltas.
	297	*/
	298	for (i = 0; i < nr_objects; i++) {
	299	struct object_entry *obj = &objects[i];
	300	obj->offset = offset;
	301	data = unpack_raw_entry(offset, &obj->type, &data_size,
	302	base_sha1, &offset);
	303	obj->real_type = obj->type;
eb32d236	304	if (obj->type == OBJ_REF_DELTA) {
9cf6d335 SV	305	struct delta_entry *delta = &deltas[nr_deltas++];
9cf6d335 SV	306	delta->obj = obj;
e702496e	307	hashcpy(delta->base_sha1, base_sha1);
9cf6d335 SV	308	} else
	309	sha1_object(data, data_size, obj->type, obj->sha1);
	310	free(data);
	311	}
	312	if (offset != pack_size - 20)
	313	die("packfile '%s' has junk at the end", pack_name);
	314
	315	/* Sort deltas by base SHA1 for fast searching */
	316	qsort(deltas, nr_deltas, sizeof(struct delta_entry),
	317	compare_delta_entry);
	318
	319	/*
	320	* Second pass:
	321	* - for all non-delta objects, look if it is used as a base for
	322	* deltas;
	323	* - if used as a base, uncompress the object and apply all deltas,
	324	* recursively checking if the resulting object is used as a base
	325	* for some more deltas.
	326	*/
	327	for (i = 0; i < nr_objects; i++) {
	328	struct object_entry *obj = &objects[i];
	329	int j, first, last;
	330
eb32d236	331	if (obj->type == OBJ_REF_DELTA)
9cf6d335 SV	332	continue;
	333	if (find_deltas_based_on_sha1(obj->sha1, &first, &last))
	334	continue;
	335	data = unpack_raw_entry(obj->offset, &obj->type, &data_size,
	336	base_sha1, &offset);
	337	for (j = first; j <= last; j++)
	338	resolve_delta(&deltas[j], data, data_size, obj->type);
	339	free(data);
	340	}
	341
	342	/* Check for unresolved deltas */
	343	for (i = 0; i < nr_deltas; i++) {
eb32d236	344	if (deltas[i].obj->real_type == OBJ_REF_DELTA)
9cf6d335 SV	345	die("packfile '%s' has unresolved deltas", pack_name);
	346	}
	347	}
	348
	349	static int sha1_compare(const void _a, const void _b)
	350	{
	351	struct object_entry a = (struct object_entry **)_a;
	352	struct object_entry b = (struct object_entry **)_b;
a89fccd2	353	return hashcmp(a->sha1, b->sha1);
9cf6d335 SV	354	}
9cf6d335 SV	355
84c8d8ae	356	static void write_index_file(const char index_name, unsigned char sha1)
9cf6d335 SV	357	{
9cf6d335 SV	358	struct sha1file *f;
7e4a2a84	359	struct object_entry sorted_by_sha, list, **last;
9cf6d335 SV	360	unsigned int array[256];
9cf6d335 SV	361	int i;
84c8d8ae	362	SHA_CTX ctx;
9cf6d335	363
7e4a2a84 JH	364	if (nr_objects) {
	365	sorted_by_sha =
	366	xcalloc(nr_objects, sizeof(struct object_entry *));
	367	list = sorted_by_sha;
	368	last = sorted_by_sha + nr_objects;
	369	for (i = 0; i < nr_objects; ++i)
	370	sorted_by_sha[i] = &objects[i];
	371	qsort(sorted_by_sha, nr_objects, sizeof(sorted_by_sha[0]),
	372	sha1_compare);
	373
	374	}
	375	else
	376	sorted_by_sha = list = last = NULL;
9cf6d335 SV	377
	378	unlink(index_name);
	379	f = sha1create("%s", index_name);
	380
	381	/*
	382	* Write the first-level table (the list is sorted,
	383	* but we use a 256-entry lookup to be able to avoid
	384	* having to do eight extra binary search iterations).
	385	*/
	386	for (i = 0; i < 256; i++) {
	387	struct object_entry **next = list;
	388	while (next < last) {
	389	struct object_entry obj = next;
	390	if (obj->sha1[0] != i)
	391	break;
	392	next++;
	393	}
	394	array[i] = htonl(next - sorted_by_sha);
	395	list = next;
	396	}
	397	sha1write(f, array, 256 * sizeof(int));
	398
84c8d8ae JH	399	/* recompute the SHA1 hash of sorted object names.
	400	* currently pack-objects does not do this, but that
	401	* can be fixed.
	402	*/
	403	SHA1_Init(&ctx);
9cf6d335 SV	404	/*
	405	* Write the actual SHA1 entries..
	406	*/
	407	list = sorted_by_sha;
	408	for (i = 0; i < nr_objects; i++) {
	409	struct object_entry obj = list++;
	410	unsigned int offset = htonl(obj->offset);
	411	sha1write(f, &offset, 4);
	412	sha1write(f, obj->sha1, 20);
84c8d8ae	413	SHA1_Update(&ctx, obj->sha1, 20);
9cf6d335 SV	414	}
	415	sha1write(f, pack_base + pack_size - 20, 20);
	416	sha1close(f, NULL, 1);
	417	free(sorted_by_sha);
84c8d8ae	418	SHA1_Final(sha1, &ctx);
9cf6d335 SV	419	}
	420
	421	int main(int argc, char **argv)
	422	{
	423	int i;
	424	char *index_name = NULL;
	425	char *index_name_buf = NULL;
84c8d8ae	426	unsigned char sha1[20];
9cf6d335 SV	427
	428	for (i = 1; i < argc; i++) {
	429	const char *arg = argv[i];
	430
	431	if (*arg == '-') {
	432	if (!strcmp(arg, "-o")) {
	433	if (index_name \|\| (i+1) >= argc)
	434	usage(index_pack_usage);
	435	index_name = argv[++i];
	436	} else
	437	usage(index_pack_usage);
	438	continue;
	439	}
	440
	441	if (pack_name)
	442	usage(index_pack_usage);
	443	pack_name = arg;
	444	}
	445
	446	if (!pack_name)
	447	usage(index_pack_usage);
	448	if (!index_name) {
	449	int len = strlen(pack_name);
5bb1cda5	450	if (!has_extension(pack_name, ".pack"))
9cf6d335 SV	451	die("packfile name '%s' does not end with '.pack'",
9cf6d335 SV	452	pack_name);
6689f087	453	index_name_buf = xmalloc(len);
9cf6d335 SV	454	memcpy(index_name_buf, pack_name, len - 5);
	455	strcpy(index_name_buf + len - 5, ".idx");
	456	index_name = index_name_buf;
	457	}
	458
	459	open_pack_file();
	460	parse_pack_header();
	461	objects = xcalloc(nr_objects, sizeof(struct object_entry));
	462	deltas = xcalloc(nr_objects, sizeof(struct delta_entry));
	463	parse_pack_objects();
	464	free(deltas);
84c8d8ae	465	write_index_file(index_name, sha1);
9cf6d335 SV	466	free(objects);
	467	free(index_name_buf);
	468
84c8d8ae JH	469	printf("%s\n", sha1_to_hex(sha1));
84c8d8ae JH	470
9cf6d335 SV	471	return 0;
9cf6d335 SV	472	}