19e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* 29e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * puff.c 304351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes * Copyright (C) 2002-2013 Mark Adler 49e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * For conditions of distribution and use, see copyright notice in puff.h 504351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes * version 2.3, 21 Jan 2013 69e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 79e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * puff.c is a simple inflate written to be an unambiguous way to specify the 89e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * deflate format. It is not written for speed but rather simplicity. As a 99e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * side benefit, this code might actually be useful when small code is more 109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * important than speed, such as bootstrap applications. For typical deflate 119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * data, zlib's inflate() is about four times as fast as puff(). zlib's 129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * inflate compiles to around 20K on my machine, whereas puff.c compiles to 139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * around 4K on my machine (a PowerPC using GNU cc). If the faster decode() 149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * function here is used, then puff() is only twice as slow as zlib's 159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * inflate(). 169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * All dynamically allocated memory comes from the stack. The stack required 189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * is less than 2K bytes. This code is compatible with 16-bit int's and 199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * assumes that long's are at least 32 bits. puff.c uses the short data type, 207291b8caf18844362881750df5cebd045d672c43Leon Scroggins III * assumed to be 16 bits, for arrays in order to conserve memory. The code 219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * works whether integers are stored big endian or little endian. 229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * In the comments below are "Format notes" that describe the inflate process 249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * and document some of the less obvious aspects of the format. This source 259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * code is meant to supplement RFC 1951, which formally describes the deflate 269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * format: 279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * http://www.zlib.org/rfc-deflate.html 299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* 329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Change history: 339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 1.0 10 Feb 2002 - First version 359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 1.1 17 Feb 2002 - Clarifications of some comments and notes 369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Update puff() dest and source pointers on negative 379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * errors to facilitate debugging deflators 389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Remove longest from struct huffman -- not needed 399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Simplify offs[] index in construct() 409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Add input size and checking, using longjmp() to 419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * maintain easy readability 429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Use short data type for large arrays 439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Use pointers instead of long to specify source and 449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * destination sizes to avoid arbitrary 4 GB limits 459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 1.2 17 Mar 2002 - Add faster version of decode(), doubles speed (!), 469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * but leave simple version for readabilty 479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Make sure invalid distances detected if pointers 489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * are 16 bits 499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Fix fixed codes table error 509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Provide a scanning mode for determining size of 519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * uncompressed data 52ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes * 1.3 20 Mar 2002 - Go back to lengths for puff() parameters [Gailly] 539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Add a puff.h file for the interface 54ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes * - Add braces in puff() for else do [Gailly] 559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Use indexes instead of pointers for readability 569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 1.4 31 Mar 2002 - Simplify construct() code set check 579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Fix some comments 589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Add FIXLCODES #define 599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 1.5 6 Apr 2002 - Minor comment fixes 609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 1.6 7 Aug 2002 - Minor format changes 619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 1.7 3 Mar 2003 - Added test code for distribution 629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Added zlib-like license 639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 1.8 9 Jan 2004 - Added some comments on no distance codes case 64381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * 1.9 21 Feb 2008 - Fix bug on 16-bit integer architectures [Pohland] 65381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * - Catch missing end-of-block symbol error 66381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * 2.0 25 Jul 2008 - Add #define to permit distance too far back 67381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * - Add option in TEST code for puff to write the data 68381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * - Add option in TEST code to skip input bytes 69381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * - Allow TEST code to read from piped stdin 70381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * 2.1 4 Apr 2010 - Avoid variable initialization for happier compilers 71381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * - Avoid unsigned comparisons for even happier compilers 72ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes * 2.2 25 Apr 2010 - Fix bug in variable initializations [Oberhumer] 73ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes * - Add const where appropriate [Oberhumer] 74ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes * - Split if's and ?'s for coverage testing 75ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes * - Break out test code to separate file 76ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes * - Move NIL to puff.h 77ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes * - Allow incomplete code only if single code length is 1 78ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes * - Add full code coverage test to Makefile 7904351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes * 2.3 21 Jan 2013 - Check for invalid code length codes in dynamic blocks 809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#include <setjmp.h> /* for setjmp(), longjmp(), and jmp_buf */ 839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#include "puff.h" /* prototype for puff() */ 849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define local static /* for local function definitions */ 869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* 889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Maximums for allocations and loops. It is not useful to change these -- 899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * they are fixed by the deflate format. 909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define MAXBITS 15 /* maximum bits in a code */ 929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define MAXLCODES 286 /* maximum number of literal/length codes */ 939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define MAXDCODES 30 /* maximum number of distance codes */ 949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define MAXCODES (MAXLCODES+MAXDCODES) /* maximum codes lengths to read */ 959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define FIXLCODES 288 /* number of fixed literal/length codes */ 969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* input and output state */ 989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectstruct state { 999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* output state */ 1009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned char *out; /* output buffer */ 1019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned long outlen; /* available space at out */ 1029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned long outcnt; /* bytes written to out so far */ 1039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* input state */ 105ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes const unsigned char *in; /* input buffer */ 1069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned long inlen; /* available input at in */ 1079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned long incnt; /* bytes read so far */ 1089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int bitbuf; /* bit buffer */ 1099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int bitcnt; /* number of bits in bit buffer */ 1109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* input limit error return state for bits() and decode() */ 1129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project jmp_buf env; 1139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project}; 1149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* 1169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Return need bits from the input stream. This always leaves less than 1179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * eight bits in the buffer. bits() works properly for need == 0. 1189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 1199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Format notes: 1209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 1219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Bits are stored in bytes from the least significant bit to the most 1229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * significant bit. Therefore bits are dropped from the bottom of the bit 1239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * buffer, using shift right, and new bytes are appended to the top of the 1249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * bit buffer, using shift left. 1259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 1269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal int bits(struct state *s, int need) 1279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 1289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project long val; /* bit accumulator (can use up to 20 bits) */ 1299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* load at least need bits into val */ 1319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project val = s->bitbuf; 1329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project while (s->bitcnt < need) { 133ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes if (s->incnt == s->inlen) 134ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes longjmp(s->env, 1); /* out of input */ 1359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project val |= (long)(s->in[s->incnt++]) << s->bitcnt; /* load eight bits */ 1369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bitcnt += 8; 1379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 1389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* drop need bits and update buffer, always zero to seven bits left */ 1409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bitbuf = (int)(val >> need); 1419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bitcnt -= need; 1429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* return need bits, zeroing the bits above that */ 1449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return (int)(val & ((1L << need) - 1)); 1459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 1469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* 1489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Process a stored block. 1499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 1509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Format notes: 1519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 1529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - After the two-bit stored block type (00), the stored block length and 1539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * stored bytes are byte-aligned for fast copying. Therefore any leftover 1549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * bits in the byte that has the last bit of the type, as many as seven, are 1559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * discarded. The value of the discarded bits are not defined and should not 1569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * be checked against any expectation. 1579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 1589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - The second inverted copy of the stored block length does not have to be 1599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * checked, but it's probably a good idea to do so anyway. 1609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 1619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - A stored block can have zero length. This is sometimes used to byte-align 1629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * subsets of the compressed data for random access or partial recovery. 1639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 1649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal int stored(struct state *s) 1659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 1669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned len; /* length of stored block */ 1679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* discard leftover bits from current byte (assumes s->bitcnt < 8) */ 1699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bitbuf = 0; 1709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bitcnt = 0; 1719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* get length and check against its one's complement */ 173ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes if (s->incnt + 4 > s->inlen) 174ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes return 2; /* not enough input */ 1759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project len = s->in[s->incnt++]; 1769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project len |= s->in[s->incnt++] << 8; 1779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (s->in[s->incnt++] != (~len & 0xff) || 1789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->in[s->incnt++] != ((~len >> 8) & 0xff)) 1799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return -2; /* didn't match complement! */ 1809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* copy len bytes from in to out */ 182ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes if (s->incnt + len > s->inlen) 183ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes return 2; /* not enough input */ 1849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (s->out != NIL) { 1859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (s->outcnt + len > s->outlen) 1869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return 1; /* not enough output space */ 1879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project while (len--) 1889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->out[s->outcnt++] = s->in[s->incnt++]; 1899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 1909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project else { /* just scanning */ 1919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->outcnt += len; 1929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->incnt += len; 1939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 1949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* done with a valid stored block */ 1969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return 0; 1979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 1989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* 2009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Huffman code decoding tables. count[1..MAXBITS] is the number of symbols of 2019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * each length, which for a canonical code are stepped through in order. 2029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * symbol[] are the symbol values in canonical order, where the number of 2039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * entries is the sum of the counts in count[]. The decoding process can be 2049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * seen in the function decode() below. 2059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 2069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectstruct huffman { 2079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project short *count; /* number of symbols of each length */ 2089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project short *symbol; /* canonically ordered symbols */ 2099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project}; 2109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* 2129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Decode a code from the stream s using huffman table h. Return the symbol or 2139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * a negative value if there is an error. If all of the lengths are zero, i.e. 2149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * an empty code, or if the code is incomplete and an invalid code is received, 215381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * then -10 is returned after reading MAXBITS bits. 2169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 2179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Format notes: 2189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 2199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - The codes as stored in the compressed data are bit-reversed relative to 2209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * a simple integer ordering of codes of the same lengths. Hence below the 2219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * bits are pulled from the compressed data one at a time and used to 2229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * build the code value reversed from what is in the stream in order to 2239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * permit simple integer comparisons for decoding. A table-based decoding 2249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * scheme (as used in zlib) does not need to do this reversal. 2259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 2269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - The first code for the shortest length is all zeros. Subsequent codes of 2279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * the same length are simply integer increments of the previous code. When 2289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * moving up a length, a zero bit is appended to the code. For a complete 2299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * code, the last code of the longest length will be all ones. 2309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 2319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Incomplete codes are handled by this decoder, since they are permitted 2329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * in the deflate format. See the format notes for fixed() and dynamic(). 2339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 2349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef SLOW 235ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hugheslocal int decode(struct state *s, const struct huffman *h) 2369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 2379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int len; /* current number of bits in code */ 2389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int code; /* len bits being decoded */ 2399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int first; /* first code of length len */ 2409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int count; /* number of codes of length len */ 2419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int index; /* index of first code of length len in symbol table */ 2429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project code = first = index = 0; 2449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (len = 1; len <= MAXBITS; len++) { 2459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project code |= bits(s, 1); /* get next bit */ 2469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project count = h->count[len]; 247381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes if (code - count < first) /* if length len, return symbol */ 2489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return h->symbol[index + (code - first)]; 2499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project index += count; /* else update for next length */ 2509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project first += count; 2519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project first <<= 1; 2529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project code <<= 1; 2539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 254381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes return -10; /* ran out of codes */ 2559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 2569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* 2589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * A faster version of decode() for real applications of this code. It's not 2599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * as readable, but it makes puff() twice as fast. And it only makes the code 2609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * a few percent larger. 2619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 2629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#else /* !SLOW */ 263ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hugheslocal int decode(struct state *s, const struct huffman *h) 2649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 2659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int len; /* current number of bits in code */ 2669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int code; /* len bits being decoded */ 2679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int first; /* first code of length len */ 2689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int count; /* number of codes of length len */ 2699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int index; /* index of first code of length len in symbol table */ 2709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int bitbuf; /* bits from stream */ 2719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int left; /* bits left in next or left to process */ 2729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project short *next; /* next number of codes */ 2739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bitbuf = s->bitbuf; 2759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project left = s->bitcnt; 2769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project code = first = index = 0; 2779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project len = 1; 2789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project next = h->count + 1; 2799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project while (1) { 2809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project while (left--) { 2819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project code |= bitbuf & 1; 2829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bitbuf >>= 1; 2839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project count = *next++; 284381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes if (code - count < first) { /* if length len, return symbol */ 2859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bitbuf = bitbuf; 2869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bitcnt = (s->bitcnt - len) & 7; 2879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return h->symbol[index + (code - first)]; 2889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project index += count; /* else update for next length */ 2909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project first += count; 2919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project first <<= 1; 2929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project code <<= 1; 2939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project len++; 2949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project left = (MAXBITS+1) - len; 296ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes if (left == 0) 297ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes break; 298ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes if (s->incnt == s->inlen) 299ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes longjmp(s->env, 1); /* out of input */ 3009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bitbuf = s->in[s->incnt++]; 301ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes if (left > 8) 302ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes left = 8; 3039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 304381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes return -10; /* ran out of codes */ 3059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 3069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif /* SLOW */ 3079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* 3099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Given the list of code lengths length[0..n-1] representing a canonical 3109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Huffman code for n symbols, construct the tables required to decode those 3119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * codes. Those tables are the number of codes of each length, and the symbols 3129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * sorted by length, retaining their original order within each length. The 3139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * return value is zero for a complete code set, negative for an over- 3149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * subscribed code set, and positive for an incomplete code set. The tables 3159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * can be used if the return value is zero or positive, but they cannot be used 3169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * if the return value is negative. If the return value is zero, it is not 3179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * possible for decode() using that table to return an error--any stream of 3189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * enough bits will resolve to a symbol. If the return value is positive, then 3199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * it is possible for decode() using that table to return an error for received 3209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * codes past the end of the incomplete lengths. 3219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 3229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Not used by decode(), but used for error checking, h->count[0] is the number 3239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * of the n symbols not in the code. So n - h->count[0] is the number of 3249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * codes. This is useful for checking for incomplete codes that have more than 3259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * one symbol, which is an error in a dynamic block. 3269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 3279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Assumption: for all i in 0..n-1, 0 <= length[i] <= MAXBITS 3289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * This is assured by the construction of the length arrays in dynamic() and 3299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * fixed() and is not verified by construct(). 3309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 3319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Format notes: 3329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 3339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Permitted and expected examples of incomplete codes are one of the fixed 3349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * codes and any code with a single symbol which in deflate is coded as one 3359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * bit instead of zero bits. See the format notes for fixed() and dynamic(). 3369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 3379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Within a given code length, the symbols are kept in ascending order for 3389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * the code bits definition. 3399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 340ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hugheslocal int construct(struct huffman *h, const short *length, int n) 3419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 3429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int symbol; /* current symbol when stepping through length[] */ 3439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int len; /* current length when stepping through h->count[] */ 3449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int left; /* number of possible codes left of current length */ 3459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project short offs[MAXBITS+1]; /* offsets in symbol table for each length */ 3469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* count number of codes of each length */ 3489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (len = 0; len <= MAXBITS; len++) 3499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project h->count[len] = 0; 3509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (symbol = 0; symbol < n; symbol++) 3519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project (h->count[length[symbol]])++; /* assumes lengths are within bounds */ 3529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (h->count[0] == n) /* no codes! */ 3539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return 0; /* complete, but decode() will fail */ 3549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* check for an over-subscribed or incomplete set of lengths */ 3569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project left = 1; /* one possible code of zero length */ 3579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (len = 1; len <= MAXBITS; len++) { 3589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project left <<= 1; /* one more bit, double codes left */ 3599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project left -= h->count[len]; /* deduct count from possible codes */ 360ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes if (left < 0) 361ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes return left; /* over-subscribed--return negative */ 3629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } /* left > 0 means incomplete */ 3639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* generate offsets into symbol table for each length for sorting */ 3659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project offs[1] = 0; 3669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (len = 1; len < MAXBITS; len++) 3679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project offs[len + 1] = offs[len] + h->count[len]; 3689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* 3709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * put symbols in table sorted by length, by symbol order within each 3719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * length 3729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 3739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (symbol = 0; symbol < n; symbol++) 3749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (length[symbol] != 0) 3759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project h->symbol[offs[length[symbol]]++] = symbol; 3769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* return zero for complete set, positive for incomplete set */ 3789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return left; 3799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 3809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* 3829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Decode literal/length and distance codes until an end-of-block code. 3839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 3849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Format notes: 3859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 3869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Compressed data that is after the block type if fixed or after the code 3879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * description if dynamic is a combination of literals and length/distance 3889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * pairs terminated by and end-of-block code. Literals are simply Huffman 3899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * coded bytes. A length/distance pair is a coded length followed by a 3909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * coded distance to represent a string that occurs earlier in the 3919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * uncompressed data that occurs again at the current location. 3929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 3939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Literals, lengths, and the end-of-block code are combined into a single 3949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * code of up to 286 symbols. They are 256 literals (0..255), 29 length 3959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * symbols (257..285), and the end-of-block symbol (256). 3969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 3979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - There are 256 possible lengths (3..258), and so 29 symbols are not enough 3989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * to represent all of those. Lengths 3..10 and 258 are in fact represented 3999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * by just a length symbol. Lengths 11..257 are represented as a symbol and 4009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * some number of extra bits that are added as an integer to the base length 4019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * of the length symbol. The number of extra bits is determined by the base 4029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * length symbol. These are in the static arrays below, lens[] for the base 4039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * lengths and lext[] for the corresponding number of extra bits. 4049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 4059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - The reason that 258 gets its own symbol is that the longest length is used 4069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * often in highly redundant files. Note that 258 can also be coded as the 4079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * base value 227 plus the maximum extra value of 31. While a good deflate 4089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * should never do this, it is not an error, and should be decoded properly. 4099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 4109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - If a length is decoded, including its extra bits if any, then it is 4119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * followed a distance code. There are up to 30 distance symbols. Again 4129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * there are many more possible distances (1..32768), so extra bits are added 4139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * to a base value represented by the symbol. The distances 1..4 get their 4149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * own symbol, but the rest require extra bits. The base distances and 4159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * corresponding number of extra bits are below in the static arrays dist[] 4169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * and dext[]. 4179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 4189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Literal bytes are simply written to the output. A length/distance pair is 4199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * an instruction to copy previously uncompressed bytes to the output. The 4209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * copy is from distance bytes back in the output stream, copying for length 4219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * bytes. 4229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 4239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Distances pointing before the beginning of the output data are not 4249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * permitted. 4259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 4269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Overlapped copies, where the length is greater than the distance, are 4279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * allowed and common. For example, a distance of one and a length of 258 4289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * simply copies the last byte 258 times. A distance of four and a length of 4299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * twelve copies the last four bytes three times. A simple forward copy 4309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * ignoring whether the length is greater than the distance or not implements 4319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * this correctly. You should not use memcpy() since its behavior is not 4329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * defined for overlapped arrays. You should not use memmove() or bcopy() 4339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * since though their behavior -is- defined for overlapping arrays, it is 4349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * defined to do the wrong thing in this case. 4359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 4369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal int codes(struct state *s, 437ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes const struct huffman *lencode, 438ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes const struct huffman *distcode) 4399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 4409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int symbol; /* decoded symbol */ 4419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int len; /* length for copy */ 4429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned dist; /* distance for copy */ 4439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project static const short lens[29] = { /* Size base for length codes 257..285 */ 4449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 4459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258}; 4469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project static const short lext[29] = { /* Extra bits for length codes 257..285 */ 4479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 4489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0}; 4499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project static const short dists[30] = { /* Offset base for distance codes 0..29 */ 4509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 4519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 4529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 8193, 12289, 16385, 24577}; 4539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project static const short dext[30] = { /* Extra bits for distance codes 0..29 */ 4549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 4559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 4569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 12, 12, 13, 13}; 4579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 4589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* decode literals and length/distance pairs */ 4599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project do { 4609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project symbol = decode(s, lencode); 461ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes if (symbol < 0) 462ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes return symbol; /* invalid symbol */ 4639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (symbol < 256) { /* literal: symbol is the byte */ 4649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* write out the literal */ 4659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (s->out != NIL) { 466ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes if (s->outcnt == s->outlen) 467ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes return 1; 4689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->out[s->outcnt] = symbol; 4699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 4709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->outcnt++; 4719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 4729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project else if (symbol > 256) { /* length */ 4739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* get and compute length */ 4749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project symbol -= 257; 475ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes if (symbol >= 29) 476ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes return -10; /* invalid fixed code */ 4779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project len = lens[symbol] + bits(s, lext[symbol]); 4789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 4799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* get and check distance */ 4809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project symbol = decode(s, distcode); 481ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes if (symbol < 0) 482ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes return symbol; /* invalid symbol */ 4839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project dist = dists[symbol] + bits(s, dext[symbol]); 484381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes#ifndef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR 4859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (dist > s->outcnt) 486381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes return -11; /* distance too far back */ 487381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes#endif 4889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 4899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* copy length bytes from distance bytes back */ 4909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (s->out != NIL) { 491ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes if (s->outcnt + len > s->outlen) 492ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes return 1; 4939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project while (len--) { 494381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes s->out[s->outcnt] = 495381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR 496ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes dist > s->outcnt ? 497ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes 0 : 498381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes#endif 499ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes s->out[s->outcnt - dist]; 5009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->outcnt++; 5019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 5029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 5039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project else 5049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->outcnt += len; 5059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 5069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } while (symbol != 256); /* end of block symbol */ 5079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 5089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* done with a valid fixed or dynamic block */ 5099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return 0; 5109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 5119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 5129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* 5139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Process a fixed codes block. 5149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 5159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Format notes: 5169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 5179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - This block type can be useful for compressing small amounts of data for 5189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * which the size of the code descriptions in a dynamic block exceeds the 5199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * benefit of custom codes for that block. For fixed codes, no bits are 5209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * spent on code descriptions. Instead the code lengths for literal/length 5219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * codes and distance codes are fixed. The specific lengths for each symbol 5229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * can be seen in the "for" loops below. 5239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 5249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - The literal/length code is complete, but has two symbols that are invalid 5259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * and should result in an error if received. This cannot be implemented 5269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * simply as an incomplete code since those two symbols are in the "middle" 5279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * of the code. They are eight bits long and the longest literal/length\ 5289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * code is nine bits. Therefore the code must be constructed with those 5299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * symbols, and the invalid symbols must be detected after decoding. 5309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 5319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - The fixed distance codes also have two invalid symbols that should result 5329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * in an error if received. Since all of the distance codes are the same 5339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * length, this can be implemented as an incomplete code. Then the invalid 5349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * codes are detected while decoding. 5359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 5369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal int fixed(struct state *s) 5379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 5389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project static int virgin = 1; 5399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project static short lencnt[MAXBITS+1], lensym[FIXLCODES]; 5409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project static short distcnt[MAXBITS+1], distsym[MAXDCODES]; 541381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes static struct huffman lencode, distcode; 5429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 5439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* build fixed huffman tables if first call (may not be thread safe) */ 5449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (virgin) { 5459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int symbol; 5469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project short lengths[FIXLCODES]; 5479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 548ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes /* construct lencode and distcode */ 549ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes lencode.count = lencnt; 550ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes lencode.symbol = lensym; 551ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes distcode.count = distcnt; 552ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes distcode.symbol = distsym; 553ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes 5549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* literal/length table */ 5559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (symbol = 0; symbol < 144; symbol++) 5569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project lengths[symbol] = 8; 5579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (; symbol < 256; symbol++) 5589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project lengths[symbol] = 9; 5599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (; symbol < 280; symbol++) 5609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project lengths[symbol] = 7; 5619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (; symbol < FIXLCODES; symbol++) 5629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project lengths[symbol] = 8; 5639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project construct(&lencode, lengths, FIXLCODES); 5649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 5659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* distance table */ 5669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (symbol = 0; symbol < MAXDCODES; symbol++) 5679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project lengths[symbol] = 5; 5689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project construct(&distcode, lengths, MAXDCODES); 5699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 5709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* do this just once */ 5719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project virgin = 0; 5729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 5739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 5749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* decode data until end-of-block code */ 5759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return codes(s, &lencode, &distcode); 5769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 5779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 5789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* 5799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Process a dynamic codes block. 5809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 5819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Format notes: 5829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 5839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - A dynamic block starts with a description of the literal/length and 5849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * distance codes for that block. New dynamic blocks allow the compressor to 5859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * rapidly adapt to changing data with new codes optimized for that data. 5869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 5879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - The codes used by the deflate format are "canonical", which means that 5889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * the actual bits of the codes are generated in an unambiguous way simply 5899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * from the number of bits in each code. Therefore the code descriptions 5909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * are simply a list of code lengths for each symbol. 5919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 5929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - The code lengths are stored in order for the symbols, so lengths are 5939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * provided for each of the literal/length symbols, and for each of the 5949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * distance symbols. 5959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 5969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - If a symbol is not used in the block, this is represented by a zero as 5979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * as the code length. This does not mean a zero-length code, but rather 5989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * that no code should be created for this symbol. There is no way in the 5999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * deflate format to represent a zero-length code. 6009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 6019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - The maximum number of bits in a code is 15, so the possible lengths for 6029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * any code are 1..15. 6039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 6049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - The fact that a length of zero is not permitted for a code has an 6059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * interesting consequence. Normally if only one symbol is used for a given 6069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * code, then in fact that code could be represented with zero bits. However 6079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * in deflate, that code has to be at least one bit. So for example, if 6089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * only a single distance base symbol appears in a block, then it will be 6099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * represented by a single code of length one, in particular one 0 bit. This 6109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * is an incomplete code, since if a 1 bit is received, it has no meaning, 6119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * and should result in an error. So incomplete distance codes of one symbol 6129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * should be permitted, and the receipt of invalid codes should be handled. 6139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 6149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - It is also possible to have a single literal/length code, but that code 6159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * must be the end-of-block code, since every dynamic block has one. This 6169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * is not the most efficient way to create an empty block (an empty fixed 6179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * block is fewer bits), but it is allowed by the format. So incomplete 6189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * literal/length codes of one symbol should also be permitted. 6199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 6209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - If there are only literal codes and no lengths, then there are no distance 6219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * codes. This is represented by one distance code with zero bits. 6229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 6239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - The list of up to 286 length/literal lengths and up to 30 distance lengths 6249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * are themselves compressed using Huffman codes and run-length encoding. In 6259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * the list of code lengths, a 0 symbol means no code, a 1..15 symbol means 6269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * that length, and the symbols 16, 17, and 18 are run-length instructions. 6279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Each of 16, 17, and 18 are follwed by extra bits to define the length of 6289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * the run. 16 copies the last length 3 to 6 times. 17 represents 3 to 10 6299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * zero lengths, and 18 represents 11 to 138 zero lengths. Unused symbols 6309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * are common, hence the special coding for zero lengths. 6319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 6329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - The symbols for 0..18 are Huffman coded, and so that code must be 6339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * described first. This is simply a sequence of up to 19 three-bit values 6349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * representing no code (0) or the code length for that symbol (1..7). 6359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 6369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - A dynamic block starts with three fixed-size counts from which is computed 6379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * the number of literal/length code lengths, the number of distance code 6389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * lengths, and the number of code length code lengths (ok, you come up with 6399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * a better name!) in the code descriptions. For the literal/length and 6409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * distance codes, lengths after those provided are considered zero, i.e. no 6419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * code. The code length code lengths are received in a permuted order (see 6429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * the order[] array below) to make a short code length code length list more 6439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * likely. As it turns out, very short and very long codes are less likely 6449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * to be seen in a dynamic code description, hence what may appear initially 6459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * to be a peculiar ordering. 6469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 6479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Given the number of literal/length code lengths (nlen) and distance code 6489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * lengths (ndist), then they are treated as one long list of nlen + ndist 6499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * code lengths. Therefore run-length coding can and often does cross the 6509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * boundary between the two sets of lengths. 6519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 6529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - So to summarize, the code description at the start of a dynamic block is 6539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * three counts for the number of code lengths for the literal/length codes, 6549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * the distance codes, and the code length codes. This is followed by the 6559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * code length code lengths, three bits each. This is used to construct the 6569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * code length code which is used to read the remainder of the lengths. Then 6579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * the literal/length code lengths and distance lengths are read as a single 6589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * set of lengths using the code length codes. Codes are constructed from 6599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * the resulting two sets of lengths, and then finally you can start 6609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * decoding actual compressed data in the block. 6619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 6629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - For reference, a "typical" size for the code description in a dynamic 6639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * block is around 80 bytes. 6649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 6659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal int dynamic(struct state *s) 6669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 6679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int nlen, ndist, ncode; /* number of lengths in descriptor */ 6689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int index; /* index of lengths[] */ 6699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int err; /* construct() return value */ 6709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project short lengths[MAXCODES]; /* descriptor code lengths */ 6719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project short lencnt[MAXBITS+1], lensym[MAXLCODES]; /* lencode memory */ 6729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project short distcnt[MAXBITS+1], distsym[MAXDCODES]; /* distcode memory */ 673381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes struct huffman lencode, distcode; /* length and distance codes */ 6749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project static const short order[19] = /* permutation of code length codes */ 6759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 6769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 677381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes /* construct lencode and distcode */ 678381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes lencode.count = lencnt; 679381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes lencode.symbol = lensym; 680381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes distcode.count = distcnt; 681381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes distcode.symbol = distsym; 682381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes 6839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* get number of lengths in each table, check lengths */ 6849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project nlen = bits(s, 5) + 257; 6859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ndist = bits(s, 5) + 1; 6869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ncode = bits(s, 4) + 4; 6879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (nlen > MAXLCODES || ndist > MAXDCODES) 6889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return -3; /* bad counts */ 6899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 6909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* read code length code lengths (really), missing lengths are zero */ 6919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (index = 0; index < ncode; index++) 6929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project lengths[order[index]] = bits(s, 3); 6939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (; index < 19; index++) 6949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project lengths[order[index]] = 0; 6959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 6969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* build huffman table for code lengths codes (use lencode temporarily) */ 6979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project err = construct(&lencode, lengths, 19); 698ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes if (err != 0) /* require complete code set here */ 699ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes return -4; 7009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 7019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* read length/literal and distance code length tables */ 7029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project index = 0; 7039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project while (index < nlen + ndist) { 7049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int symbol; /* decoded value */ 7059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int len; /* last length to repeat */ 7069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 7079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project symbol = decode(s, &lencode); 70804351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes if (symbol < 0) 70904351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes return symbol; /* invalid symbol */ 7109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (symbol < 16) /* length in 0..15 */ 7119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project lengths[index++] = symbol; 7129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project else { /* repeat instruction */ 7139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project len = 0; /* assume repeating zeros */ 7149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (symbol == 16) { /* repeat last length 3..6 times */ 715ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes if (index == 0) 716ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes return -5; /* no last length! */ 7179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project len = lengths[index - 1]; /* last length */ 7189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project symbol = 3 + bits(s, 2); 7199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 7209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project else if (symbol == 17) /* repeat zero 3..10 times */ 7219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project symbol = 3 + bits(s, 3); 7229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project else /* == 18, repeat zero 11..138 times */ 7239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project symbol = 11 + bits(s, 7); 7249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (index + symbol > nlen + ndist) 7259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return -6; /* too many lengths! */ 7269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project while (symbol--) /* repeat last or zero symbol times */ 7279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project lengths[index++] = len; 7289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 7299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 7309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 731381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes /* check for end-of-block code -- there better be one! */ 732381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes if (lengths[256] == 0) 733381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes return -9; 734381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes 7359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* build huffman table for literal/length codes */ 7369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project err = construct(&lencode, lengths, nlen); 737ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes if (err && (err < 0 || nlen != lencode.count[0] + lencode.count[1])) 738ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes return -7; /* incomplete code ok only for single length 1 code */ 7399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 7409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* build huffman table for distance codes */ 7419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project err = construct(&distcode, lengths + nlen, ndist); 742ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes if (err && (err < 0 || ndist != distcode.count[0] + distcode.count[1])) 743ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes return -8; /* incomplete code ok only for single length 1 code */ 7449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 7459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* decode data until end-of-block code */ 7469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return codes(s, &lencode, &distcode); 7479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 7489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 7499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* 7509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Inflate source to dest. On return, destlen and sourcelen are updated to the 7519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * size of the uncompressed data and the size of the deflate data respectively. 7529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * On success, the return value of puff() is zero. If there is an error in the 7539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * source data, i.e. it is not in the deflate format, then a negative value is 7549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * returned. If there is not enough input available or there is not enough 7559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * output space, then a positive error is returned. In that case, destlen and 7569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * sourcelen are not updated to facilitate retrying from the beginning with the 7579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * provision of more input data or more output space. In the case of invalid 7589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * inflate data (a negative error), the dest and source pointers are updated to 7599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * facilitate the debugging of deflators. 7609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 7619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * puff() also has a mode to determine the size of the uncompressed output with 7629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * no output written. For this dest must be (unsigned char *)0. In this case, 7639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * the input value of *destlen is ignored, and on return *destlen is set to the 7649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * size of the uncompressed output. 7659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 7669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * The return codes are: 7679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 7689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 2: available inflate data did not terminate 7699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 1: output space exhausted before completing inflate 7709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 0: successful inflate 7719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * -1: invalid block type (type == 3) 7729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * -2: stored block length did not match one's complement 7739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * -3: dynamic block code description: too many length or distance codes 7749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * -4: dynamic block code description: code lengths codes incomplete 7759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * -5: dynamic block code description: repeat lengths with no first length 7769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * -6: dynamic block code description: repeat more than specified lengths 7779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * -7: dynamic block code description: invalid literal/length code lengths 7789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * -8: dynamic block code description: invalid distance code lengths 779381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * -9: dynamic block code description: missing end-of-block code 780381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * -10: invalid literal/length or distance code in fixed or dynamic block 781381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * -11: distance is too far back in fixed or dynamic block 7829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 7839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Format notes: 7849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 7859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - Three bits are read for each block to determine the kind of block and 7869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * whether or not it is the last block. Then the block is decoded and the 7879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * process repeated if it was not the last block. 7889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 7899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * - The leftover bits in the last byte of the deflate data after the last 7909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * block (if it was a fixed or dynamic block) are undefined and have no 7919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * expected values to check. 7929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 7939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectint puff(unsigned char *dest, /* pointer to destination pointer */ 7949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned long *destlen, /* amount of output space */ 795ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes const unsigned char *source, /* pointer to source data pointer */ 7969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned long *sourcelen) /* amount of input available */ 7979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 7989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project struct state s; /* input/output state */ 7999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int last, type; /* block information */ 8009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int err; /* return value */ 8019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 8029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* initialize output state */ 8039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s.out = dest; 8049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s.outlen = *destlen; /* ignored if dest is NIL */ 8059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s.outcnt = 0; 8069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 8079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* initialize input state */ 8089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s.in = source; 8099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s.inlen = *sourcelen; 8109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s.incnt = 0; 8119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s.bitbuf = 0; 8129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s.bitcnt = 0; 8139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 8149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* return if bits() or decode() tries to read past available input */ 8159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (setjmp(s.env) != 0) /* if came back here via longjmp() */ 8169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project err = 2; /* then skip do-loop, return error */ 8179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project else { 8189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* process blocks until last block or error */ 8199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project do { 8209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project last = bits(&s, 1); /* one if last block */ 8219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project type = bits(&s, 2); /* block type 0..3 */ 822ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes err = type == 0 ? 823ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes stored(&s) : 824ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes (type == 1 ? 825ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes fixed(&s) : 826ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes (type == 2 ? 827ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes dynamic(&s) : 828ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes -1)); /* type == 3, invalid */ 829ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes if (err != 0) 830ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes break; /* return with error */ 8319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } while (!last); 8329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 8339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 8349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* update the lengths and return */ 8359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (err <= 0) { 8369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project *destlen = s.outcnt; 8379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project *sourcelen = s.incnt; 8389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 8399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return err; 8409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 841