1b33c96954667ba382fa595baf7b31290bfdd517vboxsync/*
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * puff.c
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Copyright (C) 2002-2010 Mark Adler
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * For conditions of distribution and use, see copyright notice in puff.h
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * version 2.2, 25 Apr 2010
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * puff.c is a simple inflate written to be an unambiguous way to specify the
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * deflate format. It is not written for speed but rather simplicity. As a
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * side benefit, this code might actually be useful when small code is more
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * important than speed, such as bootstrap applications. For typical deflate
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * data, zlib's inflate() is about four times as fast as puff(). zlib's
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * inflate compiles to around 20K on my machine, whereas puff.c compiles to
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * around 4K on my machine (a PowerPC using GNU cc). If the faster decode()
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * function here is used, then puff() is only twice as slow as zlib's
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * inflate().
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * All dynamically allocated memory comes from the stack. The stack required
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * is less than 2K bytes. This code is compatible with 16-bit int's and
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * assumes that long's are at least 32 bits. puff.c uses the short data type,
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * assumed to be 16 bits, for arrays in order to to conserve memory. The code
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * works whether integers are stored big endian or little endian.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * In the comments below are "Format notes" that describe the inflate process
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * and document some of the less obvious aspects of the format. This source
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * code is meant to supplement RFC 1951, which formally describes the deflate
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * format:
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * http://www.zlib.org/rfc-deflate.html
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync/*
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Change history:
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * 1.0 10 Feb 2002 - First version
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * 1.1 17 Feb 2002 - Clarifications of some comments and notes
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Update puff() dest and source pointers on negative
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * errors to facilitate debugging deflators
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Remove longest from struct huffman -- not needed
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Simplify offs[] index in construct()
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Add input size and checking, using longjmp() to
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * maintain easy readability
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Use short data type for large arrays
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Use pointers instead of long to specify source and
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * destination sizes to avoid arbitrary 4 GB limits
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * 1.2 17 Mar 2002 - Add faster version of decode(), doubles speed (!),
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * but leave simple version for readabilty
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Make sure invalid distances detected if pointers
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * are 16 bits
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Fix fixed codes table error
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Provide a scanning mode for determining size of
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * uncompressed data
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * 1.3 20 Mar 2002 - Go back to lengths for puff() parameters [Gailly]
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Add a puff.h file for the interface
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Add braces in puff() for else do [Gailly]
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Use indexes instead of pointers for readability
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * 1.4 31 Mar 2002 - Simplify construct() code set check
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Fix some comments
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Add FIXLCODES #define
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * 1.5 6 Apr 2002 - Minor comment fixes
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * 1.6 7 Aug 2002 - Minor format changes
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * 1.7 3 Mar 2003 - Added test code for distribution
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Added zlib-like license
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * 1.8 9 Jan 2004 - Added some comments on no distance codes case
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * 1.9 21 Feb 2008 - Fix bug on 16-bit integer architectures [Pohland]
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Catch missing end-of-block symbol error
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * 2.0 25 Jul 2008 - Add #define to permit distance too far back
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Add option in TEST code for puff to write the data
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Add option in TEST code to skip input bytes
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Allow TEST code to read from piped stdin
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * 2.1 4 Apr 2010 - Avoid variable initialization for happier compilers
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Avoid unsigned comparisons for even happier compilers
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * 2.2 25 Apr 2010 - Fix bug in variable initializations [Oberhumer]
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Add const where appropriate [Oberhumer]
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Split if's and ?'s for coverage testing
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Break out test code to separate file
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Move NIL to puff.h
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Allow incomplete code only if single code length is 1
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Add full code coverage test to Makefile
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync#include <setjmp.h> /* for setjmp(), longjmp(), and jmp_buf */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync#include "puff.h" /* prototype for puff() */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync#define local static /* for local function definitions */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync/*
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Maximums for allocations and loops. It is not useful to change these --
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * they are fixed by the deflate format.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync#define MAXBITS 15 /* maximum bits in a code */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync#define MAXLCODES 286 /* maximum number of literal/length codes */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync#define MAXDCODES 30 /* maximum number of distance codes */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync#define MAXCODES (MAXLCODES+MAXDCODES) /* maximum codes lengths to read */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync#define FIXLCODES 288 /* number of fixed literal/length codes */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync/* input and output state */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsyncstruct state {
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* output state */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync unsigned char *out; /* output buffer */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync unsigned long outlen; /* available space at out */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync unsigned long outcnt; /* bytes written to out so far */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* input state */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync const unsigned char *in; /* input buffer */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync unsigned long inlen; /* available input at in */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync unsigned long incnt; /* bytes read so far */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int bitbuf; /* bit buffer */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int bitcnt; /* number of bits in bit buffer */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* input limit error return state for bits() and decode() */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync jmp_buf env;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync};
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync/*
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Return need bits from the input stream. This always leaves less than
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * eight bits in the buffer. bits() works properly for need == 0.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Format notes:
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Bits are stored in bytes from the least significant bit to the most
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * significant bit. Therefore bits are dropped from the bottom of the bit
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * buffer, using shift right, and new bytes are appended to the top of the
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * bit buffer, using shift left.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsynclocal int bits(struct state *s, int need)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync{
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync long val; /* bit accumulator (can use up to 20 bits) */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* load at least need bits into val */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync val = s->bitbuf;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync while (s->bitcnt < need) {
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (s->incnt == s->inlen)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync longjmp(s->env, 1); /* out of input */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync val |= (long)(s->in[s->incnt++]) << s->bitcnt; /* load eight bits */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s->bitcnt += 8;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync }
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* drop need bits and update buffer, always zero to seven bits left */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s->bitbuf = (int)(val >> need);
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s->bitcnt -= need;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* return need bits, zeroing the bits above that */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return (int)(val & ((1L << need) - 1));
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync}
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync/*
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Process a stored block.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Format notes:
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - After the two-bit stored block type (00), the stored block length and
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * stored bytes are byte-aligned for fast copying. Therefore any leftover
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * bits in the byte that has the last bit of the type, as many as seven, are
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * discarded. The value of the discarded bits are not defined and should not
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * be checked against any expectation.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - The second inverted copy of the stored block length does not have to be
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * checked, but it's probably a good idea to do so anyway.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - A stored block can have zero length. This is sometimes used to byte-align
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * subsets of the compressed data for random access or partial recovery.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsynclocal int stored(struct state *s)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync{
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync unsigned len; /* length of stored block */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* discard leftover bits from current byte (assumes s->bitcnt < 8) */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s->bitbuf = 0;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s->bitcnt = 0;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* get length and check against its one's complement */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (s->incnt + 4 > s->inlen)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return 2; /* not enough input */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync len = s->in[s->incnt++];
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync len |= s->in[s->incnt++] << 8;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (s->in[s->incnt++] != (~len & 0xff) ||
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s->in[s->incnt++] != ((~len >> 8) & 0xff))
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return -2; /* didn't match complement! */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* copy len bytes from in to out */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (s->incnt + len > s->inlen)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return 2; /* not enough input */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (s->out != NIL) {
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (s->outcnt + len > s->outlen)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return 1; /* not enough output space */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync while (len--)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s->out[s->outcnt++] = s->in[s->incnt++];
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync }
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync else { /* just scanning */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s->outcnt += len;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s->incnt += len;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync }
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* done with a valid stored block */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return 0;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync}
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync/*
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Huffman code decoding tables. count[1..MAXBITS] is the number of symbols of
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * each length, which for a canonical code are stepped through in order.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * symbol[] are the symbol values in canonical order, where the number of
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * entries is the sum of the counts in count[]. The decoding process can be
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * seen in the function decode() below.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsyncstruct huffman {
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync short *count; /* number of symbols of each length */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync short *symbol; /* canonically ordered symbols */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync};
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync/*
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Decode a code from the stream s using huffman table h. Return the symbol or
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * a negative value if there is an error. If all of the lengths are zero, i.e.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * an empty code, or if the code is incomplete and an invalid code is received,
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * then -10 is returned after reading MAXBITS bits.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Format notes:
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - The codes as stored in the compressed data are bit-reversed relative to
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * a simple integer ordering of codes of the same lengths. Hence below the
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * bits are pulled from the compressed data one at a time and used to
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * build the code value reversed from what is in the stream in order to
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * permit simple integer comparisons for decoding. A table-based decoding
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * scheme (as used in zlib) does not need to do this reversal.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - The first code for the shortest length is all zeros. Subsequent codes of
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * the same length are simply integer increments of the previous code. When
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * moving up a length, a zero bit is appended to the code. For a complete
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * code, the last code of the longest length will be all ones.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Incomplete codes are handled by this decoder, since they are permitted
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * in the deflate format. See the format notes for fixed() and dynamic().
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync#ifdef SLOW
1b33c96954667ba382fa595baf7b31290bfdd517vboxsynclocal int decode(struct state *s, const struct huffman *h)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync{
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int len; /* current number of bits in code */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int code; /* len bits being decoded */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int first; /* first code of length len */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int count; /* number of codes of length len */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int index; /* index of first code of length len in symbol table */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync code = first = index = 0;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync for (len = 1; len <= MAXBITS; len++) {
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync code |= bits(s, 1); /* get next bit */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync count = h->count[len];
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (code - count < first) /* if length len, return symbol */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return h->symbol[index + (code - first)];
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync index += count; /* else update for next length */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync first += count;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync first <<= 1;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync code <<= 1;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync }
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return -10; /* ran out of codes */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync}
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync/*
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * A faster version of decode() for real applications of this code. It's not
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * as readable, but it makes puff() twice as fast. And it only makes the code
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * a few percent larger.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync#else /* !SLOW */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsynclocal int decode(struct state *s, const struct huffman *h)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync{
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int len; /* current number of bits in code */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int code; /* len bits being decoded */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int first; /* first code of length len */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int count; /* number of codes of length len */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int index; /* index of first code of length len in symbol table */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int bitbuf; /* bits from stream */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int left; /* bits left in next or left to process */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync short *next; /* next number of codes */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync bitbuf = s->bitbuf;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync left = s->bitcnt;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync code = first = index = 0;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync len = 1;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync next = h->count + 1;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync while (1) {
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync while (left--) {
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync code |= bitbuf & 1;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync bitbuf >>= 1;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync count = *next++;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (code - count < first) { /* if length len, return symbol */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s->bitbuf = bitbuf;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s->bitcnt = (s->bitcnt - len) & 7;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return h->symbol[index + (code - first)];
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync }
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync index += count; /* else update for next length */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync first += count;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync first <<= 1;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync code <<= 1;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync len++;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync }
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync left = (MAXBITS+1) - len;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (left == 0)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync break;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (s->incnt == s->inlen)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync longjmp(s->env, 1); /* out of input */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync bitbuf = s->in[s->incnt++];
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (left > 8)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync left = 8;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync }
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return -10; /* ran out of codes */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync}
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync#endif /* SLOW */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync/*
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Given the list of code lengths length[0..n-1] representing a canonical
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Huffman code for n symbols, construct the tables required to decode those
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * codes. Those tables are the number of codes of each length, and the symbols
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * sorted by length, retaining their original order within each length. The
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * return value is zero for a complete code set, negative for an over-
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * subscribed code set, and positive for an incomplete code set. The tables
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * can be used if the return value is zero or positive, but they cannot be used
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * if the return value is negative. If the return value is zero, it is not
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * possible for decode() using that table to return an error--any stream of
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * enough bits will resolve to a symbol. If the return value is positive, then
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * it is possible for decode() using that table to return an error for received
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * codes past the end of the incomplete lengths.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Not used by decode(), but used for error checking, h->count[0] is the number
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * of the n symbols not in the code. So n - h->count[0] is the number of
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * codes. This is useful for checking for incomplete codes that have more than
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * one symbol, which is an error in a dynamic block.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Assumption: for all i in 0..n-1, 0 <= length[i] <= MAXBITS
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * This is assured by the construction of the length arrays in dynamic() and
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * fixed() and is not verified by construct().
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Format notes:
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Permitted and expected examples of incomplete codes are one of the fixed
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * codes and any code with a single symbol which in deflate is coded as one
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * bit instead of zero bits. See the format notes for fixed() and dynamic().
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Within a given code length, the symbols are kept in ascending order for
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * the code bits definition.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsynclocal int construct(struct huffman *h, const short *length, int n)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync{
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int symbol; /* current symbol when stepping through length[] */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int len; /* current length when stepping through h->count[] */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int left; /* number of possible codes left of current length */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync short offs[MAXBITS+1]; /* offsets in symbol table for each length */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* count number of codes of each length */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync for (len = 0; len <= MAXBITS; len++)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync h->count[len] = 0;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync for (symbol = 0; symbol < n; symbol++)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync (h->count[length[symbol]])++; /* assumes lengths are within bounds */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (h->count[0] == n) /* no codes! */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return 0; /* complete, but decode() will fail */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* check for an over-subscribed or incomplete set of lengths */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync left = 1; /* one possible code of zero length */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync for (len = 1; len <= MAXBITS; len++) {
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync left <<= 1; /* one more bit, double codes left */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync left -= h->count[len]; /* deduct count from possible codes */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (left < 0)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return left; /* over-subscribed--return negative */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync } /* left > 0 means incomplete */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* generate offsets into symbol table for each length for sorting */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync offs[1] = 0;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync for (len = 1; len < MAXBITS; len++)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync offs[len + 1] = offs[len] + h->count[len];
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /*
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * put symbols in table sorted by length, by symbol order within each
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * length
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync for (symbol = 0; symbol < n; symbol++)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (length[symbol] != 0)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync h->symbol[offs[length[symbol]]++] = symbol;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* return zero for complete set, positive for incomplete set */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return left;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync}
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync/*
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Decode literal/length and distance codes until an end-of-block code.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Format notes:
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Compressed data that is after the block type if fixed or after the code
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * description if dynamic is a combination of literals and length/distance
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * pairs terminated by and end-of-block code. Literals are simply Huffman
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * coded bytes. A length/distance pair is a coded length followed by a
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * coded distance to represent a string that occurs earlier in the
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * uncompressed data that occurs again at the current location.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Literals, lengths, and the end-of-block code are combined into a single
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * code of up to 286 symbols. They are 256 literals (0..255), 29 length
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * symbols (257..285), and the end-of-block symbol (256).
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - There are 256 possible lengths (3..258), and so 29 symbols are not enough
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * to represent all of those. Lengths 3..10 and 258 are in fact represented
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * by just a length symbol. Lengths 11..257 are represented as a symbol and
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * some number of extra bits that are added as an integer to the base length
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * of the length symbol. The number of extra bits is determined by the base
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * length symbol. These are in the static arrays below, lens[] for the base
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * lengths and lext[] for the corresponding number of extra bits.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - The reason that 258 gets its own symbol is that the longest length is used
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * often in highly redundant files. Note that 258 can also be coded as the
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * base value 227 plus the maximum extra value of 31. While a good deflate
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * should never do this, it is not an error, and should be decoded properly.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - If a length is decoded, including its extra bits if any, then it is
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * followed a distance code. There are up to 30 distance symbols. Again
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * there are many more possible distances (1..32768), so extra bits are added
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * to a base value represented by the symbol. The distances 1..4 get their
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * own symbol, but the rest require extra bits. The base distances and
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * corresponding number of extra bits are below in the static arrays dist[]
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * and dext[].
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Literal bytes are simply written to the output. A length/distance pair is
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * an instruction to copy previously uncompressed bytes to the output. The
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * copy is from distance bytes back in the output stream, copying for length
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * bytes.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Distances pointing before the beginning of the output data are not
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * permitted.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Overlapped copies, where the length is greater than the distance, are
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * allowed and common. For example, a distance of one and a length of 258
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * simply copies the last byte 258 times. A distance of four and a length of
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * twelve copies the last four bytes three times. A simple forward copy
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * ignoring whether the length is greater than the distance or not implements
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * this correctly. You should not use memcpy() since its behavior is not
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * defined for overlapped arrays. You should not use memmove() or bcopy()
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * since though their behavior -is- defined for overlapping arrays, it is
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * defined to do the wrong thing in this case.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsynclocal int codes(struct state *s,
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync const struct huffman *lencode,
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync const struct huffman *distcode)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync{
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int symbol; /* decoded symbol */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int len; /* length for copy */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync unsigned dist; /* distance for copy */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync static const short lens[29] = { /* Size base for length codes 257..285 */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258};
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync static const short lext[29] = { /* Extra bits for length codes 257..285 */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0};
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync static const short dists[30] = { /* Offset base for distance codes 0..29 */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync 8193, 12289, 16385, 24577};
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync static const short dext[30] = { /* Extra bits for distance codes 0..29 */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync 12, 12, 13, 13};
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* decode literals and length/distance pairs */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync do {
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync symbol = decode(s, lencode);
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (symbol < 0)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return symbol; /* invalid symbol */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (symbol < 256) { /* literal: symbol is the byte */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* write out the literal */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (s->out != NIL) {
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (s->outcnt == s->outlen)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return 1;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s->out[s->outcnt] = symbol;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync }
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s->outcnt++;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync }
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync else if (symbol > 256) { /* length */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* get and compute length */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync symbol -= 257;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (symbol >= 29)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return -10; /* invalid fixed code */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync len = lens[symbol] + bits(s, lext[symbol]);
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* get and check distance */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync symbol = decode(s, distcode);
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (symbol < 0)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return symbol; /* invalid symbol */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync dist = dists[symbol] + bits(s, dext[symbol]);
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync#ifndef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (dist > s->outcnt)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return -11; /* distance too far back */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync#endif
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* copy length bytes from distance bytes back */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (s->out != NIL) {
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (s->outcnt + len > s->outlen)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return 1;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync while (len--) {
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s->out[s->outcnt] =
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync dist > s->outcnt ?
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync 0 :
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync#endif
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s->out[s->outcnt - dist];
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s->outcnt++;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync }
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync }
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync else
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s->outcnt += len;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync }
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync } while (symbol != 256); /* end of block symbol */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* done with a valid fixed or dynamic block */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return 0;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync}
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync/*
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Process a fixed codes block.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Format notes:
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - This block type can be useful for compressing small amounts of data for
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * which the size of the code descriptions in a dynamic block exceeds the
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * benefit of custom codes for that block. For fixed codes, no bits are
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * spent on code descriptions. Instead the code lengths for literal/length
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * codes and distance codes are fixed. The specific lengths for each symbol
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * can be seen in the "for" loops below.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - The literal/length code is complete, but has two symbols that are invalid
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * and should result in an error if received. This cannot be implemented
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * simply as an incomplete code since those two symbols are in the "middle"
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * of the code. They are eight bits long and the longest literal/length\
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * code is nine bits. Therefore the code must be constructed with those
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * symbols, and the invalid symbols must be detected after decoding.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - The fixed distance codes also have two invalid symbols that should result
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * in an error if received. Since all of the distance codes are the same
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * length, this can be implemented as an incomplete code. Then the invalid
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * codes are detected while decoding.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsynclocal int fixed(struct state *s)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync{
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync static int virgin = 1;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync static short lencnt[MAXBITS+1], lensym[FIXLCODES];
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync static short distcnt[MAXBITS+1], distsym[MAXDCODES];
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync static struct huffman lencode, distcode;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* build fixed huffman tables if first call (may not be thread safe) */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (virgin) {
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int symbol;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync short lengths[FIXLCODES];
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* construct lencode and distcode */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync lencode.count = lencnt;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync lencode.symbol = lensym;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync distcode.count = distcnt;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync distcode.symbol = distsym;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* literal/length table */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync for (symbol = 0; symbol < 144; symbol++)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync lengths[symbol] = 8;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync for (; symbol < 256; symbol++)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync lengths[symbol] = 9;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync for (; symbol < 280; symbol++)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync lengths[symbol] = 7;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync for (; symbol < FIXLCODES; symbol++)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync lengths[symbol] = 8;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync construct(&lencode, lengths, FIXLCODES);
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* distance table */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync for (symbol = 0; symbol < MAXDCODES; symbol++)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync lengths[symbol] = 5;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync construct(&distcode, lengths, MAXDCODES);
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* do this just once */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync virgin = 0;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync }
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* decode data until end-of-block code */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return codes(s, &lencode, &distcode);
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync}
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync/*
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Process a dynamic codes block.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Format notes:
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - A dynamic block starts with a description of the literal/length and
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * distance codes for that block. New dynamic blocks allow the compressor to
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * rapidly adapt to changing data with new codes optimized for that data.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - The codes used by the deflate format are "canonical", which means that
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * the actual bits of the codes are generated in an unambiguous way simply
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * from the number of bits in each code. Therefore the code descriptions
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * are simply a list of code lengths for each symbol.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - The code lengths are stored in order for the symbols, so lengths are
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * provided for each of the literal/length symbols, and for each of the
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * distance symbols.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - If a symbol is not used in the block, this is represented by a zero as
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * as the code length. This does not mean a zero-length code, but rather
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * that no code should be created for this symbol. There is no way in the
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * deflate format to represent a zero-length code.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - The maximum number of bits in a code is 15, so the possible lengths for
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * any code are 1..15.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - The fact that a length of zero is not permitted for a code has an
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * interesting consequence. Normally if only one symbol is used for a given
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * code, then in fact that code could be represented with zero bits. However
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * in deflate, that code has to be at least one bit. So for example, if
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * only a single distance base symbol appears in a block, then it will be
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * represented by a single code of length one, in particular one 0 bit. This
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * is an incomplete code, since if a 1 bit is received, it has no meaning,
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * and should result in an error. So incomplete distance codes of one symbol
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * should be permitted, and the receipt of invalid codes should be handled.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - It is also possible to have a single literal/length code, but that code
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * must be the end-of-block code, since every dynamic block has one. This
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * is not the most efficient way to create an empty block (an empty fixed
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * block is fewer bits), but it is allowed by the format. So incomplete
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * literal/length codes of one symbol should also be permitted.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - If there are only literal codes and no lengths, then there are no distance
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * codes. This is represented by one distance code with zero bits.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - The list of up to 286 length/literal lengths and up to 30 distance lengths
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * are themselves compressed using Huffman codes and run-length encoding. In
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * the list of code lengths, a 0 symbol means no code, a 1..15 symbol means
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * that length, and the symbols 16, 17, and 18 are run-length instructions.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Each of 16, 17, and 18 are follwed by extra bits to define the length of
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * the run. 16 copies the last length 3 to 6 times. 17 represents 3 to 10
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * zero lengths, and 18 represents 11 to 138 zero lengths. Unused symbols
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * are common, hence the special coding for zero lengths.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - The symbols for 0..18 are Huffman coded, and so that code must be
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * described first. This is simply a sequence of up to 19 three-bit values
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * representing no code (0) or the code length for that symbol (1..7).
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - A dynamic block starts with three fixed-size counts from which is computed
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * the number of literal/length code lengths, the number of distance code
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * lengths, and the number of code length code lengths (ok, you come up with
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * a better name!) in the code descriptions. For the literal/length and
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * distance codes, lengths after those provided are considered zero, i.e. no
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * code. The code length code lengths are received in a permuted order (see
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * the order[] array below) to make a short code length code length list more
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * likely. As it turns out, very short and very long codes are less likely
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * to be seen in a dynamic code description, hence what may appear initially
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * to be a peculiar ordering.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Given the number of literal/length code lengths (nlen) and distance code
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * lengths (ndist), then they are treated as one long list of nlen + ndist
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * code lengths. Therefore run-length coding can and often does cross the
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * boundary between the two sets of lengths.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - So to summarize, the code description at the start of a dynamic block is
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * three counts for the number of code lengths for the literal/length codes,
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * the distance codes, and the code length codes. This is followed by the
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * code length code lengths, three bits each. This is used to construct the
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * code length code which is used to read the remainder of the lengths. Then
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * the literal/length code lengths and distance lengths are read as a single
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * set of lengths using the code length codes. Codes are constructed from
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * the resulting two sets of lengths, and then finally you can start
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * decoding actual compressed data in the block.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - For reference, a "typical" size for the code description in a dynamic
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * block is around 80 bytes.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsynclocal int dynamic(struct state *s)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync{
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int nlen, ndist, ncode; /* number of lengths in descriptor */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int index; /* index of lengths[] */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int err; /* construct() return value */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync short lengths[MAXCODES]; /* descriptor code lengths */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync short lencnt[MAXBITS+1], lensym[MAXLCODES]; /* lencode memory */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync short distcnt[MAXBITS+1], distsym[MAXDCODES]; /* distcode memory */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync struct huffman lencode, distcode; /* length and distance codes */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync static const short order[19] = /* permutation of code length codes */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* construct lencode and distcode */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync lencode.count = lencnt;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync lencode.symbol = lensym;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync distcode.count = distcnt;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync distcode.symbol = distsym;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* get number of lengths in each table, check lengths */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync nlen = bits(s, 5) + 257;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync ndist = bits(s, 5) + 1;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync ncode = bits(s, 4) + 4;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (nlen > MAXLCODES || ndist > MAXDCODES)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return -3; /* bad counts */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* read code length code lengths (really), missing lengths are zero */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync for (index = 0; index < ncode; index++)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync lengths[order[index]] = bits(s, 3);
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync for (; index < 19; index++)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync lengths[order[index]] = 0;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* build huffman table for code lengths codes (use lencode temporarily) */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync err = construct(&lencode, lengths, 19);
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (err != 0) /* require complete code set here */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return -4;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* read length/literal and distance code length tables */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync index = 0;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync while (index < nlen + ndist) {
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int symbol; /* decoded value */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int len; /* last length to repeat */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync symbol = decode(s, &lencode);
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (symbol < 16) /* length in 0..15 */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync lengths[index++] = symbol;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync else { /* repeat instruction */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync len = 0; /* assume repeating zeros */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (symbol == 16) { /* repeat last length 3..6 times */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (index == 0)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return -5; /* no last length! */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync len = lengths[index - 1]; /* last length */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync symbol = 3 + bits(s, 2);
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync }
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync else if (symbol == 17) /* repeat zero 3..10 times */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync symbol = 3 + bits(s, 3);
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync else /* == 18, repeat zero 11..138 times */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync symbol = 11 + bits(s, 7);
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (index + symbol > nlen + ndist)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return -6; /* too many lengths! */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync while (symbol--) /* repeat last or zero symbol times */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync lengths[index++] = len;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync }
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync }
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* check for end-of-block code -- there better be one! */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (lengths[256] == 0)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return -9;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* build huffman table for literal/length codes */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync err = construct(&lencode, lengths, nlen);
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (err && (err < 0 || nlen != lencode.count[0] + lencode.count[1]))
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return -7; /* incomplete code ok only for single length 1 code */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* build huffman table for distance codes */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync err = construct(&distcode, lengths + nlen, ndist);
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (err && (err < 0 || ndist != distcode.count[0] + distcode.count[1]))
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return -8; /* incomplete code ok only for single length 1 code */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* decode data until end-of-block code */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return codes(s, &lencode, &distcode);
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync}
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync/*
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Inflate source to dest. On return, destlen and sourcelen are updated to the
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * size of the uncompressed data and the size of the deflate data respectively.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * On success, the return value of puff() is zero. If there is an error in the
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * source data, i.e. it is not in the deflate format, then a negative value is
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * returned. If there is not enough input available or there is not enough
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * output space, then a positive error is returned. In that case, destlen and
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * sourcelen are not updated to facilitate retrying from the beginning with the
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * provision of more input data or more output space. In the case of invalid
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * inflate data (a negative error), the dest and source pointers are updated to
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * facilitate the debugging of deflators.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * puff() also has a mode to determine the size of the uncompressed output with
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * no output written. For this dest must be (unsigned char *)0. In this case,
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * the input value of *destlen is ignored, and on return *destlen is set to the
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * size of the uncompressed output.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * The return codes are:
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * 2: available inflate data did not terminate
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * 1: output space exhausted before completing inflate
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * 0: successful inflate
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * -1: invalid block type (type == 3)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * -2: stored block length did not match one's complement
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * -3: dynamic block code description: too many length or distance codes
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * -4: dynamic block code description: code lengths codes incomplete
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * -5: dynamic block code description: repeat lengths with no first length
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * -6: dynamic block code description: repeat more than specified lengths
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * -7: dynamic block code description: invalid literal/length code lengths
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * -8: dynamic block code description: invalid distance code lengths
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * -9: dynamic block code description: missing end-of-block code
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * -10: invalid literal/length or distance code in fixed or dynamic block
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * -11: distance is too far back in fixed or dynamic block
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * Format notes:
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - Three bits are read for each block to determine the kind of block and
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * whether or not it is the last block. Then the block is decoded and the
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * process repeated if it was not the last block.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * - The leftover bits in the last byte of the deflate data after the last
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * block (if it was a fixed or dynamic block) are undefined and have no
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync * expected values to check.
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsyncint puff(unsigned char *dest, /* pointer to destination pointer */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync unsigned long *destlen, /* amount of output space */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync const unsigned char *source, /* pointer to source data pointer */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync unsigned long *sourcelen) /* amount of input available */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync{
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync struct state s; /* input/output state */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int last, type; /* block information */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync int err; /* return value */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* initialize output state */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s.out = dest;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s.outlen = *destlen; /* ignored if dest is NIL */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s.outcnt = 0;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* initialize input state */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s.in = source;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s.inlen = *sourcelen;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s.incnt = 0;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s.bitbuf = 0;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync s.bitcnt = 0;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* return if bits() or decode() tries to read past available input */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (setjmp(s.env) != 0) /* if came back here via longjmp() */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync err = 2; /* then skip do-loop, return error */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync else {
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* process blocks until last block or error */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync do {
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync last = bits(&s, 1); /* one if last block */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync type = bits(&s, 2); /* block type 0..3 */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync err = type == 0 ?
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync stored(&s) :
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync (type == 1 ?
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync fixed(&s) :
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync (type == 2 ?
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync dynamic(&s) :
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync -1)); /* type == 3, invalid */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (err != 0)
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync break; /* return with error */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync } while (!last);
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync }
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync /* update the lengths and return */
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync if (err <= 0) {
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *destlen = s.outcnt;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync *sourcelen = s.incnt;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync }
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync return err;
1b33c96954667ba382fa595baf7b31290bfdd517vboxsync}