Back to index

avfs  1.0.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 #include <assert.h>
00013 
00014 struct inflate_codes_state {int dummy;}; /* for buggy compilers */
00015 
00016 /* simplify the use of the inflate_huft type with some defines */
00017 #define exop word.what.Exop
00018 #define bits word.what.Bits
00019 
00020 /* Table for deflate from PKZIP's appnote.txt. */
00021 local const uInt border[] = { /* Order of the bit length code lengths */
00022         16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
00023 
00024 /*
00025    Notes beyond the 1.93a appnote.txt:
00026 
00027    1. Distance pointers never point before the beginning of the output
00028       stream.
00029    2. Distance pointers can point back across blocks, up to 32k away.
00030    3. There is an implied maximum of 7 bits for the bit length table and
00031       15 bits for the actual data.
00032    4. If only one code exists, then it is encoded using one bit.  (Zero
00033       would be more efficient, but perhaps a little confusing.)  If two
00034       codes exist, they are coded using one bit each (0 and 1).
00035    5. There is no way of sending zero distance codes--a dummy must be
00036       sent if there are none.  (History: a pre 2.0 version of PKZIP would
00037       store blocks with no distance codes, but this was discovered to be
00038       too harsh a criterion.)  Valid only for 1.93a.  2.04c does allow
00039       zero distance codes, which is sent as one code of zero bits in
00040       length.
00041    6. There are up to 286 literal/length codes.  Code 256 represents the
00042       end-of-block.  Note however that the static length tree defines
00043       288 codes just to fill out the Huffman codes.  Codes 286 and 287
00044       cannot be used though, since there is no length base or extra bits
00045       defined for them.  Similarily, there are up to 30 distance codes.
00046       However, static trees define 32 codes (all 5 bits) to fill out the
00047       Huffman codes, but the last two had better not show up in the data.
00048    7. Unzip can check dynamic Huffman blocks for complete code sets.
00049       The exception is that a single code would not be complete (see #4).
00050    8. The five bits following the block type is really the number of
00051       literal codes sent minus 257.
00052    9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
00053       (1+6+6).  Therefore, to output three times the length, you output
00054       three codes (1+1+1), whereas to output four times the same length,
00055       you only need two codes (1+3).  Hmm.
00056   10. In the tree reconstruction algorithm, Code = Code + Increment
00057       only if BitLength(i) is not zero.  (Pretty obvious.)
00058   11. Correction: 4 Bits: # of Bit Length codes - 4     (4 - 19)
00059   12. Note: length code 284 can represent 227-258, but length code 285
00060       really is 258.  The last length deserves its own, short code
00061       since it gets used a lot in very redundant files.  The length
00062       258 is special since 258 - 3 (the min match length) is 255.
00063   13. The literal/length and distance code bit lengths are read as a
00064       single stream of lengths.  It is possible (and advantageous) for
00065       a repeat code (16, 17, or 18) to go across the boundary between
00066       the two sets of lengths.
00067  */
00068 
00069 
00070 void inflate_blocks_reset(s, z, c)
00071 inflate_blocks_statef *s;
00072 z_streamp z;
00073 uLongf *c;
00074 {
00075   if (c != Z_NULL)
00076     *c = s->check;
00077   if (s->mode == BTREE || s->mode == DTREE)
00078     ZFREE(z, s->sub.trees.blens);
00079   if (s->mode == CODES)
00080     inflate_codes_free(s->sub.decode.codes, z);
00081   s->mode = TYPE;
00082   s->bitk = 0;
00083   s->bitb = 0;
00084   s->read = s->write = s->window;
00085   if (s->checkfn != Z_NULL)
00086     z->adler = s->check = (*s->checkfn)(0L, (const Bytef *)Z_NULL, 0);
00087   Tracev((stderr, "inflate:   blocks reset\n"));
00088 }
00089 
00090 
00091 inflate_blocks_statef *inflate_blocks_new(z, c, w)
00092 z_streamp z;
00093 check_func c;
00094 uInt w;
00095 {
00096   inflate_blocks_statef *s;
00097 
00098   if ((s = (inflate_blocks_statef *)ZALLOC
00099        (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
00100     return s;
00101   if ((s->hufts =
00102        (inflate_huft *)ZALLOC(z, sizeof(inflate_huft), MANY)) == Z_NULL)
00103   {
00104     ZFREE(z, s);
00105     return Z_NULL;
00106   }
00107   if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
00108   {
00109     ZFREE(z, s->hufts);
00110     ZFREE(z, s);
00111     return Z_NULL;
00112   }
00113   s->end = s->window + w;
00114   s->checkfn = c;
00115   s->mode = TYPE;
00116   Tracev((stderr, "inflate:   blocks allocated\n"));
00117   inflate_blocks_reset(s, z, Z_NULL);
00118   return s;
00119 }
00120 
00121 
00122 int inflate_blocks(s, z, r)
00123 inflate_blocks_statef *s;
00124 z_streamp z;
00125 int r;
00126 {
00127   uInt t;               /* temporary storage */
00128   uLong b;              /* bit buffer */
00129   uInt k;               /* bits in bit buffer */
00130   Bytef *p;             /* input data pointer */
00131   uInt n;               /* bytes available there */
00132   Bytef *q;             /* output window write pointer */
00133   uInt m;               /* bytes to end of window or read pointer */
00134 
00135   /* copy input/output information to locals (UPDATE macro restores) */
00136   LOAD
00137 
00138   /* process input based on current state */
00139   while (1) switch (s->mode)
00140   {
00141     case TYPE:
00142       NEEDBITS(3)
00143       t = (uInt)b & 7;
00144       s->last = t & 1;
00145       switch (t >> 1)
00146       {
00147         case 0:                         /* stored */
00148           Tracev((stderr, "inflate:     stored block%s\n",
00149                  s->last ? " (last)" : ""));
00150           DUMPBITS(3)
00151           t = k & 7;                    /* go to byte boundary */
00152           DUMPBITS(t)
00153           s->mode = LENS;               /* get length of stored block */
00154           break;
00155         case 1:                         /* fixed */
00156           Tracev((stderr, "inflate:     fixed codes block%s\n",
00157                  s->last ? " (last)" : ""));
00158           {
00159             uInt bl, bd;
00160             inflate_huft *tl, *td;
00161 
00162             inflate_trees_fixed(&bl, &bd, &tl, &td, z);
00163             s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
00164             if (s->sub.decode.codes == Z_NULL)
00165             {
00166               r = Z_MEM_ERROR;
00167               LEAVE
00168             }
00169           }
00170           DUMPBITS(3)
00171           s->mode = CODES;
00172           break;
00173         case 2:                         /* dynamic */
00174           Tracev((stderr, "inflate:     dynamic codes block%s\n",
00175                  s->last ? " (last)" : ""));
00176           DUMPBITS(3)
00177           s->mode = TABLE;
00178           break;
00179         case 3:                         /* illegal */
00180           DUMPBITS(3)
00181           s->mode = BAD;
00182           z->msg = (char*)"invalid block type";
00183           r = Z_DATA_ERROR;
00184           LEAVE
00185       }
00186       break;
00187     case LENS:
00188       NEEDBITS(32)
00189       if ((((~b) >> 16) & 0xffff) != (b & 0xffff))
00190       {
00191         s->mode = BAD;
00192         z->msg = (char*)"invalid stored block lengths";
00193         r = Z_DATA_ERROR;
00194         LEAVE
00195       }
00196       s->sub.left = (uInt)b & 0xffff;
00197       b = k = 0;                      /* dump bits */
00198       Tracev((stderr, "inflate:       stored length %u\n", s->sub.left));
00199       s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE);
00200       break;
00201     case STORED:
00202       if (n == 0)
00203         LEAVE
00204       NEEDOUT
00205       t = s->sub.left;
00206       if (t > n) t = n;
00207       if (t > m) t = m;
00208       zmemcpy(q, p, t);
00209       p += t;  n -= t;
00210       q += t;  m -= t;
00211       if ((s->sub.left -= t) != 0)
00212         break;
00213       Tracev((stderr, "inflate:       stored end, %lu total out\n",
00214               z->total_out + (q >= s->read ? q - s->read :
00215               (s->end - s->read) + (q - s->window))));
00216       s->mode = s->last ? DRY : TYPE;
00217       break;
00218     case TABLE:
00219       NEEDBITS(14)
00220       s->sub.trees.table = t = (uInt)b & 0x3fff;
00221 #ifndef PKZIP_BUG_WORKAROUND
00222       if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
00223       {
00224         s->mode = BAD;
00225         z->msg = (char*)"too many length or distance symbols";
00226         r = Z_DATA_ERROR;
00227         LEAVE
00228       }
00229 #endif
00230       t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
00231       if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
00232       {
00233         r = Z_MEM_ERROR;
00234         LEAVE
00235       }
00236       DUMPBITS(14)
00237       s->sub.trees.index = 0;
00238       Tracev((stderr, "inflate:       table sizes ok\n"));
00239       s->mode = BTREE;
00240     case BTREE:
00241       while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
00242       {
00243         NEEDBITS(3)
00244         s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
00245         DUMPBITS(3)
00246       }
00247       while (s->sub.trees.index < 19)
00248         s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
00249       s->sub.trees.bb = 7;
00250       t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
00251                              &s->sub.trees.tb, s->hufts, z);
00252       if (t != Z_OK)
00253       {
00254         r = t;
00255         if (r == Z_DATA_ERROR)
00256         {
00257           ZFREE(z, s->sub.trees.blens);
00258           s->mode = BAD;
00259         }
00260         LEAVE
00261       }
00262       s->sub.trees.index = 0;
00263       Tracev((stderr, "inflate:       bits tree ok\n"));
00264       s->mode = DTREE;
00265     case DTREE:
00266       while (t = s->sub.trees.table,
00267              s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
00268       {
00269         inflate_huft *h;
00270         uInt i, j, c;
00271 
00272         t = s->sub.trees.bb;
00273         NEEDBITS(t)
00274         h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
00275         t = h->bits;
00276         c = h->base;
00277         if (c < 16)
00278         {
00279           DUMPBITS(t)
00280           s->sub.trees.blens[s->sub.trees.index++] = c;
00281         }
00282         else /* c == 16..18 */
00283         {
00284           i = c == 18 ? 7 : c - 14;
00285           j = c == 18 ? 11 : 3;
00286           NEEDBITS(t + i)
00287           DUMPBITS(t)
00288           j += (uInt)b & inflate_mask[i];
00289           DUMPBITS(i)
00290           i = s->sub.trees.index;
00291           t = s->sub.trees.table;
00292           if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
00293               (c == 16 && i < 1))
00294           {
00295             ZFREE(z, s->sub.trees.blens);
00296             s->mode = BAD;
00297             z->msg = (char*)"invalid bit length repeat";
00298             r = Z_DATA_ERROR;
00299             LEAVE
00300           }
00301           c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
00302           do {
00303             s->sub.trees.blens[i++] = c;
00304           } while (--j);
00305           s->sub.trees.index = i;
00306         }
00307       }
00308       s->sub.trees.tb = Z_NULL;
00309       {
00310         uInt bl, bd;
00311         inflate_huft *tl, *td;
00312         inflate_codes_statef *c;
00313 
00314         bl = 9;         /* must be <= 9 for lookahead assumptions */
00315         bd = 6;         /* must be <= 9 for lookahead assumptions */
00316         t = s->sub.trees.table;
00317         t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
00318                                   s->sub.trees.blens, &bl, &bd, &tl, &td,
00319                                   s->hufts, z);
00320         if (t != Z_OK)
00321         {
00322           if (t == (uInt)Z_DATA_ERROR)
00323           {
00324             ZFREE(z, s->sub.trees.blens);
00325             s->mode = BAD;
00326           }
00327           r = t;
00328           LEAVE
00329         }
00330         Tracev((stderr, "inflate:       trees ok\n"));
00331         if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
00332         {
00333           r = Z_MEM_ERROR;
00334           LEAVE
00335         }
00336         s->sub.decode.codes = c;
00337       }
00338       ZFREE(z, s->sub.trees.blens);
00339       s->mode = CODES;
00340     case CODES:
00341       UPDATE
00342       if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
00343         return inflate_flush(s, z, r);
00344       r = Z_OK;
00345       inflate_codes_free(s->sub.decode.codes, z);
00346       LOAD
00347       Tracev((stderr, "inflate:       codes end, %lu total out\n",
00348               z->total_out + (q >= s->read ? q - s->read :
00349               (s->end - s->read) + (q - s->window))));
00350       if (!s->last)
00351       {
00352         s->mode = TYPE;
00353         break;
00354       }
00355       s->mode = DRY;
00356     case DRY:
00357       FLUSH
00358       if (s->read != s->write)
00359         LEAVE
00360       s->mode = DONE;
00361     case DONE:
00362       r = Z_STREAM_END;
00363       LEAVE
00364     case BAD:
00365       r = Z_DATA_ERROR;
00366       LEAVE
00367     default:
00368       r = Z_STREAM_ERROR;
00369       LEAVE
00370   }
00371 }
00372 
00373 
00374 int inflate_blocks_free(s, z)
00375 inflate_blocks_statef *s;
00376 z_streamp z;
00377 {
00378   inflate_blocks_reset(s, z, Z_NULL);
00379   ZFREE(z, s->window);
00380   ZFREE(z, s->hufts);
00381   ZFREE(z, s);
00382   Tracev((stderr, "inflate:   blocks freed\n"));
00383   return Z_OK;
00384 }
00385 
00386 
00387 void inflate_set_dictionary(s, d, n)
00388 inflate_blocks_statef *s;
00389 const Bytef *d;
00390 uInt  n;
00391 {
00392   zmemcpy(s->window, d, n);
00393   s->read = s->write = s->window + n;
00394 }
00395 
00396 
00397 /* Returns true if inflate is currently at the end of a block generated
00398  * by Z_SYNC_FLUSH or Z_FULL_FLUSH. 
00399  * IN assertion: s != Z_NULL
00400  */
00401 int inflate_blocks_sync_point(s)
00402 inflate_blocks_statef *s;
00403 {
00404   return s->mode == LENS;
00405 }
00406 
00407 int inflate_blocks_save(bufp, at, s, z, w)
00408 char **bufp;
00409 int at;
00410 inflate_blocks_statef *s;
00411 z_streamp z;
00412 uInt w;
00413 {
00414   char *buf = *bufp;
00415   struct inflate_blocks_state scpy = *s;
00416   uInt t;
00417   unsigned len = 0;
00418 
00419   len += sizeof(struct inflate_blocks_state);
00420   
00421   if (s->mode == BTREE || s->mode == DTREE) {
00422     assert(s->sub.trees.blens != NULL);
00423     scpy.sub.trees.blens = NULL;
00424 
00425     t = s->sub.trees.table;
00426     t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
00427 
00428     len += t * sizeof(uInt);
00429 
00430     assert(s->sub.trees.tb == NULL || 
00431            (s->sub.trees.tb >= s->hufts && s->sub.trees.tb < s->hufts + MANY));
00432 
00433     scpy.sub.trees.tb = (inflate_huft *) 
00434       (s->sub.trees.tb == NULL ? -1 : ((long) s->sub.trees.tb - (long) s->hufts));
00435   }
00436   if (s->mode == CODES) {
00437     assert(s->sub.decode.codes != NULL);
00438     scpy.sub.decode.codes = NULL;
00439   }
00440 
00441   assert(s->hufts != NULL);
00442   scpy.hufts = NULL;
00443   
00444   assert(s->window != NULL);
00445   scpy.window = NULL;
00446   
00447   assert(s->end >= s->window && s->end <= s->window + w);
00448   scpy.end = (Bytef *) (s->end - s->window);
00449 
00450   assert(s->read >= s->window && s->read <= s->window + w);
00451   scpy.read = (Bytef *) (s->read - s->window);
00452 
00453   assert(s->write >= s->window && s->write <= s->window + w);
00454   scpy.write = (Bytef *) (s->write - s->window);
00455 
00456   scpy.checkfn = NULL;
00457 
00458   len += sizeof(inflate_huft) * MANY;
00459   len += w;
00460 
00461   *bufp = buf = realloc(buf, at + len);
00462   if(buf == NULL)
00463       return Z_MEM_ERROR;
00464 
00465   memcpy(buf + at, &scpy, sizeof(struct inflate_blocks_state));
00466   at += sizeof(struct inflate_blocks_state);
00467 
00468   if (s->mode == BTREE || s->mode == DTREE) {
00469     t = s->sub.trees.table;
00470     t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
00471 
00472     memcpy(buf + at, s->sub.trees.blens, t * sizeof(uInt));
00473     at += t * sizeof(uInt);
00474   }
00475   
00476   memcpy(buf + at, s->hufts, sizeof(inflate_huft) * MANY);
00477   at += sizeof(inflate_huft) * MANY;
00478 
00479   memcpy(buf + at, s->window, w);
00480   at += w;
00481 
00482   if (s->mode == CODES) {
00483     at = inflate_codes_save(bufp, at, s, z);
00484     if(at < 0)
00485       return at;
00486   }
00487 
00488   return at;
00489 }
00490 
00491 inflate_blocks_statef * inflate_blocks_restore(bufp, z, c, w)
00492   char **bufp;
00493   z_streamp z;
00494   check_func c;
00495   uInt w;
00496 {
00497   inflate_blocks_statef *s;
00498   uInt t;
00499   char *buf = *bufp;
00500 
00501   if ((s = (inflate_blocks_statef *)ZALLOC
00502        (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
00503     return s;
00504 
00505   memcpy(s, buf, sizeof(struct inflate_blocks_state));
00506   buf += sizeof(struct inflate_blocks_state);
00507 
00508   if ((s->hufts =
00509        (inflate_huft *)ZALLOC(z, sizeof(inflate_huft), MANY)) == Z_NULL)
00510   {
00511     ZFREE(z, s);
00512     return Z_NULL;
00513   }
00514   if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
00515   {
00516     ZFREE(z, s->hufts);
00517     ZFREE(z, s);
00518     return Z_NULL;
00519   }
00520   
00521   if (s->mode == BTREE || s->mode == DTREE) {
00522     t = s->sub.trees.table;
00523     t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
00524 
00525     if((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
00526     {
00527       ZFREE(z, s->window);
00528       ZFREE(z, s->hufts);
00529       ZFREE(z, s);
00530       return Z_NULL;
00531     }
00532 
00533     memcpy(s->sub.trees.blens, buf, t * sizeof(uInt));
00534     buf += t * sizeof(uInt);
00535 
00536     if(s->sub.trees.tb == (inflate_huft *) -1)
00537       s->sub.trees.tb = NULL;
00538     else
00539       s->sub.trees.tb = (inflate_huft *) ((long) s->hufts + (long) s->sub.trees.tb);
00540   }
00541 
00542   memcpy(s->hufts, buf, sizeof(inflate_huft) * MANY);
00543   buf += sizeof(inflate_huft) * MANY;
00544 
00545   memcpy(s->window, buf, w);
00546   buf += w;
00547 
00548   s->end = s->window + (long) s->end;
00549   s->read = s->window + (long) s->read;
00550   s->write = s->window + (long) s->write;
00551   s->checkfn = c;
00552 
00553   *bufp = buf;
00554   
00555   if (s->mode == CODES) {
00556     s->sub.decode.codes = inflate_codes_restore(bufp, s, z);
00557     if(s->sub.decode.codes == Z_NULL) {
00558       inflate_blocks_free(s, z);
00559       return Z_NULL;
00560     }
00561   }
00562 
00563   return s;  
00564 }
00565