18b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* inffast.c -- fast decoding 217b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner * Copyright (C) 1995-2008, 2010, 2013 Mark Adler 38b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * For conditions of distribution and use, see copyright notice in zlib.h 48b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project */ 58b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 68b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#include "zutil.h" 78b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#include "inftrees.h" 88b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#include "inflate.h" 98b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#include "inffast.h" 108b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 118b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#ifndef ASMINF 128b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 138b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* Allow machine dependent optimization for post-increment or pre-increment. 148b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project Based on testing to date, 158b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project Pre-increment preferred for: 168b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project - PowerPC G3 (Adler) 178b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project - MIPS R5000 (Randers-Pehrson) 188b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project Post-increment preferred for: 198b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project - none 208b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project No measurable difference: 218b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project - Pentium III (Anderson) 228b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project - M68060 (Nikl) 238b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project */ 248b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#ifdef POSTINC 258b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# define OFF 0 268b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# define PUP(a) *(a)++ 278b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#else 288b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# define OFF 1 298b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# define PUP(a) *++(a) 308b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#endif 318b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 328b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* 338b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project Decode literal, length, and distance codes and write out the resulting 348b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project literal and match bytes until either not enough input or output is 358b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project available, an end-of-block is encountered, or a data error is encountered. 368b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project When large enough input and output buffers are supplied to inflate(), for 378b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project example, a 16K input buffer and a 64K output buffer, more than 95% of the 388b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project inflate execution time is spent in this routine. 398b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 408b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project Entry assumptions: 418b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 428b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project state->mode == LEN 438b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project strm->avail_in >= 6 448b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project strm->avail_out >= 258 458b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project start >= strm->avail_out 468b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project state->bits < 8 478b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 488b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project On return, state->mode is one of: 498b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 508b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project LEN -- ran out of enough output space or enough available input 518b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project TYPE -- reached end of block code, inflate() to interpret next block 528b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project BAD -- error in block data 538b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 548b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project Notes: 558b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 568b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project - The maximum input bits used by a length/distance pair is 15 bits for the 578b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project length code, 5 bits for the length extra, 15 bits for the distance code, 588b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project and 13 bits for the distance extra. This totals 48 bits, or six bytes. 598b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project Therefore if strm->avail_in >= 6, then there is enough input to avoid 608b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project checking for available input while decoding. 618b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 628b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project - The maximum bytes that a single length/distance pair can output is 258 638b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project bytes, which is the maximum length that can be coded. inflate_fast() 648b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project requires strm->avail_out >= 258 for each loop to avoid checking for 658b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project output space. 668b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project */ 6717b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turnervoid ZLIB_INTERNAL inflate_fast(strm, start) 688b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectz_streamp strm; 698b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectunsigned start; /* inflate()'s starting value for strm->avail_out */ 708b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 718b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project struct inflate_state FAR *state; 7217b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner z_const unsigned char FAR *in; /* local strm->next_in */ 7317b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner z_const unsigned char FAR *last; /* have enough input while in < last */ 748b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned char FAR *out; /* local strm->next_out */ 758b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned char FAR *beg; /* inflate()'s initial strm->next_out */ 768b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned char FAR *end; /* while out < end, enough space available */ 778b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#ifdef INFLATE_STRICT 788b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned dmax; /* maximum distance from zlib header */ 798b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#endif 808b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned wsize; /* window size or zero if not using window */ 818b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned whave; /* valid bytes in the window */ 8217b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner unsigned wnext; /* window write index */ 838b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */ 848b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned long hold; /* local strm->hold */ 858b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned bits; /* local strm->bits */ 868b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project code const FAR *lcode; /* local strm->lencode */ 878b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project code const FAR *dcode; /* local strm->distcode */ 888b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned lmask; /* mask for first level of length codes */ 898b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned dmask; /* mask for first level of distance codes */ 9017b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner code here; /* retrieved table entry */ 918b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned op; /* code bits, operation, extra bits, or */ 928b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* window position, window bytes to copy */ 938b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned len; /* match length, unused bytes */ 948b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned dist; /* match distance */ 958b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned char FAR *from; /* where to copy match from */ 968b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 978b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* copy state to local variables */ 988b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project state = (struct inflate_state FAR *)strm->state; 998b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project in = strm->next_in - OFF; 1008b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project last = in + (strm->avail_in - 5); 1018b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project out = strm->next_out - OFF; 1028b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project beg = out - (start - strm->avail_out); 1038b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project end = out + (strm->avail_out - 257); 1048b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#ifdef INFLATE_STRICT 1058b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project dmax = state->dmax; 1068b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#endif 1078b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project wsize = state->wsize; 1088b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project whave = state->whave; 10917b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner wnext = state->wnext; 1108b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project window = state->window; 1118b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project hold = state->hold; 1128b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project bits = state->bits; 1138b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project lcode = state->lencode; 1148b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project dcode = state->distcode; 1158b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project lmask = (1U << state->lenbits) - 1; 1168b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project dmask = (1U << state->distbits) - 1; 1178b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1188b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* decode literals and length/distances until end-of-block or not enough 1198b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project input data or output space */ 1208b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project do { 1218b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (bits < 15) { 1228b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project hold += (unsigned long)(PUP(in)) << bits; 1238b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project bits += 8; 1248b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project hold += (unsigned long)(PUP(in)) << bits; 1258b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project bits += 8; 1268b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 12717b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner here = lcode[hold & lmask]; 1288b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project dolen: 12917b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner op = (unsigned)(here.bits); 1308b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project hold >>= op; 1318b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project bits -= op; 13217b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner op = (unsigned)(here.op); 1338b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (op == 0) { /* literal */ 13417b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ? 1358b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project "inflate: literal '%c'\n" : 13617b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner "inflate: literal 0x%02x\n", here.val)); 13717b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner PUP(out) = (unsigned char)(here.val); 1388b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 1398b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project else if (op & 16) { /* length base */ 14017b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner len = (unsigned)(here.val); 1418b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project op &= 15; /* number of extra bits */ 1428b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (op) { 1438b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (bits < op) { 1448b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project hold += (unsigned long)(PUP(in)) << bits; 1458b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project bits += 8; 1468b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 1478b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project len += (unsigned)hold & ((1U << op) - 1); 1488b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project hold >>= op; 1498b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project bits -= op; 1508b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 1518b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project Tracevv((stderr, "inflate: length %u\n", len)); 1528b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (bits < 15) { 1538b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project hold += (unsigned long)(PUP(in)) << bits; 1548b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project bits += 8; 1558b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project hold += (unsigned long)(PUP(in)) << bits; 1568b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project bits += 8; 1578b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 15817b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner here = dcode[hold & dmask]; 1598b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project dodist: 16017b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner op = (unsigned)(here.bits); 1618b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project hold >>= op; 1628b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project bits -= op; 16317b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner op = (unsigned)(here.op); 1648b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (op & 16) { /* distance base */ 16517b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner dist = (unsigned)(here.val); 1668b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project op &= 15; /* number of extra bits */ 1678b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (bits < op) { 1688b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project hold += (unsigned long)(PUP(in)) << bits; 1698b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project bits += 8; 1708b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (bits < op) { 1718b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project hold += (unsigned long)(PUP(in)) << bits; 1728b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project bits += 8; 1738b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 1748b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 1758b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project dist += (unsigned)hold & ((1U << op) - 1); 1768b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#ifdef INFLATE_STRICT 1778b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (dist > dmax) { 1788b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project strm->msg = (char *)"invalid distance too far back"; 1798b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project state->mode = BAD; 1808b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project break; 1818b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 1828b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#endif 1838b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project hold >>= op; 1848b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project bits -= op; 1858b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project Tracevv((stderr, "inflate: distance %u\n", dist)); 1868b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project op = (unsigned)(out - beg); /* max distance in output */ 1878b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (dist > op) { /* see if copy from window */ 1888b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project op = dist - op; /* distance back in window */ 1898b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (op > whave) { 19017b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner if (state->sane) { 19117b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner strm->msg = 19217b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner (char *)"invalid distance too far back"; 19317b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner state->mode = BAD; 19417b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner break; 19517b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner } 19617b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR 19717b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner if (len <= op - whave) { 19817b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner do { 19917b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner PUP(out) = 0; 20017b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner } while (--len); 20117b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner continue; 20217b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner } 20317b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner len -= op - whave; 20417b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner do { 20517b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner PUP(out) = 0; 20617b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner } while (--op > whave); 20717b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner if (op == 0) { 20817b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner from = out - dist; 20917b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner do { 21017b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner PUP(out) = PUP(from); 21117b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner } while (--len); 21217b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner continue; 21317b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner } 21417b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner#endif 2158b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2168b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project from = window - OFF; 21717b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner if (wnext == 0) { /* very common case */ 2188b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project from += wsize - op; 2198b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (op < len) { /* some from window */ 2208b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project len -= op; 2218b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project do { 2228b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project PUP(out) = PUP(from); 2238b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } while (--op); 2248b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project from = out - dist; /* rest from output */ 2258b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2268b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 22717b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner else if (wnext < op) { /* wrap around window */ 22817b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner from += wsize + wnext - op; 22917b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner op -= wnext; 2308b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (op < len) { /* some from end of window */ 2318b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project len -= op; 2328b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project do { 2338b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project PUP(out) = PUP(from); 2348b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } while (--op); 2358b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project from = window - OFF; 23617b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner if (wnext < len) { /* some from start of window */ 23717b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner op = wnext; 2388b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project len -= op; 2398b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project do { 2408b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project PUP(out) = PUP(from); 2418b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } while (--op); 2428b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project from = out - dist; /* rest from output */ 2438b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2448b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2458b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2468b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project else { /* contiguous in window */ 24717b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner from += wnext - op; 2488b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (op < len) { /* some from window */ 2498b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project len -= op; 2508b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project do { 2518b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project PUP(out) = PUP(from); 2528b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } while (--op); 2538b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project from = out - dist; /* rest from output */ 2548b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2558b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2568b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project while (len > 2) { 2578b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project PUP(out) = PUP(from); 2588b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project PUP(out) = PUP(from); 2598b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project PUP(out) = PUP(from); 2608b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project len -= 3; 2618b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2628b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (len) { 2638b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project PUP(out) = PUP(from); 2648b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (len > 1) 2658b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project PUP(out) = PUP(from); 2668b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2678b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2688b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project else { 2698b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project from = out - dist; /* copy direct from output */ 2708b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project do { /* minimum length is three */ 2718b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project PUP(out) = PUP(from); 2728b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project PUP(out) = PUP(from); 2738b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project PUP(out) = PUP(from); 2748b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project len -= 3; 2758b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } while (len > 2); 2768b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (len) { 2778b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project PUP(out) = PUP(from); 2788b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (len > 1) 2798b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project PUP(out) = PUP(from); 2808b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2818b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2828b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2838b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project else if ((op & 64) == 0) { /* 2nd level distance code */ 28417b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner here = dcode[here.val + (hold & ((1U << op) - 1))]; 2858b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project goto dodist; 2868b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2878b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project else { 2888b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project strm->msg = (char *)"invalid distance code"; 2898b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project state->mode = BAD; 2908b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project break; 2918b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2928b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2938b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project else if ((op & 64) == 0) { /* 2nd level length code */ 29417b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner here = lcode[here.val + (hold & ((1U << op) - 1))]; 2958b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project goto dolen; 2968b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2978b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project else if (op & 32) { /* end-of-block */ 2988b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project Tracevv((stderr, "inflate: end of block\n")); 2998b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project state->mode = TYPE; 3008b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project break; 3018b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 3028b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project else { 3038b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project strm->msg = (char *)"invalid literal/length code"; 3048b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project state->mode = BAD; 3058b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project break; 3068b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 3078b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } while (in < last && out < end); 3088b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3098b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* return unused bytes (on entry, bits < 8, so in won't go too far back) */ 3108b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project len = bits >> 3; 3118b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project in -= len; 3128b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project bits -= len << 3; 3138b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project hold &= (1U << bits) - 1; 3148b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3158b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* update state and return */ 3168b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project strm->next_in = in + OFF; 3178b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project strm->next_out = out + OFF; 3188b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last)); 3198b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project strm->avail_out = (unsigned)(out < end ? 3208b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 257 + (end - out) : 257 - (out - end)); 3218b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project state->hold = hold; 3228b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project state->bits = bits; 3238b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return; 3248b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 3258b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3268b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* 3278b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe): 3288b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project - Using bit fields for code structure 3298b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project - Different op definition to avoid & for extra bits (do & for table bits) 33017b20e6f38ad2263e47a6884c4f68ce9773d8b29David 'Digit' Turner - Three separate decoding do-loops for direct, window, and wnext == 0 3318b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project - Special case for distance > 1 copies to do overlapped load and store copy 3328b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project - Explicit branch predictions (based on measured branch probabilities) 3338b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project - Deferring match copy and interspersed it with decoding subsequent codes 3348b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project - Swapping literal/length else 3358b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project - Swapping window/direct else 3368b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project - Larger unrolled copy loops (three is about right) 3378b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project - Moving len -= 3 statement into middle of loop 3388b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project */ 3398b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3408b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#endif /* !ASMINF */ 341