[thirdparty/git.git] / diff-delta.c

/*
 * diff-delta.c: generate a delta between two buffers
 *
 * This code was greatly inspired by parts of LibXDiff from Davide Libenzi
 * http://www.xmailserver.org/xdiff-lib.html
 *
 * Rewritten for GIT by Nicolas Pitre <nico@fluxnic.net>, (C) 2005-2007
 *
 * This code is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation.
 */

#include "git-compat-util.h"
#include "delta.h"

/* maximum hash entry list for the same hash bucket */
#define HASH_LIMIT 64

#define RABIN_SHIFT 23
#define RABIN_WINDOW 16

static const unsigned int T[256] = {
	0x00000000, 0xab59b4d1, 0x56b369a2, 0xfdeadd73, 0x063f6795, 0xad66d344,
	0x508c0e37, 0xfbd5bae6, 0x0c7ecf2a, 0xa7277bfb, 0x5acda688, 0xf1941259,
	0x0a41a8bf, 0xa1181c6e, 0x5cf2c11d, 0xf7ab75cc, 0x18fd9e54, 0xb3a42a85,
	0x4e4ef7f6, 0xe5174327, 0x1ec2f9c1, 0xb59b4d10, 0x48719063, 0xe32824b2,
	0x1483517e, 0xbfdae5af, 0x423038dc, 0xe9698c0d, 0x12bc36eb, 0xb9e5823a,
	0x440f5f49, 0xef56eb98, 0x31fb3ca8, 0x9aa28879, 0x6748550a, 0xcc11e1db,
	0x37c45b3d, 0x9c9defec, 0x6177329f, 0xca2e864e, 0x3d85f382, 0x96dc4753,
	0x6b369a20, 0xc06f2ef1, 0x3bba9417, 0x90e320c6, 0x6d09fdb5, 0xc6504964,
	0x2906a2fc, 0x825f162d, 0x7fb5cb5e, 0xd4ec7f8f, 0x2f39c569, 0x846071b8,
	0x798aaccb, 0xd2d3181a, 0x25786dd6, 0x8e21d907, 0x73cb0474, 0xd892b0a5,
	0x23470a43, 0x881ebe92, 0x75f463e1, 0xdeadd730, 0x63f67950, 0xc8afcd81,
	0x354510f2, 0x9e1ca423, 0x65c91ec5, 0xce90aa14, 0x337a7767, 0x9823c3b6,
	0x6f88b67a, 0xc4d102ab, 0x393bdfd8, 0x92626b09, 0x69b7d1ef, 0xc2ee653e,
	0x3f04b84d, 0x945d0c9c, 0x7b0be704, 0xd05253d5, 0x2db88ea6, 0x86e13a77,
	0x7d348091, 0xd66d3440, 0x2b87e933, 0x80de5de2, 0x7775282e, 0xdc2c9cff,
	0x21c6418c, 0x8a9ff55d, 0x714a4fbb, 0xda13fb6a, 0x27f92619, 0x8ca092c8,
	0x520d45f8, 0xf954f129, 0x04be2c5a, 0xafe7988b, 0x5432226d, 0xff6b96bc,
	0x02814bcf, 0xa9d8ff1e, 0x5e738ad2, 0xf52a3e03, 0x08c0e370, 0xa39957a1,
	0x584ced47, 0xf3155996, 0x0eff84e5, 0xa5a63034, 0x4af0dbac, 0xe1a96f7d,
	0x1c43b20e, 0xb71a06df, 0x4ccfbc39, 0xe79608e8, 0x1a7cd59b, 0xb125614a,
	0x468e1486, 0xedd7a057, 0x103d7d24, 0xbb64c9f5, 0x40b17313, 0xebe8c7c2,
	0x16021ab1, 0xbd5bae60, 0x6cb54671, 0xc7ecf2a0, 0x3a062fd3, 0x915f9b02,
	0x6a8a21e4, 0xc1d39535, 0x3c394846, 0x9760fc97, 0x60cb895b, 0xcb923d8a,
	0x3678e0f9, 0x9d215428, 0x66f4eece, 0xcdad5a1f, 0x3047876c, 0x9b1e33bd,
	0x7448d825, 0xdf116cf4, 0x22fbb187, 0x89a20556, 0x7277bfb0, 0xd92e0b61,
	0x24c4d612, 0x8f9d62c3, 0x7836170f, 0xd36fa3de, 0x2e857ead, 0x85dcca7c,
	0x7e09709a, 0xd550c44b, 0x28ba1938, 0x83e3ade9, 0x5d4e7ad9, 0xf617ce08,
	0x0bfd137b, 0xa0a4a7aa, 0x5b711d4c, 0xf028a99d, 0x0dc274ee, 0xa69bc03f,
	0x5130b5f3, 0xfa690122, 0x0783dc51, 0xacda6880, 0x570fd266, 0xfc5666b7,
	0x01bcbbc4, 0xaae50f15, 0x45b3e48d, 0xeeea505c, 0x13008d2f, 0xb85939fe,
	0x438c8318, 0xe8d537c9, 0x153feaba, 0xbe665e6b, 0x49cd2ba7, 0xe2949f76,
	0x1f7e4205, 0xb427f6d4, 0x4ff24c32, 0xe4abf8e3, 0x19412590, 0xb2189141,
	0x0f433f21, 0xa41a8bf0, 0x59f05683, 0xf2a9e252, 0x097c58b4, 0xa225ec65,
	0x5fcf3116, 0xf49685c7, 0x033df00b, 0xa86444da, 0x558e99a9, 0xfed72d78,
	0x0502979e, 0xae5b234f, 0x53b1fe3c, 0xf8e84aed, 0x17bea175, 0xbce715a4,
	0x410dc8d7, 0xea547c06, 0x1181c6e0, 0xbad87231, 0x4732af42, 0xec6b1b93,
	0x1bc06e5f, 0xb099da8e, 0x4d7307fd, 0xe62ab32c, 0x1dff09ca, 0xb6a6bd1b,
	0x4b4c6068, 0xe015d4b9, 0x3eb80389, 0x95e1b758, 0x680b6a2b, 0xc352defa,
	0x3887641c, 0x93ded0cd, 0x6e340dbe, 0xc56db96f, 0x32c6cca3, 0x999f7872,
	0x6475a501, 0xcf2c11d0, 0x34f9ab36, 0x9fa01fe7, 0x624ac294, 0xc9137645,
	0x26459ddd, 0x8d1c290c, 0x70f6f47f, 0xdbaf40ae, 0x207afa48, 0x8b234e99,
	0x76c993ea, 0xdd90273b, 0x2a3b52f7, 0x8162e626, 0x7c883b55, 0xd7d18f84,
	0x2c043562, 0x875d81b3, 0x7ab75cc0, 0xd1eee811
};

