libkern/zlib/trees.c

39  *      Each code tree is stored in a compressed form which is itself
40  * a Huffman encoding of the lengths of all the code strings (in
41  * ascending order by source values).  The actual code strings are
77 /* end of block literal code */
88 local const int extra_lbits[LENGTH_CODES] /* extra bits for each length code */
91 local const int extra_dbits[D_CODES] /* extra bits for each distance code */
94 local const int extra_blbits[BL_CODES]/* extra bits for each bit length code */
136 /* length code for each normalized match length (0 == MIN_MATCH) */
139 /* First normalized length for each code (0 = MIN_MATCH) */
142 /* First normalized distance for each code (0 = distance of 1) */
150     const intf *extra_bits;      /* extra bits for each code or NULL */
195    /* Send a code of the given tree. c and tree must not have side effects */
272     int code;     /* code value */
286     /* Initialize the mapping length (0..255) -> length code (0..28) */
288     for (code = 0; code < LENGTH_CODES-1; code++) {
289         base_length[code] = length;
290         for (n = 0; n < (1<<extra_lbits[code]); n++) {
291             _length_code[length++] = (uch)code;
296      * in two different ways: code 284 + 5 bits or code 285, so we
299     _length_code[length-1] = (uch)code;
301     /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
303     for (code = 0 ; code < 16; code++) {
304         base_dist[code] = dist;
305         for (n = 0; n < (1<<extra_dbits[code]); n++) {
306             _dist_code[dist++] = (uch)code;
311     for ( ; code < D_CODES; code++) {
312         base_dist[code] = dist << 7;
313         for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
314             _dist_code[256 + dist++] = (uch)code;
327      * tree construction to get a canonical Huffman tree (longest code
586                 Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
601  * OUT assertion: the field code is set for all tree elements of non
602  *     zero code length.
606     int max_code;              /* largest code with non zero frequency */
609     ush next_code[MAX_BITS+1]; /* next code value for each bit length */
610     ush code = 0;              /* running code value */
612     int n;                     /* code index */
614     /* The distribution counts are first used to generate the code values
618         next_code[bits] = code = (code + bl_count[bits-1]) << 1;
620     /* Check that the bit counts in bl_count are consistent. The last code
623     Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
639  * Construct one Huffman tree and assigns the code bit strings and lengths.
642  * OUT assertions: the fields len and code are set to the optimal bit length
643  *     and corresponding code. The length opt_len is updated; static_len is
654     int max_code = -1; /* largest code with non zero frequency */
672     /* The pkzip format requires that at least one distance code exists,
674      * possible code. So to avoid special checks later on we force at least
737     int max_code;    /* and its largest code of non zero frequency */
741     int curlen;                /* length of current code */
742     int nextlen = tree[0].Len; /* length of next code */
743     int count = 0;             /* repeat count of the current code */
782     int max_code;       /* and its largest code of non zero frequency */
786     int curlen;                /* length of current code */
787     int nextlen = tree[0].Len; /* length of next code */
788     int count = 0;             /* repeat count of the current code */
828  * bl_order of the last bit length code to send.
833     int max_blindex;  /* index of last bit length code of non zero freq */
879         Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
911  * The current inflate code requires 9 bits of lookahead. If the
912  * last two codes for the previous block (real code plus EOB) were coded
914  * the last real code. In this case we send two empty static blocks instead
916  * To simplify the code, we assume the worst case of last real code encoded
929      * (10 - bi_valid) bits. The lookahead for the last real code (before
955     int max_blindex = 0;  /* index of last bit length code of non zero freq */
977          * in bl_order of the last bit length code to send.
1107     unsigned code;      /* the code to send */
1118             code = _length_code[lc];
1119             send_code(s, code+LITERALS+1, ltree); /* send the length code */
1120             extra = extra_lbits[code];
1122                 lc -= base_length[code];
1126             code = d_code(dist);
1127             Assert (code < D_CODES, "bad d_code");
1129             send_code(s, code, dtree);       /* send the distance code */
1130             extra = extra_dbits[code];
1132                 dist -= base_dist[code];
1169  * Reverse the first len bits of a code, using straightforward code (a faster
1173 local unsigned bi_reverse(code, len)
1174     unsigned code; /* the value to invert */
1179         res |= code & 1;
1180         code >>= 1, res <<= 1;