root/vowfsc/xdelta3-decode.h

/* xdelta 3 - delta compression tools and library
 * Copyright (C) 2002, 2003, 2004, 2005, 2006, 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_DECODE_H_
#define _XDELTA3_DECODE_H_


/* Return true if the caller must provide a source.  Theoretically, this has to be checked
 * after every window.  It could be that the first window requires no source, but the
 * second window does.  In practice? */
int xd3_decoder_needs_source (xd3_stream *stream)
{
  return stream->dec_win_ind & VCD_SOURCE;
}

/* Initialize the decoder for a new window.  The dec_tgtlen value is preserved across
 * successive window decodings, and the update to dec_winstart is delayed until a new
 * window actually starts.  This is to avoid throwing an error due to overflow until the
 * last possible moment.  This makes it possible to encode exactly 4GB through a 32-bit
 * encoder. */
static int
xd3_decode_init_window (xd3_stream *stream)
{
  stream->dec_cpylen = 0;
  stream->dec_cpyoff = 0;
  stream->dec_cksumbytes = 0;

  xd3_init_cache (& stream->acache);

  return 0;
}

/* Allocates buffer space for the target window and possibly the VCD_TARGET copy-window.
 * Also sets the base of the two copy segments. */
static int
xd3_decode_setup_buffers (xd3_stream *stream)
{
  /* If VCD_TARGET is set then the previous buffer may be reused. */
  if (stream->dec_win_ind & VCD_TARGET)
    {
      /* But this implementation only supports copying from the last target window.  If the
       * offset is outside that range, it can't be done. */
      if (stream->dec_cpyoff < stream->dec_laststart)
        {
          stream->msg = "unsupported VCD_TARGET offset";
          return XD3_INVALID_INPUT;
        }

      /* See if the two windows are the same.  This indicates the first time VCD_TARGET is
       * used.  This causes a second buffer to be allocated, after that the two are
       * swapped in the DEC_FINISH case. */
      if (stream->dec_lastwin == stream->next_out)
        {
          stream->next_out  = NULL;
          stream->space_out = 0;
        }

      stream->dec_cpyaddrbase = stream->dec_lastwin + (usize_t) (stream->dec_cpyoff - stream->dec_laststart);
    }

  /* See if the current output window is large enough. */
  if (stream->space_out < stream->dec_tgtlen)
    {
      xd3_free (stream, stream->dec_buffer);

      stream->space_out = xd3_round_blksize (stream->dec_tgtlen, XD3_ALLOCSIZE);

      if ((stream->dec_buffer = xd3_alloc (stream, stream->space_out, 1)) == NULL)
        {
          return ENOMEM;
        }

      stream->next_out = stream->dec_buffer;
    }

  /* dec_tgtaddrbase refers to an invalid base address, but it is always used with a
   * sufficiently large instruction offset (i.e., beyond the copy window).  This condition
   * is enforced by xd3_decode_output_halfinst. */
  stream->dec_tgtaddrbase = stream->next_out - stream->dec_cpylen;

  return 0;
}

static int
xd3_decode_allocate (xd3_stream  *stream,
                     usize_t       size,
                     uint8_t    **buf_ptr,
                     usize_t      *buf_alloc)
{
  if (*buf_ptr != NULL && *buf_alloc < size)
    {
      xd3_free (stream, *buf_ptr);
      *buf_ptr = NULL;
    }

  if (*buf_ptr == NULL)
    {
      *buf_alloc = xd3_round_blksize (size, XD3_ALLOCSIZE);

      if ((*buf_ptr = xd3_alloc (stream, *buf_alloc, 1)) == NULL)
        {
          return ENOMEM;
        }
    }

  return 0;
}