static const unsigned int U[256] = {
	0x00000000, 0x7eb5200d, 0x5633f4cb, 0x2886d4c6, 0x073e5d47, 0x798b7d4a,
	0x510da98c, 0x2fb88981, 0x0e7cba8e, 0x70c99a83, 0x584f4e45, 0x26fa6e48,
	0x0942e7c9, 0x77f7c7c4, 0x5f711302, 0x21c4330f, 0x1cf9751c, 0x624c5511,
	0x4aca81d7, 0x347fa1da, 0x1bc7285b, 0x65720856, 0x4df4dc90, 0x3341fc9d,
	0x1285cf92, 0x6c30ef9f, 0x44b63b59, 0x3a031b54, 0x15bb92d5, 0x6b0eb2d8,
	0x4388661e, 0x3d3d4613, 0x39f2ea38, 0x4747ca35, 0x6fc11ef3, 0x11743efe,
	0x3eccb77f, 0x40799772, 0x68ff43b4, 0x164a63b9, 0x378e50b6, 0x493b70bb,
	0x61bda47d, 0x1f088470, 0x30b00df1, 0x4e052dfc, 0x6683f93a, 0x1836d937,
	0x250b9f24, 0x5bbebf29, 0x73386bef, 0x0d8d4be2, 0x2235c263, 0x5c80e26e,
	0x740636a8, 0x0ab316a5, 0x2b7725aa, 0x55c205a7, 0x7d44d161, 0x03f1f16c,
	0x2c4978ed, 0x52fc58e0, 0x7a7a8c26, 0x04cfac2b, 0x73e5d470, 0x0d50f47d,
	0x25d620bb, 0x5b6300b6, 0x74db8937, 0x0a6ea93a, 0x22e87dfc, 0x5c5d5df1,
	0x7d996efe, 0x032c4ef3, 0x2baa9a35, 0x551fba38, 0x7aa733b9, 0x041213b4,
	0x2c94c772, 0x5221e77f, 0x6f1ca16c, 0x11a98161, 0x392f55a7, 0x479a75aa,
	0x6822fc2b, 0x1697dc26, 0x3e1108e0, 0x40a428ed, 0x61601be2, 0x1fd53bef,
	0x3753ef29, 0x49e6cf24, 0x665e46a5, 0x18eb66a8, 0x306db26e, 0x4ed89263,
	0x4a173e48, 0x34a21e45, 0x1c24ca83, 0x6291ea8e, 0x4d29630f, 0x339c4302,
	0x1b1a97c4, 0x65afb7c9, 0x446b84c6, 0x3adea4cb, 0x1258700d, 0x6ced5000,
	0x4355d981, 0x3de0f98c, 0x15662d4a, 0x6bd30d47, 0x56ee4b54, 0x285b6b59,
	0x00ddbf9f, 0x7e689f92, 0x51d01613, 0x2f65361e, 0x07e3e2d8, 0x7956c2d5,
	0x5892f1da, 0x2627d1d7, 0x0ea10511, 0x7014251c, 0x5facac9d, 0x21198c90,
	0x099f5856, 0x772a785b, 0x4c921c31, 0x32273c3c, 0x1aa1e8fa, 0x6414c8f7,
	0x4bac4176, 0x3519617b, 0x1d9fb5bd, 0x632a95b0, 0x42eea6bf, 0x3c5b86b2,
	0x14dd5274, 0x6a687279, 0x45d0fbf8, 0x3b65dbf5, 0x13e30f33, 0x6d562f3e,
	0x506b692d, 0x2ede4920, 0x06589de6, 0x78edbdeb, 0x5755346a, 0x29e01467,
	0x0166c0a1, 0x7fd3e0ac, 0x5e17d3a3, 0x20a2f3ae, 0x08242768, 0x76910765,
	0x59298ee4, 0x279caee9, 0x0f1a7a2f, 0x71af5a22, 0x7560f609, 0x0bd5d604,
	0x235302c2, 0x5de622cf, 0x725eab4e, 0x0ceb8b43, 0x246d5f85, 0x5ad87f88,
	0x7b1c4c87, 0x05a96c8a, 0x2d2fb84c, 0x539a9841, 0x7c2211c0, 0x029731cd,
	0x2a11e50b, 0x54a4c506, 0x69998315, 0x172ca318, 0x3faa77de, 0x411f57d3,
	0x6ea7de52, 0x1012fe5f, 0x38942a99, 0x46210a94, 0x67e5399b, 0x19501996,
	0x31d6cd50, 0x4f63ed5d, 0x60db64dc, 0x1e6e44d1, 0x36e89017, 0x485db01a,
	0x3f77c841, 0x41c2e84c, 0x69443c8a, 0x17f11c87, 0x38499506, 0x46fcb50b,
	0x6e7a61cd, 0x10cf41c0, 0x310b72cf, 0x4fbe52c2, 0x67388604, 0x198da609,
	0x36352f88, 0x48800f85, 0x6006db43, 0x1eb3fb4e, 0x238ebd5d, 0x5d3b9d50,
	0x75bd4996, 0x0b08699b, 0x24b0e01a, 0x5a05c017, 0x728314d1, 0x0c3634dc,
	0x2df207d3, 0x534727de, 0x7bc1f318, 0x0574d315, 0x2acc5a94, 0x54797a99,
	0x7cffae5f, 0x024a8e52, 0x06852279, 0x78300274, 0x50b6d6b2, 0x2e03f6bf,
	0x01bb7f3e, 0x7f0e5f33, 0x57888bf5, 0x293dabf8, 0x08f998f7, 0x764cb8fa,
	0x5eca6c3c, 0x207f4c31, 0x0fc7c5b0, 0x7172e5bd, 0x59f4317b, 0x27411176,
	0x1a7c5765, 0x64c97768, 0x4c4fa3ae, 0x32fa83a3, 0x1d420a22, 0x63f72a2f,
	0x4b71fee9, 0x35c4dee4, 0x1400edeb, 0x6ab5cde6, 0x42331920, 0x3c86392d,
	0x133eb0ac, 0x6d8b90a1, 0x450d4467, 0x3bb8646a
};

struct index_entry {
	const unsigned char *ptr;
	unsigned int val;
};

struct unpacked_index_entry {
	struct index_entry entry;
	struct unpacked_index_entry *next;
};

