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