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