unlzw.c

   1 /* unlzw.c -- decompress files in LZW format.
   2  * The code in this file is directly derived from the public domain 'compress'
   3  * written by Spencer Thomas, Joe Orost, James Woods, Jim McKie, Steve Davies,
   4  * Ken Turkowski, Dave Mack and Peter Jannesen.
   5  *
   6  * This is a temporary version which will be rewritten in some future version
   7  * to accommodate in-memory decompression.
   8  *
   9  * Tue Dec 12 17:54:07 CET 2006 - werner@suse.de
  10  * Be able to emulate a zlib-like behaviour: open, read, and close .Z files
  11  * in memory. I'm using context switchting and a global allocated structure
  12  * to be able to read during the main loop in unlzw() does its work. For this
  13  * nearly _all_ variables affected by the context switch are forward to this
  14  * structure, even the stack and the context type its self.
  15  * The original source was adopted from the gzip version 1.3.7.
  16  */
  17
  18 #include <stdlib.h>
  19 #include <stdint.h>
  20 #include <stdio.h>
  21 #include <string.h>
  22 #include <unistd.h>
  23 #include <fcntl.h>
  24 #include <errno.h>
  25
  26 #define DIST_BUFSIZE    0x2000
  27 #define INBUFSIZ        0x2000
  28 #define WSIZE           0x2000
  29 #define INBUF_EXTRA     0x40
  30 #define OUTBUFSIZ       0x2000
  31 #define OUTBUF_EXTRA    0x800
  32 #define STACK_SIZE      0x1000
  33
  34 #include "lzw.h"
  35
  36 static void unlzw(LZW_t *in);
  37
  38 /* ===========================================================================
  39  * Fill the input buffer. This is called only when the buffer is empty.
  40  * Adopted from gzip version 1.3.7 util.c
  41  */
  42 __extension__
  43 static __inline__ int fill_inbuf(LZW_t *in)
  44 {
  45     /* Read as much as possible */
  46     in->insize = 0;
  47     do {
  48         ssize_t len = read(in->ifd, in->inbuf + in->insize, INBUFSIZ - in->insize);
  49         if (len < 0) {
  50             if (errno == EINTR)
  51                 continue;
  52             perror(__FUNCTION__);
  53             break;
  54         }
  55         if (len == 0)
  56             break;
  57         in->insize += len;
  58     } while (in->insize < INBUFSIZ);
  59
  60     if (in->insize == 0)
  61         return EOF;
  62
  63     in->bytes_in += (off_t)in->insize;
  64     in->inptr = 1;
  65     return (in->inbuf)[0];
  66 }
  67
  68 /* ===========================================================================
  69  * Does the same as write(), but also handles partial pipe writes and checks
  70  * for error return.
  71  * Adopted from gzip version 1.3.7 util.c
  72  * Note that this version uses context switching, switch back to old context.
  73  */
  74 __extension__
  75 static __inline__ void write_buf(LZW_t *in, const unsigned char* buf, size_t cnt)
  76 {
  77     do {
  78         if ((in->tsize = (in->tcount > cnt) ? cnt : in->tcount)) {
  79             (void)memcpy(in->transfer, buf, in->tsize);
  80             buf += in->tsize;
  81             cnt -= in->tsize;
  82         }
  83         swapcontext(&in->uc[1], &in->uc[0]);
  84     } while (cnt);
  85 }
  86
  87 #define get_byte(in)    ((in)->inptr < (in)->insize ? (in)->inbuf[(in)->inptr++] : fill_inbuf((in)))
  88 #define memzero(s,n)    memset ((void*)(s), 0, (n))
  89
  90 #define MAXCODE(n)      (1L << (n))
  91
  92 #ifndef BYTEORDER
  93 #       define  BYTEORDER       0000
  94 #endif
  95
  96 #ifndef NOALLIGN
  97 #       define  NOALLIGN        0
  98 #endif
  99
 100
 101 union   bytes {
 102     long  word;
 103     struct {
 104 #if BYTEORDER == 4321
 105         uint8_t b1;
 106         uint8_t b2;
 107         uint8_t b3;
 108         uint8_t b4;
 109 #else
 110 #if BYTEORDER == 1234
 111         uint8_t b4;
 112         uint8_t b3;
 113         uint8_t b2;
 114         uint8_t b1;
 115 #else
 116 #       undef   BYTEORDER
 117         int  dummy;
 118 #endif
 119 #endif
 120     } bytes;
 121 };
 122
 123 #if BYTEORDER == 4321 && NOALLIGN == 1
 124 #  define input(b,o,c,n,m){ \
 125      (c) = (*(uint32_t *)(&(b)[(o)>>3])>>((o)&0x7))&(m); \
 126      (o) += (n); \
 127    }
 128 #else
 129 #  define input(b,o,c,n,m){ \
 130      uint8_t *p = &(b)[(o)>>3]; \
 131      (c) = ((((long)(p[0]))|((long)(p[1])<<8)| \
 132      ((long)(p[2])<<16))>>((o)&0x7))&(m); \
 133      (o) += (n); \
 134    }
 135 #endif
 136
 137 #define tab_prefixof(i)         in->tab_prefix[i]
 138 #define clear_tab_prefixof(in)  memzero((in)->tab_prefix, sizeof(unsigned short)*(1<<(BITS)));
 139 #define de_stack                ((uint8_t *)(&in->d_buf[DIST_BUFSIZE-1]))
 140 #define tab_suffixof(i)         in->tab_suffix[i]
 141
 142 /* ============================================================================
 143  * Decompress in to out.  This routine adapts to the codes in the
 144  * file building the "string" table on-the-fly; requiring no table to
 145  * be stored in the compressed file.
 146  * IN assertions: the buffer inbuf contains already the beginning of
 147  *   the compressed data, from offsets iptr to insize-1 included.
 148  *   The magic header has already been checked and skipped.
 149  *   bytes_in and bytes_out have been initialized.
 150  *
 151  * Adopted from gzip version 1.3.7 unlzw.c
 152  * This is mainly the head of the old unlzw() before its main loop.
 153  */
 154 LZW_t *openlzw(const char * path, const char *mode)
 155 {
 156     int fildes;
 157     if (!mode || *mode != 'r')
 158         goto out;
 159     if ((fildes = open(path, O_RDONLY)) < 0)
 160         goto out;
 161     return dopenlzw(fildes, mode);
 162 out:
 163     return (LZW_t*)0;
 164 }
 165
 166 LZW_t *dopenlzw(int fildes, const char *mode)
 167 {
 168     LZW_t *in = (LZW_t*)0;
 169     uint8_t magic[2];
 170     sigset_t sigmask, oldmask;
 171
 172     if (!mode || *mode != 'r')
 173         goto out;
 174
 175     if ((in = (LZW_t*)malloc(sizeof(LZW_t))) == (LZW_t*)0)
 176         goto err;
 177     memset(in, 0, sizeof(LZW_t));
 178
 179     if ((in->inbuf = (uint8_t*)malloc(sizeof(uint8_t)*(INBUFSIZ))) == (uint8_t*)0)
 180         goto err;
 181     if ((in->outbuf = (uint8_t*)malloc(sizeof(uint8_t)*(OUTBUFSIZ+OUTBUF_EXTRA))) == (uint8_t*)0)
 182         goto err;
 183     if ((in->d_buf = (uint16_t*)malloc(sizeof(uint16_t)*DIST_BUFSIZE)) == (uint16_t*)0)
 184         goto err;
 185     if ((in->tab_suffix = (uint8_t*) malloc(sizeof(uint8_t )*(2L*WSIZE))) == (uint8_t*)0)
 186         goto err;
 187     if ((in->tab_prefix = (uint16_t*)malloc(sizeof(uint16_t)*(1<<(BITS)))) == (uint16_t*)0)
 188         goto err;
 189     if ((in->ifd = fildes) < 0)
 190         goto err;
 191
 192     if ((in->stack = (uint8_t*)malloc(STACK_SIZE)) == (uint8_t*)0)
 193         goto err;
 194     if ((in->uc = (ucontext_t*)malloc(2*sizeof(ucontext_t))) == (ucontext_t*)0)
 195         goto err;
 196     if (getcontext(&in->uc[1]) < 0)
 197         goto err;
 198     in->uc[1].uc_link = &in->uc[0];
 199     in->uc[1].uc_stack.ss_sp = in->stack;
 200     in->uc[1].uc_stack.ss_size = STACK_SIZE;
 201     if (sigucmask(SIG_SETMASK, (sigset_t*)0, &sigmask) < 0)
 202         goto err;
 203     if (sigaddset(&sigmask, SIGINT) < 0)
 204         goto err;
 205     if (sigaddset(&sigmask, SIGQUIT) < 0)
 206         goto err;
 207 #if defined(__ia64__) && defined(uc_sigmask)    /* On ia64 the type of uc_sigmask is ulong not sigset_t */
 208     in->uc[1].uc_sigmask = sig_ia64_mask(sigmask);
 209 #else
 210     in->uc[1].uc_sigmask = sigmask;
 211 #endif
 212     makecontext(&in->uc[1], (void(*)(void))unlzw, 1, in);
 213
 214     sigucmask(SIG_SETMASK, &sigmask, &oldmask);
 215     magic[0] = get_byte(in);
 216     magic[1] = get_byte(in);
 217     sigucmask(SIG_SETMASK, &oldmask, &sigmask);
 218
 219     if (memcmp(magic, LZW_MAGIC, sizeof(magic)))
 220         goto err;
 221
 222     in->n.block_mode = BLOCK_MODE;  /* block compress mode -C compatible with 2.0 */
 223     in->rsize = in->insize;
 224
 225     in->n.maxbits = get_byte(in);
 226     in->n.block_mode = in->n.maxbits & BLOCK_MODE;
 227
 228     if ((in->n.maxbits & LZW_RESERVED) != 0) {
 229         fprintf(stderr, "%s: warning, unknown flags 0x%x\n",
 230                 __FUNCTION__, in->n.maxbits & LZW_RESERVED);
 231     }
 232     in->n.maxbits &= BIT_MASK;
 233     in->n.maxmaxcode = MAXCODE(in->n.maxbits);
 234
 235     if (in->n.maxbits > BITS) {
 236         fprintf(stderr, "%s: compressed with %d bits, can only handle %d bits\n",
 237                 __FUNCTION__, in->n.maxbits, BITS);
 238         goto err;
 239     }
 240
 241     in->n.maxcode = MAXCODE(in->n.n_bits = INIT_BITS)-1;
 242     in->n.bitmask = (1<<in->n.n_bits)-1;
 243     in->n.oldcode = -1;
 244     in->n.finchar = 0;
 245     in->n.posbits = in->inptr<<3;
 246
 247     in->n.free_ent = ((in->n.block_mode) ? FIRST : 256);
 248
 249     clear_tab_prefixof(in);     /* Initialize the first 256 entries in the table. */
 250
 251     for (in->n.code = 255 ; in->n.code >= 0 ; --in->n.code) {
 252         tab_suffixof(in->n.code) = (uint8_t)in->n.code;
 253     }
 254 out:
 255     return in;
 256 err:
 257     closelzw(in);
 258     return (LZW_t*)0;
 259 }
 260
 261 /*
 262  * New function, simply to free all allocated objects in
 263  * reverse order and close the input file.
 264  */
 265 void closelzw(LZW_t * in)
 266 {
 267     if (in == (LZW_t*)0)
 268         return;
 269     if (in->uc) free(in->uc);
 270     if (in->stack) free(in->stack);
 271     if (in->ifd >= 0) close(in->ifd);
 272     if (in->tab_prefix) free(in->tab_prefix);
 273     if (in->tab_suffix) free(in->tab_suffix);
 274     if (in->d_buf)  free(in->d_buf);
 275     if (in->outbuf) free(in->outbuf);
 276     if (in->inbuf)  free(in->inbuf);
 277     free(in);
 278     in = (LZW_t*)0;
 279 }
 280
 281 /*
 282  * Adopted from gzip version 1.3.7 unlzw.c
 283  * This is mainly the body of the old unlzw() which is its main loop.
 284  */
 285 static void unlzw(LZW_t *in)
 286 {
 287     do {
 288         int i;
 289         int e;
 290         int o;
 291
 292     resetbuf:
 293         e = in->insize - (o = (in->n.posbits>>3));
 294
 295         for (i = 0 ; i < e ; ++i) {
 296             in->inbuf[i] = in->inbuf[i+o];
 297         }
 298         in->insize = e;
 299         in->n.posbits = 0;
 300
 301         if (in->insize < INBUF_EXTRA) {
 302             do {
 303                 in->rsize = read(in->ifd, in->inbuf + in->insize, INBUFSIZ - in->insize);
 304                 if (in->rsize < 0) {
 305                     if (errno == EINTR)
 306                         continue;
 307                     perror(__FUNCTION__);
 308                     break;
 309                 }
 310                 if (in->rsize == 0)
 311                     break;
 312                 in->insize += in->rsize;
 313             } while (in->insize < INBUFSIZ);
 314             in->bytes_in += (off_t)in->insize;
 315         }
 316         in->n.inbits = ((in->rsize != 0) ? ((long)in->insize - in->insize%in->n.n_bits)<<3 :
 317                         ((long)in->insize<<3)-(in->n.n_bits-1));
 318
 319         while (in->n.inbits > in->n.posbits) {
 320             if (in->n.free_ent > in->n.maxcode) {
 321                 in->n.posbits = ((in->n.posbits-1) +
 322                            ((in->n.n_bits<<3)-(in->n.posbits-1+(in->n.n_bits<<3))%(in->n.n_bits<<3)));
 323                 ++in->n.n_bits;
 324                 if (in->n.n_bits == in->n.maxbits) {
 325                     in->n.maxcode = in->n.maxmaxcode;
 326                 } else {
 327                     in->n.maxcode = MAXCODE(in->n.n_bits)-1;
 328                 }
 329                 in->n.bitmask = (1<<in->n.n_bits)-1;
 330                 goto resetbuf;
 331             }
 332             input(in->inbuf,in->n.posbits,in->n.code,in->n.n_bits,in->n.bitmask);
 333
 334             if (in->n.oldcode == -1) {
 335                 if (256 <= in->n.code)
 336                     fprintf(stderr, "%s: corrupt input.\n", __FUNCTION__);
 337                 in->outbuf[in->outpos++] = (uint8_t)(in->n.finchar = (int)(in->n.oldcode=in->n.code));
 338                 continue;
 339             }
 340             if (in->n.code == CLEAR && in->n.block_mode) {
 341                 clear_tab_prefixof(in);
 342                 in->n.free_ent = FIRST - 1;
 343                 in->n.posbits = ((in->n.posbits-1) +
 344                            ((in->n.n_bits<<3)-(in->n.posbits-1+(in->n.n_bits<<3))%(in->n.n_bits<<3)));
 345                 in->n.maxcode = MAXCODE(in->n.n_bits = INIT_BITS)-1;
 346                 in->n.bitmask = (1<<in->n.n_bits)-1;
 347                 goto resetbuf;
 348             }
 349             in->n.incode = in->n.code;
 350             in->n.stackp = de_stack;
 351
 352             if (in->n.code >= in->n.free_ent) { /* Special case for KwKwK string. */
 353                 if (in->n.code > in->n.free_ent) {
 354 #ifdef DEBUG
 355                     uint8_t *p;
 356                     in->n.posbits -= in->n.n_bits;
 357                     p = &in->inbuf[in->n.posbits>>3];
 358                     fprintf(stderr,
 359                             "code:%ld free_ent:%ld n_bits:%d insize:%lu\n",
 360                             in->n.code, in->n.free_ent, in->n.n_bits, in->insize);
 361                     fprintf(stderr,
 362                             "posbits:%ld inbuf:%02X %02X %02X %02X %02X\n",
 363                             in->n.posbits, p[-1],p[0],p[1],p[2],p[3]);
 364 #endif
 365                     if (in->outpos > 0) {
 366                         write_buf(in, in->outbuf, in->outpos);
 367                         in->bytes_out += (off_t)in->outpos;
 368                         in->outpos = 0;
 369                     }
 370                     fprintf(stderr, "%s: corrupt input.\n", __FUNCTION__);
 371                 }
 372                 *--in->n.stackp = (uint8_t)in->n.finchar;
 373                 in->n.code = in->n.oldcode;
 374             }
 375
 376             /* Generate output characters in reverse order */
 377             while ((uint32_t)in->n.code >= (uint32_t)256) {
 378                 *--in->n.stackp = tab_suffixof(in->n.code);
 379                 in->n.code = tab_prefixof(in->n.code);
 380             }
 381             *--in->n.stackp =   (uint8_t)(in->n.finchar = tab_suffixof(in->n.code));
 382
 383             /* And put them out in forward order */
 384             if (in->outpos + (in->n.newdif = (de_stack - in->n.stackp)) >= OUTBUFSIZ) {
 385                 do {
 386                     if (in->n.newdif > OUTBUFSIZ - in->outpos)
 387                         in->n.newdif = OUTBUFSIZ - in->outpos;
 388
 389                     if (in->n.newdif > 0) {
 390                         memcpy(in->outbuf + in->outpos, in->n.stackp, in->n.newdif);
 391                         in->outpos += in->n.newdif;
 392                     }
 393                     if (in->outpos >= OUTBUFSIZ) {
 394                         write_buf(in, in->outbuf, in->outpos);
 395                         in->bytes_out += (off_t)in->outpos;
 396                         in->outpos = 0;
 397                     }
 398                     in->n.stackp+= in->n.newdif;
 399                 } while ((in->n.newdif = (de_stack - in->n.stackp)) > 0);
 400             } else {
 401                 memcpy(in->outbuf + in->outpos, in->n.stackp, in->n.newdif);
 402                 in->outpos += in->n.newdif;
 403             }
 404
 405             if ((in->n.code = in->n.free_ent) < in->n.maxmaxcode) { /* Generate the new entry. */
 406
 407                 tab_prefixof(in->n.code) = (uint16_t)in->n.oldcode;
 408                 tab_suffixof(in->n.code) = (uint8_t)in->n.finchar;
 409                 in->n.free_ent = in->n.code+1;
 410             }
 411             in->n.oldcode = in->n.incode;       /* Remember previous code.      */
 412         }
 413     } while (in->rsize != 0);
 414
 415     if (in->outpos > 0) {
 416         write_buf(in, in->outbuf, in->outpos);
 417         in->bytes_out += (off_t)in->outpos;
 418         in->tsize = EOF;
 419         in->outpos = 0;
 420     }
 421 }
 422
 423 /*
 424  * New function, simply to read from the output buffer of unlzw().
 425  * We do this by switching into the context of unlzw() and back
 426  * to our old context if the provided buffer is filled.
 427  */
 428 ssize_t readlzw(LZW_t * in, char* buffer, const size_t size)
 429 {
 430     in->transfer = (uint8_t*)buffer;
 431     in->tcount = size;
 432     in->tsize = 0;
 433     if (in->uc == (ucontext_t*)0)
 434         return 0;                       /* For (f)lex scanner ... */
 435     swapcontext(&in->uc[0], &in->uc[1]);
 436     if (in->tsize < 0) {
 437         free(in->uc);                   /* ... do not enter next */
 438         in->uc = (ucontext_t*)0;
 439         free(in->stack);
 440         in->stack = (uint8_t*)0;
 441         return 0;
 442     }
 443     return in->tsize;
 444 }
 445
 446 #ifdef TEST
 447 int main()
 448 {
 449     ssize_t len;
 450     char buffer[1024];
 451
 452     LZW_t *lzw = openlzw("man.1.Z", "r");
 453     if (!lzw)
 454         return -1;
 455
 456     do {
 457         len = readlzw(lzw, &buffer[0], sizeof(buffer));
 458         write(1, &buffer[0], len);
 459     } while (len != 0);
 460
 461     closelzw(lzw);
 462     return 0;
 463 }
 464 #endif