]>
Commit | Line | Data |
---|---|---|
a310d434 NP |
1 | /* |
2 | * diff-delta.c: generate a delta between two buffers | |
3 | * | |
4 | * Many parts of this file have been lifted from LibXDiff version 0.10. | |
5 | * http://www.xmailserver.org/xdiff-lib.html | |
6 | * | |
7 | * LibXDiff was written by Davide Libenzi <davidel@xmailserver.org> | |
8 | * Copyright (C) 2003 Davide Libenzi | |
9 | * | |
10 | * Many mods for GIT usage by Nicolas Pitre <nico@cam.org>, (C) 2005. | |
11 | * | |
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. | |
16 | * | |
17 | * Use of this within git automatically means that the LGPL | |
18 | * licensing gets turned into GPLv2 within this project. | |
19 | */ | |
20 | ||
21 | #include <stdlib.h> | |
22 | #include "delta.h" | |
04fe2a17 | 23 | #include "zlib.h" |
a310d434 NP |
24 | |
25 | ||
26 | /* block size: min = 16, max = 64k, power of 2 */ | |
27 | #define BLK_SIZE 16 | |
28 | ||
29 | #define MIN(a, b) ((a) < (b) ? (a) : (b)) | |
30 | ||
31 | #define GR_PRIME 0x9e370001 | |
32 | #define HASH(v, b) (((unsigned int)(v) * GR_PRIME) >> (32 - (b))) | |
33 | ||
a310d434 NP |
34 | static unsigned int hashbits(unsigned int size) |
35 | { | |
36 | unsigned int val = 1, bits = 0; | |
37 | while (val < size && bits < 32) { | |
38 | val <<= 1; | |
39 | bits++; | |
40 | } | |
41 | return bits ? bits: 1; | |
42 | } | |
43 | ||
44 | typedef struct s_chanode { | |
45 | struct s_chanode *next; | |
46 | int icurr; | |
47 | } chanode_t; | |
48 | ||
49 | typedef struct s_chastore { | |
a310d434 NP |
50 | int isize, nsize; |
51 | chanode_t *ancur; | |
a310d434 NP |
52 | } chastore_t; |
53 | ||
54 | static void cha_init(chastore_t *cha, int isize, int icount) | |
55 | { | |
a310d434 NP |
56 | cha->isize = isize; |
57 | cha->nsize = icount * isize; | |
e5e3a9d8 | 58 | cha->ancur = NULL; |
a310d434 NP |
59 | } |
60 | ||
61 | static void *cha_alloc(chastore_t *cha) | |
62 | { | |
63 | chanode_t *ancur; | |
64 | void *data; | |
65 | ||
66 | ancur = cha->ancur; | |
67 | if (!ancur || ancur->icurr == cha->nsize) { | |
68 | ancur = malloc(sizeof(chanode_t) + cha->nsize); | |
69 | if (!ancur) | |
70 | return NULL; | |
71 | ancur->icurr = 0; | |
e5e3a9d8 | 72 | ancur->next = cha->ancur; |
a310d434 NP |
73 | cha->ancur = ancur; |
74 | } | |
75 | ||
76 | data = (void *)ancur + sizeof(chanode_t) + ancur->icurr; | |
77 | ancur->icurr += cha->isize; | |
78 | return data; | |
79 | } | |
80 | ||
81 | static void cha_free(chastore_t *cha) | |
82 | { | |
e5e3a9d8 | 83 | chanode_t *cur = cha->ancur; |
a310d434 NP |
84 | while (cur) { |
85 | chanode_t *tmp = cur; | |
86 | cur = cur->next; | |
87 | free(tmp); | |
88 | } | |
89 | } | |
90 | ||
91 | typedef struct s_bdrecord { | |
92 | struct s_bdrecord *next; | |
93 | unsigned int fp; | |
94 | const unsigned char *ptr; | |
95 | } bdrecord_t; | |
96 | ||
97 | typedef struct s_bdfile { | |
a310d434 NP |
98 | chastore_t cha; |
99 | unsigned int fphbits; | |
100 | bdrecord_t **fphash; | |
101 | } bdfile_t; | |
102 | ||
103 | static int delta_prepare(const unsigned char *buf, int bufsize, bdfile_t *bdf) | |
104 | { | |
105 | unsigned int fphbits; | |
106 | int i, hsize; | |
e5e3a9d8 | 107 | const unsigned char *data, *top; |
a310d434 NP |
108 | bdrecord_t *brec; |
109 | bdrecord_t **fphash; | |
110 | ||
111 | fphbits = hashbits(bufsize / BLK_SIZE + 1); | |
112 | hsize = 1 << fphbits; | |
113 | fphash = malloc(hsize * sizeof(bdrecord_t *)); | |
114 | if (!fphash) | |
115 | return -1; | |
116 | for (i = 0; i < hsize; i++) | |
117 | fphash[i] = NULL; | |
118 | cha_init(&bdf->cha, sizeof(bdrecord_t), hsize / 4 + 1); | |
119 | ||
e5e3a9d8 NP |
120 | top = buf + bufsize; |
121 | data = buf + (bufsize / BLK_SIZE) * BLK_SIZE; | |
a310d434 NP |
122 | if (data == top) |
123 | data -= BLK_SIZE; | |
124 | ||
e5e3a9d8 | 125 | for ( ; data >= buf; data -= BLK_SIZE) { |
a310d434 NP |
126 | brec = cha_alloc(&bdf->cha); |
127 | if (!brec) { | |
128 | cha_free(&bdf->cha); | |
129 | free(fphash); | |
130 | return -1; | |
131 | } | |
132 | brec->fp = adler32(0, data, MIN(BLK_SIZE, top - data)); | |
133 | brec->ptr = data; | |
134 | i = HASH(brec->fp, fphbits); | |
135 | brec->next = fphash[i]; | |
136 | fphash[i] = brec; | |
137 | } | |
138 | ||
139 | bdf->fphbits = fphbits; | |
140 | bdf->fphash = fphash; | |
141 | ||
142 | return 0; | |
143 | } | |
144 | ||
145 | static void delta_cleanup(bdfile_t *bdf) | |
146 | { | |
147 | free(bdf->fphash); | |
148 | cha_free(&bdf->cha); | |
149 | } | |
150 | ||
151 | #define COPYOP_SIZE(o, s) \ | |
152 | (!!(o & 0xff) + !!(o & 0xff00) + !!(o & 0xff0000) + !!(o & 0xff000000) + \ | |
153 | !!(s & 0xff) + !!(s & 0xff00) + 1) | |
154 | ||
155 | void *diff_delta(void *from_buf, unsigned long from_size, | |
156 | void *to_buf, unsigned long to_size, | |
75c42d8c LT |
157 | unsigned long *delta_size, |
158 | unsigned long max_size) | |
a310d434 NP |
159 | { |
160 | int i, outpos, outsize, inscnt, csize, msize, moff; | |
161 | unsigned int fp; | |
e5e3a9d8 | 162 | const unsigned char *ref_data, *ref_top, *data, *top, *ptr1, *ptr2; |
a310d434 NP |
163 | unsigned char *out, *orig; |
164 | bdrecord_t *brec; | |
165 | bdfile_t bdf; | |
166 | ||
c7a45bd2 | 167 | if (!from_size || !to_size || delta_prepare(from_buf, from_size, &bdf)) |
a310d434 NP |
168 | return NULL; |
169 | ||
170 | outpos = 0; | |
171 | outsize = 8192; | |
172 | out = malloc(outsize); | |
173 | if (!out) { | |
174 | delta_cleanup(&bdf); | |
175 | return NULL; | |
176 | } | |
177 | ||
e5e3a9d8 NP |
178 | ref_data = from_buf; |
179 | ref_top = from_buf + from_size; | |
a310d434 NP |
180 | data = to_buf; |
181 | top = to_buf + to_size; | |
182 | ||
183 | /* store reference buffer size */ | |
69a2d426 NP |
184 | out[outpos++] = from_size; |
185 | from_size >>= 7; | |
186 | while (from_size) { | |
187 | out[outpos - 1] |= 0x80; | |
188 | out[outpos++] = from_size; | |
189 | from_size >>= 7; | |
190 | } | |
a310d434 NP |
191 | |
192 | /* store target buffer size */ | |
69a2d426 NP |
193 | out[outpos++] = to_size; |
194 | to_size >>= 7; | |
195 | while (to_size) { | |
196 | out[outpos - 1] |= 0x80; | |
197 | out[outpos++] = to_size; | |
198 | to_size >>= 7; | |
199 | } | |
a310d434 NP |
200 | |
201 | inscnt = 0; | |
202 | moff = 0; | |
203 | while (data < top) { | |
204 | msize = 0; | |
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) { | |
e5e3a9d8 | 209 | csize = ref_top - brec->ptr; |
a310d434 NP |
210 | if (csize > top - data) |
211 | csize = top - data; | |
212 | for (ptr1 = brec->ptr, ptr2 = data; | |
213 | csize && *ptr1 == *ptr2; | |
214 | csize--, ptr1++, ptr2++); | |
215 | ||
216 | csize = ptr1 - brec->ptr; | |
217 | if (csize > msize) { | |
e5e3a9d8 | 218 | moff = brec->ptr - ref_data; |
a310d434 NP |
219 | msize = csize; |
220 | if (msize >= 0x10000) { | |
221 | msize = 0x10000; | |
222 | break; | |
223 | } | |
224 | } | |
225 | } | |
226 | } | |
227 | ||
228 | if (!msize || msize < COPYOP_SIZE(moff, msize)) { | |
229 | if (!inscnt) | |
230 | outpos++; | |
231 | out[outpos++] = *data++; | |
232 | inscnt++; | |
233 | if (inscnt == 0x7f) { | |
234 | out[outpos - inscnt - 1] = inscnt; | |
235 | inscnt = 0; | |
236 | } | |
237 | } else { | |
238 | if (inscnt) { | |
239 | out[outpos - inscnt - 1] = inscnt; | |
240 | inscnt = 0; | |
241 | } | |
242 | ||
243 | data += msize; | |
244 | orig = out + outpos++; | |
245 | i = 0x80; | |
246 | ||
247 | if (moff & 0xff) { out[outpos++] = moff; i |= 0x01; } | |
248 | moff >>= 8; | |
249 | if (moff & 0xff) { out[outpos++] = moff; i |= 0x02; } | |
250 | moff >>= 8; | |
251 | if (moff & 0xff) { out[outpos++] = moff; i |= 0x04; } | |
252 | moff >>= 8; | |
253 | if (moff & 0xff) { out[outpos++] = moff; i |= 0x08; } | |
254 | ||
255 | if (msize & 0xff) { out[outpos++] = msize; i |= 0x10; } | |
256 | msize >>= 8; | |
257 | if (msize & 0xff) { out[outpos++] = msize; i |= 0x20; } | |
258 | ||
259 | *orig = i; | |
260 | } | |
261 | ||
75c42d8c LT |
262 | if (max_size && outpos > max_size) { |
263 | free(out); | |
264 | delta_cleanup(&bdf); | |
265 | return NULL; | |
266 | } | |
dcde55bc NP |
267 | |
268 | /* next time around the largest possible output is 1 + 4 + 3 */ | |
a310d434 NP |
269 | if (outpos > outsize - 8) { |
270 | void *tmp = out; | |
271 | outsize = outsize * 3 / 2; | |
272 | out = realloc(out, outsize); | |
273 | if (!out) { | |
274 | free(tmp); | |
275 | delta_cleanup(&bdf); | |
276 | return NULL; | |
277 | } | |
278 | } | |
279 | } | |
280 | ||
281 | if (inscnt) | |
282 | out[outpos - inscnt - 1] = inscnt; | |
283 | ||
284 | delta_cleanup(&bdf); | |
285 | *delta_size = outpos; | |
286 | return out; | |
287 | } |