workbench/devs/diskimage/dms/maketbl.c

   1 /*
   2  *     xDMS  v1.3  -  Portable DMS archive unpacker  -  Public Domain
   3  *     Written by     Andre Rodrigues de la Rocha  <adlroc@usa.net>
   4  *
   5  *     Makes decoding table for Heavy LZH decompression
   6  *     From  UNIX LHA made by Masaru Oki
   7  *
   8  */
   9
  10 #include "xdms.h"
  11
  12 struct mktbl_data {
  13         WORD c;
  14         UWORD n, tblsiz, len, depth, maxdepth, avail;
  15         UWORD codeword, bit, *tbl, TabErr;
  16         UBYTE *blen;
  17 };
  18
  19 static UWORD mktbl (struct xdms_data *xdms, struct mktbl_data *mt);
  20
  21 UWORD make_table (struct xdms_data *xdms, UWORD nchar, UBYTE bitlen[],UWORD tablebits, UWORD table[]) {
  22         struct mktbl_data mt_s, *mt = &mt_s;
  23         memset(mt, 0, sizeof(*mt));
  24         mt->n = mt->avail = nchar;
  25         mt->blen = bitlen;
  26         mt->tbl = table;
  27         mt->tblsiz = (UWORD)(1U << tablebits);
  28         mt->bit = (UWORD)(mt->tblsiz / 2);
  29         mt->maxdepth = (UWORD)(tablebits + 1);
  30         mt->depth = mt->len = 1;
  31         mt->c = -1;
  32         mt->codeword = 0;
  33         mt->TabErr = 0;
  34         mktbl(xdms, mt);        /* left subtree */
  35         if (mt->TabErr) return mt->TabErr;
  36         mktbl(xdms, mt);        /* right subtree */
  37         if (mt->TabErr) return mt->TabErr;
  38         if (mt->codeword != mt->tblsiz) return 5;
  39         return 0;
  40 }
  41
  42 static UWORD mktbl (struct xdms_data *xdms, struct mktbl_data *mt) {
  43         UWORD i = 0;
  44
  45         if (mt->TabErr) return 0;
  46
  47         if (mt->len == mt->depth) {
  48                 while (++mt->c < mt->n)
  49                         if (mt->blen[mt->c] == mt->len) {
  50                                 i = mt->codeword;
  51                                 mt->codeword += mt->bit;
  52                                 if (mt->codeword > mt->tblsiz) {
  53                                         mt->TabErr=1;
  54                                         return 0;
  55                                 }
  56                                 while (i < mt->codeword) mt->tbl[i++] = (UWORD)mt->c;
  57                                 return (UWORD)mt->c;
  58                         }
  59                 mt->c = -1;
  60                 mt->len++;
  61                 mt->bit >>= 1;
  62         }
  63         mt->depth++;
  64         if (mt->depth < mt->maxdepth) {
  65                 mktbl(xdms, mt);
  66                 mktbl(xdms, mt);
  67         } else if (mt->depth > 32) {
  68                 mt->TabErr = 2;
  69                 return 0;
  70         } else {
  71                 if ((i = mt->avail++) >= 2 * mt->n - 1) {
  72                         mt->TabErr = 3;
  73                         return 0;
  74                 }
  75                 xdms->u_heavy.left[i] = mktbl(xdms, mt);
  76                 xdms->u_heavy.right[i] = mktbl(xdms, mt);
  77                 if (mt->codeword >= mt->tblsiz) {
  78                         mt->TabErr = 4;
  79                         return 0;
  80                 }
  81                 if (mt->depth == mt->maxdepth) mt->tbl[mt->codeword++] = i;
  82         }
  83         mt->depth--;
  84         return i;
  85 }