home *** CD-ROM | disk | FTP | other *** search
/ PC Extra Super CD 1998 January / PCPLUS131.iso / DJGPP / V2 / DJLSR201.ZIP / src / utils / djtar / unlzw.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-01-10  |  8.9 KB  |  371 lines
  1. /* Copyright (C) 1996 DJ Delorie, see COPYING.DJ for details */
  2. /* Copyright (C) 1995 DJ Delorie, see COPYING.DJ for details */
  3. /* unlzw.c -- decompress files in LZW format.
  4.  * The code in this file is directly derived from the public domain 'compress'
  5.  * written by Spencer Thomas, Joe Orost, James Woods, Jim McKie, Steve Davies,
  6.  * Ken Turkowski, Dave Mack and Peter Jannesen.
  7.  *
  8.  * This is a temporary version which will be rewritten in some future version
  9.  * to accommodate in-memory decompression.
  10.  *
  11.  * Minor changes for DJTAR program, Eli Zaretskii November 1995.
  12.  */
  13.  
  14. #ifdef RCSID
  15. static char rcsid[] = "$Id: unlzw.c,v 0.15 1993/06/10 13:28:35 jloup Exp $";
  16. #endif
  17.  
  18. #include <sys/types.h>
  19.  
  20. #include "tailor.h"
  21.  
  22. #include <unistd.h>
  23. #include <fcntl.h>
  24.  
  25. #include "zread.h"
  26. #include "lzw.h"
  27.  
  28. #include "oread.h"
  29.  
  30. typedef    unsigned char    char_type;
  31. typedef          long   code_int;
  32. typedef unsigned long     count_int;
  33. typedef unsigned short    count_short;
  34. typedef unsigned long     cmp_code_int;
  35.  
  36. #define MAXCODE(n)    (1L << (n))
  37.     
  38. #ifndef    REGISTERS
  39. #    define    REGISTERS    2
  40. #endif
  41. #define    REG1    
  42. #define    REG2    
  43. #define    REG3    
  44. #define    REG4    
  45. #define    REG5    
  46. #define    REG6    
  47. #define    REG7    
  48. #define    REG8    
  49. #define    REG9    
  50. #define    REG10
  51. #define    REG11    
  52. #define    REG12    
  53. #define    REG13
  54. #define    REG14
  55. #define    REG15
  56. #define    REG16
  57. #if REGISTERS >= 1
  58. #    undef    REG1
  59. #    define    REG1    register
  60. #endif
  61. #if REGISTERS >= 2
  62. #    undef    REG2
  63. #    define    REG2    register
  64. #endif
  65. #if REGISTERS >= 3
  66. #    undef    REG3
  67. #    define    REG3    register
  68. #endif
  69. #if REGISTERS >= 4
  70. #    undef    REG4
  71. #    define    REG4    register
  72. #endif
  73. #if REGISTERS >= 5
  74. #    undef    REG5
  75. #    define    REG5    register
  76. #endif
  77. #if REGISTERS >= 6
  78. #    undef    REG6
  79. #    define    REG6    register
  80. #endif
  81. #if REGISTERS >= 7
  82. #    undef    REG7
  83. #    define    REG7    register
  84. #endif
  85. #if REGISTERS >= 8
  86. #    undef    REG8
  87. #    define    REG8    register
  88. #endif
  89. #if REGISTERS >= 9
  90. #    undef    REG9
  91. #    define    REG9    register
  92. #endif
  93. #if REGISTERS >= 10
  94. #    undef    REG10
  95. #    define    REG10    register
  96. #endif
  97. #if REGISTERS >= 11
  98. #    undef    REG11
  99. #    define    REG11    register
  100. #endif
  101. #if REGISTERS >= 12
  102. #    undef    REG12
  103. #    define    REG12    register
  104. #endif
  105. #if REGISTERS >= 13
  106. #    undef    REG13
  107. #    define    REG13    register
  108. #endif
  109. #if REGISTERS >= 14
  110. #    undef    REG14
  111. #    define    REG14    register
  112. #endif
  113. #if REGISTERS >= 15
  114. #    undef    REG15
  115. #    define    REG15    register
  116. #endif
  117. #if REGISTERS >= 16
  118. #    undef    REG16
  119. #    define    REG16    register
  120. #endif
  121.     
  122. #ifndef    BYTEORDER
  123. #    define    BYTEORDER    0000
  124. #endif
  125.     
  126. #ifndef    NOALLIGN
  127. #    define    NOALLIGN    0
  128. #endif
  129.  
  130.  
  131. union    bytes {
  132.     long  word;
  133.     struct {
  134. #if BYTEORDER == 4321
  135.     char_type    b1;
  136.     char_type    b2;
  137.     char_type    b3;
  138.     char_type    b4;
  139. #else
  140. #if BYTEORDER == 1234
  141.     char_type    b4;
  142.     char_type    b3;
  143.     char_type    b2;
  144.     char_type    b1;
  145. #else
  146. #    undef    BYTEORDER
  147.     int  dummy;
  148. #endif
  149. #endif
  150.     } bytes;
  151. };
  152.  
  153. #if BYTEORDER == 4321 && NOALLIGN == 1
  154. #  define input(b,o,c,n,m){ \
  155.      (c) = (*(long *)(&(b)[(o)>>3])>>((o)&0x7))&(m); \
  156.      (o) += (n); \
  157.    }
  158. #else
  159. #  define input(b,o,c,n,m){ \
  160.      REG1 char_type *p = &(b)[(o)>>3]; \
  161.      (c) = ((((long)(p[0]))|((long)(p[1])<<8)| \
  162.      ((long)(p[2])<<16))>>((o)&0x7))&(m); \
  163.      (o) += (n); \
  164.    }
  165. #endif
  166.  
  167. #ifndef MAXSEG_64K
  168.    /* DECLARE(ush, tab_prefix, (1<<BITS)); -- prefix code */
  169. #  define tab_prefixof(i) tab_prefix[i]
  170. #  define clear_tab_prefixof()    memzero(tab_prefix, 256);
  171. #else
  172.    /* DECLARE(ush, tab_prefix0, (1<<(BITS-1)); -- prefix for even codes */
  173.    /* DECLARE(ush, tab_prefix1, (1<<(BITS-1)); -- prefix for odd  codes */
  174.    ush *tab_prefix[2];
  175. #  define tab_prefixof(i) tab_prefix[(i)&1][(i)>>1]
  176. #  define clear_tab_prefixof()    \
  177.       memzero(tab_prefix0, 128), \
  178.       memzero(tab_prefix1, 128);
  179. #endif
  180. #define de_stack        ((char_type *)(&d_buf[DIST_BUFSIZE-1]))
  181. #define tab_suffixof(i) tab_suffix[i]
  182.  
  183. int block_mode = BLOCK_MODE; /* block compress mode -C compatible with 2.0 */
  184.  
  185. /* ============================================================================
  186.  * Decompress in to out.  This routine adapts to the codes in the
  187.  * file building the "string" table on-the-fly; requiring no table to
  188.  * be stored in the compressed file.
  189.  * IN assertions: the buffer inbuf contains already the beginning of
  190.  *   the compressed data, from offsets iptr to insize-1 included.
  191.  *   The magic header has already been checked and skipped.
  192.  *   bytes_in and bytes_out have been initialized.
  193.  */
  194. int unlzw(void *in)
  195. {
  196.     REG2   char_type  *stackp;
  197.     REG3   code_int   code;
  198.     REG4   int        finchar;
  199.     REG5   code_int   oldcode;
  200.     REG6   code_int   incode;
  201.     REG7   long       inbits;
  202.     REG8   long       posbits;
  203.     REG9   int        outpos;
  204. /*  REG10  int        insize; (global) */
  205.     REG11  unsigned   bitmask;
  206.     REG12  code_int   free_ent;
  207.     REG13  code_int   maxcode;
  208.     REG14  code_int   maxmaxcode;
  209.     REG15  int        n_bits;
  210.     REG16  int        rsize;
  211.  
  212.     maxbits = get_byte();
  213.     block_mode = maxbits & BLOCK_MODE;
  214.     if ((maxbits & LZW_RESERVED) != 0) {
  215.     WARN((log_out, "\n%s: %s: warning, unknown flags 0x%x\n",
  216.           progname, ifname, maxbits & LZW_RESERVED));
  217.     }
  218.     maxbits &= BIT_MASK;
  219.     maxmaxcode = MAXCODE(maxbits);
  220.     
  221.     if (maxbits > BITS) {
  222.     fprintf(log_out,
  223.         "\n%s: %s: compressed with %d bits, can only handle %d bits\n",
  224.         progname, ifname, maxbits, BITS);
  225.     exit_code = ERROR;
  226.     return ERROR;
  227.     }
  228.     rsize = insize;
  229.     maxcode = MAXCODE(n_bits = INIT_BITS)-1;
  230.     bitmask = (1<<n_bits)-1;
  231.     oldcode = -1;
  232.     finchar = 0;
  233.     outpos = 0;
  234.     posbits = inptr<<3;
  235.  
  236.     free_ent = ((block_mode) ? FIRST : 256);
  237.     
  238.     clear_tab_prefixof(); /* Initialize the first 256 entries in the table. */
  239.     
  240.     for (code = 255 ; code >= 0 ; --code) {
  241.     tab_suffixof(code) = (char_type)code;
  242.     }
  243.     do {
  244.     REG1 int i;
  245.     int  e;
  246.     int  o;
  247.     
  248.     resetbuf:
  249.     e = insize-(o = (posbits>>3));
  250.     
  251.     for (i = 0 ; i < e ; ++i) {
  252.         inbuf[i] = inbuf[i+o];
  253.     }
  254.     insize = e;
  255.     posbits = 0;
  256.     
  257.     if (insize < INBUF_EXTRA) {
  258.         if ((rsize = oread_read(in, (char*)inbuf+insize)) == EOF) {
  259.         read_error();
  260.         }
  261.         insize += rsize;
  262.     }
  263.     inbits = ((rsize != 0) ? ((long)insize - insize%n_bits)<<3 : 
  264.           ((long)insize<<3)-(n_bits-1));
  265.     
  266.     while (inbits > posbits) {
  267.         if (free_ent > maxcode) {
  268.         posbits = ((posbits-1) +
  269.                ((n_bits<<3)-(posbits-1+(n_bits<<3))%(n_bits<<3)));
  270.         ++n_bits;
  271.         if (n_bits == maxbits) {
  272.             maxcode = maxmaxcode;
  273.         } else {
  274.             maxcode = MAXCODE(n_bits)-1;
  275.         }
  276.         bitmask = (1<<n_bits)-1;
  277.         goto resetbuf;
  278.         }
  279.         input(inbuf,posbits,code,n_bits,bitmask);
  280.         Tracev((stderr, "%d ", code));
  281.  
  282.         if (oldcode == -1) {
  283.         if (code >= 256) error("corrupt input.");
  284.         outbuf[outpos++] = (char_type)(finchar = (int)(oldcode=code));
  285.         continue;
  286.         }
  287.         if (code == CLEAR && block_mode) {
  288.         clear_tab_prefixof();
  289.         free_ent = FIRST - 1;
  290.         posbits = ((posbits-1) +
  291.                ((n_bits<<3)-(posbits-1+(n_bits<<3))%(n_bits<<3)));
  292.         maxcode = MAXCODE(n_bits = INIT_BITS)-1;
  293.         bitmask = (1<<n_bits)-1;
  294.         goto resetbuf;
  295.         }
  296.         incode = code;
  297.         stackp = de_stack;
  298.         
  299.         if (code >= free_ent) { /* Special case for KwKwK string. */
  300.         if (code > free_ent) {
  301. #ifdef DEBUG            
  302.             char_type *p;
  303.  
  304.             posbits -= n_bits;
  305.             p = &inbuf[posbits>>3];
  306.             fprintf(log_out,
  307.                 "code:%ld free_ent:%ld n_bits:%d insize:%u\n",
  308.                 code, free_ent, n_bits, insize);
  309.             fprintf(log_out,
  310.                 "posbits:%ld inbuf:%02X %02X %02X %02X %02X\n",
  311.                 posbits, p[-1],p[0],p[1],p[2],p[3]);
  312. #endif
  313.             if (!test && outpos > 0) {
  314.             tarread((char*)outbuf, outpos);
  315.             }
  316.             error("corrupt input. Use zcat to recover some data.");
  317.         }
  318.         *--stackp = (char_type)finchar;
  319.         code = oldcode;
  320.         }
  321.  
  322.         while ((cmp_code_int)code >= (cmp_code_int)256) {
  323.         /* Generate output characters in reverse order */
  324.         *--stackp = tab_suffixof(code);
  325.         code = tab_prefixof(code);
  326.         }
  327.         *--stackp =    (char_type)(finchar = tab_suffixof(code));
  328.         
  329.         /* And put them out in forward order */
  330.         {
  331.         REG1 int    ii;
  332.         
  333.         if (outpos+(ii = (de_stack-stackp)) >= OUTBUFSIZ) {
  334.             do {
  335.             if (ii > OUTBUFSIZ-outpos) ii = OUTBUFSIZ-outpos;
  336.  
  337.             if (ii > 0) {
  338.                 memcpy(outbuf+outpos, stackp, ii);
  339.                 outpos += ii;
  340.             }
  341.             if (outpos >= OUTBUFSIZ) {
  342.                 if (!test) {
  343.                 if (tarread((char*)outbuf, outpos) == EOF)
  344.                     return OK;
  345.                 }
  346.                 outpos = 0;
  347.             }
  348.             stackp+= ii;
  349.             } while ((ii = (de_stack-stackp)) > 0);
  350.         } else {
  351.             memcpy(outbuf+outpos, stackp, ii);
  352.             outpos += ii;
  353.         }
  354.         }
  355.  
  356.         if ((code = free_ent) < maxmaxcode) { /* Generate the new entry. */
  357.  
  358.         tab_prefixof(code) = (unsigned short)oldcode;
  359.         tab_suffixof(code) = (char_type)finchar;
  360.         free_ent = code+1;
  361.         } 
  362.         oldcode = incode;    /* Remember previous code.    */
  363.     }
  364.     } while (rsize != 0);
  365.     
  366.     if (!test && outpos > 0) {
  367.     tarread((char*)outbuf, outpos);
  368.     }
  369.     return OK;
  370. }
  371.