git.oblomov.eu Git - linux-2.6/blob - lib/zlib_inflate/infblock.c

   1 /* infblock.c -- interpret and process block types to last block
   2  * Copyright (C) 1995-1998 Mark Adler
   3  * For conditions of distribution and use, see copyright notice in zlib.h
   4  */
   5
   6 #include <linux/zutil.h>
   7 #include "infblock.h"
   8 #include "inftrees.h"
   9 #include "infcodes.h"
  10 #include "infutil.h"
  11
  12 struct inflate_codes_state;
  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 static 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 void zlib_inflate_blocks_reset(
  69         inflate_blocks_statef *s,
  70         z_streamp z,
  71         uLong *c
  72 )
  73 {
  74   if (c != NULL)
  75     *c = s->check;
  76   if (s->mode == CODES)
  77     zlib_inflate_codes_free(s->sub.decode.codes, z);
  78   s->mode = TYPE;
  79   s->bitk = 0;
  80   s->bitb = 0;
  81   s->read = s->write = s->window;
  82   if (s->checkfn != NULL)
  83     z->adler = s->check = (*s->checkfn)(0L, NULL, 0);
  84 }
  85
  86 inflate_blocks_statef *zlib_inflate_blocks_new(
  87         z_streamp z,
  88         check_func c,
  89         uInt w
  90 )
  91 {
  92   inflate_blocks_statef *s;
  93
  94   s = &WS(z)->working_blocks_state;
  95   s->hufts = WS(z)->working_hufts;
  96   s->window = WS(z)->working_window;
  97   s->end = s->window + w;
  98   s->checkfn = c;
  99   s->mode = TYPE;
 100   zlib_inflate_blocks_reset(s, z, NULL);
 101   return s;
 102 }
 103
 104
 105 int zlib_inflate_blocks(
 106         inflate_blocks_statef *s,
 107         z_streamp z,
 108         int r
 109 )
 110 {
 111   uInt t;               /* temporary storage */
 112   uLong b;              /* bit buffer */
 113   uInt k;               /* bits in bit buffer */
 114   Byte *p;              /* input data pointer */
 115   uInt n;               /* bytes available there */
 116   Byte *q;              /* output window write pointer */
 117   uInt m;               /* bytes to end of window or read pointer */
 118
 119   /* copy input/output information to locals (UPDATE macro restores) */
 120   LOAD
 121
 122   /* process input based on current state */
 123   while (1) switch (s->mode)
 124   {
 125     case TYPE:
 126       NEEDBITS(3)
 127       t = (uInt)b & 7;
 128       s->last = t & 1;
 129       switch (t >> 1)
 130       {
 131         case 0:                         /* stored */
 132           DUMPBITS(3)
 133           t = k & 7;                    /* go to byte boundary */
 134           DUMPBITS(t)
 135           s->mode = LENS;               /* get length of stored block */
 136           break;
 137         case 1:                         /* fixed */
 138           {
 139             uInt bl, bd;
 140             inflate_huft *tl, *td;
 141
 142             zlib_inflate_trees_fixed(&bl, &bd, &tl, &td, s->hufts, z);
 143             s->sub.decode.codes = zlib_inflate_codes_new(bl, bd, tl, td, z);
 144             if (s->sub.decode.codes == NULL)
 145             {
 146               r = Z_MEM_ERROR;
 147               LEAVE
 148             }
 149           }
 150           DUMPBITS(3)
 151           s->mode = CODES;
 152           break;
 153         case 2:                         /* dynamic */
 154           DUMPBITS(3)
 155           s->mode = TABLE;
 156           break;
 157         case 3:                         /* illegal */
 158           DUMPBITS(3)
 159           s->mode = B_BAD;
 160           z->msg = (char*)"invalid block type";
 161           r = Z_DATA_ERROR;
 162           LEAVE
 163       }
 164       break;
 165     case LENS:
 166       NEEDBITS(32)
 167       if ((((~b) >> 16) & 0xffff) != (b & 0xffff))
 168       {
 169         s->mode = B_BAD;
 170         z->msg = (char*)"invalid stored block lengths";
 171         r = Z_DATA_ERROR;
 172         LEAVE
 173       }
 174       s->sub.left = (uInt)b & 0xffff;
 175       b = k = 0;                      /* dump bits */
 176       s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE);
 177       break;
 178     case STORED:
 179       if (n == 0)
 180         LEAVE
 181       NEEDOUT
 182       t = s->sub.left;
 183       if (t > n) t = n;
 184       if (t > m) t = m;
 185       memcpy(q, p, t);
 186       p += t;  n -= t;
 187       q += t;  m -= t;
 188       if ((s->sub.left -= t) != 0)
 189         break;
 190       s->mode = s->last ? DRY : TYPE;
 191       break;
 192     case TABLE:
 193       NEEDBITS(14)
 194       s->sub.trees.table = t = (uInt)b & 0x3fff;
 195 #ifndef PKZIP_BUG_WORKAROUND
 196       if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
 197       {
 198         s->mode = B_BAD;
 199         z->msg = (char*)"too many length or distance symbols";
 200         r = Z_DATA_ERROR;
 201         LEAVE
 202       }
 203 #endif
 204       {
 205         s->sub.trees.blens = WS(z)->working_blens;
 206       }
 207       DUMPBITS(14)
 208       s->sub.trees.index = 0;
 209       s->mode = BTREE;
 210     case BTREE:
 211       while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
 212       {
 213         NEEDBITS(3)
 214         s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
 215         DUMPBITS(3)
 216       }
 217       while (s->sub.trees.index < 19)
 218         s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
 219       s->sub.trees.bb = 7;
 220       t = zlib_inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
 221                                   &s->sub.trees.tb, s->hufts, z);
 222       if (t != Z_OK)
 223       {
 224         r = t;
 225         if (r == Z_DATA_ERROR)
 226           s->mode = B_BAD;
 227         LEAVE
 228       }
 229       s->sub.trees.index = 0;
 230       s->mode = DTREE;
 231     case DTREE:
 232       while (t = s->sub.trees.table,
 233              s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
 234       {
 235         inflate_huft *h;
 236         uInt i, j, c;
 237
 238         t = s->sub.trees.bb;
 239         NEEDBITS(t)
 240         h = s->sub.trees.tb + ((uInt)b & zlib_inflate_mask[t]);
 241         t = h->bits;
 242         c = h->base;
 243         if (c < 16)
 244         {
 245           DUMPBITS(t)
 246           s->sub.trees.blens[s->sub.trees.index++] = c;
 247         }
 248         else /* c == 16..18 */
 249         {
 250           i = c == 18 ? 7 : c - 14;
 251           j = c == 18 ? 11 : 3;
 252           NEEDBITS(t + i)
 253           DUMPBITS(t)
 254           j += (uInt)b & zlib_inflate_mask[i];
 255           DUMPBITS(i)
 256           i = s->sub.trees.index;
 257           t = s->sub.trees.table;
 258           if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
 259               (c == 16 && i < 1))
 260           {
 261             s->mode = B_BAD;
 262             z->msg = (char*)"invalid bit length repeat";
 263             r = Z_DATA_ERROR;
 264             LEAVE
 265           }
 266           c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
 267           do {
 268             s->sub.trees.blens[i++] = c;
 269           } while (--j);
 270           s->sub.trees.index = i;
 271         }
 272       }
 273       s->sub.trees.tb = NULL;
 274       {
 275         uInt bl, bd;
 276         inflate_huft *tl, *td;
 277         inflate_codes_statef *c;
 278
 279         bl = 9;         /* must be <= 9 for lookahead assumptions */
 280         bd = 6;         /* must be <= 9 for lookahead assumptions */
 281         t = s->sub.trees.table;
 282         t = zlib_inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
 283                                        s->sub.trees.blens, &bl, &bd, &tl, &td,
 284                                        s->hufts, z);
 285         if (t != Z_OK)
 286         {
 287           if (t == (uInt)Z_DATA_ERROR)
 288             s->mode = B_BAD;
 289           r = t;
 290           LEAVE
 291         }
 292         if ((c = zlib_inflate_codes_new(bl, bd, tl, td, z)) == NULL)
 293         {
 294           r = Z_MEM_ERROR;
 295           LEAVE
 296         }
 297         s->sub.decode.codes = c;
 298       }
 299       s->mode = CODES;
 300     case CODES:
 301       UPDATE
 302       if ((r = zlib_inflate_codes(s, z, r)) != Z_STREAM_END)
 303         return zlib_inflate_flush(s, z, r);
 304       r = Z_OK;
 305       zlib_inflate_codes_free(s->sub.decode.codes, z);
 306       LOAD
 307       if (!s->last)
 308       {
 309         s->mode = TYPE;
 310         break;
 311       }
 312       s->mode = DRY;
 313     case DRY:
 314       FLUSH
 315       if (s->read != s->write)
 316         LEAVE
 317       s->mode = B_DONE;
 318     case B_DONE:
 319       r = Z_STREAM_END;
 320       LEAVE
 321     case B_BAD:
 322       r = Z_DATA_ERROR;
 323       LEAVE
 324     default:
 325       r = Z_STREAM_ERROR;
 326       LEAVE
 327   }
 328 }
 329
 330
 331 int zlib_inflate_blocks_free(
 332         inflate_blocks_statef *s,
 333         z_streamp z
 334 )
 335 {
 336   zlib_inflate_blocks_reset(s, z, NULL);
 337   return Z_OK;
 338 }
 339
 340
 341 #if 0
 342 void zlib_inflate_set_dictionary(
 343         inflate_blocks_statef *s,
 344         const Byte *d,
 345         uInt  n
 346 )
 347 {
 348   memcpy(s->window, d, n);
 349   s->read = s->write = s->window + n;
 350 }
 351 #endif  /*  0  */
 352
 353
 354 /* Returns true if inflate is currently at the end of a block generated
 355  * by Z_SYNC_FLUSH or Z_FULL_FLUSH.
 356  * IN assertion: s != NULL
 357  */
 358 #if 0
 359 int zlib_inflate_blocks_sync_point(
 360         inflate_blocks_statef *s
 361 )
 362 {
 363   return s->mode == LENS;
 364 }
 365 #endif  /*  0  */