workbench/devs/diskimage/dms/u_heavy.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-Huffman decompression functions used in Heavy 1 & 2
   6  *     compression modes. Based on LZH decompression functions from
   7  *     UNIX LHA made by Masaru Oki
   8  *
   9  */
  10
  11 #include "xdms.h"
  12
  13 #define NC 510
  14 #define NPT 20
  15 #define N1 510
  16 #define OFFSET 253
  17
  18 #if 0
  19 UWORD left[2 * NC - 1], right[2 * NC - 1 + 9];
  20 static UBYTE c_len[NC], pt_len[NPT];
  21 static UWORD c_table[4096], pt_table[256];
  22 static UWORD lastlen, np;
  23 #endif
  24
  25 static UWORD read_tree_c (struct xdms_data *xdms);
  26 static UWORD read_tree_p (struct xdms_data *xdms);
  27 static inline UWORD decode_c (struct xdms_data *xdms);
  28 static inline UWORD decode_p (struct xdms_data *xdms);
  29
  30 UWORD Unpack_HEAVY (struct xdms_data *xdms, UBYTE *in, UBYTE *out, UBYTE flags, UWORD origsize) {
  31         UWORD heavy_text_loc = xdms->heavy_text_loc;
  32         UBYTE *text = xdms->text;
  33         UWORD j, i, c, bitmask;
  34         UBYTE *outend;
  35
  36         /*  Heavy 1 uses a 4Kb dictionary,  Heavy 2 uses 8Kb  */
  37
  38         if (flags & 8) {
  39                 xdms->u_heavy.np = 15;
  40                 bitmask = 0x1fff;
  41         } else {
  42                 xdms->u_heavy.np = 14;
  43                 bitmask = 0x0fff;
  44         }
  45
  46         INITBITBUF(in);
  47
  48         if (flags & 2) {
  49                 if (read_tree_c(xdms)) return 1;
  50                 if (read_tree_p(xdms)) return 2;
  51         }
  52
  53         outend = out+origsize;
  54
  55         while (out<outend) {
  56                 c = decode_c(xdms);
  57                 if (c < 256) {
  58                         *out++ = text[heavy_text_loc++ & bitmask] = (UBYTE)c;
  59                 } else {
  60                         j = (UWORD)(c - OFFSET);
  61                         i = (UWORD)(heavy_text_loc - decode_p(xdms) - 1);
  62                         while(j--) *out++ = text[heavy_text_loc++ & bitmask] = text[i++ & bitmask];
  63                 }
  64         }
  65
  66         xdms->heavy_text_loc = heavy_text_loc;
  67
  68         return 0;
  69 }
  70
  71 static UWORD decode_c (struct xdms_data *xdms) {
  72         const UWORD * const left = xdms->u_heavy.left;
  73         const UWORD * const right = xdms->u_heavy.right;
  74         UWORD * const c_table = xdms->u_heavy.c_table;
  75         UBYTE * const c_len = xdms->u_heavy.c_len;
  76         UWORD i, j, m;
  77
  78         j = c_table[GETBITS(12)];
  79         if (j < N1) {
  80                 DROPBITS(c_len[j]);
  81         } else {
  82                 DROPBITS(12);
  83                 i = GETBITS(16);
  84                 m = 0x8000;
  85                 do {
  86                         if (i & m) j = right[j];
  87                         else j = left [j];
  88                         m >>= 1;
  89                 } while (j >= N1);
  90                 DROPBITS(c_len[j] - 12);
  91         }
  92         return j;
  93 }
  94
  95 static UWORD decode_p (struct xdms_data *xdms) {
  96         const UWORD * const left = xdms->u_heavy.left;
  97         const UWORD * const right = xdms->u_heavy.right;
  98         UWORD * const pt_table = xdms->u_heavy.pt_table;
  99         UBYTE * const pt_len = xdms->u_heavy.pt_len;
 100         const UWORD np = xdms->u_heavy.np;
 101         UWORD i, j, m;
 102
 103         j = pt_table[GETBITS(8)];
 104         if (j < np) {
 105                 DROPBITS(pt_len[j]);
 106         } else {
 107                 DROPBITS(8);
 108                 i = GETBITS(16);
 109                 m = 0x8000;
 110                 do {
 111                         if (i & m) j = right[j];
 112                         else j = left [j];
 113                         m >>= 1;
 114                 } while (j >= np);
 115                 DROPBITS(pt_len[j] - 8);
 116         }
 117
 118         if (j != np-1) {
 119                 if (j > 0) {
 120                         j = (UWORD)(GETBITS(i=(UWORD)(j-1)) | (1U << (j-1)));
 121                         DROPBITS(i);
 122                 }
 123                 xdms->u_heavy.lastlen=j;
 124         }
 125
 126         return xdms->u_heavy.lastlen;
 127
 128 }
 129
 130 static UWORD read_tree_c (struct xdms_data *xdms) {
 131         UWORD * const c_table = xdms->u_heavy.c_table;
 132         UBYTE * const c_len = xdms->u_heavy.c_len;
 133         UWORD i,n;
 134
 135         n = GETBITS(9);
 136         DROPBITS(9);
 137         if (n>0){
 138                 for (i=0; i<n; i++) {
 139                         c_len[i] = (UBYTE)GETBITS(5);
 140                         DROPBITS(5);
 141                 }
 142                 for (i=n; i<510; i++) c_len[i] = 0;
 143                 if (make_table(xdms,510,c_len,12,c_table)) return 1;
 144         } else {
 145                 n = GETBITS(9);
 146                 DROPBITS(9);
 147                 for (i=0; i<510; i++) c_len[i] = 0;
 148                 for (i=0; i<4096; i++) c_table[i] = n;
 149         }
 150         return 0;
 151 }
 152
 153 static UWORD read_tree_p (struct xdms_data *xdms) {
 154         UWORD * const pt_table = xdms->u_heavy.pt_table;
 155         UBYTE * const pt_len = xdms->u_heavy.pt_len;
 156         const UWORD np = xdms->u_heavy.np;
 157         UWORD i,n;
 158
 159         n = GETBITS(5);
 160         DROPBITS(5);
 161         if (n>0){
 162                 for (i=0; i<n; i++) {
 163                         pt_len[i] = (UBYTE)GETBITS(4);
 164                         DROPBITS(4);
 165                 }
 166                 for (i=n; i<np; i++) pt_len[i] = 0;
 167                 if (make_table(xdms,np,pt_len,8,pt_table)) return 1;
 168         } else {
 169                 n = GETBITS(5);
 170                 DROPBITS(5);
 171                 for (i=0; i<np; i++) pt_len[i] = 0;
 172                 for (i=0; i<256; i++) pt_table[i] = n;
 173         }
 174         return 0;
 175 }