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