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