maketree.c was refined

diff --git a/maketree.c b/maketree.c
index 8522abb..dd5e9a9 100644 (file)
--- a/maketree.c
+++ b/maketree.c
@@ -15,12 +15,13 @@ freq | leafs(0..nparm)       | nodes(nparm..nparm*2) |
    frequency of huffman leafs    frequency of humman nodes
 
 
-      e.g:
-                 .     ... freq[4]
+      e.g: nparm = 3
+
+                 4     ... freq[4]
                 / \
-               .   \   ... freq[3]
+               3   \   ... freq[3]
               /\    \
-             a  b    c ... freq[0 .. 2]
+             0  1    2 ... freq[0 .. 2]
 
 */
 struct heap_t {
@@ -163,7 +164,7 @@ static void
 make_len(struct tree_t *t, uint8_t *len, uint16_t *sortptr)
 {
     int i, k;
-    uint cum;
+    uint32_t cum;
 
     for (i = 0; i <= 16; i++)
         t->len_cnt[i] = 0;
@@ -193,13 +194,41 @@ static void
 make_code(struct tree_t *t, uint8_t *len, uint16_t *code)
 {
     int i;
-    ushort start[18];
+    uint16_t start[18], c;
 
+    /*
+       /\               a: 0     len_cnt[1] = 1
+      a /\              b: 10    len_cnt[2] = 2
+        b c             c: 11    len_cnt[2] = 2
+
+              i     len_cnt[i]   start[i]
+          --------------------------------
+              1         1         0
+              2         2        (0 + 1)*2 = 2
+              3         0        (2 + 2)*2 = 8
+              4         0        (8 + 0)*2 =16
+              5         0                   32
+              6         0                   64
+              :         :                    :
+             15         0    (16384 + 0)*2 =32768
+             16         0    (32768 + 0)*2 = 0
+             17         -    (65536 + 0)*2 = 2
+     */
     start[1] = 0;
     for (i = 1; i <= 16; i++)
         start[i + 1] = (start[i] + t->len_cnt[i]) << 1;
-    for (i = 0; i < t->max_leafs; i++)
-        code[i] = start[len[i]]++;
+
+    /*
+      c  len[c]   i     len_cnt[i]   start[i]   code[c] (Huffman coding)
+     ----------------------------------------------------------------
+      a     1     1         1            0      00000000 0000000 0
+      b     2     2         2            2      00000000 000000 10
+      c     2     2         2            3      00000000 000000 11
+    */
+    for (c = 0; c < t->max_leafs; c++) {
+        i = len[c];
+        code[c] = start[i]++;
+    }
 }
 
 /* make Huffman encoding tables.