src/zlib/infblock.c

   1 /* infblock.c -- interpret and process block types to last block
   2  * Copyright (C) 1995-2002 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         r = t;
 263         if (r == Z_DATA_ERROR)
 264         {
 265           ZFREE(z, s->sub.trees.blens);
 266           s->mode = BAD;
 267         }
 268         LEAVE
 269       }
 270       s->sub.trees.index = 0;
 271       Tracev((stderr, "inflate:       bits tree ok\n"));
 272       s->mode = DTREE;
 273     case DTREE:
 274       while (t = s->sub.trees.table,
 275              s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
 276       {
 277         inflate_huft *h;
 278         uInt i, j, c;
 279
 280         t = s->sub.trees.bb;
 281         NEEDBITS(t)
 282         h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
 283         t = h->bits;
 284         c = h->base;
 285         if (c < 16)
 286         {
 287           DUMPBITS(t)
 288           s->sub.trees.blens[s->sub.trees.index++] = c;
 289         }
 290         else /* c == 16..18 */
 291         {
 292           i = c == 18 ? 7 : c - 14;
 293           j = c == 18 ? 11 : 3;
 294           NEEDBITS(t + i)
 295           DUMPBITS(t)
 296           j += (uInt)b & inflate_mask[i];
 297           DUMPBITS(i)
 298           i = s->sub.trees.index;
 299           t = s->sub.trees.table;
 300           if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
 301               (c == 16 && i < 1))
 302           {
 303             ZFREE(z, s->sub.trees.blens);
 304             s->mode = BAD;
 305             z->msg = (char*)"invalid bit length repeat";
 306             r = Z_DATA_ERROR;
 307             LEAVE
 308           }
 309           c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
 310           do {
 311             s->sub.trees.blens[i++] = c;
 312           } while (--j);
 313           s->sub.trees.index = i;
 314         }
 315       }
 316       s->sub.trees.tb = Z_NULL;
 317       {
 318         uInt bl, bd;
 319         inflate_huft *tl, *td;
 320         inflate_codes_statef *c;
 321
 322         bl = 9;         /* must be <= 9 for lookahead assumptions */
 323         bd = 6;         /* must be <= 9 for lookahead assumptions */
 324         t = s->sub.trees.table;
 325         t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
 326                                   s->sub.trees.blens, &bl, &bd, &tl, &td,
 327                                   s->hufts, z);
 328         if (t != Z_OK)
 329         {
 330           if (t == (uInt)Z_DATA_ERROR)
 331           {
 332             ZFREE(z, s->sub.trees.blens);
 333             s->mode = BAD;
 334           }
 335           r = t;
 336           LEAVE
 337         }
 338         Tracev((stderr, "inflate:       trees ok\n"));
 339         if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
 340         {
 341           r = Z_MEM_ERROR;
 342           LEAVE
 343         }
 344         s->sub.decode.codes = c;
 345       }
 346       ZFREE(z, s->sub.trees.blens);
 347       s->mode = CODES;
 348     case CODES:
 349       UPDATE
 350       if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
 351         return inflate_flush(s, z, r);
 352       r = Z_OK;
 353       inflate_codes_free(s->sub.decode.codes, z);
 354       LOAD
 355       Tracev((stderr, "inflate:       codes end, %lu total out\n",
 356               z->total_out + (q >= s->read ? q - s->read :
 357               (s->end - s->read) + (q - s->window))));
 358       if (!s->last)
 359       {
 360         s->mode = TYPE;
 361         break;
 362       }
 363       s->mode = DRY;
 364     case DRY:
 365       FLUSH
 366       if (s->read != s->write)
 367         LEAVE
 368       s->mode = DONE;
 369     case DONE:
 370       r = Z_STREAM_END;
 371       LEAVE
 372     case BAD:
 373       r = Z_DATA_ERROR;
 374       LEAVE
 375     default:
 376       r = Z_STREAM_ERROR;
 377       LEAVE
 378   }
 379 }
 380
 381 #if defined(__VISAGECPP__) /* Visualage can't handle this antiquated interface */
 382 int inflate_blocks_free(inflate_blocks_statef* s, z_streamp z)
 383 #else
 384 int inflate_blocks_free(s, z)
 385 inflate_blocks_statef *s;
 386 z_streamp z;
 387 #endif
 388 {
 389   inflate_blocks_reset(s, z, Z_NULL);
 390   ZFREE(z, s->window);
 391   ZFREE(z, s->hufts);
 392   ZFREE(z, s);
 393   Tracev((stderr, "inflate:   blocks freed\n"));
 394   return Z_OK;
 395 }
 396
 397 #if defined(__VISAGECPP__) /* Visualage can't handle this antiquated interface */
 398 void inflate_set_dictionary(inflate_blocks_statef* s, const Bytef* d, uInt n)
 399 #else
 400 void inflate_set_dictionary(s, d, n)
 401 inflate_blocks_statef *s;
 402 const Bytef *d;
 403 uInt  n;
 404 #endif
 405 {
 406   zmemcpy(s->window, d, n);
 407   s->read = s->write = s->window + n;
 408 }
 409
 410 /* Returns true if inflate is currently at the end of a block generated
 411  * by Z_SYNC_FLUSH or Z_FULL_FLUSH.
 412  * IN assertion: s != Z_NULL
 413  */
 414 #if defined(__VISAGECPP__) /* Visualage can't handle this antiquated interface */
 415 int inflate_blocks_sync_point(inflate_blocks_statef* s)
 416 #else
 417 int inflate_blocks_sync_point(s)
 418 inflate_blocks_statef *s;
 419 #endif
 420 {
 421   return s->mode == LENS;
 422 }