X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diff-delta.c;h=1188b31cd0f1e2f3a1fc2096a10243a03b439021;hb=4c691724f175573a2dc4118782744cb0e852ab41;hp=b2ae7b5e6c3b4aa409ccfa60f67d5c8eb1690504;hpb=8fc66df237afce0b4318657f166b3583831949f3;p=git.git

diff --git a/diff-delta.c b/diff-delta.c
index b2ae7b5e..1188b31c 100644
--- a/diff-delta.c
+++ b/diff-delta.c
@@ -19,6 +19,8 @@
  */
 
 #include <stdlib.h>
+#include <string.h>
+#include <zlib.h>
 #include "delta.h"
 
 
@@ -28,202 +30,136 @@
 #define MIN(a, b) ((a) < (b) ? (a) : (b))
 
 #define GR_PRIME 0x9e370001
-#define HASH(v, b) (((unsigned int)(v) * GR_PRIME) >> (32 - (b)))
-	
-/* largest prime smaller than 65536 */
-#define BASE 65521
+#define HASH(v, shift) (((unsigned int)(v) * GR_PRIME) >> (shift))
 
-/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
-#define NMAX 5552
-
-#define DO1(buf, i)  { s1 += buf[i]; s2 += s1; }
-#define DO2(buf, i)  DO1(buf, i); DO1(buf, i + 1);
-#define DO4(buf, i)  DO2(buf, i); DO2(buf, i + 2);
-#define DO8(buf, i)  DO4(buf, i); DO4(buf, i + 4);
-#define DO16(buf)    DO8(buf, 0); DO8(buf, 8);
-
-static unsigned int adler32(unsigned int adler, const unsigned char *buf, int len)
-{
-	int k;
-	unsigned int s1 = adler & 0xffff;
-	unsigned int s2 = adler >> 16;
-
-	while (len > 0) {
-		k = MIN(len, NMAX);
-		len -= k;
-		while (k >= 16) {
-			DO16(buf);
-			buf += 16;
-			k -= 16;
-		}
-		if (k != 0)
-			do {
-				s1 += *buf++;
-				s2 += s1;
-			} while (--k);
-		s1 %= BASE;
-		s2 %= BASE;
-	}
-
-	return (s2 << 16) | s1;
-}
-
-static unsigned int hashbits(unsigned int size)
-{
-	unsigned int val = 1, bits = 0;
-	while (val < size && bits < 32) {
-		val <<= 1;
-	       	bits++;
-	}
-	return bits ? bits: 1;
-}
-
-typedef struct s_chanode {
-	struct s_chanode *next;
-	int icurr;
-} chanode_t;
-
-typedef struct s_chastore {
-	chanode_t *head, *tail;
-	int isize, nsize;
-	chanode_t *ancur;
-	chanode_t *sncur;
-	int scurr;
-} chastore_t;
-
-static void cha_init(chastore_t *cha, int isize, int icount)
-{
-	cha->head = cha->tail = NULL;
-	cha->isize = isize;
-	cha->nsize = icount * isize;
-	cha->ancur = cha->sncur = NULL;
-	cha->scurr = 0;
-}
-
-static void *cha_alloc(chastore_t *cha)
-{
-	chanode_t *ancur;
-	void *data;
-
-	ancur = cha->ancur;
-	if (!ancur || ancur->icurr == cha->nsize) {
-		ancur = malloc(sizeof(chanode_t) + cha->nsize);
-		if (!ancur)
-			return NULL;
-		ancur->icurr = 0;
-		ancur->next = NULL;
-		if (cha->tail)
-			cha->tail->next = ancur;
-		if (!cha->head)
-			cha->head = ancur;
-		cha->tail = ancur;
-		cha->ancur = ancur;
-	}
-
-	data = (void *)ancur + sizeof(chanode_t) + ancur->icurr;
-	ancur->icurr += cha->isize;
-	return data;
-}
-
-static void cha_free(chastore_t *cha)
+struct index {
+	const unsigned char *ptr;
+	unsigned int val;
+	struct index *next;
+};
+
+static struct index ** delta_index(const unsigned char *buf,
+				   unsigned long bufsize,
+				   unsigned long trg_bufsize,
+				   unsigned int *hash_shift)
 {
-	chanode_t *cur = cha->head;
-	while (cur) {
-		chanode_t *tmp = cur;
-		cur = cur->next;
-		free(tmp);
+	unsigned int i, hsize, hshift, hlimit, entries, *hash_count;
+	const unsigned char *data;
+	struct index *entry, **hash;
+	void *mem;
+
+	/* determine index hash size */
+	entries = bufsize  / BLK_SIZE;
+	hsize = entries / 4;
+	for (i = 4; (1 << i) < hsize && i < 31; i++);
+	hsize = 1 << i;
+	hshift = 32 - i;
+	*hash_shift = hshift;
+
+	/* allocate lookup index */
+	mem = malloc(hsize * sizeof(*hash) + entries * sizeof(*entry));
+	if (!mem)
+		return NULL;
+	hash = mem;
+	entry = mem + hsize * sizeof(*hash);
+	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;
 	}
-}
-
-typedef struct s_bdrecord {
-	struct s_bdrecord *next;
-	unsigned int fp;
-	const unsigned char *ptr;
-} bdrecord_t;
-
-typedef struct s_bdfile {
-	const unsigned char *data, *top;
-	chastore_t cha;
-	unsigned int fphbits;
-	bdrecord_t **fphash;
-} bdfile_t;
 