struct delta_index {
	unsigned long memsize;
	const void *src_buf;
	unsigned long src_size;
	unsigned int hash_mask;
	struct index_entry *hash[FLEX_ARRAY];
};

struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
{
	unsigned int i, hsize, hmask, entries, prev_val, *hash_count;
	const unsigned char *data, *buffer = buf;
	struct delta_index *index;
	struct unpacked_index_entry *entry, **hash;
	struct index_entry *packed_entry, **packed_hash;
	void *mem;
	unsigned long memsize;

	if (!buf || !bufsize)
		return NULL;

	/* Determine index hash size.  Note that indexing skips the
	   first byte to allow for optimizing the Rabin's polynomial
	   initialization in create_delta(). */
	entries = (bufsize - 1)  / RABIN_WINDOW;
	hsize = entries / 4;
	for (i = 4; (1u << i) < hsize && i < 31; i++);
	hsize = 1 << i;
	hmask = hsize - 1;

	/* allocate lookup index */
	memsize = sizeof(*hash) * hsize +
		  sizeof(*entry) * entries;
	mem = malloc(memsize);
	if (!mem)
		return NULL;
	hash = mem;
	mem = hash + hsize;
	entry = mem;

	memset(hash, 0, hsize * sizeof(*hash));

	/* allocate an array to count hash entries */
	hash_count = calloc(hsize, sizeof(*hash_count));
	if (!hash_count) {
		free(hash);
		return NULL;
	}

	/* then populate the index */
	prev_val = ~0;
	for (data = buffer + entries * RABIN_WINDOW - RABIN_WINDOW;
	     data >= buffer;
	     data -= RABIN_WINDOW) {
		unsigned int val = 0;
		for (i = 1; i <= RABIN_WINDOW; i++)
			val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];
		if (val == prev_val) {
			/* keep the lowest of consecutive identical blocks */
			entry[-1].entry.ptr = data + RABIN_WINDOW;
			--entries;
		} else {
			prev_val = val;
			i = val & hmask;
			entry->entry.ptr = data + RABIN_WINDOW;
			entry->entry.val = val;
			entry->next = hash[i];
			hash[i] = entry++;
			hash_count[i]++;
		}
	}

	/*
	 * Determine a limit on the number of entries in the same hash
	 * bucket.  This guards us against pathological data sets causing
	 * really bad hash distribution with most entries in the same hash
	 * bucket that would bring us to O(m*n) computing costs (m and n
	 * corresponding to reference and target buffer sizes).
	 *
	 * Make sure none of the hash buckets has more entries than
	 * we're willing to test.  Otherwise we cull the entry list
	 * uniformly to still preserve a good repartition across
	 * the reference buffer.
	 */
	for (i = 0; i < hsize; i++) {
		int acc;

		if (hash_count[i] <= HASH_LIMIT)
			continue;

		/* We leave exactly HASH_LIMIT entries in the bucket */
		entries -= hash_count[i] - HASH_LIMIT;

		entry = hash[i];
		acc = 0;

		/*
		 * Assume that this loop is gone through exactly
		 * HASH_LIMIT times and is entered and left with
		 * acc==0.  So the first statement in the loop
		 * contributes (hash_count[i]-HASH_LIMIT)*HASH_LIMIT
		 * to the accumulator, and the inner loop consequently
		 * is run (hash_count[i]-HASH_LIMIT) times, removing
		 * one element from the list each time.  Since acc
		 * balances out to 0 at the final run, the inner loop
		 * body can't be left with entry==NULL.  So we indeed
		 * encounter entry==NULL in the outer loop only.
		 */
		do {
			acc += hash_count[i] - HASH_LIMIT;
			if (acc > 0) {
				struct unpacked_index_entry *keep = entry;
				do {
					entry = entry->next;
					acc -= HASH_LIMIT;
				} while (acc > 0);
				keep->next = entry->next;
			}
			entry = entry->next;
		} while (entry);
	}
	free(hash_count);

	/*
	 * Now create the packed index in array form
	 * rather than linked lists.
	 */
	memsize = sizeof(*index)
		+ sizeof(*packed_hash) * (hsize+1)
		+ sizeof(*packed_entry) * entries;
	mem = malloc(memsize);
	if (!mem) {
		free(hash);
		return NULL;
	}

	index = mem;
	index->memsize = memsize;
	index->src_buf = buf;
	index->src_size = bufsize;
	index->hash_mask = hmask;

	mem = index->hash;
	packed_hash = mem;
	mem = packed_hash + (hsize+1);
	packed_entry = mem;

	for (i = 0; i < hsize; i++) {
		/*
		 * Coalesce all entries belonging to one linked list
		 * into consecutive array entries.
		 */
		packed_hash[i] = packed_entry;
		for (entry = hash[i]; entry; entry = entry->next)
			*packed_entry++ = entry->entry;
	}

	/* Sentinel value to indicate the length of the last hash bucket */
	packed_hash[hsize] = packed_entry;

	assert(packed_entry - (struct index_entry *)mem == entries);
	free(hash);

	return index;
}

void free_delta_index(struct delta_index *index)
{
	free(index);
}

unsigned long sizeof_delta_index(struct delta_index *index)
{
	if (index)
		return index->memsize;
	else
		return 0;
}

/*
 * The maximum size for any opcode sequence, including the initial header
 * plus Rabin window plus biggest copy.
 */
#define MAX_OP_SIZE	(5 + 5 + 1 + RABIN_WINDOW + 7)