static int
xd3_decode_section (xd3_stream *stream,
                    xd3_desect *section,
                    xd3_decode_state nstate,
                    int copy)
{
  XD3_ASSERT (section->pos <= section->size);
  XD3_ASSERT (stream->dec_state != nstate);

  if (section->pos < section->size)
    {
      usize_t sect_take;

      if (stream->avail_in == 0)
        {
          return XD3_INPUT;
        }

      if ((copy == 0) && (section->pos == 0))
        {
          /* No allocation/copy needed */
          section->buf = stream->next_in;
          sect_take    = section->size;
        }
      else
        {
          usize_t sect_need = section->size - section->pos;

          /* Allocate and copy */
          sect_take = min (sect_need, stream->avail_in);

          if (section->pos == 0)
            {
              int ret;

              if ((ret = xd3_decode_allocate (stream,
                                              section->size,
                                              & section->copied1,
                                              & section->alloc1))) { return ret; }

              section->buf = section->copied1;
            }

          memcpy (section->copied1 + section->pos,
                  stream->next_in,
                  sect_take);
        }

      section->pos += sect_take;

      stream->dec_winbytes += sect_take;

      DECODE_INPUT (sect_take);
    }

  if (section->pos < section->size)
    {
      stream->msg = "further input required";
      return XD3_INPUT;
    }

  XD3_ASSERT (section->pos == section->size);

  stream->dec_state = nstate;
  section->buf_max  = section->buf + section->size;
  section->pos      = 0;
  return 0;
}

/* Decode the size and address for half of an instruction (i.e., a single opcode).  This
 * updates the stream->dec_position, which are bytes already output prior to processing
 * this instruction.  Perform bounds checking for sizes and copy addresses, which uses the
 * dec_position (which is why these checks are done here). */
static int
xd3_decode_parse_halfinst (xd3_stream *stream, xd3_hinst *inst)
{
  int ret;

  /* If the size from the instruction table is zero then read a size value. */
  if ((inst->size == 0) &&
      (ret = xd3_read_size (stream,
                            & stream->inst_sect.buf,
                              stream->inst_sect.buf_max,
                            & inst->size)))
    {
      return XD3_INVALID_INPUT;
    }

  /* For copy instructions, read address. */
  if (inst->type >= XD3_CPY)
    {
      IF_DEBUG1 ({
        static int cnt = 0;
        DP(RINT "DECODE:%u: COPY at %"Q"u (winoffset %u) size %u winaddr %u\n",
                 cnt++,
                 stream->total_out + (stream->dec_position - stream->dec_cpylen),
                 (stream->dec_position - stream->dec_cpylen),
                 inst->size,
                 inst->addr);
      });

      if ((ret = xd3_decode_address (stream,
                                     stream->dec_position,
                                     inst->type - XD3_CPY,
                                     & stream->addr_sect.buf,
                                     stream->addr_sect.buf_max,
                                     & inst->addr)))
        {
          return ret;
        }

      /* Cannot copy an address before it is filled-in. */
      if (inst->addr >= stream->dec_position)
        {
          stream->msg = "address too large";
          return XD3_INVALID_INPUT;
        }

      /* Check: a VCD_TARGET or VCD_SOURCE copy cannot exceed the remaining buffer space
       * in its own segment. */
      if (inst->addr < stream->dec_cpylen && inst->addr + inst->size > stream->dec_cpylen)
        {
          stream->msg = "size too large";
          return XD3_INVALID_INPUT;
        }
    }
  else
    {
      IF_DEBUG1 ({
        if (inst->type == XD3_ADD)
          {
            static int cnt;
            DP(RINT "DECODE:%d: ADD at %"Q"u (winoffset %u) size %u\n",
                     cnt++,
                     stream->total_out + stream->dec_position - stream->dec_cpylen,
                     stream->dec_position - stream->dec_cpylen,
                     inst->size);
          }
        else
          {
            static int cnt;
            XD3_ASSERT (inst->type == XD3_RUN);
            DP(RINT "DECODE:%d: RUN at %"Q"u (winoffset %u) size %u\n",
                     cnt++,
                     stream->total_out + stream->dec_position - stream->dec_cpylen,
                     stream->dec_position - stream->dec_cpylen,
                     inst->size);
          }
      });
    }

  /* Check: The instruction will not overflow the output buffer. */
  if (stream->dec_position + inst->size > stream->dec_maxpos)
    {
      stream->msg = "size too large";
      return XD3_INVALID_INPUT;
    }

  stream->dec_position += inst->size;
  return 0;
}

