cbits/inffast.c · typeable/wai

git.iko.soy/typeable/wai

on wai-extra/0.2.2 help sign in

typeable/wai/cbits/inffast.c

318 lines 13 kB history raw

1/* inffast.c -- fast decoding

3 * For conditions of distribution and use, see copyright notice in zlib.h

4 */

6#include "zutil.h"

7#include "inftrees.h"

8#include "inflate.h"

9#include "inffast.h"

11#ifndef ASMINF

13/* Allow machine dependent optimization for post-increment or pre-increment.

14 Based on testing to date,

15 Pre-increment preferred for:

16 - PowerPC G3 (Adler)

17 - MIPS R5000 (Randers-Pehrson)

18 Post-increment preferred for:

19 - none

20 No measurable difference:

21 - Pentium III (Anderson)

22 - M68060 (Nikl)

23 */

24#ifdef POSTINC

25# define OFF 0

26# define PUP(a) *(a)++

27#else

28# define OFF 1

29# define PUP(a) *++(a)

30#endif

32/*

33 Decode literal, length, and distance codes and write out the resulting

34 literal and match bytes until either not enough input or output is

35 available, an end-of-block is encountered, or a data error is encountered.

36 When large enough input and output buffers are supplied to inflate(), for

37 example, a 16K input buffer and a 64K output buffer, more than 95% of the

38 inflate execution time is spent in this routine.

40 Entry assumptions:

42 state->mode == LEN

43 strm->avail_in >= 6

44 strm->avail_out >= 258

45 start >= strm->avail_out

46 state->bits < 8

48 On return, state->mode is one of:

50 LEN -- ran out of enough output space or enough available input

51 TYPE -- reached end of block code, inflate() to interpret next block

52 BAD -- error in block data

54 Notes:

56 - The maximum input bits used by a length/distance pair is 15 bits for the

57 length code, 5 bits for the length extra, 15 bits for the distance code,

58 and 13 bits for the distance extra. This totals 48 bits, or six bytes.

59 Therefore if strm->avail_in >= 6, then there is enough input to avoid

60 checking for available input while decoding.

62 - The maximum bytes that a single length/distance pair can output is 258

63 bytes, which is the maximum length that can be coded. inflate_fast()

64 requires strm->avail_out >= 258 for each loop to avoid checking for

65 output space.

66 */

67void inflate_fast(strm, start)

68z_streamp strm;

69unsigned start; /* inflate()'s starting value for strm->avail_out */

70{

71 struct inflate_state FAR *state;

72 unsigned char FAR *in; /* local strm->next_in */

73 unsigned char FAR *last; /* while in < last, enough input available */

74 unsigned char FAR *out; /* local strm->next_out */

75 unsigned char FAR *beg; /* inflate()'s initial strm->next_out */

76 unsigned char FAR *end; /* while out < end, enough space available */

77#ifdef INFLATE_STRICT

78 unsigned dmax; /* maximum distance from zlib header */

79#endif

80 unsigned wsize; /* window size or zero if not using window */

81 unsigned whave; /* valid bytes in the window */

82 unsigned write; /* window write index */

83 unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */

84 unsigned long hold; /* local strm->hold */

85 unsigned bits; /* local strm->bits */

86 code const FAR *lcode; /* local strm->lencode */

87 code const FAR *dcode; /* local strm->distcode */

88 unsigned lmask; /* mask for first level of length codes */

89 unsigned dmask; /* mask for first level of distance codes */

90 code this; /* retrieved table entry */

91 unsigned op; /* code bits, operation, extra bits, or */

92 /* window position, window bytes to copy */

93 unsigned len; /* match length, unused bytes */

94 unsigned dist; /* match distance */

95 unsigned char FAR *from; /* where to copy match from */

97 /* copy state to local variables */

98 state = (struct inflate_state FAR *)strm->state;

99 in = strm->next_in - OFF;

100 last = in + (strm->avail_in - 5);

101 out = strm->next_out - OFF;

102 beg = out - (start - strm->avail_out);

103 end = out + (strm->avail_out - 257);

104#ifdef INFLATE_STRICT

105 dmax = state->dmax;

106#endif

107 wsize = state->wsize;

108 whave = state->whave;

109 write = state->write;

110 window = state->window;

111 hold = state->hold;

112 bits = state->bits;

113 lcode = state->lencode;

114 dcode = state->distcode;

115 lmask = (1U << state->lenbits) - 1;

116 dmask = (1U << state->distbits) - 1;

117

118 /* decode literals and length/distances until end-of-block or not enough

119 input data or output space */

120 do {

121 if (bits < 15) {

122 hold += (unsigned long)(PUP(in)) << bits;

123 bits += 8;

124 hold += (unsigned long)(PUP(in)) << bits;

125 bits += 8;

126 }

127 this = lcode[hold & lmask];

128 dolen:

129 op = (unsigned)(this.bits);

130 hold >>= op;

131 bits -= op;

132 op = (unsigned)(this.op);

133 if (op == 0) { /* literal */

134 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?

135 "inflate: literal '%c'\n" :

136 "inflate: literal 0x%02x\n", this.val));

137 PUP(out) = (unsigned char)(this.val);

138 }

