lib/zlib_deflate/deftree.c

50 /* Bit length codes must not exceed MAX_BL_BITS bits */
56 /* repeat previous bit length 3-6 times (2 bits of repeat count) */
59 /* repeat a zero length 3-10 times  (3 bits of repeat count) */
62 /* repeat a zero length 11-138 times  (7 bits of repeat count) */
64 static const int extra_lbits[LENGTH_CODES] /* extra bits for each length code */
70 static const int extra_blbits[BL_CODES]/* extra bits for each bit length code */
75 /* The lengths of the bit length codes are sent in order of decreasing
76  * probability, to avoid transmitting the lengths for unused bit length codes.
102 /* length code for each normalized match length (0 == MIN_MATCH) */
105 /* First normalized length for each code (0 = MIN_MATCH) */
115     int     max_length;          /* max bit length for the codes */
176     int length;   /* length value */
180     /* number of codes at each bit length for an optimal tree */
184     /* Initialize the mapping length (0..255) -> length code (0..28) */
185     length = 0;
187         base_length[code] = length;
189             length_code[length++] = (uch)code;
192     Assert (length == 256, "tr_static_init: length != 256");
193     /* Note that the length 255 (match length 258) can be represented
197     length_code[length-1] = (uch)code;
305  * the subtrees have equal frequency. This minimizes the worst case length.
344  * Compute the optimal bit lengths for a tree and update the total bit length
348  * OUT assertions: the field len is set to the optimal bit length, the
349  *     array bl_count contains the frequencies for each bit length.
350  *     The length opt_len is updated; static_len is also updated if stree is
366     int bits;           /* bit length */
369     int overflow = 0;   /* number of elements with bit length too large */
374      * overflow in the case of the bit length tree).
396     Trace((stderr,"\nbit length overflow\n"));
399     /* Find the first bit length which could increase: */
436  * IN assertion: the array bl_count contains the bit length statistics for
439  *     zero code length.
444 	ush *bl_count             /* number of codes at each bit length */
447     ush next_code[MAX_BITS+1]; /* next code value for each bit length */
478  * Update the total bit length for the current block.
480  * OUT assertions: the fields len and code are set to the optimal bit length
481  *     and corresponding code. The length opt_len is updated; static_len is
570  * in the bit length tree.
579     int prevlen = -1;          /* last emitted length */
580     int curlen;                /* length of current code */
581     int nextlen = tree[0].Len; /* length of next code */
625     int prevlen = -1;          /* last emitted length */
626     int curlen;                /* length of current code */
627     int nextlen = tree[0].Len; /* length of next code */
668  * bl_order of the last bit length code to send.
674     int max_blindex;  /* index of last bit length code of non zero freq */
676     /* Determine the bit length frequencies for literal and distance trees */
680     /* Build the bit length tree: */
682     /* opt_len now includes the length of the tree representations, except
686     /* Determine the number of bit length codes to send. The pkzip format
687      * requires that at least 4 bit length codes be sent. (appnote.txt says
693     /* Update opt_len to include the bit length tree and counts */
703  * lengths of the bit length codes, the literal tree and the distance tree.
741 	ulg stored_len,   /* length of input block */
752 /* Send just the `stored block' type code without any length bytes or data.
785      * the EOB of the previous block) was thus at least one plus the length
800  * returns the total compressed length for the file so far.
805 	ulg stored_len,   /* length of input block */
810     int max_blindex = 0;  /* index of last bit length code of non zero freq */
830 	/* Build the bit length tree for the above two trees, and get the index
831 	 * in bl_order of the last bit length code to send.
835 	/* Determine the best encoding. Compute first the block length in bytes*/
918 	unsigned lc     /* match length-MIN_MATCH or unmatched char (if dist==0) */
928         /* Here, lc is the match length - MIN_MATCH */
940         /* Compute an upper bound for the compressed length */
971     int lc;             /* match length or unmatched char (if dist == 0) */
983             /* Here, lc is the match length - MIN_MATCH */
985             send_code(s, code+LITERALS+1, ltree); /* send the length code */
989                 send_bits(s, lc, extra);       /* send the extra length bits */
1032  * Copy a stored block, storing first the length and its
1038 	unsigned len,     /* its length */