(s, desc)
| 23008 | * also updated if stree is not null. The field max_code is set. |
| 23009 | */ |
| 23010 | function build_tree(s, desc) |
| 23011 | // deflate_state *s; |
| 23012 | // tree_desc *desc; /* the tree descriptor */ |
| 23013 | { |
| 23014 | var tree = desc.dyn_tree; |
| 23015 | var stree = desc.stat_desc.static_tree; |
| 23016 | var has_stree = desc.stat_desc.has_stree; |
| 23017 | var elems = desc.stat_desc.elems; |
| 23018 | var n, m; /* iterate over heap elements */ |
| 23019 | var max_code = -1; /* largest code with non zero frequency */ |
| 23020 | var node; /* new node being created */ |
| 23021 | |
| 23022 | /* Construct the initial heap, with least frequent element in |
| 23023 | * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. |
| 23024 | * heap[0] is not used. |
| 23025 | */ |
| 23026 | s.heap_len = 0; |
| 23027 | s.heap_max = HEAP_SIZE; |
| 23028 | |
| 23029 | for (n = 0; n < elems; n++) { |
| 23030 | if (tree[n * 2]/*.Freq*/ !== 0) { |
| 23031 | s.heap[++s.heap_len] = max_code = n; |
| 23032 | s.depth[n] = 0; |
| 23033 | |
| 23034 | } else { |
| 23035 | tree[n * 2 + 1]/*.Len*/ = 0; |
| 23036 | } |
| 23037 | } |
| 23038 | |
| 23039 | /* The pkzip format requires that at least one distance code exists, |
| 23040 | * and that at least one bit should be sent even if there is only one |
| 23041 | * possible code. So to avoid special checks later on we force at least |
| 23042 | * two codes of non zero frequency. |
| 23043 | */ |
| 23044 | while (s.heap_len < 2) { |
| 23045 | node = s.heap[++s.heap_len] = (max_code < 2 ? ++max_code : 0); |
| 23046 | tree[node * 2]/*.Freq*/ = 1; |
| 23047 | s.depth[node] = 0; |
| 23048 | s.opt_len--; |
| 23049 | |
| 23050 | if (has_stree) { |
| 23051 | s.static_len -= stree[node * 2 + 1]/*.Len*/; |
| 23052 | } |
| 23053 | /* node is 0 or 1 so it does not have extra bits */ |
| 23054 | } |
| 23055 | desc.max_code = max_code; |
| 23056 | |
| 23057 | /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, |
| 23058 | * establish sub-heaps of increasing lengths: |
| 23059 | */ |
| 23060 | for (n = (s.heap_len >> 1/*int /2*/); n >= 1; n--) { pqdownheap(s, tree, n); } |
| 23061 | |
| 23062 | /* Construct the Huffman tree by repeatedly combining the least two |
| 23063 | * frequent nodes. |
| 23064 | */ |
| 23065 | node = elems; /* next internal node of the tree */ |
| 23066 | do { |
| 23067 | //pqremove(s, tree, n); /* n = node of least frequency */ |
no test coverage detected