src/pm2tree.c

   1 /***********************************************************
   2         pm2tree.c -- tree for pmext2 decoding
   3 ***********************************************************/
   4 #include "lha.h"
   5
   6 struct tree {
   7     unsigned char root, *leftarr, *rightarr;
   8 };
   9
  10 static unsigned char tree1left[32];
  11 static unsigned char tree1right[32];
  12 static struct tree tree1 = { 0, tree1left, tree1right };
  13
  14 static unsigned char tree2left[8];
  15 static unsigned char tree2right[8];
  16 static struct tree tree2 = { 0, tree2left, tree2right };
  17
  18 static void tree_setsingle(struct tree *t, unsigned char value);
  19 static void tree_rebuild(struct tree *t, unsigned char bound,
  20                   unsigned char mindepth, unsigned char maxdepth,
  21                   unsigned char *table);
  22 static void tree_setsingle(struct tree *t, unsigned char value);
  23
  24 static unsigned char tree1bound;
  25 static unsigned char mindepth;
  26
  27 void
  28 maketree1()
  29 {
  30     int i, nbits, x;
  31     unsigned char table1[32];
  32
  33     tree1bound = getbits(5);
  34     mindepth = getbits(3);
  35     if (mindepth == 0) {
  36         tree_setsingle(&tree1, tree1bound - 1);
  37     }
  38     else {
  39         for (i = 0; i < 32; i++)
  40             table1[i] = 0;
  41         nbits = getbits(3);
  42         for (i = 0; i < tree1bound; i++) {
  43             x = getbits(nbits);
  44             table1[i] = (x == 0 ? 0 : x - 1 + mindepth);
  45         }
  46         tree_rebuild(&tree1, tree1bound, mindepth, 31, table1);
  47     }
  48 }
  49
  50 void
  51 maketree2(int tree2bound) /* in use: 5 <= tree2bound <= 8 */
  52 {
  53     int i, count, index;
  54     unsigned char table2[8];
  55
  56
  57     if (tree1bound < 10)
  58         /* tree1bound=1..8: character only, offset value is no needed. */
  59         /* tree1bound=9: offset value is not encoded by Huffman tree */
  60         return;
  61
  62     if (tree1bound == 29 && mindepth == 0)
  63         /* the length value is just 256 and offset value is just 0 */
  64         return;
  65
  66     /* need to build tree2 for offset value */
  67
  68     for (i = 0; i < 8; i++)
  69         table2[i] = 0;
  70     for (i = 0; i < tree2bound; i++)
  71         table2[i] = getbits(3);
  72
  73     index = 0;
  74     count = 0;
  75     for (i = 0; i < tree2bound; i++) {
  76         if (table2[i] != 0) {
  77             index = i;
  78             count++;
  79         }
  80     }
  81
  82     if (count == 1) {
  83         tree_setsingle(&tree2, index);
  84     }
  85     else if (count > 1) {
  86         tree_rebuild(&tree2, tree2bound, 1, 7, table2);
  87     }
  88     // Note: count == 0 is possible!
  89     //       Excluding that possibility was a bug in version 1.
  90
  91 }
  92
  93 static int
  94 tree_get(struct tree *t)
  95 {
  96     int i;
  97     i = t->root;
  98     while (i < 0x80) {
  99         i = (getbits(1) == 0 ? t->leftarr[i] : t->rightarr[i]);
 100     }
 101     return i & 0x7F;
 102 }
 103
 104 int
 105 tree1_get()
 106 {
 107     return tree_get(&tree1);
 108 }
 109
 110 int
 111 tree2_get()
 112 {
 113     return tree_get(&tree2);
 114 }
 115
 116 static void
 117 tree_setsingle(struct tree *t, unsigned char value)
 118 {
 119     t->root = 128 | value;
 120 }
 121
 122 static void
 123 tree_rebuild(struct tree *t,
 124              unsigned char bound,
 125              unsigned char mindepth,
 126              unsigned char maxdepth,
 127              unsigned char *table)
 128 {
 129     unsigned char parentarr[32], d;
 130     int i, curr, empty, n;
 131
 132     /* validate table */
 133     {
 134         unsigned int count[32];
 135         double total;
 136
 137         memset(count, 0, sizeof(count));
 138         for (i = 0; i < bound; i++) {
 139             if (table[i] > maxdepth) {
 140                 error("Bad table");
 141                 exit(1);
 142             }
 143             count[table[i]]++;
 144         }
 145         total = 0.0;
 146         for (i = mindepth; i <= maxdepth; i++) {
 147             int max_leaves = (1<<i);
 148             if (count[i] > max_leaves) {
 149                 error("Bad table");
 150                 exit(1);
 151             }
 152             total += 1.0/max_leaves * count[i];
 153         }
 154         if (total != 1.0) {
 155             /* check the Kraft's inequality */
 156             error("Bad table");
 157             exit(1);
 158         }
 159     }
 160
 161     /* initialize tree */
 162     t->root = 0;
 163     for (i = 0; i < bound; i++) {
 164         t->leftarr[i] = 0;
 165         t->rightarr[i] = 0;
 166         parentarr[i] = 0;
 167     }
 168
 169     /* build tree */
 170     for (i = 0; i < mindepth - 1; i++) {
 171         t->leftarr[i] = i + 1;
 172         parentarr[i + 1] = i;
 173     }
 174
 175     curr = mindepth - 1;
 176     empty = mindepth;
 177     for (d = mindepth; d <= maxdepth; d++) {
 178         for (i = 0; i < bound; i++) {
 179             if (table[i] != d)
 180                 continue;
 181
 182             if (t->leftarr[curr] == 0) {
 183                 t->leftarr[curr] = i | 128;
 184                 continue;
 185             }
 186
 187             t->rightarr[curr] = i | 128;
 188             n = 0;
 189             while (t->rightarr[curr] != 0) {
 190                 if (curr == 0) {        /* root? -> done */
 191                     return;
 192                 }
 193                 curr = parentarr[curr];
 194                 n++;
 195             }
 196
 197             t->rightarr[curr] = empty;
 198             for (;;) {
 199                 parentarr[empty] = curr;
 200                 curr = empty;
 201                 empty++;
 202
 203                 n--;
 204                 if (n == 0)
 205                     break;
 206                 t->leftarr[curr] = empty;
 207             }
 208         }
 209
 210         if (t->leftarr[curr] == 0)
 211             t->leftarr[curr] = empty;
 212         else
 213             t->rightarr[curr] = empty;
 214
 215         parentarr[empty] = curr;
 216         curr = empty;
 217         empty++;
 218     }
 219
 220     /* unreachable */
 221     error("bad table");
 222     exit(1);
 223 }