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/xdelta.c | |
parent | 5a7c245871879325d7b05c06e0b2011203986ee8 (diff) |
import 1.1.3
Diffstat (limited to 'xdelta1/xdelta.c')
-rwxr-xr-x | xdelta1/xdelta.c | 1532 |
1 files changed, 1532 insertions, 0 deletions
diff --git a/xdelta1/xdelta.c b/xdelta1/xdelta.c new file mode 100755 index 0000000..a6d25b4 --- /dev/null +++ b/xdelta1/xdelta.c | |||
@@ -0,0 +1,1532 @@ | |||
1 | /* -*- Mode: C;-*- | ||
2 | * | ||
3 | * This file is part of XDelta - A binary delta generator. | ||
4 | * | ||
5 | * Copyright (C) 1997, 1998, 1999, 2001 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: xdelta.c 1.4.1.50.1.2 Fri, 29 Jun 2001 06:01:08 -0700 jmacd $ | ||
24 | */ | ||
25 | |||
26 | #define G_DISABLE_ASSERT | ||
27 | |||
28 | #include <string.h> | ||
29 | #include <stdlib.h> | ||
30 | #include <ctype.h> | ||
31 | |||
32 | #include "xdelta.h" | ||
33 | #include "xdeltapriv.h" | ||
34 | |||
35 | /* $Format: "const guint xdelta_major_version = $ReleaseMajorVersion$;" $ */ | ||
36 | const guint xdelta_major_version = 1; | ||
37 | /* $Format: "const guint xdelta_minor_version = $ReleaseMinorVersion$;" $ */ | ||
38 | const guint xdelta_minor_version = 1; | ||
39 | /* $Format: "const guint xdelta_micro_version = $ReleaseMicroVersion$;" $ */ | ||
40 | const guint xdelta_micro_version = 3; | ||
41 | |||
42 | /* Control functions. | ||
43 | */ | ||
44 | |||
45 | static XdeltaControl* control_version_0 (SerialVersion0Control* cont) ; | ||
46 | static void control_copy (XdeltaControl* cont, XdeltaSource* src, guint from, guint to); | ||
47 | static gboolean control_add_info (XdeltaControl* cont, XdeltaSource* src, const guint8* md5, guint len); | ||
48 | |||
49 | #ifndef XDELTA_HARDCODE_SIZE | ||
50 | int QUERY_SIZE = 0; | ||
51 | int QUERY_SIZE_POW = 0; | ||
52 | int QUERY_SIZE_MASK = 0; | ||
53 | #endif | ||
54 | |||
55 | int xdp_set_query_size_pow (int size_pow) | ||
56 | { | ||
57 | #ifdef XDELTA_HARDCODE_SIZE | ||
58 | return XDP_QUERY_HARDCODED; | ||
59 | #else | ||
60 | |||
61 | int x = 1; | ||
62 | int size_log = 0; | ||
63 | |||
64 | for (; x != 0; x <<= 1, size_log += 1) | ||
65 | { | ||
66 | if (x == size_pow) | ||
67 | goto good; | ||
68 | } | ||
69 | |||
70 | return XDP_QUERY_POW2; | ||
71 | |||
72 | good: | ||
73 | |||
74 | QUERY_SIZE = size_log; | ||
75 | QUERY_SIZE_POW = size_pow; | ||
76 | QUERY_SIZE_MASK = size_pow-1; | ||
77 | |||
78 | return 0; | ||
79 | |||
80 | #endif | ||
81 | } | ||
82 | |||
83 | int | ||
84 | xdp_blocksize () | ||
85 | { | ||
86 | if (QUERY_SIZE == 0) | ||
87 | { | ||
88 | xdp_set_query_size_pow (1<<QUERY_SIZE_DEFAULT); | ||
89 | } | ||
90 | |||
91 | return QUERY_SIZE_POW; | ||
92 | } | ||
93 | |||
94 | const char* | ||
95 | xdp_errno (int errval) | ||
96 | { | ||
97 | switch (errval) | ||
98 | { | ||
99 | case XDP_QUERY_HARDCODED: | ||
100 | return "query size hardcoded"; | ||
101 | case XDP_QUERY_POW2: | ||
102 | return "query size must be a power of 2"; | ||
103 | } | ||
104 | |||
105 | return g_strerror (errval); | ||
106 | } | ||
107 | |||
108 | const guint16 single_hash[256] = | ||
109 | { | ||
110 | /* Random numbers generated using SLIB's pseudo-random number | ||
111 | * generator. */ | ||
112 | 0xbcd1, 0xbb65, 0x42c2, 0xdffe, 0x9666, 0x431b, 0x8504, 0xeb46, | ||
113 | 0x6379, 0xd460, 0xcf14, 0x53cf, 0xdb51, 0xdb08, 0x12c8, 0xf602, | ||
114 | 0xe766, 0x2394, 0x250d, 0xdcbb, 0xa678, 0x02af, 0xa5c6, 0x7ea6, | ||
115 | 0xb645, 0xcb4d, 0xc44b, 0xe5dc, 0x9fe6, 0x5b5c, 0x35f5, 0x701a, | ||
116 | 0x220f, 0x6c38, 0x1a56, 0x4ca3, 0xffc6, 0xb152, 0x8d61, 0x7a58, | ||
117 | 0x9025, 0x8b3d, 0xbf0f, 0x95a3, 0xe5f4, 0xc127, 0x3bed, 0x320b, | ||
118 | 0xb7f3, 0x6054, 0x333c, 0xd383, 0x8154, 0x5242, 0x4e0d, 0x0a94, | ||
119 | 0x7028, 0x8689, 0x3a22, 0x0980, 0x1847, 0xb0f1, 0x9b5c, 0x4176, | ||
120 | 0xb858, 0xd542, 0x1f6c, 0x2497, 0x6a5a, 0x9fa9, 0x8c5a, 0x7743, | ||
121 | 0xa8a9, 0x9a02, 0x4918, 0x438c, 0xc388, 0x9e2b, 0x4cad, 0x01b6, | ||
122 | 0xab19, 0xf777, 0x365f, 0x1eb2, 0x091e, 0x7bf8, 0x7a8e, 0x5227, | ||
123 | 0xeab1, 0x2074, 0x4523, 0xe781, 0x01a3, 0x163d, 0x3b2e, 0x287d, | ||
124 | 0x5e7f, 0xa063, 0xb134, 0x8fae, 0x5e8e, 0xb7b7, 0x4548, 0x1f5a, | ||
125 | 0xfa56, 0x7a24, 0x900f, 0x42dc, 0xcc69, 0x02a0, 0x0b22, 0xdb31, | ||
126 | 0x71fe, 0x0c7d, 0x1732, 0x1159, 0xcb09, 0xe1d2, 0x1351, 0x52e9, | ||
127 | 0xf536, 0x5a4f, 0xc316, 0x6bf9, 0x8994, 0xb774, 0x5f3e, 0xf6d6, | ||
128 | 0x3a61, 0xf82c, 0xcc22, 0x9d06, 0x299c, 0x09e5, 0x1eec, 0x514f, | ||
129 | 0x8d53, 0xa650, 0x5c6e, 0xc577, 0x7958, 0x71ac, 0x8916, 0x9b4f, | ||
130 | 0x2c09, 0x5211, 0xf6d8, 0xcaaa, 0xf7ef, 0x287f, 0x7a94, 0xab49, | ||
131 | 0xfa2c, 0x7222, 0xe457, 0xd71a, 0x00c3, 0x1a76, 0xe98c, 0xc037, | ||
132 | 0x8208, 0x5c2d, 0xdfda, 0xe5f5, 0x0b45, 0x15ce, 0x8a7e, 0xfcad, | ||
133 | 0xaa2d, 0x4b5c, 0xd42e, 0xb251, 0x907e, 0x9a47, 0xc9a6, 0xd93f, | ||
134 | 0x085e, 0x35ce, 0xa153, 0x7e7b, 0x9f0b, 0x25aa, 0x5d9f, 0xc04d, | ||
135 | 0x8a0e, 0x2875, 0x4a1c, 0x295f, 0x1393, 0xf760, 0x9178, 0x0f5b, | ||
136 | 0xfa7d, 0x83b4, 0x2082, 0x721d, 0x6462, 0x0368, 0x67e2, 0x8624, | ||
137 | 0x194d, 0x22f6, 0x78fb, 0x6791, 0xb238, 0xb332, 0x7276, 0xf272, | ||
138 | 0x47ec, 0x4504, 0xa961, 0x9fc8, 0x3fdc, 0xb413, 0x007a, 0x0806, | ||
139 | 0x7458, 0x95c6, 0xccaa, 0x18d6, 0xe2ae, 0x1b06, 0xf3f6, 0x5050, | ||
140 | 0xc8e8, 0xf4ac, 0xc04c, 0xf41c, 0x992f, 0xae44, 0x5f1b, 0x1113, | ||
141 | 0x1738, 0xd9a8, 0x19ea, 0x2d33, 0x9698, 0x2fe9, 0x323f, 0xcde2, | ||
142 | 0x6d71, 0xe37d, 0xb697, 0x2c4f, 0x4373, 0x9102, 0x075d, 0x8e25, | ||
143 | 0x1672, 0xec28, 0x6acb, 0x86cc, 0x186e, 0x9414, 0xd674, 0xd1a5 | ||
144 | }; | ||
145 | |||
146 | /* Compute the hash of length len for buf, a single byte array of | ||
147 | * values, by first indexing the random array. | ||
148 | */ | ||
149 | |||
150 | static void | ||
151 | init_query_checksum (const guint8 *buf, XdeltaChecksum *cksum) | ||
152 | { | ||
153 | gint i = QUERY_SIZE_POW; | ||
154 | guint16 low = 0; | ||
155 | guint16 high = 0; | ||
156 | |||
157 | for (; i != 0; i -= 1) | ||
158 | { | ||
159 | low += CHEW(*buf++); | ||
160 | high += low; | ||
161 | } | ||
162 | |||
163 | cksum->low = low; | ||
164 | cksum->high = high; | ||
165 | } | ||
166 | |||
167 | /* Generate checksums | ||
168 | */ | ||
169 | |||
170 | static gboolean | ||
171 | generate_checksums (XdeltaStream *stream, | ||
172 | XdeltaSource *source) | ||
173 | { | ||
174 | gint total_checksums = handle_length (stream) / QUERY_SIZE_POW; | ||
175 | gint checksum_index = 0; | ||
176 | XdeltaChecksum cksum; | ||
177 | XdeltaChecksum *result; | ||
178 | const guint8* segment = NULL, *segment_pointer; | ||
179 | gint segment_len, orig_segment_len; | ||
180 | guint segment_page = 0; | ||
181 | guint pages; | ||
182 | |||
183 | #ifdef DEBUG_CKSUM | ||
184 | g_print ("Total base checksums: %d\n", total_checksums); | ||
185 | #endif | ||
186 | |||
187 | source->ck_count = total_checksums; | ||
188 | |||
189 | if (total_checksums == 0) | ||
190 | return TRUE; | ||
191 | |||
192 | /* This is the in-core FROM checksum table. */ | ||
193 | result = g_new (XdeltaChecksum, total_checksums); | ||
194 | source->cksums = result; | ||
195 | |||
196 | for (pages = handle_pages (stream); segment_page <= pages; segment_page += 1) | ||
197 | { | ||
198 | segment_len = handle_map_page (stream, segment_page, &segment); | ||
199 | |||
200 | if (segment_len < 0) | ||
201 | return FALSE; | ||
202 | |||
203 | orig_segment_len = segment_len; | ||
204 | |||
205 | segment_len >>= QUERY_SIZE; | ||
206 | |||
207 | for (segment_pointer = segment; | ||
208 | segment_len != 0; | ||
209 | segment_len -= 1, segment_pointer += QUERY_SIZE_POW) | ||
210 | { | ||
211 | /* note: cheating at the boundaries */ | ||
212 | init_query_checksum (segment_pointer, &cksum); | ||
213 | |||
214 | #ifdef DEBUG_CKSUM | ||
215 | g_print ("New cksum %04x %04x indices %d-%d\n", | ||
216 | cksum.low, cksum.high, | ||
217 | checksum_index * QUERY_SIZE_POW, (checksum_index * QUERY_SIZE_POW) + QUERY_SIZE_POW - 1); | ||
218 | #endif | ||
219 | |||
220 | result[checksum_index++] = cksum; | ||
221 | } | ||
222 | |||
223 | if (! handle_unmap_page (stream, segment_page, &segment)) | ||
224 | return FALSE; | ||
225 | } | ||
226 | |||
227 | return TRUE; | ||
228 | } | ||
229 | |||
230 | /* $Format: "#define XDELTA_REQUIRED_VERSION \"$ReleaseMajorVersion$.$ReleaseMinorVersion$.\"" $ */ | ||
231 | #define XDELTA_REQUIRED_VERSION "1.1." | ||
232 | |||
233 | XdeltaGenerator* | ||
234 | __xdp_generator_new (const char* version) | ||
235 | { | ||
236 | XdeltaGenerator* xg; | ||
237 | |||
238 | if (strncmp (version, XDELTA_REQUIRED_VERSION, strlen (XDELTA_REQUIRED_VERSION)) != 0) | ||
239 | g_error ("XDelta library version mismatched, compiled for %s, running %s\n", version, XDELTA_VERSION); | ||
240 | |||
241 | xg = g_new0 (XdeltaGenerator, 1); | ||
242 | |||
243 | xg->sources = g_ptr_array_new (); | ||
244 | |||
245 | xg->data_source = g_new0 (XdeltaSource, 1); | ||
246 | xg->data_source->name = "(patch data)"; | ||
247 | |||
248 | g_ptr_array_add (xg->sources, xg->data_source); | ||
249 | |||
250 | return xg; | ||
251 | } | ||
252 | |||
253 | void | ||
254 | xdp_generator_free (XdeltaGenerator *gen) | ||
255 | { | ||
256 | int i; | ||
257 | |||
258 | for (i = 0; i < gen->sources->len; i += 1) | ||
259 | xdp_source_free (gen->sources->pdata[i]); | ||
260 | |||
261 | g_ptr_array_free (gen->sources, TRUE); | ||
262 | g_free ((void*) gen->table); | ||
263 | g_free (gen); | ||
264 | } | ||
265 | |||
266 | void | ||
267 | init_pos (XdeltaStream* str, XdeltaPos* pos) | ||
268 | { | ||
269 | g_assert (str); | ||
270 | |||
271 | memset (pos, 0, sizeof (*pos)); | ||
272 | |||
273 | pos->page_size = handle_pagesize (str); | ||
274 | } | ||
275 | |||
276 | gboolean | ||
277 | check_stream_integrity (XdeltaStream* str, const guint8* md5, guint len) | ||
278 | { | ||
279 | const guint8* act_md5; | ||
280 | |||
281 | if (len != handle_length (str)) | ||
282 | { | ||
283 | xd_generate_handleintint_event (EC_XdStreamLengthFailed, str, len, handle_length (str)); | ||
284 | return FALSE; | ||
285 | } | ||
286 | |||
287 | act_md5 = handle_checksum_md5 (str); | ||
288 | |||
289 | if (! act_md5) | ||
290 | return FALSE; | ||
291 | |||
292 | if (memcmp (md5, act_md5, 16) != 0) | ||
293 | { | ||
294 | char exp[33], rec[33]; | ||
295 | |||
296 | edsio_md5_to_string (md5, exp); | ||
297 | edsio_md5_to_string (act_md5, rec); | ||
298 | |||
299 | xd_generate_handlestringstring_event (EC_XdStreamChecksumFailed, str, exp, rec); | ||
300 | g_free ((void*) act_md5); | ||
301 | return FALSE; | ||
302 | } | ||
303 | |||
304 | g_free ((void*) act_md5); | ||
305 | |||
306 | return TRUE; | ||
307 | } | ||
308 | |||
309 | static gboolean | ||
310 | xdp_source_index_read (XdeltaSource *xs, | ||
311 | XdeltaStream *index_in) | ||
312 | { | ||
313 | SerialSource *ss = handle_source (index_in); | ||
314 | XdeltaIndex *index; | ||
315 | |||
316 | if (! ss) | ||
317 | return FALSE; | ||
318 | |||
319 | if (! unserialize_xdeltaindex (ss, &index)) | ||
320 | return FALSE; | ||
321 | |||
322 | if (! check_stream_integrity (xs->source_in, index->file_md5, index->file_len)) | ||
323 | return FALSE; | ||
324 | |||
325 | xs->ck_count = index->index_len; | ||
326 | xs->cksums = index->index; | ||
327 | |||
328 | /* @@@ how to free this? */ | ||
329 | |||
330 | return TRUE; | ||
331 | } | ||
332 | |||
333 | static gboolean | ||
334 | xdp_source_index_internal (XdeltaSource *init, | ||
335 | XdeltaStream *source_in, | ||
336 | XdeltaOutStream *index_out) | ||
337 | { | ||
338 | if (! generate_checksums (source_in, init)) | ||
339 | return FALSE; | ||
340 | |||
341 | if (index_out) | ||
342 | { | ||
343 | const guint8* source_in_md5; | ||
344 | SerialSink* sink = handle_sink (index_out, NULL, NULL, NULL, NULL); | ||
345 | |||
346 | if (! sink) | ||
347 | return FALSE; | ||
348 | |||
349 | if (! (source_in_md5 = handle_checksum_md5 (source_in))) | ||
350 | return FALSE; | ||
351 | |||
352 | if (! serialize_xdeltaindex (sink, | ||
353 | handle_length (source_in), | ||
354 | source_in_md5, | ||
355 | init->ck_count, | ||
356 | init->cksums)) | ||
357 | { | ||
358 | g_free ((void*) source_in_md5); | ||
359 | return FALSE; | ||
360 | } | ||
361 | |||
362 | g_free ((void*) source_in_md5); | ||
363 | |||
364 | if (! handle_close (index_out, 0)) | ||
365 | return FALSE; | ||
366 | } | ||
367 | |||
368 | return TRUE; | ||
369 | } | ||
370 | |||
371 | gboolean | ||
372 | xdp_source_index (XdeltaStream *source_in, | ||
373 | XdeltaOutStream *index_out) | ||
374 | { | ||
375 | XdeltaSource* xs = xdp_source_new ("(ignored)", source_in, NULL, index_out); | ||
376 | |||
377 | if (xs) | ||
378 | { | ||
379 | xdp_source_free (xs); | ||
380 | return TRUE; | ||
381 | } | ||
382 | |||
383 | return FALSE; | ||
384 | } | ||
385 | |||
386 | XdeltaSource* | ||
387 | xdp_source_new (const char *name, | ||
388 | XdeltaStream *source_in, | ||
389 | XdeltaStream *index_in, | ||
390 | XdeltaOutStream *index_out) | ||
391 | { | ||
392 | XdeltaSource* xs = g_new0 (XdeltaSource, 1); | ||
393 | |||
394 | xs->source_in = source_in; | ||
395 | xs->name = name; | ||
396 | |||
397 | g_return_val_if_fail (source_in, NULL); | ||
398 | g_return_val_if_fail (index_in ? ! index_out : TRUE, NULL); | ||
399 | |||
400 | xs->index_in = index_in; | ||
401 | xs->index_out = index_out; | ||
402 | xs->source_pos.page_size = handle_pagesize (source_in); | ||
403 | |||
404 | return xs; | ||
405 | } | ||
406 | |||
407 | static gboolean | ||
408 | xdp_source_check_index (XdeltaSource *xs) | ||
409 | { | ||
410 | if (xs->source_index == 0) | ||
411 | return TRUE; | ||
412 | |||
413 | if (! xs->index_in) | ||
414 | return xdp_source_index_internal (xs, xs->source_in, xs->index_out); | ||
415 | else | ||
416 | return xdp_source_index_read (xs, xs->index_in); | ||
417 | } | ||
418 | |||
419 | void | ||
420 | xdp_source_free (XdeltaSource* xs) | ||
421 | { | ||
422 | if (xs) | ||
423 | { | ||
424 | /* if (xs->ckarray) @@@ this is troublesome now | ||
425 | g_free (xs->ckarray);*/ | ||
426 | |||
427 | g_free (xs); | ||
428 | } | ||
429 | } | ||
430 | |||
431 | void | ||
432 | xdp_source_add (XdeltaGenerator *gen, | ||
433 | XdeltaSource *src) | ||
434 | { | ||
435 | if (gen->table) | ||
436 | { | ||
437 | g_free ((gpointer)gen->table); | ||
438 | gen->table = NULL; | ||
439 | } | ||
440 | |||
441 | g_ptr_array_add (gen->sources, src); | ||
442 | } | ||
443 | |||
444 | guint | ||
445 | c_hash (const XdeltaChecksum* c) | ||
446 | { | ||
447 | const guint high = c->high; | ||
448 | const guint low = c->low; | ||
449 | const guint it = (high >> 2) + (low << 3) + (high << 16); | ||
450 | |||
451 | return (it ^ high ^ low); | ||
452 | } | ||
453 | |||
454 | static gboolean | ||
455 | region_insert (XdeltaGenerator* gen, const XdeltaPos *xpos, guint len) | ||
456 | { | ||
457 | /* This is a little bit cryptic: the xpos.mem + EXPR expression | ||
458 | * computes the offset into the current page, which is guaranteed | ||
459 | * to be correct since map_page has not occured yet. */ | ||
460 | const guint8* buf = xpos->mem + (gen->to_output_pos % xpos->page_size); | ||
461 | |||
462 | if (len == 0) | ||
463 | return TRUE; | ||
464 | |||
465 | #ifdef DEBUG_INST | ||
466 | g_print ("insert %d at %d\n", len, gen->to_output_pos); | ||
467 | #endif | ||
468 | |||
469 | if (! handle_write (gen->data_out, buf, len)) | ||
470 | return FALSE; | ||
471 | |||
472 | control_copy (gen->control, gen->data_source, gen->data_output_pos, gen->data_output_pos + len); | ||
473 | |||
474 | gen->to_output_pos += len; | ||
475 | gen->data_output_pos += len; | ||
476 | |||
477 | return TRUE; | ||
478 | } | ||
479 | |||
480 | static gboolean | ||
481 | region_copy (XdeltaGenerator* gen, XdeltaSource* src, guint from, guint to) | ||
482 | { | ||
483 | #ifdef DEBUG_INST | ||
484 | g_print ("copy %d - %d (%d) to %d\n", from, to, to-from, gen->to_output_pos); | ||
485 | #endif | ||
486 | |||
487 | control_copy (gen->control, src, from, to); | ||
488 | |||
489 | gen->to_output_pos += (to-from); | ||
490 | |||
491 | return TRUE; | ||
492 | } | ||
493 | |||
494 | gboolean | ||
495 | unmap_page (XdeltaStream* stream, XdeltaPos* pos) | ||
496 | { | ||
497 | if (! pos->mem) | ||
498 | return TRUE; | ||
499 | |||
500 | if (handle_unmap_page (stream, | ||
501 | pos->mem_page, | ||
502 | &pos->mem)) | ||
503 | { | ||
504 | pos->mem = NULL; | ||
505 | return TRUE; | ||
506 | } | ||
507 | |||
508 | return FALSE; | ||
509 | } | ||
510 | |||
511 | gboolean | ||
512 | map_page (XdeltaStream* stream, XdeltaPos* pos) | ||
513 | { | ||
514 | gint on_page; | ||
515 | |||
516 | if (pos->mem && pos->mem_page == pos->page) | ||
517 | return TRUE; | ||
518 | |||
519 | if (pos->mem) | ||
520 | { | ||
521 | if (! handle_unmap_page (stream, | ||
522 | pos->mem_page, | ||
523 | &pos->mem)) | ||
524 | return FALSE; | ||
525 | |||
526 | pos->mem = NULL; | ||
527 | } | ||
528 | |||
529 | pos->mem_page = pos->page; | ||
530 | |||
531 | on_page = handle_map_page (stream, | ||
532 | pos->mem_page, | ||
533 | &pos->mem); | ||
534 | |||
535 | if (on_page >= 0) | ||
536 | { | ||
537 | pos->mem_rem = on_page; | ||
538 | return TRUE; | ||
539 | } | ||
540 | |||
541 | return FALSE; | ||
542 | } | ||
543 | |||
544 | static gboolean | ||
545 | try_match (XdeltaGenerator *gen, | ||
546 | XdeltaStream *in, | ||
547 | XdeltaPos *xpos_ptr, | ||
548 | XdeltaSource *src, | ||
549 | guint src_offset, | ||
550 | gboolean *found) | ||
551 | { | ||
552 | XdeltaPos xpos = *xpos_ptr; | ||
553 | XdeltaPos ypos = src->source_pos; | ||
554 | gint rem, remsave; | ||
555 | gint match_forward = 0; | ||
556 | gint match_backward = 0; | ||
557 | gint match_forward_max; | ||
558 | gint match_backward_max; | ||
559 | guint to_offset = XPOS (xpos); | ||
560 | gboolean one_insert = FALSE; | ||
561 | |||
562 | *found = FALSE; | ||
563 | |||
564 | ypos.page = src_offset / ypos.page_size; | ||
565 | ypos.off = src_offset % ypos.page_size; | ||
566 | |||
567 | match_forward_max = MIN (handle_length (in) - to_offset, | ||
568 | handle_length (src->source_in) - src_offset); | ||
569 | match_backward_max = MIN (src_offset, to_offset - gen->to_output_pos); | ||
570 | |||
571 | /* Don't allow backward paging */ | ||
572 | match_backward_max = MIN (match_backward_max, xpos.off); | ||
573 | |||
574 | /* We're testing against the negative below. */ | ||
575 | match_backward_max = - match_backward_max; | ||
576 | |||
577 | for (; match_backward > match_backward_max; ) | ||
578 | { | ||
579 | g_assert (xpos.off != 0); | ||
580 | |||
581 | if (ypos.off == 0) | ||
582 | { | ||
583 | ypos.off = ypos.page_size; | ||
584 | ypos.page -= 1; | ||
585 | } | ||
586 | |||
587 | if (! map_page (src->source_in, &ypos)) | ||
588 | goto bail; | ||
589 | |||
590 | rem = MIN (xpos.off, ypos.off); | ||
591 | rem = MIN (match_backward - match_backward_max, rem); | ||
592 | |||
593 | for (; rem > 0; rem -= 1, match_backward -= 1) | ||
594 | { | ||
595 | if (xpos.mem[xpos.off-1] != ypos.mem[ypos.off-1]) | ||
596 | goto doneback; | ||
597 | |||
598 | xpos.off -= 1; | ||
599 | ypos.off -= 1; | ||
600 | } | ||
601 | } | ||
602 | |||
603 | doneback: | ||
604 | |||
605 | xpos.page = to_offset / xpos.page_size; | ||
606 | xpos.off = to_offset % xpos.page_size; | ||
607 | |||
608 | ypos.page = src_offset / ypos.page_size; | ||
609 | ypos.off = src_offset % ypos.page_size; | ||
610 | |||
611 | for (; match_forward < match_forward_max; ) | ||
612 | { | ||
613 | if (! map_page (src->source_in, &ypos)) | ||
614 | goto bail; | ||
615 | |||
616 | /* Fortunately, if this map happens it means that the match must | ||
617 | * be long enough to succeed below, therefore it is safe to write | ||
618 | * the insert out now. */ | ||
619 | if (! one_insert && xpos.page != xpos.mem_page) | ||
620 | { | ||
621 | one_insert = TRUE; | ||
622 | |||
623 | if (! region_insert (gen, &xpos, (to_offset + match_backward) - gen->to_output_pos)) | ||
624 | goto bail; | ||
625 | } | ||
626 | |||
627 | if (! map_page (in, &xpos)) | ||
628 | goto bail; | ||
629 | |||
630 | rem = MIN (xpos.mem_rem - xpos.off, ypos.mem_rem - ypos.off); | ||
631 | rem = MIN (match_forward_max - match_forward, rem); | ||
632 | |||
633 | /* Do a int-wise comparison if the regions are aligned. */ | ||
634 | if (rem > (4*sizeof(int)) && (xpos.off % sizeof (int)) == (ypos.off % sizeof(int))) | ||
635 | { | ||
636 | gint is; | ||
637 | const int *xi, *yi; | ||
638 | |||
639 | for (; xpos.off % sizeof(int); rem -= 1, match_forward += 1) | ||
640 | { | ||
641 | if (xpos.mem[xpos.off] != ypos.mem[ypos.off]) | ||
642 | goto done; | ||
643 | |||
644 | xpos.off += 1; | ||
645 | ypos.off += 1; | ||
646 | } | ||
647 | |||
648 | remsave = rem; | ||
649 | rem /= sizeof(int); | ||
650 | |||
651 | xi = (const int*) (xpos.mem + xpos.off); | ||
652 | yi = (const int*) (ypos.mem + ypos.off); | ||
653 | |||
654 | is = rem; | ||
655 | |||
656 | for (; rem > 0 && *xi == *yi; ) | ||
657 | { | ||
658 | rem -= 1; | ||
659 | xi += 1; | ||
660 | yi += 1; | ||
661 | } | ||
662 | |||
663 | is -= rem; | ||
664 | |||
665 | match_forward += is * sizeof(int); | ||
666 | xpos.off += is * sizeof(int); | ||
667 | ypos.off += is * sizeof(int); | ||
668 | |||
669 | rem = (rem * sizeof(int)) + (remsave % sizeof(int)); | ||
670 | } | ||
671 | |||
672 | for (; rem > 0; rem -= 1, match_forward += 1) | ||
673 | { | ||
674 | if (xpos.mem[xpos.off] != ypos.mem[ypos.off]) | ||
675 | goto done; | ||
676 | |||
677 | xpos.off += 1; | ||
678 | ypos.off += 1; | ||
679 | } | ||
680 | |||
681 | FLIP_FORWARD (xpos); | ||
682 | FLIP_FORWARD (ypos); | ||
683 | } | ||
684 | |||
685 | done: | ||
686 | |||
687 | if (match_forward - match_backward >= QUERY_SIZE_POW) | ||
688 | { | ||
689 | *found = TRUE; | ||
690 | |||
691 | if (! one_insert) | ||
692 | { | ||
693 | if (! region_insert (gen, &xpos, (to_offset + match_backward) - gen->to_output_pos)) | ||
694 | goto bail; | ||
695 | } | ||
696 | |||
697 | if (! region_copy (gen, src, src_offset + match_backward, src_offset + match_forward)) | ||
698 | goto bail; | ||
699 | } | ||
700 | else | ||
701 | { | ||
702 | g_assert (! one_insert); | ||
703 | } | ||
704 | |||
705 | *xpos_ptr = xpos; | ||
706 | src->source_pos = ypos; | ||
707 | return TRUE; | ||
708 | |||
709 | bail: | ||
710 | *xpos_ptr = xpos; | ||
711 | src->source_pos = ypos; | ||
712 | return FALSE; | ||
713 | } | ||
714 | |||
715 | static gboolean | ||
716 | compute_copies (XdeltaGenerator* gen, XdeltaStream* stream) | ||
717 | { | ||
718 | XdeltaChecksum cksum; | ||
719 | const XdeltaChecksum *source_cksum; | ||
720 | const guint8 *segment_pointer; | ||
721 | guint source_offset, segment_index, index, prime = gen->table_size; | ||
722 | guint source_index; | ||
723 | const guint32* table = gen->table; | ||
724 | guint16 old_c, new_c; | ||
725 | guint save_page, save_off; | ||
726 | #ifdef DEBUG_MATCH_PRINT | ||
727 | guint i; | ||
728 | #endif | ||
729 | XdeltaPos xpos; | ||
730 | gboolean found; | ||
731 | gboolean ret = TRUE; | ||
732 | |||
733 | if (handle_length (stream) < QUERY_SIZE_POW) | ||
734 | return TRUE; | ||
735 | |||
736 | init_pos (stream, &xpos); | ||
737 | |||
738 | while (XPOS (xpos) <= (handle_length (stream) - QUERY_SIZE_POW)) | ||
739 | { | ||
740 | if (!map_page (stream, &xpos)) | ||
741 | return FALSE; | ||
742 | |||
743 | g_assert (xpos.mem_rem > xpos.off); | ||
744 | |||
745 | segment_index = (xpos.mem_rem - xpos.off); | ||
746 | |||
747 | if (segment_index < QUERY_SIZE_POW) | ||
748 | goto nextpage; | ||
749 | |||
750 | segment_index -= QUERY_SIZE_POW; | ||
751 | |||
752 | segment_pointer = xpos.mem + xpos.off; | ||
753 | |||
754 | init_query_checksum (segment_pointer, &cksum); | ||
755 | |||
756 | for (; ; segment_pointer += 1) | ||
757 | { | ||
758 | #ifdef DEBUG_CKSUM_UPDATE | ||
759 | XdeltaChecksum cktest; | ||
760 | |||
761 | init_query_checksum (segment_pointer, &cktest); | ||
762 | |||
763 | if (cktest.high != cksum.high || cktest.low != cktest.low) | ||
764 | abort (); | ||
765 | #endif | ||
766 | |||
767 | index = c_hash (&cksum) % prime; | ||
768 | |||
769 | #ifdef DEBUG_MATCH_PRINT | ||
770 | g_print ("%d: searching for match \"", XPOS(xpos)); | ||
771 | for (i = 0; i < QUERY_SIZE_POW; i += 1) | ||
772 | { | ||
773 | if (isprint (segment_pointer[i])) | ||
774 | g_print ("%c", segment_pointer[i]); | ||
775 | else | ||
776 | g_print ("\\0%o", segment_pointer[i]); | ||
777 | } | ||
778 | g_print ("\"... %s\n", table[index] ? "found" : "notfound"); | ||
779 | #endif | ||
780 | |||
781 | if (table[index]) | ||
782 | { | ||
783 | source_index = (table[index] & QUERY_SIZE_MASK) - 1; | ||
784 | source_offset = (table[index] >> QUERY_SIZE); | ||
785 | |||
786 | source_cksum = ((XdeltaSource*)gen->sources->pdata[source_index])->cksums + source_offset; | ||
787 | |||
788 | if (cksum.high == source_cksum->high && | ||
789 | cksum.low == source_cksum->low) | ||
790 | { | ||
791 | save_page = xpos.page; | ||
792 | save_off = xpos.off; | ||
793 | |||
794 | if (! try_match (gen, | ||
795 | stream, | ||
796 | &xpos, | ||
797 | gen->sources->pdata[source_index], | ||
798 | source_offset << QUERY_SIZE, | ||
799 | &found)) | ||
800 | { | ||
801 | ret = FALSE; | ||
802 | goto bail; | ||
803 | } | ||
804 | |||
805 | if (found) | ||
806 | { | ||
807 | g_assert (xpos.page*xpos.page_size+xpos.off == gen->to_output_pos); | ||
808 | |||
809 | goto reenter; | ||
810 | } | ||
811 | else | ||
812 | { | ||
813 | xpos.page = save_page; | ||
814 | xpos.off = save_off; | ||
815 | } | ||
816 | } | ||
817 | } | ||
818 | |||
819 | if (segment_index == 0) | ||
820 | goto nextpage; | ||
821 | |||
822 | segment_index -= 1; | ||
823 | xpos.off += 1; | ||
824 | |||
825 | old_c = CHEW(segment_pointer[0]); | ||
826 | new_c = CHEW(segment_pointer[QUERY_SIZE_POW]); | ||
827 | |||
828 | cksum.low -= old_c; | ||
829 | cksum.low += new_c; | ||
830 | |||
831 | cksum.high -= old_c << QUERY_SIZE; | ||
832 | cksum.high += cksum.low; | ||
833 | } | ||
834 | |||
835 | nextpage: | ||
836 | |||
837 | if (xpos.mem_rem < xpos.page_size) | ||
838 | break; | ||
839 | |||
840 | xpos.page += 1; | ||
841 | xpos.off = 0; | ||
842 | |||
843 | if (xpos.page != xpos.mem_page) | ||
844 | { | ||
845 | if (! region_insert (gen, &xpos, XPOS (xpos) - gen->to_output_pos)) | ||
846 | return FALSE; | ||
847 | } | ||
848 | |||
849 | reenter: | ||
850 | (void) 0; | ||
851 | } | ||
852 | |||
853 | xpos.off = gen->to_output_pos % handle_pagesize (stream); | ||
854 | |||
855 | while (gen->to_output_pos < handle_length (stream)) | ||
856 | { | ||
857 | if (! map_page (stream, &xpos)) | ||
858 | return FALSE; | ||
859 | |||
860 | if (! region_insert (gen, &xpos, xpos.mem_rem - xpos.off)) | ||
861 | ret = FALSE; | ||
862 | |||
863 | xpos.off = 0; | ||
864 | xpos.page += 1; | ||
865 | } | ||
866 | |||
867 | bail: | ||
868 | |||
869 | if (! unmap_page (stream, &xpos)) | ||
870 | return FALSE; | ||
871 | |||
872 | return ret; | ||
873 | } | ||
874 | |||
875 | static gboolean | ||
876 | just_output (XdeltaGenerator *gen, | ||
877 | XdeltaStream *in) | ||
878 | { | ||
879 | XdeltaPos pos; | ||
880 | |||
881 | init_pos (in, &pos); | ||
882 | |||
883 | while (gen->to_output_pos < handle_length (in)) | ||
884 | { | ||
885 | if (! map_page (in, &pos)) | ||
886 | return FALSE; | ||
887 | |||
888 | if (! region_insert (gen, &pos, pos.mem_rem - pos.off)) | ||
889 | return FALSE; | ||
890 | |||
891 | pos.off = 0; | ||
892 | pos.page += 1; | ||
893 | } | ||
894 | |||
895 | if (! unmap_page (in, &pos)) | ||
896 | return FALSE; | ||
897 | |||
898 | return TRUE; | ||
899 | } | ||
900 | |||
901 | /* Clobbering decision (see below): | ||
902 | * | ||
903 | * Algorithm A: Clobber it always (its fast!). The problem | ||
904 | * is that this prefers matches at the front of | ||
905 | * the file and leads to poor matches at the back | ||
906 | * of the file (assuming I insert going backwards). | ||
907 | * | ||
908 | * Algorithm B: Keep a table of how many times there has | ||
909 | * been a clobber at each index i, C[i]. | ||
910 | * With probability 1/(C[i]+1), replace the | ||
911 | * previous entry. This gives a uniform | ||
912 | * probability of each entry surviving. | ||
913 | * The problem (supposed) with this | ||
914 | * algorithm is that the probabilities | ||
915 | * should not be uniform (though uniform is | ||
916 | * better than A) because there are more | ||
917 | * chances to match a segment at the end of | ||
918 | * the file than at the beginning. | ||
919 | * | ||
920 | * Algorithm C: Give a linear weight to each match | ||
921 | * according to it's position in the file | ||
922 | * -- number the segments from N down to 1 | ||
923 | * starting at the beginning. Same as the | ||
924 | * above but with a different weight. The | ||
925 | * weight for segment i, match at checksum | ||
926 | * offset k, follows. The total number of | ||
927 | * checksums in the segment is C_i, | ||
928 | * therefore the total checksum count is | ||
929 | * C = sum_i (C_i). | ||
930 | * Now the interior weight is the (C_i-k) | ||
931 | * (the linear assumption) and the total | ||
932 | * interior weight is sum_{j=1}^{N}{j}=(N)(N+1)/2 | ||
933 | * so the kth segment has interior weight | ||
934 | * | ||
935 | * [2 (C_i - k)] / [(C_i) (C_i + 1)] | ||
936 | * | ||
937 | * add in the exterior weight (after | ||
938 | * cancelling a C_i): | ||
939 | * | ||
940 | * w(i,k) = [2 (C_i - k)] / [(C_i + 1) (C)] | ||
941 | * | ||
942 | * Now, as above, we will compute whether to | ||
943 | * keep or replace the current value at the j-th | ||
944 | * decision. Let R_j be the running sum of | ||
945 | * weights considered so far. R_0 = 0. At the | ||
946 | * j-th decision, | ||
947 | * | ||
948 | * P_ikj(use new value) = w(i,k)/R_{j+1} | ||
949 | * R_{j+1} = R_j + w(i,k) | ||
950 | */ | ||
951 | |||
952 | static gboolean | ||
953 | xdp_generate_delta_int (XdeltaGenerator *gen, | ||
954 | XdeltaStream *in, | ||
955 | XdeltaOutStream *control_out, | ||
956 | XdeltaOutStream *data_out) | ||
957 | { | ||
958 | gint i, j, total_from_ck_count = 0, prime = 0, index = 0; | ||
959 | gint total_from_len = 0; | ||
960 | guint32* table = NULL; | ||
961 | |||
962 | if (QUERY_SIZE == 0) | ||
963 | { | ||
964 | xdp_set_query_size_pow (1<<QUERY_SIZE_DEFAULT); | ||
965 | } | ||
966 | |||
967 | if (gen->sources->len == 0) | ||
968 | { | ||
969 | xd_generate_void_event (EC_XdTooFewSources); | ||
970 | return FALSE; | ||
971 | } | ||
972 | |||
973 | for (i = 0; i < gen->sources->len; i += 1) | ||
974 | { | ||
975 | XdeltaSource* src = gen->sources->pdata[i]; | ||
976 | |||
977 | src->used = FALSE; | ||
978 | src->sequential = TRUE; | ||
979 | src->position = 0; | ||
980 | src->source_index = i; | ||
981 | |||
982 | if (src->source_index != 0) | ||
983 | total_from_len += handle_length (src->source_in); | ||
984 | } | ||
985 | |||
986 | /* QUERY_SIZE_POW is the number of elements freed in the cksum hash | ||
987 | * table for storing segment number + (offset/QUERY_SIZE_POW) in. 1 | ||
988 | * for the zero + 1 for the data segment */ | ||
989 | if (gen->sources->len > (QUERY_SIZE_POW-2)) | ||
990 | { | ||
991 | xd_generate_void_event (EC_XdTooManySources); | ||
992 | return FALSE; | ||
993 | } | ||
994 | |||
995 | if (handle_length (in) < QUERY_SIZE_POW || total_from_len < QUERY_SIZE_POW) | ||
996 | { | ||
997 | if (! just_output (gen, in)) | ||
998 | return FALSE; | ||
999 | } | ||
1000 | else | ||
1001 | { | ||
1002 | for (i = 0; i < gen->sources->len; i += 1) | ||
1003 | { | ||
1004 | XdeltaSource* xs = (XdeltaSource*)gen->sources->pdata[i]; | ||
1005 | |||
1006 | if (! xdp_source_check_index (xs)) | ||
1007 | return FALSE; | ||
1008 | |||
1009 | total_from_ck_count += xs->ck_count; | ||
1010 | } | ||
1011 | |||
1012 | prime = g_spaced_primes_closest (total_from_ck_count); | ||
1013 | |||
1014 | gen->table = table = g_new0 (guint32, prime); | ||
1015 | gen->table_size = prime; | ||
1016 | |||
1017 | for (i = 0; i < gen->sources->len; i += 1) | ||
1018 | { | ||
1019 | XdeltaSource* xs = (XdeltaSource*)gen->sources->pdata[i]; | ||
1020 | |||
1021 | for (j = xs->ck_count-1; j >= 0; j -= 1) | ||
1022 | { | ||
1023 | index = c_hash (xs->cksums + j) % prime; | ||
1024 | |||
1025 | #ifdef DEBUG_HASH | ||
1026 | gen->hash_entries += 1; | ||
1027 | |||
1028 | if (table[index]) | ||
1029 | { | ||
1030 | gen->hash_conflicts += 1; | ||
1031 | |||
1032 | /*regions_similar (gen, | ||
1033 | i, | ||
1034 | j, | ||
1035 | (table[index] & QUERY_SIZE_MASK) - 1, | ||
1036 | table[index] >> QUERY_SIZE);*/ | ||
1037 | } | ||
1038 | #endif | ||
1039 | |||
1040 | /* This is the real code */ | ||
1041 | table[index] = (j << QUERY_SIZE) + 1 + i; | ||
1042 | } | ||
1043 | } | ||
1044 | |||
1045 | #ifdef DEBUG_HASH | ||
1046 | for (i = 0; i < prime; i += 1) | ||
1047 | { | ||
1048 | if (gen->table[i]) | ||
1049 | gen->hash_fill += 1; | ||
1050 | } | ||
1051 | |||
1052 | g_print ("*** Hash stats:\n"); | ||
1053 | g_print ("Hash conflicts: %d\n", gen->hash_conflicts); | ||
1054 | g_print ("Hash real conflicts: %d\n", gen->hash_real_conflicts); | ||
1055 | g_print ("Hash real real conflicts: %d\n", gen->hash_real_real_conflicts); | ||
1056 | g_print ("Hash fill: %d\n", gen->hash_fill); | ||
1057 | g_print ("Hash size: %d\n", gen->table_size); | ||
1058 | g_print ("Hash entries: %d\n", gen->hash_entries); | ||
1059 | g_print ("Hash fill/entries: %f\n", (float)gen->hash_fill/(float)gen->hash_entries); | ||
1060 | #endif | ||
1061 | |||
1062 | if (! compute_copies (gen, in)) | ||
1063 | return FALSE; | ||
1064 | } | ||
1065 | |||
1066 | return TRUE; | ||
1067 | } | ||
1068 | |||
1069 | XdeltaControl* | ||
1070 | xdp_generate_delta (XdeltaGenerator *gen, | ||
1071 | XdeltaStream *in, | ||
1072 | XdeltaOutStream *control_out, | ||
1073 | XdeltaOutStream *data_out) | ||
1074 | { | ||
1075 | gint i; | ||
1076 | const guint8* in_md5; | ||
1077 | const guint8* data_out_md5; | ||
1078 | |||
1079 | gen->data_out = data_out; | ||
1080 | gen->control_out = control_out; | ||
1081 | gen->control = control_new (); | ||
1082 | |||
1083 | if (! xdp_generate_delta_int (gen, in, control_out, data_out)) | ||
1084 | return NULL; | ||
1085 | |||
1086 | if (! handle_close (data_out, 0)) | ||
1087 | return NULL; | ||
1088 | |||
1089 | if (! (in_md5 = handle_checksum_md5 (in))) | ||
1090 | return FALSE; | ||
1091 | |||
1092 | if (! (data_out_md5 = handle_checksum_md5 (data_out))) | ||
1093 | return FALSE; | ||
1094 | |||
1095 | gen->control->has_data = gen->data_source->used; | ||
1096 | gen->control->inst = &g_array_index (gen->control->inst_array, XdeltaInstruction, 0); | ||
1097 | gen->control->inst_len = gen->control->inst_array->len; | ||
1098 | |||
1099 | gen->control->to_len = handle_length (in); | ||
1100 | memcpy (gen->control->to_md5, in_md5, 16); | ||
1101 | |||
1102 | for (i = 0; i < gen->sources->len; i += 1) | ||
1103 | { | ||
1104 | XdeltaSource* src = gen->sources->pdata[i]; | ||
1105 | const guint8* md5; | ||
1106 | guint len; | ||
1107 | |||
1108 | if (src->source_in) | ||
1109 | { | ||
1110 | if (! (md5 = handle_checksum_md5 (src->source_in))) | ||
1111 | return FALSE; | ||
1112 | |||
1113 | len = handle_length (src->source_in); | ||
1114 | } | ||
1115 | else | ||
1116 | { | ||
1117 | len = handle_length (data_out); | ||
1118 | md5 = data_out_md5; | ||
1119 | } | ||
1120 | |||
1121 | if (! control_add_info (gen->control, src, md5, len)) | ||
1122 | return NULL; | ||
1123 | } | ||
1124 | |||
1125 | gen->control->source_info = (XdeltaSourceInfo**) gen->control->source_info_array->pdata; | ||
1126 | gen->control->source_info_len = gen->control->source_info_array->len; | ||
1127 | |||
1128 | if (control_out && ! xdp_control_write (gen->control, control_out)) | ||
1129 | return NULL; | ||
1130 | |||
1131 | return gen->control; | ||
1132 | } | ||
1133 | |||
1134 | /* Below here boring details mostly to do with reading and writing | ||
1135 | * control. */ | ||
1136 | |||
1137 | XdeltaControl* | ||
1138 | control_new (void) | ||
1139 | { | ||
1140 | XdeltaControl* it = g_new0 (XdeltaControl, 1); | ||
1141 | |||
1142 | it->inst_array = g_array_new (FALSE, FALSE, sizeof (XdeltaInstruction)); | ||
1143 | it->source_info_array = g_ptr_array_new (); | ||
1144 | |||
1145 | return it; | ||
1146 | } | ||
1147 | |||
1148 | static void | ||
1149 | control_reindex (XdeltaControl* cont, XdeltaSource* src) | ||
1150 | { | ||
1151 | gint i; | ||
1152 | gint new_index = cont->source_info_array->len; | ||
1153 | |||
1154 | for (i = 0; i < cont->inst_len; i += 1) | ||
1155 | { | ||
1156 | XdeltaInstruction* inst = cont->inst + i; | ||
1157 | |||
1158 | if (inst->index == src->source_index) | ||
1159 | inst->index = new_index; | ||
1160 | } | ||
1161 | } | ||
1162 | |||
1163 | gboolean | ||
1164 | control_add_info (XdeltaControl* cont, XdeltaSource* src, const guint8* md5, guint len) | ||
1165 | { | ||
1166 | XdeltaSourceInfo* si; | ||
1167 | |||
1168 | if (! src->used) | ||
1169 | return TRUE; | ||
1170 | |||
1171 | si = g_new0 (XdeltaSourceInfo, 1); | ||
1172 | |||
1173 | si->name = src->name; | ||
1174 | si->sequential = src->sequential; | ||
1175 | si->len = len; | ||
1176 | si->isdata = (src->source_index == 0); | ||
1177 | |||
1178 | memcpy (si->md5, md5, 16); | ||
1179 | |||
1180 | control_reindex (cont, src); | ||
1181 | |||
1182 | g_ptr_array_add (cont->source_info_array, si); | ||
1183 | |||
1184 | return TRUE; | ||
1185 | } | ||
1186 | |||
1187 | void | ||
1188 | xdp_control_free (XdeltaControl* cont) | ||
1189 | { | ||
1190 | if (cont->source_info_array) | ||
1191 | g_ptr_array_free (cont->source_info_array, TRUE); | ||
1192 | if (cont->inst_array) | ||
1193 | g_array_free (cont->inst_array, TRUE); | ||
1194 | g_free (cont); | ||
1195 | } | ||
1196 | |||
1197 | void | ||
1198 | control_copy (XdeltaControl* cont, XdeltaSource* src, guint from, guint to) | ||
1199 | { | ||
1200 | XdeltaInstruction i; | ||
1201 | |||
1202 | if (cont->inst_array->len > 0) | ||
1203 | { | ||
1204 | XdeltaInstruction* oi = & g_array_index (cont->inst_array, XdeltaInstruction, cont->inst_array->len-1); | ||
1205 | |||
1206 | if (oi->index == src->source_index && (oi->offset + oi->length) == from) | ||
1207 | { | ||
1208 | oi->length += (to - from); | ||
1209 | return; | ||
1210 | } | ||
1211 | } | ||
1212 | |||
1213 | i.index = src->source_index; | ||
1214 | i.offset = from; | ||
1215 | i.length = to - from; | ||
1216 | |||
1217 | src->used = TRUE; | ||
1218 | |||
1219 | if (src->position != from) | ||
1220 | src->sequential = FALSE; | ||
1221 | |||
1222 | src->position = to; | ||
1223 | |||
1224 | g_array_append_val (cont->inst_array, i); | ||
1225 | } | ||
1226 | |||
1227 | #ifdef DEBUG_CONT | ||
1228 | static void | ||
1229 | print_info (XdeltaSourceInfo* si) | ||
1230 | { | ||
1231 | char md5str[33]; | ||
1232 | |||
1233 | edsio_md5_to_string (si->md5, md5str); | ||
1234 | |||
1235 | g_print (" ** info\n"); | ||
1236 | g_print (" md5: %s\n", md5str); | ||
1237 | g_print (" len: %d\n", si->length); | ||
1238 | } | ||
1239 | |||
1240 | static void | ||
1241 | print_inst (XdeltaInstruction* i) | ||
1242 | { | ||
1243 | switch (i->type) | ||
1244 | { | ||
1245 | case INST_TYPE_COPY: | ||
1246 | g_print (" copy (%c) %d-%d (%d) from %d\n", i->type, i->offset, i->offset + i->length, i->length, i->index); | ||
1247 | break; | ||
1248 | case INST_TYPE_INSERT: | ||
1249 | g_print (" insert %d\n", i->length); | ||
1250 | break; | ||
1251 | } | ||
1252 | } | ||
1253 | |||
1254 | static void | ||
1255 | xdp_print_control (XdeltaControl *cont) | ||
1256 | { | ||
1257 | gint i; | ||
1258 | |||
1259 | g_print ("*** control\n"); | ||
1260 | |||
1261 | g_print (" data len: %d\n", cont->data_len); | ||
1262 | print_info (&cont->to_info); | ||
1263 | |||
1264 | g_print (" source info len: %d\n", cont->source_info_len); | ||
1265 | |||
1266 | for (i = 0; i < cont->source_info_len; i += 1) | ||
1267 | print_info (cont->source_info[i]); | ||
1268 | |||
1269 | g_print (" inst len: %d\n", cont->inst_len); | ||
1270 | |||
1271 | for (i = 0; i < cont->inst_len; i += 1) | ||
1272 | print_inst (cont->inst + i); | ||
1273 | |||
1274 | } | ||
1275 | #endif | ||
1276 | |||
1277 | #ifdef DEBUG_CHECK_CONTROL | ||
1278 | void | ||
1279 | check_control (XdeltaControl* cont) | ||
1280 | { | ||
1281 | gint i; | ||
1282 | |||
1283 | for (i = 0; i < cont->inst_len; i += 1) | ||
1284 | { | ||
1285 | switch (cont->inst[i].type) | ||
1286 | { | ||
1287 | case INST_TYPE_NCOPY: | ||
1288 | case INST_TYPE_COPY: | ||
1289 | if (cont->inst[i].index >= cont->source_info_len) | ||
1290 | g_error ("control has a too high instruction index\n"); | ||
1291 | } | ||
1292 | } | ||
1293 | } | ||
1294 | #endif | ||
1295 | |||
1296 | static gboolean | ||
1297 | unpack_instructions (XdeltaControl* cont) | ||
1298 | { | ||
1299 | gint i; | ||
1300 | guint output_pos = 0; | ||
1301 | |||
1302 | for (i = 0; i < cont->source_info_len; i += 1) | ||
1303 | { | ||
1304 | XdeltaSourceInfo* info = cont->source_info[i]; | ||
1305 | |||
1306 | info->position = 0; | ||
1307 | info->copies = 0; | ||
1308 | info->copy_length = 0; | ||
1309 | } | ||
1310 | |||
1311 | for (i = 0; i < cont->inst_len; i += 1) | ||
1312 | { | ||
1313 | XdeltaSourceInfo* info; | ||
1314 | XdeltaInstruction *inst = cont->inst + i; | ||
1315 | |||
1316 | if (inst->index >= cont->source_info_len) | ||
1317 | { | ||
1318 | xd_generate_int_event (EC_XdOutOfRangeSourceIndex, inst->index); | ||
1319 | return FALSE; | ||
1320 | } | ||
1321 | |||
1322 | info = cont->source_info[inst->index]; | ||
1323 | |||
1324 | if (info->sequential) | ||
1325 | { | ||
1326 | inst->offset = info->position; | ||
1327 | info->position = inst->offset + inst->length; | ||
1328 | } | ||
1329 | |||
1330 | inst->output_start = output_pos; | ||
1331 | output_pos += inst->length; | ||
1332 | |||
1333 | info->copies += 1; | ||
1334 | info->copy_length += inst->length; | ||
1335 | } | ||
1336 | |||
1337 | return TRUE; | ||
1338 | } | ||
1339 | |||
1340 | static gboolean | ||
1341 | pack_instructions (XdeltaControl* cont) | ||
1342 | { | ||
1343 | gint i; | ||
1344 | |||
1345 | for (i = 0; i < cont->source_info_len; i += 1) | ||
1346 | { | ||
1347 | XdeltaSourceInfo* info = cont->source_info[i]; | ||
1348 | |||
1349 | info->position = 0; | ||
1350 | info->copies = 0; | ||
1351 | info->copy_length = 0; | ||
1352 | } | ||
1353 | |||
1354 | for (i = 0; i < cont->inst_len; i += 1) | ||
1355 | { | ||
1356 | XdeltaSourceInfo* info; | ||
1357 | XdeltaInstruction *inst = cont->inst + i; | ||
1358 | |||
1359 | if (inst->index >= cont->source_info_len) | ||
1360 | { | ||
1361 | xd_generate_int_event (EC_XdOutOfRangeSourceIndex, inst->index); | ||
1362 | return FALSE; | ||
1363 | } | ||
1364 | |||
1365 | info = cont->source_info[inst->index]; | ||
1366 | |||
1367 | if (info->sequential) | ||
1368 | { | ||
1369 | g_assert (info->position == inst->offset); | ||
1370 | info->position += inst->length; | ||
1371 | inst->offset = 0; | ||
1372 | } | ||
1373 | |||
1374 | info->copies += 1; | ||
1375 | info->copy_length += inst->length; | ||
1376 | } | ||
1377 | |||
1378 | return TRUE; | ||
1379 | } | ||
1380 | |||
1381 | |||
1382 | gboolean | ||
1383 | xdp_control_write (XdeltaControl *cont, | ||
1384 | XdeltaOutStream *cont_out) | ||
1385 | { | ||
1386 | SerialSink* sink = handle_sink (cont_out, NULL, NULL, NULL, NULL); | ||
1387 | |||
1388 | #ifdef DEBUG_CONT | ||
1389 | xdp_print_control (cont); | ||
1390 | #endif | ||
1391 | #ifdef DEBUG_CHECK_CONTROL | ||
1392 | check_control (cont); | ||
1393 | #endif | ||
1394 | |||
1395 | if (! sink) | ||
1396 | return FALSE; | ||
1397 | |||
1398 | if (! pack_instructions (cont)) | ||
1399 | return FALSE; | ||
1400 | |||
1401 | /* @@@ think about how the count function overcounts on the instruction | ||
1402 | * array by a factor of 2 or more. */ | ||
1403 | if (! serialize_xdeltacontrol_obj (sink, cont)) | ||
1404 | return FALSE; | ||
1405 | |||
1406 | if (! handle_close (cont_out, 0)) | ||
1407 | return FALSE; | ||
1408 | |||
1409 | return TRUE; | ||
1410 | } | ||
1411 | |||
1412 | XdeltaControl* | ||
1413 | xdp_control_read (XdeltaStream *cont_in) | ||
1414 | { | ||
1415 | SerialSource* src = handle_source (cont_in); | ||
1416 | XdeltaControl* cont; | ||
1417 | SerialType type; | ||
1418 | |||
1419 | if (! src) | ||
1420 | return NULL; | ||
1421 | |||
1422 | if (! serializeio_unserialize_generic_acceptable (src, ST_XdeltaControl | ST_Version0Control, & type, (void**) & cont)) | ||
1423 | return NULL; | ||
1424 | |||
1425 | if (type == ST_Version0Control) | ||
1426 | { | ||
1427 | SerialVersion0Control *ocont = (SerialVersion0Control*) cont; | ||
1428 | |||
1429 | xd_generate_string_event (EC_XdBackwardCompatibilityMode, "1.0"); | ||
1430 | |||
1431 | cont = control_version_0 (ocont); | ||
1432 | |||
1433 | g_free (ocont); | ||
1434 | } | ||
1435 | |||
1436 | if (! unpack_instructions (cont)) | ||
1437 | return NULL; | ||
1438 | |||
1439 | #ifdef DEBUG_CHECK_CONTROL | ||
1440 | check_control (cont); | ||
1441 | #endif | ||
1442 | |||
1443 | return cont; | ||
1444 | } | ||
1445 | |||
1446 | XdeltaControl* | ||
1447 | control_version_0 (SerialVersion0Control* ocont) | ||
1448 | { | ||
1449 | XdeltaControl* cont = g_new0 (XdeltaControl, 1); | ||
1450 | gint i; | ||
1451 | XdeltaSourceInfo* dinfo; | ||
1452 | |||
1453 | g_assert (! ocont->normalized); | ||
1454 | |||
1455 | memcpy (cont->to_md5, ocont->to_info.real_md5, 16); | ||
1456 | |||
1457 | cont->to_len = ocont->to_info.length; | ||
1458 | |||
1459 | cont->has_data = TRUE; | ||
1460 | |||
1461 | cont->source_info_len = ocont->source_info_len + 1; | ||
1462 | cont->source_info = g_new (XdeltaSourceInfo*, cont->source_info_len); | ||
1463 | |||
1464 | cont->source_info[0] = dinfo = g_new0 (XdeltaSourceInfo, 1); | ||
1465 | |||
1466 | dinfo->name = "(patch data)"; | ||
1467 | memcpy (dinfo->md5, ocont->to_info.md5, 15); | ||
1468 | dinfo->len = ocont->data_len; | ||
1469 | dinfo->isdata = TRUE; | ||
1470 | dinfo->sequential = FALSE; | ||
1471 | |||
1472 | for (i = 0; i < ocont->source_info_len; i += 1) | ||
1473 | { | ||
1474 | XdeltaSourceInfo* info = g_new0 (XdeltaSourceInfo, 1); | ||
1475 | SerialVersion0SourceInfo* oinfo = ocont->source_info[i]; | ||
1476 | |||
1477 | cont->source_info[i+1] = info; | ||
1478 | |||
1479 | info->name = "unnamed"; | ||
1480 | memcpy (info->md5, oinfo->md5, 16); | ||
1481 | info->len = oinfo->length; | ||
1482 | info->isdata = FALSE; | ||
1483 | info->sequential = FALSE; | ||
1484 | } | ||
1485 | |||
1486 | /* The old unpack */ | ||
1487 | #define OLD_QUERY_SIZE 4 | ||
1488 | for (i = 0; i < ocont->inst_len; i += 1) | ||
1489 | { | ||
1490 | switch (ocont->inst[i].length & 3) | ||
1491 | { | ||
1492 | case 0: ocont->inst[i].type = 'N'; break; | ||
1493 | case 1: ocont->inst[i].type = 'E'; break; | ||
1494 | case 2: ocont->inst[i].type = 'C'; break; | ||
1495 | case 3: ocont->inst[i].type = 'I'; break; | ||
1496 | } | ||
1497 | |||
1498 | ocont->inst[i].length >>= 2; | ||
1499 | ocont->inst[i].index = ocont->inst[i].length & OLD_QUERY_SIZE; | ||
1500 | ocont->inst[i].length >>= OLD_QUERY_SIZE; | ||
1501 | } | ||
1502 | |||
1503 | cont->inst_len = ocont->inst_len; | ||
1504 | cont->inst = g_new (XdeltaInstruction, cont->inst_len); | ||
1505 | |||
1506 | for (i = 0; i < cont->inst_len; i += 1) | ||
1507 | { | ||
1508 | cont->inst[i].length = ocont->inst[i].length; | ||
1509 | cont->inst[i].offset = ocont->inst[i].offset; | ||
1510 | |||
1511 | switch (ocont->inst[i].type) | ||
1512 | { | ||
1513 | case 'N': | ||
1514 | case 'E': | ||
1515 | abort (); | ||
1516 | break; | ||
1517 | |||
1518 | case 'C': | ||
1519 | g_assert (ocont->inst[i].index == 0); | ||
1520 | |||
1521 | cont->inst[i].index = 1; | ||
1522 | break; | ||
1523 | |||
1524 | case 'I': | ||
1525 | cont->inst[i].index = 0; | ||
1526 | break; | ||
1527 | } | ||
1528 | |||
1529 | } | ||
1530 | |||
1531 | return cont; | ||
1532 | } | ||