=========================================================================== * 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
(s, desc)
| 628 | * also updated if stree is not null. The field max_code is set. |
| 629 | */ |
| 630 | local void build_tree(s, desc) |
| 631 | deflate_state* s; |
| 632 | |
| 633 | tree_desc* desc; /* the tree descriptor */ |
| 634 | { |
| 635 | ct_data* tree = desc->dyn_tree; |
| 636 | const ct_data* stree = desc->stat_desc->static_tree; |
| 637 | int elems = desc->stat_desc->elems; |
| 638 | int n, m; /* iterate over heap elements */ |
| 639 | int max_code = -1; /* largest code with non zero frequency */ |
| 640 | int node; /* new node being created */ |
| 641 | |
| 642 | /* Construct the initial heap, with least frequent element in |
| 643 | * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. |
| 644 | * heap[0] is not used. |
| 645 | */ |
| 646 | s->heap_len = 0 , s->heap_max = HEAP_SIZE; |
| 647 | |
| 648 | for (n = 0; n < elems; n++) |
| 649 | { |
| 650 | if (tree[n].Freq != 0) |
| 651 | { |
| 652 | s->heap[++(s->heap_len)] = max_code = n; |
| 653 | s->depth[n] = 0; |
| 654 | } |
| 655 | else |
| 656 | { |
| 657 | tree[n].Len = 0; |
| 658 | } |
| 659 | } |
| 660 | |
| 661 | /* The pkzip format requires that at least one distance code exists, |
| 662 | * and that at least one bit should be sent even if there is only one |
| 663 | * possible code. So to avoid special checks later on we force at least |
| 664 | * two codes of non zero frequency. |
| 665 | */ |
| 666 | while (s->heap_len < 2) |
| 667 | { |
| 668 | node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0); |
| 669 | tree[node].Freq = 1; |
| 670 | s->depth[node] = 0; |
| 671 | s->opt_len--; |
| 672 | if (stree) s->static_len -= stree[node].Len; |
| 673 | /* node is 0 or 1 so it does not have extra bits */ |
| 674 | } |
| 675 | desc->max_code = max_code; |
| 676 | |
| 677 | /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, |
| 678 | * establish sub-heaps of increasing lengths: |
| 679 | */ |
| 680 | for (n = s->heap_len / 2; n >= 1; n--) pqdownheap(s, tree, n); |
| 681 | |
| 682 | /* Construct the Huffman tree by repeatedly combining the least two |
| 683 | * frequent nodes. |
| 684 | */ |
| 685 | node = elems; /* next internal node of the tree */ |
| 686 | do |
| 687 | { |
no test coverage detected