home *** CD-ROM | disk | FTP | other *** search
/ Mega CD-ROM 1 / megacd_rom_1.zip / megacd_rom_1 / MAGAZINE / DDJMAG / DDJ8910.ZIP / NELSON.LST < prev    next >
File List  |  1989-09-07  |  10KB  |  307 lines
  1. _LZW Data Compression_
  2. by Mark R. Nelson
  3.  
  4. [LISTING ONE]
  5.  
  6.  
  7. /****************************************************************************
  8. ** LZW data compression/expansion demonstration program.
  9. ** Mark R. Nelson
  10. *****************************************************************************/
  11. #include <stdio.h>
  12.  
  13. #define BITS 12                      /* Setting the number of bits to 12, 13 */
  14. #define HASHING_SHIFT BITS-8         /* or 14 affects several constants.     */
  15. #define MAX_VALUE (1 << BITS) - 1    /* Note that MS-DOS machines need to    */
  16. #define MAX_CODE MAX_VALUE - 1       /* compile their code in large model if */
  17.                                      /* 14 bits are selected.                */
  18. #if BITS == 14
  19.   #define TABLE_SIZE 18041           /* The string table size needs to be a  */
  20. #endif                               /* prime number that is somwhat larger  */
  21. #if BITS == 13                       /* than 2**BITS.                        */
  22.   #define TABLE_SIZE 9029
  23. #endif
  24. #if BITS <= 12
  25.   #define TABLE_SIZE 5021
  26. #endif
  27.  
  28. void *malloc();
  29.  
  30. int *code_value;                     /* This is the code value array         */
  31. unsigned int *prefix_code;           /* This array holds the prefix codes    */
  32. unsigned char *append_character;     /* This array holds the appended chars  */
  33. unsigned char decode_stack[4000];    /* This array holds the decoded string  */
  34.  
  35. /****************************************************************************
  36. ** This program gets a file name from the command line.  It compresses the
  37. ** file, placing its output in a file named test.lzw.  It then expands
  38. ** test.lzw into test.out.  Test.out should then be an exact duplicate of
  39. ** the input file.
  40. ****************************************************************************/
  41.  
  42. main(int argc, char *argv[])
  43. {
  44. FILE *input_file;
  45. FILE *output_file;
  46. FILE *lzw_file;
  47. char input_file_name[81];
  48. /*
  49. **  The three buffers are needed for the compression phase.
  50. */
  51.     code_value=malloc(TABLE_SIZE*sizeof(unsigned int));
  52.     prefix_code=malloc(TABLE_SIZE*sizeof(unsigned int));
  53.     append_character=malloc(TABLE_SIZE*sizeof(unsigned char));
  54.     if (code_value==NULL || prefix_code==NULL || append_character==NULL)
  55.     {
  56.         printf("Fatal error allocating table space!\n");
  57.         exit();
  58.     }
  59. /*
  60. ** Get the file name, open it up, and open up the lzw output file.
  61. */
  62.     if (argc>1)
  63.         strcpy(input_file_name,argv[1]);
  64.     else
  65.     {
  66.         printf("Input file name? ");
  67.         scanf("%s",input_file_name);
  68.     }
  69.     input_file=fopen(input_file_name,"rb");
  70.     lzw_file=fopen("test.lzw","wb");
  71.     if (input_file==NULL || lzw_file==NULL)
  72.     {
  73.         printf("Fatal error opening files.\n");
  74.         exit();
  75.     };
  76. /*
  77. ** Compress the file.
  78. */
  79.     compress(input_file,lzw_file);
  80.     fclose(input_file);
  81.     fclose(lzw_file);
  82.     free(code_value);
  83. /*
  84. ** Now open the files for the expansion.
  85. */
  86.     lzw_file=fopen("test.lzw","rb");
  87.     output_file=fopen("test.out","wb");
  88.     if (lzw_file==NULL || output_file==NULL)
  89.     {
  90.         printf("Fatal error opening files.\n");
  91.         exit();
  92.     };
  93. /*
  94. ** Expand the file.
  95. */
  96.     expand(lzw_file,output_file);
  97.     fclose(lzw_file);
  98.     fclose(output_file);
  99.     free(prefix_code);
  100.     free(append_character);
  101. }
  102.  
  103. /*
  104. ** This is the compression routine.  The code should be a fairly close
  105. ** match to the algorithm accompanying the article.
  106. **
  107. */
  108. compress(FILE *input,FILE *output)
  109. {
  110. unsigned int next_code;
  111. unsigned int character;
  112. unsigned int string_code;
  113. unsigned int index;
  114. int i;
  115.     next_code=256;             /* Next code is the next available string code*/
  116.     for (i=0;i<TABLE_SIZE;i++) /* Clear out the string table before starting */
  117.         code_value[i]=-1;
  118.     i=0;
  119.     printf("Compressing...\n");
  120.     string_code=getc(input);   /* Get the first code*/
  121. /*
  122. ** This is the main loop where it all happens.  This loop runs util all of
  123. ** the input has been exhausted.  Note that it stops adding codes to the
  124. ** table after all of the possible codes have been defined.
  125. */
  126.     while ((character=getc(input)) != (unsigned)EOF)
  127.     {
  128.         if (++i==1000)                   /* Print a * every 1000    */
  129.         {                                /* input characters.  This */
  130.             i=0;                         /* is just a pacifier.     */
  131.             printf("*");
  132.         }
  133.         index=find_match(string_code,character); /* See if the string is in */
  134.         if (code_value[index] != -1)             /* the table.  If it is,   */
  135.             string_code=code_value[index];       /* get the code value.  If */
  136.         else                                     /* the string is not in the*/
  137.         {                                        /* table, try to add it.   */
  138.             if (next_code <= MAX_CODE)
  139.             {
  140.                 code_value[index]=next_code++;
  141.                 prefix_code[index]=string_code;
  142.                 append_character[index]=character;
  143.             }
  144.             output_code(output,string_code);     /* When a string is found  */
  145.             string_code=character;               /* that is not in the table*/
  146.         }                                        /* I output the last string*/
  147.     }                                            /* after adding the new one*/
  148. /*
  149. ** End of the main loop.
  150. */
  151.     output_code(output,string_code);  /* Output the last code */
  152.     output_code(output,MAX_VALUE);    /* Output the end of buffer code */
  153.     output_code(output,0);            /* This code flushes the output buffer*/
  154.     printf("\n");
  155. }
  156. /*
  157. ** This is the hashing routine.  It tries to find a match for the prefix+char
  158. ** string in the string table.  If it finds it, the index is returned.  If
  159. ** the string is not found, the first available index in the string table is
  160. ** returned instead.
  161. */
  162. find_match(int hash_prefix,unsigned int hash_character)
  163. {
  164. int index;
  165. int offset;
  166.  
  167.     index = (hash_character << HASHING_SHIFT) ^ hash_prefix;
  168.     if (index == 0)
  169.         offset = 1;
  170.     else
  171.         offset = TABLE_SIZE - index;
  172.     while (1)
  173.     {
  174. if (code_value[index] == -1)
  175.       return(index);
  176. if (prefix_code[index] == hash_prefix && append_character[index] == hash_character)
  177.       return(index);
  178.   index -= offset;
  179.   if (index < 0)
  180.       index += TABLE_SIZE;
  181.     }
  182. }
  183. /*
  184. **  This is the expansion routine.  It takes an LZW format file, and expands
  185. **  it to an output file.  The code here should be a fairly close match to
  186. **  the algorithm in the accompanying article.
  187. */
  188. expand(FILE *input,FILE *output)
  189. {
  190. unsigned int next_code;
  191. unsigned int new_code;
  192. unsigned int old_code;
  193. int character;
  194. int counter;
  195. unsigned char *string;
  196. char *decode_string(unsigned char *buffer,unsigned int code);
  197.     next_code=256;          /* This is the next available code to define */
  198.     counter=0;              /* Counter is used as a pacifier.            */
  199.     printf("Expanding...\n");
  200.  
  201.     old_code=input_code(input);  /* Read in the first code, initialize the */
  202.     character=old_code;          /* character variable, and send the first */
  203.     putc(old_code,output);       /* code to the output file                */
  204. /*
  205. **  This is the main expansion loop.  It reads in characters from the LZW file
  206. **  until it sees the special code used to inidicate the end of the data.
  207. */
  208.     while ((new_code=input_code(input)) != (MAX_VALUE))
  209.     {
  210.         if (++counter==1000)           /* This section of code prints out  */
  211.         {                              /* an asterisk every 1000 characters*/
  212.             counter=0;                 /* It is just a pacifier.           */
  213.             printf("*");
  214.         }
  215. /*
  216. ** This code checks for the special STRING+CHARACTER+STRING+CHARACTER+STRING
  217. ** case which generates an undefined code.  It handles it by decoding
  218. ** the last code, adding a single character to the end of the decode string.
  219. */
  220.         if (new_code>=next_code)
  221.         {
  222.             *decode_stack=character;
  223.             string=decode_string(decode_stack+1,old_code);
  224.         }
  225. /*
  226. ** Otherwise we do a straight decode of the new code.
  227. */
  228.         else
  229.             string=decode_string(decode_stack,new_code);
  230. /*
  231. ** Now we output the decoded string in reverse order.
  232. */
  233.         character=*string;
  234.         while (string >= decode_stack)
  235.             putc(*string--,output);
  236. /*
  237. ** Finally, if possible, add a new code to the string table.
  238. */
  239.         if (next_code <= MAX_CODE)
  240.         {
  241.             prefix_code[next_code]=old_code;
  242.             append_character[next_code]=character;
  243.             next_code++;
  244.         }
  245.         old_code=new_code;
  246.     }
  247.     printf("\n");
  248. }
  249. /*
  250. ** This routine simply decodes a string from the string table, storing
  251. ** it in a buffer.  The buffer can then be output in reverse order by
  252. ** the expansion program.
  253. */
  254. char *decode_string(unsigned char *buffer,unsigned int code)
  255. {
  256. int i;
  257.  
  258.     i=0;
  259.     while (code > 255)
  260.     {
  261.         *buffer++ = append_character[code];
  262.         code=prefix_code[code];
  263.         if (i++>=4094)
  264.         {
  265.             printf("Fatal error during code expansion.\n");
  266.             exit();
  267.         }
  268.     }
  269.     *buffer=code;
  270.     return(buffer);
  271. }
  272. /*
  273. ** The following two routines are used to output variable length
  274. ** codes.  They are written strictly for clarity, and are not
  275. ** particularly efficient.
  276. */
  277. input_code(FILE *input)
  278. {
  279. unsigned int return_value;
  280. static int input_bit_count=0;
  281. static unsigned long input_bit_buffer=0L;
  282.     while (input_bit_count <= 24)
  283.     {
  284.        input_bit_buffer |= (unsigned long) getc(input) << (24-input_bit_count);
  285.        input_bit_count += 8;
  286.     }
  287.     return_value=input_bit_buffer >> (32-BITS);
  288.     input_bit_buffer <<= BITS;
  289.     input_bit_count -= BITS;
  290.     return(return_value);
  291. }
  292. output_code(FILE *output,unsigned int code)
  293. {
  294. static int output_bit_count=0;
  295. static unsigned long output_bit_buffer=0L;
  296.     output_bit_buffer |= (unsigned long) code << (32-BITS-output_bit_count);
  297.     output_bit_count += BITS;
  298.     while (output_bit_count >= 8)
  299.     {
  300.         putc(output_bit_buffer >> 24,output);
  301.         output_bit_buffer <<= 8;
  302.         output_bit_count -= 8;
  303.     }
  304. }
  305.  
  306.  
  307.