Lines Matching refs:code
9 * side benefit, this code might actually be useful when small code is more
18 * is less than 2K bytes. This code is compatible with 16-bit int's and
20 * assumed to be 16 bits, for arrays in order to to conserve memory. The code
25 * code is meant to supplement RFC 1951, which formally describes the deflate
56 * 1.4 31 Mar 2002 - Simplify construct() code set check
61 * 1.7 3 Mar 2003 - Added test code for distribution
67 * - Add option in TEST code for puff to write the data
68 * - Add option in TEST code to skip input bytes
69 * - Allow TEST code to read from piped stdin
75 * - Break out test code to separate file
77 * - Allow incomplete code only if single code length is 1
78 * - Add full code coverage test to Makefile
79 * 2.3 21 Jan 2013 - Check for invalid code length codes in dynamic blocks
91 #define MAXBITS 15 /* maximum bits in a code */
200 * Huffman code decoding tables. count[1..MAXBITS] is the number of symbols of
201 * each length, which for a canonical code are stepped through in order.
212 * Decode a code from the stream s using huffman table h. Return the symbol or
214 * an empty code, or if the code is incomplete and an invalid code is received,
222 * build the code value reversed from what is in the stream in order to
226 * - The first code for the shortest length is all zeros. Subsequent codes of
227 * the same length are simply integer increments of the previous code. When
228 * moving up a length, a zero bit is appended to the code. For a complete
229 * code, the last code of the longest length will be all ones.
237 int len; /* current number of bits in code */
238 int code; /* len bits being decoded */
239 int first; /* first code of length len */
241 int index; /* index of first code of length len in symbol table */
243 code = first = index = 0;
245 code |= bits(s, 1); /* get next bit */
247 if (code - count < first) /* if length len, return symbol */
248 return h->symbol[index + (code - first)];
252 code <<= 1;
258 * A faster version of decode() for real applications of this code. It's not
259 * as readable, but it makes puff() twice as fast. And it only makes the code
265 int len; /* current number of bits in code */
266 int code; /* len bits being decoded */
267 int first; /* first code of length len */
269 int index; /* index of first code of length len in symbol table */
276 code = first = index = 0;
281 code |= bitbuf & 1;
284 if (code - count < first) { /* if length len, return symbol */
287 return h->symbol[index + (code - first)];
292 code <<= 1;
309 * Given the list of code lengths length[0..n-1] representing a canonical
310 * Huffman code for n symbols, construct the tables required to decode those
313 * return value is zero for a complete code set, negative for an over-
314 * subscribed code set, and positive for an incomplete code set. The tables
323 * of the n symbols not in the code. So n - h->count[0] is the number of
334 * codes and any code with a single symbol which in deflate is coded as one
337 * - Within a given code length, the symbols are kept in ascending order for
338 * the code bits definition.
356 left = 1; /* one possible code of zero length */
382 * Decode literal/length and distance codes until an end-of-block code.
386 * - Compressed data that is after the block type if fixed or after the code
388 * pairs terminated by and end-of-block code. Literals are simply Huffman
393 * - Literals, lengths, and the end-of-block code are combined into a single
394 * code of up to 286 symbols. They are 256 literals (0..255), 29 length
411 * followed a distance code. There are up to 30 distance symbols. Again
476 return -10; /* invalid fixed code */
518 * which the size of the code descriptions in a dynamic block exceeds the
520 * spent on code descriptions. Instead the code lengths for literal/length
524 * - The literal/length code is complete, but has two symbols that are invalid
526 * simply as an incomplete code since those two symbols are in the "middle"
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
533 * length, this can be implemented as an incomplete code. Then the invalid
574 /* decode data until end-of-block code */
589 * from the number of bits in each code. Therefore the code descriptions
590 * are simply a list of code lengths for each symbol.
592 * - The code lengths are stored in order for the symbols, so lengths are
597 * as the code length. This does not mean a zero-length code, but rather
598 * that no code should be created for this symbol. There is no way in the
599 * deflate format to represent a zero-length code.
601 * - The maximum number of bits in a code is 15, so the possible lengths for
602 * any code are 1..15.
604 * - The fact that a length of zero is not permitted for a code has an
606 * code, then in fact that code could be represented with zero bits. However
607 * in deflate, that code has to be at least one bit. So for example, if
609 * represented by a single code of length one, in particular one 0 bit. This
610 * is an incomplete code, since if a 1 bit is received, it has no meaning,
614 * - It is also possible to have a single literal/length code, but that code
615 * must be the end-of-block code, since every dynamic block has one. This
621 * codes. This is represented by one distance code with zero bits.
625 * the list of code lengths, a 0 symbol means no code, a 1..15 symbol means
632 * - The symbols for 0..18 are Huffman coded, and so that code must be
634 * representing no code (0) or the code length for that symbol (1..7).
637 * the number of literal/length code lengths, the number of distance code
638 * lengths, and the number of code length code lengths (ok, you come up with
639 * a better name!) in the code descriptions. For the literal/length and
641 * code. The code length code lengths are received in a permuted order (see
642 * the order[] array below) to make a short code length code length list more
644 * to be seen in a dynamic code description, hence what may appear initially
647 * - Given the number of literal/length code lengths (nlen) and distance code
649 * code lengths. Therefore run-length coding can and often does cross the
652 * - So to summarize, the code description at the start of a dynamic block is
653 * three counts for the number of code lengths for the literal/length codes,
654 * the distance codes, and the code length codes. This is followed by the
655 * code length code lengths, three bits each. This is used to construct the
656 * code length code which is used to read the remainder of the lengths. Then
657 * the literal/length code lengths and distance lengths are read as a single
658 * set of lengths using the code length codes. Codes are constructed from
662 * - For reference, a "typical" size for the code description in a dynamic
670 short lengths[MAXCODES]; /* descriptor code lengths */
674 static const short order[19] = /* permutation of code length codes */
690 /* read code length code lengths (really), missing lengths are zero */
696 /* build huffman table for code lengths codes (use lencode temporarily) */
698 if (err != 0) /* require complete code set here */
701 /* read length/literal and distance code length tables */
731 /* check for end-of-block code -- there better be one! */
738 return -7; /* incomplete code ok only for single length 1 code */
743 return -8; /* incomplete code ok only for single length 1 code */
745 /* decode data until end-of-block code */
773 * -3: dynamic block code description: too many length or distance codes
774 * -4: dynamic block code description: code lengths codes incomplete
775 * -5: dynamic block code description: repeat lengths with no first length
776 * -6: dynamic block code description: repeat more than specified lengths
777 * -7: dynamic block code description: invalid literal/length code lengths
778 * -8: dynamic block code description: invalid distance code lengths
779 * -9: dynamic block code description: missing end-of-block code
780 * -10: invalid literal/length or distance code in fixed or dynamic block