contrib/puff/puff.c

19  * assumes that long's are at least 32 bits.  puff.c uses the short data type,
20  * assumed to be 16 bits, for arrays in order to to conserve memory.  The code
48  *                        are 16 bits
91 #define MAXBITS 15              /* maximum bits in a code */
109     int bitcnt;                 /* number of bits in bit buffer */
111     /* input limit error return state for bits() and decode() */
116  * Return need bits from the input stream.  This always leaves less than
117  * eight bits in the buffer.  bits() works properly for need == 0.
122  *   significant bit.  Therefore bits are dropped from the bottom of the bit
126 local int bits(struct state *s, int need)
128     long val;           /* bit accumulator (can use up to 20 bits) */
130     /* load at least need bits into val */
135         val |= (long)(s->in[s->incnt++]) << s->bitcnt;  /* load eight bits */
139     /* drop need bits and update buffer, always zero to seven bits left */
143     /* return need bits, zeroing the bits above that */
154  *   bits in the byte that has the last bit of the type, as many as seven, are
155  *   discarded.  The value of the discarded bits are not defined and should not
168     /* discard leftover bits from current byte (assumes s->bitcnt < 8) */
215  * then -10 is returned after reading MAXBITS bits.
221  *   bits are pulled from the compressed data one at a time and used to
237     int len;            /* current number of bits in code */
238     int code;           /* len bits being decoded */
245         code |= bits(s, 1);             /* get next bit */
265     int len;            /* current number of bits in code */
266     int code;           /* len bits being decoded */
270     int bitbuf;         /* bits from stream */
271     int left;           /* bits left in next or left to process */
318  * enough bits will resolve to a symbol.  If the return value is positive, then
335  *   bit instead of zero bits.  See the format notes for fixed() and dynamic().
338  *   the code bits definition.
400  *   some number of extra bits that are added as an integer to the base length
401  *   of the length symbol.  The number of extra bits is determined by the base
403  *   lengths and lext[] for the corresponding number of extra bits.
410  * - If a length is decoded, including its extra bits if any, then it is
412  *   there are many more possible distances (1..32768), so extra bits are added
414  *   own symbol, but the rest require extra bits.  The base distances and
415  *   corresponding number of extra bits are below in the static arrays dist[]
446     static const short lext[29] = { /* Extra bits for length codes 257..285 */
453     static const short dext[30] = { /* Extra bits for distance codes 0..29 */
477             len = lens[symbol] + bits(s, lext[symbol]);
483             dist = dists[symbol] + bits(s, dext[symbol]);
519  *   benefit of custom codes for that block.  For fixed codes, no bits are
527  *   of the code.  They are eight bits long and the longest literal/length\
528  *   code is nine bits.  Therefore the code must be constructed with those
588  *   the actual bits of the codes are generated in an unambiguous way simply
589  *   from the number of bits in each code.  Therefore the code descriptions
601  * - The maximum number of bits in a code is 15, so the possible lengths for
606  *   code, then in fact that code could be represented with zero bits.  However
617  *   block is fewer bits), but it is allowed by the format.  So incomplete
621  *   codes.  This is represented by one distance code with zero bits.
627  *   Each of 16, 17, and 18 are follwed by extra bits to define the length of
655  *   code length code lengths, three bits each.  This is used to construct the
684     nlen = bits(s, 5) + 257;
685     ndist = bits(s, 5) + 1;
686     ncode = bits(s, 4) + 4;
692         lengths[order[index]] = bits(s, 3);
718                 symbol = 3 + bits(s, 2);
721                 symbol = 3 + bits(s, 3);
723                 symbol = 11 + bits(s, 7);
785  * - Three bits are read for each block to determine the kind of block and
789  * - The leftover bits in the last byte of the deflate data after the last
814     /* return if bits() or decode() tries to read past available input */
820             last = bits(&s, 1);         /* one if last block */
821             type = bits(&s, 2);         /* block type 0..3 */