unlzh.c

   1 /* unlzh.c -- decompress files in SCO compress -H (LZH) format.
   2  * The code in this file is directly derived from the public domain 'ar002'
   3  * written by Haruhiko Okumura.
   4  */
   5
   6 #include <config.h>
   7 #include <stdio.h>
   8
   9 #include "tailor.h"
  10 #include "gzip.h"
  11 #include "lzw.h" /* just for consistency checking */
  12
  13 /* decode.c */
  14
  15 static unsigned  decode (unsigned count, uch buffer[]);
  16 static void decode_start (void);
  17
  18 /* huf.c */
  19 static void huf_decode_start (void);
  20 static unsigned decode_c (void);
  21 static unsigned decode_p (void);
  22 static void read_pt_len (int nn, int nbit, int i_special);
  23 static void read_c_len (void);
  24
  25 /* io.c */
  26 static void fillbuf (int n);
  27 static unsigned getbits (int n);
  28 static void init_getbits (void);
  29
  30 /* maketbl.c */
  31
  32 static void make_table (int nchar, uch bitlen[], int tablebits, ush table[]);
  33
  34
  35 #define DICBIT    13    /* 12(-lh4-) or 13(-lh5-) */
  36 #define DICSIZ ((unsigned) 1 << DICBIT)
  37
  38 #ifndef CHAR_BIT
  39 #  define CHAR_BIT 8
  40 #endif
  41
  42 #ifndef UCHAR_MAX
  43 #  define UCHAR_MAX 255
  44 #endif
  45
  46 #define BITBUFSIZ (CHAR_BIT * 2 * sizeof(char))
  47 /* Do not use CHAR_BIT * sizeof(bitbuf), does not work on machines
  48  * for which short is not on 16 bits (Cray).
  49  */
  50
  51 /* encode.c and decode.c */
  52
  53 #define MAXMATCH 256    /* formerly F (not more than UCHAR_MAX + 1) */
  54 #define THRESHOLD  3    /* choose optimal value */
  55
  56 /* huf.c */
  57
  58 #define NC (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD)
  59         /* alphabet = {0, 1, 2, ..., NC - 1} */
  60 #define CBIT 9  /* $\lfloor \log_2 NC \rfloor + 1$ */
  61 #define CODE_BIT  16  /* codeword length */
  62
  63 #define NP (DICBIT + 1)
  64 #define NT (CODE_BIT + 3)
  65 #define PBIT 4  /* smallest integer such that (1U << PBIT) > NP */
  66 #define TBIT 5  /* smallest integer such that (1U << TBIT) > NT */
  67 #define NPT (1 << TBIT)
  68
  69 /* static ush left[2 * NC - 1]; */
  70 /* static ush right[2 * NC - 1]; */
  71 #define left  prev
  72 #define right head
  73 #if NC > (1<<(BITS-2))
  74     error cannot overlay left+right and prev
  75 #endif
  76
  77 /* static uch c_len[NC]; */
  78 #define c_len outbuf
  79 #if NC > OUTBUFSIZ
  80     error cannot overlay c_len and outbuf
  81 #endif
  82
  83 static uch pt_len[NPT];
  84 static unsigned blocksize;
  85 static ush pt_table[256];
  86
  87 /* static ush c_table[4096]; */
  88 #define c_table d_buf
  89 #if (DIST_BUFSIZE-1) < 4095
  90     error cannot overlay c_table and d_buf
  91 #endif
  92
  93 /***********************************************************
  94         io.c -- input/output
  95 ***********************************************************/
  96
  97 static ush       bitbuf;
  98 static unsigned  subbitbuf;
  99 static int       bitcount;
 100
 101 /* Shift bitbuf N bits left, read N bits.  */
 102 static void
 103 fillbuf (int n)
 104 {
 105     bitbuf <<= n;
 106     while (n > bitcount) {
 107         bitbuf |= subbitbuf << (n -= bitcount);
 108         subbitbuf = (unsigned)try_byte();
 109         if ((int)subbitbuf == EOF) subbitbuf = 0;
 110         bitcount = CHAR_BIT;
 111     }
 112     bitbuf |= subbitbuf >> (bitcount -= n);
 113 }
 114
 115 static unsigned
 116 getbits (int n)
 117 {
 118     unsigned x;
 119
 120     x = bitbuf >> (BITBUFSIZ - n);  fillbuf(n);
 121     return x;
 122 }
 123
 124 static void
 125 init_getbits ()
 126 {
 127     bitbuf = 0;  subbitbuf = 0;  bitcount = 0;
 128     fillbuf(BITBUFSIZ);
 129 }
 130
 131 /***********************************************************
 132         maketbl.c -- make table for decoding
 133 ***********************************************************/
 134
 135 static void
 136 make_table (int nchar, uch bitlen[], int tablebits, ush table[])
 137 {
 138     ush count[17], weight[17], start[18], *p;
 139     unsigned i, k, len, ch, jutbits, avail, nextcode, mask;
 140
 141     for (i = 1; i <= 16; i++) count[i] = 0;
 142     for (i = 0; i < (unsigned)nchar; i++) count[bitlen[i]]++;
 143
 144     start[1] = 0;
 145     for (i = 1; i <= 16; i++)
 146         start[i + 1] = start[i] + (count[i] << (16 - i));
 147     if ((start[17] & 0xffff) != 0)
 148       gzip_error ("Bad table\n");
 149
 150     jutbits = 16 - tablebits;
 151     for (i = 1; i <= (unsigned)tablebits; i++) {
 152         start[i] >>= jutbits;
 153         weight[i] = (unsigned) 1 << (tablebits - i);
 154     }
 155     while (i <= 16) {
 156         weight[i] = (unsigned) 1 << (16 - i);
 157         i++;
 158     }
 159
 160     i = start[tablebits + 1] >> jutbits;
 161     if (i != 0) {
 162         k = 1 << tablebits;
 163         while (i != k) table[i++] = 0;
 164     }
 165
 166     avail = nchar;
 167     mask = (unsigned) 1 << (15 - tablebits);
 168     for (ch = 0; ch < (unsigned)nchar; ch++) {
 169         if ((len = bitlen[ch]) == 0) continue;
 170         nextcode = start[len] + weight[len];
 171         if (len <= (unsigned)tablebits) {
 172             if ((unsigned) 1 << tablebits < nextcode)
 173               gzip_error ("Bad table\n");
 174             for (i = start[len]; i < nextcode; i++) table[i] = ch;
 175         } else {
 176             k = start[len];
 177             p = &table[k >> jutbits];
 178             i = len - tablebits;
 179             while (i != 0) {
 180                 if (*p == 0) {
 181                     right[avail] = left[avail] = 0;
 182                     *p = avail++;
 183                 }
 184                 if (k & mask) p = &right[*p];
 185                 else          p = &left[*p];
 186                 k <<= 1;  i--;
 187             }
 188             *p = ch;
 189         }
 190         start[len] = nextcode;
 191     }
 192 }
 193
 194 /***********************************************************
 195         huf.c -- static Huffman
 196 ***********************************************************/
 197
 198 static void
 199 read_pt_len (int nn, int nbit, int i_special)
 200 {
 201     int i, c, n;
 202     unsigned mask;
 203
 204     n = getbits(nbit);
 205     if (n == 0) {
 206         c = getbits(nbit);
 207         for (i = 0; i < nn; i++) pt_len[i] = 0;
 208         for (i = 0; i < 256; i++) pt_table[i] = c;
 209     } else {
 210         i = 0;
 211         while (i < n) {
 212             c = bitbuf >> (BITBUFSIZ - 3);
 213             if (c == 7) {
 214                 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 3);
 215                 while (mask & bitbuf) {  mask >>= 1;  c++;  }
 216                 if (16 < c)
 217                   gzip_error ("Bad table\n");
 218             }
 219             fillbuf((c < 7) ? 3 : c - 3);
 220             pt_len[i++] = c;
 221             if (i == i_special) {
 222                 c = getbits(2);
 223                 while (--c >= 0) pt_len[i++] = 0;
 224             }
 225         }
 226         while (i < nn) pt_len[i++] = 0;
 227         make_table(nn, pt_len, 8, pt_table);
 228     }
 229 }
 230
 231 static void
 232 read_c_len ()
 233 {
 234     int i, c, n;
 235     unsigned mask;
 236
 237     n = getbits(CBIT);
 238     if (n == 0) {
 239         c = getbits(CBIT);
 240         for (i = 0; i < NC; i++) c_len[i] = 0;
 241         for (i = 0; i < 4096; i++) c_table[i] = c;
 242     } else {
 243         i = 0;
 244         while (i < n) {
 245             c = pt_table[bitbuf >> (BITBUFSIZ - 8)];
 246             if (c >= NT) {
 247                 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
 248                 do {
 249                     if (bitbuf & mask) c = right[c];
 250                     else               c = left [c];
 251                     mask >>= 1;
 252                 } while (c >= NT);
 253             }
 254             fillbuf((int) pt_len[c]);
 255             if (c <= 2) {
 256                 if      (c == 0) c = 1;
 257                 else if (c == 1) c = getbits(4) + 3;
 258                 else             c = getbits(CBIT) + 20;
 259                 while (--c >= 0) c_len[i++] = 0;
 260             } else c_len[i++] = c - 2;
 261         }
 262         while (i < NC) c_len[i++] = 0;
 263         make_table(NC, c_len, 12, c_table);
 264     }
 265 }
 266
 267 static unsigned
 268 decode_c ()
 269 {
 270     unsigned j, mask;
 271
 272     if (blocksize == 0) {
 273         blocksize = getbits(16);
 274         if (blocksize == 0) {
 275             return NC; /* end of file */
 276         }
 277         read_pt_len(NT, TBIT, 3);
 278         read_c_len();
 279         read_pt_len(NP, PBIT, -1);
 280     }
 281     blocksize--;
 282     j = c_table[bitbuf >> (BITBUFSIZ - 12)];
 283     if (j >= NC) {
 284         mask = (unsigned) 1 << (BITBUFSIZ - 1 - 12);
 285         do {
 286             if (bitbuf & mask) j = right[j];
 287             else               j = left [j];
 288             mask >>= 1;
 289         } while (j >= NC);
 290     }
 291     fillbuf((int) c_len[j]);
 292     return j;
 293 }
 294
 295 static unsigned
 296 decode_p ()
 297 {
 298     unsigned j, mask;
 299
 300     j = pt_table[bitbuf >> (BITBUFSIZ - 8)];
 301     if (j >= NP) {
 302         mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
 303         do {
 304             if (bitbuf & mask) j = right[j];
 305             else               j = left [j];
 306             mask >>= 1;
 307         } while (j >= NP);
 308     }
 309     fillbuf((int) pt_len[j]);
 310     if (j != 0) j = ((unsigned) 1 << (j - 1)) + getbits((int) (j - 1));
 311     return j;
 312 }
 313
 314 static void
 315 huf_decode_start ()
 316 {
 317     init_getbits();  blocksize = 0;
 318 }
 319
 320 /***********************************************************
 321         decode.c
 322 ***********************************************************/
 323
 324 static int j;    /* remaining bytes to copy */
 325 static int done; /* set at end of input */
 326
 327 static void
 328 decode_start ()
 329 {
 330     huf_decode_start();
 331     j = 0;
 332     done = 0;
 333 }
 334
 335 /* Decode the input and return the number of decoded bytes put in buffer
 336  */
 337 static unsigned
 338 decode (unsigned count, uch buffer[])
 339     /* The calling function must keep the number of
 340        bytes to be processed.  This function decodes
 341        either 'count' bytes or 'DICSIZ' bytes, whichever
 342        is smaller, into the array 'buffer[]' of size
 343        'DICSIZ' or more.
 344        Call decode_start() once for each new file
 345        before calling this function.
 346      */
 347 {
 348     static unsigned i;
 349     unsigned r, c;
 350
 351     r = 0;
 352     while (--j >= 0) {
 353         buffer[r] = buffer[i];
 354         i = (i + 1) & (DICSIZ - 1);
 355         if (++r == count) return r;
 356     }
 357     for ( ; ; ) {
 358         c = decode_c();
 359         if (c == NC) {
 360             done = 1;
 361             return r;
 362         }
 363         if (c <= UCHAR_MAX) {
 364             buffer[r] = c;
 365             if (++r == count) return r;
 366         } else {
 367             j = c - (UCHAR_MAX + 1 - THRESHOLD);
 368             i = (r - decode_p() - 1) & (DICSIZ - 1);
 369             while (--j >= 0) {
 370                 buffer[r] = buffer[i];
 371                 i = (i + 1) & (DICSIZ - 1);
 372                 if (++r == count) return r;
 373             }
 374         }
 375     }
 376 }
 377
 378
 379 /* ===========================================================================
 380  * Unlzh in to out. Return OK or ERROR.
 381  */
 382 int
 383 unlzh (int in, int out)
 384 {
 385     unsigned n;
 386     ifd = in;
 387     ofd = out;
 388
 389     decode_start();
 390     while (!done) {
 391         n = decode((unsigned) DICSIZ, window);
 392         if (n > 0)
 393           write_buf (out, window, n);
 394     }
 395     return OK;
 396 }