src/pm2tree.c

   1 /***********************************************************
   2         pm2tree.c -- tree for pmext2 decoding
   3 ***********************************************************/
   4 /*
   5   Copyright (c) 1999 Maarten ter Huurne
   6
   7   Permission is hereby granted, free of charge, to any person
   8   obtaining a copy of this software and associated documentation files
   9   (the "Software"), to deal in the Software without restriction,
  10   including without limitation the rights to use, copy, modify, merge,
  11   publish, distribute, sublicense, and/or sell copies of the Software,
  12   and to permit persons to whom the Software is furnished to do so,
  13   subject to the following conditions:
  14
  15   The above copyright notice and this permission notice shall be
  16   included in all copies or substantial portions of the Software.
  17
  18   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  19   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  21   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  22   BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  23   ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  24   CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  25   SOFTWARE.
  26 */
  27 #include "lha.h"
  28
  29 struct tree {
  30     unsigned char root, *leftarr, *rightarr;
  31 };
  32
  33 static unsigned char tree1left[32];
  34 static unsigned char tree1right[32];
  35 static struct tree tree1 = { 0, tree1left, tree1right };
  36
  37 static unsigned char tree2left[8];
  38 static unsigned char tree2right[8];
  39 static struct tree tree2 = { 0, tree2left, tree2right };
  40
  41 static void tree_setsingle(struct tree *t, unsigned char value);
  42 static void tree_rebuild(struct tree *t, unsigned char bound,
  43                   unsigned char mindepth, unsigned char maxdepth,
  44                   unsigned char *table);
  45 static void tree_setsingle(struct tree *t, unsigned char value);
  46
  47 static unsigned char tree1bound;
  48 static unsigned char mindepth;
  49
  50 void
  51 maketree1()
  52 {
  53     int i, nbits, x;
  54     unsigned char table1[32];
  55
  56     tree1bound = getbits(5);
  57     mindepth = getbits(3);
  58     if (mindepth == 0) {
  59         tree_setsingle(&tree1, tree1bound - 1);
  60     }
  61     else {
  62         for (i = 0; i < 32; i++)
  63             table1[i] = 0;
  64         nbits = getbits(3);
  65         for (i = 0; i < tree1bound; i++) {
  66             x = getbits(nbits);
  67             table1[i] = (x == 0 ? 0 : x - 1 + mindepth);
  68         }
  69         tree_rebuild(&tree1, tree1bound, mindepth, 31, table1);
  70     }
  71 }
  72
  73 void
  74 maketree2(int tree2bound) /* in use: 5 <= tree2bound <= 8 */
  75 {
  76     int i, count, index;
  77     unsigned char table2[8];
  78
  79
  80     if (tree1bound < 10)
  81         /* tree1bound=1..8: character only, offset value is no needed. */
  82         /* tree1bound=9: offset value is not encoded by Huffman tree */
  83         return;
  84
  85     if (tree1bound == 29 && mindepth == 0)
  86         /* the length value is just 256 and offset value is just 0 */
  87         return;
  88
  89     /* need to build tree2 for offset value */
  90
  91     for (i = 0; i < 8; i++)
  92         table2[i] = 0;
  93     for (i = 0; i < tree2bound; i++)
  94         table2[i] = getbits(3);
  95
  96     index = 0;
  97     count = 0;
  98     for (i = 0; i < tree2bound; i++) {
  99         if (table2[i] != 0) {
 100             index = i;
 101             count++;
 102         }
 103     }
 104
 105     if (count == 1) {
 106         tree_setsingle(&tree2, index);
 107     }
 108     else if (count > 1) {
 109         tree_rebuild(&tree2, tree2bound, 1, 7, table2);
 110     }
 111     // Note: count == 0 is possible!
 112     //       Excluding that possibility was a bug in version 1.
 113
 114 }
 115
 116 static int
 117 tree_get(struct tree *t)
 118 {
 119     int i;
 120     i = t->root;
 121     while (i < 0x80) {
 122         i = (getbits(1) == 0 ? t->leftarr[i] : t->rightarr[i]);
 123     }
 124     return i & 0x7F;
 125 }
 126
 127 int
 128 tree1_get()
 129 {
 130     return tree_get(&tree1);
 131 }
 132
 133 int
 134 tree2_get()
 135 {
 136     return tree_get(&tree2);
 137 }
 138
 139 static void
 140 tree_setsingle(struct tree *t, unsigned char value)
 141 {
 142     t->root = 128 | value;
 143 }
 144
 145 static void
 146 tree_rebuild(struct tree *t,
 147              unsigned char bound,
 148              unsigned char mindepth,
 149              unsigned char maxdepth,
 150              unsigned char *table)
 151 {
 152     unsigned char parentarr[32], d;
 153     int i, curr, empty, n;
 154
 155     /* validate table */
 156     {
 157         unsigned int count[32];
 158         double total;
 159
 160         memset(count, 0, sizeof(count));
 161         for (i = 0; i < bound; i++) {
 162             if (table[i] > maxdepth) {
 163                 error("Bad table");
 164                 exit(1);
 165             }
 166             count[table[i]]++;
 167         }
 168         total = 0.0;
 169         for (i = mindepth; i <= maxdepth; i++) {
 170             int max_leaves = (1<<i);
 171             if (count[i] > max_leaves) {
 172                 error("Bad table");
 173                 exit(1);
 174             }
 175             total += 1.0/max_leaves * count[i];
 176         }
 177         if (total != 1.0) {
 178             /* check the Kraft's inequality */
 179             error("Bad table");
 180             exit(1);
 181         }
 182     }
 183
 184     /* initialize tree */
 185     t->root = 0;
 186     for (i = 0; i < bound; i++) {
 187         t->leftarr[i] = 0;
 188         t->rightarr[i] = 0;
 189         parentarr[i] = 0;
 190     }
 191
 192     /* build tree */
 193     for (i = 0; i < mindepth - 1; i++) {
 194         t->leftarr[i] = i + 1;
 195         parentarr[i + 1] = i;
 196     }
 197
 198     curr = mindepth - 1;
 199     empty = mindepth;
 200     for (d = mindepth; d <= maxdepth; d++) {
 201         for (i = 0; i < bound; i++) {
 202             if (table[i] != d)
 203                 continue;
 204
 205             if (t->leftarr[curr] == 0) {
 206                 t->leftarr[curr] = i | 128;
 207                 continue;
 208             }
 209
 210             t->rightarr[curr] = i | 128;
 211             n = 0;
 212             while (t->rightarr[curr] != 0) {
 213                 if (curr == 0) {        /* root? -> done */
 214                     return;
 215                 }
 216                 curr = parentarr[curr];
 217                 n++;
 218             }
 219
 220             t->rightarr[curr] = empty;
 221             for (;;) {
 222                 parentarr[empty] = curr;
 223                 curr = empty;
 224                 empty++;
 225
 226                 n--;
 227                 if (n == 0)
 228                     break;
 229                 t->leftarr[curr] = empty;
 230             }
 231         }
 232
 233         if (t->leftarr[curr] == 0)
 234             t->leftarr[curr] = empty;
 235         else
 236             t->rightarr[curr] = empty;
 237
 238         parentarr[empty] = curr;
 239         curr = empty;
 240         empty++;
 241     }
 242
 243     /* unreachable */
 244     error("bad table");
 245     exit(1);
 246 }