Logo Search packages:      
Sourcecode: xdelta3 version File versions  Download package

xdelta3-merge.h

/* 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  Doxygen 1.6.0   Back to index