void *
create_delta(const struct delta_index *index,
	     const void *trg_buf, unsigned long trg_size,
	     unsigned long *delta_size, unsigned long max_size)
{
	unsigned int i, outpos, outsize, moff, msize, val;
	int inscnt;
	const unsigned char *ref_data, *ref_top, *data, *top;
	unsigned char *out;

	if (!trg_buf || !trg_size)
		return NULL;

	outpos = 0;
	outsize = 8192;
	if (max_size && outsize >= max_size)
		outsize = max_size + MAX_OP_SIZE + 1;
	out = malloc(outsize);
	if (!out)
		return NULL;

	/* store reference buffer size */
	i = index->src_size;
	while (i >= 0x80) {
		out[outpos++] = i | 0x80;
		i >>= 7;
	}
	out[outpos++] = i;

	/* store target buffer size */
	i = trg_size;
	while (i >= 0x80) {
		out[outpos++] = i | 0x80;
		i >>= 7;
	}
	out[outpos++] = i;

	ref_data = index->src_buf;
	ref_top = ref_data + index->src_size;
	data = trg_buf;
	top = (const unsigned char *) trg_buf + trg_size;

	outpos++;
	val = 0;
	for (i = 0; i < RABIN_WINDOW && data < top; i++, data++) {
		out[outpos++] = *data;
		val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];
	}
	inscnt = i;

	moff = 0;
	msize = 0;
	while (data < top) {
		if (msize < 4096) {
			struct index_entry *entry;
			val ^= U[data[-RABIN_WINDOW]];
			val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];
			i = val & index->hash_mask;
			for (entry = index->hash[i]; entry < index->hash[i+1]; entry++) {
				const unsigned char *ref = entry->ptr;
				const unsigned char *src = data;
				unsigned int ref_size = ref_top - ref;
				if (entry->val != val)
					continue;
				if (ref_size > top - src)
					ref_size = top - src;
				if (ref_size <= msize)
					break;
				while (ref_size-- && *src++ == *ref)
					ref++;
				if (msize < ref - entry->ptr) {
					/* this is our best match so far */
					msize = ref - entry->ptr;
					moff = entry->ptr - ref_data;
					if (msize >= 4096) /* good enough */
						break;
				}
			}
		}

		if (msize < 4) {
			if (!inscnt)
				outpos++;
			out[outpos++] = *data++;
			inscnt++;
			if (inscnt == 0x7f) {
				out[outpos - inscnt - 1] = inscnt;
				inscnt = 0;
			}
			msize = 0;
		} else {
			unsigned int left;
			unsigned char *op;

			if (inscnt) {
				while (moff && ref_data[moff-1] == data[-1]) {
					/* we can match one byte back */
					msize++;
					moff--;
					data--;
					outpos--;
					if (--inscnt)
						continue;
					outpos--;  /* remove count slot */
					inscnt--;  /* make it -1 */
					break;
				}
				out[outpos - inscnt - 1] = inscnt;
				inscnt = 0;
			}

			/* A copy op is currently limited to 64KB (pack v2) */
			left = (msize < 0x10000) ? 0 : (msize - 0x10000);
			msize -= left;

			op = out + outpos++;
			i = 0x80;

			if (moff & 0x000000ff)
				out[outpos++] = moff >> 0,  i |= 0x01;
			if (moff & 0x0000ff00)
				out[outpos++] = moff >> 8,  i |= 0x02;
			if (moff & 0x00ff0000)
				out[outpos++] = moff >> 16, i |= 0x04;
			if (moff & 0xff000000)
				out[outpos++] = moff >> 24, i |= 0x08;

			if (msize & 0x00ff)
				out[outpos++] = msize >> 0, i |= 0x10;
			if (msize & 0xff00)
				out[outpos++] = msize >> 8, i |= 0x20;

			*op = i;

			data += msize;
			moff += msize;
			msize = left;

			if (msize < 4096) {
				int j;
				val = 0;
				for (j = -RABIN_WINDOW; j < 0; j++)
					val = ((val << 8) | data[j])
					      ^ T[val >> RABIN_SHIFT];
			}
		}

		if (outpos >= outsize - MAX_OP_SIZE) {
			void *tmp = out;
			outsize = outsize * 3 / 2;
			if (max_size && outsize >= max_size)
				outsize = max_size + MAX_OP_SIZE + 1;
			if (max_size && outpos > max_size)
				break;
			out = realloc(out, outsize);
			if (!out) {
				free(tmp);
				return NULL;
			}
		}
	}

	if (inscnt)
		out[outpos - inscnt - 1] = inscnt;

	if (max_size && outpos > max_size) {
		free(out);
		return NULL;
	}

	*delta_size = outpos;
	return out;
}
Commit	Line	Data
a310d434 NP	1	/*
	2	* diff-delta.c: generate a delta between two buffers
	3	*
366b53c1 NP	4	* This code was greatly inspired by parts of LibXDiff from Davide Libenzi
366b53c1 NP	5	* http://www.xmailserver.org/xdiff-lib.html
a310d434	6	*
03aa8ff3	7	* Rewritten for GIT by Nicolas Pitre <nico@fluxnic.net>, (C) 2005-2007
a310d434	8	*
366b53c1 NP	9	* This code is free software; you can redistribute it and/or modify
	10	* it under the terms of the GNU General Public License version 2 as
	11	* published by the Free Software Foundation.
a310d434 NP	12	*/
a310d434 NP	13
63f17569	14	#include "git-compat-util.h"
85023577	15	#include "delta.h"
a310d434	16
08abe669 NP	17	/* maximum hash entry list for the same hash bucket */
08abe669 NP	18	#define HASH_LIMIT 64
a310d434	19
3dc5a9e4 NP	20	#define RABIN_SHIFT 23
	21	#define RABIN_WINDOW 16
	22
	23	static const unsigned int T[256] = {
	24	0x00000000, 0xab59b4d1, 0x56b369a2, 0xfdeadd73, 0x063f6795, 0xad66d344,
	25	0x508c0e37, 0xfbd5bae6, 0x0c7ecf2a, 0xa7277bfb, 0x5acda688, 0xf1941259,
	26	0x0a41a8bf, 0xa1181c6e, 0x5cf2c11d, 0xf7ab75cc, 0x18fd9e54, 0xb3a42a85,
	27	0x4e4ef7f6, 0xe5174327, 0x1ec2f9c1, 0xb59b4d10, 0x48719063, 0xe32824b2,
	28	0x1483517e, 0xbfdae5af, 0x423038dc, 0xe9698c0d, 0x12bc36eb, 0xb9e5823a,
	29	0x440f5f49, 0xef56eb98, 0x31fb3ca8, 0x9aa28879, 0x6748550a, 0xcc11e1db,
	30	0x37c45b3d, 0x9c9defec, 0x6177329f, 0xca2e864e, 0x3d85f382, 0x96dc4753,
	31	0x6b369a20, 0xc06f2ef1, 0x3bba9417, 0x90e320c6, 0x6d09fdb5, 0xc6504964,
	32	0x2906a2fc, 0x825f162d, 0x7fb5cb5e, 0xd4ec7f8f, 0x2f39c569, 0x846071b8,
	33	0x798aaccb, 0xd2d3181a, 0x25786dd6, 0x8e21d907, 0x73cb0474, 0xd892b0a5,
	34	0x23470a43, 0x881ebe92, 0x75f463e1, 0xdeadd730, 0x63f67950, 0xc8afcd81,
	35	0x354510f2, 0x9e1ca423, 0x65c91ec5, 0xce90aa14, 0x337a7767, 0x9823c3b6,
	36	0x6f88b67a, 0xc4d102ab, 0x393bdfd8, 0x92626b09, 0x69b7d1ef, 0xc2ee653e,
	37	0x3f04b84d, 0x945d0c9c, 0x7b0be704, 0xd05253d5, 0x2db88ea6, 0x86e13a77,
	38	0x7d348091, 0xd66d3440, 0x2b87e933, 0x80de5de2, 0x7775282e, 0xdc2c9cff,
	39	0x21c6418c, 0x8a9ff55d, 0x714a4fbb, 0xda13fb6a, 0x27f92619, 0x8ca092c8,
	40	0x520d45f8, 0xf954f129, 0x04be2c5a, 0xafe7988b, 0x5432226d, 0xff6b96bc,
	41	0x02814bcf, 0xa9d8ff1e, 0x5e738ad2, 0xf52a3e03, 0x08c0e370, 0xa39957a1,
	42	0x584ced47, 0xf3155996, 0x0eff84e5, 0xa5a63034, 0x4af0dbac, 0xe1a96f7d,
	43	0x1c43b20e, 0xb71a06df, 0x4ccfbc39, 0xe79608e8, 0x1a7cd59b, 0xb125614a,
	44	0x468e1486, 0xedd7a057, 0x103d7d24, 0xbb64c9f5, 0x40b17313, 0xebe8c7c2,
	45	0x16021ab1, 0xbd5bae60, 0x6cb54671, 0xc7ecf2a0, 0x3a062fd3, 0x915f9b02,
	46	0x6a8a21e4, 0xc1d39535, 0x3c394846, 0x9760fc97, 0x60cb895b, 0xcb923d8a,
	47	0x3678e0f9, 0x9d215428, 0x66f4eece, 0xcdad5a1f, 0x3047876c, 0x9b1e33bd,
	48	0x7448d825, 0xdf116cf4, 0x22fbb187, 0x89a20556, 0x7277bfb0, 0xd92e0b61,
	49	0x24c4d612, 0x8f9d62c3, 0x7836170f, 0xd36fa3de, 0x2e857ead, 0x85dcca7c,
	50	0x7e09709a, 0xd550c44b, 0x28ba1938, 0x83e3ade9, 0x5d4e7ad9, 0xf617ce08,
	51	0x0bfd137b, 0xa0a4a7aa, 0x5b711d4c, 0xf028a99d, 0x0dc274ee, 0xa69bc03f,
	52	0x5130b5f3, 0xfa690122, 0x0783dc51, 0xacda6880, 0x570fd266, 0xfc5666b7,
	53	0x01bcbbc4, 0xaae50f15, 0x45b3e48d, 0xeeea505c, 0x13008d2f, 0xb85939fe,
	54	0x438c8318, 0xe8d537c9, 0x153feaba, 0xbe665e6b, 0x49cd2ba7, 0xe2949f76,
	55	0x1f7e4205, 0xb427f6d4, 0x4ff24c32, 0xe4abf8e3, 0x19412590, 0xb2189141,
	56	0x0f433f21, 0xa41a8bf0, 0x59f05683, 0xf2a9e252, 0x097c58b4, 0xa225ec65,
	57	0x5fcf3116, 0xf49685c7, 0x033df00b, 0xa86444da, 0x558e99a9, 0xfed72d78,
	58	0x0502979e, 0xae5b234f, 0x53b1fe3c, 0xf8e84aed, 0x17bea175, 0xbce715a4,
	59	0x410dc8d7, 0xea547c06, 0x1181c6e0, 0xbad87231, 0x4732af42, 0xec6b1b93,
	60	0x1bc06e5f, 0xb099da8e, 0x4d7307fd, 0xe62ab32c, 0x1dff09ca, 0xb6a6bd1b,
	61	0x4b4c6068, 0xe015d4b9, 0x3eb80389, 0x95e1b758, 0x680b6a2b, 0xc352defa,
	62	0x3887641c, 0x93ded0cd, 0x6e340dbe, 0xc56db96f, 0x32c6cca3, 0x999f7872,
	63	0x6475a501, 0xcf2c11d0, 0x34f9ab36, 0x9fa01fe7, 0x624ac294, 0xc9137645,
	64	0x26459ddd, 0x8d1c290c, 0x70f6f47f, 0xdbaf40ae, 0x207afa48, 0x8b234e99,
	65	0x76c993ea, 0xdd90273b, 0x2a3b52f7, 0x8162e626, 0x7c883b55, 0xd7d18f84,
	66	0x2c043562, 0x875d81b3, 0x7ab75cc0, 0xd1eee811
	67	};
	68
	69	static const unsigned int U[256] = {
	70	0x00000000, 0x7eb5200d, 0x5633f4cb, 0x2886d4c6, 0x073e5d47, 0x798b7d4a,
	71	0x510da98c, 0x2fb88981, 0x0e7cba8e, 0x70c99a83, 0x584f4e45, 0x26fa6e48,
	72	0x0942e7c9, 0x77f7c7c4, 0x5f711302, 0x21c4330f, 0x1cf9751c, 0x624c5511,
	73	0x4aca81d7, 0x347fa1da, 0x1bc7285b, 0x65720856, 0x4df4dc90, 0x3341fc9d,
	74	0x1285cf92, 0x6c30ef9f, 0x44b63b59, 0x3a031b54, 0x15bb92d5, 0x6b0eb2d8,
	75	0x4388661e, 0x3d3d4613, 0x39f2ea38, 0x4747ca35, 0x6fc11ef3, 0x11743efe,
	76	0x3eccb77f, 0x40799772, 0x68ff43b4, 0x164a63b9, 0x378e50b6, 0x493b70bb,
	77	0x61bda47d, 0x1f088470, 0x30b00df1, 0x4e052dfc, 0x6683f93a, 0x1836d937,
	78	0x250b9f24, 0x5bbebf29, 0x73386bef, 0x0d8d4be2, 0x2235c263, 0x5c80e26e,
	79	0x740636a8, 0x0ab316a5, 0x2b7725aa, 0x55c205a7, 0x7d44d161, 0x03f1f16c,
	80	0x2c4978ed, 0x52fc58e0, 0x7a7a8c26, 0x04cfac2b, 0x73e5d470, 0x0d50f47d,
	81	0x25d620bb, 0x5b6300b6, 0x74db8937, 0x0a6ea93a, 0x22e87dfc, 0x5c5d5df1,
	82	0x7d996efe, 0x032c4ef3, 0x2baa9a35, 0x551fba38, 0x7aa733b9, 0x041213b4,
	83	0x2c94c772, 0x5221e77f, 0x6f1ca16c, 0x11a98161, 0x392f55a7, 0x479a75aa,
84	0x6822fc2b, 0x1697dc26, 0x3e1108e0, 0x40a428ed, 0x61601be2, 0x1fd53bef,
85	0x3753ef29, 0x49e6cf24, 0x665e46a5, 0x18eb66a8, 0x306db26e, 0x4ed89263,
86	0x4a173e48, 0x34a21e45, 0x1c24ca83, 0x6291ea8e, 0x4d29630f, 0x339c4302,
87	0x1b1a97c4, 0x65afb7c9, 0x446b84c6, 0x3adea4cb, 0x1258700d, 0x6ced5000,
88	0x4355d981, 0x3de0f98c, 0x15662d4a, 0x6bd30d47, 0x56ee4b54, 0x285b6b59,
89	0x00ddbf9f, 0x7e689f92, 0x51d01613, 0x2f65361e, 0x07e3e2d8, 0x7956c2d5,
90	0x5892f1da, 0x2627d1d7, 0x0ea10511, 0x7014251c, 0x5facac9d, 0x21198c90,
91	0x099f5856, 0x772a785b, 0x4c921c31, 0x32273c3c, 0x1aa1e8fa, 0x6414c8f7,
92	0x4bac4176, 0x3519617b, 0x1d9fb5bd, 0x632a95b0, 0x42eea6bf, 0x3c5b86b2,
93	0x14dd5274, 0x6a687279, 0x45d0fbf8, 0x3b65dbf5, 0x13e30f33, 0x6d562f3e,
94	0x506b692d, 0x2ede4920, 0x06589de6, 0x78edbdeb, 0x5755346a, 0x29e01467,
95	0x0166c0a1, 0x7fd3e0ac, 0x5e17d3a3, 0x20a2f3ae, 0x08242768, 0x76910765,
96	0x59298ee4, 0x279caee9, 0x0f1a7a2f, 0x71af5a22, 0x7560f609, 0x0bd5d604,
97	0x235302c2, 0x5de622cf, 0x725eab4e, 0x0ceb8b43, 0x246d5f85, 0x5ad87f88,
98	0x7b1c4c87, 0x05a96c8a, 0x2d2fb84c, 0x539a9841, 0x7c2211c0, 0x029731cd,
99	0x2a11e50b, 0x54a4c506, 0x69998315, 0x172ca318, 0x3faa77de, 0x411f57d3,
100	0x6ea7de52, 0x1012fe5f, 0x38942a99, 0x46210a94, 0x67e5399b, 0x19501996,
101	0x31d6cd50, 0x4f63ed5d, 0x60db64dc, 0x1e6e44d1, 0x36e89017, 0x485db01a,
102	0x3f77c841, 0x41c2e84c, 0x69443c8a, 0x17f11c87, 0x38499506, 0x46fcb50b,
103	0x6e7a61cd, 0x10cf41c0, 0x310b72cf, 0x4fbe52c2, 0x67388604, 0x198da609,
104	0x36352f88, 0x48800f85, 0x6006db43, 0x1eb3fb4e, 0x238ebd5d, 0x5d3b9d50,
105	0x75bd4996, 0x0b08699b, 0x24b0e01a, 0x5a05c017, 0x728314d1, 0x0c3634dc,
106	0x2df207d3, 0x534727de, 0x7bc1f318, 0x0574d315, 0x2acc5a94, 0x54797a99,
107	0x7cffae5f, 0x024a8e52, 0x06852279, 0x78300274, 0x50b6d6b2, 0x2e03f6bf,
108	0x01bb7f3e, 0x7f0e5f33, 0x57888bf5, 0x293dabf8, 0x08f998f7, 0x764cb8fa,
109	0x5eca6c3c, 0x207f4c31, 0x0fc7c5b0, 0x7172e5bd, 0x59f4317b, 0x27411176,
110	0x1a7c5765, 0x64c97768, 0x4c4fa3ae, 0x32fa83a3, 0x1d420a22, 0x63f72a2f,
111	0x4b71fee9, 0x35c4dee4, 0x1400edeb, 0x6ab5cde6, 0x42331920, 0x3c86392d,
112	0x133eb0ac, 0x6d8b90a1, 0x450d4467, 0x3bb8646a
113	};
a310d434	114
08abe669	115	struct index_entry {
a310d434	116	const unsigned char *ptr;
8e1454b5	117	unsigned int val;
d2100860 DK	118	};
	119
	120	struct unpacked_index_entry {
	121	struct index_entry entry;
	122	struct unpacked_index_entry *next;
8e1454b5	123	};
a310d434	124
08abe669	125	struct delta_index {
11779e79	126	unsigned long memsize;
08abe669 NP	127	const void *src_buf;
08abe669 NP	128	unsigned long src_size;
3dc5a9e4	129	unsigned int hash_mask;
63f17569	130	struct index_entry *hash[FLEX_ARRAY];
08abe669 NP	131	};
	132
	133	struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
