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