1 /* xdelta 3 - delta compression tools and library
2 * Copyright (C) 2007. Joshua P. MacDonald
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.
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.
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
19 #ifndef _XDELTA3_MERGE_H_
20 #define _XDELTA3_MERGE_H_
22 int xd3_merge_inputs (xd3_stream *stream,
23 xd3_whole_state *source,
24 xd3_whole_state *input);
27 xd3_whole_state_init (xd3_stream *stream)
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);
34 stream->whole_target.adds_alloc = XD3_ALLOCSIZE;
35 stream->whole_target.inst_alloc = XD3_ALLOCSIZE;
36 stream->whole_target.wininfo_alloc = XD3_ALLOCSIZE;
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)
51 xd3_swap_whole_state (xd3_whole_state *a,
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));
64 xd3_realloc_buffer (xd3_stream *stream,
65 usize_t current_units,
76 needed = (current_units + new_units) * unit_size;
78 if (needed <= *alloc_size)
83 cur_size = current_units * unit_size;
84 new_alloc = xd3_round_blksize (needed * 2, XD3_ALLOCSIZE);
86 if ((new_buf = (uint8_t*) xd3_alloc (stream, new_alloc, 1)) == NULL)
93 memcpy (new_buf, *alloc_ptr, cur_size);
96 if (*alloc_ptr != NULL)
98 xd3_free (stream, *alloc_ptr);
101 *alloc_size = new_alloc;
102 *alloc_ptr = new_buf;
107 /* allocate one new output instruction */
109 xd3_whole_alloc_winst (xd3_stream *stream,
114 if ((ret = xd3_realloc_buffer (stream,
115 stream->whole_target.instlen,
118 & stream->whole_target.inst_alloc,
119 (void**) & stream->whole_target.inst)))
124 *winstp = &stream->whole_target.inst[stream->whole_target.instlen++];
130 xd3_whole_alloc_adds (xd3_stream *stream,
133 return xd3_realloc_buffer (stream,
134 stream->whole_target.addslen,
137 & stream->whole_target.adds_alloc,
138 (void**) & stream->whole_target.adds);
142 xd3_whole_alloc_wininfo (xd3_stream *stream,
143 xd3_wininfo **wininfop)
147 if ((ret = xd3_realloc_buffer (stream,
148 stream->whole_target.wininfolen,
149 sizeof (xd3_wininfo),
151 & stream->whole_target.wininfo_alloc,
152 (void**) & stream->whole_target.wininfo)))
157 *wininfop = &stream->whole_target.wininfo[stream->whole_target.wininfolen++];
163 xd3_whole_append_inst (xd3_stream *stream,
169 if ((ret = xd3_whole_alloc_winst (stream, &winst)))
174 winst->type = inst->type;
176 winst->size = inst->size;
177 winst->position = stream->whole_target.length;
178 stream->whole_target.length += inst->size;
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))))
190 winst->addr = stream->whole_target.addslen;
191 stream->whole_target.adds[stream->whole_target.addslen++] =
192 *stream->data_sect.buf++;
196 winst->addr = stream->whole_target.addslen;
197 memcpy (stream->whole_target.adds + stream->whole_target.addslen,
198 stream->data_sect.buf,
200 stream->data_sect.buf += inst->size;
201 stream->whole_target.addslen += inst->size;
205 if (inst->addr < stream->dec_cpylen)
207 winst->mode = SRCORTGT (stream->dec_win_ind);
208 winst->addr = stream->dec_cpyoff + inst->addr;
212 winst->addr = (stream->dec_winstart +
223 xd3_whole_append_window (xd3_stream *stream)
226 xd3_wininfo *wininfo;
228 if ((ret = xd3_whole_alloc_wininfo (stream, &wininfo))) { return ret; }
230 wininfo->length = stream->dec_tgtlen;
231 wininfo->offset = stream->dec_winstart;
232 wininfo->adler32 = stream->dec_adler32;
234 while (stream->inst_sect.buf < stream->inst_sect.buf_max)
236 if ((ret = xd3_decode_instruction (stream)))
241 if ((stream->dec_current1.type != XD3_NOOP) &&
242 (ret = xd3_whole_append_inst (stream,
243 & stream->dec_current1)))
248 if ((stream->dec_current2.type != XD3_NOOP) &&
249 (ret = xd3_whole_append_inst (stream,
250 & stream->dec_current2)))
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)
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,
271 & stream->whole_target)))
273 XPR(NT XD3_LIB_ERRMSG (&tmp_stream, ret));
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);
286 xd3_merge_run (xd3_stream *stream,
287 xd3_whole_state *target,
293 if ((ret = xd3_whole_alloc_winst (stream, &oinst)) ||
294 (ret = xd3_whole_alloc_adds (stream, 1)))
299 oinst->type = iinst->type;
300 oinst->mode = iinst->mode;
301 oinst->size = iinst->size;
302 oinst->addr = stream->whole_target.addslen;
304 XD3_ASSERT (stream->whole_target.length == iinst->position);
305 oinst->position = stream->whole_target.length;
306 stream->whole_target.length += iinst->size;
308 stream->whole_target.adds[stream->whole_target.addslen++] =
309 target->adds[iinst->addr];
315 xd3_merge_add (xd3_stream *stream,
316 xd3_whole_state *target,
322 if ((ret = xd3_whole_alloc_winst (stream, &oinst)) ||
323 (ret = xd3_whole_alloc_adds (stream, iinst->size)))
328 oinst->type = iinst->type;
329 oinst->mode = iinst->mode;
330 oinst->size = iinst->size;
331 oinst->addr = stream->whole_target.addslen;
333 XD3_ASSERT (stream->whole_target.length == iinst->position);
334 oinst->position = stream->whole_target.length;
335 stream->whole_target.length += iinst->size;
337 memcpy(stream->whole_target.adds + stream->whole_target.addslen,
338 target->adds + iinst->addr,
341 stream->whole_target.addslen += iinst->size;
347 xd3_merge_target_copy (xd3_stream *stream,
353 if ((ret = xd3_whole_alloc_winst (stream, &oinst)))
358 XD3_ASSERT (stream->whole_target.length == iinst->position);
360 memcpy (oinst, iinst, sizeof (*oinst));
365 xd3_merge_find_position (xd3_stream *stream,
366 xd3_whole_state *source,
373 if (address >= source->length)
375 stream->msg = "Invalid copy offset in merge";
376 return XD3_INVALID_INPUT;
380 high = source->instlen;
386 usize_t mid = low + (high - low) / 2;
387 mid_lpos = source->inst[mid].position;
389 if (address < mid_lpos)
395 mid_hpos = mid_lpos + source->inst[mid].size;
397 if (address >= mid_hpos)
407 stream->msg = "Internal error in merge";
412 xd3_merge_source_copy (xd3_stream *stream,
413 xd3_whole_state *source,
414 const xd3_winst *iinst_orig)
420 memcpy (& iinst, iinst_orig, sizeof (iinst));
422 XD3_ASSERT (iinst.mode == VCD_SOURCE);
424 if ((ret = xd3_merge_find_position (stream, source,
425 iinst.addr, &sinst_num)))
430 while (iinst.size > 0)
434 usize_t sinst_offset;
438 XD3_ASSERT (sinst_num < source->instlen);
440 sinst = &source->inst[sinst_num];
442 XD3_ASSERT (iinst.addr >= sinst->position);
444 sinst_offset = (usize_t)(iinst.addr - sinst->position);
446 XD3_ASSERT (sinst->size > sinst_offset);
448 sinst_left = sinst->size - sinst_offset;
449 this_take = min (iinst.size, sinst_left);
451 XD3_ASSERT (this_take > 0);
453 if ((ret = xd3_whole_alloc_winst (stream, &minst)))
458 minst->size = this_take;
459 minst->type = sinst->type;
460 minst->position = iinst.position;
466 if ((ret = xd3_whole_alloc_adds (stream, 1)))
471 minst->addr = stream->whole_target.addslen;
472 stream->whole_target.adds[stream->whole_target.addslen++] =
473 source->adds[sinst->addr];
476 if ((ret = xd3_whole_alloc_adds (stream, this_take)))
481 minst->addr = stream->whole_target.addslen;
482 memcpy(stream->whole_target.adds + stream->whole_target.addslen,
483 source->adds + sinst->addr + sinst_offset,
485 stream->whole_target.addslen += this_take;
488 if (sinst->mode != 0)
490 minst->mode = sinst->mode;
491 minst->addr = sinst->addr + sinst_offset;
495 // TODO: this is slow because of the recursion, which
496 // could reach a depth equal to the number of target
497 // copies, and this is compression-inefficient because
498 // it can produce duplicate adds.
500 tinst.type = XD3_CPY;
501 tinst.mode = iinst.mode;
502 tinst.addr = sinst->addr + sinst_offset;
503 tinst.size = this_take;
504 tinst.position = iinst.position;
506 // The instruction allocated in this frame will not be used.
507 stream->whole_target.instlen -= 1;
509 if ((ret = xd3_merge_source_copy (stream, source, &tinst)))
517 iinst.position += this_take;
518 iinst.addr += this_take;
519 iinst.size -= this_take;
526 /* xd3_merge_inputs() applies *input to *source, returns its result in
528 int xd3_merge_inputs (xd3_stream *stream,
529 xd3_whole_state *source,
530 xd3_whole_state *input)
536 for (i = 0; i < input->wininfolen; ++i) {
537 xd3_wininfo *copyinfo;
539 if ((ret = xd3_whole_alloc_wininfo (stream, ©info))) { return ret; }
541 *copyinfo = input->wininfo[i];
544 /* iterate over each instruction. */
545 for (input_i = 0; ret == 0 && input_i < input->instlen; ++input_i)
547 xd3_winst *iinst = &input->inst[input_i];
552 ret = xd3_merge_run (stream, input, iinst);
555 ret = xd3_merge_add (stream, input, iinst);
558 /* TODO: VCD_TARGET support is completely untested all
560 if (iinst->mode == 0 || iinst->mode == VCD_TARGET)
562 ret = xd3_merge_target_copy (stream, iinst);
566 ret = xd3_merge_source_copy (stream, source, iinst);
569 /* The whole_target.length is not updated in the xd3_merge*copy
570 * routine because of recursion in xd3_merge_source_copy. */
571 stream->whole_target.length += iinst->size;