-static int delta_prepare(const unsigned char *buf, int bufsize, bdfile_t *bdf)
-{
-	unsigned int fphbits;
-	int i, hsize;
-	const unsigned char *base, *data, *top;
-	bdrecord_t *brec;
-	bdrecord_t **fphash;
-
-	fphbits = hashbits(bufsize / BLK_SIZE + 1);
-	hsize = 1 << fphbits;
-	fphash = malloc(hsize * sizeof(bdrecord_t *));
-	if (!fphash)
-		return -1;
-	for (i = 0; i < hsize; i++)
-		fphash[i] = NULL;
-	cha_init(&bdf->cha, sizeof(bdrecord_t), hsize / 4 + 1);
-
-	bdf->data = data = base = buf;
-	bdf->top = top = buf + bufsize;
-	data += (bufsize / BLK_SIZE) * BLK_SIZE;
-	if (data == top)
+	/* then populate the index */
+	data = buf + entries * BLK_SIZE - BLK_SIZE;
+	while (data >= buf) {
+		unsigned int val = adler32(0, data, BLK_SIZE);
+		i = HASH(val, hshift);
+		entry->ptr = data;
+		entry->val = val;
+		entry->next = hash[i];
+		hash[i] = entry++;
+		hash_count[i]++;
 		data -= BLK_SIZE;
-
-	for ( ; data >= base; data -= BLK_SIZE) {
-		brec = cha_alloc(&bdf->cha);
-		if (!brec) {
-			cha_free(&bdf->cha);
-			free(fphash);
-			return -1;
-		}
-		brec->fp = adler32(0, data, MIN(BLK_SIZE, top - data));
-		brec->ptr = data;
-		i = HASH(brec->fp, fphbits);
-		brec->next = fphash[i];
-		fphash[i] = brec;
+ 	}
+
+	/*
+	 * Determine a limit on the number of entries in the same hash
+	 * bucket.  This guard us against patological 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).
+	 *
+	 * The more the target buffer is large, the more it is important to
+	 * have small entry lists for each hash buckets.  With such a limit
+	 * the cost is bounded to something more like O(m+n).
+	 */
+	hlimit = (1 << 26) / trg_bufsize;
+	if (hlimit < 4*BLK_SIZE)
+		hlimit = 4*BLK_SIZE;
+
+	/*
+	 * Now 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++) {
+		if (hash_count[i] < hlimit)
+			continue;
+		entry = hash[i];
+		do {
+			struct index *keep = entry;
+			int skip = hash_count[i] / hlimit / 2;
+			do {
+				entry = entry->next;
+			} while(--skip && entry);
+			keep->next = entry;
+		} while(entry);
 	}
+	free(hash_count);
 
-	bdf->fphbits = fphbits;
-	bdf->fphash = fphash;
-
-	return 0;
-}
-
-static void delta_cleanup(bdfile_t *bdf)
-{
-	free(bdf->fphash);
-	cha_free(&bdf->cha);
+	return hash;
 }
 
+/* provide the size of the copy opcode given the block offset and size */
 #define COPYOP_SIZE(o, s) \
     (!!(o & 0xff) + !!(o & 0xff00) + !!(o & 0xff0000) + !!(o & 0xff000000) + \
      !!(s & 0xff) + !!(s & 0xff00) + 1)
 
+/* the maximum size for any opcode */
+#define MAX_OP_SIZE COPYOP_SIZE(0xffffffff, 0xffffffff)
+
 void *diff_delta(void *from_buf, unsigned long from_size,
 		 void *to_buf, unsigned long to_size,
 		 unsigned long *delta_size,
 		 unsigned long max_size)
 {
-	int i, outpos, outsize, inscnt, csize, msize, moff;
-	unsigned int fp;
-	const unsigned char *data, *top, *ptr1, *ptr2;
-	unsigned char *out, *orig;
-	bdrecord_t *brec;
-	bdfile_t bdf;
-
-	if (!from_size || !to_size || delta_prepare(from_buf, from_size, &bdf))
+	unsigned int i, outpos, outsize, hash_shift;
+	int inscnt;
+	const unsigned char *ref_data, *ref_top, *data, *top;
+	unsigned char *out;
+	struct index *entry, **hash;
+
+	if (!from_size || !to_size)
 		return NULL;
-	
+	hash = delta_index(from_buf, from_size, to_size, &hash_shift);
+	if (!hash)
+		return NULL;
+
 	outpos = 0;
 	outsize = 8192;
+	if (max_size && outsize >= max_size)
+		outsize = max_size + MAX_OP_SIZE + 1;
 	out = malloc(outsize);
 	if (!out) {
-		delta_cleanup(&bdf);
+		free(hash);
 		return NULL;
 	}
 
+	ref_data = from_buf;
+	ref_top = from_buf + from_size;
 	data = to_buf;
 	top = to_buf + to_size;
 
@@ -246,28 +182,30 @@ void *diff_delta(void *from_buf, unsigned long from_size,
 	}
 
 	inscnt = 0;
-	moff = 0;
+
 	while (data < top) {
-		msize = 0;
-		fp = adler32(0, data, MIN(top - data, BLK_SIZE));
-		i = HASH(fp, bdf.fphbits);
-		for (brec = bdf.fphash[i]; brec; brec = brec->next) {
-			if (brec->fp == fp) {
-				csize = bdf.top - brec->ptr;
-				if (csize > top - data)
-					csize = top - data;
-				for (ptr1 = brec->ptr, ptr2 = data; 
-				     csize && *ptr1 == *ptr2;
-				     csize--, ptr1++, ptr2++);
-
-				csize = ptr1 - brec->ptr;
-				if (csize > msize) {
-					moff = brec->ptr - bdf.data;
-					msize = csize;
-					if (msize >= 0x10000) {
-						msize = 0x10000;
-						break;
-					}
+		unsigned int moff = 0, msize = 0;
+		if (data + BLK_SIZE <= top) {
+			unsigned int val = adler32(0, data, BLK_SIZE);
+			i = HASH(val, hash_shift);
+			for (entry = hash[i]; entry; entry = entry->next) {
+				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 > 0x10000)
+					ref_size = 0x10000;
+				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;
 				}
 			}
 		}
@@ -282,13 +220,29 @@ void *diff_delta(void *from_buf, unsigned long from_size,
 				inscnt = 0;
 			}
 		} else {
+			unsigned char *op;
+
 			if (inscnt) {
+				while (moff && ref_data[moff-1] == data[-1]) {
+					if (msize == 0x10000)
+						break;
+					/* 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;
 			}
 
 			data += msize;
-			orig = out + outpos++;
+			op = out + outpos++;
 			i = 0x80;
 
 			if (moff & 0xff) { out[outpos++] = moff; i |= 0x01; }
@@ -303,23 +257,21 @@ void *diff_delta(void *from_buf, unsigned long from_size,
 			msize >>= 8;
 			if (msize & 0xff) { out[outpos++] = msize; i |= 0x20; }
 
-			*orig = i;
-		}
-
-		if (max_size && outpos > max_size) {
-			free(out);
-			delta_cleanup(&bdf);
-			return NULL;
+			*op = i;
 		}
 
-		/* next time around the largest possible output is 1 + 4 + 3 */
-		if (outpos > outsize - 8) {
+		if (outpos >= outsize - MAX_OP_SIZE) {
 			void *tmp = out;
 			outsize = outsize * 3 / 2;
-			out = realloc(out, outsize);
+			if (max_size && outsize >= max_size)
+				outsize = max_size + MAX_OP_SIZE + 1;
+			if (max_size && outpos > max_size)
+				out = NULL;
+			else
+				out = realloc(out, outsize);
 			if (!out) {
 				free(tmp);
-				delta_cleanup(&bdf);
+				free(hash);
 				return NULL;
 			}
 		}
@@ -328,7 +280,7 @@ void *diff_delta(void *from_buf, unsigned long from_size,
 	if (inscnt)
 		out[outpos - inscnt - 1] = inscnt;
 
-	delta_cleanup(&bdf);
+	free(hash);
 	*delta_size = outpos;
 	return out;
 }