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