=========================================================================== * 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
| 478 | * not null. |
| 479 | */ |
| 480 | local void gen_bitlen(deflate_state *s, tree_desc *desc) |
| 481 | { |
| 482 | ct_data *tree = desc->dyn_tree; |
| 483 | int max_code = desc->max_code; |
| 484 | const ct_data *stree = desc->stat_desc->static_tree; |
| 485 | const intf *extra = desc->stat_desc->extra_bits; |
| 486 | int base = desc->stat_desc->extra_base; |
| 487 | int max_length = desc->stat_desc->max_length; |
| 488 | int h; /* heap index */ |
| 489 | int n, m; /* iterate over the tree elements */ |
| 490 | int bits; /* bit length */ |
| 491 | int xbits; /* extra bits */ |
| 492 | ush f; /* frequency */ |
| 493 | int overflow = 0; /* number of elements with bit length too large */ |
| 494 | |
| 495 | for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0; |
| 496 | |
| 497 | /* In a first pass, compute the optimal bit lengths (which may |
| 498 | * overflow in the case of the bit length tree). |
| 499 | */ |
| 500 | tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */ |
| 501 | |
| 502 | for (h = s->heap_max+1; h < HEAP_SIZE; h++) { |
| 503 | n = s->heap[h]; |
| 504 | bits = tree[tree[n].Dad].Len + 1; |
| 505 | if (bits > max_length) bits = max_length, overflow++; |
| 506 | tree[n].Len = (ush)bits; |
| 507 | /* We overwrite tree[n].Dad which is no longer needed */ |
| 508 | |
| 509 | if (n > max_code) continue; /* not a leaf node */ |
| 510 | |
| 511 | s->bl_count[bits]++; |
| 512 | xbits = 0; |
| 513 | if (n >= base) xbits = extra[n-base]; |
| 514 | f = tree[n].Freq; |
| 515 | s->opt_len += (ulg)f * (bits + xbits); |
| 516 | if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits); |
| 517 | } |
| 518 | if (overflow == 0) return; |
| 519 | |
| 520 | Trace((stderr,"\nbit length overflow\n")); |
| 521 | /* This happens for example on obj2 and pic of the Calgary corpus */ |
| 522 | |
| 523 | /* Find the first bit length which could increase: */ |
| 524 | do { |
| 525 | bits = max_length-1; |
| 526 | while (s->bl_count[bits] == 0) bits--; |
| 527 | s->bl_count[bits]--; /* move one leaf down the tree */ |
| 528 | s->bl_count[bits+1] += 2; /* move one overflow item as its brother */ |
| 529 | s->bl_count[max_length]--; |
| 530 | /* The brother of the overflow item also moves one step up, |
| 531 | * but this does not affect bl_count[max_length] |
| 532 | */ |
| 533 | overflow -= 2; |
| 534 | } while (overflow > 0); |
| 535 | |
| 536 | /* Now recompute all bit lengths, scanning in increasing frequency. |
| 537 | * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all |