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.4 2006/11/20 08:40:34 eggert 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 #define NPT (1 << TBIT)
  73
  74 /* local ush left[2 * NC - 1]; */
  75 /* local ush right[2 * NC - 1]; */
  76 #define left  prev
  77 #define right head
  78 #if NC > (1<<(BITS-2))
  79     error cannot overlay left+right and prev
  80 #endif
  81
  82 /* local uch c_len[NC]; */
  83 #define c_len outbuf
  84 #if NC > OUTBUFSIZ
  85     error cannot overlay c_len and outbuf
  86 #endif
  87
  88 local uch pt_len[NPT];
  89 local unsigned blocksize;
  90 local ush pt_table[256];
  91
  92 /* local ush c_table[4096]; */
  93 #define c_table d_buf
  94 #if (DIST_BUFSIZE-1) < 4095
  95     error cannot overlay c_table and d_buf
  96 #endif
  97
  98 /***********************************************************
  99         io.c -- input/output
 100 ***********************************************************/
 101
 102 local ush       bitbuf;
 103 local unsigned  subbitbuf;
 104 local int       bitcount;
 105
 106 local void fillbuf(n)  /* Shift bitbuf n bits left, read n bits */
 107     int n;
 108 {
 109     bitbuf <<= n;
 110     while (n > bitcount) {
 111         bitbuf |= subbitbuf << (n -= bitcount);
 112         subbitbuf = (unsigned)try_byte();
 113         if ((int)subbitbuf == EOF) subbitbuf = 0;
 114         bitcount = CHAR_BIT;
 115     }
 116     bitbuf |= subbitbuf >> (bitcount -= n);
 117 }
 118
 119 local unsigned getbits(n)
 120     int n;
 121 {
 122     unsigned x;
 123
 124     x = bitbuf >> (BITBUFSIZ - n);  fillbuf(n);
 125     return x;
 126 }
 127
 128 local void init_getbits()
 129 {
 130     bitbuf = 0;  subbitbuf = 0;  bitcount = 0;
 131     fillbuf(BITBUFSIZ);
 132 }
 133
 134 /***********************************************************
 135         maketbl.c -- make table for decoding
 136 ***********************************************************/
 137
 138 local void make_table(nchar, bitlen, tablebits, table)
 139     int nchar;
 140     uch bitlen[];
 141     int tablebits;
 142     ush table[];
 143 {
 144     ush count[17], weight[17], start[18], *p;
 145     unsigned i, k, len, ch, jutbits, avail, nextcode, mask;
 146
 147     for (i = 1; i <= 16; i++) count[i] = 0;
 148     for (i = 0; i < (unsigned)nchar; i++) count[bitlen[i]]++;
 149
 150     start[1] = 0;
 151     for (i = 1; i <= 16; i++)
 152         start[i + 1] = start[i] + (count[i] << (16 - i));
 153     if ((start[17] & 0xffff) != 0)
 154       gzip_error ("Bad table\n");
 155
 156     jutbits = 16 - tablebits;
 157     for (i = 1; i <= (unsigned)tablebits; i++) {
 158         start[i] >>= jutbits;
 159         weight[i] = (unsigned) 1 << (tablebits - i);
 160     }
 161     while (i <= 16) {
 162         weight[i] = (unsigned) 1 << (16 - i);
 163         i++;
 164     }
 165
 166     i = start[tablebits + 1] >> jutbits;
 167     if (i != 0) {
 168         k = 1 << tablebits;
 169         while (i != k) table[i++] = 0;
 170     }
 171
 172     avail = nchar;
 173     mask = (unsigned) 1 << (15 - tablebits);
 174     for (ch = 0; ch < (unsigned)nchar; ch++) {
 175         if ((len = bitlen[ch]) == 0) continue;
 176         nextcode = start[len] + weight[len];
 177         if (len <= (unsigned)tablebits) {
 178             if ((unsigned) 1 << tablebits < nextcode)
 179               gzip_error ("Bad table\n");
 180             for (i = start[len]; i < nextcode; i++) table[i] = ch;
 181         } else {
 182             k = start[len];
 183             p = &table[k >> jutbits];
 184             i = len - tablebits;
 185             while (i != 0) {
 186                 if (*p == 0) {
 187                     right[avail] = left[avail] = 0;
 188                     *p = avail++;
 189                 }
 190                 if (k & mask) p = &right[*p];
 191                 else          p = &left[*p];
 192                 k <<= 1;  i--;
 193             }
 194             *p = ch;
 195         }
 196         start[len] = nextcode;
 197     }
 198 }
 199
 200 /***********************************************************
 201         huf.c -- static Huffman
 202 ***********************************************************/
 203
 204 local void read_pt_len(nn, nbit, i_special)
 205     int nn;
 206     int nbit;
 207     int i_special;
 208 {
 209     int i, c, n;
 210     unsigned mask;
 211
 212     n = getbits(nbit);
 213     if (n == 0) {
 214         c = getbits(nbit);
 215         for (i = 0; i < nn; i++) pt_len[i] = 0;
 216         for (i = 0; i < 256; i++) pt_table[i] = c;
 217     } else {
 218         i = 0;
 219         while (i < n) {
 220             c = bitbuf >> (BITBUFSIZ - 3);
 221             if (c == 7) {
 222                 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 3);
 223                 while (mask & bitbuf) {  mask >>= 1;  c++;  }
 224                 if (16 < c)
 225                   gzip_error ("Bad table\n");
 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 }