Developing.ru

Код: Выделить всё

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <alloc.h>
#define BITS 12
#define HASHING_SHIFT BITS-8
#define MAX_VALUE (1 << BITS) - 1
#define MAX_CODE MAX_VALUE - 1


#if BITS == 14
#define TABLE_SIZE 18041
#endif
#if BITS == 13
#define TABLE_SIZE 9029
#endif
#if BITS <= 12
#define TABLE_SIZE 5021
#endif

void *malloc();

int *code_value;

unsigned int *prefix_code;

unsigned char *append_character;

unsigned char decode_stack[4000];
/*********************************************************************

********************************************************************/
main(int argc, char *argv[])
{
FILE *input_file;
FILE *output_file;
FILE *lzw_file;
char input_file_name[81];
/*
** эти три буфера необходимы на стадии упаковки
*/
code_value=malloc(TABLE_SIZE*sizeof(unsigned int));
prefix_code=malloc(TABLE_SIZE*sizeof(unsigned int));
append_character=malloc(TABLE_SIZE*sizeof(unsigned char));
if (code_value==NULL || prefix_code==NULL || append_character==NULL)
{
 printf("Fatal error allocating table space!\n");
 /*exit(); */
}
/*
** получить имя файла, открыть его и открыть выходной лзв-файл
*/
 if (argc>1)
	   strcpy("C:\\vot.bmp",argv[1]);
 else
     { printf("Input file name? ");
       scanf("%s","C:\\vot.bmp");
     }
input_file=fopen("C:\\vot.bmp","rb");
lzw_file=fopen("C:\\test.lzw","wb");
 if (input_file==NULL || lzw_file==NULL)
     {
       printf("Fatal error opening files.\n");
      /* exit();*/
     };
/*
** сжатие файла.
*/
compress(input_file,lzw_file);
fclose(input_file);
fclose(lzw_file);
free(code_value);
/*
** открываем файлы для распаковки.
*/
 lzw_file=fopen("C:\\test.lzw","rb");
 output_file=fopen("C:\\test.out","wb");
    if (lzw_file==NULL || output_file==NULL)
     {
       printf("Fatal error opening files.\n");
     /*  exit();  */
     };
/*
** распаковка файла.
*/
expand(lzw_file,output_file);
fclose(lzw_file);
fclose(output_file);
free(prefix_code);
free(append_character);
}
/*
** процедурка сжатия_.
*/
void compress(FILE *input,FILE *output)
{
unsigned int next_code;
unsigned int character;
unsigned int string_code;
unsigned int index;
int i;
next_code=256;    /* Next_code - следующий доступный код строки */
for (i=0; i<next_code; i++)
code_value[i]=-1;
/*i=0;*/
printf("Compressing...\n");
string_code=getc(input);   /* Get the first code*/
/*
** основной цикл
*/
    while ((character=getc(input)) != (unsigned)EOF)
	  {
	   if (++i==1000)   /* печатает * через каждые 1000  */
	     {              /* чтений входных символов_ */
	       i=0;
	      printf("*");
	       }
/*  */
index=find_match(string_code,character);
  if (code_value[index] != -1)
     string_code=code_value[index];
  else
      {
	if (next_code <= MAX_CODE)
	 {
	   code_value[index]=next_code++;
	   prefix_code[index]=string_code;
	   append_character[index]=character;
	 }
output_code(output,string_code);
string_code=character;
      }
}

/*
** End of the main loop.
*/
output_code(output,string_code);  /* вывод последнего кода   */
output_code(output,MAX_VALUE);    /* вывод признака конца потока */
output_code(output,0);            /* очистка буфера вывода  */
printf("\n");
}
/*
**
*/
find_match(int hash_prefix,unsigned int hash_character)
{
int index;
int offset;
       index = (hash_character << HASHING_SHIFT) ^ hash_prefix;
       if (index == 0)
	   offset = 1;
       else   offset = TABLE_SIZE - index;
       while (1)
		{
		 if (code_value[index] == -1)
		 return(index);
       if (prefix_code[index]==hash_prefix && append_character[index]==hash_character)
		 return(index);
		 index -= offset;
	 if (index < 0)
	    index += TABLE_SIZE;
		}
}
/*
**  процедура распаковки
*/
void expand(FILE *input,FILE *output)
{
unsigned int next_code;
unsigned int new_code;
unsigned int old_code;
int character;
int counter;
unsigned char *string;
char *decode_string(unsigned char *buffer,unsigned int code);
    next_code=256;            /* след доступный код   */
    counter=0;
    printf("Expanding...\n");
old_code=input_code(input);
character=old_code;
putc(old_code,output);
/*
**  основной цикл распаковки
*/
while ((new_code=input_code(input)) != (MAX_VALUE))
{
   if (++counter==1000)
	 { counter=0;
	   printf("*");
	  }
/* */
   if (new_code>=next_code)
     {
	*decode_stack=character;
	string=decode_string(decode_stack+1,old_code);
     }
/*
** .
*/
   else
	string=decode_string(decode_stack,new_code);
/*
** выводится декодируемая строка в обратном порядке.
*/
   character=*string;
   while (string >= decode_stack)
      putc(*string--,output);
/*
** наконец, если возможно, добавляется новый код в таблицу строк.
*/
	 if (next_code <= MAX_CODE)
	 {
	  prefix_code[next_code]=old_code;
	  append_character[next_code]=character;
	  next_code++;
	 }
     old_code=new_code;
   }
printf("\n");}
/*
**.
*/
char *decode_string(unsigned char *buffer,unsigned int code)
{
int i;
i=0;
     while (code > 255)
	 {  *buffer++ = append_character[code];
	    code=prefix_code[code];
	    if (i++>=4094)
	      {
		printf("Fatal error during code expansion.\n");
	      /*	exit(); */
	       }
	  }
  *buffer=code;
 return(buffer);}
/*
**
*/
input_code(FILE *input)
{
unsigned int return_value;
static int input_bit_count=0;
static unsigned long input_bit_buffer=0L;
     while (input_bit_count <= 24)
     {
      input_bit_buffer|=(unsigned long)getc(input)<<(24-input_bit_count);
      input_bit_count += 8;
     }
 return_value=input_bit_buffer >> (32-BITS);
 input_bit_buffer <<= BITS;
 input_bit_count -= BITS;
 return(return_value);
}
output_code(FILE *output,unsigned int code)
{
static int output_bit_count=0;
static unsigned long output_bit_buffer=0L;
output_bit_buffer|=(unsigned long)code<<(32-BITS-output_bit_count);
  output_bit_count += BITS;
  while (output_bit_count >= 8)
  {
  putc(output_bit_buffer >> 24,output);
  output_bit_buffer <<= 8;
  output_bit_count -= 8;
  }
  }