Lines Matching defs:length
77 * - Allow incomplete code only if single code length is 1
79 * 2.3 21 Jan 2013 - Check for invalid code length codes in dynamic blocks
92 #define MAXLCODES 286 /* maximum number of literal/length codes */
95 #define FIXLCODES 288 /* number of fixed literal/length codes */
152 * - After the two-bit stored block type (00), the stored block length and
158 * - The second inverted copy of the stored block length does not have to be
161 * - A stored block can have zero length. This is sometimes used to byte-align
166 unsigned len; /* length of stored block */
172 /* get length and check against its one's complement */
201 * each length, which for a canonical code are stepped through in order.
207 short *count; /* number of symbols of each length */
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.
239 int first; /* first code of length len */
240 int count; /* number of codes of length len */
241 int index; /* index of first code of length len in symbol table */
247 if (code - count < first) /* if length len, return symbol */
249 index += count; /* else update for next length */
267 int first; /* first code of length len */
268 int count; /* number of codes of length len */
269 int index; /* index of first code of length len in symbol table */
284 if (code - count < first) { /* if length len, return symbol */
289 index += count; /* else update for next length */
309 * Given the list of code lengths length[0..n-1] representing a canonical
311 * codes. Those tables are the number of codes of each length, and the symbols
312 * sorted by length, retaining their original order within each length. The
327 * Assumption: for all i in 0..n-1, 0 <= length[i] <= MAXBITS
328 * This is assured by the construction of the length arrays in dynamic() and
337 * - Within a given code length, the symbols are kept in ascending order for
340 local int construct(struct huffman *h, const short *length, int n)
342 int symbol; /* current symbol when stepping through length[] */
343 int len; /* current length when stepping through h->count[] */
344 int left; /* number of possible codes left of current length */
345 short offs[MAXBITS+1]; /* offsets in symbol table for each length */
347 /* count number of codes of each length */
351 (h->count[length[symbol]])++; /* assumes lengths are within bounds */
356 left = 1; /* one possible code of zero length */
364 /* generate offsets into symbol table for each length for sorting */
370 * put symbols in table sorted by length, by symbol order within each
371 * length
374 if (length[symbol] != 0)
375 h->symbol[offs[length[symbol]]++] = symbol;
382 * Decode literal/length and distance codes until an end-of-block code.
387 * description if dynamic is a combination of literals and length/distance
389 * coded bytes. A length/distance pair is a coded length followed by a
394 * code of up to 286 symbols. They are 256 literals (0..255), 29 length
399 * by just a length symbol. Lengths 11..257 are represented as a symbol and
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
402 * length symbol. These are in the static arrays below, lens[] for the base
405 * - The reason that 258 gets its own symbol is that the longest length is used
410 * - If a length is decoded, including its extra bits if any, then it is
418 * - Literal bytes are simply written to the output. A length/distance pair is
420 * copy is from distance bytes back in the output stream, copying for length
426 * - Overlapped copies, where the length is greater than the distance, are
427 * allowed and common. For example, a distance of one and a length of 258
428 * simply copies the last byte 258 times. A distance of four and a length of
430 * ignoring whether the length is greater than the distance or not implements
441 int len; /* length for copy */
443 static const short lens[29] = { /* Size base for length codes 257..285 */
446 static const short lext[29] = { /* Extra bits for length codes 257..285 */
458 /* decode literals and length/distance pairs */
472 else if (symbol > 256) { /* length */
473 /* get and compute length */
489 /* copy length bytes from distance bytes back */
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
527 * of the code. They are eight bits long and the longest literal/length\
533 * length, this can be implemented as an incomplete code. Then the invalid
554 /* literal/length table */
583 * - A dynamic block starts with a description of the literal/length and
593 * provided for each of the literal/length symbols, and for each of the
597 * code length. This does not mean a zero-length code, but rather that no
599 * format to represent a zero-length code.
604 * - The fact that a length of zero is not permitted for a code has an
609 * represented by a single code of length one, in particular one 0 bit. This
614 * - It is also possible to have a single literal/length code, but that code
618 * literal/length codes of one symbol should also be permitted.
623 * - The list of up to 286 length/literal lengths and up to 30 distance lengths
624 * are themselves compressed using Huffman codes and run-length encoding. In
626 * that length, and the symbols 16, 17, and 18 are run-length instructions.
627 * Each of 16, 17, and 18 are followed by extra bits to define the length of
628 * the run. 16 copies the last length 3 to 6 times. 17 represents 3 to 10
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
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
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
673 struct huffman lencode, distcode; /* length and distance codes */
674 static const short order[19] = /* permutation of code length codes */
690 /* read code length code lengths (really), missing lengths are zero */
701 /* read length/literal and distance code length tables */
705 int len; /* last length to repeat */
710 if (symbol < 16) /* length in 0..15 */
714 if (symbol == 16) { /* repeat last length 3..6 times */
716 return -5; /* no last length! */
717 len = lengths[index - 1]; /* last length */
735 /* build huffman table for literal/length codes */
738 return -7; /* incomplete code ok only for single length 1 code */
743 return -8; /* incomplete code ok only for single length 1 code */
772 * -2: stored block length did not match one's complement
773 * -3: dynamic block code description: too many length or distance codes
775 * -5: dynamic block code description: repeat lengths with no first length
777 * -7: dynamic block code description: invalid literal/length code lengths
780 * -10: invalid literal/length or distance code in fixed or dynamic block