1 /*
2 * LibXDiff by Davide Libenzi ( File Differential Library )
3 * Copyright (C) 2003 Davide Libenzi
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 *
19 * Davide Libenzi <davidel@xmailserver.org>
20 *
21 */
22
23 #include "xinclude.h"
24
25
26 typedef struct s_bdrecord {
27 struct s_bdrecord *next;
28 unsigned long fp;
29 char const *ptr;
30 } bdrecord_t;
31
32 typedef struct s_bdfile {
33 char const *data, *top;
34 chastore_t cha;
35 unsigned int fphbits;
36 bdrecord_t **fphash;
37 } bdfile_t;
38
39
40
xdl_prepare_bdfile(mmbuffer_t * mmb,long fpbsize,bdfile_t * bdf)41 static int xdl_prepare_bdfile(mmbuffer_t *mmb, long fpbsize, bdfile_t *bdf) {
42 unsigned int fphbits;
43 long i, size, hsize;
44 char const *base, *data, *top;
45 bdrecord_t *brec;
46 bdrecord_t **fphash;
47
48 fphbits = xdl_hashbits((unsigned int) (mmb->size / fpbsize) + 1);
49 hsize = 1 << fphbits;
50 if (!(fphash = (bdrecord_t **) xdl_malloc(hsize * sizeof(bdrecord_t *)))) {
51
52 return -1;
53 }
54 for (i = 0; i < hsize; i++)
55 fphash[i] = NULL;
56
57 if (xdl_cha_init(&bdf->cha, sizeof(bdrecord_t), hsize / 4 + 1) < 0) {
58
59 xdl_free(fphash);
60 return -1;
61 }
62
63 if (!(size = mmb->size)) {
64 bdf->data = bdf->top = NULL;
65 } else {
66 bdf->data = data = base = mmb->ptr;
67 bdf->top = top = mmb->ptr + mmb->size;
68
69 if ((data += (size / fpbsize) * fpbsize) == top)
70 data -= fpbsize;
71
72 for (; data >= base; data -= fpbsize) {
73 if (!(brec = (bdrecord_t *) xdl_cha_alloc(&bdf->cha))) {
74
75 xdl_cha_free(&bdf->cha);
76 xdl_free(fphash);
77 return -1;
78 }
79
80 brec->fp = xdl_adler32(0, (unsigned char const *) data,
81 XDL_MIN(fpbsize, (long) (top - data)));
82 brec->ptr = data;
83
84 i = (long) XDL_HASHLONG(brec->fp, fphbits);
85 brec->next = fphash[i];
86 fphash[i] = brec;
87 }
88 }
89
90 bdf->fphbits = fphbits;
91 bdf->fphash = fphash;
92
93 return 0;
94 }
95
96
xdl_free_bdfile(bdfile_t * bdf)97 static void xdl_free_bdfile(bdfile_t *bdf) {
98
99 xdl_free(bdf->fphash);
100 xdl_cha_free(&bdf->cha);
101 }
102
103
xdl_mmb_adler32(mmbuffer_t * mmb)104 unsigned long xdl_mmb_adler32(mmbuffer_t *mmb) {
105
106 return mmb->size ? xdl_adler32(0, (unsigned char const *) mmb->ptr, mmb->size): 0;
107 }
108
109
xdl_mmf_adler32(mmfile_t * mmf)110 unsigned long xdl_mmf_adler32(mmfile_t *mmf) {
111 unsigned long fp = 0;
112 long size;
113 char const *blk;
114
115 if ((blk = (char const *) xdl_mmfile_first(mmf, &size)) != NULL) {
116 do {
117 fp = xdl_adler32(fp, (unsigned char const *) blk, size);
118 } while ((blk = (char const *) xdl_mmfile_next(mmf, &size)) != NULL);
119 }
120 return fp;
121 }
122
123
xdl_bdiff_mb(mmbuffer_t * mmb1,mmbuffer_t * mmb2,bdiffparam_t const * bdp,xdemitcb_t * ecb)124 int xdl_bdiff_mb(mmbuffer_t *mmb1, mmbuffer_t *mmb2, bdiffparam_t const *bdp, xdemitcb_t *ecb) {
125 long i, rsize, size, bsize, csize, msize, moff;
126 unsigned long fp;
127 char const *blk, *base, *data, *top, *ptr1, *ptr2;
128 bdrecord_t *brec;
129 bdfile_t bdf;
130 mmbuffer_t mb[2];
131 unsigned char cpybuf[32];
132
133 if ((bsize = bdp->bsize) < XDL_MIN_BLKSIZE)
134 bsize = XDL_MIN_BLKSIZE;
135 if (xdl_prepare_bdfile(mmb1, bsize, &bdf) < 0) {
136
137 return -1;
138 }
139
140 /*
141 * Prepare and emit the binary patch file header. It will be used
142 * to verify that that file being patched matches in size and fingerprint
143 * the one that generated the patch.
144 */
145 fp = xdl_mmb_adler32(mmb1);
146 size = mmb1->size;
147 XDL_LE32_PUT(cpybuf, fp);
148 XDL_LE32_PUT(cpybuf + 4, size);
149
150 mb[0].ptr = (char *) cpybuf;
151 mb[0].size = 4 + 4;
152
153 if (ecb->outf(ecb->priv, mb, 1) < 0) {
154
155 xdl_free_bdfile(&bdf);
156 return -1;
157 }
158
159 if ((blk = (char const *) mmb2->ptr) != NULL) {
160 size = mmb2->size;
161 for (base = data = blk, top = data + size; data < top;) {
162 rsize = XDL_MIN(bsize, (long) (top - data));
163 fp = xdl_adler32(0, (unsigned char const *) data, rsize);
164
165 i = (long) XDL_HASHLONG(fp, bdf.fphbits);
166 for (msize = 0, brec = bdf.fphash[i]; brec; brec = brec->next)
167 if (brec->fp == fp) {
168 csize = XDL_MIN((long) (top - data), (long) (bdf.top - brec->ptr));
169 for (ptr1 = brec->ptr, ptr2 = data; csize && *ptr1 == *ptr2;
170 csize--, ptr1++, ptr2++);
171
172 if ((csize = (long) (ptr1 - brec->ptr)) > msize) {
173 moff = (long) (brec->ptr - bdf.data);
174 msize = csize;
175 }
176 }
177
178 if (msize < XDL_COPYOP_SIZE) {
179 data++;
180 } else {
181 if (data > base) {
182 i = (long) (data - base);
183 if (i > 255) {
184 cpybuf[0] = XDL_BDOP_INSB;
185 XDL_LE32_PUT(cpybuf + 1, i);
186
187 mb[0].ptr = (char *) cpybuf;
188 mb[0].size = XDL_INSBOP_SIZE;
189 } else {
190 cpybuf[0] = XDL_BDOP_INS;
191 cpybuf[1] = (unsigned char) i;
192
193 mb[0].ptr = (char *) cpybuf;
194 mb[0].size = 2;
195 }
196 mb[1].ptr = (char *) base;
197 mb[1].size = i;
198
199 if (ecb->outf(ecb->priv, mb, 2) < 0) {
200
201 xdl_free_bdfile(&bdf);
202 return -1;
203 }
204 }
205
206 data += msize;
207
208 cpybuf[0] = XDL_BDOP_CPY;
209 XDL_LE32_PUT(cpybuf + 1, moff);
210 XDL_LE32_PUT(cpybuf + 5, msize);
211
212 mb[0].ptr = (char *) cpybuf;
213 mb[0].size = XDL_COPYOP_SIZE;
214
215 if (ecb->outf(ecb->priv, mb, 1) < 0) {
216
217 xdl_free_bdfile(&bdf);
218 return -1;
219 }
220 base = data;
221 }
222 }
223 if (data > base) {
224 i = (long) (data - base);
225 if (i > 255) {
226 cpybuf[0] = XDL_BDOP_INSB;
227 XDL_LE32_PUT(cpybuf + 1, i);
228
229 mb[0].ptr = (char *) cpybuf;
230 mb[0].size = XDL_INSBOP_SIZE;
231 } else {
232 cpybuf[0] = XDL_BDOP_INS;
233 cpybuf[1] = (unsigned char) i;
234
235 mb[0].ptr = (char *) cpybuf;
236 mb[0].size = 2;
237 }
238 mb[1].ptr = (char *) base;
239 mb[1].size = i;
240
241 if (ecb->outf(ecb->priv, mb, 2) < 0) {
242
243 xdl_free_bdfile(&bdf);
244 return -1;
245 }
246 }
247 }
248
249 xdl_free_bdfile(&bdf);
250
251 return 0;
252 }
253
254
xdl_bdiff(mmfile_t * mmf1,mmfile_t * mmf2,bdiffparam_t const * bdp,xdemitcb_t * ecb)255 int xdl_bdiff(mmfile_t *mmf1, mmfile_t *mmf2, bdiffparam_t const *bdp, xdemitcb_t *ecb) {
256 mmbuffer_t mmb1, mmb2;
257
258 if (!xdl_mmfile_iscompact(mmf1) || !xdl_mmfile_iscompact(mmf2)) {
259
260 return -1;
261 }
262
263 if ((mmb1.ptr = (char *) xdl_mmfile_first(mmf1, &mmb1.size)) == NULL)
264 mmb1.size = 0;
265 if ((mmb2.ptr = (char *) xdl_mmfile_first(mmf2, &mmb2.size)) == NULL)
266 mmb2.size = 0;
267
268 return xdl_bdiff_mb(&mmb1, &mmb2, bdp, ecb);
269 }
270
271
xdl_bdiff_tgsize(mmfile_t * mmfp)272 long xdl_bdiff_tgsize(mmfile_t *mmfp) {
273 long tgsize = 0, size, off, csize;
274 char const *blk;
275 unsigned char const *data, *top;
276
277 if ((blk = (char const *) xdl_mmfile_first(mmfp, &size)) == NULL ||
278 size < XDL_BPATCH_HDR_SIZE) {
279
280 return -1;
281 }
282 blk += XDL_BPATCH_HDR_SIZE;
283 size -= XDL_BPATCH_HDR_SIZE;
284
285 do {
286 for (data = (unsigned char const *) blk, top = data + size;
287 data < top;) {
288 if (*data == XDL_BDOP_INS) {
289 data++;
290 csize = (long) *data++;
291 tgsize += csize;
292 data += csize;
293 } else if (*data == XDL_BDOP_INSB) {
294 data++;
295 XDL_LE32_GET(data, csize);
296 data += 4;
297 tgsize += csize;
298 data += csize;
299 } else if (*data == XDL_BDOP_CPY) {
300 data++;
301 XDL_LE32_GET(data, off);
302 data += 4;
303 XDL_LE32_GET(data, csize);
304 data += 4;
305 tgsize += csize;
306 } else {
307
308 return -1;
309 }
310 }
311 } while ((blk = (char const *) xdl_mmfile_next(mmfp, &size)) != NULL);
312
313 return tgsize;
314 }
315
316