src/pm2tree.c

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