/* Decode a single opcode and then decode the two half-instructions. */
static int
xd3_decode_instruction (xd3_stream *stream)
{
  int ret;
  const xd3_dinst *inst;

  if (stream->inst_sect.buf == stream->inst_sect.buf_max)
    {
      stream->msg = "instruction underflow";
      return XD3_INVALID_INPUT;
    }

  inst = &stream->code_table[*stream->inst_sect.buf++];

  stream->dec_current1.type = inst->type1;
  stream->dec_current2.type = inst->type2;
  stream->dec_current1.size = inst->size1;
  stream->dec_current2.size = inst->size2;

  /* For each instruction with a real operation, decode the corresponding size and
   * addresses if necessary.  Assume a code-table may have NOOP in either position,
   * although this is unlikely. */
  if (inst->type1 != XD3_NOOP && (ret = xd3_decode_parse_halfinst (stream, & stream->dec_current1)))
    {
      return ret;
    }
  if (inst->type2 != XD3_NOOP && (ret = xd3_decode_parse_halfinst (stream, & stream->dec_current2)))
    {
      return ret;
    }
  return 0;
}

/* Output the result of a single half-instruction. OPT: This the decoder hotspot. */
static int
xd3_decode_output_halfinst (xd3_stream *stream, xd3_hinst *inst)
{
  /* To make this reentrant, set take = min (inst->size, available space)... */
  usize_t take = inst->size;

  XD3_ASSERT (inst->type != XD3_NOOP);

  switch (inst->type)
    {
    case XD3_RUN:
      {
        /* Only require a single data byte. */
        if (stream->data_sect.buf == stream->data_sect.buf_max)
          {
            stream->msg = "data underflow";
            return XD3_INVALID_INPUT;
          }

        memset (stream->next_out + stream->avail_out,
                stream->data_sect.buf[0],
                take);

        stream->data_sect.buf += 1;
        stream->avail_out += take;
        inst->type = XD3_NOOP;
        break;
      }
    case XD3_ADD:
      {
        /* Require at least TAKE data bytes. */
        if (stream->data_sect.buf + take > stream->data_sect.buf_max)
          {
            stream->msg = "data underflow";
            return XD3_INVALID_INPUT;
          }

        memcpy (stream->next_out + stream->avail_out,
                stream->data_sect.buf,
                take);

        stream->data_sect.buf += take;
        stream->avail_out += take;
        inst->type = XD3_NOOP;
        break;
      }
    default:
      {
        usize_t i;
        const uint8_t *src;
        uint8_t *dst;

        /* See if it copies from the VCD_TARGET/VCD_SOURCE window or the target window.
         * Out-of-bounds checks for the addresses and sizes are performed in
         * xd3_decode_parse_halfinst. */
        if (inst->addr < stream->dec_cpylen)
          {
            if (stream->dec_win_ind & VCD_TARGET)
              {
                /* For VCD_TARGET we know the entire range is in-memory, as established by
                 * decode_setup_buffers. */
                src = stream->dec_cpyaddrbase + inst->addr;
                inst->type = XD3_NOOP;
                inst->size = 0;
              }
            else
              {
                /* In this case we have to read a source block, which could return control
                 * to the caller.  We need to know the first block number needed for this
                 * copy. */
                xd3_source *source;
                xoff_t block;
                usize_t blkoff;
                usize_t blksize;
                int ret;

              more:

                source  = stream->src;
                block   = source->cpyoff_blocks;
                blkoff  = source->cpyoff_blkoff + inst->addr;
                blksize = source->blksize;

                while (blkoff >= blksize)
                  {
                    block  += 1;
                    blkoff -= blksize;
                  }

                if ((ret = xd3_getblk (stream, block)))
                  {
                    /* could be a XD3_GETSRCBLK failure. */
                    if (ret == XD3_TOOFARBACK)
                      {
                        ret = XD3_INTERNAL;
                      }
                    return ret;
                  }

                src = source->curblk + blkoff;

                /* This block either contains enough data or the source file is
                 * short. */
                if ((source->onblk != blksize) && (blkoff + take > source->onblk))
                  {
                    stream->msg = "source file too short";
                    return XD3_INVALID_INPUT;

                  }

                XD3_ASSERT (blkoff != blksize);

                if (blkoff + take <= blksize)
                  {
                    inst->type = XD3_NOOP;
                    inst->size = 0;
                  }
                else
                  {
                    /* This block doesn't contain all the data, modify the instruction, do
                     * not set to XD3_NOOP. */
                    take = blksize - blkoff;
                    inst->size -= take;
                    inst->addr += take;
                  }
              }
          }
        else
          {
            /* For a target-window copy, we know the entire range is in-memory.  The
             * dec_tgtaddrbase is negatively offset by dec_cpylen because the addresses
             * start beyond that point. */
            src = stream->dec_tgtaddrbase + inst->addr;
            inst->type = XD3_NOOP;
            inst->size = 0;
          }

        dst = stream->next_out + stream->avail_out;

        stream->avail_out += take;

        /* Can't just memcpy here due to possible overlap. */
        for (i = take; i != 0; i -= 1)
          {
            *dst++ = *src++;
          }

        take = inst->size;

        /* If there is more to copy, call getblk again. */
        if (inst->type != XD3_NOOP)
          {
            XD3_ASSERT (take > 0);
            goto more;
          }
        else
          {
            XD3_ASSERT (take == 0);
          }
      }
    }

  return 0;
}

