| 22607 | * not null. |
| 22608 | */ |
| 22609 | function gen_bitlen(s, desc) |
| 22610 | // deflate_state *s; |
| 22611 | // tree_desc *desc; /* the tree descriptor */ |
| 22612 | { |
| 22613 | var tree = desc.dyn_tree; |
| 22614 | var max_code = desc.max_code; |
| 22615 | var stree = desc.stat_desc.static_tree; |
| 22616 | var has_stree = desc.stat_desc.has_stree; |
| 22617 | var extra = desc.stat_desc.extra_bits; |
| 22618 | var base = desc.stat_desc.extra_base; |
| 22619 | var max_length = desc.stat_desc.max_length; |
| 22620 | var h; /* heap index */ |
| 22621 | var n, m; /* iterate over the tree elements */ |
| 22622 | var bits; /* bit length */ |
| 22623 | var xbits; /* extra bits */ |
| 22624 | var f; /* frequency */ |
| 22625 | var overflow = 0; /* number of elements with bit length too large */ |
| 22626 | |
| 22627 | for (bits = 0; bits <= MAX_BITS; bits++) { |
| 22628 | s.bl_count[bits] = 0; |
| 22629 | } |
| 22630 | |
| 22631 | /* In a first pass, compute the optimal bit lengths (which may |
| 22632 | * overflow in the case of the bit length tree). |
| 22633 | */ |
| 22634 | tree[s.heap[s.heap_max] * 2 + 1]/*.Len*/ = 0; /* root of the heap */ |
| 22635 | |
| 22636 | for (h = s.heap_max + 1; h < HEAP_SIZE; h++) { |
| 22637 | n = s.heap[h]; |
| 22638 | bits = tree[tree[n * 2 + 1]/*.Dad*/ * 2 + 1]/*.Len*/ + 1; |
| 22639 | if (bits > max_length) { |
| 22640 | bits = max_length; |
| 22641 | overflow++; |
| 22642 | } |
| 22643 | tree[n * 2 + 1]/*.Len*/ = bits; |
| 22644 | /* We overwrite tree[n].Dad which is no longer needed */ |
| 22645 | |
| 22646 | if (n > max_code) { continue; } /* not a leaf node */ |
| 22647 | |
| 22648 | s.bl_count[bits]++; |
| 22649 | xbits = 0; |
| 22650 | if (n >= base) { |
| 22651 | xbits = extra[n - base]; |
| 22652 | } |
| 22653 | f = tree[n * 2]/*.Freq*/; |
| 22654 | s.opt_len += f * (bits + xbits); |
| 22655 | if (has_stree) { |
| 22656 | s.static_len += f * (stree[n * 2 + 1]/*.Len*/ + xbits); |
| 22657 | } |
| 22658 | } |
| 22659 | if (overflow === 0) { return; } |
| 22660 | |
| 22661 | // Trace((stderr,"\nbit length overflow\n")); |
| 22662 | /* This happens for example on obj2 and pic of the Calgary corpus */ |
| 22663 | |
| 22664 | /* Find the first bit length which could increase: */ |
| 22665 | do { |
| 22666 | bits = max_length - 1; |