a310d434	134	{
06a9f920	135	unsigned int i, hsize, hmask, entries, prev_val, *hash_count;
08abe669 NP	136	const unsigned char data, buffer = buf;
08abe669 NP	137	struct delta_index *index;
d2100860 DK	138	struct unpacked_index_entry entry, *hash;
d2100860 DK	139	struct index_entry packed_entry, *packed_hash;
8e1454b5	140	void *mem;
06a9f920	141	unsigned long memsize;
8e1454b5	142
08abe669 NP	143	if (!buf \|\| !bufsize)
	144	return NULL;
	145
3dc5a9e4	146	/* Determine index hash size. Note that indexing skips the
82e5a82f	147	first byte to allow for optimizing the Rabin's polynomial
3dc5a9e4 NP	148	initialization in create_delta(). */
3dc5a9e4 NP	149	entries = (bufsize - 1) / RABIN_WINDOW;
8e1454b5	150	hsize = entries / 4;
b05faa2d	151	for (i = 4; (1u << i) < hsize && i < 31; i++);
8e1454b5	152	hsize = 1 << i;
3dc5a9e4	153	hmask = hsize - 1;
8e1454b5 NP	154
8e1454b5 NP	155	/* allocate lookup index */
d2100860	156	memsize = sizeof(hash) hsize +
06a9f920 NP	157	sizeof(entry) entries;
06a9f920 NP	158	mem = malloc(memsize);
8e1454b5 NP	159	if (!mem)
	160	return NULL;
	161	hash = mem;
08abe669 NP	162	mem = hash + hsize;
	163	entry = mem;
	164
8e1454b5 NP	165	memset(hash, 0, hsize * sizeof(*hash));
8e1454b5 NP	166
c13c6bf7 NP	167	/* allocate an array to count hash entries */
	168	hash_count = calloc(hsize, sizeof(*hash_count));
	169	if (!hash_count) {
d2100860	170	free(hash);
c13c6bf7 NP	171	return NULL;
	172	}
	173
	174	/* then populate the index */
06a9f920 NP	175	prev_val = ~0;
	176	for (data = buffer + entries * RABIN_WINDOW - RABIN_WINDOW;
	177	data >= buffer;
	178	data -= RABIN_WINDOW) {
3dc5a9e4 NP	179	unsigned int val = 0;
	180	for (i = 1; i <= RABIN_WINDOW; i++)
	181	val = ((val << 8) \| data[i]) ^ T[val >> RABIN_SHIFT];
06a9f920 NP	182	if (val == prev_val) {
06a9f920 NP	183	/* keep the lowest of consecutive identical blocks */
d2100860 DK	184	entry[-1].entry.ptr = data + RABIN_WINDOW;
d2100860 DK	185	--entries;
06a9f920 NP	186	} else {
	187	prev_val = val;
	188	i = val & hmask;
d2100860 DK	189	entry->entry.ptr = data + RABIN_WINDOW;
d2100860 DK	190	entry->entry.val = val;
06a9f920 NP	191	entry->next = hash[i];
	192	hash[i] = entry++;
	193	hash_count[i]++;
06a9f920	194	}
3dc5a9e4	195	}
a310d434	196
c13c6bf7 NP	197	/*
c13c6bf7 NP	198	* Determine a limit on the number of entries in the same hash
82e5a82f	199	* bucket. This guards us against pathological data sets causing
c13c6bf7 NP	200	* really bad hash distribution with most entries in the same hash
	201	* bucket that would bring us to O(m*n) computing costs (m and n
	202	* corresponding to reference and target buffer sizes).
	203	*
08abe669	204	* Make sure none of the hash buckets has more entries than
c13c6bf7 NP	205	* we're willing to test. Otherwise we cull the entry list
	206	* uniformly to still preserve a good repartition across
	207	* the reference buffer.
	208	*/
	209	for (i = 0; i < hsize; i++) {
02e665ce DK	210	int acc;
	211
	212	if (hash_count[i] <= HASH_LIMIT)
c13c6bf7	213	continue;
02e665ce	214
02e665ce	215	/* We leave exactly HASH_LIMIT entries in the bucket */
ce85b053	216	entries -= hash_count[i] - HASH_LIMIT;
02e665ce	217
c13c6bf7	218	entry = hash[i];
02e665ce	219	acc = 0;
ce85b053 NP	220
	221	/*
	222	* Assume that this loop is gone through exactly
	223	* HASH_LIMIT times and is entered and left with
	224	* acc==0. So the first statement in the loop
	225	* contributes (hash_count[i]-HASH_LIMIT)*HASH_LIMIT
	226	* to the accumulator, and the inner loop consequently
	227	* is run (hash_count[i]-HASH_LIMIT) times, removing
	228	* one element from the list each time. Since acc
	229	* balances out to 0 at the final run, the inner loop
	230	* body can't be left with entry==NULL. So we indeed
	231	* encounter entry==NULL in the outer loop only.
	232	*/
c13c6bf7	233	do {
02e665ce DK	234	acc += hash_count[i] - HASH_LIMIT;
	235	if (acc > 0) {
	236	struct unpacked_index_entry *keep = entry;
	237	do {
	238	entry = entry->next;
	239	acc -= HASH_LIMIT;
	240	} while (acc > 0);
	241	keep->next = entry->next;
	242	}
	243	entry = entry->next;
	244	} while (entry);
c13c6bf7 NP	245	}
	246	free(hash_count);
	247
ce85b053 NP	248	/*
	249	* Now create the packed index in array form
	250	* rather than linked lists.
	251	*/
d2100860 DK	252	memsize = sizeof(*index)
	253	+ sizeof(packed_hash) (hsize+1)
	254	+ sizeof(packed_entry) entries;
d2100860	255	mem = malloc(memsize);
d2100860 DK	256	if (!mem) {
	257	free(hash);
	258	return NULL;
	259	}
	260
	261	index = mem;
	262	index->memsize = memsize;
	263	index->src_buf = buf;
	264	index->src_size = bufsize;
	265	index->hash_mask = hmask;
	266
f9c5a80c	267	mem = index->hash;
d2100860 DK	268	packed_hash = mem;
	269	mem = packed_hash + (hsize+1);
	270	packed_entry = mem;
	271
d2100860	272	for (i = 0; i < hsize; i++) {
ce85b053 NP	273	/*
	274	* Coalesce all entries belonging to one linked list
	275	* into consecutive array entries.
	276	*/
d2100860 DK	277	packed_hash[i] = packed_entry;
	278	for (entry = hash[i]; entry; entry = entry->next)
	279	*packed_entry++ = entry->entry;
	280	}
	281
ce85b053	282	/* Sentinel value to indicate the length of the last hash bucket */
d2100860	283	packed_hash[hsize] = packed_entry;
ce85b053	284
d2100860 DK	285	assert(packed_entry - (struct index_entry *)mem == entries);
	286	free(hash);
	287
08abe669 NP	288	return index;
	289	}
	290
	291	void free_delta_index(struct delta_index *index)
	292	{
	293	free(index);
a310d434 NP	294	}
a310d434 NP	295
11779e79 BD	296	unsigned long sizeof_delta_index(struct delta_index *index)
	297	{
	298	if (index)
	299	return index->memsize;
	300	else
	301	return 0;
	302	}
	303
