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