X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diff-delta.c;h=c2f656ae39b4c43b5bd74b1557b2486e0e682412;hb=8e1618f9612a78ea09b2a926797c781fe06027c9;hp=fd9b37f4910e95faac206339e23b05312ba3a52d;hpb=85c1f337be49eaa9a22e42a1c9958deef5ab57c3;p=git.git diff --git a/diff-delta.c b/diff-delta.c index fd9b37f4..c2f656ae 100644 --- a/diff-delta.c +++ b/diff-delta.c @@ -20,6 +20,7 @@ #include #include "delta.h" +#include "zlib.h" /* block size: min = 16, max = 64k, power of 2 */ @@ -30,44 +31,6 @@ #define GR_PRIME 0x9e370001 #define HASH(v, b) (((unsigned int)(v) * GR_PRIME) >> (32 - (b))) -/* largest prime smaller than 65536 */ -#define BASE 65521 - -/* 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; @@ -84,20 +47,15 @@ typedef struct s_chanode { } 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; + cha->ancur = NULL; } static void *cha_alloc(chastore_t *cha) @@ -111,12 +69,7 @@ static void *cha_alloc(chastore_t *cha) 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; + ancur->next = cha->ancur; cha->ancur = ancur; } @@ -127,7 +80,7 @@ static void *cha_alloc(chastore_t *cha) static void cha_free(chastore_t *cha) { - chanode_t *cur = cha->head; + chanode_t *cur = cha->ancur; while (cur) { chanode_t *tmp = cur; cur = cur->next; @@ -142,7 +95,6 @@ typedef struct s_bdrecord { } bdrecord_t; typedef struct s_bdfile { - const unsigned char *data, *top; chastore_t cha; unsigned int fphbits; bdrecord_t **fphash; @@ -152,7 +104,7 @@ 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; + const unsigned char *data, *top; bdrecord_t *brec; bdrecord_t **fphash; @@ -165,13 +117,12 @@ static int delta_prepare(const unsigned char *buf, int bufsize, bdfile_t *bdf) 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; + top = buf + bufsize; + data = buf + (bufsize / BLK_SIZE) * BLK_SIZE; if (data == top) data -= BLK_SIZE; - for ( ; data >= base; data -= BLK_SIZE) { + for ( ; data >= buf; data -= BLK_SIZE) { brec = cha_alloc(&bdf->cha); if (!brec) { cha_free(&bdf->cha); @@ -208,7 +159,7 @@ void *diff_delta(void *from_buf, unsigned long from_size, { int i, outpos, outsize, inscnt, csize, msize, moff; unsigned int fp; - const unsigned char *data, *top, *ptr1, *ptr2; + const unsigned char *ref_data, *ref_top, *data, *top, *ptr1, *ptr2; unsigned char *out, *orig; bdrecord_t *brec; bdfile_t bdf; @@ -224,32 +175,28 @@ void *diff_delta(void *from_buf, unsigned long from_size, return NULL; } + ref_data = from_buf; + ref_top = from_buf + from_size; data = to_buf; top = to_buf + to_size; /* store reference buffer size */ - orig = out + outpos++; - *orig = i = 0; - do { - if (from_size & 0xff) { - *orig |= (1 << i); - out[outpos++] = from_size; - } - i++; - from_size >>= 8; - } while (from_size); + out[outpos++] = from_size; + from_size >>= 7; + while (from_size) { + out[outpos - 1] |= 0x80; + out[outpos++] = from_size; + from_size >>= 7; + } /* store target buffer size */ - orig = out + outpos++; - *orig = i = 0; - do { - if (to_size & 0xff) { - *orig |= (1 << i); - out[outpos++] = to_size; - } - i++; - to_size >>= 8; - } while (to_size); + out[outpos++] = to_size; + to_size >>= 7; + while (to_size) { + out[outpos - 1] |= 0x80; + out[outpos++] = to_size; + to_size >>= 7; + } inscnt = 0; moff = 0; @@ -259,7 +206,7 @@ void *diff_delta(void *from_buf, unsigned long from_size, i = HASH(fp, bdf.fphbits); for (brec = bdf.fphash[i]; brec; brec = brec->next) { if (brec->fp == fp) { - csize = bdf.top - brec->ptr; + csize = ref_top - brec->ptr; if (csize > top - data) csize = top - data; for (ptr1 = brec->ptr, ptr2 = data; @@ -268,7 +215,7 @@ void *diff_delta(void *from_buf, unsigned long from_size, csize = ptr1 - brec->ptr; if (csize > msize) { - moff = brec->ptr - bdf.data; + moff = brec->ptr - ref_data; msize = csize; if (msize >= 0x10000) { msize = 0x10000; @@ -312,12 +259,13 @@ void *diff_delta(void *from_buf, unsigned long from_size, *orig = i; } - /* next time around the largest possible output is 1 + 4 + 3 */ if (max_size && outpos > max_size) { free(out); delta_cleanup(&bdf); return NULL; } + + /* next time around the largest possible output is 1 + 4 + 3 */ if (outpos > outsize - 8) { void *tmp = out; outsize = outsize * 3 / 2;