src/zlib/infblock.c

   1 /* infblock.c -- interpret and process block types to last block
   2  * Copyright (C) 1995-1998 Mark Adler
   3  * For conditions of distribution and use, see copyright notice in zlib.h
   4  */
   5
   6 #include "zutil.h"
   7 #include "infblock.h"
   8 #include "inftrees.h"
   9 #include "infcodes.h"
  10 #include "infutil.h"
  11
  12 struct inflate_codes_state {int dummy;}; /* for buggy compilers */
  13
  14 /* simplify the use of the inflate_huft type with some defines */
  15 #define exop word.what.Exop
  16 #define bits word.what.Bits
  17
  18 /* Table for deflate from PKZIP's appnote.txt. */
  19 local const uInt border[] = { /* Order of the bit length code lengths */
  20         16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
  21
  22 /*
  23    Notes beyond the 1.93a appnote.txt:
  24
  25    1. Distance pointers never point before the beginning of the output
  26       stream.
  27    2. Distance pointers can point back across blocks, up to 32k away.
  28    3. There is an implied maximum of 7 bits for the bit length table and
  29       15 bits for the actual data.
  30    4. If only one code exists, then it is encoded using one bit.  (Zero
  31       would be more efficient, but perhaps a little confusing.)  If two
  32       codes exist, they are coded using one bit each (0 and 1).
  33    5. There is no way of sending zero distance codes--a dummy must be
  34       sent if there are none.  (History: a pre 2.0 version of PKZIP would
  35       store blocks with no distance codes, but this was discovered to be
  36       too harsh a criterion.)  Valid only for 1.93a.  2.04c does allow
  37       zero distance codes, which is sent as one code of zero bits in
  38       length.
  39    6. There are up to 286 literal/length codes.  Code 256 represents the
  40       end-of-block.  Note however that the static length tree defines
  41       288 codes just to fill out the Huffman codes.  Codes 286 and 287
  42       cannot be used though, since there is no length base or extra bits
  43       defined for them.  Similarily, there are up to 30 distance codes.
  44       However, static trees define 32 codes (all 5 bits) to fill out the
  45       Huffman codes, but the last two had better not show up in the data.
  46    7. Unzip can check dynamic Huffman blocks for complete code sets.
  47       The exception is that a single code would not be complete (see #4).
  48    8. The five bits following the block type is really the number of
  49       literal codes sent minus 257.
  50    9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
  51       (1+6+6).  Therefore, to output three times the length, you output
  52       three codes (1+1+1), whereas to output four times the same length,
  53       you only need two codes (1+3).  Hmm.
  54   10. In the tree reconstruction algorithm, Code = Code + Increment
  55       only if BitLength(i) is not zero.  (Pretty obvious.)
  56   11. Correction: 4 Bits: # of Bit Length codes - 4     (4 - 19)
  57   12. Note: length code 284 can represent 227-258, but length code 285
  58       really is 258.  The last length deserves its own, short code
  59       since it gets used a lot in very redundant files.  The length
  60       258 is special since 258 - 3 (the min match length) is 255.
  61   13. The literal/length and distance code bit lengths are read as a
  62       single stream of lengths.  It is possible (and advantageous) for
  63       a repeat code (16, 17, or 18) to go across the boundary between
  64       the two sets of lengths.
  65  */
  66
  67
  68 #if defined(__VISAGECPP__) /* Visualage can't handle this antiquated interface */
  69 void inflate_blocks_reset(inflate_blocks_statef* s, z_streamp z, uLongf* c)
  70 #else
  71 void inflate_blocks_reset(s, z, c)
  72 inflate_blocks_statef *s;
  73 z_streamp z;
  74 uLongf *c;
  75 #endif
  76 {
  77   if (c != Z_NULL)
  78     *c = s->check;
  79   if (s->mode == BTREE || s->mode == DTREE)
  80     ZFREE(z, s->sub.trees.blens);
  81   if (s->mode == CODES)
  82     inflate_codes_free(s->sub.decode.codes, z);
  83   s->mode = TYPE;
  84   s->bitk = 0;
  85   s->bitb = 0;
  86   s->read = s->write = s->window;
  87   if (s->checkfn != Z_NULL)
  88     z->adler = s->check = (*s->checkfn)(0L, (const Bytef *)Z_NULL, 0);
  89   Tracev((stderr, "inflate:   blocks reset\n"));
  90 }
  91
  92 #if defined(__VISAGECPP__) /* Visualage can't handle this antiquated interface */
  93 inflate_blocks_statef *inflate_blocks_new(z_streamp z, check_func c, uInt w)
  94 #else
  95 inflate_blocks_statef *inflate_blocks_new(z, c, w)
  96 z_streamp z;
  97 check_func c;
  98 uInt w;
  99 #endif
 100 {
 101   inflate_blocks_statef *s;
 102
 103   if ((s = (inflate_blocks_statef *)ZALLOC
 104        (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
 105     return s;
 106   if ((s->hufts =
 107        (inflate_huft *)ZALLOC(z, sizeof(inflate_huft), MANY)) == Z_NULL)
 108   {
 109     ZFREE(z, s);
 110     return Z_NULL;
 111   }
 112   if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
 113   {
 114     ZFREE(z, s->hufts);
 115     ZFREE(z, s);
 116     return Z_NULL;
 117   }
 118   s->end = s->window + w;
 119   s->checkfn = c;
 120   s->mode = TYPE;
 121   Tracev((stderr, "inflate:   blocks allocated\n"));
 122   inflate_blocks_reset(s, z, Z_NULL);
 123   return s;
 124 }
 125
 126 #if defined(__VISAGECPP__) /* Visualage can't handle this antiquated interface */
 127 int inflate_blocks(inflate_blocks_statef* s, z_streamp z, int r)
 128 #else
 129 int inflate_blocks(s, z, r)
 130 inflate_blocks_statef *s;
 131 z_streamp z;
 132 int r;
 133 #endif
 134 {
 135   uInt t;               /* temporary storage */
 136   uLong b;              /* bit buffer */
 137   uInt k;               /* bits in bit buffer */
 138   Bytef *p;             /* input data pointer */
 139   uInt n;               /* bytes available there */
 140   Bytef *q;             /* output window write pointer */
 141   uInt m;               /* bytes to end of window or read pointer */
 142
 143   /* copy input/output information to locals (UPDATE macro restores) */
 144   LOAD
 145
 146   /* process input based on current state */
 147   while (1) switch (s->mode)
 148   {
 149     case TYPE:
 150       NEEDBITS(3)
 151       t = (uInt)b & 7;
 152       s->last = t & 1;
 153       switch (t >> 1)
 154       {
 155         case 0:                         /* stored */
 156           Tracev((stderr, "inflate:     stored block%s\n",
 157                  s->last ? " (last)" : ""));
 158           DUMPBITS(3)
 159           t = k & 7;                    /* go to byte boundary */
 160           DUMPBITS(t)
 161           s->mode = LENS;               /* get length of stored block */
 162           break;
 163         case 1:                         /* fixed */
 164           Tracev((stderr, "inflate:     fixed codes block%s\n",
 165                  s->last ? " (last)" : ""));
 166           {
 167             uInt bl, bd;
 168             inflate_huft *tl, *td;
 169
 170             inflate_trees_fixed(&bl, &bd, &tl, &td, z);
 171             s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
 172             if (s->sub.decode.codes == Z_NULL)
 173             {
 174               r = Z_MEM_ERROR;
 175               LEAVE
 176             }
 177           }
 178           DUMPBITS(3)
 179           s->mode = CODES;
 180           break;
 181         case 2:                         /* dynamic */
 182           Tracev((stderr, "inflate:     dynamic codes block%s\n",
 183                  s->last ? " (last)" : ""));
 184           DUMPBITS(3)
 185           s->mode = TABLE;
 186           break;
 187         case 3:                         /* illegal */
 188           DUMPBITS(3)
 189           s->mode = BAD;
 190           z->msg = (char*)"invalid block type";
 191           r = Z_DATA_ERROR;
 192           LEAVE
 193       }
 194       break;
 195     case LENS:
 196       NEEDBITS(32)
 197       if ((((~b) >> 16) & 0xffff) != (b & 0xffff))
 198       {
 199         s->mode = BAD;
 200         z->msg = (char*)"invalid stored block lengths";
 201         r = Z_DATA_ERROR;
 202         LEAVE
 203       }
 204       s->sub.left = (uInt)b & 0xffff;
 205       b = k = 0;                      /* dump bits */
 206       Tracev((stderr, "inflate:       stored length %u\n", s->sub.left));
 207       s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE);
 208       break;
 209     case STORED:
 210       if (n == 0)
 211         LEAVE
 212       NEEDOUT
 213       t = s->sub.left;
 214       if (t > n) t = n;
 215       if (t > m) t = m;
 216       zmemcpy(q, p, t);
 217       p += t;  n -= t;
 218       q += t;  m -= t;
 219       if ((s->sub.left -= t) != 0)
 220         break;
 221       Tracev((stderr, "inflate:       stored end, %lu total out\n",
 222               z->total_out + (q >= s->read ? q - s->read :
 223               (s->end - s->read) + (q - s->window))));
 224       s->mode = s->last ? DRY : TYPE;
 225       break;
 226     case TABLE:
 227       NEEDBITS(14)
 228       s->sub.trees.table = t = (uInt)b & 0x3fff;
 229 #ifndef PKZIP_BUG_WORKAROUND
 230       if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
 231       {
 232         s->mode = BAD;
 233         z->msg = (char*)"too many length or distance symbols";
 234         r = Z_DATA_ERROR;
 235         LEAVE
 236       }
 237 #endif
 238       t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
 239       if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
 240       {
 241         r = Z_MEM_ERROR;
 242         LEAVE
 243       }
 244       DUMPBITS(14)
 245       s->sub.trees.index = 0;
 246       Tracev((stderr, "inflate:       table sizes ok\n"));
 247       s->mode = BTREE;
 248     case BTREE:
 249       while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
 250       {
 251         NEEDBITS(3)
 252         s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
 253         DUMPBITS(3)
 254       }
 255       while (s->sub.trees.index < 19)
 256         s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
 257       s->sub.trees.bb = 7;
 258       t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
 259                              &s->sub.trees.tb, s->hufts, z);
 260       if (t != Z_OK)
 261       {
 262         ZFREE(z, s->sub.trees.blens);
 263         r = t;
 264         if (r == Z_DATA_ERROR)
 265           s->mode = BAD;
 266         LEAVE
 267       }
 268       s->sub.trees.index = 0;
 269       Tracev((stderr, "inflate:       bits tree ok\n"));
 270       s->mode = DTREE;
 271     case DTREE:
 272       while (t = s->sub.trees.table,
 273              s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
 274       {
 275         inflate_huft *h;
 276         uInt i, j, c;
 277
 278         t = s->sub.trees.bb;
 279         NEEDBITS(t)
 280         h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
 281         t = h->bits;
 282         c = h->base;
 283         if (c < 16)
 284         {
 285           DUMPBITS(t)
 286           s->sub.trees.blens[s->sub.trees.index++] = c;
 287         }
 288         else /* c == 16..18 */
 289         {
 290           i = c == 18 ? 7 : c - 14;
 291           j = c == 18 ? 11 : 3;
 292           NEEDBITS(t + i)
 293           DUMPBITS(t)
 294           j += (uInt)b & inflate_mask[i];
 295           DUMPBITS(i)
 296           i = s->sub.trees.index;
 297           t = s->sub.trees.table;
 298           if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
 299               (c == 16 && i < 1))
 300           {
 301             ZFREE(z, s->sub.trees.blens);
 302             s->mode = BAD;
 303             z->msg = (char*)"invalid bit length repeat";
 304             r = Z_DATA_ERROR;
 305             LEAVE
 306           }
 307           c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
 308           do {
 309             s->sub.trees.blens[i++] = c;
 310           } while (--j);
 311           s->sub.trees.index = i;
 312         }
 313       }
 314       s->sub.trees.tb = Z_NULL;
 315       {
 316         uInt bl, bd;
 317         inflate_huft *tl, *td;
 318         inflate_codes_statef *c;
 319
 320         bl = 9;         /* must be <= 9 for lookahead assumptions */
 321         bd = 6;         /* must be <= 9 for lookahead assumptions */
 322         t = s->sub.trees.table;
 323         t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
 324                                   s->sub.trees.blens, &bl, &bd, &tl, &td,
 325                                   s->hufts, z);
 326         ZFREE(z, s->sub.trees.blens);
 327         if (t != Z_OK)
 328         {
 329           if (t == (uInt)Z_DATA_ERROR)
 330             s->mode = BAD;
 331           r = t;
 332           LEAVE
 333         }
 334         Tracev((stderr, "inflate:       trees ok\n"));
 335         if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
 336         {
 337           r = Z_MEM_ERROR;
 338           LEAVE
 339         }
 340         s->sub.decode.codes = c;
 341       }
 342       s->mode = CODES;
 343     case CODES:
 344       UPDATE
 345       if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
 346         return inflate_flush(s, z, r);
 347       r = Z_OK;
 348       inflate_codes_free(s->sub.decode.codes, z);
 349       LOAD
 350       Tracev((stderr, "inflate:       codes end, %lu total out\n",
 351               z->total_out + (q >= s->read ? q - s->read :
 352               (s->end - s->read) + (q - s->window))));
 353       if (!s->last)
 354       {
 355         s->mode = TYPE;
 356         break;
 357       }
 358       if (k > 7)              /* return unused byte, if any */
 359       {
 360         Assert(k < 16, "inflate_codes grabbed too many bytes")
 361         k -= 8;
 362         n++;
 363         p--;                    /* can always return one */
 364       }
 365       s->mode = DRY;
 366     case DRY:
 367       FLUSH
 368       if (s->read != s->write)
 369         LEAVE
 370       s->mode = DONE;
 371     case DONE:
 372       r = Z_STREAM_END;
 373       LEAVE
 374     case BAD:
 375       r = Z_DATA_ERROR;
 376       LEAVE
 377     default:
 378       r = Z_STREAM_ERROR;
 379       LEAVE
 380   }
 381 }
 382
 383 #if defined(__VISAGECPP__) /* Visualage can't handle this antiquated interface */
 384 int inflate_blocks_free(inflate_blocks_statef* s, z_streamp z)
 385 #else
 386 int inflate_blocks_free(s, z)
 387 inflate_blocks_statef *s;
 388 z_streamp z;
 389 #endif
 390 {
 391   inflate_blocks_reset(s, z, Z_NULL);
 392   ZFREE(z, s->window);
 393   ZFREE(z, s->hufts);
 394   ZFREE(z, s);
 395   Tracev((stderr, "inflate:   blocks freed\n"));
 396   return Z_OK;
 397 }
 398
 399 #if defined(__VISAGECPP__) /* Visualage can't handle this antiquated interface */
 400 void inflate_set_dictionary(inflate_blocks_statef* s, const Bytef* d, uInt n)
 401 #else
 402 void inflate_set_dictionary(s, d, n)
 403 inflate_blocks_statef *s;
 404 const Bytef *d;
 405 uInt  n;
 406 #endif
 407 {
 408   zmemcpy(s->window, d, n);
 409   s->read = s->write = s->window + n;
 410 }
 411
 412 /* Returns true if inflate is currently at the end of a block generated
 413  * by Z_SYNC_FLUSH or Z_FULL_FLUSH.
 414  * IN assertion: s != Z_NULL
 415  */
 416 #if defined(__VISAGECPP__) /* Visualage can't handle this antiquated interface */
 417 int inflate_blocks_sync_point(inflate_blocks_statef* s)
 418 #else
 419 int inflate_blocks_sync_point(s)
 420 inflate_blocks_statef *s;
 421 #endif
 422 {
 423   return s->mode == LENS;
 424 }