3dc5a9e4 NP	304	/*
3dc5a9e4 NP	305	* The maximum size for any opcode sequence, including the initial header
82e5a82f	306	* plus Rabin window plus biggest copy.
3dc5a9e4 NP	307	*/
3dc5a9e4 NP	308	#define MAX_OP_SIZE (5 + 5 + 1 + RABIN_WINDOW + 7)
fe474b58	309
08abe669 NP	310	void *
	311	create_delta(const struct delta_index *index,
	312	const void *trg_buf, unsigned long trg_size,
	313	unsigned long *delta_size, unsigned long max_size)
a310d434	314	{
84336696	315	unsigned int i, outpos, outsize, moff, msize, val;
5a1fb2ca	316	int inscnt;
8e1454b5 NP	317	const unsigned char ref_data, ref_top, data, top;
8e1454b5 NP	318	unsigned char *out;
a310d434	319
08abe669	320	if (!trg_buf \|\| !trg_size)
8e1454b5 NP	321	return NULL;
8e1454b5 NP	322
a310d434 NP	323	outpos = 0;
a310d434 NP	324	outsize = 8192;
fe474b58 NP	325	if (max_size && outsize >= max_size)
fe474b58 NP	326	outsize = max_size + MAX_OP_SIZE + 1;
a310d434	327	out = malloc(outsize);
08abe669	328	if (!out)
a310d434	329	return NULL;
a310d434 NP	330
a310d434 NP	331	/* store reference buffer size */
08abe669 NP	332	i = index->src_size;
	333	while (i >= 0x80) {
	334	out[outpos++] = i \| 0x80;
	335	i >>= 7;
69a2d426	336	}
08abe669	337	out[outpos++] = i;
a310d434 NP	338
a310d434 NP	339	/* store target buffer size */
08abe669 NP	340	i = trg_size;
	341	while (i >= 0x80) {
	342	out[outpos++] = i \| 0x80;
	343	i >>= 7;
69a2d426	344	}
08abe669	345	out[outpos++] = i;
a310d434	346
08abe669 NP	347	ref_data = index->src_buf;
	348	ref_top = ref_data + index->src_size;
	349	data = trg_buf;
1d7f171c	350	top = (const unsigned char *) trg_buf + trg_size;
3dc5a9e4 NP	351
	352	outpos++;
	353	val = 0;
	354	for (i = 0; i < RABIN_WINDOW && data < top; i++, data++) {
	355	out[outpos++] = *data;
	356	val = ((val << 8) \| *data) ^ T[val >> RABIN_SHIFT];
	357	}
	358	inscnt = i;
a310d434	359
84336696 NP	360	moff = 0;
84336696 NP	361	msize = 0;
8e1454b5	362	while (data < top) {
84336696 NP	363	if (msize < 4096) {
	364	struct index_entry *entry;
	365	val ^= U[data[-RABIN_WINDOW]];
	366	val = ((val << 8) \| *data) ^ T[val >> RABIN_SHIFT];
	367	i = val & index->hash_mask;
d2100860	368	for (entry = index->hash[i]; entry < index->hash[i+1]; entry++) {
84336696 NP	369	const unsigned char *ref = entry->ptr;
	370	const unsigned char *src = data;
	371	unsigned int ref_size = ref_top - ref;
	372	if (entry->val != val)
	373	continue;
	374	if (ref_size > top - src)
	375	ref_size = top - src;
	376	if (ref_size <= msize)
	377	break;
	378	while (ref_size-- && src++ == ref)
	379	ref++;
	380	if (msize < ref - entry->ptr) {
	381	/* this is our best match so far */
	382	msize = ref - entry->ptr;
	383	moff = entry->ptr - ref_data;
	384	if (msize >= 4096) /* good enough */
	385	break;
	386	}
a310d434 NP	387	}
	388	}
	389
3dc5a9e4	390	if (msize < 4) {
a310d434 NP	391	if (!inscnt)
	392	outpos++;
	393	out[outpos++] = *data++;
	394	inscnt++;
	395	if (inscnt == 0x7f) {
	396	out[outpos - inscnt - 1] = inscnt;
	397	inscnt = 0;
	398	}
84336696	399	msize = 0;
a310d434	400	} else {
84336696	401	unsigned int left;
8e1454b5 NP	402	unsigned char *op;
8e1454b5 NP	403
a310d434	404	if (inscnt) {
5a1fb2ca	405	while (moff && ref_data[moff-1] == data[-1]) {
5a1fb2ca NP	406	/* we can match one byte back */
	407	msize++;
	408	moff--;
	409	data--;
	410	outpos--;
	411	if (--inscnt)
	412	continue;
	413	outpos--; /* remove count slot */
	414	inscnt--; /* make it -1 */
	415	break;
	416	}
a310d434 NP	417	out[outpos - inscnt - 1] = inscnt;
	418	inscnt = 0;
	419	}
	420
84336696 NP	421	/* A copy op is currently limited to 64KB (pack v2) */
	422	left = (msize < 0x10000) ? 0 : (msize - 0x10000);
	423	msize -= left;
	424
8e1454b5	425	op = out + outpos++;
a310d434 NP	426	i = 0x80;
a310d434 NP	427
84336696 NP	428	if (moff & 0x000000ff)
	429	out[outpos++] = moff >> 0, i \|= 0x01;
	430	if (moff & 0x0000ff00)
	431	out[outpos++] = moff >> 8, i \|= 0x02;
	432	if (moff & 0x00ff0000)
	433	out[outpos++] = moff >> 16, i \|= 0x04;
	434	if (moff & 0xff000000)
	435	out[outpos++] = moff >> 24, i \|= 0x08;
a310d434	436
84336696 NP	437	if (msize & 0x00ff)
	438	out[outpos++] = msize >> 0, i \|= 0x10;
	439	if (msize & 0xff00)
	440	out[outpos++] = msize >> 8, i \|= 0x20;
a310d434	441
8e1454b5	442	*op = i;
84336696 NP	443
	444	data += msize;
	445	moff += msize;
	446	msize = left;
	447
	448	if (msize < 4096) {
	449	int j;
	450	val = 0;
	451	for (j = -RABIN_WINDOW; j < 0; j++)
	452	val = ((val << 8) \| data[j])
	453	^ T[val >> RABIN_SHIFT];
	454	}
a310d434 NP	455	}
a310d434 NP	456
fe474b58	457	if (outpos >= outsize - MAX_OP_SIZE) {
a310d434 NP	458	void *tmp = out;
a310d434 NP	459	outsize = outsize * 3 / 2;
fe474b58 NP	460	if (max_size && outsize >= max_size)
	461	outsize = max_size + MAX_OP_SIZE + 1;
	462	if (max_size && outpos > max_size)
3dc5a9e4	463	break;
b75c6c6d	464	out = realloc(out, outsize);
a310d434 NP	465	if (!out) {
a310d434 NP	466	free(tmp);
a310d434 NP	467	return NULL;
	468	}
	469	}
	470	}
	471
	472	if (inscnt)
	473	out[outpos - inscnt - 1] = inscnt;
	474
3dc5a9e4 NP	475	if (max_size && outpos > max_size) {
	476	free(out);
	477	return NULL;
	478	}
	479
a310d434 NP	480	*delta_size = outpos;
	481	return out;
	482	}