Merge part of np/delta
[gitweb.git] / diff-delta.c
index b2ae7b5e6c3b4aa409ccfa60f67d5c8eb1690504..2ed5984b1c360194d53fd287962d7857e19a097c 100644 (file)
@@ -19,6 +19,8 @@
  */
 
 #include <stdlib.h>
+#include <string.h>
+#include <zlib.h>
 #include "delta.h"
 
 
 #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)
-{
-       chanode_t *cur = cha->head;
-       while (cur) {
-               chanode_t *tmp = cur;
-               cur = cur->next;
-               free(tmp);
-       }
-}
-
-typedef struct s_bdrecord {
-       struct s_bdrecord *next;
-       unsigned int fp;
+struct index {
        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;
+       unsigned int val;
+       struct index *next;
+};
 
-static int delta_prepare(const unsigned char *buf, int bufsize, bdfile_t *bdf)
+static struct index ** delta_index(const unsigned char *buf,
+                                  unsigned long bufsize,
+                                  unsigned int *hash_shift)
 {
-       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)
+       unsigned int hsize, hshift, entries, blksize, i;
+       const unsigned char *data;
+       struct index *entry, **hash;
+       void *mem;
+
+       /* determine index hash size */
+       entries = (bufsize + BLK_SIZE - 1) / BLK_SIZE;
+       hsize = entries / 4;
+       for (i = 4; (1 << i) < hsize && i < 16; 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));
+
+       /* then populate it */
+       data = buf + entries * BLK_SIZE - BLK_SIZE;
+       blksize = bufsize - (data - buf);
+       while (data >= buf) {
+               unsigned int val = adler32(0, data, blksize);
+               i = HASH(val, hshift);
+               entry->ptr = data;
+               entry->val = val;
+               entry->next = hash[i];
+               hash[i] = entry++;
+               blksize = BLK_SIZE;
                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;
-       }
-
-       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;
+       unsigned int i, outpos, outsize, inscnt, hash_shift;
+       const unsigned char *ref_data, *ref_top, *data, *top;
+       unsigned char *out;
+       struct index *entry, **hash;
 
-       if (!from_size || !to_size || delta_prepare(from_buf, from_size, &bdf))
+       if (!from_size || !to_size)
+               return NULL;
+       hash = delta_index(from_buf, from_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 +138,32 @@ 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;
-                                       }
+       while (data < top) {
+               unsigned int moff = 0, msize = 0;
+               unsigned int blksize = MIN(top - data, BLK_SIZE);
+               unsigned int val = adler32(0, data, blksize);
+               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;
+                       while (ref_size && *src++ == *ref) {
+                               ref++;
+                               ref_size--;
+                       }
+                       ref_size = ref - entry->ptr;
+                       if (ref_size > msize) {
+                               /* this is our best match so far */
+                               moff = entry->ptr - ref_data;
+                               msize = ref_size;
+                               if (msize >= 0x10000) {
+                                       msize = 0x10000;
+                                       break;
                                }
                        }
                }
@@ -282,13 +178,15 @@ void *diff_delta(void *from_buf, unsigned long from_size,
                                inscnt = 0;
                        }
                } else {
+                       unsigned char *op;
+
                        if (inscnt) {
                                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 +201,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 +224,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;
 }