Back to index

plt-scheme  4.2.1
infblock.c
Go to the documentation of this file.
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 }