Lines Matching defs: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
84 #define MAXBITS 15 /* maximum bits in a code */
190 * Huffman code decoding tables. count[1..MAXBITS] is the number of symbols of
191 * each length, which for a canonical code are stepped through in order.
202 * Decode a code from the stream s using huffman table h. Return the symbol or
204 * an empty code, or if the code is incomplete and an invalid code is received,
212 * build the code value reversed from what is in the stream in order to
216 * - The first code for the shortest length is all zeros. Subsequent codes of
217 * the same length are simply integer increments of the previous code. When
218 * moving up a length, a zero bit is appended to the code. For a complete
219 * code, the last code of the longest length will be all ones.
227 int len; /* current number of bits in code */
228 int code; /* len bits being decoded */
229 int first; /* first code of length len */
231 int index; /* index of first code of length len in symbol table */
233 code = first = index = 0;
235 code |= bits(s, 1); /* get next bit */
237 if (code - count < first) /* if length len, return symbol */
238 return h->symbol[index + (code - first)];
242 code <<= 1;
248 * A faster version of decode() for real applications of this code. It's not
249 * as readable, but it makes puff() twice as fast. And it only makes the code
255 int len; /* current number of bits in code */
256 int code; /* len bits being decoded */
257 int first; /* first code of length len */
259 int index; /* index of first code of length len in symbol table */
266 code = first = index = 0;
271 code |= bitbuf & 1;
274 if (code - count < first) { /* if length len, return symbol */
277 return h->symbol[index + (code - first)];
282 code <<= 1;
296 * Given the list of code lengths length[0..n-1] representing a canonical
297 * Huffman code for n symbols, construct the tables required to decode those
300 * return value is zero for a complete code set, negative for an over-
301 * subscribed code set, and positive for an incomplete code set. The tables
310 * of the n symbols not in the code. So n - h->count[0] is the number of
321 * codes and any code with a single symbol which in deflate is coded as one
324 * - Within a given code length, the symbols are kept in ascending order for
325 * the code bits definition.
343 left = 1; /* one possible code of zero length */
368 * Decode literal/length and distance codes until an end-of-block code.
372 * - Compressed data that is after the block type if fixed or after the code
374 * pairs terminated by and end-of-block code. Literals are simply Huffman
379 * - Literals, lengths, and the end-of-block code are combined into a single
380 * code of up to 286 symbols. They are 256 literals (0..255), 29 length
397 * followed a distance code. There are up to 30 distance symbols. Again
459 if (symbol >= 29) return -10; /* invalid fixed code */
498 * which the size of the code descriptions in a dynamic block exceeds the
500 * spent on code descriptions. Instead the code lengths for literal/length
504 * - The literal/length code is complete, but has two symbols that are invalid
506 * simply as an incomplete code since those two symbols are in the "middle"
507 * of the code. They are eight bits long and the longest literal/length\
508 * code is nine bits. Therefore the code must be constructed with those
513 * length, this can be implemented as an incomplete code. Then the invalid
554 /* decode data until end-of-block code */
569 * from the number of bits in each code. Therefore the code descriptions
570 * are simply a list of code lengths for each symbol.
572 * - The code lengths are stored in order for the symbols, so lengths are
577 * as the code length. This does not mean a zero-length code, but rather
578 * that no code should be created for this symbol. There is no way in the
579 * deflate format to represent a zero-length code.
581 * - The maximum number of bits in a code is 15, so the possible lengths for
582 * any code are 1..15.
584 * - The fact that a length of zero is not permitted for a code has an
586 * code, then in fact that code could be represented with zero bits. However
587 * in deflate, that code has to be at least one bit. So for example, if
589 * represented by a single code of length one, in particular one 0 bit. This
590 * is an incomplete code, since if a 1 bit is received, it has no meaning,
594 * - It is also possible to have a single literal/length code, but that code
595 * must be the end-of-block code, since every dynamic block has one. This
601 * codes. This is represented by one distance code with zero bits.
605 * the list of code lengths, a 0 symbol means no code, a 1..15 symbol means
612 * - The symbols for 0..18 are Huffman coded, and so that code must be
614 * representing no code (0) or the code length for that symbol (1..7).
617 * the number of literal/length code lengths, the number of distance code
618 * lengths, and the number of code length code lengths (ok, you come up with
619 * a better name!) in the code descriptions. For the literal/length and
621 * code. The code length code lengths are received in a permuted order (see
622 * the order[] array below) to make a short code length code length list more
624 * to be seen in a dynamic code description, hence what may appear initially
627 * - Given the number of literal/length code lengths (nlen) and distance code
629 * code lengths. Therefore run-length coding can and often does cross the
632 * - So to summarize, the code description at the start of a dynamic block is
633 * three counts for the number of code lengths for the literal/length codes,
634 * the distance codes, and the code length codes. This is followed by the
635 * code length code lengths, three bits each. This is used to construct the
636 * code length code which is used to read the remainder of the lengths. Then
637 * the literal/length code lengths and distance lengths are read as a single
638 * set of lengths using the code length codes. Codes are constructed from
642 * - For reference, a "typical" size for the code description in a dynamic
650 short lengths[MAXCODES]; /* descriptor code lengths */
654 static const short order[19] = /* permutation of code length codes */
670 /* read code length code lengths (really), missing lengths are zero */
676 /* build huffman table for code lengths codes (use lencode temporarily) */
678 if (err != 0) return -4; /* require complete code set here */
680 /* read length/literal and distance code length tables */
707 /* check for end-of-block code -- there better be one! */
714 return -7; /* only allow incomplete codes if just one code */
719 code */
721 /* decode data until end-of-block code */
749 * -3: dynamic block code description: too many length or distance codes
750 * -4: dynamic block code description: code lengths codes incomplete
751 * -5: dynamic block code description: repeat lengths with no first length
752 * -6: dynamic block code description: repeat more than specified lengths
753 * -7: dynamic block code description: invalid literal/length code lengths
754 * -8: dynamic block code description: invalid distance code lengths
755 * -9: dynamic block code description: missing end-of-block code
756 * -10: invalid literal/length or distance code in fixed or dynamic block
931 fprintf(stderr, "puff() failed with return code %d\n", ret);
