"Fossies" - the Fresh Open Source Software Archive

Member "xdelta3-3.1.0/xdelta3-decode.h" (5 Jan 2016, 33197 Bytes) of package /linux/misc/xdelta3-3.1.0.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-decode.h" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 3.0.11_vs_3.1.0.

    1 /* xdelta 3 - delta compression tools and library
    2  * Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
    3  * 2011, 2012, 2013, 2014, 2015.  Joshua P. MacDonald
    4  *
    5  *  This program is free software; you can redistribute it and/or modify
    6  *  it under the terms of the GNU General Public License as published by
    7  *  the Free Software Foundation; either version 2 of the License, or
    8  *  (at your option) any later version.
    9  *
   10  *  This program is distributed in the hope that it will be useful,
   11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
   12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   13  *  GNU General Public License for more details.
   14  *
   15  *  You should have received a copy of the GNU General Public License
   16  *  along with this program; if not, write to the Free Software
   17  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
   18  */
   19 
   20 #ifndef _XDELTA3_DECODE_H_
   21 #define _XDELTA3_DECODE_H_
   22 
   23 #include "xdelta3-internal.h"
   24 
   25 #define SRCORTGT(x) ((((x) & VCD_SRCORTGT) == VCD_SOURCE) ? \
   26                      VCD_SOURCE : ((((x) & VCD_SRCORTGT) == \
   27                                     VCD_TARGET) ? VCD_TARGET : 0))
   28 
   29 static inline int
   30 xd3_decode_byte (xd3_stream *stream, usize_t *val)
   31 {
   32   if (stream->avail_in == 0)
   33     {
   34       stream->msg = "further input required";
   35       return XD3_INPUT;
   36     }
   37 
   38   (*val) = stream->next_in[0];
   39 
   40   DECODE_INPUT (1);
   41   return 0;
   42 }
   43 
   44 static inline int
   45 xd3_decode_bytes (xd3_stream *stream, uint8_t *buf, usize_t *pos, usize_t size)
   46 {
   47   usize_t want;
   48   usize_t take;
   49 
   50   /* Note: The case where (*pos == size) happens when a zero-length
   51    * appheader or code table is transmitted, but there is nothing in
   52    * the standard against that. */
   53   while (*pos < size)
   54     {
   55       if (stream->avail_in == 0)
   56     {
   57       stream->msg = "further input required";
   58       return XD3_INPUT;
   59     }
   60 
   61       want = size - *pos;
   62       take = xd3_min (want, stream->avail_in);
   63 
   64       memcpy (buf + *pos, stream->next_in, (size_t) take);
   65 
   66       DECODE_INPUT (take);
   67       (*pos) += take;
   68     }
   69 
   70   return 0;
   71 }
   72 
   73 /* Initialize the decoder for a new window.  The dec_tgtlen value is
   74  * preserved across successive window decodings, and the update to
   75  * dec_winstart is delayed until a new window actually starts.  This
   76  * is to avoid throwing an error due to overflow until the last
   77  * possible moment.  This makes it possible to encode exactly 4GB
   78  * through a 32-bit encoder. */
   79 static int
   80 xd3_decode_init_window (xd3_stream *stream)
   81 {
   82   stream->dec_cpylen = 0;
   83   stream->dec_cpyoff = 0;
   84   stream->dec_cksumbytes = 0;
   85 
   86   xd3_init_cache (& stream->acache);
   87 
   88   return 0;
   89 }
   90 
   91 /* Allocates buffer space for the target window and possibly the
   92  * VCD_TARGET copy-window.  Also sets the base of the two copy
   93  * segments. */
   94 static int
   95 xd3_decode_setup_buffers (xd3_stream *stream)
   96 {
   97   /* If VCD_TARGET is set then the previous buffer may be reused. */
   98   if (stream->dec_win_ind & VCD_TARGET)
   99     {
  100       /* Note: this implementation is untested, since Xdelta3 itself
  101        * does not implement an encoder for VCD_TARGET mode. Thus, mark
  102        * unimplemented until needed. */
  103       if (1)
  104     {
  105       stream->msg = "VCD_TARGET not implemented";
  106       return XD3_UNIMPLEMENTED;
  107     }
  108 
  109       /* But this implementation only supports copying from the last
  110        * target window.  If the offset is outside that range, it can't
  111        * be done. */
  112       if (stream->dec_cpyoff < stream->dec_laststart)
  113     {
  114       stream->msg = "unsupported VCD_TARGET offset";
  115       return XD3_INVALID_INPUT;
  116     }
  117 
  118       /* See if the two windows are the same.  This indicates the
  119        * first time VCD_TARGET is used.  This causes a second buffer
  120        * to be allocated, after that the two are swapped in the
  121        * DEC_FINISH case. */
  122       if (stream->dec_lastwin == stream->next_out)
  123     {
  124       stream->next_out  = NULL;
  125       stream->space_out = 0;
  126     }
  127 
  128       /* TODO: (See note above, this looks incorrect) */
  129       stream->dec_cpyaddrbase = stream->dec_lastwin +
  130     (usize_t) (stream->dec_cpyoff - stream->dec_laststart);
  131     }
  132 
  133   /* See if the current output window is large enough. */
  134   if (stream->space_out < stream->dec_tgtlen)
  135     {
  136       xd3_free (stream, stream->dec_buffer);
  137 
  138       stream->space_out =
  139     xd3_round_blksize (stream->dec_tgtlen, XD3_ALLOCSIZE);
  140 
  141       if ((stream->dec_buffer =
  142        (uint8_t*) xd3_alloc (stream, stream->space_out, 1)) == NULL)
  143     {
  144       return ENOMEM;
  145     }
  146 
  147       stream->next_out = stream->dec_buffer;
  148     }
  149 
  150   /* dec_tgtaddrbase refers to an invalid base address, but it is
  151    * always used with a sufficiently large instruction offset (i.e.,
  152    * beyond the copy window).  This condition is enforced by
  153    * xd3_decode_output_halfinst. */
  154   stream->dec_tgtaddrbase = stream->next_out - stream->dec_cpylen;
  155 
  156   return 0;
  157 }
  158 
  159 static int
  160 xd3_decode_allocate (xd3_stream  *stream,
  161              usize_t       size,
  162              uint8_t    **buf_ptr,
  163              usize_t      *buf_alloc)
  164 {
  165   IF_DEBUG2 (DP(RINT "[xd3_decode_allocate] size %"W"u alloc %"W"u\n",
  166         size, *buf_alloc));
  167   
  168   if (*buf_ptr != NULL && *buf_alloc < size)
  169     {
  170       xd3_free (stream, *buf_ptr);
  171       *buf_ptr = NULL;
  172     }
  173 
  174   if (*buf_ptr == NULL)
  175     {
  176       *buf_alloc = xd3_round_blksize (size, XD3_ALLOCSIZE);
  177 
  178       if ((*buf_ptr = (uint8_t*) xd3_alloc (stream, *buf_alloc, 1)) == NULL)
  179     {
  180       return ENOMEM;
  181     }
  182     }
  183 
  184   return 0;
  185 }
  186 
  187 static int
  188 xd3_decode_section (xd3_stream *stream,
  189             xd3_desect *section,
  190             xd3_decode_state nstate,
  191             int copy)
  192 {
  193   XD3_ASSERT (section->pos <= section->size);
  194   XD3_ASSERT (stream->dec_state != nstate);
  195 
  196   if (section->pos < section->size)
  197     {
  198       usize_t sect_take;
  199 
  200       if (stream->avail_in == 0)
  201     {
  202       return XD3_INPUT;
  203     }
  204 
  205       if ((copy == 0) && (section->pos == 0))
  206     {
  207       /* No allocation/copy needed */
  208       section->buf = stream->next_in;
  209       sect_take    = section->size;
  210       IF_DEBUG1 (DP(RINT "[xd3_decode_section] zerocopy %"W"u @ %"W"u avail %"W"u\n",
  211             sect_take, section->pos, stream->avail_in));
  212     }
  213       else
  214     {
  215       usize_t sect_need = section->size - section->pos;
  216 
  217       /* Allocate and copy */
  218       sect_take = xd3_min (sect_need, stream->avail_in);
  219 
  220       if (section->pos == 0)
  221         {
  222           int ret;
  223 
  224           if ((ret = xd3_decode_allocate (stream,
  225                           section->size,
  226                           & section->copied1,
  227                           & section->alloc1)))
  228         {
  229           return ret;
  230         }
  231 
  232           section->buf = section->copied1;
  233         }
  234 
  235       IF_DEBUG2 (DP(RINT "[xd3_decode_section] take %"W"u @ %"W"u [need %"W"u] avail %"W"u\n",
  236             sect_take, section->pos, sect_need, stream->avail_in));
  237       XD3_ASSERT (section->pos + sect_take <= section->alloc1);
  238 
  239       memcpy (section->copied1 + section->pos,
  240           stream->next_in,
  241           sect_take);
  242     }
  243 
  244       section->pos += sect_take;
  245 
  246       stream->dec_winbytes += sect_take;
  247 
  248       DECODE_INPUT (sect_take);
  249     }
  250 
  251   if (section->pos < section->size)
  252     {
  253       IF_DEBUG1 (DP(RINT "[xd3_decode_section] further input required %"W"u\n",
  254             section->size - section->pos));
  255       stream->msg = "further input required";
  256       return XD3_INPUT;
  257     }
  258 
  259   XD3_ASSERT (section->pos == section->size);
  260 
  261   stream->dec_state = nstate;
  262   section->buf_max  = section->buf + section->size;
  263   section->pos      = 0;
  264   return 0;
  265 }
  266 
  267 /* Decode the size and address for half of an instruction (i.e., a
  268  * single opcode).  This updates the stream->dec_position, which are
  269  * bytes already output prior to processing this instruction.  Perform
  270  * bounds checking for sizes and copy addresses, which uses the
  271  * dec_position (which is why these checks are done here). */
  272 static int
  273 xd3_decode_parse_halfinst (xd3_stream *stream, xd3_hinst *inst)
  274 {
  275   int ret;
  276 
  277   /* If the size from the instruction table is zero then read a size value. */
  278   if ((inst->size == 0) &&
  279       (ret = xd3_read_size (stream,
  280                 & stream->inst_sect.buf,
  281                   stream->inst_sect.buf_max,
  282                 & inst->size)))
  283     {
  284       return XD3_INVALID_INPUT;
  285     }
  286 
  287   /* For copy instructions, read address. */
  288   if (inst->type >= XD3_CPY)
  289     {
  290       IF_DEBUG2 ({
  291     static int cnt = 0;
  292     XPR(NT "DECODE:%u: COPY at %"Q"u (winoffset %"W"u) "
  293         "size %"W"u winaddr %"W"u\n",
  294         cnt++,
  295         stream->total_out + (stream->dec_position -
  296                  stream->dec_cpylen),
  297         (stream->dec_position - stream->dec_cpylen),
  298         inst->size,
  299         inst->addr);
  300       });
  301 
  302       if ((ret = xd3_decode_address (stream,
  303                      stream->dec_position,
  304                      inst->type - XD3_CPY,
  305                      & stream->addr_sect.buf,
  306                      stream->addr_sect.buf_max,
  307                      & inst->addr)))
  308     {
  309       return ret;
  310     }
  311 
  312       /* Cannot copy an address before it is filled-in. */
  313       if (inst->addr >= stream->dec_position)
  314     {
  315       stream->msg = "address too large";
  316       return XD3_INVALID_INPUT;
  317     }
  318 
  319       /* Check: a VCD_TARGET or VCD_SOURCE copy cannot exceed the remaining
  320        * buffer space in its own segment. */
  321       if (inst->addr < stream->dec_cpylen &&
  322       inst->addr + inst->size > stream->dec_cpylen)
  323     {
  324       stream->msg = "size too large";
  325       return XD3_INVALID_INPUT;
  326     }
  327     }
  328   else
  329     {
  330       IF_DEBUG2 ({
  331     if (inst->type == XD3_ADD)
  332       {
  333         static int cnt;
  334         XPR(NT "DECODE:%d: ADD at %"Q"u (winoffset %"W"u) size %"W"u\n",
  335            cnt++,
  336            (stream->total_out + stream->dec_position - stream->dec_cpylen),
  337            stream->dec_position - stream->dec_cpylen,
  338            inst->size);
  339       }
  340     else
  341       {
  342         static int cnt;
  343         XD3_ASSERT (inst->type == XD3_RUN);
  344         XPR(NT "DECODE:%d: RUN at %"Q"u (winoffset %"W"u) size %"W"u\n",
  345            cnt++,
  346            stream->total_out + stream->dec_position - stream->dec_cpylen,
  347            stream->dec_position - stream->dec_cpylen,
  348            inst->size);
  349       }
  350       });
  351     }
  352 
  353   /* Check: The instruction will not overflow the output buffer. */
  354   if (stream->dec_position + inst->size > stream->dec_maxpos)
  355     {
  356       stream->msg = "size too large";
  357       return XD3_INVALID_INPUT;
  358     }
  359 
  360   stream->dec_position += inst->size;
  361   return 0;
  362 }
  363 
  364 /* Decode a single opcode and then decode the two half-instructions. */
  365 static int
  366 xd3_decode_instruction (xd3_stream *stream)
  367 {
  368   int ret;
  369   const xd3_dinst *inst;
  370 
  371   if (stream->inst_sect.buf == stream->inst_sect.buf_max)
  372     {
  373       stream->msg = "instruction underflow";
  374       return XD3_INVALID_INPUT;
  375     }
  376 
  377   inst = &stream->code_table[*stream->inst_sect.buf++];
  378 
  379   stream->dec_current1.type = inst->type1;
  380   stream->dec_current2.type = inst->type2;
  381   stream->dec_current1.size = inst->size1;
  382   stream->dec_current2.size = inst->size2;
  383 
  384   /* For each instruction with a real operation, decode the
  385    * corresponding size and addresses if necessary.  Assume a
  386    * code-table may have NOOP in either position, although this is
  387    * unlikely. */
  388   if (inst->type1 != XD3_NOOP &&
  389       (ret = xd3_decode_parse_halfinst (stream, & stream->dec_current1)))
  390     {
  391       return ret;
  392     }
  393   if (inst->type2 != XD3_NOOP &&
  394       (ret = xd3_decode_parse_halfinst (stream, & stream->dec_current2)))
  395     {
  396       return ret;
  397     }
  398   return 0;
  399 }
  400 
  401 /* Output the result of a single half-instruction. OPT: This the
  402    decoder hotspot.  Modifies "hinst", see below.  */
  403 static int
  404 xd3_decode_output_halfinst (xd3_stream *stream, xd3_hinst *inst)
  405 {
  406   /* This method is reentrant for copy instructions which may return
  407    * XD3_GETSRCBLK to the caller.  Each time through a copy takes the
  408    * minimum of inst->size and the available space on whichever block
  409    * supplies the data */
  410   usize_t take = inst->size;
  411 
  412   if (USIZE_T_OVERFLOW (stream->avail_out, take) ||
  413       stream->avail_out + take > stream->space_out)
  414     {
  415       stream->msg = "overflow while decoding";
  416       return XD3_INVALID_INPUT;
  417     }
  418 
  419   XD3_ASSERT (inst->type != XD3_NOOP);
  420 
  421   switch (inst->type)
  422     {
  423     case XD3_RUN:
  424       {
  425     /* Only require a single data byte. */
  426     if (stream->data_sect.buf == stream->data_sect.buf_max)
  427       {
  428         stream->msg = "data underflow";
  429         return XD3_INVALID_INPUT;
  430       }
  431 
  432     memset (stream->next_out + stream->avail_out,
  433         stream->data_sect.buf[0],
  434         take);
  435 
  436     stream->data_sect.buf += 1;
  437     stream->avail_out += take;
  438     inst->type = XD3_NOOP;
  439     break;
  440       }
  441     case XD3_ADD:
  442       {
  443     /* Require at least TAKE data bytes. */
  444     if (stream->data_sect.buf + take > stream->data_sect.buf_max)
  445       {
  446         stream->msg = "data underflow";
  447         return XD3_INVALID_INPUT;
  448       }
  449 
  450     memcpy (stream->next_out + stream->avail_out,
  451         stream->data_sect.buf,
  452         take);
  453 
  454     stream->data_sect.buf += take;
  455     stream->avail_out += take;
  456     inst->type = XD3_NOOP;
  457     break;
  458       }
  459     default:
  460       {
  461     usize_t i;
  462     const uint8_t *src;
  463     uint8_t *dst;
  464     int overlap;
  465 
  466     /* See if it copies from the VCD_TARGET/VCD_SOURCE window or
  467      * the target window.  Out-of-bounds checks for the addresses
  468      * and sizes are performed in xd3_decode_parse_halfinst.  This
  469      * if/else must set "overlap", "src", and "dst". */
  470     if (inst->addr < stream->dec_cpylen)
  471       {
  472         /* In both branches we are copying from outside the
  473          * current decoder window, the first (VCD_TARGET) is
  474          * unimplemented. */
  475         overlap = 0;
  476         
  477         /* This branch sets "src".  As a side-effect, we modify
  478          * "inst" so that if we reenter this method after a
  479          * XD3_GETSRCBLK response the state is correct.  So if the
  480          * instruction can be fulfilled by a contiguous block of
  481          * memory then we will set:
  482          *
  483          *  inst->type = XD3_NOOP;
  484          *  inst->size = 0;
  485          */
  486         if (stream->dec_win_ind & VCD_TARGET)
  487           {
  488         /* TODO: Users have requested long-distance copies of
  489          * similar material within a target (e.g., for dup
  490          * supression in backups). This code path is probably
  491          * dead due to XD3_UNIMPLEMENTED in xd3_decode_setup_buffers */
  492         inst->size = 0;
  493         inst->type = XD3_NOOP;
  494         stream->msg = "VCD_TARGET not implemented";
  495         return XD3_UNIMPLEMENTED;
  496           }
  497         else
  498           {
  499         /* In this case we have to read a source block, which
  500          * could return control to the caller.  We need to
  501          * know the first block number needed for this
  502          * copy. */
  503         xd3_source *source = stream->src;
  504         xoff_t block = source->cpyoff_blocks;
  505         usize_t blkoff = source->cpyoff_blkoff;
  506         const usize_t blksize = source->blksize;
  507         int ret;
  508 
  509         xd3_blksize_add (&block, &blkoff, source, inst->addr);
  510         XD3_ASSERT (blkoff < blksize);
  511 
  512         if ((ret = xd3_getblk (stream, block)))
  513           {
  514             /* could be a XD3_GETSRCBLK failure. */
  515             if (ret == XD3_TOOFARBACK)
  516               {
  517             stream->msg = "non-seekable source in decode";
  518             ret = XD3_INTERNAL;
  519               }
  520             return ret;
  521           }
  522 
  523         src = source->curblk + blkoff;
  524 
  525         /* This block is either full, or a partial block that
  526          * must contain enough bytes. */
  527         if ((source->onblk != blksize) &&
  528             (blkoff + take > source->onblk))
  529           {
  530             IF_DEBUG1 (XPR(NT "[srcfile] short at blkno %"Q"u onblk "
  531                    "%"W"u blksize %"W"u blkoff %"W"u take %"W"u\n",
  532                    block,
  533                    source->onblk,
  534                    blksize,
  535                    blkoff,
  536                    take));
  537             stream->msg = "source file too short";
  538             return XD3_INVALID_INPUT;
  539           }
  540 
  541         XD3_ASSERT (blkoff != blksize);
  542 
  543         /* Check if we have enough data on this block to
  544          * finish the instruction. */
  545         if (blkoff + take <= blksize)
  546           {
  547             inst->type = XD3_NOOP;
  548             inst->size = 0;
  549           }
  550         else
  551           {
  552             take = blksize - blkoff;
  553             inst->size -= take;
  554             inst->addr += take;
  555 
  556             /* because (blkoff + take > blksize), above */
  557             XD3_ASSERT (inst->size != 0);
  558           }
  559           }
  560       }
  561     else
  562       {
  563         /* TODO: the memcpy/overlap optimization, etc.  Overlap
  564          * here could be more specific, it's whether (inst->addr -
  565          * srclen) + inst->size > input_pos ?  And is the system
  566          * memcpy really any good? */
  567         overlap = 1;
  568 
  569         /* For a target-window copy, we know the entire range is
  570          * in-memory.  The dec_tgtaddrbase is negatively offset by
  571          * dec_cpylen because the addresses start beyond that
  572          * point. */
  573         src = stream->dec_tgtaddrbase + inst->addr;
  574         inst->type = XD3_NOOP;
  575         inst->size = 0;
  576       }
  577 
  578     dst = stream->next_out + stream->avail_out;
  579 
  580     stream->avail_out += take;
  581 
  582     if (overlap)
  583       {
  584         /* Can't just memcpy here due to possible overlap. */
  585         for (i = take; i != 0; i -= 1)
  586           {
  587         *dst++ = *src++;
  588           }
  589       }
  590     else
  591       {
  592         memcpy (dst, src, take);
  593       }
  594       }
  595     }
  596 
  597   return 0;
  598 }
  599 
  600 static int
  601 xd3_decode_finish_window (xd3_stream *stream)
  602 {
  603   stream->dec_winbytes  = 0;
  604   stream->dec_state     = DEC_FINISH;
  605 
  606   stream->data_sect.pos = 0;
  607   stream->inst_sect.pos = 0;
  608   stream->addr_sect.pos = 0;
  609 
  610   return XD3_OUTPUT;
  611 }
  612 
  613 static int
  614 xd3_decode_secondary_sections (xd3_stream *secondary_stream)
  615 {
  616 #if SECONDARY_ANY
  617   int ret;
  618 #define DECODE_SECONDARY_SECTION(UPPER,LOWER) \
  619   ((secondary_stream->dec_del_ind & VCD_ ## UPPER ## COMP) && \
  620    (ret = xd3_decode_secondary (secondary_stream, \
  621                 & secondary_stream-> LOWER ## _sect,    \
  622                 & xd3_sec_ ## LOWER (secondary_stream))))
  623 
  624   if (DECODE_SECONDARY_SECTION (DATA, data) ||
  625       DECODE_SECONDARY_SECTION (INST, inst) ||
  626       DECODE_SECONDARY_SECTION (ADDR, addr))
  627     {
  628       return ret;
  629     }
  630 #undef DECODE_SECONDARY_SECTION
  631 #endif
  632   return 0;
  633 }
  634 
  635 static int
  636 xd3_decode_sections (xd3_stream *stream)
  637 {
  638   usize_t need, more, take;
  639   int copy, ret;
  640 
  641   if ((stream->flags & XD3_JUST_HDR) != 0)
  642     {
  643       /* Nothing left to do. */
  644       return xd3_decode_finish_window (stream);
  645     }
  646 
  647   /* To avoid extra copying, allocate three sections at once (but
  648    * check for overflow). */
  649   need = stream->inst_sect.size;
  650 
  651   if (USIZE_T_OVERFLOW (need, stream->addr_sect.size))
  652     {
  653       stream->msg = "decoder section size overflow";
  654       return XD3_INTERNAL;
  655     }
  656   need += stream->addr_sect.size;
  657 
  658   if (USIZE_T_OVERFLOW (need, stream->data_sect.size))
  659     {
  660       stream->msg = "decoder section size overflow";
  661       return XD3_INTERNAL;
  662     }
  663   need += stream->data_sect.size;
  664 
  665   /* The window may be entirely processed. */
  666   XD3_ASSERT (stream->dec_winbytes <= need);
  667 
  668   /* Compute how much more input is needed. */
  669   more = (need - stream->dec_winbytes);
  670 
  671   /* How much to consume. */
  672   take = xd3_min (more, stream->avail_in);
  673 
  674   /* See if the input is completely available, to avoid copy. */
  675   copy = (take != more);
  676 
  677   /* If the window is skipped... */
  678   if ((stream->flags & XD3_SKIP_WINDOW) != 0)
  679     {
  680       /* Skip the available input. */
  681       DECODE_INPUT (take);
  682 
  683       stream->dec_winbytes += take;
  684 
  685       if (copy)
  686     {
  687       stream->msg = "further input required";
  688       return XD3_INPUT;
  689     }
  690 
  691       return xd3_decode_finish_window (stream);
  692     }
  693 
  694   /* Process all but the DATA section. */
  695   switch (stream->dec_state)
  696     {
  697     default:
  698       stream->msg = "internal error";
  699       return XD3_INVALID_INPUT;
  700 
  701     case DEC_DATA:
  702       if ((ret = xd3_decode_section (stream, & stream->data_sect,
  703                      DEC_INST, copy))) { return ret; }
  704     case DEC_INST:
  705       if ((ret = xd3_decode_section (stream, & stream->inst_sect,
  706                      DEC_ADDR, copy))) { return ret; }
  707     case DEC_ADDR:
  708       if ((ret = xd3_decode_section (stream, & stream->addr_sect,
  709                      DEC_EMIT, copy))) { return ret; }
  710     }
  711 
  712   XD3_ASSERT (stream->dec_winbytes == need);
  713 
  714   if ((ret = xd3_decode_secondary_sections (stream))) { return ret; }
  715 
  716   if (stream->flags & XD3_SKIP_EMIT)
  717     {
  718       return xd3_decode_finish_window (stream);
  719     }
  720 
  721   /* OPT: A possible optimization is to avoid allocating memory in
  722    * decode_setup_buffers and to avoid a large memcpy when the window
  723    * consists of a single VCD_SOURCE copy instruction. */
  724   if ((ret = xd3_decode_setup_buffers (stream))) { return ret; }
  725 
  726   return 0;
  727 }
  728 
  729 static int
  730 xd3_decode_emit (xd3_stream *stream)
  731 {
  732   int ret;
  733 
  734   /* Produce output: originally structured to allow reentrant code
  735    * that fills as much of the output buffer as possible, but VCDIFF
  736    * semantics allows to copy from anywhere from the target window, so
  737    * instead allocate a sufficiently sized buffer after the target
  738    * window length is decoded.
  739    *
  740    * This code still needs to be reentrant to allow XD3_GETSRCBLK to
  741    * return control.  This is handled by setting the
  742    * stream->dec_currentN instruction types to XD3_NOOP after they
  743    * have been processed. */
  744   XD3_ASSERT (! (stream->flags & XD3_SKIP_EMIT));
  745   XD3_ASSERT (stream->dec_tgtlen <= stream->space_out);
  746 
  747   while (stream->inst_sect.buf != stream->inst_sect.buf_max ||
  748      stream->dec_current1.type != XD3_NOOP ||
  749      stream->dec_current2.type != XD3_NOOP)
  750     {
  751       /* Decode next instruction pair. */
  752       if ((stream->dec_current1.type == XD3_NOOP) &&
  753       (stream->dec_current2.type == XD3_NOOP) &&
  754       (ret = xd3_decode_instruction (stream))) { return ret; }
  755 
  756       /* Output dec_current1 */
  757       while ((stream->dec_current1.type != XD3_NOOP))
  758     {
  759       if ((ret = xd3_decode_output_halfinst (stream, & stream->dec_current1)))
  760         {
  761           return ret;
  762         }
  763     }
  764       /* Output dec_current2 */
  765       while (stream->dec_current2.type != XD3_NOOP)
  766     {
  767       if ((ret = xd3_decode_output_halfinst (stream, & stream->dec_current2)))
  768         {
  769           return ret;
  770         }
  771     }
  772     }
  773 
  774   if (stream->avail_out != stream->dec_tgtlen)
  775     {
  776       IF_DEBUG2 (DP(RINT "AVAIL_OUT(%"W"u) != DEC_TGTLEN(%"W"u)\n",
  777             stream->avail_out, stream->dec_tgtlen));
  778       stream->msg = "wrong window length";
  779       return XD3_INVALID_INPUT;
  780     }
  781 
  782   if (stream->data_sect.buf != stream->data_sect.buf_max)
  783     {
  784       stream->msg = "extra data section";
  785       return XD3_INVALID_INPUT;
  786     }
  787 
  788   if (stream->addr_sect.buf != stream->addr_sect.buf_max)
  789     {
  790       stream->msg = "extra address section";
  791       return XD3_INVALID_INPUT;
  792     }
  793 
  794   /* OPT: Should cksum computation be combined with the above loop? */
  795   if ((stream->dec_win_ind & VCD_ADLER32) != 0 &&
  796       (stream->flags & XD3_ADLER32_NOVER) == 0)
  797     {
  798       uint32_t a32 = adler32 (1L, stream->next_out, stream->avail_out);
  799 
  800       if (a32 != stream->dec_adler32)
  801     {
  802       stream->msg = "target window checksum mismatch";
  803       return XD3_INVALID_INPUT;
  804     }
  805     }
  806 
  807   /* Finished with a window. */
  808   return xd3_decode_finish_window (stream);
  809 }
  810 
  811 int
  812 xd3_decode_input (xd3_stream *stream)
  813 {
  814   int ret;
  815 
  816   if (stream->enc_state != 0)
  817     {
  818       stream->msg = "encoder/decoder transition";
  819       return XD3_INVALID_INPUT;
  820     }
  821 
  822 #define BYTE_CASE(expr,x,nstate) \
  823       do { \
  824       if ( (expr) && \
  825            ((ret = xd3_decode_byte (stream, & (x))) != 0) ) { return ret; } \
  826       stream->dec_state = (nstate); \
  827       } while (0)
  828 
  829 #define OFFSET_CASE(expr,x,nstate) \
  830       do { \
  831       if ( (expr) && \
  832            ((ret = xd3_decode_offset (stream, & (x))) != 0) ) { return ret; } \
  833       stream->dec_state = (nstate); \
  834       } while (0)
  835 
  836 #define SIZE_CASE(expr,x,nstate) \
  837       do { \
  838       if ( (expr) && \
  839            ((ret = xd3_decode_size (stream, & (x))) != 0) ) { return ret; } \
  840       stream->dec_state = (nstate); \
  841       } while (0)
  842 
  843   switch (stream->dec_state)
  844     {
  845     case DEC_VCHEAD:
  846       {
  847     if ((ret = xd3_decode_bytes (stream, stream->dec_magic,
  848                      & stream->dec_magicbytes, 4)))
  849       {
  850         return ret;
  851       }
  852 
  853     if (stream->dec_magic[0] != VCDIFF_MAGIC1 ||
  854         stream->dec_magic[1] != VCDIFF_MAGIC2 ||
  855         stream->dec_magic[2] != VCDIFF_MAGIC3)
  856       {
  857         stream->msg = "not a VCDIFF input";
  858         return XD3_INVALID_INPUT;
  859       }
  860 
  861     if (stream->dec_magic[3] != 0)
  862       {
  863         stream->msg = "VCDIFF input version > 0 is not supported";
  864         return XD3_INVALID_INPUT;
  865       }
  866 
  867     stream->dec_state = DEC_HDRIND;
  868       }
  869     case DEC_HDRIND:
  870       {
  871     if ((ret = xd3_decode_byte (stream, & stream->dec_hdr_ind)))
  872       {
  873         return ret;
  874       }
  875 
  876     if ((stream->dec_hdr_ind & VCD_INVHDR) != 0)
  877       {
  878         stream->msg = "unrecognized header indicator bits set";
  879         return XD3_INVALID_INPUT;
  880       }
  881 
  882     stream->dec_state = DEC_SECONDID;
  883       }
  884 
  885     case DEC_SECONDID:
  886       /* Secondary compressor ID: only if VCD_SECONDARY is set */
  887       if ((stream->dec_hdr_ind & VCD_SECONDARY) != 0)
  888     {
  889       BYTE_CASE (1, stream->dec_secondid, DEC_TABLEN);
  890 
  891       switch (stream->dec_secondid)
  892         {
  893         case VCD_FGK_ID:
  894           FGK_CASE (stream);
  895         case VCD_DJW_ID:
  896           DJW_CASE (stream);
  897         case VCD_LZMA_ID:
  898           LZMA_CASE (stream);
  899         default:
  900           stream->msg = "unknown secondary compressor ID";
  901           return XD3_INVALID_INPUT;
  902         }
  903     }
  904 
  905     case DEC_TABLEN:
  906       /* Length of code table data: only if VCD_CODETABLE is set */
  907       SIZE_CASE ((stream->dec_hdr_ind & VCD_CODETABLE) != 0,
  908          stream->dec_codetblsz, DEC_NEAR);
  909 
  910       /* The codetblsz counts the two NEAR/SAME bytes */
  911       if ((stream->dec_hdr_ind & VCD_CODETABLE) != 0) {
  912     if (stream->dec_codetblsz <= 2) {
  913       stream->msg = "invalid code table size";
  914       return ENOMEM;
  915     }
  916     stream->dec_codetblsz -= 2;
  917       }
  918     case DEC_NEAR:
  919       /* Near modes: only if VCD_CODETABLE is set */
  920       BYTE_CASE((stream->dec_hdr_ind & VCD_CODETABLE) != 0,
  921         stream->acache.s_near, DEC_SAME);
  922     case DEC_SAME:
  923       /* Same modes: only if VCD_CODETABLE is set */
  924       BYTE_CASE((stream->dec_hdr_ind & VCD_CODETABLE) != 0,
  925         stream->acache.s_same, DEC_TABDAT);
  926     case DEC_TABDAT:
  927       /* Compressed code table data */
  928 
  929       if ((stream->dec_hdr_ind & VCD_CODETABLE) != 0)
  930     {
  931       stream->msg = "VCD_CODETABLE support was removed";
  932       return XD3_UNIMPLEMENTED;
  933     }
  934       else
  935     {
  936       /* Use the default table. */
  937       stream->acache.s_near = __rfc3284_code_table_desc.near_modes;
  938       stream->acache.s_same = __rfc3284_code_table_desc.same_modes;
  939       stream->code_table    = xd3_rfc3284_code_table ();
  940     }
  941 
  942       if ((ret = xd3_alloc_cache (stream))) { return ret; }
  943 
  944       stream->dec_state = DEC_APPLEN;
  945 
  946     case DEC_APPLEN:
  947       /* Length of application data */
  948       SIZE_CASE((stream->dec_hdr_ind & VCD_APPHEADER) != 0,
  949         stream->dec_appheadsz, DEC_APPDAT);
  950 
  951     case DEC_APPDAT:
  952       /* Application data */
  953       if (stream->dec_hdr_ind & VCD_APPHEADER)
  954     {
  955       /* Note: we add an additional byte for padding, to allow
  956          0-termination. Check for overflow: */
  957       if (USIZE_T_OVERFLOW(stream->dec_appheadsz, 1))
  958         {
  959           stream->msg = "exceptional appheader size";
  960           return XD3_INVALID_INPUT;
  961         }
  962 
  963       if ((stream->dec_appheader == NULL) &&
  964           (stream->dec_appheader =
  965            (uint8_t*) xd3_alloc (stream,
  966                      stream->dec_appheadsz+1, 1)) == NULL)
  967         {
  968           return ENOMEM;
  969         }
  970 
  971       stream->dec_appheader[stream->dec_appheadsz] = 0;
  972 
  973       if ((ret = xd3_decode_bytes (stream, stream->dec_appheader,
  974                        & stream->dec_appheadbytes,
  975                        stream->dec_appheadsz)))
  976         {
  977           return ret;
  978         }
  979     }
  980 
  981       /* xoff_t -> usize_t is safe because this is the first block. */
  982       stream->dec_hdrsize = (usize_t) stream->total_in;
  983       stream->dec_state = DEC_WININD;
  984 
  985     case DEC_WININD:
  986       {
  987     /* Start of a window: the window indicator */
  988     if ((ret = xd3_decode_byte (stream, & stream->dec_win_ind)))
  989       {
  990         return ret;
  991       }
  992 
  993     stream->current_window = stream->dec_window_count;
  994 
  995     if (XOFF_T_OVERFLOW (stream->dec_winstart, stream->dec_tgtlen))
  996       {
  997         stream->msg = "decoder file offset overflow";
  998         return XD3_INVALID_INPUT;
  999       }
 1000 
 1001     stream->dec_winstart += stream->dec_tgtlen;
 1002 
 1003     if ((stream->dec_win_ind & VCD_INVWIN) != 0)
 1004       {
 1005         stream->msg = "unrecognized window indicator bits set";
 1006         return XD3_INVALID_INPUT;
 1007       }
 1008 
 1009     if ((ret = xd3_decode_init_window (stream))) { return ret; }
 1010 
 1011     stream->dec_state = DEC_CPYLEN;
 1012 
 1013     IF_DEBUG2 (DP(RINT "--------- TARGET WINDOW %"Q"u -----------\n",
 1014               stream->current_window));
 1015       }
 1016 
 1017     case DEC_CPYLEN:
 1018       /* Copy window length: only if VCD_SOURCE or VCD_TARGET is set */
 1019       SIZE_CASE(SRCORTGT (stream->dec_win_ind), stream->dec_cpylen,
 1020         DEC_CPYOFF);
 1021 
 1022       /* Set the initial, logical decoder position (HERE address) in
 1023        * dec_position.  This is set to just after the source/copy
 1024        * window, as we are just about to output the first byte of
 1025        * target window. */
 1026       stream->dec_position = stream->dec_cpylen;
 1027 
 1028     case DEC_CPYOFF:
 1029       /* Copy window offset: only if VCD_SOURCE or VCD_TARGET is set */
 1030       OFFSET_CASE(SRCORTGT (stream->dec_win_ind), stream->dec_cpyoff,
 1031           DEC_ENCLEN);
 1032 
 1033       /* Copy offset and copy length may not overflow. */
 1034       if (XOFF_T_OVERFLOW (stream->dec_cpyoff, stream->dec_cpylen))
 1035     {
 1036       stream->msg = "decoder copy window overflows a file offset";
 1037       return XD3_INVALID_INPUT;
 1038     }
 1039 
 1040       /* Check copy window bounds: VCD_TARGET window may not exceed
 1041      current position. */
 1042       if ((stream->dec_win_ind & VCD_TARGET) &&
 1043       (stream->dec_cpyoff + stream->dec_cpylen >
 1044        stream->dec_winstart))
 1045     {
 1046       stream->msg = "VCD_TARGET window out of bounds";
 1047       return XD3_INVALID_INPUT;
 1048     }
 1049 
 1050     case DEC_ENCLEN:
 1051       /* Length of the delta encoding */
 1052       SIZE_CASE(1, stream->dec_enclen, DEC_TGTLEN);
 1053     case DEC_TGTLEN:
 1054       /* Length of target window */
 1055       SIZE_CASE(1, stream->dec_tgtlen, DEC_DELIND);
 1056 
 1057       /* Set the maximum decoder position, beyond which we should not
 1058        * decode any data.  This is the maximum value for dec_position.
 1059        * This may not exceed the size of a usize_t. */
 1060       if (USIZE_T_OVERFLOW (stream->dec_cpylen, stream->dec_tgtlen))
 1061     {
 1062       stream->msg = "decoder target window overflows a usize_t";
 1063       return XD3_INVALID_INPUT;
 1064     }
 1065 
 1066       /* Check for malicious files. */
 1067       if (stream->dec_tgtlen > XD3_HARDMAXWINSIZE)
 1068     {
 1069       stream->msg = "hard window size exceeded";
 1070       return XD3_INVALID_INPUT;
 1071     }
 1072 
 1073       stream->dec_maxpos = stream->dec_cpylen + stream->dec_tgtlen;
 1074 
 1075     case DEC_DELIND:
 1076       /* Delta indicator */
 1077       BYTE_CASE(1, stream->dec_del_ind, DEC_DATALEN);
 1078 
 1079       if ((stream->dec_del_ind & VCD_INVDEL) != 0)
 1080     {
 1081       stream->msg = "unrecognized delta indicator bits set";
 1082       return XD3_INVALID_INPUT;
 1083     }
 1084 
 1085       /* Delta indicator is only used with secondary compression. */
 1086       if ((stream->dec_del_ind != 0) && (stream->sec_type == NULL))
 1087     {
 1088       stream->msg = "invalid delta indicator bits set";
 1089       return XD3_INVALID_INPUT;
 1090     }
 1091 
 1092       /* Section lengths */
 1093     case DEC_DATALEN:
 1094       SIZE_CASE(1, stream->data_sect.size, DEC_INSTLEN);
 1095     case DEC_INSTLEN:
 1096       SIZE_CASE(1, stream->inst_sect.size, DEC_ADDRLEN);
 1097     case DEC_ADDRLEN:
 1098       SIZE_CASE(1, stream->addr_sect.size, DEC_CKSUM);
 1099 
 1100     case DEC_CKSUM:
 1101       /* Window checksum. */
 1102       if ((stream->dec_win_ind & VCD_ADLER32) != 0)
 1103     {
 1104       int i;
 1105 
 1106       if ((ret = xd3_decode_bytes (stream, stream->dec_cksum,
 1107                        & stream->dec_cksumbytes, 4)))
 1108         {
 1109           return ret;
 1110         }
 1111 
 1112       for (i = 0; i < 4; i += 1)
 1113         {
 1114           stream->dec_adler32 =
 1115         (stream->dec_adler32 << 8) | stream->dec_cksum[i];
 1116         }
 1117     }
 1118 
 1119       stream->dec_state = DEC_DATA;
 1120 
 1121       /* Check dec_enclen for redundency, otherwise it is not really used. */
 1122       {
 1123     usize_t enclen_check =
 1124       (1 + (xd3_sizeof_size (stream->dec_tgtlen) +
 1125         xd3_sizeof_size (stream->data_sect.size) +
 1126         xd3_sizeof_size (stream->inst_sect.size) +
 1127         xd3_sizeof_size (stream->addr_sect.size)) +
 1128        stream->data_sect.size +
 1129        stream->inst_sect.size +
 1130        stream->addr_sect.size +
 1131        ((stream->dec_win_ind & VCD_ADLER32) ? 4 : 0));
 1132 
 1133     if (stream->dec_enclen != enclen_check)
 1134       {
 1135         stream->msg = "incorrect encoding length (redundent)";
 1136         return XD3_INVALID_INPUT;
 1137       }
 1138       }
 1139 
 1140       /* Returning here gives the application a chance to inspect the
 1141        * header, skip the window, etc. */
 1142       if (stream->current_window == 0) { return XD3_GOTHEADER; }
 1143       else                             { return XD3_WINSTART; }
 1144 
 1145     case DEC_DATA:
 1146     case DEC_INST:
 1147     case DEC_ADDR:
 1148       /* Next read the three sections. */
 1149      if ((ret = xd3_decode_sections (stream))) { return ret; }
 1150 
 1151     case DEC_EMIT:
 1152 
 1153       /* To speed VCD_SOURCE block-address calculations, the source
 1154        * cpyoff_blocks and cpyoff_blkoff are pre-computed. */
 1155       if (stream->dec_win_ind & VCD_SOURCE)
 1156     {
 1157       xd3_source *src = stream->src;
 1158 
 1159       if (src == NULL)
 1160         {
 1161           stream->msg = "source input required";
 1162           return XD3_INVALID_INPUT;
 1163         }
 1164 
 1165       xd3_blksize_div(stream->dec_cpyoff, src,
 1166               &src->cpyoff_blocks,
 1167               &src->cpyoff_blkoff);
 1168       
 1169       IF_DEBUG2(DP(RINT
 1170                "[decode_cpyoff] %"Q"u "
 1171                "cpyblkno %"Q"u "
 1172                "cpyblkoff %"W"u "
 1173                "blksize %"W"u\n",
 1174                stream->dec_cpyoff,
 1175                src->cpyoff_blocks,
 1176                src->cpyoff_blkoff,
 1177                src->blksize));
 1178     }
 1179 
 1180       /* xd3_decode_emit returns XD3_OUTPUT on every success. */
 1181       if ((ret = xd3_decode_emit (stream)) == XD3_OUTPUT)
 1182     {
 1183       stream->total_out += stream->avail_out;
 1184     }
 1185 
 1186       return ret;
 1187 
 1188     case DEC_FINISH:
 1189       {
 1190     if (stream->dec_win_ind & VCD_TARGET)
 1191       {
 1192         if (stream->dec_lastwin == NULL)
 1193           {
 1194         stream->dec_lastwin   = stream->next_out;
 1195         stream->dec_lastspace = stream->space_out;
 1196           }
 1197         else
 1198           {
 1199         xd3_swap_uint8p (& stream->dec_lastwin,
 1200                  & stream->next_out);
 1201         xd3_swap_usize_t (& stream->dec_lastspace,
 1202                   & stream->space_out);
 1203           }
 1204       }
 1205 
 1206     stream->dec_lastlen   = stream->dec_tgtlen;
 1207     stream->dec_laststart = stream->dec_winstart;
 1208     stream->dec_window_count += 1;
 1209 
 1210     /* Note: the updates to dec_winstart & current_window are
 1211      * deferred until after the next DEC_WININD byte is read. */
 1212     stream->dec_state = DEC_WININD;
 1213     return XD3_WINFINISH;
 1214       }
 1215 
 1216     default:
 1217       stream->msg = "invalid state";
 1218       return XD3_INVALID_INPUT;
 1219     }
 1220 }
 1221 
 1222 #endif // _XDELTA3_DECODE_H_