(s, desc)
| 11026 | * also updated if stree is not null. The field max_code is set. |
| 11027 | */ |
| 11028 | function build_tree(s, desc) |
| 11029 | // deflate_state *s; |
| 11030 | // tree_desc *desc; /* the tree descriptor */ |
| 11031 | { |
| 11032 | var tree = desc.dyn_tree; |
| 11033 | var stree = desc.stat_desc.static_tree; |
| 11034 | var has_stree = desc.stat_desc.has_stree; |
| 11035 | var elems = desc.stat_desc.elems; |
| 11036 | var n, m; /* iterate over heap elements */ |
| 11037 | var max_code = -1; /* largest code with non zero frequency */ |
| 11038 | var node; /* new node being created */ |
| 11039 | |
| 11040 | /* Construct the initial heap, with least frequent element in |
| 11041 | * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. |
| 11042 | * heap[0] is not used. |
| 11043 | */ |
| 11044 | s.heap_len = 0; |
| 11045 | s.heap_max = HEAP_SIZE; |
| 11046 | |
| 11047 | for (n = 0; n < elems; n++) { |
| 11048 | if (tree[n * 2]/*.Freq*/ !== 0) { |
| 11049 | s.heap[++s.heap_len] = max_code = n; |
| 11050 | s.depth[n] = 0; |
| 11051 | |
| 11052 | } else { |
| 11053 | tree[n * 2 + 1]/*.Len*/ = 0; |
| 11054 | } |
| 11055 | } |
| 11056 | |
| 11057 | /* The pkzip format requires that at least one distance code exists, |
| 11058 | * and that at least one bit should be sent even if there is only one |
| 11059 | * possible code. So to avoid special checks later on we force at least |
| 11060 | * two codes of non zero frequency. |
| 11061 | */ |
| 11062 | while (s.heap_len < 2) { |
| 11063 | node = s.heap[++s.heap_len] = (max_code < 2 ? ++max_code : 0); |
| 11064 | tree[node * 2]/*.Freq*/ = 1; |
| 11065 | s.depth[node] = 0; |
| 11066 | s.opt_len--; |
| 11067 | |
| 11068 | if (has_stree) { |
| 11069 | s.static_len -= stree[node * 2 + 1]/*.Len*/; |
| 11070 | } |
| 11071 | /* node is 0 or 1 so it does not have extra bits */ |
| 11072 | } |
| 11073 | desc.max_code = max_code; |
| 11074 | |
| 11075 | /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, |
| 11076 | * establish sub-heaps of increasing lengths: |
| 11077 | */ |
| 11078 | for (n = (s.heap_len >> 1/*int /2*/); n >= 1; n--) { pqdownheap(s, tree, n); } |
| 11079 | |
| 11080 | /* Construct the Huffman tree by repeatedly combining the least two |
| 11081 | * frequent nodes. |
| 11082 | */ |
| 11083 | node = elems; /* next internal node of the tree */ |
| 11084 | do { |
| 11085 | //pqremove(s, tree, n); /* n = node of least frequency */ |
no test coverage detected