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