libkern/zlib/trees.c

74 /* Bit length codes must not exceed MAX_BL_BITS bits */
80 /* repeat previous bit length 3-6 times (2 bits of repeat count) */
83 /* repeat a zero length 3-10 times  (3 bits of repeat count) */
86 /* repeat a zero length 11-138 times  (7 bits of repeat count) */
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 */
104 /* Number of bits used within bi_buf. (bi_buf might be implemented on
105  * more than 16 bits on some systems.)
126  * 5 bits.)
131  * 3 .. 258, the last 256 values correspond to the top 8 bits of
150     const intf *extra_bits;      /* extra bits for each code or NULL */
213  * Send a value on a given number of bits.
214  * IN assertion: length <= 16 and value fits in length bits.
222     int length; /* number of bits */
228     /* If not enough room in bi_buf, use (valid) bits from bi_buf and
229      * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
230      * unused bits in value.
270     int bits;     /* bit counter */
296      * in two different ways: code 284 + 5 bits or code 285, so we
320     for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
529     int bits;           /* bit length */
530     int xbits;          /* extra bits */
534     for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
543         bits = tree[tree[n].Dad].Len + 1;
544         if (bits > max_length) bits = max_length, overflow++;
545         tree[n].Len = (ush)bits;
550         s->bl_count[bits]++;
554         s->opt_len += (ulg)f * (bits + xbits);
564         bits = max_length-1;
565         while (s->bl_count[bits] == 0) bits--;
566         s->bl_count[bits]--;      /* move one leaf down the tree */
567         s->bl_count[bits+1] += 2; /* move one overflow item as its brother */
580     for (bits = max_length; bits != 0; bits--) {
581         n = s->bl_count[bits];
585             if ((unsigned) tree[m].Len != (unsigned) bits) {
586                 Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
587                 s->opt_len += ((long)bits - (long)tree[m].Len)
589                 tree[m].Len = (ush)bits;
611     int bits;                  /* bit index */
617     for (bits = 1; bits <= MAX_BITS; bits++) {
618         next_code[bits] = code = (code + bl_count[bits-1]) << 1;
630         /* Now reverse the bits */
682         /* node is 0 or 1 so it does not have extra bits */
842      * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
910  * This takes 10 bits, of which 7 may remain in the bit buffer.
911  * The current inflate code requires 9 bits of lookahead. If the
913  * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode
928     /* Of the 10 bits for the empty block, we have already sent
929      * (10 - bi_valid) bits. The lookahead for the last real code (before
1031      * and uLong implemented on 32 bits.
1108     int extra;          /* number of extra bits to send */
1123                 send_bits(s, lc, extra);       /* send the extra length bits */
1133                 send_bits(s, dist, extra);   /* send the extra distance bits */
1169  * Reverse the first len bits of a code, using straightforward code (a faster
1186  * Flush the bit buffer, keeping at most 7 bits in it.