home *** CD-ROM | disk | FTP | other *** search
/ Piper's Pit BBS/FTP: ibm 0020 - 0029 / ibm0020-0029 / ibm0028.tar / ibm0028 / INSTALL2.TD0 / SOURCES.LIF / EXPAND.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-09-27  |  14.7 KB  |  531 lines
  1. /*=============================================================================
  2.  
  3.      The INSTALL program source code, object code, sample  script files,
  4.      executable  program,  and  documentation  are  subject to copyright
  5.      protection under the laws of the United States and other countries.
  6.  
  7.      This software is licensed, not sold, and may only be  redistributed
  8.      in  executable format and only in accordance with the provisions of
  9.      the INSTALL Source Code License Agreement.
  10.  
  11.         INSTALL is Copyright(C) 1987-1990 by Knowledge Dynamics Corp
  12.        Highway Contract 4 Box 185-H, Canyon Lake, TX (USA) 78133-3508
  13.               512-964-3994 (Voice)   512-964-3958 (24-hr FAX)
  14.  
  15.                       All rights reserved worldwide.
  16.  
  17. ===============================================================================
  18.  
  19. FILENAME:
  20.     expand.c
  21.  
  22. AUTHOR:
  23.     eric jon heflin
  24.  
  25. PUBLIC FUNCTIONS:
  26.     lz_init()   -  allocate and initializes memory for decompressor
  27.     lz_bye()    -  free all allocated memory
  28.     expand()    -  decompress file
  29.  
  30. LOCAL FUNCTIONS:
  31.     s_read()    -  reads file into buffer
  32.     s_write()   -  writes file
  33.     lzd()       -  data compression routine
  34.     hash_init() -  initialize lzw table
  35.     get_code()  -  reads a code from the internal buffer
  36.     put_char()  -  puts a character into output buffer
  37.  
  38. DESCRIPTION:
  39.     This file implements standard Limpel-Ziv-Welch decompression.  If you 
  40.     plan on making any changes to this file, be advised: This file has been
  41.     subjected to extensive data flow analysis, profiling, and hand 
  42.     optimization.  Even a minor change could significantly (as in double or
  43.     triple) the execution time of the decompressor.
  44.  
  45. REVISION HISTORY:
  46.     DATE:    AUTHOR:        DESCRIPTION OF CHANGES:
  47.     900102    ejh            Cosmetic changes.
  48.  
  49. ==============================================================================*/
  50.  
  51. #include "install.h"
  52.  
  53. #if defined(InstantC)
  54. #define assert(c) if(!(c)) _()
  55. #include <sys\types.h>
  56. #include <sys\stat.h>
  57. #include <dos.h>
  58. #include <io.h>
  59. #include <process.h>
  60. #elif defined(__TURBOC__)
  61. #include <sys\types.h>
  62. #include <sys\stat.h>
  63. #include <dos.h>
  64. #include <assert.h>
  65. #include <alloc.h>
  66. #include <io.h>
  67. #include <process.h>
  68. #elif defined(__MICROSOFTC__)
  69. #include <sys\types.h>
  70. #include <sys\stat.h>
  71. #include <dos.h>
  72. #include <malloc.h>
  73. #include <assert.h>
  74. #include <io.h>
  75. #include <process.h>
  76. #elif defined(LATTICE)
  77. #include <assert.h>
  78. #include <types.h>
  79. #include <stat.h>
  80. #undef LATTICE
  81. #include <dos.h>
  82. #define LATTICE
  83. #endif
  84. #include <stdio.h>
  85. #include <ctype.h>
  86. #include <stdlib.h>
  87. #include <fcntl.h>
  88. #include <string.h>
  89.  
  90. /* valid bytes for the 'technique' file header field */
  91. #define NONE    1    /* file is not compressed */
  92. #define LZ        2    /* file is compressed using lz coding */
  93. #define DELETE    9    /* file is marked for deletion */
  94.  
  95. /* valid actions for s_read & s_write upon failure */
  96. #define ABORT 1
  97. #define IGNORE 0
  98.  
  99. /* max number of an unsigned word on this machine */
  100. #define MAX_WORD (0xffff)
  101.  
  102. #define  IN_BUF_SIZE       (8192)
  103. #define  OUT_BUF_SIZE      (8192)
  104.  
  105. #define  INBUFSIZ    (IN_BUF_SIZE - 10)
  106. #define  OUTBUFSIZ   (OUT_BUF_SIZE - 10)
  107. #define  MEMERR      2
  108. #define  IOERR       1
  109. #define  MAXBITS     13
  110. #define  CLEAR       256         /* clear code */
  111. #define  Z_EOF       257         /* end of file marker */
  112. #define  FIRST_FREE  258         /* first free code */
  113. #define  MAXMAX      8192        /* max code + 1 */
  114.  
  115. /* interval at which to check ratio */
  116. #define CHECKGAP 4000
  117. #define NEXT_USE  1
  118. #define FIRST_USE 2
  119. #define FOUND 0
  120.  
  121. #define  STACKSIZE   4000
  122.  
  123. typedef struct 
  124.     {
  125.     word next;
  126.     byte z_ch;
  127.     } element_t;
  128.  
  129. /* local function protos */
  130. static int s_read(int file, byte *work_buf, int len, int action);
  131. static int lzd(project_t *, byte *, int, int, unsigned short, unsigned short);
  132. static void hash_init(void);
  133. static word get_code(void);
  134. static void put_char(project_t *, byte);
  135.  
  136. /* local vars */
  137. static unsigned short our_c_crc, our_o_crc;
  138. static word sp;
  139. word *stack;
  140. static byte *out_buf;    /* output buffer */
  141. static byte *in_buf;    /* input buffer */
  142. static element_t *work_buf;    /* defined in either main.c or lib.c */
  143. static word cur_code;
  144. static word old_code;
  145. static word in_code;
  146. static word buf_size;    /* sizeof work_buffer */
  147. static word free_code;
  148. static int nbits;
  149. static word max_code;
  150. static byte fin_char;
  151. static byte k;
  152. /* used to mask unneeded bits off a code */
  153. static word masks[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff};
  154.  
  155. static file_t *in_file;
  156. static long written;
  157.  
  158. /* offset (in bits) within input buffer array */
  159. static word bit_offset;
  160. /* offset (in bytes) within output buffer array */
  161. static word output_offset;
  162. /* global file handles */
  163. static int input, output;
  164. /* TRUE if memory already allocated */
  165. int done;
  166.  
  167. /* local macros to implement a 16-bit wide stack */
  168. #define  push(x)  {stack[sp++]=(x);if(sp>=STACKSIZE)error("Stack overflow in expand()");}
  169. #define  pop()    (stack[--sp])
  170.  
  171. void lz_init(void)
  172.     {                    /* lz_init */
  173.     /* size of work_buf */
  174.     if (done)
  175.         error("lz_init: Diagnostic error, memory already allocated");
  176.     work_buf = (element_t *) smart_calloc(MAXMAX + 10, sizeof(element_t), "expand_init: Unable to allocate work_buf");
  177.     buf_size = (MAXMAX + 10) * sizeof(element_t);
  178.     stack = (word *) smart_calloc(sizeof(word), STACKSIZE + 20, "expand_init: Unable to allocate stack");
  179.     out_buf = smart_calloc(1, OUTBUFSIZ, "expand_init: Unable to allocate out_buf");
  180.     in_buf = smart_calloc(1, INBUFSIZ, "expand_init: Unable to allocate in_buf");
  181.     done = TRUE;
  182.     }                    /* lz_init */
  183.  
  184.  
  185. void lz_bye(void)
  186.     {                    /* lz_bye */
  187.     if (work_buf != NULL)
  188.         free(work_buf);
  189.     if (stack != NULL)
  190.         free(stack);
  191.     if (out_buf != NULL)
  192.         free(out_buf);
  193.     if (in_buf != NULL)
  194.         free(in_buf);
  195.     work_buf = NULL;
  196.     stack = NULL;
  197.     out_buf = NULL;
  198.     in_buf = NULL;
  199.     done = FALSE;
  200.     }                    /* lz_bye */
  201.  
  202. static int lzd(project_t *project, byte *in_name, int in, int out, unsigned short c_crc, unsigned short o_crc)
  203.     {                    /* lzd */
  204.     word byte_offset;
  205.     word intrabyte_offset;
  206.     input = in;
  207.     output = out;
  208.     nbits = 9;
  209.     max_code = 512;
  210.     free_code = FIRST_FREE;
  211.     sp = 0;
  212.     bit_offset = 0;
  213.     output_offset = 0;
  214.  
  215.     /* some funcs depend on cleared memory */
  216.     memset(in_buf, 0, INBUFSIZ);
  217.     memset(out_buf, 0, OUTBUFSIZ);
  218.     memset(stack, 0, STACKSIZE);
  219.     memset(work_buf, 0, buf_size);
  220.     our_c_crc = our_o_crc = 0xFFFF;
  221.     if (c_crc)
  222.         ;                /* quiet lint */
  223.  
  224.     /* fill buffer before first call to get_code */
  225.     s_read(input, in_buf, INBUFSIZ, IGNORE);
  226.  
  227.     hash_init();        /* initialize work_buf */
  228.  
  229. loop:
  230.     byte_offset = bit_offset / 8;    /* offset w/i in buffer */
  231.     intrabyte_offset = bit_offset % 8;    /* offset w/i byte */
  232.     bit_offset += nbits;
  233.  
  234.     assert(nbits>=9&&nbits<=13);
  235.  
  236.     if (byte_offset >= INBUFSIZ - 5)
  237.         {
  238.         #ifdef COMP_CRC
  239.         our_c_crc = updcrc(our_c_crc, in_buf, byte_offset);
  240.         #endif
  241.  
  242.         /* rotate remaining codes in input buffer before next read */
  243.         memcpy(in_buf, in_buf + byte_offset, INBUFSIZ - byte_offset);
  244.         /* read new data */
  245.         s_read(input, in_buf + INBUFSIZ - byte_offset, byte_offset, IGNORE);
  246.         /* update offsets */
  247.         byte_offset = 0;
  248.         bit_offset = intrabyte_offset + nbits;
  249.         }
  250.  
  251.     cur_code = in_buf[byte_offset] | (in_buf[byte_offset + 1] << 8);
  252.  
  253.     if (intrabyte_offset != 0)
  254.         {
  255.         /* shift next_byte right by intrabyte_offset bits */
  256.         /* and shift those bits right into first_word; */
  257.         cur_code = (cur_code >> intrabyte_offset) | ((in_buf[byte_offset + 2]) << (16 - intrabyte_offset));
  258.         }
  259.     cur_code &= masks[nbits];
  260.     if (cur_code == Z_EOF)
  261.         {
  262.         if (output_offset != 0)
  263.             {
  264.             if (written + output_offset > in_file->o_size)
  265.                 output_offset = (word) (in_file->o_size - written);
  266.             assert(written+output_offset<=in_file->o_size);
  267.             if (output != -2)
  268.                 smart_write(project->out_drive, out_buf, output_offset, output);
  269.             written += output_offset;
  270.             our_o_crc = updcrc(our_o_crc, out_buf, output_offset);
  271.             }
  272.         if (our_o_crc != o_crc)
  273.             {
  274.             wputs(yes_w, "The compressed file %c:%s has been damaged.", project->in_drive, in_name);
  275.             wputs(yes_w, NULL);
  276.             wputs(yes_w, "You may either skip this file and attempt to install the remaining");
  277.             wputs(yes_w, "files or abort the installation process.");
  278.             wputs(yes_w, NULL);
  279.             wputs(yes_w, "Do you wish to skip this file (Y/N)?");
  280.             if (!put_yes(yes_w))
  281.                 say_bye();
  282.             else 
  283.                 {
  284.                 sputs("      Skipping: ");
  285.                 sputs(in_name);
  286.                 sputs("\n");
  287.                 }
  288.             return -1;
  289.             }
  290.         #ifdef COMP_CRC
  291.         our_c_crc = updcrc(our_c_crc, in_buf, bit_offset/8+1);
  292.         if(our_c_crc != c_crc)
  293.             error("Compressed input file is corrupted");
  294.         #endif
  295.         return 0;
  296.         }
  297.  
  298.     assert(nbits>=9&&nbits<=13);
  299.  
  300.     if (cur_code == CLEAR)
  301.         {
  302.         hash_init();
  303.         old_code = cur_code = get_code();
  304.         fin_char = k = (byte) old_code;
  305.         put_char(project, k);
  306.         goto loop;
  307.         }
  308.  
  309.     in_code = cur_code;
  310.     if (cur_code >= free_code)
  311.         {                /* if code not in table (k<w>k<w>k) */
  312.         cur_code = old_code;    /* previous code becomes current */
  313.         push(fin_char);
  314.         }
  315.  
  316.     while (cur_code > 255)
  317.         {                /* if code, not character */
  318.         push(work_buf[cur_code].z_ch);    /* push suffix char */
  319.         cur_code = work_buf[cur_code].next;    /* <w> := <w>.code */
  320.         }
  321.  
  322.     assert(nbits>=9&&nbits<=13);
  323.  
  324.     k = fin_char = (byte) cur_code;
  325.     push(k);
  326.     while (sp != 0)
  327.         {
  328.         if (output_offset >= OUTBUFSIZ)
  329.             {
  330.             /* output buffer is full */
  331.             assert(written+output_offset<=in_file->o_size);
  332.             if (output != -2)
  333.                 smart_write(project->out_drive, out_buf, output_offset, output);
  334.             written += output_offset;
  335.             /* calculate new crc based on old crc and new data */
  336.             our_o_crc = updcrc(our_o_crc, out_buf, output_offset);
  337.             /* reset output buffer pointer */
  338.             output_offset = 0;
  339.             }
  340.         assert(output_offset<OUTBUFSIZ);
  341.         /* now place char in output buffer */
  342.         out_buf[output_offset++] = (byte) pop();
  343.         }
  344.  
  345.     assert(nbits>=9&&nbits<=13);
  346.     assert(free_code<=MAXMAX+1);
  347.     work_buf[free_code].z_ch = k;    /* save suffix char */
  348.     work_buf[free_code].next = old_code;    /* save prefix code */
  349.  
  350.     if (++free_code >= max_code && nbits < MAXBITS)
  351.         {
  352.         /* increase the code size */
  353.         nbits++;
  354.         assert(nbits>=9&&nbits<=13);
  355.         max_code <<= 1;    /* double max_code */
  356.         }
  357.  
  358.     old_code = in_code;
  359.  
  360.     assert(nbits>=9&&nbits<=13);
  361.     goto loop;
  362.     }                    /* lzd */
  363.  
  364. void expand(project_t *project, file_t *file)
  365.     {                    /* expand */
  366.     int in = -1, out = -1;
  367.     int l;
  368.     byte out_file[100], temp_file[100];
  369.     byte pa[100], dr[5];
  370.     sp = 0;
  371.  
  372.     in_file = file;
  373.     written = 0l;
  374.  
  375.     if (!file->expand || file->c_size == 0 || file->damaged)
  376.         {
  377.         /* file was not compressed, or is damaged, no work to be done */
  378.         return;
  379.         }
  380.  
  381.     if (!file->abs)
  382.         sprintf(out_file, "%c:%s%s", project->out_drive, project->subdir, file->out_fname);
  383.     else 
  384.         strcpy(out_file, file->out_fname);
  385.     parse_file(out_file, dr, pa, NULL, NULL);
  386.     l = strlen(pa);
  387.     if ((l >= 1 && pa[l - 1] != '\\') || l == 0)
  388.         strcat(pa, "\\");
  389.     l = strlen(dr);
  390.     if (!file->abs)
  391.         sprintf(temp_file, "%c:%sTEMP.$$$", project->out_drive, pa);
  392.     else 
  393.         {
  394.         if (l > 0)
  395.             sprintf(temp_file, "%c:%sTEMP.$$$", dr[0], pa);
  396.         else 
  397.             sprintf(temp_file, "%c:%sTEMP.$$$", project->out_drive, pa);
  398.         }
  399.  
  400.     in = smart_open(temp_file, O_RDONLY | O_BINARY, 0);
  401.  
  402.     if (file->append && exists(out_file))
  403.         {
  404.         /* open file for append access */
  405.         out = smart_open(out_file, O_BINARY | O_APPEND | O_WRONLY, S_IWRITE | S_IREAD);
  406.         smart_seek(out, 0l, SEEK_END, out_file);
  407.         }
  408.     else 
  409.         {
  410.         /* erase any existing file */
  411.         if (exists(out_file))
  412.             remove(out_file);
  413.         out = smart_open(out_file, O_BINARY | O_CREAT | O_WRONLY, S_IWRITE | S_IREAD);
  414.         }
  415.     if (lzd(project, file->in_fname, in, out, file->c_crc, file->o_crc) == -1)
  416.         {
  417.         /* damaged file */
  418.         file->damaged = TRUE;
  419.         remove(out_file);
  420.         smart_close(in, temp_file);
  421.         smart_close(out, out_file);
  422.         remove(out_file);
  423.         remove(temp_file);
  424.         return;
  425.         }
  426.     while (chgfilet(out, file->time) == -1)
  427.         {
  428.         byte *s;
  429.         if((s = dosprob(NULL)) != NULL)
  430.             wputs(retry_w, s);
  431.         wputs(retry_w, "Unable to change time/date information: %s", out_file);
  432.         put_retry(retry_w);
  433.         }
  434.  
  435.     smart_close(out, temp_file);
  436.     smart_close(in, out_file);
  437.     remove(temp_file);
  438.     }                    /* expand */
  439.  
  440.  
  441. static void hash_init()
  442.     {                    /* hash_init */
  443.     nbits = 9;
  444.     max_code = 512;
  445.     free_code = FIRST_FREE;
  446.     }                    /* hash_init */
  447.  
  448. /*
  449.  *    Reads a code from internally managed buffer.  The buffer is regarded
  450.  *    as a bit-stream of codes potentially interdispursed by lz commands
  451.  *    clear and eof.
  452.  */
  453.  
  454. static word get_code()
  455.     {                    /* get_code */
  456.     word first_word;    /* first 16 bits in buffer */
  457.     word byte_offset;
  458.     byte next_byte;        /* next 8 bits in buffer */
  459.     word intrabyte_offset;    /* offset within byte */
  460.  
  461.     intrabyte_offset = bit_offset % 8;
  462.     byte_offset = bit_offset / 8;
  463.     bit_offset = bit_offset + nbits;
  464.  
  465.     assert(nbits>=9&&nbits<=13);
  466.  
  467.     if (byte_offset >= INBUFSIZ - 5)
  468.         {
  469.         #ifdef COMP_CRC
  470.         our_c_crc = updcrc(our_c_crc, in_buf, byte_offset);
  471.         #endif
  472.  
  473.         /* rotate remaining codes in input buffer before next read */
  474.         memcpy(in_buf, in_buf + byte_offset, INBUFSIZ - byte_offset);
  475.         /* read new data */
  476.         s_read(input, in_buf + INBUFSIZ - byte_offset, byte_offset, IGNORE);
  477.         /* update offsets */
  478.         byte_offset = 0;
  479.         bit_offset = intrabyte_offset + nbits;
  480.         }
  481.  
  482.     first_word = in_buf[byte_offset];
  483.     first_word = first_word | ((in_buf[byte_offset + 1]) << 8);
  484.     next_byte = in_buf[byte_offset + 2];
  485.     if (intrabyte_offset != 0)
  486.         {
  487.         /* shift next_byte right by intrabyte_offset bits */
  488.         /* and shift those bits right into first_word; */
  489.         first_word = (first_word >> intrabyte_offset) | (((word) next_byte) << (16 - intrabyte_offset));
  490.         }
  491.     return first_word & masks[nbits];
  492.     }                    /* get_code */
  493.  
  494.  
  495. static void put_char(project_t *project, byte c)
  496.     {                    /* put_char */
  497.     if (output_offset >= OUTBUFSIZ)
  498.         {
  499.         /* output buffer is full */
  500.         assert(written+output_offset<=in_file->o_size);
  501.         if (output != -2)
  502.             smart_write(project->out_drive, out_buf, output_offset, output);
  503.         written += output_offset;
  504.         /* calculate new crc based on old crc and new data */
  505.         our_o_crc = updcrc(our_o_crc, out_buf, output_offset);
  506.         /* reset output buffer pointer */
  507.         output_offset = 0;
  508.         }
  509.     assert(output_offset<OUTBUFSIZ);
  510.     /* now place char in output buffer */
  511.     out_buf[output_offset++] = c;
  512.     }                    /* put_char */
  513.  
  514. static int s_read(int file, byte *work_buf, int len, int action)
  515.     {                    /* s_read */
  516.     byte *s;
  517.     word error_code;
  518.     int bytes_read = read(file, work_buf, len);
  519.  
  520.     if (bytes_read < len && action == ABORT)
  521.         {
  522.         if ((s = dosprob(&error_code)) != NULL)
  523.             wputs(error_w, s);
  524.         wputs(error_w, "Unable to read file: %s", file);
  525.         put_error(error_w);
  526.         }
  527.     return bytes_read;
  528.     }                    /* s_read */
  529.  
  530. /* end-of-file */
  531.