- Main Page
- Namespaces
- Classes
- Files
- Directories

- File List
- File Members

# infblock.c

    00001 /* infblock.c -- interpret and process block types to last block
    00002  * Copyright (C) 1995-2002 Mark Adler
    00003  * For conditions of distribution and use, see copyright notice in zlib.h
    00004  */
    00005
    00006 #include "zutil.h"
    00007 #include "infblock.h"
    00008 #include "inftrees.h"
    00009 #include "infcodes.h"
    00010 #include "infutil.h"
    00011
    00012 struct inflate_codes_state {int dummy;}; /* for buggy compilers */
    00013
    00014 /* simplify the use of the inflate_huft type with some defines */
    00015 #define exop word.what.Exop
    00016 #define bits word.what.Bits
    00017
    00018 /* Table for deflate from PKZIP's appnote.txt. */
    00019 local const uInt border[] = { /* Order of the bit length code lengths */
    00020         16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
    00021
    00022 /*
    00023    Notes beyond the 1.93a appnote.txt:
    00024
    00025    1. Distance pointers never point before the beginning of the output
    00026       stream.
    00027    2. Distance pointers can point back across blocks, up to 32k away.
    00028    3. There is an implied maximum of 7 bits for the bit length table and
    00029       15 bits for the actual data.
    00030    4. If only one code exists, then it is encoded using one bit.  (Zero
    00031       would be more efficient, but perhaps a little confusing.)  If two
    00032       codes exist, they are coded using one bit each (0 and 1).
    00033    5. There is no way of sending zero distance codes--a dummy must be
    00034       sent if there are none.  (History: a pre 2.0 version of PKZIP would
    00035       store blocks with no distance codes, but this was discovered to be
    00036       too harsh a criterion.)  Valid only for 1.93a.  2.04c does allow
    00037       zero distance codes, which is sent as one code of zero bits in
    00038       length.
    00039    6. There are up to 286 literal/length codes.  Code 256 represents the
    00040       end-of-block.  Note however that the static length tree defines
    00041       288 codes just to fill out the Huffman codes.  Codes 286 and 287
    00042       cannot be used though, since there is no length base or extra bits
    00043       defined for them.  Similarily, there are up to 30 distance codes.
    00044       However, static trees define 32 codes (all 5 bits) to fill out the
    00045       Huffman codes, but the last two had better not show up in the data.
    00046    7. Unzip can check dynamic Huffman blocks for complete code sets.
    00047       The exception is that a single code would not be complete (see #4).
    00048    8. The five bits following the block type is really the number of
    00049       literal codes sent minus 257.
    00050    9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
    00051       (1+6+6).  Therefore, to output three times the length, you output
    00052       three codes (1+1+1), whereas to output four times the same length,
    00053       you only need two codes (1+3).  Hmm.
    00054   10. In the tree reconstruction algorithm, Code = Code + Increment
    00055       only if BitLength(i) is not zero.  (Pretty obvious.)
    00056   11. Correction: 4 Bits: # of Bit Length codes - 4     (4 - 19)
    00057   12. Note: length code 284 can represent 227-258, but length code 285
    00058       really is 258.  The last length deserves its own, short code
    00059       since it gets used a lot in very redundant files.  The length
    00060       258 is special since 258 - 3 (the min match length) is 255.
    00061   13. The literal/length and distance code bit lengths are read as a
    00062       single stream of lengths.  It is possible (and advantageous) for
    00063       a repeat code (16, 17, or 18) to go across the boundary between
    00064       the two sets of lengths.
    00065  */
    00066
    00067
    00068 void inflate_blocks_reset(s, z, c)
    00069 inflate_blocks_statef *s;
    00070 z_streamp z;
    00071 uLongf *c;
    00072 {
    00073   if (c != Z_NULL)
    00074     *c = s->check;
    00075   if (s->mode == BTREE || s->mode == DTREE)
    00076     ZFREE(z, s->sub.trees.blens);
    00077   if (s->mode == CODES)
    00078     inflate_codes_free(s->sub.decode.codes, z);
    00079   s->mode = TYPE;
    00080   s->bitk = 0;
    00081   s->bitb = 0;
    00082   s->read = s->write = s->window;
    00083   if (s->checkfn != Z_NULL)
    00084     z->adler = s->check = (*s->checkfn)(0L, (const Bytef *)Z_NULL, 0);
    00085   Tracev((stderr, "inflate:   blocks reset\n"));
    00086 }
    00087
    00088
    00089 inflate_blocks_statef *inflate_blocks_new(z, c, w)
    00090 z_streamp z;
    00091 check_func c;
    00092 uInt w;
    00093 {
    00094   inflate_blocks_statef *s;
    00095
    00096   if ((s = (inflate_blocks_statef *)ZALLOC
    00097        (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
    00098     return s;
    00099   if ((s->hufts =
    00100        (inflate_huft *)ZALLOC(z, sizeof(inflate_huft), MANY)) == Z_NULL)
    00101   {
    00102     ZFREE(z, s);
    00103     return Z_NULL;
    00104   }
    00105   if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
    00106   {
    00107     ZFREE(z, s->hufts);
    00108     ZFREE(z, s);
    00109     return Z_NULL;
    00110   }
    00111   s->end = s->window + w;
    00112   s->checkfn = c;
    00113   s->mode = TYPE;
    00114   Tracev((stderr, "inflate:   blocks allocated\n"));
    00115   inflate_blocks_reset(s, z, Z_NULL);
    00116   return s;
    00117 }
    00118
    00119
    00120 int inflate_blocks(s, z, r)
    00121 inflate_blocks_statef *s;
    00122 z_streamp z;
    00123 int r;
    00124 {
    00125   uInt t;               /* temporary storage */
    00126   uLong b;              /* bit buffer */
    00127   uInt k;               /* bits in bit buffer */
    00128   Bytef *p;             /* input data pointer */
    00129   uInt n;               /* bytes available there */
    00130   Bytef *q;             /* output window write pointer */
    00131   uInt m;               /* bytes to end of window or read pointer */
    00132
    00133   /* copy input/output information to locals (UPDATE macro restores) */
    00134   LOAD
    00135
    00136   /* process input based on current state */
    00137   while (1) switch (s->mode)
    00138   {
    00139     case TYPE:
    00140       NEEDBITS(3)
    00141       t = (uInt)b & 7;
    00142       s->last = t & 1;
    00143       switch (t >> 1)
    00144       {
    00145         case 0:                         /* stored */
    00146           Tracev((stderr, "inflate:     stored block%s\n",
    00147                  s->last ? " (last)" : ""));
    00148           DUMPBITS(3)
    00149           t = k & 7;                    /* go to byte boundary */
    00150           DUMPBITS(t)
    00151           s->mode = LENS;               /* get length of stored block */
    00152           break;
    00153         case 1:                         /* fixed */
    00154           Tracev((stderr, "inflate:     fixed codes block%s\n",
    00155                  s->last ? " (last)" : ""));
    00156           {
    00157             uInt bl, bd;
    00158             inflate_huft *tl, *td;
    00159
    00160             inflate_trees_fixed(&bl, &bd, &tl, &td, z);
    00161             s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
    00162             if (s->sub.decode.codes == Z_NULL)
    00163             {
    00164               r = Z_MEM_ERROR;
    00165               LEAVE
    00166             }
    00167           }
    00168           DUMPBITS(3)
    00169           s->mode = CODES;
    00170           break;
    00171         case 2:                         /* dynamic */
    00172           Tracev((stderr, "inflate:     dynamic codes block%s\n",
    00173                  s->last ? " (last)" : ""));
    00174           DUMPBITS(3)
    00175           s->mode = TABLE;
    00176           break;
    00177         case 3:                         /* illegal */
    00178           DUMPBITS(3)
    00179           s->mode = BAD;
    00180           z->msg = (char*)"invalid block type";
    00181           r = Z_DATA_ERROR;
    00182           LEAVE
    00183       }
    00184       break;
    00185     case LENS:
    00186       NEEDBITS(32)
    00187       if ((((~b) >> 16) & 0xffff) != (b & 0xffff))
    00188       {
    00189         s->mode = BAD;
    00190         z->msg = (char*)"invalid stored block lengths";
    00191         r = Z_DATA_ERROR;
    00192         LEAVE
    00193       }
    00194       s->sub.left = (uInt)b & 0xffff;
    00195       b = k = 0;                      /* dump bits */
    00196       Tracev((stderr, "inflate:       stored length %u\n", s->sub.left));
    00197       s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE);
    00198       break;
    00199     case STORED:
    00200       if (n == 0)
    00201         LEAVE
    00202       NEEDOUT
    00203       t = s->sub.left;
    00204       if (t > n) t = n;
    00205       if (t > m) t = m;
    00206       zmemcpy(q, p, t);
    00207       p += t;  n -= t;
    00208       q += t;  m -= t;
    00209       if ((s->sub.left -= t) != 0)
    00210         break;
    00211       Tracev((stderr, "inflate:       stored end, %lu total out\n",
    00212               z->total_out + (q >= s->read ? q - s->read :
    00213               (s->end - s->read) + (q - s->window))));
    00214       s->mode = s->last ? DRY : TYPE;
    00215       break;
    00216     case TABLE:
    00217       NEEDBITS(14)
    00218       s->sub.trees.table = t = (uInt)b & 0x3fff;
    00219 #ifndef PKZIP_BUG_WORKAROUND
    00220       if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
    00221       {
    00222         s->mode = BAD;
    00223         z->msg = (char*)"too many length or distance symbols";
    00224         r = Z_DATA_ERROR;
    00225         LEAVE
    00226       }
    00227 #endif
    00228       t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
    00229       if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
    00230       {
    00231         r = Z_MEM_ERROR;
    00232         LEAVE
    00233       }
    00234       DUMPBITS(14)
    00235       s->sub.trees.index = 0;
    00236       Tracev((stderr, "inflate:       table sizes ok\n"));
    00237       s->mode = BTREE;
    00238     case BTREE:
    00239       while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
    00240       {
    00241         NEEDBITS(3)
    00242         s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
    00243         DUMPBITS(3)
    00244       }
    00245       while (s->sub.trees.index < 19)
    00246         s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
    00247       s->sub.trees.bb = 7;
    00248       t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
    00249                              &s->sub.trees.tb, s->hufts, z);
    00250       if (t != Z_OK)
    00251       {
    00252         r = t;
    00253         if (r == Z_DATA_ERROR)
    00254         {
    00255           ZFREE(z, s->sub.trees.blens);
    00256           s->mode = BAD;
    00257         }
    00258         LEAVE
    00259       }
    00260       s->sub.trees.index = 0;
    00261       Tracev((stderr, "inflate:       bits tree ok\n"));
    00262       s->mode = DTREE;
    00263     case DTREE:
    00264       while (t = s->sub.trees.table,
    00265              s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
    00266       {
    00267         inflate_huft *h;
    00268         uInt i, j, c;
    00269
    00270         t = s->sub.trees.bb;
    00271         NEEDBITS(t)
    00272         h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
    00273         t = h->bits;
    00274         c = h->base;
    00275         if (c < 16)
    00276         {
    00277           DUMPBITS(t)
    00278           s->sub.trees.blens[s->sub.trees.index++] = c;
    00279         }
    00280         else /* c == 16..18 */
    00281         {
    00282           i = c == 18 ? 7 : c - 14;
    00283           j = c == 18 ? 11 : 3;
    00284           NEEDBITS(t + i)
    00285           DUMPBITS(t)
    00286           j += (uInt)b & inflate_mask[i];
    00287           DUMPBITS(i)
    00288           i = s->sub.trees.index;
    00289           t = s->sub.trees.table;
    00290           if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
    00291               (c == 16 && i < 1))
    00292           {
    00293             ZFREE(z, s->sub.trees.blens);
    00294             s->mode = BAD;
    00295             z->msg = (char*)"invalid bit length repeat";
    00296             r = Z_DATA_ERROR;
    00297             LEAVE
    00298           }
    00299           c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
    00300           do {
    00301             s->sub.trees.blens[i++] = c;
    00302           } while (--j);
    00303           s->sub.trees.index = i;
    00304         }
    00305       }
    00306       s->sub.trees.tb = Z_NULL;
    00307       {
    00308         uInt bl, bd;
    00309         inflate_huft *tl, *td;
    00310         inflate_codes_statef *c;
    00311
    00312         bl = 9;         /* must be <= 9 for lookahead assumptions */
    00313         bd = 6;         /* must be <= 9 for lookahead assumptions */
    00314         t = s->sub.trees.table;
    00315         t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
    00316                                   s->sub.trees.blens, &bl, &bd, &tl, &td,
    00317                                   s->hufts, z);
    00318         if (t != Z_OK)
    00319         {
    00320           if (t == (uInt)Z_DATA_ERROR)
    00321           {
    00322             ZFREE(z, s->sub.trees.blens);
    00323             s->mode = BAD;
    00324           }
    00325           r = t;
    00326           LEAVE
    00327         }
    00328         Tracev((stderr, "inflate:       trees ok\n"));
    00329         if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
    00330         {
    00331           r = Z_MEM_ERROR;
    00332           LEAVE
    00333         }
    00334         s->sub.decode.codes = c;
    00335       }
    00336       ZFREE(z, s->sub.trees.blens);
    00337       s->mode = CODES;
    00338     case CODES:
    00339       UPDATE
    00340       if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
    00341         return inflate_flush(s, z, r);
    00342       r = Z_OK;
    00343       inflate_codes_free(s->sub.decode.codes, z);
    00344       LOAD
    00345       Tracev((stderr, "inflate:       codes end, %lu total out\n",
    00346               z->total_out + (q >= s->read ? q - s->read :
    00347               (s->end - s->read) + (q - s->window))));
    00348       if (!s->last)
    00349       {
    00350         s->mode = TYPE;
    00351         break;
    00352       }
    00353       s->mode = DRY;
    00354     case DRY:
    00355       FLUSH
    00356       if (s->read != s->write)
    00357         LEAVE
    00358       s->mode = DONE;
    00359     case DONE:
    00360       r = Z_STREAM_END;
    00361       LEAVE
    00362     case BAD:
    00363       r = Z_DATA_ERROR;
    00364       LEAVE
    00365     default:
    00366       r = Z_STREAM_ERROR;
    00367       LEAVE
    00368   }
    00369 }
    00370
    00371
    00372 int inflate_blocks_free(s, z)
    00373 inflate_blocks_statef *s;
    00374 z_streamp z;
    00375 {
    00376   inflate_blocks_reset(s, z, Z_NULL);
    00377   ZFREE(z, s->window);
    00378   ZFREE(z, s->hufts);
    00379   ZFREE(z, s);
    00380   Tracev((stderr, "inflate:   blocks freed\n"));
    00381   return Z_OK;
    00382 }
    00383
    00384
    00385 void inflate_set_dictionary(s, d, n)
    00386 inflate_blocks_statef *s;
    00387 const Bytef *d;
    00388 uInt  n;
    00389 {
    00390   zmemcpy(s->window, d, n);
    00391   s->read = s->write = s->window + n;
    00392 }
    00393
    00394
    00395 /* Returns true if inflate is currently at the end of a block generated
    00396  * by Z_SYNC_FLUSH or Z_FULL_FLUSH.
    00397  * IN assertion: s != Z_NULL
    00398  */
    00399 int inflate_blocks_sync_point(s)
    00400 inflate_blocks_statef *s;
    00401 {
    00402   return s->mode == LENS;
    00403 }