diff options
author | dotdotisdead <dotdotisdead@a3eca27d-f21b-0410-9b4a-6511e771f64e> | 2006-09-30 04:47:47 +0000 |
---|---|---|
committer | dotdotisdead <dotdotisdead@a3eca27d-f21b-0410-9b4a-6511e771f64e> | 2006-09-30 04:47:47 +0000 |
commit | ad85653ca73c8126de516b9a4294e8f08577c00d (patch) | |
tree | 79fb4d644ccf6a4fe8dac146b801a21d63537b23 /xdelta1/xdrsync.c | |
parent | 5a7c245871879325d7b05c06e0b2011203986ee8 (diff) |
import 1.1.3
Diffstat (limited to 'xdelta1/xdrsync.c')
-rwxr-xr-x | xdelta1/xdrsync.c | 443 |
1 files changed, 443 insertions, 0 deletions
diff --git a/xdelta1/xdrsync.c b/xdelta1/xdrsync.c new file mode 100755 index 0000000..db7ed94 --- /dev/null +++ b/xdelta1/xdrsync.c | |||
@@ -0,0 +1,443 @@ | |||
1 | /* -*- Mode: C;-*- | ||
2 | * | ||
3 | * This file is part of XDelta - A binary delta generator. | ||
4 | * | ||
5 | * Copyright (C) 1997, 1998, 1999 Josh MacDonald | ||
6 | * | ||
7 | * This program is free software; you can redistribute it and/or modify | ||
8 | * it under the terms of the GNU General Public License as published by | ||
9 | * the Free Software Foundation; either version 2 of the License, or | ||
10 | * (at your option) any later version. | ||
11 | * | ||
12 | * This program is distributed in the hope that it will be useful, | ||
13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||
15 | * GNU General Public License for more details. | ||
16 | * | ||
17 | * You should have received a copy of the GNU General Public License | ||
18 | * along with this program; if not, write to the Free Software | ||
19 | * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. | ||
20 | * | ||
21 | * Author: Josh MacDonald <jmacd@CS.Berkeley.EDU> | ||
22 | * | ||
23 | * $Id: xdrsync.c 1.2 Thu, 01 Apr 1999 23:29:11 -0800 jmacd $ | ||
24 | */ | ||
25 | |||
26 | #include <string.h> | ||
27 | #include <stdlib.h> | ||
28 | |||
29 | #include "xdelta.h" | ||
30 | #include "xdeltapriv.h" | ||
31 | |||
32 | /* Rsync | ||
33 | */ | ||
34 | |||
35 | static void | ||
36 | init_long_checksum (const guint8 *buf, guint len, XdeltaChecksum *cksum) | ||
37 | { | ||
38 | guint16 low = cksum->low; | ||
39 | guint16 high = cksum->high; | ||
40 | |||
41 | /* @@@ unroll me? */ | ||
42 | for (; len > 0; len -= 1) | ||
43 | { | ||
44 | low += CHEW(*buf++); | ||
45 | high += low; | ||
46 | } | ||
47 | |||
48 | cksum->low = low; | ||
49 | cksum->high = high; | ||
50 | } | ||
51 | |||
52 | static XdeltaRsync* | ||
53 | xdp_rsync_index_int (XdeltaStream *str, | ||
54 | guint seg_len) | ||
55 | { | ||
56 | guint to_index = seg_len; | ||
57 | XdeltaPos pos; | ||
58 | XdeltaChecksum cksum; | ||
59 | GArray *index; | ||
60 | EdsioMD5Ctx ctx; | ||
61 | |||
62 | index = g_array_new (FALSE, FALSE, sizeof (XdeltaRsyncElt)); | ||
63 | |||
64 | init_pos (str, &pos); | ||
65 | |||
66 | memset (&cksum, 0, sizeof (cksum)); | ||
67 | |||
68 | edsio_md5_init (& ctx); | ||
69 | |||
70 | for (;;) | ||
71 | { | ||
72 | gint consume; | ||
73 | |||
74 | if (! map_page (str, &pos)) | ||
75 | return NULL; | ||
76 | |||
77 | consume = MIN (to_index, pos.mem_rem - pos.off); | ||
78 | |||
79 | if (consume == 0) | ||
80 | break; | ||
81 | |||
82 | to_index -= consume; | ||
83 | |||
84 | edsio_md5_update (& ctx, pos.mem + pos.off, consume); | ||
85 | init_long_checksum (pos.mem + pos.off, consume, &cksum); | ||
86 | |||
87 | if (to_index == 0) | ||
88 | { | ||
89 | XdeltaRsyncElt elt; | ||
90 | |||
91 | edsio_md5_final (elt.md5, &ctx); | ||
92 | |||
93 | elt.cksum = cksum; | ||
94 | |||
95 | g_array_append_val (index, elt); | ||
96 | |||
97 | edsio_md5_init (& ctx); | ||
98 | memset (&cksum, 0, sizeof (cksum)); | ||
99 | to_index = seg_len; | ||
100 | } | ||
101 | |||
102 | pos.off += consume; | ||
103 | |||
104 | FLIP_FORWARD (pos); | ||
105 | } | ||
106 | |||
107 | if (! unmap_page (str, &pos)) | ||
108 | return NULL; | ||
109 | |||
110 | { | ||
111 | XdeltaRsync* rsync = g_new (XdeltaRsync, 1); | ||
112 | |||
113 | rsync->seg_len = seg_len; | ||
114 | rsync->file_len = handle_length (str); | ||
115 | |||
116 | memcpy (rsync->file_md5, handle_checksum_md5 (str), 16); | ||
117 | |||
118 | rsync->index = &g_array_index (index, XdeltaRsyncElt, 0); | ||
119 | rsync->index_len = index->len; | ||
120 | |||
121 | return rsync; | ||
122 | } | ||
123 | } | ||
124 | |||
125 | static XdeltaRsync* | ||
126 | xdp_rsync_read_index (XdeltaStream* cache_in) | ||
127 | { | ||
128 | SerialSource* src = handle_source (cache_in); | ||
129 | XdeltaRsync* rsync; | ||
130 | |||
131 | if (! src) | ||
132 | return NULL; | ||
133 | |||
134 | if (! unserialize_rsyncindex (src, &rsync)) | ||
135 | return NULL; | ||
136 | |||
137 | return rsync; | ||
138 | } | ||
139 | |||
140 | static gboolean | ||
141 | xdp_rsync_write_index (XdeltaRsync* rsync, | ||
142 | XdeltaOutStream* cache_out) | ||
143 | { | ||
144 | SerialSink* sink = handle_sink (cache_out, NULL, NULL, NULL, NULL); | ||
145 | |||
146 | if (! sink) | ||
147 | return FALSE; | ||
148 | |||
149 | if (! serialize_rsyncindex_obj (sink, rsync)) | ||
150 | return FALSE; | ||
151 | |||
152 | if (! handle_close (cache_out, 0)) | ||
153 | return FALSE; | ||
154 | |||
155 | return TRUE; | ||
156 | } | ||
157 | |||
158 | XdeltaRsync* | ||
159 | xdp_rsync_index (XdeltaStream *str, | ||
160 | guint seg_len, | ||
161 | XdeltaStream *cache_in, | ||
162 | XdeltaOutStream *cache_out) | ||
163 | { | ||
164 | XdeltaRsync* rsync; | ||
165 | |||
166 | if (cache_in) | ||
167 | { | ||
168 | if (! (rsync = xdp_rsync_read_index (cache_in))) | ||
169 | return NULL; | ||
170 | |||
171 | if (seg_len != rsync->seg_len || | ||
172 | (str && ! check_stream_integrity (str, rsync->file_md5, rsync->file_len))) | ||
173 | { | ||
174 | xd_generate_void_event (EC_XdInvalidRsyncCache); | ||
175 | goto bail; | ||
176 | } | ||
177 | |||
178 | return rsync; | ||
179 | } | ||
180 | else | ||
181 | { | ||
182 | if (! (rsync = xdp_rsync_index_int (str, seg_len))) | ||
183 | return NULL; | ||
184 | |||
185 | if (cache_out) | ||
186 | { | ||
187 | if (! xdp_rsync_write_index (rsync, cache_out)) | ||
188 | goto bail; | ||
189 | } | ||
190 | |||
191 | return rsync; | ||
192 | } | ||
193 | |||
194 | bail: | ||
195 | |||
196 | xdp_rsync_index_free (rsync); | ||
197 | |||
198 | return NULL; | ||
199 | } | ||
200 | |||
201 | void | ||
202 | xdp_rsync_index_free (XdeltaRsync *rsync) | ||
203 | { | ||
204 | /* ??? */ | ||
205 | } | ||
206 | |||
207 | static | ||
208 | gboolean xdp_rsync_hash (XdeltaRsync* rsync) | ||
209 | { | ||
210 | guint i, index, prime = 0; | ||
211 | gboolean already_hashed = rsync->table != NULL; | ||
212 | SerialRsyncIndexElt** table = NULL; | ||
213 | |||
214 | if (! already_hashed) | ||
215 | { | ||
216 | prime = rsync->table_size = g_spaced_primes_closest (rsync->index_len); | ||
217 | table = rsync->table = g_new0 (SerialRsyncIndexElt*, prime); | ||
218 | } | ||
219 | |||
220 | for (i = 0; i < rsync->index_len; i += 1) | ||
221 | { | ||
222 | SerialRsyncIndexElt* elt = rsync->index + i; | ||
223 | |||
224 | elt->match_offset = -1; | ||
225 | |||
226 | if (! already_hashed) | ||
227 | { | ||
228 | index = c_hash (& elt->cksum) % prime; | ||
229 | |||
230 | elt->next = table[index]; | ||
231 | table[index] = elt; | ||
232 | } | ||
233 | } | ||
234 | |||
235 | return TRUE; | ||
236 | } | ||
237 | |||
238 | static void | ||
239 | incr_by (XdeltaPos* pos, gint incr) | ||
240 | { | ||
241 | do | ||
242 | { | ||
243 | gint rem = MIN (incr, pos->mem_rem - pos->off); | ||
244 | |||
245 | pos->off += incr; | ||
246 | incr -= rem; | ||
247 | FLIP_FORWARD (*pos); | ||
248 | } | ||
249 | while (incr > 0 && pos->mem_rem != pos->page_size); | ||
250 | } | ||
251 | |||
252 | GArray* | ||
253 | xdp_rsync_request (XdeltaStream *file, | ||
254 | XdeltaRsync *rsync) | ||
255 | { | ||
256 | XdeltaPos opos, npos; | ||
257 | XdeltaChecksum cksum; | ||
258 | guint max_buffer_index = handle_length (file); | ||
259 | GArray *request = g_array_new (FALSE, FALSE, sizeof (guint)); | ||
260 | const guint8* n_pointer, *o_pointer; | ||
261 | guint thistime; | ||
262 | guint prime, index; | ||
263 | SerialRsyncIndexElt **table; | ||
264 | guint i; | ||
265 | guint matched = 0; | ||
266 | guint16 old_c, new_c; | ||
267 | |||
268 | if (max_buffer_index < rsync->seg_len) | ||
269 | return request; | ||
270 | |||
271 | max_buffer_index -= rsync->seg_len; | ||
272 | |||
273 | if (! xdp_rsync_hash (rsync)) | ||
274 | return NULL; | ||
275 | |||
276 | g_assert (rsync->seg_len < handle_pagesize (file)); | ||
277 | |||
278 | init_pos (file, &opos); | ||
279 | init_pos (file, &npos); | ||
280 | memset (&cksum, 0, sizeof (cksum)); | ||
281 | |||
282 | prime = rsync->table_size; | ||
283 | table = rsync->table; | ||
284 | |||
285 | if (!map_page (file, &opos)) | ||
286 | return NULL; | ||
287 | |||
288 | init_long_checksum (opos.mem, rsync->seg_len, &cksum); | ||
289 | |||
290 | npos.off += rsync->seg_len; | ||
291 | |||
292 | for (; XPOS (opos) < max_buffer_index; ) | ||
293 | { | ||
294 | if (!map_page (file, &opos)) | ||
295 | return FALSE; | ||
296 | |||
297 | if (!map_page (file, &npos)) | ||
298 | return FALSE; | ||
299 | |||
300 | if (matched == rsync->index_len) | ||
301 | break; | ||
302 | |||
303 | thistime = MIN (opos.mem_rem - opos.off, | ||
304 | npos.mem_rem - npos.off); | ||
305 | |||
306 | o_pointer = opos.mem + opos.off; | ||
307 | n_pointer = npos.mem + npos.off; | ||
308 | |||
309 | for (; ; o_pointer += 1, n_pointer += 1) | ||
310 | { | ||
311 | index = c_hash (&cksum) % prime; | ||
312 | |||
313 | if (table[index]) | ||
314 | { | ||
315 | gboolean md5_computed = FALSE; | ||
316 | gboolean found = FALSE; | ||
317 | guint8 md5[16]; | ||
318 | SerialRsyncIndexElt* elt; | ||
319 | |||
320 | for (elt = table[index]; elt; elt = elt->next) | ||
321 | { | ||
322 | if (elt->match_offset >= 0) | ||
323 | continue; | ||
324 | |||
325 | if (elt->cksum.high != cksum.high || | ||
326 | elt->cksum.low != cksum.low) | ||
327 | continue; | ||
328 | |||
329 | if (! md5_computed) | ||
330 | { | ||
331 | EdsioMD5Ctx ctx; | ||
332 | |||
333 | edsio_md5_init (& ctx); | ||
334 | |||
335 | if (opos.page == npos.page) | ||
336 | edsio_md5_update (& ctx, opos.mem + opos.off, rsync->seg_len); | ||
337 | else | ||
338 | { | ||
339 | edsio_md5_update (& ctx, opos.mem + opos.off, opos.mem_rem - opos.off); | ||
340 | edsio_md5_update (& ctx, npos.mem, rsync->seg_len - (opos.mem_rem - opos.off)); | ||
341 | } | ||
342 | |||
343 | edsio_md5_final (md5, & ctx); | ||
344 | |||
345 | md5_computed = TRUE; | ||
346 | } | ||
347 | |||
348 | if (memcmp (md5, elt->md5, 16) == 0) | ||
349 | { | ||
350 | matched += 1; | ||
351 | found = TRUE; | ||
352 | elt->match_offset = XPOS (opos); | ||
353 | } | ||
354 | } | ||
355 | |||
356 | if (found) | ||
357 | { | ||
358 | incr_by (&opos, rsync->seg_len); | ||
359 | incr_by (&npos, rsync->seg_len); | ||
360 | goto reenter; | ||
361 | } | ||
362 | } | ||
363 | |||
364 | if (thistime == 0) | ||
365 | goto nextpage; | ||
366 | |||
367 | thistime -= 1; | ||
368 | opos.off += 1; | ||
369 | npos.off += 1; | ||
370 | |||
371 | old_c = CHEW(*o_pointer); | ||
372 | new_c = CHEW(*n_pointer); | ||
373 | |||
374 | cksum.low -= old_c; | ||
375 | cksum.low += new_c; | ||
376 | |||
377 | cksum.high -= old_c * rsync->seg_len; | ||
378 | cksum.high += cksum.low; | ||
379 | } | ||
380 | |||
381 | nextpage: | ||
382 | |||
383 | FLIP_FORWARD (opos); | ||
384 | FLIP_FORWARD (npos); | ||
385 | |||
386 | reenter: | ||
387 | (void) 0; | ||
388 | } | ||
389 | |||
390 | for (i = 0; i < rsync->index_len; i += 1) | ||
391 | { | ||
392 | SerialRsyncIndexElt* elt = rsync->index + i; | ||
393 | |||
394 | if (elt->match_offset < 0) | ||
395 | { | ||
396 | #ifdef DEBUG_RSYNC_REQUEST | ||
397 | g_print ("request segment %d\n", i); | ||
398 | #endif | ||
399 | g_array_append_val (request, i); | ||
400 | } | ||
401 | } | ||
402 | |||
403 | return request; | ||
404 | } | ||
405 | |||
406 | gboolean | ||
407 | xdp_apply_rsync_reply (XdeltaRsync *rsync, | ||
408 | XdeltaStream *from, | ||
409 | XdeltaStream *reply, | ||
410 | XdeltaStream *out) | ||
411 | { | ||
412 | gint i; | ||
413 | guint reply_offset = 0; | ||
414 | |||
415 | for (i = 0; i < rsync->index_len; i += 1) | ||
416 | { | ||
417 | SerialRsyncIndexElt* elt = rsync->index + i; | ||
418 | |||
419 | if (elt->match_offset >= 0) | ||
420 | { | ||
421 | if (! handle_copy (from, out, elt->match_offset, rsync->seg_len)) | ||
422 | return FALSE; | ||
423 | } | ||
424 | else | ||
425 | { | ||
426 | if (! handle_copy (reply, out, reply_offset, rsync->seg_len)) | ||
427 | return FALSE; | ||
428 | |||
429 | reply_offset += rsync->seg_len; | ||
430 | } | ||
431 | } | ||
432 | |||
433 | if (! handle_copy (reply, out, reply_offset, rsync->file_len % rsync->seg_len)) | ||
434 | return FALSE; | ||
435 | |||
436 | if (! handle_close (out, 0)) | ||
437 | return FALSE; | ||
438 | |||
439 | if (! check_stream_integrity (out, rsync->file_md5, rsync->file_len)) | ||
440 | return FALSE; | ||
441 | |||
442 | return TRUE; | ||
443 | } | ||