Код:
#define _CRT_SECURE_NO_WARNINGS
#include <ctype.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*-константы используемые при работе лзв
*/
/* количество битов в коде */
#define BITS 12
/* максимальное значение кода* */
#define MAX_CODE ( ( 1 << BITS ) - 1 )
/* размер словаря элементов */
#define TABLE_SIZE 5021
/* код конца потока* */
#define END_OF_STREAM 256
/* значение кода получаемое первой добавленной в словарь фразой* */
#define FIRST_CODE 257
/* признак свободной ячейки в словаре */
#define UNUSED -1
typedef unsigned char uchar;
typedef unsigned long ulong;
typedef unsigned int uint;
void clrscr(void);
/*---------------------------------------------------------
Побитовый доступ к файлам
*/
typedef struct _bfile
{
FILE *file;
uchar mask;
int rack;
int pacifier_counter;
} BFILE;
#define PACIFIER_COUNT 2047
/*---------------------------------------------------------
функции высокого уровня
*/
void print_ratios ( char *input, char *output );
void Arhiv ( FILE *input, BFILE *output );
void DeArhiv ( BFILE *input, FILE *output );
long file_size ( char *name );
void messege_complite ( char *prog_name );
/*---------------------------------------------------------
прочие функции необходимые для работы программы
*/
BFILE *OpenInputBFile ( char *name );
BFILE *OpenOutputBFile ( char *name );
void WriteBit ( BFILE *bfile, int bit );
void WriteBits ( BFILE *bfile, ulong code, int count );
int ReadBit ( BFILE *bfile );
ulong ReadBits ( BFILE *bfile, int bit_count );
void CloseInputBFile ( BFILE *bfile );
void CloseOutputBFile ( BFILE *bfile );
/*---------------------------------------------------------
функции работы с моделью данных для алгоритма лзв
*/
uint find_dictionary_match ( int prefix_code, int character );
uint decode_string ( uint offset, uint code );
char *CompressionName = "LZW 12-bit Coder";
char *Usage = "input file-output file\n\n";
void fatal_error( char *str, ... );
/*-----------------------------------------------------------
головная процедура*.
*/
void main(void)
{
char ch;
char filename_in[256];
char filename_out[256];
int i;
BFILE *output;
FILE *input, *output2;
clrscr();
setbuf( stdout, NULL );
printf("\nPlease chose the procedure:");
printf("\n1.Compress file");
printf("\n2.Decompres file");
printf("\n3. Stop and Exit!=)");
printf("\nEnter your choyse: ");
ch=_getche();
switch (ch)
{
case '1':
{
for(i=0;i<256;i++)
{
filename_in[i]=filename_out[i]=NULL;
}
printf("\nEnter name of input file: ");
gets(filename_in);
input = fopen( filename_in, "rb" );
if ( input == NULL )
fatal_error( "Error to open %s for input\n", filename_in);
printf("\nEnter name of output file: ");
gets(filename_out);
output = OpenOutputBFile( filename_out);
if ( output == NULL )
fatal_error( "Error to open %s for output\n", filename_out);
printf( "\nPlease wait-Compresing... %s in %s\n", filename_in, filename_out );
printf( "Using %s\n", CompressionName );
Arhiv( input, output );
CloseOutputBFile( output );
fclose( input );
print_ratios( filename_in, filename_out );
}
break;
case '2':
{
for(i=0;i<256;i++)
{
filename_in[i]=filename_out[i]=NULL;
}
printf("\nEnter name of input file: ");
gets(filename_in);
output = OpenInputBFile( filename_in);
if ( output == NULL )
fatal_error( "Error to open %s for input\n", filename_in);
printf("\nEnter name of output file: ");
gets(filename_out);
output2 = fopen( filename_out, "wb");
if ( output2 == NULL )
fatal_error( "Error to open %s for output\n", filename_out);
printf( "\nPlease wait-Decompresing... %s in %s\n", filename_in, filename_out );
printf( "Using %s\n", CompressionName );
//ExpandFile( output, output2 ); ***** НИГДЕ НЕ ОБЪЯВЛЕНА ЭТА ФУНКЦИЯ *****
CloseOutputBFile( output );
fclose( output2 );
print_ratios( filename_in, filename_out );
}
break;
case '3':
{
}break;
}
_getch();
}
/*-----------------------------------------------------------
обработка фатальной ошибки при работе программы.
*/
void fatal_error( char *str, ... )
{
printf( "Fatal Error: %s\n", str );
exit(1);
}
/*-----------------------------------------------------------
открытие файла для побитовой записи
*/
BFILE *OpenOutputBFile ( char * name )
{
BFILE *bfile;
bfile = (BFILE *) calloc( 1, sizeof( BFILE ) );
bfile->file = fopen( name, "wb" );
bfile->rack = 0;
bfile->mask = 0x80;
bfile->pacifier_counter = 0;
return bfile;
}
/*-----------------------------------------------------------
открытие файла для побитового чтения
*/
BFILE *OpenInputBFile( char *name )
{
BFILE *bfile;
bfile = (BFILE *) calloc( 1, sizeof( BFILE ) );
bfile->file = fopen( name, "rb" );
bfile->rack = 0;
bfile->mask = 0x80;
bfile->pacifier_counter = 0;
return bfile;
}
/*-----------------------------------------------------------
закрытие файла для побитовой записи
*/
void CloseOutputBFile ( BFILE *bfile )
{
if ( bfile->mask != 0x80 )
putc( bfile->rack, bfile->file );
fclose ( bfile->file );
free ( (char *) bfile );
}
/*-----------------------------------------------------------
закрытие файла для опбитового чтения
*/
void CloseInputBFile ( BFILE *bfile )
{
fclose ( bfile->file );
free ( (char *) bfile );
}
/*-----------------------------------------------------------
вывод одного бита*
*/
void WriteBit ( BFILE *bfile, int bit )
{
if ( bit )
bfile->rack |= bfile->mask;
bfile->mask >>= 1;
if ( bfile->mask == 0 )
{
putc( bfile->rack, bfile->file );
if ( ( bfile->pacifier_counter++ & PACIFIER_COUNT ) == 0 )
putc( '.', stdout );
bfile->rack = 0;
bfile->mask = 0x80;
}
}
/*-----------------------------------------------------------
вывод нескольких битов
*/
void WriteBits( BFILE *bfile, ulong code, int count )
{
ulong mask;
mask = 1L << ( count - 1 );
while ( mask != 0)
{
if ( mask & code )
bfile->rack |= bfile->mask;
bfile->mask >>= 1;
if ( bfile->mask == 0 )
{
putc( bfile->rack, bfile->file );
if ( ( bfile->pacifier_counter++ & PACIFIER_COUNT ) == 0 )
putc( '.', stdout );
bfile->rack = 0;
bfile->mask = 0x80;
}
mask >>= 1;
}
}
/*-----------------------------------------------------------
‚Ввод дного бита
*/
int ReadBit( BFILE *bfile )
{
int value;
if ( bfile->mask == 0x80 )
{
bfile->rack = getc( bfile->file );
if ( bfile->rack == EOF )
fatal_error( "Error in procedure ReadBit! Something wrong, chek it!\n" );
if ( ( bfile->pacifier_counter++ & PACIFIER_COUNT ) == 0 )
putc( '.', stdout );
}
value = bfile->rack & bfile->mask;
bfile->mask >>= 1;
if ( bfile->mask == 0 )
bfile->mask = 0x80;
return ( value ? 1 : 0 );
}
/*-----------------------------------------------------------
ввод нескольких битов
*/
ulong ReadBits ( BFILE *bfile, int bit_count )
{
ulong mask;
ulong return_value;
mask = 1L << ( bit_count - 1 );
return_value = 0;
while ( mask != 0 )
{
if ( bfile->mask == 0x80 )
{
bfile->rack = getc( bfile->file );
if ( bfile->rack == EOF )
fatal_error( "Error in procedure ReadBits (not ReadBit)! Something wrong, chek it!\n" );
if ( ( bfile->pacifier_counter++ & PACIFIER_COUNT ) == 0 )
putc( '.', stdout );
}
if ( bfile->rack & bfile->mask )
return_value |= mask;
mask >>= 1;
bfile->mask >>= 1;
if ( bfile->mask == 0 )
bfile->mask = 0x80;
}
return return_value;
}
/*-----------------------------------------------------------
вывод сообщения об использовании
*/
void messege_complite ( char *prog_name )
{
char *short_name;
char *extension;
short_name = strrchr( prog_name, '\\' );
if ( short_name == NULL )
short_name = strrchr( prog_name, '/' );
if ( short_name == NULL )
short_name = strrchr( prog_name, ':' );
if ( short_name != NULL )
short_name++;
else
short_name = prog_name;
extension = strrchr( short_name, '.' );
if ( extension != NULL )
*extension = '\0';
printf( "\nUsing: %s %s\n", short_name, Usage );
exit( 0 );
}
/*-----------------------------------------------------------
измерение длинны файла
*/
long file_size ( char *name )
{
long eof_ftell;
FILE *file;
file = fopen( name, "r" );
if ( file == NULL )
return( 0L );
fseek( file, 0L, SEEK_END );
eof_ftell = ftell( file );
fclose( file );
return eof_ftell;
}
/*-----------------------------------------------------------
вывод сообщения о соотношении размеров файлов
*/
void print_ratios( char *input, char *output )
{
long input_size;
long output_size;
int ratio;
input_size = file_size( input );
if ( input_size == 0 )
input_size = 1;
output_size = file_size( output );
ratio = 100 - (int) ( output_size * 100L / input_size );
printf( "\nByte in: %ld\n", input_size );
printf( "Byte out: %ld\n", output_size );
if ( output_size == 0 )
output_size = 1;
printf( "Compression degree: %d%%\n", ratio );
}
/*-----------------------------------------------------------
„Алгоритм ЛЗВ:
*/
/* ‘структура словаря */
struct dictionary
{
int code_value;
int prefix_code;
char character;
}
dict[TABLE_SIZE];
/*стек для декодирования */
char decode_stack[TABLE_SIZE];
/*-----------------------------------------------------------
сжатие файла:
*/
void Arhiv ( FILE *input, BFILE *output )
{
int next_code, character, string_code;
uint index, i;
/* инициализация */
next_code = FIRST_CODE;
for ( i = 0 ; i < TABLE_SIZE ; i++ )
dict[i].code_value = UNUSED;
/* ‘считать первый символ */
if ( ( string_code = getc( input ) ) == EOF )
string_code = END_OF_STREAM;
/* пока не конец сообщения */
while ( ( character = getc( input ) ) != EOF )
{
/* попытка найти в словаре фразу <фраза*, символ> */
index = find_dictionary_match ( string_code, character );
/* соответствие найдено*/
if ( dict[index].code_value != -1 )
string_code = dict[index].code_value;
/* ’такой пары в словаре нет */
else
{
/* „добавление в словарь */
if ( next_code <= MAX_CODE )
{
dict[index].code_value = next_code++;
dict[index].prefix_code = string_code;
dict[index].character = (char) character;
}
/* выдача кода */
WriteBits( output, (ulong) string_code, BITS );
string_code = character;
}
}
/* завершение кодирования */
WriteBits( output, (ulong) string_code, BITS );
WriteBits( output, (ulong) END_OF_STREAM, BITS );
}
/*-----------------------------------------------------------
извлечение сжатого фала (декодирование)
*/
void DeArhiv( BFILE *input, FILE *output )
{
uint next_code, new_code, old_code;
int character;
uint count;
next_code = FIRST_CODE;
old_code = (uint) ReadBits( input, BITS );
if ( old_code == END_OF_STREAM )
return;
character = old_code;
putc ( old_code, output );
while ( ( new_code = (uint) ReadBits( input, BITS ) )
!= END_OF_STREAM )
{
/* обработка неожиданной ситуации */
if ( new_code >= next_code )
{
decode_stack[ 0 ] = (char) character;
count = decode_string( 1, old_code );
}
else
count = decode_string( 0, new_code );
character = decode_stack[ count - 1 ];
/* выдача раскодированной строки */
while ( count > 0 )
putc( decode_stack[--count], output );
/* обновление словаря */
if ( next_code <= MAX_CODE )
{
dict[next_code].prefix_code = old_code;
dict[next_code].character = (char) character;
next_code++;
}
old_code = new_code;
}
}
/*-----------------------------------------------------------
процедура поиска в словаре указанной пары (код фразы, символ).
используеться хеш, получаемый из параметров
*/
uint find_dictionary_match ( int prefix_code, int character )
{
int index;
int offset;
/* получение значения хеш функции */
index = ( character << ( BITS - 8 ) ) ^ prefix_code;
/* разрешение возможных коллизий
Коллизией хеш-функции H называется два различных входных блока данных x и y таких, что H(x) = H(y).
Коллизии существуют для большинства хеш-функций, но для «хороших» хеш-функций частота их возникновения близка к теоретическому минимуму.
В некоторых частных случаях, когда множество различных входных данных конечно, можно задать инъективную хеш-функцию, по определению не
имеющую коллизий. Однако, для функций, принимающих вход переменной длины и возвращающих хеш постоянной длины (такие, как MD5), коллизии
обязаны существовать, поскольку хотя бы для одного значения хеш-функции соответствующее ему множество входных данных будет бесконечно —
и любые два набора данных из этого множества образуют коллизию. */
if ( index == 0 )
offset = 1;
else
offset = TABLE_SIZE - index;
for ( ; ; )
{
/* ячейка словаря не использована*** */
if ( dict[index].code_value == UNUSED )
return index;
/* найдено соответствие */
if ( dict[index].prefix_code == prefix_code &&
dict[index].character == (char) character )
return index;
/* коллизия.. попытка ее разрешения */
index -= offset;
if ( index < 0 )
index += TABLE_SIZE;
}
}
/*-----------------------------------------------------------
декодирование тсроки. процедура размещает символы в стеке, возвращая их количество
*/
uint decode_string ( uint count, uint kod )
{
while ( kod > 255 ) /*пока не встретитсья код символа* */
{
decode_stack[count++] = dict[kod].character;
kod = dict[kod].prefix_code;
}
decode_stack[count++] = (char) kod;
return count;
}
148 строка:
ExpandFile( output, output2 );
Нигде не определена эта функция, и нигде не написано что она должна делать, поэтому я её закомментировал.
а так
Код:
1>------ Build started: Project: asfasfd, Configuration: Debug Win32 ------
1>Compiling...
1>asfasfd.cpp
1>Build log was saved at "file://d:\Projects\asfasfd\asfasfd\Debug\BuildLog.htm"
1>asfasfd - 0 error(s), 0 warning(s)
========== Build: 1 succeeded, 0 failed, 0 up-to-date, 0 skipped ==========
|
