2 * diff-delta.c: generate a delta between two buffers
4 * Many parts of this file have been lifted from LibXDiff version 0.10.
5 * http://www.xmailserver.org/xdiff-lib.html
7 * LibXDiff was written by Davide Libenzi <davidel@xmailserver.org>
8 * Copyright (C) 2003 Davide Libenzi
10 * Many mods for GIT usage by Nicolas Pitre <nico@cam.org>, (C) 2005.
12 * This file is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU Lesser General Public
14 * License as published by the Free Software Foundation; either
15 * version 2.1 of the License, or (at your option) any later version.
17 * Use of this within git automatically means that the LGPL
18 * licensing gets turned into GPLv2 within this project.
26 /* block size: min = 16, max = 64k, power of 2 */
29 #define MIN(a, b) ((a) < (b) ? (a) : (b))
31 #define GR_PRIME 0x9e370001
32 #define HASH(v, b) (((unsigned int)(v) * GR_PRIME) >> (32 - (b)))
34 static unsigned int hashbits(unsigned int size)
36 unsigned int val = 1, bits = 0;
37 while (val < size && bits < 32) {
41 return bits ? bits: 1;
44 typedef struct s_chanode {
45 struct s_chanode *next;
49 typedef struct s_chastore {
54 static void cha_init(chastore_t *cha, int isize, int icount)
57 cha->nsize = icount * isize;
61 static void *cha_alloc(chastore_t *cha)
67 if (!ancur || ancur->icurr == cha->nsize) {
68 ancur = malloc(sizeof(chanode_t) + cha->nsize);
72 ancur->next = cha->ancur;
76 data = (void *)ancur + sizeof(chanode_t) + ancur->icurr;
77 ancur->icurr += cha->isize;
81 static void cha_free(chastore_t *cha)
83 chanode_t *cur = cha->ancur;
91 typedef struct s_bdrecord {
92 struct s_bdrecord *next;
94 const unsigned char *ptr;
97 typedef struct s_bdfile {
103 static int delta_prepare(const unsigned char *buf, int bufsize, bdfile_t *bdf)
105 unsigned int fphbits;
107 const unsigned char *data, *top;
111 fphbits = hashbits(bufsize / BLK_SIZE + 1);
112 hsize = 1 << fphbits;
113 fphash = malloc(hsize * sizeof(bdrecord_t *));
116 for (i = 0; i < hsize; i++)
118 cha_init(&bdf->cha, sizeof(bdrecord_t), hsize / 4 + 1);
121 data = buf + (bufsize / BLK_SIZE) * BLK_SIZE;
125 for ( ; data >= buf; data -= BLK_SIZE) {
126 brec = cha_alloc(&bdf->cha);
132 brec->fp = adler32(0, data, MIN(BLK_SIZE, top - data));
134 i = HASH(brec->fp, fphbits);
135 brec->next = fphash[i];
139 bdf->fphbits = fphbits;
140 bdf->fphash = fphash;
145 static void delta_cleanup(bdfile_t *bdf)
151 #define COPYOP_SIZE(o, s) \
152 (!!(o & 0xff) + !!(o & 0xff00) + !!(o & 0xff0000) + !!(o & 0xff000000) + \
153 !!(s & 0xff) + !!(s & 0xff00) + 1)
155 void *diff_delta(void *from_buf, unsigned long from_size,
156 void *to_buf, unsigned long to_size,
157 unsigned long *delta_size,
158 unsigned long max_size)
160 int i, outpos, outsize, inscnt, csize, msize, moff;
162 const unsigned char *ref_data, *ref_top, *data, *top, *ptr1, *ptr2;
163 unsigned char *out, *orig;
167 if (!from_size || !to_size || delta_prepare(from_buf, from_size, &bdf))
172 out = malloc(outsize);
179 ref_top = from_buf + from_size;
181 top = to_buf + to_size;
183 /* store reference buffer size */
184 out[outpos++] = from_size;
187 out[outpos - 1] |= 0x80;
188 out[outpos++] = from_size;
192 /* store target buffer size */
193 out[outpos++] = to_size;
196 out[outpos - 1] |= 0x80;
197 out[outpos++] = to_size;
205 fp = adler32(0, data, MIN(top - data, BLK_SIZE));
206 i = HASH(fp, bdf.fphbits);
207 for (brec = bdf.fphash[i]; brec; brec = brec->next) {
208 if (brec->fp == fp) {
209 csize = ref_top - brec->ptr;
210 if (csize > top - data)
212 for (ptr1 = brec->ptr, ptr2 = data;
213 csize && *ptr1 == *ptr2;
214 csize--, ptr1++, ptr2++);
216 csize = ptr1 - brec->ptr;
218 moff = brec->ptr - ref_data;
220 if (msize >= 0x10000) {
228 if (!msize || msize < COPYOP_SIZE(moff, msize)) {
231 out[outpos++] = *data++;
233 if (inscnt == 0x7f) {
234 out[outpos - inscnt - 1] = inscnt;
239 out[outpos - inscnt - 1] = inscnt;
244 orig = out + outpos++;
247 if (moff & 0xff) { out[outpos++] = moff; i |= 0x01; }
249 if (moff & 0xff) { out[outpos++] = moff; i |= 0x02; }
251 if (moff & 0xff) { out[outpos++] = moff; i |= 0x04; }
253 if (moff & 0xff) { out[outpos++] = moff; i |= 0x08; }
255 if (msize & 0xff) { out[outpos++] = msize; i |= 0x10; }
257 if (msize & 0xff) { out[outpos++] = msize; i |= 0x20; }
262 if (max_size && outpos > max_size) {
268 /* next time around the largest possible output is 1 + 4 + 3 */
269 if (outpos > outsize - 8) {
271 outsize = outsize * 3 / 2;
272 out = realloc(out, outsize);
282 out[outpos - inscnt - 1] = inscnt;
285 *delta_size = outpos;