139 else if (op & 16) { /* length base */

140 len = (unsigned)(this.val);

141 op &= 15; /* number of extra bits */

142 if (op) {

143 if (bits < op) {

144 hold += (unsigned long)(PUP(in)) << bits;

145 bits += 8;

146 }

147 len += (unsigned)hold & ((1U << op) - 1);

148 hold >>= op;

149 bits -= op;

150 }

151 Tracevv((stderr, "inflate: length %u\n", len));

152 if (bits < 15) {

153 hold += (unsigned long)(PUP(in)) << bits;

154 bits += 8;

155 hold += (unsigned long)(PUP(in)) << bits;

156 bits += 8;

157 }

158 this = dcode[hold & dmask];

159 dodist:

160 op = (unsigned)(this.bits);

161 hold >>= op;

162 bits -= op;

163 op = (unsigned)(this.op);

164 if (op & 16) { /* distance base */

165 dist = (unsigned)(this.val);

166 op &= 15; /* number of extra bits */

167 if (bits < op) {

168 hold += (unsigned long)(PUP(in)) << bits;

169 bits += 8;

170 if (bits < op) {

171 hold += (unsigned long)(PUP(in)) << bits;

172 bits += 8;

173 }

174 }

175 dist += (unsigned)hold & ((1U << op) - 1);

176#ifdef INFLATE_STRICT

177 if (dist > dmax) {

178 strm->msg = (char *)"invalid distance too far back";

179 state->mode = BAD;

180 break;

181 }

182#endif

183 hold >>= op;

184 bits -= op;

185 Tracevv((stderr, "inflate: distance %u\n", dist));

186 op = (unsigned)(out - beg); /* max distance in output */

187 if (dist > op) { /* see if copy from window */

188 op = dist - op; /* distance back in window */

189 if (op > whave) {

190 strm->msg = (char *)"invalid distance too far back";

191 state->mode = BAD;

192 break;

193 }

194 from = window - OFF;

195 if (write == 0) { /* very common case */

196 from += wsize - op;

197 if (op < len) { /* some from window */

198 len -= op;

199 do {

200 PUP(out) = PUP(from);

201 } while (--op);

202 from = out - dist; /* rest from output */

203 }

204 }

205 else if (write < op) { /* wrap around window */

206 from += wsize + write - op;

207 op -= write;

208 if (op < len) { /* some from end of window */

209 len -= op;

210 do {

211 PUP(out) = PUP(from);

212 } while (--op);

213 from = window - OFF;

214 if (write < len) { /* some from start of window */

215 op = write;

216 len -= op;

217 do {

218 PUP(out) = PUP(from);

219 } while (--op);

220 from = out - dist; /* rest from output */

221 }

222 }

223 }

224 else { /* contiguous in window */

225 from += write - op;

226 if (op < len) { /* some from window */

227 len -= op;

228 do {

229 PUP(out) = PUP(from);

230 } while (--op);

231 from = out - dist; /* rest from output */

232 }

233 }

234 while (len > 2) {

235 PUP(out) = PUP(from);

236 PUP(out) = PUP(from);

237 PUP(out) = PUP(from);

238 len -= 3;

239 }

240 if (len) {

241 PUP(out) = PUP(from);

242 if (len > 1)

243 PUP(out) = PUP(from);

244 }

245 }

246 else {

247 from = out - dist; /* copy direct from output */

248 do { /* minimum length is three */

249 PUP(out) = PUP(from);

250 PUP(out) = PUP(from);

251 PUP(out) = PUP(from);

252 len -= 3;

253 } while (len > 2);

254 if (len) {

255 PUP(out) = PUP(from);

256 if (len > 1)

257 PUP(out) = PUP(from);

258 }

259 }

260 }

261 else if ((op & 64) == 0) { /* 2nd level distance code */

262 this = dcode[this.val + (hold & ((1U << op) - 1))];

263 goto dodist;

264 }

265 else {

266 strm->msg = (char *)"invalid distance code";

267 state->mode = BAD;

268 break;

269 }

270 }

271 else if ((op & 64) == 0) { /* 2nd level length code */

272 this = lcode[this.val + (hold & ((1U << op) - 1))];

273 goto dolen;

274 }

275 else if (op & 32) { /* end-of-block */

276 Tracevv((stderr, "inflate: end of block\n"));

277 state->mode = TYPE;

278 break;

279 }

280 else {

281 strm->msg = (char *)"invalid literal/length code";

282 state->mode = BAD;

283 break;

284 }

285 } while (in < last && out < end);

286

287 /* return unused bytes (on entry, bits < 8, so in won't go too far back) */

288 len = bits >> 3;

289 in -= len;

290 bits -= len << 3;

291 hold &= (1U << bits) - 1;

292

293 /* update state and return */

294 strm->next_in = in + OFF;

295 strm->next_out = out + OFF;

296 strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));

297 strm->avail_out = (unsigned)(out < end ?

298 257 + (end - out) : 257 - (out - end));

299 state->hold = hold;

300 state->bits = bits;

301 return;

302}

303

304/*

305 inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):

306 - Using bit fields for code structure

307 - Different op definition to avoid & for extra bits (do & for table bits)

308 - Three separate decoding do-loops for direct, window, and write == 0

309 - Special case for distance > 1 copies to do overlapped load and store copy

310 - Explicit branch predictions (based on measured branch probabilities)

311 - Deferring match copy and interspersed it with decoding subsequent codes

312 - Swapping literal/length else

313 - Swapping window/direct else

314 - Larger unrolled copy loops (three is about right)

315 - Moving len -= 3 statement into middle of loop

316 */

317

318#endif /* !ASMINF */