workbench/devs/diskimage/dms/u_deep.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  *     Lempel-Ziv-DynamicHuffman decompression functions used in Deep
   6  *     mode.
   7  *     Most routines ripped from LZHUF written by  Haruyasu Yoshizaki
   8  *
   9  */
  10
  11 #include "xdms.h"
  12
  13 static UWORD DecodeChar (struct xdms_data *xdms);
  14 static UWORD DecodePosition (struct xdms_data *xdms);
  15 static void update (struct xdms_data *xdms, UWORD c);
  16 static void reconst (struct xdms_data *xdms);
  17
  18 #define DBITMASK 0x3fff   /*  uses 16Kb dictionary  */
  19
  20 #define F 60 /* lookahead buffer size */
  21 #define THRESHOLD 2
  22 #define N_CHAR (256 - THRESHOLD + F) /* kinds of characters (character code = 0..N_CHAR-1) */
  23 #define T (N_CHAR * 2 - 1) /* size of table */
  24 #define R (T - 1) /* position of root */
  25 #define MAX_FREQ 0x8000 /* updates tree when the */
  26
  27 #if 0
  28 UWORD freq[T + 1]; /* frequency table */
  29
  30 UWORD prnt[T + N_CHAR]; /* pointers to parent nodes, except for the */
  31                                 /* elements [T..T + N_CHAR - 1] which are used to get */
  32                                 /* the positions of leaves corresponding to the codes. */
  33
  34 UWORD son[T];   /* pointers to child nodes (son[], son[] + 1) */
  35 #endif
  36
  37 static void Init_DEEP_Tabs (struct xdms_data *xdms) {
  38         UWORD * const freq = xdms->u_deep.freq;
  39         UWORD * const prnt = xdms->u_deep.prnt;
  40         UWORD * const son = xdms->u_deep.son;
  41         UWORD i, j;
  42
  43         for (i = 0; i < N_CHAR; i++) {
  44                 freq[i] = 1;
  45                 son[i] = (UWORD)(i + T);
  46                 prnt[i + T] = i;
  47         }
  48         i = 0; j = N_CHAR;
  49         while (j <= R) {
  50                 freq[j] = (UWORD)(freq[i] + freq[i + 1]);
  51                 son[j] = i;
  52                 prnt[i] = prnt[i + 1] = j;
  53                 i += 2; j++;
  54         }
  55         freq[T] = 0xffff;
  56         prnt[R] = 0;
  57
  58         xdms->init_deep_tabs = 0;
  59 }
  60
  61 UWORD Unpack_DEEP (struct xdms_data *xdms, UBYTE *in, UBYTE *out, UWORD origsize) {
  62         UWORD deep_text_loc = xdms->deep_text_loc;
  63         UBYTE *text = xdms->text;
  64         UWORD i, j, c;
  65         UBYTE *outend;
  66
  67         INITBITBUF(in);
  68
  69         if (xdms->init_deep_tabs) Init_DEEP_Tabs(xdms);
  70
  71         outend = out+origsize;
  72         while (out < outend) {
  73                 c = DecodeChar(xdms);
  74                 if (c < 256) {
  75                         *out++ = text[deep_text_loc++ & DBITMASK] = (UBYTE)c;
  76                 } else {
  77                         j = (UWORD)(c - 255 + THRESHOLD);
  78                         i = (UWORD)(deep_text_loc - DecodePosition(xdms) - 1);
  79                         while (j--) *out++ = text[deep_text_loc++ & DBITMASK] = text[i++ & DBITMASK];
  80                 }
  81         }
  82
  83         xdms->deep_text_loc = (UWORD)((deep_text_loc+60) & DBITMASK);
  84
  85         return 0;
  86 }
  87
  88 static UWORD DecodeChar (struct xdms_data *xdms) {
  89         UWORD * const son = xdms->u_deep.son;
  90         UWORD c;
  91
  92         c = son[R];
  93
  94         /* travel from root to leaf, */
  95         /* choosing the smaller child node (son[]) if the read bit is 0, */
  96         /* the bigger (son[]+1} if 1 */
  97         while (c < T) {
  98                 c = son[c + GETBITS(1)];
  99                 DROPBITS(1);
 100         }
 101         c -= T;
 102         update(xdms, c);
 103
 104         return c;
 105 }
 106
 107 static UWORD DecodePosition (struct xdms_data *xdms) {
 108         UWORD i, j, c;
 109
 110         i = GETBITS(8);  DROPBITS(8);
 111         c = (UWORD)(d_code[i] << 8);
 112         j = d_len[i];
 113         i = (UWORD)(((i << j) | GETBITS(j)) & 0xff);  DROPBITS(j);
 114
 115         return (UWORD)(c | i);
 116 }
 117
 118 /* reconstruction of tree */
 119
 120 static void reconst (struct xdms_data *xdms) {
 121         UWORD * const freq = xdms->u_deep.freq;
 122         UWORD * const prnt = xdms->u_deep.prnt;
 123         UWORD * const son = xdms->u_deep.son;
 124         UWORD i, j, k, f, l;
 125
 126         /* collect leaf nodes in the first half of the table */
 127         /* and replace the freq by (freq + 1) / 2. */
 128         j = 0;
 129         for (i = 0; i < T; i++) {
 130                 if (son[i] >= T) {
 131                         freq[j] = (UWORD)((freq[i] + 1) / 2);
 132                         son[j] = son[i];
 133                         j++;
 134                 }
 135         }
 136         /* begin constructing tree by connecting sons */
 137         for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
 138                 k = (UWORD)(i + 1);
 139                 f = freq[j] = (UWORD)(freq[i] + freq[k]);
 140                 for (k = (UWORD)(j - 1); f < freq[k]; k--);
 141                 k++;
 142                 l = (UWORD)((j - k) * 2);
 143                 memmove(&freq[k + 1], &freq[k], (size_t)l);
 144                 freq[k] = f;
 145                 memmove(&son[k + 1], &son[k], (size_t)l);
 146                 son[k] = i;
 147         }
 148         /* connect prnt */
 149         for (i = 0; i < T; i++) {
 150                 if ((k = son[i]) >= T) {
 151                         prnt[k] = i;
 152                 } else {
 153                         prnt[k] = prnt[k + 1] = i;
 154                 }
 155         }
 156 }
 157
 158 /* increment frequency of given code by one, and update tree */
 159
 160 static void update (struct xdms_data *xdms, UWORD c){
 161         UWORD * const freq = xdms->u_deep.freq;
 162         UWORD * const prnt = xdms->u_deep.prnt;
 163         UWORD * const son = xdms->u_deep.son;
 164         UWORD i, j, k, l;
 165
 166         if (freq[R] == MAX_FREQ) {
 167                 reconst(xdms);
 168         }
 169         c = prnt[c + T];
 170         do {
 171                 k = ++freq[c];
 172
 173                 /* if the order is disturbed, exchange nodes */
 174                 if (k > freq[l = (UWORD)(c + 1)]) {
 175                         while (k > freq[++l]);
 176                         l--;
 177                         freq[c] = freq[l];
 178                         freq[l] = k;
 179
 180                         i = son[c];
 181                         prnt[i] = l;
 182                         if (i < T) prnt[i + 1] = l;
 183
 184                         j = son[l];
 185                         son[l] = i;
 186
 187                         prnt[j] = c;
 188                         if (j < T) prnt[j + 1] = c;
 189                         son[c] = j;
 190
 191                         c = l;
 192                 }
 193         } while ((c = prnt[c]) != 0); /* repeat up to root */
 194 }