=========================================================================== * Construct one Huffman tree and assigns the code bit strings and lengths. * Update the total bit length for the current block. * IN assertion: the field freq is set for all tree elements. * OUT assertions: the fields len and code are set to the optimal bit length * and corresponding code. The length opt_len is up
| 602 | * also updated if stree is not null. The field max_code is set. |
| 603 | */ |
| 604 | local void build_tree(deflate_state *s, tree_desc *desc) |
| 605 | { |
| 606 | ct_data *tree = desc->dyn_tree; |
| 607 | const ct_data *stree = desc->stat_desc->static_tree; |
| 608 | int elems = desc->stat_desc->elems; |
| 609 | int n, m; /* iterate over heap elements */ |
| 610 | int max_code = -1; /* largest code with non zero frequency */ |
| 611 | int node; /* new node being created */ |
| 612 | |
| 613 | /* Construct the initial heap, with least frequent element in |
| 614 | * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. |
| 615 | * heap[0] is not used. |
| 616 | */ |
| 617 | s->heap_len = 0, s->heap_max = HEAP_SIZE; |
| 618 | |
| 619 | for (n = 0; n < elems; n++) { |
| 620 | if (tree[n].Freq != 0) { |
| 621 | s->heap[++(s->heap_len)] = max_code = n; |
| 622 | s->depth[n] = 0; |
| 623 | } else { |
| 624 | tree[n].Len = 0; |
| 625 | } |
| 626 | } |
| 627 | |
| 628 | /* The pkzip format requires that at least one distance code exists, |
| 629 | * and that at least one bit should be sent even if there is only one |
| 630 | * possible code. So to avoid special checks later on we force at least |
| 631 | * two codes of non zero frequency. |
| 632 | */ |
| 633 | while (s->heap_len < 2) { |
| 634 | node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0); |
| 635 | tree[node].Freq = 1; |
| 636 | s->depth[node] = 0; |
| 637 | s->opt_len--; if (stree) s->static_len -= stree[node].Len; |
| 638 | /* node is 0 or 1 so it does not have extra bits */ |
| 639 | } |
| 640 | desc->max_code = max_code; |
| 641 | |
| 642 | /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, |
| 643 | * establish sub-heaps of increasing lengths: |
| 644 | */ |
| 645 | for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n); |
| 646 | |
| 647 | /* Construct the Huffman tree by repeatedly combining the least two |
| 648 | * frequent nodes. |
| 649 | */ |
| 650 | node = elems; /* next internal node of the tree */ |
| 651 | do { |
| 652 | pqremove(s, tree, n); /* n = node of least frequency */ |
| 653 | m = s->heap[SMALLEST]; /* m = node of next least frequency */ |
| 654 | |
| 655 | s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */ |
| 656 | s->heap[--(s->heap_max)] = m; |
| 657 | |
| 658 | /* Create a new node father of n and m */ |
| 659 | tree[node].Freq = tree[n].Freq + tree[m].Freq; |
| 660 | s->depth[node] = (uch)((s->depth[n] >= s->depth[m] ? |
| 661 | s->depth[n] : s->depth[m]) + 1); |
no test coverage detected