"Fossies" - the Fresh Open Source Software Archive 
Member "xdelta3-3.0.11/xdelta3-merge.h" (11 Nov 2015, 13934 Bytes) of package /linux/misc/xdelta3-3.0.11.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "xdelta3-merge.h" see the
Fossies "Dox" file reference documentation.
1 /* xdelta 3 - delta compression tools and library
2 * Copyright (C) 2007. Joshua P. MacDonald
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 */
18
19 #ifndef _XDELTA3_MERGE_H_
20 #define _XDELTA3_MERGE_H_
21
22 int xd3_merge_inputs (xd3_stream *stream,
23 xd3_whole_state *source,
24 xd3_whole_state *input);
25
26 static int
27 xd3_whole_state_init (xd3_stream *stream)
28 {
29 XD3_ASSERT (stream->whole_target.adds == NULL);
30 XD3_ASSERT (stream->whole_target.inst == NULL);
31 XD3_ASSERT (stream->whole_target.wininfo == NULL);
32 XD3_ASSERT (stream->whole_target.length == 0);
33
34 stream->whole_target.adds_alloc = XD3_ALLOCSIZE;
35 stream->whole_target.inst_alloc = XD3_ALLOCSIZE;
36 stream->whole_target.wininfo_alloc = XD3_ALLOCSIZE;
37
38 if ((stream->whole_target.adds = (uint8_t*)
39 xd3_alloc (stream, stream->whole_target.adds_alloc, 1)) == NULL ||
40 (stream->whole_target.inst = (xd3_winst*)
41 xd3_alloc (stream, stream->whole_target.inst_alloc, 1)) == NULL ||
42 (stream->whole_target.wininfo = (xd3_wininfo*)
43 xd3_alloc (stream, stream->whole_target.wininfo_alloc, 1)) == NULL)
44 {
45 return ENOMEM;
46 }
47 return 0;
48 }
49
50 static void
51 xd3_swap_whole_state (xd3_whole_state *a,
52 xd3_whole_state *b)
53 {
54 xd3_whole_state tmp;
55 XD3_ASSERT (a->inst != NULL && a->adds != NULL);
56 XD3_ASSERT (b->inst != NULL && b->adds != NULL);
57 XD3_ASSERT (b->wininfo != NULL && b->wininfo != NULL);
58 memcpy (&tmp, a, sizeof (xd3_whole_state));
59 memcpy (a, b, sizeof (xd3_whole_state));
60 memcpy (b, &tmp, sizeof (xd3_whole_state));
61 }
62
63 static int
64 xd3_realloc_buffer (xd3_stream *stream,
65 usize_t current_units,
66 usize_t unit_size,
67 usize_t new_units,
68 usize_t *alloc_size,
69 void **alloc_ptr)
70 {
71 usize_t needed;
72 usize_t new_alloc;
73 usize_t cur_size;
74 uint8_t *new_buf;
75
76 needed = (current_units + new_units) * unit_size;
77
78 if (needed <= *alloc_size)
79 {
80 return 0;
81 }
82
83 cur_size = current_units * unit_size;
84 new_alloc = xd3_round_blksize (needed * 2, XD3_ALLOCSIZE);
85
86 if ((new_buf = (uint8_t*) xd3_alloc (stream, new_alloc, 1)) == NULL)
87 {
88 return ENOMEM;
89 }
90
91 if (cur_size != 0)
92 {
93 memcpy (new_buf, *alloc_ptr, cur_size);
94 }
95
96 if (*alloc_ptr != NULL)
97 {
98 xd3_free (stream, *alloc_ptr);
99 }
100
101 *alloc_size = new_alloc;
102 *alloc_ptr = new_buf;
103
104 return 0;
105 }
106
107 /* allocate one new output instruction */
108 static int
109 xd3_whole_alloc_winst (xd3_stream *stream,
110 xd3_winst **winstp)
111 {
112 int ret;
113
114 if ((ret = xd3_realloc_buffer (stream,
115 stream->whole_target.instlen,
116 sizeof (xd3_winst),
117 1,
118 & stream->whole_target.inst_alloc,
119 (void**) & stream->whole_target.inst)))
120 {
121 return ret;
122 }
123
124 *winstp = &stream->whole_target.inst[stream->whole_target.instlen++];
125
126 return 0;
127 }
128
129 static int
130 xd3_whole_alloc_adds (xd3_stream *stream,
131 usize_t count)
132 {
133 return xd3_realloc_buffer (stream,
134 stream->whole_target.addslen,
135 1,
136 count,
137 & stream->whole_target.adds_alloc,
138 (void**) & stream->whole_target.adds);
139 }
140
141 static int
142 xd3_whole_alloc_wininfo (xd3_stream *stream,
143 xd3_wininfo **wininfop)
144 {
145 int ret;
146
147 if ((ret = xd3_realloc_buffer (stream,
148 stream->whole_target.wininfolen,
149 sizeof (xd3_wininfo),
150 1,
151 & stream->whole_target.wininfo_alloc,
152 (void**) & stream->whole_target.wininfo)))
153 {
154 return ret;
155 }
156
157 *wininfop = &stream->whole_target.wininfo[stream->whole_target.wininfolen++];
158
159 return 0;
160 }
161
162 static int
163 xd3_whole_append_inst (xd3_stream *stream,
164 xd3_hinst *inst)
165 {
166 int ret;
167 xd3_winst *winst;
168
169 if ((ret = xd3_whole_alloc_winst (stream, &winst)))
170 {
171 return ret;
172 }
173
174 winst->type = inst->type;
175 winst->mode = 0;
176 winst->size = inst->size;
177 winst->position = stream->whole_target.length;
178 stream->whole_target.length += inst->size;
179
180 if (((inst->type == XD3_ADD) || (inst->type == XD3_RUN)) &&
181 (ret = xd3_whole_alloc_adds (stream,
182 (inst->type == XD3_RUN ? 1 : inst->size))))
183 {
184 return ret;
185 }
186
187 switch (inst->type)
188 {
189 case XD3_RUN:
190 winst->addr = stream->whole_target.addslen;
191 stream->whole_target.adds[stream->whole_target.addslen++] =
192 *stream->data_sect.buf++;
193 break;
194
195 case XD3_ADD:
196 winst->addr = stream->whole_target.addslen;
197 memcpy (stream->whole_target.adds + stream->whole_target.addslen,
198 stream->data_sect.buf,
199 inst->size);
200 stream->data_sect.buf += inst->size;
201 stream->whole_target.addslen += inst->size;
202 break;
203
204 default:
205 if (inst->addr < stream->dec_cpylen)
206 {
207 winst->mode = SRCORTGT (stream->dec_win_ind);
208 winst->addr = stream->dec_cpyoff + inst->addr;
209 }
210 else
211 {
212 winst->addr = (stream->dec_winstart +
213 inst->addr -
214 stream->dec_cpylen);
215 }
216 break;
217 }
218
219 return 0;
220 }
221
222 int
223 xd3_whole_append_window (xd3_stream *stream)
224 {
225 int ret;
226 xd3_wininfo *wininfo;
227
228 if ((ret = xd3_whole_alloc_wininfo (stream, &wininfo))) { return ret; }
229
230 wininfo->length = stream->dec_tgtlen;
231 wininfo->offset = stream->dec_winstart;
232 wininfo->adler32 = stream->dec_adler32;
233
234 while (stream->inst_sect.buf < stream->inst_sect.buf_max)
235 {
236 if ((ret = xd3_decode_instruction (stream)))
237 {
238 return ret;
239 }
240
241 if ((stream->dec_current1.type != XD3_NOOP) &&
242 (ret = xd3_whole_append_inst (stream,
243 & stream->dec_current1)))
244 {
245 return ret;
246 }
247
248 if ((stream->dec_current2.type != XD3_NOOP) &&
249 (ret = xd3_whole_append_inst (stream,
250 & stream->dec_current2)))
251 {
252 return ret;
253 }
254 }
255
256 return 0;
257 }
258
259 /* xd3_merge_input_output applies *source to *stream, returns the
260 * result in stream. */
261 int xd3_merge_input_output (xd3_stream *stream,
262 xd3_whole_state *source)
263 {
264 int ret;
265 xd3_stream tmp_stream;
266 memset (& tmp_stream, 0, sizeof (tmp_stream));
267 if ((ret = xd3_config_stream (& tmp_stream, NULL)) ||
268 (ret = xd3_whole_state_init (& tmp_stream)) ||
269 (ret = xd3_merge_inputs (& tmp_stream,
270 source,
271 & stream->whole_target)))
272 {
273 XPR(NT XD3_LIB_ERRMSG (&tmp_stream, ret));
274 return ret;
275 }
276
277 /* the output is in tmp_stream.whole_state, swap into input */
278 xd3_swap_whole_state (& stream->whole_target,
279 & tmp_stream.whole_target);
280 /* total allocation counts are preserved */
281 xd3_free_stream (& tmp_stream);
282 return 0;
283 }
284
285 static int
286 xd3_merge_run (xd3_stream *stream,
287 xd3_whole_state *target,
288 xd3_winst *iinst)
289 {
290 int ret;
291 xd3_winst *oinst;
292
293 if ((ret = xd3_whole_alloc_winst (stream, &oinst)) ||
294 (ret = xd3_whole_alloc_adds (stream, 1)))
295 {
296 return ret;
297 }
298
299 oinst->type = iinst->type;
300 oinst->mode = iinst->mode;
301 oinst->size = iinst->size;
302 oinst->addr = stream->whole_target.addslen;
303
304 XD3_ASSERT (stream->whole_target.length == iinst->position);
305 oinst->position = stream->whole_target.length;
306 stream->whole_target.length += iinst->size;
307
308 stream->whole_target.adds[stream->whole_target.addslen++] =
309 target->adds[iinst->addr];
310
311 return 0;
312 }
313
314 static int
315 xd3_merge_add (xd3_stream *stream,
316 xd3_whole_state *target,
317 xd3_winst *iinst)
318 {
319 int ret;
320 xd3_winst *oinst;
321
322 if ((ret = xd3_whole_alloc_winst (stream, &oinst)) ||
323 (ret = xd3_whole_alloc_adds (stream, iinst->size)))
324 {
325 return ret;
326 }
327
328 oinst->type = iinst->type;
329 oinst->mode = iinst->mode;
330 oinst->size = iinst->size;
331 oinst->addr = stream->whole_target.addslen;
332
333 XD3_ASSERT (stream->whole_target.length == iinst->position);
334 oinst->position = stream->whole_target.length;
335 stream->whole_target.length += iinst->size;
336
337 memcpy(stream->whole_target.adds + stream->whole_target.addslen,
338 target->adds + iinst->addr,
339 iinst->size);
340
341 stream->whole_target.addslen += iinst->size;
342
343 return 0;
344 }
345
346 static int
347 xd3_merge_target_copy (xd3_stream *stream,
348 xd3_winst *iinst)
349 {
350 int ret;
351 xd3_winst *oinst;
352
353 if ((ret = xd3_whole_alloc_winst (stream, &oinst)))
354 {
355 return ret;
356 }
357
358 XD3_ASSERT (stream->whole_target.length == iinst->position);
359
360 memcpy (oinst, iinst, sizeof (*oinst));
361 return 0;
362 }
363
364 static int
365 xd3_merge_find_position (xd3_stream *stream,
366 xd3_whole_state *source,
367 xoff_t address,
368 usize_t *inst_num)
369 {
370 usize_t low;
371 usize_t high;
372
373 if (address >= source->length)
374 {
375 stream->msg = "Invalid copy offset in merge";
376 return XD3_INVALID_INPUT;
377 }
378
379 low = 0;
380 high = source->instlen;
381
382 while (low != high)
383 {
384 xoff_t mid_lpos;
385 xoff_t mid_hpos;
386 usize_t mid = low + (high - low) / 2;
387 mid_lpos = source->inst[mid].position;
388
389 if (address < mid_lpos)
390 {
391 high = mid;
392 continue;
393 }
394
395 mid_hpos = mid_lpos + source->inst[mid].size;
396
397 if (address >= mid_hpos)
398 {
399 low = mid + 1;
400 continue;
401 }
402
403 *inst_num = mid;
404 return 0;
405 }
406
407 stream->msg = "Internal error in merge";
408 return XD3_INTERNAL;
409 }
410
411 static int
412 xd3_merge_source_copy (xd3_stream *stream,
413 xd3_whole_state *source,
414 const xd3_winst *iinst_orig)
415 {
416 int ret;
417 xd3_winst iinst;
418 usize_t sinst_num;
419
420 memcpy (& iinst, iinst_orig, sizeof (iinst));
421
422 XD3_ASSERT (iinst.mode == VCD_SOURCE);
423
424 if ((ret = xd3_merge_find_position (stream, source,
425 iinst.addr, &sinst_num)))
426 {
427 return ret;
428 }
429
430 while (iinst.size > 0)
431 {
432 xd3_winst *sinst;
433 xd3_winst *minst;
434 usize_t sinst_offset;
435 usize_t sinst_left;
436 usize_t this_take;
437
438 XD3_ASSERT (sinst_num < source->instlen);
439
440 sinst = &source->inst[sinst_num];
441
442 XD3_ASSERT (iinst.addr >= sinst->position);
443
444 sinst_offset = (usize_t)(iinst.addr - sinst->position);
445
446 XD3_ASSERT (sinst->size > sinst_offset);
447
448 sinst_left = sinst->size - sinst_offset;
449 this_take = xd3_min (iinst.size, sinst_left);
450
451 XD3_ASSERT (this_take > 0);
452
453 if ((ret = xd3_whole_alloc_winst (stream, &minst)))
454 {
455 return ret;
456 }
457
458 minst->size = this_take;
459 minst->type = sinst->type;
460 minst->position = iinst.position;
461 minst->mode = 0;
462
463 switch (sinst->type)
464 {
465 case XD3_RUN:
466 if ((ret = xd3_whole_alloc_adds (stream, 1)))
467 {
468 return ret;
469 }
470
471 minst->addr = stream->whole_target.addslen;
472 stream->whole_target.adds[stream->whole_target.addslen++] =
473 source->adds[sinst->addr];
474 break;
475 case XD3_ADD:
476 if ((ret = xd3_whole_alloc_adds (stream, this_take)))
477 {
478 return ret;
479 }
480
481 minst->addr = stream->whole_target.addslen;
482 memcpy(stream->whole_target.adds + stream->whole_target.addslen,
483 source->adds + sinst->addr + sinst_offset,
484 this_take);
485 stream->whole_target.addslen += this_take;
486 break;
487 default:
488 if (sinst->mode != 0)
489 {
490 minst->mode = sinst->mode;
491 minst->addr = sinst->addr + sinst_offset;
492 }
493 else
494 {
495 // Note: A better implementation will construct the
496 // mapping of output ranges, starting from the input
497 // range, applying deltas in forward order, using an
498 // interval tree. This code uses recursion to construct
499 // each copied range, recursively (using binary search
500 // in xd3_merge_find_position).
501 //
502 // TODO: This code can cause stack overflow. Fix as
503 // described above.
504 xd3_winst tinst;
505 tinst.type = XD3_CPY;
506 tinst.mode = iinst.mode;
507 tinst.addr = sinst->addr + sinst_offset;
508 tinst.size = this_take;
509 tinst.position = iinst.position;
510
511 // The instruction allocated in this frame will not be used.
512 stream->whole_target.instlen -= 1;
513
514 if ((ret = xd3_merge_source_copy (stream, source, &tinst)))
515 {
516 return ret;
517 }
518 }
519 break;
520 }
521
522 iinst.position += this_take;
523 iinst.addr += this_take;
524 iinst.size -= this_take;
525 sinst_num += 1;
526 }
527
528 return 0;
529 }
530
531 /* xd3_merge_inputs() applies *input to *source, returns its result in
532 * stream. */
533 int xd3_merge_inputs (xd3_stream *stream,
534 xd3_whole_state *source,
535 xd3_whole_state *input)
536 {
537 int ret = 0;
538 usize_t i;
539 size_t input_i;
540
541 for (i = 0; i < input->wininfolen; ++i) {
542 xd3_wininfo *copyinfo;
543
544 if ((ret = xd3_whole_alloc_wininfo (stream, ©info))) { return ret; }
545
546 *copyinfo = input->wininfo[i];
547 }
548
549 /* iterate over each instruction. */
550 for (input_i = 0; ret == 0 && input_i < input->instlen; ++input_i)
551 {
552 xd3_winst *iinst = &input->inst[input_i];
553
554 switch (iinst->type)
555 {
556 case XD3_RUN:
557 ret = xd3_merge_run (stream, input, iinst);
558 break;
559 case XD3_ADD:
560 ret = xd3_merge_add (stream, input, iinst);
561 break;
562 default:
563 if (iinst->mode == 0)
564 {
565 ret = xd3_merge_target_copy (stream, iinst);
566 }
567 else if (iinst->mode == VCD_TARGET)
568 {
569 ret = XD3_INVALID_INPUT;
570 }
571 else
572 {
573 ret = xd3_merge_source_copy (stream, source, iinst);
574 }
575
576 /* The whole_target.length is not updated in the xd3_merge*copy
577 * routine because of recursion in xd3_merge_source_copy. */
578 stream->whole_target.length += iinst->size;
579 break;
580 }
581 }
582
583 return ret;
584 }
585
586 #endif