X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diff-delta.c;h=1188b31cd0f1e2f3a1fc2096a10243a03b439021;hb=a4a6e4ab32648631204398691f4066719dea1029;hp=dcd3f5572e2682d1ef94b030efe1682dc3f76b67;hpb=38fd0721d0a2a1a723bc28fc0817e3571987b1ef;p=git.git diff --git a/diff-delta.c b/diff-delta.c index dcd3f557..1188b31c 100644 --- a/diff-delta.c +++ b/diff-delta.c @@ -20,40 +20,48 @@ #include #include +#include #include "delta.h" +/* block size: min = 16, max = 64k, power of 2 */ +#define BLK_SIZE 16 + +#define MIN(a, b) ((a) < (b) ? (a) : (b)) + +#define GR_PRIME 0x9e370001 +#define HASH(v, shift) (((unsigned int)(v) * GR_PRIME) >> (shift)) + 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 long trg_bufsize, + unsigned int *hash_shift) { - unsigned long hsize; - unsigned int i, hshift, hlimit, *hash_count; + unsigned int i, hsize, hshift, hlimit, entries, *hash_count; const unsigned char *data; struct index *entry, **hash; void *mem; /* determine index hash size */ - hsize = bufsize / 4; - for (i = 8; (1 << i) < hsize && i < 24; i += 2); + entries = bufsize / BLK_SIZE; + hsize = entries / 4; + for (i = 4; (1 << i) < hsize && i < 31; i++); hsize = 1 << i; - hshift = (i - 8) / 2; + hshift = 32 - i; + *hash_shift = hshift; - /* - * Allocate lookup index. Note the first hash pointer - * is used to store the hash shift value. - */ - mem = malloc((1 + hsize) * sizeof(*hash) + bufsize * sizeof(*entry)); + /* allocate lookup index */ + mem = malloc(hsize * sizeof(*hash) + entries * sizeof(*entry)); if (!mem) return NULL; hash = mem; - *hash++ = (void *)hshift; - entry = mem + (1 + hsize) * sizeof(*hash); + entry = mem + hsize * sizeof(*hash); memset(hash, 0, hsize * sizeof(*hash)); /* allocate an array to count hash entries */ @@ -64,13 +72,16 @@ static struct index ** delta_index(const unsigned char *buf, } /* then populate the index */ - data = buf + bufsize - 2; - while (data > buf) { - entry->ptr = --data; - i = data[0] ^ ((data[1] ^ (data[2] << hshift)) << hshift); + 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; } /* @@ -85,13 +96,13 @@ static struct index ** delta_index(const unsigned char *buf, * the cost is bounded to something more like O(m+n). */ hlimit = (1 << 26) / trg_bufsize; - if (hlimit < 16) - hlimit = 16; + 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 short-circuit the entry - * list uniformly to still preserve a good repartition across + * 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++) { @@ -109,7 +120,7 @@ static struct index ** delta_index(const unsigned char *buf, } free(hash_count); - return hash-1; + return hash; } /* provide the size of the copy opcode given the block offset and size */ @@ -123,26 +134,19 @@ static struct index ** delta_index(const unsigned char *buf, 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, - void **from_index) + unsigned long max_size) { - unsigned int i, outpos, outsize, inscnt, hash_shift; + 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; - if (from_index && *from_index) { - hash = *from_index; - } else { - hash = delta_index(from_buf, from_size, to_size); - if (!hash) - return NULL; - if (from_index) - *from_index = hash; - } - hash_shift = (unsigned int)(*hash++); + hash = delta_index(from_buf, from_size, to_size, &hash_shift); + if (!hash) + return NULL; outpos = 0; outsize = 8192; @@ -150,8 +154,7 @@ void *diff_delta(void *from_buf, unsigned long from_size, outsize = max_size + MAX_OP_SIZE + 1; out = malloc(outsize); if (!out) { - if (!from_index) - free(hash-1); + free(hash); return NULL; } @@ -182,21 +185,23 @@ void *diff_delta(void *from_buf, unsigned long from_size, while (data < top) { unsigned int moff = 0, msize = 0; - if (data + 3 <= top) { - i = data[0] ^ ((data[1] ^ (data[2] << hash_shift)) << hash_shift); + 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; - if (*ref != *src) - continue; - while (ref_size-- && *++src == *++ref); + while (ref_size-- && *src++ == *ref) + ref++; if (msize < ref - entry->ptr) { /* this is our best match so far */ msize = ref - entry->ptr; @@ -218,6 +223,20 @@ void *diff_delta(void *from_buf, unsigned long from_size, 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; } @@ -252,8 +271,7 @@ void *diff_delta(void *from_buf, unsigned long from_size, out = realloc(out, outsize); if (!out) { free(tmp); - if (!from_index) - free(hash-1); + free(hash); return NULL; } } @@ -262,8 +280,7 @@ void *diff_delta(void *from_buf, unsigned long from_size, if (inscnt) out[outpos - inscnt - 1] = inscnt; - if (!from_index) - free(hash-1); + free(hash); *delta_size = outpos; return out; }