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