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     tree1bound = getbits(5);
  25     mindepth = getbits(3);
  26     if (mindepth == 0) {
  27         tree_setsingle(&tree1, tree1bound - 1);
  28     }
  29     else {
  30         for (i = 0; i < 32; i++)
  31             table1[i] = 0;
  32         nbits = getbits(3);
  33         for (i = 0; i < tree1bound; i++) {
  34             x = getbits(nbits);
  35             table1[i] = (x == 0 ? 0 : x - 1 + mindepth);
  36         }
  37         tree_rebuild(&tree1, tree1bound, mindepth, table1);
  38     }
  39 }
  40
  41 void
  42 maketree2(int par_b) /* in use: 5 <= par_b <= 8 */
  43 {
  44     int i, count, index;
  45
  46     if (tree1bound < 10)
  47         return;
  48
  49     if (tree1bound == 29 && mindepth == 0)
  50         return;
  51
  52     for (i = 0; i < 8; i++)
  53         table2[i] = 0;
  54     for (i = 0; i < par_b; i++)
  55         table2[i] = getbits(3);
  56
  57     index = 0;
  58     count = 0;
  59     for (i = 0; i < 8; i++) {
  60         if (table2[i] != 0) {
  61             index = i;
  62             count++;
  63         }
  64     }
  65
  66     if (count == 1) {
  67         tree_setsingle(&tree2, index);
  68     }
  69     else if (count > 1) {
  70         mindepth = 1;
  71         tree_rebuild(&tree2, 8, mindepth, table2);
  72     }
  73     // Note: count == 0 is possible!
  74     //       Excluding that possibility was a bug in version 1.
  75
  76 }
  77
  78 int
  79 tree_get(struct tree *t)
  80 {
  81     int i;
  82     i = t->root;
  83     while (i < 0x80) {
  84         i = (getbits(1) == 0 ? t->leftarr[i] : t->rightarr[i]);
  85     }
  86     return i & 0x7F;
  87 }
  88
  89 void
  90 tree_setsingle(struct tree *t, unsigned char value)
  91 {
  92     t->root = 128 | value;
  93 }
  94
  95 void
  96 tree_rebuild(struct tree *t,
  97              unsigned char bound,
  98              unsigned char mindepth,
  99              unsigned char *table)
 100 {
 101     unsigned char *parentarr, d;
 102     int i, curr, empty, n;
 103
 104     parentarr = (unsigned char *)malloc(bound * sizeof(unsigned char));
 105     t->root = 0;
 106     for (i = 0; i < bound; i++) {
 107         t->leftarr[i] = 0;
 108         t->rightarr[i] = 0;
 109         parentarr[i] = 0;
 110     }
 111
 112     for (i = 0; i < mindepth - 1; i++) {
 113         t->leftarr[i] = i + 1;
 114         parentarr[i + 1] = i;
 115     }
 116
 117     curr = mindepth - 1;
 118     empty = mindepth;
 119     for (d = mindepth; TRUE; d++) {
 120         for (i = 0; i < bound; i++) {
 121             if (table[i] == d) {
 122                 if (t->leftarr[curr] == 0)
 123                     t->leftarr[curr] = i | 128;
 124                 else {
 125                     t->rightarr[curr] = i | 128;
 126                     n = 0;
 127                     while (t->rightarr[curr] != 0) {
 128                         if (curr == 0) {        /* root? -> done */
 129                             free(parentarr);
 130                             return;
 131                         }
 132                         curr = parentarr[curr];
 133                         n++;
 134                     }
 135                     t->rightarr[curr] = empty;
 136                     for (;;) {
 137                         parentarr[empty] = curr;
 138                         curr = empty;
 139                         empty++;
 140
 141                         n--;
 142                         if (n == 0)
 143                             break;
 144                         t->leftarr[curr] = empty;
 145                     }
 146                 }
 147             }
 148         }
 149         if (t->leftarr[curr] == 0)
 150             t->leftarr[curr] = empty;
 151         else
 152             t->rightarr[curr] = empty;
 153
 154         parentarr[empty] = curr;
 155         curr = empty;
 156         empty++;
 157     }
 158 }