aboutsummaryrefslogtreecommitdiff
path: root/xdelta3-merge.h
diff options
context:
space:
mode:
Diffstat (limited to 'xdelta3-merge.h')
-rw-r--r--xdelta3-merge.h579
1 files changed, 579 insertions, 0 deletions
diff --git a/xdelta3-merge.h b/xdelta3-merge.h
new file mode 100644
index 0000000..2253a2c
--- /dev/null
+++ b/xdelta3-merge.h
@@ -0,0 +1,579 @@
+/* xdelta 3 - delta compression tools and library
+ * Copyright (C) 2007. Joshua P. MacDonald
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef _XDELTA3_MERGE_H_
+#define _XDELTA3_MERGE_H_
+
+int xd3_merge_inputs (xd3_stream *stream,
+ xd3_whole_state *source,
+ xd3_whole_state *input);
+
+static int
+xd3_whole_state_init (xd3_stream *stream)
+{
+ XD3_ASSERT (stream->whole_target.adds == NULL);
+ XD3_ASSERT (stream->whole_target.inst == NULL);
+ XD3_ASSERT (stream->whole_target.wininfo == NULL);
+ XD3_ASSERT (stream->whole_target.length == 0);
+
+ stream->whole_target.adds_alloc = XD3_ALLOCSIZE;
+ stream->whole_target.inst_alloc = XD3_ALLOCSIZE;
+ stream->whole_target.wininfo_alloc = XD3_ALLOCSIZE;
+
+ if ((stream->whole_target.adds = (uint8_t*)
+ xd3_alloc (stream, stream->whole_target.adds_alloc, 1)) == NULL ||
+ (stream->whole_target.inst = (xd3_winst*)
+ xd3_alloc (stream, stream->whole_target.inst_alloc, 1)) == NULL ||
+ (stream->whole_target.wininfo = (xd3_wininfo*)
+ xd3_alloc (stream, stream->whole_target.wininfo_alloc, 1)) == NULL)
+ {
+ return ENOMEM;
+ }
+ return 0;
+}
+
+static void
+xd3_swap_whole_state (xd3_whole_state *a,
+ xd3_whole_state *b)
+{
+ xd3_whole_state tmp;
+ XD3_ASSERT (a->inst != NULL && a->adds != NULL);
+ XD3_ASSERT (b->inst != NULL && b->adds != NULL);
+ XD3_ASSERT (b->wininfo != NULL && b->wininfo != NULL);
+ memcpy (&tmp, a, sizeof (xd3_whole_state));
+ memcpy (a, b, sizeof (xd3_whole_state));
+ memcpy (b, &tmp, sizeof (xd3_whole_state));
+}
+
+static int
+xd3_realloc_buffer (xd3_stream *stream,
+ usize_t current_units,
+ usize_t unit_size,
+ usize_t new_units,
+ usize_t *alloc_size,
+ void **alloc_ptr)
+{
+ usize_t needed;
+ usize_t new_alloc;
+ usize_t cur_size;
+ uint8_t *new_buf;
+
+ needed = (current_units + new_units) * unit_size;
+
+ if (needed <= *alloc_size)
+ {
+ return 0;
+ }
+
+ cur_size = current_units * unit_size;
+ new_alloc = xd3_round_blksize (needed * 2, XD3_ALLOCSIZE);
+
+ if ((new_buf = (uint8_t*) xd3_alloc (stream, new_alloc, 1)) == NULL)
+ {
+ return ENOMEM;
+ }
+
+ if (cur_size != 0)
+ {
+ memcpy (new_buf, *alloc_ptr, cur_size);
+ }
+
+ if (*alloc_ptr != NULL)
+ {
+ xd3_free (stream, *alloc_ptr);
+ }
+
+ *alloc_size = new_alloc;
+ *alloc_ptr = new_buf;
+
+ return 0;
+}
+
+/* allocate one new output instruction */
+static int
+xd3_whole_alloc_winst (xd3_stream *stream,
+ xd3_winst **winstp)
+{
+ int ret;
+
+ if ((ret = xd3_realloc_buffer (stream,
+ stream->whole_target.instlen,
+ sizeof (xd3_winst),
+ 1,
+ & stream->whole_target.inst_alloc,
+ (void**) & stream->whole_target.inst)))
+ {
+ return ret;
+ }
+
+ *winstp = &stream->whole_target.inst[stream->whole_target.instlen++];
+
+ return 0;
+}
+
+static int
+xd3_whole_alloc_adds (xd3_stream *stream,
+ usize_t count)
+{
+ return xd3_realloc_buffer (stream,
+ stream->whole_target.addslen,
+ 1,
+ count,
+ & stream->whole_target.adds_alloc,
+ (void**) & stream->whole_target.adds);
+}
+
+static int
+xd3_whole_alloc_wininfo (xd3_stream *stream,
+ xd3_wininfo **wininfop)
+{
+ int ret;
+
+ if ((ret = xd3_realloc_buffer (stream,
+ stream->whole_target.wininfolen,
+ sizeof (xd3_wininfo),
+ 1,
+ & stream->whole_target.wininfo_alloc,
+ (void**) & stream->whole_target.wininfo)))
+ {
+ return ret;
+ }
+
+ *wininfop = &stream->whole_target.wininfo[stream->whole_target.wininfolen++];
+
+ return 0;
+}
+
+static int
+xd3_whole_append_inst (xd3_stream *stream,
+ xd3_hinst *inst)
+{
+ int ret;
+ xd3_winst *winst;
+
+ if ((ret = xd3_whole_alloc_winst (stream, &winst)))
+ {
+ return ret;
+ }
+
+ winst->type = inst->type;
+ winst->mode = 0;
+ winst->size = inst->size;
+ winst->position = stream->whole_target.length;
+ stream->whole_target.length += inst->size;
+
+ if (((inst->type == XD3_ADD) || (inst->type == XD3_RUN)) &&
+ (ret = xd3_whole_alloc_adds (stream,
+ (inst->type == XD3_RUN ? 1 : inst->size))))
+ {
+ return ret;
+ }
+
+ switch (inst->type)
+ {
+ case XD3_RUN:
+ winst->addr = stream->whole_target.addslen;
+ stream->whole_target.adds[stream->whole_target.addslen++] =
+ *stream->data_sect.buf++;
+ break;
+
+ case XD3_ADD:
+ winst->addr = stream->whole_target.addslen;
+ memcpy (stream->whole_target.adds + stream->whole_target.addslen,
+ stream->data_sect.buf,
+ inst->size);
+ stream->data_sect.buf += inst->size;
+ stream->whole_target.addslen += inst->size;
+ break;
+
+ default:
+ if (inst->addr < stream->dec_cpylen)
+ {
+ winst->mode = SRCORTGT (stream->dec_win_ind);
+ winst->addr = stream->dec_cpyoff + inst->addr;
+ }
+ else
+ {
+ winst->addr = (stream->dec_winstart +
+ inst->addr -
+ stream->dec_cpylen);
+ }
+ break;
+ }
+
+ return 0;
+}
+
+int
+xd3_whole_append_window (xd3_stream *stream)
+{
+ int ret;
+ xd3_wininfo *wininfo;
+
+ if ((ret = xd3_whole_alloc_wininfo (stream, &wininfo))) { return ret; }
+
+ wininfo->length = stream->dec_tgtlen;
+ wininfo->offset = stream->dec_winstart;
+ wininfo->adler32 = stream->dec_adler32;
+
+ while (stream->inst_sect.buf < stream->inst_sect.buf_max)
+ {
+ if ((ret = xd3_decode_instruction (stream)))
+ {
+ return ret;
+ }
+
+ if ((stream->dec_current1.type != XD3_NOOP) &&
+ (ret = xd3_whole_append_inst (stream,
+ & stream->dec_current1)))
+ {
+ return ret;
+ }
+
+ if ((stream->dec_current2.type != XD3_NOOP) &&
+ (ret = xd3_whole_append_inst (stream,
+ & stream->dec_current2)))
+ {
+ return ret;
+ }
+ }
+
+ return 0;
+}
+
+/* xd3_merge_input_output applies *source to *stream, returns the
+ * result in stream. */
+int xd3_merge_input_output (xd3_stream *stream,
+ xd3_whole_state *source)
+{
+ int ret;
+ xd3_stream tmp_stream;
+ memset (& tmp_stream, 0, sizeof (tmp_stream));
+ if ((ret = xd3_config_stream (& tmp_stream, NULL)) ||
+ (ret = xd3_whole_state_init (& tmp_stream)) ||
+ (ret = xd3_merge_inputs (& tmp_stream,
+ source,
+ & stream->whole_target)))
+ {
+ XPR(NT XD3_LIB_ERRMSG (&tmp_stream, ret));
+ return ret;
+ }
+
+ /* the output is in tmp_stream.whole_state, swap into input */
+ xd3_swap_whole_state (& stream->whole_target,
+ & tmp_stream.whole_target);
+ /* total allocation counts are preserved */
+ xd3_free_stream (& tmp_stream);
+ return 0;
+}
+
+static int
+xd3_merge_run (xd3_stream *stream,
+ xd3_whole_state *target,
+ xd3_winst *iinst)
+{
+ int ret;
+ xd3_winst *oinst;
+
+ if ((ret = xd3_whole_alloc_winst (stream, &oinst)) ||
+ (ret = xd3_whole_alloc_adds (stream, 1)))
+ {
+ return ret;
+ }
+
+ oinst->type = iinst->type;
+ oinst->mode = iinst->mode;
+ oinst->size = iinst->size;
+ oinst->addr = stream->whole_target.addslen;
+
+ XD3_ASSERT (stream->whole_target.length == iinst->position);
+ oinst->position = stream->whole_target.length;
+ stream->whole_target.length += iinst->size;
+
+ stream->whole_target.adds[stream->whole_target.addslen++] =
+ target->adds[iinst->addr];
+
+ return 0;
+}
+
+static int
+xd3_merge_add (xd3_stream *stream,
+ xd3_whole_state *target,
+ xd3_winst *iinst)
+{
+ int ret;
+ xd3_winst *oinst;
+
+ if ((ret = xd3_whole_alloc_winst (stream, &oinst)) ||
+ (ret = xd3_whole_alloc_adds (stream, iinst->size)))
+ {
+ return ret;
+ }
+
+ oinst->type = iinst->type;
+ oinst->mode = iinst->mode;
+ oinst->size = iinst->size;
+ oinst->addr = stream->whole_target.addslen;
+
+ XD3_ASSERT (stream->whole_target.length == iinst->position);
+ oinst->position = stream->whole_target.length;
+ stream->whole_target.length += iinst->size;
+
+ memcpy(stream->whole_target.adds + stream->whole_target.addslen,
+ target->adds + iinst->addr,
+ iinst->size);
+
+ stream->whole_target.addslen += iinst->size;
+
+ return 0;
+}
+
+static int
+xd3_merge_target_copy (xd3_stream *stream,
+ xd3_winst *iinst)
+{
+ int ret;
+ xd3_winst *oinst;
+
+ if ((ret = xd3_whole_alloc_winst (stream, &oinst)))
+ {
+ return ret;
+ }
+
+ XD3_ASSERT (stream->whole_target.length == iinst->position);
+
+ memcpy (oinst, iinst, sizeof (*oinst));
+ return 0;
+}
+
+static int
+xd3_merge_find_position (xd3_stream *stream,
+ xd3_whole_state *source,
+ xoff_t address,
+ usize_t *inst_num)
+{
+ usize_t low;
+ usize_t high;
+
+ if (address >= source->length)
+ {
+ stream->msg = "Invalid copy offset in merge";
+ return XD3_INVALID_INPUT;
+ }
+
+ low = 0;
+ high = source->instlen;
+
+ while (low != high)
+ {
+ xoff_t mid_lpos;
+ xoff_t mid_hpos;
+ usize_t mid = low + (high - low) / 2;
+ mid_lpos = source->inst[mid].position;
+
+ if (address < mid_lpos)
+ {
+ high = mid;
+ continue;
+ }
+
+ mid_hpos = mid_lpos + source->inst[mid].size;
+
+ if (address >= mid_hpos)
+ {
+ low = mid + 1;
+ continue;
+ }
+
+ *inst_num = mid;
+ return 0;
+ }
+
+ stream->msg = "Internal error in merge";
+ return XD3_INTERNAL;
+}
+
+static int
+xd3_merge_source_copy (xd3_stream *stream,
+ xd3_whole_state *source,
+ const xd3_winst *iinst_orig)
+{
+ int ret;
+ xd3_winst iinst;
+ usize_t sinst_num;
+
+ memcpy (& iinst, iinst_orig, sizeof (iinst));
+
+ XD3_ASSERT (iinst.mode == VCD_SOURCE);
+
+ if ((ret = xd3_merge_find_position (stream, source,
+ iinst.addr, &sinst_num)))
+ {
+ return ret;
+ }
+
+ while (iinst.size > 0)
+ {
+ xd3_winst *sinst;
+ xd3_winst *minst;
+ usize_t sinst_offset;
+ usize_t sinst_left;
+ usize_t this_take;
+
+ XD3_ASSERT (sinst_num < source->instlen);
+
+ sinst = &source->inst[sinst_num];
+
+ XD3_ASSERT (iinst.addr >= sinst->position);
+
+ sinst_offset = iinst.addr - sinst->position;
+
+ XD3_ASSERT (sinst->size > sinst_offset);
+
+ sinst_left = sinst->size - sinst_offset;
+ this_take = min (iinst.size, sinst_left);
+
+ XD3_ASSERT (this_take > 0);
+
+ if ((ret = xd3_whole_alloc_winst (stream, &minst)))
+ {
+ return ret;
+ }
+
+ minst->size = this_take;
+ minst->type = sinst->type;
+ minst->position = iinst.position;
+ minst->mode = 0;
+
+ switch (sinst->type)
+ {
+ case XD3_RUN:
+ if ((ret = xd3_whole_alloc_adds (stream, 1)))
+ {
+ return ret;
+ }
+
+ minst->addr = stream->whole_target.addslen;
+ stream->whole_target.adds[stream->whole_target.addslen++] =
+ source->adds[sinst->addr];
+ break;
+ case XD3_ADD:
+ if ((ret = xd3_whole_alloc_adds (stream, this_take)))
+ {
+ return ret;
+ }
+
+ minst->addr = stream->whole_target.addslen;
+ memcpy(stream->whole_target.adds + stream->whole_target.addslen,
+ source->adds + sinst->addr + sinst_offset,
+ this_take);
+ stream->whole_target.addslen += this_take;
+ break;
+ default:
+ if (sinst->mode != 0)
+ {
+ minst->mode = sinst->mode;
+ minst->addr = sinst->addr + sinst_offset;
+ }
+ else
+ {
+ // TODO: this is slow because of the recursion, which
+ // could reach a depth equal to the number of target
+ // copies, and this is compression-inefficient because
+ // it can produce duplicate adds.
+ xd3_winst tinst;
+ tinst.type = XD3_CPY;
+ tinst.mode = iinst.mode;
+ tinst.addr = sinst->addr + sinst_offset;
+ tinst.size = this_take;
+ tinst.position = iinst.position;
+
+ // The instruction allocated in this frame will not be used.
+ stream->whole_target.instlen -= 1;
+
+ if ((ret = xd3_merge_source_copy (stream, source, &tinst)))
+ {
+ return ret;
+ }
+ }
+ break;
+ }
+
+ iinst.position += this_take;
+ iinst.addr += this_take;
+ iinst.size -= this_take;
+ sinst_num += 1;
+ }
+
+ return 0;
+}
+
+/* xd3_merge_inputs() applies *input to *source, returns its result in
+ * stream. */
+int xd3_merge_inputs (xd3_stream *stream,
+ xd3_whole_state *source,
+ xd3_whole_state *input)
+{
+ int ret = 0;
+ usize_t i;
+ size_t input_i;
+
+ for (i = 0; i < input->wininfolen; ++i) {
+ xd3_wininfo *copyinfo;
+
+ if ((ret = xd3_whole_alloc_wininfo (stream, &copyinfo))) { return ret; }
+
+ *copyinfo = input->wininfo[i];
+ }
+
+ /* iterate over each instruction. */
+ for (input_i = 0; ret == 0 && input_i < input->instlen; ++input_i)
+ {
+ xd3_winst *iinst = &input->inst[input_i];
+
+ switch (iinst->type)
+ {
+ case XD3_RUN:
+ ret = xd3_merge_run (stream, input, iinst);
+ break;
+ case XD3_ADD:
+ ret = xd3_merge_add (stream, input, iinst);
+ break;
+ default:
+ /* TODO: VCD_TARGET support is completely untested all
+ * throughout. */
+ if (iinst->mode == 0 || iinst->mode == VCD_TARGET)
+ {
+ ret = xd3_merge_target_copy (stream, iinst);
+ }
+ else
+ {
+ ret = xd3_merge_source_copy (stream, source, iinst);
+ }
+
+ /* The whole_target.length is not updated in the xd3_merge*copy
+ * routine because of recursion in xd3_merge_source_copy. */
+ stream->whole_target.length += iinst->size;
+ break;
+ }
+ }
+
+ return ret;
+}
+
+#endif
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-19 04:01:59 +0000