=========================================================================== * Compute the optimal bit lengths for a tree and update the total bit length * for the current block. * IN assertion: the fields freq and dad are set, heap[heap_max] and * above are the tree nodes sorted by increasing frequency. * OUT assertions: the field len is set to the optimal bit length, the * array bl_c
| 538 | * not null. |
| 539 | */ |
| 540 | local void gen_bitlen(deflate_state *s, tree_desc *desc) { |
| 541 | ct_data *tree = desc->dyn_tree; |
| 542 | int max_code = desc->max_code; |
| 543 | const ct_data *stree = desc->stat_desc->static_tree; |
| 544 | const intf *extra = desc->stat_desc->extra_bits; |
| 545 | int base = desc->stat_desc->extra_base; |
| 546 | int max_length = desc->stat_desc->max_length; |
| 547 | int h; /* heap index */ |
| 548 | int n, m; /* iterate over the tree elements */ |
| 549 | int bits; /* bit length */ |
| 550 | int xbits; /* extra bits */ |
| 551 | ush f; /* frequency */ |
| 552 | int overflow = 0; /* number of elements with bit length too large */ |
| 553 | |
| 554 | for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0; |
| 555 | |
| 556 | /* In a first pass, compute the optimal bit lengths (which may |
| 557 | * overflow in the case of the bit length tree). |
| 558 | */ |
| 559 | tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */ |
| 560 | |
| 561 | for (h = s->heap_max + 1; h < HEAP_SIZE; h++) { |
| 562 | n = s->heap[h]; |
| 563 | bits = tree[tree[n].Dad].Len + 1; |
| 564 | if (bits > max_length) bits = max_length, overflow++; |
| 565 | tree[n].Len = (ush)bits; |
| 566 | /* We overwrite tree[n].Dad which is no longer needed */ |
| 567 | |
| 568 | if (n > max_code) continue; /* not a leaf node */ |
| 569 | |
| 570 | s->bl_count[bits]++; |
| 571 | xbits = 0; |
| 572 | if (n >= base) xbits = extra[n - base]; |
| 573 | f = tree[n].Freq; |
| 574 | s->opt_len += (ulg)f * (unsigned)(bits + xbits); |
| 575 | if (stree) s->static_len += (ulg)f * (unsigned)(stree[n].Len + xbits); |
| 576 | } |
| 577 | if (overflow == 0) return; |
| 578 | |
| 579 | Tracev((stderr,"\nbit length overflow\n")); |
| 580 | /* This happens for example on obj2 and pic of the Calgary corpus */ |
| 581 | |
| 582 | /* Find the first bit length which could increase: */ |
| 583 | do { |
| 584 | bits = max_length - 1; |
| 585 | while (s->bl_count[bits] == 0) bits--; |
| 586 | s->bl_count[bits]--; /* move one leaf down the tree */ |
| 587 | s->bl_count[bits + 1] += 2; /* move one overflow item as its brother */ |
| 588 | s->bl_count[max_length]--; |
| 589 | /* The brother of the overflow item also moves one step up, |
| 590 | * but this does not affect bl_count[max_length] |
| 591 | */ |
| 592 | overflow -= 2; |
| 593 | } while (overflow > 0); |
| 594 | |
| 595 | /* Now recompute all bit lengths, scanning in increasing frequency. |
| 596 | * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all |
| 597 | * lengths instead of fixing only the wrong ones. This idea is taken |