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