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