Lines Matching full: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
76 #define MAXBITS 15 /* maximum bits in a code */
182 * Huffman code decoding tables. count[1..MAXBITS] is the number of symbols of
183 * each length, which for a canonical code are stepped through in order.
194 * Decode a code from the stream s using huffman table h. Return the symbol or
196 * an empty code, or if the code is incomplete and an invalid code is received,
204 * build the code value reversed from what is in the stream in order to
208 * - The first code for the shortest length is all zeros. Subsequent codes of
209 * the same length are simply integer increments of the previous code. When
210 * moving up a length, a zero bit is appended to the code. For a complete
211 * code, the last code of the longest length will be all ones.
219 int len; /* current number of bits in code */
220 int code; /* len bits being decoded */
221 int first; /* first code of length len */
223 int index; /* index of first code of length len in symbol table */
225 code = first = index = 0;
227 code |= bits(s, 1); /* get next bit */
229 if (code < first + count) /* if length len, return symbol */
230 return h->symbol[index + (code - first)];
234 code <<= 1;
240 * A faster version of decode() for real applications of this code. It's not
241 * as readable, but it makes puff() twice as fast. And it only makes the code
247 int len; /* current number of bits in code */
248 int code; /* len bits being decoded */
249 int first; /* first code of length len */
251 int index; /* index of first code of length len in symbol table */
258 code = first = index = 0;
263 code |= bitbuf & 1;
266 if (code < first + count) { /* if length len, return symbol */
269 return h->symbol[index + (code - first)];
274 code <<= 1;
288 * Given the list of code lengths length[0..n-1] representing a canonical
289 * Huffman code for n symbols, construct the tables required to decode those
292 * return value is zero for a complete code set, negative for an over-
293 * subscribed code set, and positive for an incomplete code set. The tables
302 * of the n symbols not in the code. So n - h->count[0] is the number of
313 * codes and any code with a single symbol which in deflate is coded as one
316 * - Within a given code length, the symbols are kept in ascending order for
317 * the code bits definition.
335 left = 1; /* one possible code of zero length */
360 * Decode literal/length and distance codes until an end-of-block code.
364 * - Compressed data that is after the block type if fixed or after the code
366 * pairs terminated by and end-of-block code. Literals are simply Huffman
371 * - Literals, lengths, and the end-of-block code are combined into a single
372 * code of up to 286 symbols. They are 256 literals (0..255), 29 length
389 * followed a distance code. There are up to 30 distance symbols. Again
451 if (symbol >= 29) return -9; /* invalid fixed code */
484 * which the size of the code descriptions in a dynamic block exceeds the
486 * spent on code descriptions. Instead the code lengths for literal/length
490 * - The literal/length code is complete, but has two symbols that are invalid
492 * simply as an incomplete code since those two symbols are in the "middle"
493 * of the code. They are eight bits long and the longest literal/length\
494 * code is nine bits. Therefore the code must be constructed with those
499 * length, this can be implemented as an incomplete code. Then the invalid
535 /* decode data until end-of-block code */
550 * from the number of bits in each code. Therefore the code descriptions
551 * are simply a list of code lengths for each symbol.
553 * - The code lengths are stored in order for the symbols, so lengths are
558 * as the code length. This does not mean a zero-length code, but rather
559 * that no code should be created for this symbol. There is no way in the
560 * deflate format to represent a zero-length code.
562 * - The maximum number of bits in a code is 15, so the possible lengths for
563 * any code are 1..15.
565 * - The fact that a length of zero is not permitted for a code has an
567 * code, then in fact that code could be represented with zero bits. However
568 * in deflate, that code has to be at least one bit. So for example, if
570 * represented by a single code of length one, in particular one 0 bit. This
571 * is an incomplete code, since if a 1 bit is received, it has no meaning,
575 * - It is also possible to have a single literal/length code, but that code
576 * must be the end-of-block code, since every dynamic block has one. This
582 * codes. This is represented by one distance code with zero bits.
586 * the list of code lengths, a 0 symbol means no code, a 1..15 symbol means
593 * - The symbols for 0..18 are Huffman coded, and so that code must be
595 * representing no code (0) or the code length for that symbol (1..7).
598 * the number of literal/length code lengths, the number of distance code
599 * lengths, and the number of code length code lengths (ok, you come up with
600 * a better name!) in the code descriptions. For the literal/length and
602 * code. The code length code lengths are received in a permuted order (see
603 * the order[] array below) to make a short code length code length list more
605 * to be seen in a dynamic code description, hence what may appear initially
608 * - Given the number of literal/length code lengths (nlen) and distance code
610 * code lengths. Therefore run-length coding can and often does cross the
613 * - So to summarize, the code description at the start of a dynamic block is
614 * three counts for the number of code lengths for the literal/length codes,
615 * the distance codes, and the code length codes. This is followed by the
616 * code length code lengths, three bits each. This is used to construct the
617 * code length code which is used to read the remainder of the lengths. Then
618 * the literal/length code lengths and distance lengths are read as a single
619 * set of lengths using the code length codes. Codes are constructed from
623 * - For reference, a "typical" size for the code description in a dynamic
631 short lengths[MAXCODES]; /* descriptor code lengths */
634 struct huffman lencode = {lencnt, lensym}; /* length code */
635 struct huffman distcode = {distcnt, distsym}; /* distance code */
636 static const short order[19] = /* permutation of code length codes */
646 /* read code length code lengths (really), missing lengths are zero */
652 /* build huffman table for code lengths codes (use lencode temporarily) */
654 if (err != 0) return -4; /* require complete code set here */
656 /* read length/literal and distance code length tables */
686 return -7; /* only allow incomplete codes if just one code */
691 return -8; /* only allow incomplete codes if just one code */
693 /* decode data until end-of-block code */
721 * -3: dynamic block code description: too many length or distance codes
722 * -4: dynamic block code description: code lengths codes incomplete
723 * -5: dynamic block code description: repeat lengths with no first length
724 * -6: dynamic block code description: repeat more than specified lengths
725 * -7: dynamic block code description: invalid literal/length code lengths
726 * -8: dynamic block code description: invalid distance code lengths
727 * -9: invalid literal/length or distance code in fixed or dynamic block
828 printf("puff() failed with return code %d\n", ret);
