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