19e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* inffast.c -- fast decoding 204351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes * Copyright (C) 1995-2008, 2010, 2013 Mark Adler 39e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * For conditions of distribution and use, see copyright notice in zlib.h 49e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 59e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 69e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#include "zutil.h" 79e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#include "inftrees.h" 89e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#include "inflate.h" 99e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#include "inffast.h" 109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifndef ASMINF 129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Allow machine dependent optimization for post-increment or pre-increment. 149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Based on testing to date, 159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Pre-increment preferred for: 169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project - PowerPC G3 (Adler) 179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project - MIPS R5000 (Randers-Pehrson) 189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Post-increment preferred for: 199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project - none 209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project No measurable difference: 219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project - Pentium III (Anderson) 229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project - M68060 (Nikl) 239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef POSTINC 259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project# define OFF 0 269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project# define PUP(a) *(a)++ 279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#else 289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project# define OFF 1 299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project# define PUP(a) *++(a) 309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* 339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Decode literal, length, and distance codes and write out the resulting 349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project literal and match bytes until either not enough input or output is 359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project available, an end-of-block is encountered, or a data error is encountered. 369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project When large enough input and output buffers are supplied to inflate(), for 379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project example, a 16K input buffer and a 64K output buffer, more than 95% of the 389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project inflate execution time is spent in this routine. 399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Entry assumptions: 419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project state->mode == LEN 439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm->avail_in >= 6 449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm->avail_out >= 258 459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project start >= strm->avail_out 469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project state->bits < 8 479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project On return, state->mode is one of: 499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project LEN -- ran out of enough output space or enough available input 519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project TYPE -- reached end of block code, inflate() to interpret next block 529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project BAD -- error in block data 539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Notes: 559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project - The maximum input bits used by a length/distance pair is 15 bits for the 579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project length code, 5 bits for the length extra, 15 bits for the distance code, 589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project and 13 bits for the distance extra. This totals 48 bits, or six bytes. 599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Therefore if strm->avail_in >= 6, then there is enough input to avoid 609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project checking for available input while decoding. 619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project - The maximum bytes that a single length/distance pair can output is 258 639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bytes, which is the maximum length that can be coded. inflate_fast() 649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project requires strm->avail_out >= 258 for each loop to avoid checking for 659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project output space. 669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 67381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughesvoid ZLIB_INTERNAL inflate_fast(strm, start) 689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectz_streamp strm; 699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectunsigned start; /* inflate()'s starting value for strm->avail_out */ 709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project struct inflate_state FAR *state; 7204351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes z_const unsigned char FAR *in; /* local strm->next_in */ 7304351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes z_const unsigned char FAR *last; /* have enough input while in < last */ 749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned char FAR *out; /* local strm->next_out */ 759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned char FAR *beg; /* inflate()'s initial strm->next_out */ 769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned char FAR *end; /* while out < end, enough space available */ 779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef INFLATE_STRICT 789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned dmax; /* maximum distance from zlib header */ 799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned wsize; /* window size or zero if not using window */ 819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned whave; /* valid bytes in the window */ 82381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes unsigned wnext; /* window write index */ 839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */ 849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned long hold; /* local strm->hold */ 859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned bits; /* local strm->bits */ 869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project code const FAR *lcode; /* local strm->lencode */ 879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project code const FAR *dcode; /* local strm->distcode */ 889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned lmask; /* mask for first level of length codes */ 899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned dmask; /* mask for first level of distance codes */ 90381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes code here; /* retrieved table entry */ 919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned op; /* code bits, operation, extra bits, or */ 929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* window position, window bytes to copy */ 939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned len; /* match length, unused bytes */ 949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned dist; /* match distance */ 959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned char FAR *from; /* where to copy match from */ 969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* copy state to local variables */ 989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project state = (struct inflate_state FAR *)strm->state; 999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project in = strm->next_in - OFF; 1009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project last = in + (strm->avail_in - 5); 1019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project out = strm->next_out - OFF; 1029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project beg = out - (start - strm->avail_out); 1039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project end = out + (strm->avail_out - 257); 1049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef INFLATE_STRICT 1059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project dmax = state->dmax; 1069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 1079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project wsize = state->wsize; 1089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project whave = state->whave; 109381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes wnext = state->wnext; 1109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project window = state->window; 1119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project hold = state->hold; 1129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bits = state->bits; 1139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project lcode = state->lencode; 1149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project dcode = state->distcode; 1159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project lmask = (1U << state->lenbits) - 1; 1169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project dmask = (1U << state->distbits) - 1; 1179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* decode literals and length/distances until end-of-block or not enough 1199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project input data or output space */ 1209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project do { 1219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (bits < 15) { 1229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project hold += (unsigned long)(PUP(in)) << bits; 1239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bits += 8; 1249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project hold += (unsigned long)(PUP(in)) << bits; 1259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bits += 8; 1269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 127381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes here = lcode[hold & lmask]; 1289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project dolen: 129381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes op = (unsigned)(here.bits); 1309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project hold >>= op; 1319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bits -= op; 132381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes op = (unsigned)(here.op); 1339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (op == 0) { /* literal */ 134381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ? 1359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project "inflate: literal '%c'\n" : 136381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes "inflate: literal 0x%02x\n", here.val)); 137381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes PUP(out) = (unsigned char)(here.val); 1389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 1399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project else if (op & 16) { /* length base */ 140381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes len = (unsigned)(here.val); 1419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project op &= 15; /* number of extra bits */ 1429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (op) { 1439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (bits < op) { 1449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project hold += (unsigned long)(PUP(in)) << bits; 1459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bits += 8; 1469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 1479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project len += (unsigned)hold & ((1U << op) - 1); 1489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project hold >>= op; 1499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bits -= op; 1509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 1519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Tracevv((stderr, "inflate: length %u\n", len)); 1529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (bits < 15) { 1539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project hold += (unsigned long)(PUP(in)) << bits; 1549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bits += 8; 1559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project hold += (unsigned long)(PUP(in)) << bits; 1569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bits += 8; 1579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 158381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes here = dcode[hold & dmask]; 1599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project dodist: 160381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes op = (unsigned)(here.bits); 1619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project hold >>= op; 1629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bits -= op; 163381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes op = (unsigned)(here.op); 1649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (op & 16) { /* distance base */ 165381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes dist = (unsigned)(here.val); 1669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project op &= 15; /* number of extra bits */ 1679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (bits < op) { 1689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project hold += (unsigned long)(PUP(in)) << bits; 1699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bits += 8; 1709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (bits < op) { 1719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project hold += (unsigned long)(PUP(in)) << bits; 1729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bits += 8; 1739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 1749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 1759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project dist += (unsigned)hold & ((1U << op) - 1); 1769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef INFLATE_STRICT 1779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (dist > dmax) { 1789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm->msg = (char *)"invalid distance too far back"; 1799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project state->mode = BAD; 1809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project break; 1819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 1829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 1839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project hold >>= op; 1849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bits -= op; 1859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Tracevv((stderr, "inflate: distance %u\n", dist)); 1869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project op = (unsigned)(out - beg); /* max distance in output */ 1879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (dist > op) { /* see if copy from window */ 1889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project op = dist - op; /* distance back in window */ 1899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (op > whave) { 190381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes if (state->sane) { 191381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes strm->msg = 192381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes (char *)"invalid distance too far back"; 193381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes state->mode = BAD; 194381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes break; 195381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes } 196381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR 197381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes if (len <= op - whave) { 198381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes do { 199381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes PUP(out) = 0; 200381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes } while (--len); 201381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes continue; 202381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes } 203381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes len -= op - whave; 204381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes do { 205381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes PUP(out) = 0; 206381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes } while (--op > whave); 207381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes if (op == 0) { 208381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes from = out - dist; 209381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes do { 210381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes PUP(out) = PUP(from); 211381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes } while (--len); 212381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes continue; 213381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes } 214381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes#endif 2159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project from = window - OFF; 217381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes if (wnext == 0) { /* very common case */ 2189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project from += wsize - op; 2199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (op < len) { /* some from window */ 2209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project len -= op; 2219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project do { 2229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project PUP(out) = PUP(from); 2239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } while (--op); 2249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project from = out - dist; /* rest from output */ 2259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 227381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes else if (wnext < op) { /* wrap around window */ 228381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes from += wsize + wnext - op; 229381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes op -= wnext; 2309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (op < len) { /* some from end of window */ 2319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project len -= op; 2329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project do { 2339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project PUP(out) = PUP(from); 2349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } while (--op); 2359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project from = window - OFF; 236381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes if (wnext < len) { /* some from start of window */ 237381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes op = wnext; 2389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project len -= op; 2399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project do { 2409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project PUP(out) = PUP(from); 2419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } while (--op); 2429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project from = out - dist; /* rest from output */ 2439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project else { /* contiguous in window */ 247381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes from += wnext - op; 2489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (op < len) { /* some from window */ 2499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project len -= op; 2509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project do { 2519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project PUP(out) = PUP(from); 2529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } while (--op); 2539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project from = out - dist; /* rest from output */ 2549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project while (len > 2) { 2579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project PUP(out) = PUP(from); 2589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project PUP(out) = PUP(from); 2599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project PUP(out) = PUP(from); 2609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project len -= 3; 2619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (len) { 2639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project PUP(out) = PUP(from); 2649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (len > 1) 2659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project PUP(out) = PUP(from); 2669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project else { 2699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project from = out - dist; /* copy direct from output */ 2709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project do { /* minimum length is three */ 2719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project PUP(out) = PUP(from); 2729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project PUP(out) = PUP(from); 2739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project PUP(out) = PUP(from); 2749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project len -= 3; 2759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } while (len > 2); 2769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (len) { 2779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project PUP(out) = PUP(from); 2789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (len > 1) 2799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project PUP(out) = PUP(from); 2809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project else if ((op & 64) == 0) { /* 2nd level distance code */ 284381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes here = dcode[here.val + (hold & ((1U << op) - 1))]; 2859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project goto dodist; 2869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project else { 2889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm->msg = (char *)"invalid distance code"; 2899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project state->mode = BAD; 2909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project break; 2919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project else if ((op & 64) == 0) { /* 2nd level length code */ 294381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes here = lcode[here.val + (hold & ((1U << op) - 1))]; 2959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project goto dolen; 2969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project else if (op & 32) { /* end-of-block */ 2989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Tracevv((stderr, "inflate: end of block\n")); 2999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project state->mode = TYPE; 3009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project break; 3019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 3029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project else { 3039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm->msg = (char *)"invalid literal/length code"; 3049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project state->mode = BAD; 3059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project break; 3069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 3079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } while (in < last && out < end); 3089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* return unused bytes (on entry, bits < 8, so in won't go too far back) */ 3109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project len = bits >> 3; 3119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project in -= len; 3129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bits -= len << 3; 3139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project hold &= (1U << bits) - 1; 3149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* update state and return */ 3169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm->next_in = in + OFF; 3179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm->next_out = out + OFF; 3189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last)); 3199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm->avail_out = (unsigned)(out < end ? 3209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 257 + (end - out) : 257 - (out - end)); 3219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project state->hold = hold; 3229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project state->bits = bits; 3239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return; 3249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 3259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* 3279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe): 3289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project - Using bit fields for code structure 3299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project - Different op definition to avoid & for extra bits (do & for table bits) 330381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes - Three separate decoding do-loops for direct, window, and wnext == 0 3319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project - Special case for distance > 1 copies to do overlapped load and store copy 3329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project - Explicit branch predictions (based on measured branch probabilities) 3339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project - Deferring match copy and interspersed it with decoding subsequent codes 3349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project - Swapping literal/length else 3359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project - Swapping window/direct else 3369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project - Larger unrolled copy loops (three is about right) 3379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project - Moving len -= 3 statement into middle of loop 3389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 3399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif /* !ASMINF */ 341