xdelta3-decode.h

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