1 /* infcodes.c -- process literals and length/distance pairs 2 * Copyright (C) 1995-2002 Mark Adler 3 * For conditions of distribution and use, see copyright notice in zlib.h 4 */ 5 6 #include "zutil.h" 7 #include "inftrees.h" 8 #include "infblock.h" 9 #include "infcodes.h" 10 #include "infutil.h" 11 12 /* simplify the use of the inflate_huft type with some defines */ 13 #define exop word.what.Exop 14 #define bits word.what.Bits 15 16 typedef enum { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ 17 START, /* x: set up for LEN */ 18 LEN, /* i: get length/literal/eob next */ 19 LENEXT, /* i: getting length extra (have base) */ 20 DIST, /* i: get distance next */ 21 DISTEXT, /* i: getting distance extra */ 22 COPY, /* o: copying bytes in window, waiting for space */ 23 LIT, /* o: got literal, waiting for output space */ 24 WASH, /* o: got eob, possibly still output waiting */ 25 END, /* x: got eob and all data flushed */ 26 BADCODE} /* x: got error */ 27 inflate_codes_mode; 28 29 /* inflate codes private state */ 30 struct inflate_codes_state { 31 32 /* mode */ 33 inflate_codes_mode mode; /* current inflate_codes mode */ 34 35 /* mode dependent information */ 36 uInt len; 37 union { 38 struct { 39 inflate_huft *tree; /* pointer into tree */ 40 uInt need; /* bits needed */ 41 } code; /* if LEN or DIST, where in tree */ 42 uInt lit; /* if LIT, literal */ 43 struct { 44 uInt get; /* bits to get for extra */ 45 uInt dist; /* distance back to copy from */ 46 } copy; /* if EXT or COPY, where and how much */ 47 } sub; /* submode */ 48 49 /* mode independent information */ 50 Byte lbits; /* ltree bits decoded per branch */ 51 Byte dbits; /* dtree bits decoder per branch */ 52 inflate_huft *ltree; /* literal/length/eob tree */ 53 inflate_huft *dtree; /* distance tree */ 54 55 }; 56 57 58 local inflate_codes_statef *inflate_codes_new( /* bl, bd, tl, td, z) */ 59 uInt bl, uInt bd, 60 inflate_huft *tl, 61 inflate_huft *td, /* need separate declaration for Borland C++ */ 62 z_streamp z ) 63 { 64 inflate_codes_statef *c; 65 66 if ((c = (inflate_codes_statef *) 67 ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL) 68 { 69 c->mode = START; 70 c->lbits = (Byte)bl; 71 c->dbits = (Byte)bd; 72 c->ltree = tl; 73 c->dtree = td; 74 Tracev((stderr, "inflate: codes new\n")); 75 } 76 return c; 77 } 78 79 80 local int inflate_codes( /* s, z, r) */ 81 inflate_blocks_statef *s, 82 z_streamp z, 83 int r ) 84 { 85 uInt j; /* temporary storage */ 86 inflate_huft *t; /* temporary pointer */ 87 uInt e; /* extra bits or operation */ 88 uLong b; /* bit buffer */ 89 uInt k; /* bits in bit buffer */ 90 Bytef *p; /* input data pointer */ 91 uInt n; /* bytes available there */ 92 Bytef *q; /* output window write pointer */ 93 uInt m; /* bytes to end of window or read pointer */ 94 Bytef *f; /* pointer to copy strings from */ 95 inflate_codes_statef *c = s->sub.decode.codes; /* codes state */ 96 97 /* copy input/output information to locals (UPDATE macro restores) */ 98 LOAD 99 100 /* process input and output based on current state */ 101 while (1) switch (c->mode) 102 { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ 103 case START: /* x: set up for LEN */ 104 #ifndef SLOW 105 if (m >= 258 && n >= 10) 106 { 107 UPDATE 108 r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z); 109 LOAD 110 if (r != Z_OK) 111 { 112 c->mode = r == Z_STREAM_END ? WASH : BADCODE; 113 break; 114 } 115 } 116 #endif /* !SLOW */ 117 c->sub.code.need = c->lbits; 118 c->sub.code.tree = c->ltree; 119 c->mode = LEN; 120 case LEN: /* i: get length/literal/eob next */ 121 j = c->sub.code.need; 122 NEEDBITS(j) 123 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); 124 DUMPBITS(t->bits) 125 e = (uInt)(t->exop); 126 if (e == 0) /* literal */ 127 { 128 c->sub.lit = t->base; 129 Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? 130 "inflate: literal '%c'\n" : 131 "inflate: literal 0x%02x\n", t->base)); 132 c->mode = LIT; 133 break; 134 } 135 if (e & 16) /* length */ 136 { 137 c->sub.copy.get = e & 15; 138 c->len = t->base; 139 c->mode = LENEXT; 140 break; 141 } 142 if ((e & 64) == 0) /* next table */ 143 { 144 c->sub.code.need = e; 145 c->sub.code.tree = t + t->base; 146 break; 147 } 148 if (e & 32) /* end of block */ 149 { 150 Tracevv((stderr, "inflate: end of block\n")); 151 c->mode = WASH; 152 break; 153 } 154 c->mode = BADCODE; /* invalid code */ 155 z->msg = (char*)"invalid literal/length code"; 156 r = Z_DATA_ERROR; 157 LEAVE 158 case LENEXT: /* i: getting length extra (have base) */ 159 j = c->sub.copy.get; 160 NEEDBITS(j) 161 c->len += (uInt)b & inflate_mask[j]; 162 DUMPBITS(j) 163 c->sub.code.need = c->dbits; 164 c->sub.code.tree = c->dtree; 165 Tracevv((stderr, "inflate: length %u\n", c->len)); 166 c->mode = DIST; 167 case DIST: /* i: get distance next */ 168 j = c->sub.code.need; 169 NEEDBITS(j) 170 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); 171 DUMPBITS(t->bits) 172 e = (uInt)(t->exop); 173 if (e & 16) /* distance */ 174 { 175 c->sub.copy.get = e & 15; 176 c->sub.copy.dist = t->base; 177 c->mode = DISTEXT; 178 break; 179 } 180 if ((e & 64) == 0) /* next table */ 181 { 182 c->sub.code.need = e; 183 c->sub.code.tree = t + t->base; 184 break; 185 } 186 c->mode = BADCODE; /* invalid code */ 187 z->msg = (char*)"invalid distance code"; 188 r = Z_DATA_ERROR; 189 LEAVE 190 case DISTEXT: /* i: getting distance extra */ 191 j = c->sub.copy.get; 192 NEEDBITS(j) 193 c->sub.copy.dist += (uInt)b & inflate_mask[j]; 194 DUMPBITS(j) 195 Tracevv((stderr, "inflate: distance %u\n", c->sub.copy.dist)); 196 c->mode = COPY; 197 case COPY: /* o: copying bytes in window, waiting for space */ 198 f = q - c->sub.copy.dist; 199 while (f < s->window) /* modulo window size-"while" instead */ 200 f += s->end - s->window; /* of "if" handles invalid distances */ 201 while (c->len) 202 { 203 NEEDOUT 204 OUTBYTE(*f++) 205 if (f == s->end) 206 f = s->window; 207 c->len--; 208 } 209 c->mode = START; 210 break; 211 case LIT: /* o: got literal, waiting for output space */ 212 NEEDOUT 213 OUTBYTE(c->sub.lit) 214 c->mode = START; 215 break; 216 case WASH: /* o: got eob, possibly more output */ 217 if (k > 7) /* return unused byte, if any */ 218 { 219 Assert(k < 16, "inflate_codes grabbed too many bytes") 220 k -= 8; 221 n++; 222 p--; /* can always return one */ 223 } 224 FLUSH 225 if (s->read != s->write) 226 LEAVE 227 c->mode = END; 228 case END: 229 r = Z_STREAM_END; 230 LEAVE 231 case BADCODE: /* x: got error */ 232 r = Z_DATA_ERROR; 233 LEAVE 234 default: 235 r = Z_STREAM_ERROR; 236 LEAVE 237 } 238 #ifdef NEED_DUMMY_RETURN 239 return Z_STREAM_ERROR; /* Some dumb compilers complain without this */ 240 #endif 241 } 242 243 244 local void inflate_codes_free( /* c, z) */ 245 inflate_codes_statef *c, 246 z_streamp z ) 247 { 248 ZFREE(z, c); 249 Tracev((stderr, "inflate: codes free\n")); 250 } 251
