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
init_long_checksum(const guint8 * buf,guint len,XdeltaChecksum * cksum)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*
xdp_rsync_index_int(XdeltaStream * str,guint seg_len)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*
xdp_rsync_read_index(XdeltaStream * cache_in)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
xdp_rsync_write_index(XdeltaRsync * rsync,XdeltaOutStream * cache_out)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*
xdp_rsync_index(XdeltaStream * str,guint seg_len,XdeltaStream * cache_in,XdeltaOutStream * cache_out)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
xdp_rsync_index_free(XdeltaRsync * rsync)202 xdp_rsync_index_free (XdeltaRsync *rsync)
203 {
204 /* ??? */
205 }
206
207 static
xdp_rsync_hash(XdeltaRsync * rsync)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
incr_by(XdeltaPos * pos,gint incr)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*
xdp_rsync_request(XdeltaStream * file,XdeltaRsync * rsync)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
xdp_apply_rsync_reply(XdeltaRsync * rsync,XdeltaStream * from,XdeltaStream * reply,XdeltaStream * out)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 }
444