*/
#include <stdlib.h>
+#include <string.h>
#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, 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;
- 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;
+ 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 long trg_bufsize)
{
- 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)
- 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;
+ unsigned long hsize;
+ unsigned int i, hshift, hlimit, *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);
+ hsize = 1 << i;
+ hshift = (i - 8) / 2;
+
+ /*
+ * 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));
+ if (!mem)
+ return NULL;
+ hash = mem;
+ *hash++ = (void *)hshift;
+ entry = mem + (1 + 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;
}
- bdf->fphbits = fphbits;
- bdf->fphash = fphash;
-
- return 0;
-}
+ /* then populate the index */
+ data = buf + bufsize - 2;
+ while (data > buf) {
+ entry->ptr = --data;
+ i = data[0] ^ ((data[1] ^ (data[2] << hshift)) << hshift);
+ entry->next = hash[i];
+ hash[i] = entry++;
+ hash_count[i]++;
+ }
+
+ /*
+ * 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 < 16)
+ hlimit = 16;
+
+ /*
+ * 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
+ * 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);
-static void delta_cleanup(bdfile_t *bdf)
-{
- free(bdf->fphash);
- cha_free(&bdf->cha);
+ return hash-1;
}
+/* 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)
+ unsigned long max_size,
+ void **from_index)
{
- 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 (delta_prepare(from_buf, from_size, &bdf))
+ 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++);
+
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);
+ if (!from_index)
+ free(hash-1);
return NULL;
}
+ ref_data = from_buf;
+ ref_top = from_buf + from_size;
data = to_buf;
top = to_buf + to_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;
+ if (data + 3 <= top) {
+ i = data[0] ^ ((data[1] ^ (data[2] << hash_shift)) << 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 (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);
+ if (msize < ref - entry->ptr) {
+ /* this is our best match so far */
+ msize = ref - entry->ptr;
+ moff = entry->ptr - ref_data;
}
}
}
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; }
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);
+ if (!from_index)
+ free(hash-1);
return NULL;
}
}
if (inscnt)
out[outpos - inscnt - 1] = inscnt;
- delta_cleanup(&bdf);
+ if (!from_index)
+ free(hash-1);
*delta_size = outpos;
return out;
}