| 10625 | * not null. |
| 10626 | */ |
| 10627 | function gen_bitlen(s, desc) |
| 10628 | // deflate_state *s; |
| 10629 | // tree_desc *desc; /* the tree descriptor */ |
| 10630 | { |
| 10631 | var tree = desc.dyn_tree; |
| 10632 | var max_code = desc.max_code; |
| 10633 | var stree = desc.stat_desc.static_tree; |
| 10634 | var has_stree = desc.stat_desc.has_stree; |
| 10635 | var extra = desc.stat_desc.extra_bits; |
| 10636 | var base = desc.stat_desc.extra_base; |
| 10637 | var max_length = desc.stat_desc.max_length; |
| 10638 | var h; /* heap index */ |
| 10639 | var n, m; /* iterate over the tree elements */ |
| 10640 | var bits; /* bit length */ |
| 10641 | var xbits; /* extra bits */ |
| 10642 | var f; /* frequency */ |
| 10643 | var overflow = 0; /* number of elements with bit length too large */ |
| 10644 | |
| 10645 | for (bits = 0; bits <= MAX_BITS; bits++) { |
| 10646 | s.bl_count[bits] = 0; |
| 10647 | } |
| 10648 | |
| 10649 | /* In a first pass, compute the optimal bit lengths (which may |
| 10650 | * overflow in the case of the bit length tree). |
| 10651 | */ |
| 10652 | tree[s.heap[s.heap_max] * 2 + 1]/*.Len*/ = 0; /* root of the heap */ |
| 10653 | |
| 10654 | for (h = s.heap_max + 1; h < HEAP_SIZE; h++) { |
| 10655 | n = s.heap[h]; |
| 10656 | bits = tree[tree[n * 2 + 1]/*.Dad*/ * 2 + 1]/*.Len*/ + 1; |
| 10657 | if (bits > max_length) { |
| 10658 | bits = max_length; |
| 10659 | overflow++; |
| 10660 | } |
| 10661 | tree[n * 2 + 1]/*.Len*/ = bits; |
| 10662 | /* We overwrite tree[n].Dad which is no longer needed */ |
| 10663 | |
| 10664 | if (n > max_code) { continue; } /* not a leaf node */ |
| 10665 | |
| 10666 | s.bl_count[bits]++; |
| 10667 | xbits = 0; |
| 10668 | if (n >= base) { |
| 10669 | xbits = extra[n - base]; |
| 10670 | } |
| 10671 | f = tree[n * 2]/*.Freq*/; |
| 10672 | s.opt_len += f * (bits + xbits); |
| 10673 | if (has_stree) { |
| 10674 | s.static_len += f * (stree[n * 2 + 1]/*.Len*/ + xbits); |
| 10675 | } |
| 10676 | } |
| 10677 | if (overflow === 0) { return; } |
| 10678 | |
| 10679 | // Trace((stderr,"\nbit length overflow\n")); |
| 10680 | /* This happens for example on obj2 and pic of the Calgary corpus */ |
| 10681 | |
| 10682 | /* Find the first bit length which could increase: */ |
| 10683 | do { |
| 10684 | bits = max_length - 1; |