infblock.c

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

FreeBSD/Linux Kernel Cross Reference
sys/lib/libz/infblock.c
