src/pm2tree.c

   1 /***********************************************************
   2         pm2tree.c -- tree for pmext2 decoding
   3 ***********************************************************/
   4
   5 #ifdef __STDC__
   6 #include <stdlib.h>
   7 #endif
   8 #include "pm2tree.h"
   9 #include "lha.h"
  10
  11 static unsigned char tree1left[32];
  12 static unsigned char tree1right[32];
  13 struct tree tree1 = { 0, tree1left, tree1right };
  14 static unsigned char table1[32];
  15
  16 static unsigned char tree2left[8];
  17 static unsigned char tree2right[8];
  18 struct tree tree2 = { 0, tree2left, tree2right };
  19 static unsigned char table2[8];
  20
  21 static unsigned char tree1bound;
  22 static unsigned char mindepth;
  23
  24 void maketree1()
  25 {
  26     int i, nbits, x;
  27     tree1bound = getbits(5);
  28     mindepth = getbits(3);
  29     if (mindepth == 0)
  30     {
  31         tree_setsingle(&tree1, tree1bound - 1);
  32     }
  33     else
  34     {
  35         for (i = 0; i<32; i++) table1[i] = 0;
  36         nbits = getbits(3);
  37         for (i = 0; i < tree1bound; i++) {
  38             x = getbits(nbits);
  39             table1[i] = ( x == 0 ? 0 : x - 1 + mindepth );
  40         }
  41         tree_rebuild(&tree1, tree1bound, mindepth, table1);
  42     }
  43 }
  44
  45 void maketree2(int par_b) /* in use: 5 <= par_b <= 8 */
  46 {
  47     int i, count, index;
  48     if (tree1bound < 10) return;
  49     if (tree1bound == 29 && mindepth == 0) return;
  50
  51     for (i = 0; i < 8; i++) table2[i] = 0;
  52     for (i = 0; i < par_b; i++) table2[i] = getbits(3);
  53     index = 0;
  54     count = 0;
  55     for (i = 0; i < 8; i++)
  56     {
  57         if (table2[i] != 0)
  58         {
  59             index = i;
  60             count++;
  61         }
  62     }
  63
  64     if (count == 1)
  65     {
  66         tree_setsingle(&tree2, index);
  67     }
  68     else if (count > 1)
  69     {
  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 tree_get(struct tree *t)
  79 {
  80     int i;
  81     i = t->root;
  82     while (i < 0x80)
  83     {
  84         i = ( getbits(1) == 0 ? t->leftarr[i] : t->rightarr[i] );
  85     }
  86     return i & 0x7F;
  87 }
  88
  89 void tree_setsingle(struct tree *t, unsigned char value)
  90 {
  91     t->root = 128 | value;
  92 }
  93
  94 void tree_rebuild(t, bound, mindepth, table)
  95 struct tree *t;
  96 unsigned char bound;
  97 unsigned char mindepth;
  98 unsigned char *table;
  99 {
 100     unsigned char *parentarr, d;
 101     int i, curr, empty, n;
 102     parentarr = (unsigned char *)malloc(bound * sizeof(unsigned char));
 103     t->root = 0;
 104     for (i = 0; i < bound; i++)
 105     {
 106         t->leftarr[i]   = 0;
 107         t->rightarr[i]  = 0;
 108         parentarr[i] = 0;
 109     }
 110
 111     for (i = 0; i < mindepth - 1; i++)
 112     {
 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     {
 121         for (i = 0; i < bound; i++)
 122         {
 123             if (table[i] == d)
 124             {
 125                 if (t->leftarr[curr] == 0) t->leftarr[curr] = i | 128;
 126                 else
 127                 {
 128                     t->rightarr[curr] = i | 128;
 129                     n = 0;
 130                     while (t->rightarr[curr] != 0)
 131                     {
 132                         if (curr == 0) /* root? -> done */
 133                         {
 134                             free(parentarr);
 135                             return;
 136                         }
 137                         curr = parentarr[curr];
 138                         n++;
 139                     }
 140                     t->rightarr[curr] = empty;
 141                     for (;;)
 142                     {
 143                         parentarr[empty] = curr;
 144                         curr = empty;
 145                         empty++;
 146
 147                         n--; if (n == 0) break;
 148                         t->leftarr[curr] = empty;
 149                     }
 150                 }
 151             }
 152         }
 153         if (t->leftarr[curr] == 0) t->leftarr[curr] = empty; else t->rightarr[curr] = empty;
 154
 155         parentarr[empty] = curr;
 156         curr = empty;
 157         empty++;
 158     }
 159 }
 160