static int
xd3_decode_finish_window (xd3_stream *stream)
{
  stream->dec_winbytes  = 0;
  stream->dec_state     = DEC_FINISH;

  stream->data_sect.pos = 0;
  stream->inst_sect.pos = 0;
  stream->addr_sect.pos = 0;

  return XD3_OUTPUT;
}

static int
xd3_decode_secondary_sections (xd3_stream *secondary_stream)
{
#if SECONDARY_ANY
  int ret;
#define DECODE_SECONDARY_SECTION(UPPER,LOWER) \
  ((secondary_stream->dec_del_ind & VCD_ ## UPPER ## COMP) && \
   (ret = xd3_decode_secondary (secondary_stream, & secondary_stream-> LOWER ## _sect, \
                                        & xd3_sec_ ## LOWER (secondary_stream))))

  if (DECODE_SECONDARY_SECTION (DATA, data) ||
      DECODE_SECONDARY_SECTION (INST, inst) ||
      DECODE_SECONDARY_SECTION (ADDR, addr))
    {
      return ret;
    }
#undef DECODE_SECONDARY_SECTION
#endif
  return 0;
}

static int
xd3_decode_sections (xd3_stream *stream)
{
  usize_t need, more, take;
  int copy, ret;

  if ((stream->flags & XD3_JUST_HDR) != 0)
    {
      /* Nothing left to do. */
      return xd3_decode_finish_window (stream);
    }

  /* To avoid copying, need this much data available */
  need = (stream->inst_sect.size +
          stream->addr_sect.size +
          stream->data_sect.size);

  /* The window may be entirely processed. */
  XD3_ASSERT (stream->dec_winbytes <= need);

  /* Compute how much more input is needed. */
  more = (need - stream->dec_winbytes);

  /* How much to consume. */
  take = min (more, stream->avail_in);

  /* See if the input is completely available, to avoid copy. */
  copy = (take != more);

  /* If the window is skipped... */
  if ((stream->flags & XD3_SKIP_WINDOW) != 0)
    {
      /* Skip the available input. */
      DECODE_INPUT (take);

      stream->dec_winbytes += take;

      if (copy)
        {
          stream->msg = "further input required";
          return XD3_INPUT;
        }

      return xd3_decode_finish_window (stream);
    }

  /* Process all but the DATA section. */
  switch (stream->dec_state)
    {
    default:
      stream->msg = "internal error";
      return XD3_INVALID_INPUT;

    case DEC_DATA:
      if ((ret = xd3_decode_section (stream, & stream->data_sect, DEC_INST, copy))) { return ret; }
    case DEC_INST:
      if ((ret =