summaryrefslogtreecommitdiffstatshomepage
path: root/src/lib/util/huffman.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/util/huffman.c')
-rw-r--r--src/lib/util/huffman.c23
1 files changed, 20 insertions, 3 deletions
diff --git a/src/lib/util/huffman.c b/src/lib/util/huffman.c
index 21ef7adc029..60120bbdf32 100644
--- a/src/lib/util/huffman.c
+++ b/src/lib/util/huffman.c
@@ -535,7 +535,11 @@ int CLIB_DECL huffman_context_base::tree_node_compare(const void *item1, const v
{
const node_t *node1 = *(const node_t **)item1;
const node_t *node2 = *(const node_t **)item2;
- return node2->m_weight - node1->m_weight;
+ if (node2->m_weight != node1->m_weight)
+ return node2->m_weight - node1->m_weight;
+ if (node2->m_bits - node1->m_bits == 0)
+ fprintf(stderr, "identical node sort keys, should not happen!\n");
+ return (int)node1->m_bits - (int)node2->m_bits;
}
@@ -555,16 +559,28 @@ int huffman_context_base::build_tree(UINT32 totaldata, UINT32 totalweight)
{
list[listitems++] = &m_huffnode[curcode];
m_huffnode[curcode].m_count = m_datahisto[curcode];
+ m_huffnode[curcode].m_bits = curcode;
// scale the weight by the current effective length, ensuring we don't go to 0
m_huffnode[curcode].m_weight = UINT64(m_datahisto[curcode]) * UINT64(totalweight) / UINT64(totaldata);
if (m_huffnode[curcode].m_weight == 0)
m_huffnode[curcode].m_weight = 1;
}
-
+/*
+ fprintf(stderr, "Pre-sort:\n");
+ for (int i = 0; i < listitems; i++) {
+ fprintf(stderr, "weight: %d code: %d\n", list[i]->m_weight, list[i]->m_bits);
+ }
+*/
// sort the list by weight, largest weight first
qsort(list, listitems, sizeof(list[0]), tree_node_compare);
-
+/*
+ fprintf(stderr, "Post-sort:\n");
+ for (int i = 0; i < listitems; i++) {
+ fprintf(stderr, "weight: %d code: %d\n", list[i]->m_weight, list[i]->m_bits);
+ }
+ fprintf(stderr, "===================\n");
+*/
// now build the tree
int nextalloc = m_numcodes;
while (listitems > 1)
@@ -597,6 +613,7 @@ int huffman_context_base::build_tree(UINT32 totaldata, UINT32 totalweight)
{
node_t &node = m_huffnode[curcode];
node.m_numbits = 0;
+ node.m_bits = 0;
// if we have a non-zero weight, compute the number of bits
if (node.m_weight > 0)