inffast.c 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356
  1. /* inffast.c -- fast decoding
  2. * Copyright (C) 1995-2004 Mark Adler
  3. * For conditions of distribution and use, see copyright notice in zlib.h
  4. */
  5. /* U-Boot: we already included these
  6. #include "zutil.h"
  7. #include "inftrees.h"
  8. #include "inflate.h"
  9. #include "inffast.h"
  10. */
  11. #ifndef ASMINF
  12. /* Allow machine dependent optimization for post-increment or pre-increment.
  13. Based on testing to date,
  14. Pre-increment preferred for:
  15. - PowerPC G3 (Adler)
  16. - MIPS R5000 (Randers-Pehrson)
  17. Post-increment preferred for:
  18. - none
  19. No measurable difference:
  20. - Pentium III (Anderson)
  21. - M68060 (Nikl)
  22. */
  23. #ifdef POSTINC
  24. # define OFF 0
  25. # define PUP(a) *(a)++
  26. #else
  27. # define OFF 1
  28. # define PUP(a) *++(a)
  29. #endif
  30. /*
  31. Decode literal, length, and distance codes and write out the resulting
  32. literal and match bytes until either not enough input or output is
  33. available, an end-of-block is encountered, or a data error is encountered.
  34. When large enough input and output buffers are supplied to inflate(), for
  35. example, a 16K input buffer and a 64K output buffer, more than 95% of the
  36. inflate execution time is spent in this routine.
  37. Entry assumptions:
  38. state->mode == LEN
  39. strm->avail_in >= 6
  40. strm->avail_out >= 258
  41. start >= strm->avail_out
  42. state->bits < 8
  43. On return, state->mode is one of:
  44. LEN -- ran out of enough output space or enough available input
  45. TYPE -- reached end of block code, inflate() to interpret next block
  46. BAD -- error in block data
  47. Notes:
  48. - The maximum input bits used by a length/distance pair is 15 bits for the
  49. length code, 5 bits for the length extra, 15 bits for the distance code,
  50. and 13 bits for the distance extra. This totals 48 bits, or six bytes.
  51. Therefore if strm->avail_in >= 6, then there is enough input to avoid
  52. checking for available input while decoding.
  53. - The maximum bytes that a single length/distance pair can output is 258
  54. bytes, which is the maximum length that can be coded. inflate_fast()
  55. requires strm->avail_out >= 258 for each loop to avoid checking for
  56. output space.
  57. */
  58. void inflate_fast(z_streamp strm, unsigned start)
  59. /* start: inflate()'s starting value for strm->avail_out */
  60. {
  61. struct inflate_state FAR *state;
  62. unsigned char FAR *in; /* local strm->next_in */
  63. unsigned char FAR *last; /* while in < last, enough input available */
  64. unsigned char FAR *out; /* local strm->next_out */
  65. unsigned char FAR *beg; /* inflate()'s initial strm->next_out */
  66. unsigned char FAR *end; /* while out < end, enough space available */
  67. #ifdef INFLATE_STRICT
  68. unsigned dmax; /* maximum distance from zlib header */
  69. #endif
  70. unsigned wsize; /* window size or zero if not using window */
  71. unsigned whave; /* valid bytes in the window */
  72. unsigned write; /* window write index */
  73. unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */
  74. unsigned long hold; /* local strm->hold */
  75. unsigned bits; /* local strm->bits */
  76. code const FAR *lcode; /* local strm->lencode */
  77. code const FAR *dcode; /* local strm->distcode */
  78. unsigned lmask; /* mask for first level of length codes */
  79. unsigned dmask; /* mask for first level of distance codes */
  80. code this; /* retrieved table entry */
  81. unsigned op; /* code bits, operation, extra bits, or */
  82. /* window position, window bytes to copy */
  83. unsigned len; /* match length, unused bytes */
  84. unsigned dist; /* match distance */
  85. unsigned char FAR *from; /* where to copy match from */
  86. /* copy state to local variables */
  87. state = (struct inflate_state FAR *)strm->state;
  88. in = strm->next_in - OFF;
  89. last = in + (strm->avail_in - 5);
  90. if (in > last && strm->avail_in > 5) {
  91. /*
  92. * overflow detected, limit strm->avail_in to the
  93. * max. possible size and recalculate last
  94. */
  95. strm->avail_in = 0xffffffff - (uintptr_t)in;
  96. last = in + (strm->avail_in - 5);
  97. }
  98. out = strm->next_out - OFF;
  99. beg = out - (start - strm->avail_out);
  100. end = out + (strm->avail_out - 257);
  101. #ifdef INFLATE_STRICT
  102. dmax = state->dmax;
  103. #endif
  104. wsize = state->wsize;
  105. whave = state->whave;
  106. write = state->write;
  107. window = state->window;
  108. hold = state->hold;
  109. bits = state->bits;
  110. lcode = state->lencode;
  111. dcode = state->distcode;
  112. lmask = (1U << state->lenbits) - 1;
  113. dmask = (1U << state->distbits) - 1;
  114. /* decode literals and length/distances until end-of-block or not enough
  115. input data or output space */
  116. do {
  117. if (bits < 15) {
  118. hold += (unsigned long)(PUP(in)) << bits;
  119. bits += 8;
  120. hold += (unsigned long)(PUP(in)) << bits;
  121. bits += 8;
  122. }
  123. this = lcode[hold & lmask];
  124. dolen:
  125. op = (unsigned)(this.bits);
  126. hold >>= op;
  127. bits -= op;
  128. op = (unsigned)(this.op);
  129. if (op == 0) { /* literal */
  130. Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
  131. "inflate: literal '%c'\n" :
  132. "inflate: literal 0x%02x\n", this.val));
  133. PUP(out) = (unsigned char)(this.val);
  134. }
  135. else if (op & 16) { /* length base */
  136. len = (unsigned)(this.val);
  137. op &= 15; /* number of extra bits */
  138. if (op) {
  139. if (bits < op) {
  140. hold += (unsigned long)(PUP(in)) << bits;
  141. bits += 8;
  142. }
  143. len += (unsigned)hold & ((1U << op) - 1);
  144. hold >>= op;
  145. bits -= op;
  146. }
  147. Tracevv((stderr, "inflate: length %u\n", len));
  148. if (bits < 15) {
  149. hold += (unsigned long)(PUP(in)) << bits;
  150. bits += 8;
  151. hold += (unsigned long)(PUP(in)) << bits;
  152. bits += 8;
  153. }
  154. this = dcode[hold & dmask];
  155. dodist:
  156. op = (unsigned)(this.bits);
  157. hold >>= op;
  158. bits -= op;
  159. op = (unsigned)(this.op);
  160. if (op & 16) { /* distance base */
  161. dist = (unsigned)(this.val);
  162. op &= 15; /* number of extra bits */
  163. if (bits < op) {
  164. hold += (unsigned long)(PUP(in)) << bits;
  165. bits += 8;
  166. if (bits < op) {
  167. hold += (unsigned long)(PUP(in)) << bits;
  168. bits += 8;
  169. }
  170. }
  171. dist += (unsigned)hold & ((1U << op) - 1);
  172. #ifdef INFLATE_STRICT
  173. if (dist > dmax) {
  174. strm->msg = (char *)"invalid distance too far back";
  175. state->mode = BAD;
  176. break;
  177. }
  178. #endif
  179. hold >>= op;
  180. bits -= op;
  181. Tracevv((stderr, "inflate: distance %u\n", dist));
  182. op = (unsigned)(out - beg); /* max distance in output */
  183. if (dist > op) { /* see if copy from window */
  184. op = dist - op; /* distance back in window */
  185. if (op > whave) {
  186. strm->msg = (char *)"invalid distance too far back";
  187. state->mode = BAD;
  188. break;
  189. }
  190. from = window - OFF;
  191. if (write == 0) { /* very common case */
  192. from += wsize - op;
  193. if (op < len) { /* some from window */
  194. len -= op;
  195. do {
  196. PUP(out) = PUP(from);
  197. } while (--op);
  198. from = out - dist; /* rest from output */
  199. }
  200. }
  201. else if (write < op) { /* wrap around window */
  202. from += wsize + write - op;
  203. op -= write;
  204. if (op < len) { /* some from end of window */
  205. len -= op;
  206. do {
  207. PUP(out) = PUP(from);
  208. } while (--op);
  209. from = window - OFF;
  210. if (write < len) { /* some from start of window */
  211. op = write;
  212. len -= op;
  213. do {
  214. PUP(out) = PUP(from);
  215. } while (--op);
  216. from = out - dist; /* rest from output */
  217. }
  218. }
  219. }
  220. else { /* contiguous in window */
  221. from += write - op;
  222. if (op < len) { /* some from window */
  223. len -= op;
  224. do {
  225. PUP(out) = PUP(from);
  226. } while (--op);
  227. from = out - dist; /* rest from output */
  228. }
  229. }
  230. while (len > 2) {
  231. PUP(out) = PUP(from);
  232. PUP(out) = PUP(from);
  233. PUP(out) = PUP(from);
  234. len -= 3;
  235. }
  236. if (len) {
  237. PUP(out) = PUP(from);
  238. if (len > 1)
  239. PUP(out) = PUP(from);
  240. }
  241. }
  242. else {
  243. unsigned short *sout;
  244. unsigned long loops;
  245. from = out - dist; /* copy direct from output */
  246. /* minimum length is three */
  247. /* Align out addr */
  248. if (!((long)(out - 1 + OFF) & 1)) {
  249. PUP(out) = PUP(from);
  250. len--;
  251. }
  252. sout = (unsigned short *)(out - OFF);
  253. if (dist > 2 ) {
  254. unsigned short *sfrom;
  255. sfrom = (unsigned short *)(from - OFF);
  256. loops = len >> 1;
  257. do
  258. PUP(sout) = get_unaligned(++sfrom);
  259. while (--loops);
  260. out = (unsigned char *)sout + OFF;
  261. from = (unsigned char *)sfrom + OFF;
  262. } else { /* dist == 1 or dist == 2 */
  263. unsigned short pat16;
  264. pat16 = *(sout-2+2*OFF);
  265. if (dist == 1)
  266. #if defined(__BIG_ENDIAN)
  267. pat16 = (pat16 & 0xff) | ((pat16 & 0xff ) << 8);
  268. #elif defined(__LITTLE_ENDIAN)
  269. pat16 = (pat16 & 0xff00) | ((pat16 & 0xff00 ) >> 8);
  270. #else
  271. #error __BIG_ENDIAN nor __LITTLE_ENDIAN is defined
  272. #endif
  273. loops = len >> 1;
  274. do
  275. PUP(sout) = pat16;
  276. while (--loops);
  277. out = (unsigned char *)sout + OFF;
  278. }
  279. if (len & 1)
  280. PUP(out) = PUP(from);
  281. }
  282. }
  283. else if ((op & 64) == 0) { /* 2nd level distance code */
  284. this = dcode[this.val + (hold & ((1U << op) - 1))];
  285. goto dodist;
  286. }
  287. else {
  288. strm->msg = (char *)"invalid distance code";
  289. state->mode = BAD;
  290. break;
  291. }
  292. }
  293. else if ((op & 64) == 0) { /* 2nd level length code */
  294. this = lcode[this.val + (hold & ((1U << op) - 1))];
  295. goto dolen;
  296. }
  297. else if (op & 32) { /* end-of-block */
  298. Tracevv((stderr, "inflate: end of block\n"));
  299. state->mode = TYPE;
  300. break;
  301. }
  302. else {
  303. strm->msg = (char *)"invalid literal/length code";
  304. state->mode = BAD;
  305. break;
  306. }
  307. } while (in < last && out < end);
  308. /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
  309. len = bits >> 3;
  310. in -= len;
  311. bits -= len << 3;
  312. hold &= (1U << bits) - 1;
  313. /* update state and return */
  314. strm->next_in = in + OFF;
  315. strm->next_out = out + OFF;
  316. strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
  317. strm->avail_out = (unsigned)(out < end ?
  318. 257 + (end - out) : 257 - (out - end));
  319. state->hold = hold;
  320. state->bits = bits;
  321. return;
  322. }
  323. /*
  324. inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
  325. - Using bit fields for code structure
  326. - Different op definition to avoid & for extra bits (do & for table bits)
  327. - Three separate decoding do-loops for direct, window, and write == 0
  328. - Special case for distance > 1 copies to do overlapped load and store copy
  329. - Explicit branch predictions (based on measured branch probabilities)
  330. - Deferring match copy and interspersed it with decoding subsequent codes
  331. - Swapping literal/length else
  332. - Swapping window/direct else
  333. - Larger unrolled copy loops (three is about right)
  334. - Moving len -= 3 statement into middle of loop
  335. */
  336. #endif /* !ASMINF */