LZ77

Исходный код реализации алгоритма LZ77 (Visual C++) - скачать.

Алгоритм LZ77 - теория.

Исходный код реализации алгоритма LZ77

// LZ77.cpp

#include <io.h>
#include <fcntl.h>
#include <sys/stat.h>
//=========================================================
// Класс для ввода-вывода
class TPackedFile
{
 int handle;
 unsigned char buffer, mask;
public:
 void assign_read(int h); // связывание для чтения
 void assign_write(int h); // связываение для записи
 void flush(); // заполнение нулями

 void putbit(bool val); // запись бита
 bool getbit(); //чтенние бита

 void putbits(int val, int n); // запись n битов
 int getbits(int n); // чтение n битов
};
//---------------------------------------------------------
// заполнение нулями
void TPackedFile::flush()
{
 for (int i = 0; i < 7; i++) putbit(0);
}
//---------------------------------------------------------
// связываение для записи
void TPackedFile::assign_write(int h)
{
 handle = h;
 buffer = 0;
 mask = 128;
}
//---------------------------------------------------------
// связывание для чтения
void TPackedFile::assign_read(int h)
{
 handle = h;
 buffer = 0;
 mask = 0;
}
//---------------------------------------------------------
//чтенние бита
bool TPackedFile::getbit()
{
 if ((mask >>= 1) == 0) 
 {
  read(handle, &buffer, 1);
  mask = 128;//двоичное 10000000
 }
 return (buffer & mask) != 0;
}
//---------------------------------------------------------
// запись бита
void TPackedFile::putbit(bool val)
{
 if (val) buffer |= mask;
 if ((mask >>= 1) == 0) 
 {
  write(handle, &buffer, 1);
  buffer = 0;  
  mask = 128;//двоичное 10000000
 }
}
//---------------------------------------------------------
// запись n битов
void TPackedFile::putbits(int val, int n)
{
 int m = 1;
 for (int i = 0; i < n; i++)
 {
  putbit((val & m) != 0);
  m <<= 1;
 }
}
//---------------------------------------------------------
// чтение n битов
int TPackedFile::getbits(int n)
{
 int result = 0;
 for (int i = 0; i < n; i++)
  result |= getbit() << i;
 return result;
}
//=========================================================
#define OFFS_LN 8
#define LEN_LN 4
#define BYTE_LN 8

//#define BUF_LEN 15
#define BUF_LEN ((1 << LEN_LN) - 1)
//#define DICT_LEN 256
#define DICT_LEN ((1 << OFFS_LN) - 1)

int in_file;  // входной файл
int out_file; // выходной файл
static TPackedFile archive;

/*
 Сделаем буфер на 1 больше, т. к. в find_match
 `unmatched = buffer[match_len];` а match_len
 может достигать BUF_LEN
*/
char buffer[BUF_LEN + 1], dict[DICT_LEN];
int match_pos, match_len, unmatched;
int dict_pos = 0;
//int strpos(char *src, int len, char *sub, int sub_len);
//---------------------------------------------------------
/*
 Возвращает позицию sub от КОНЦА src. от 1 до len
 Если не найдено возвращает 0
*/
int strpos(char *src, int len, char *sub, int sub_len)
{
 for (int i = 0; i <= len - sub_len; i++)
  if (memcmp(src + i, sub, sub_len) == 0) return len - i;
 return 0;
}
//---------------------------------------------------------
// добавление в словарь символа
void add_dict(char c)
{
 if (dict_pos == (DICT_LEN - 1))
 {
  memcpy(dict, dict + 1, DICT_LEN - 1);
  dict[dict_pos - 1] = c;
 }
 else
 {
  dict[dict_pos] = c;
  dict_pos++;
 }
}
//---------------------------------------------------------
// поиск совпадения в словаре
void find_match()
{
 match_len = 0;
 match_pos = 1;
 while(match_len < BUF_LEN)
 {
  read(in_file, &buffer[match_len], 1);
  if (eof(in_file)) break;
  int pos1 = strpos(dict, dict_pos, buffer, match_len + 1);
  if (pos1 == 0) break;
  match_pos = pos1;
  match_len++;
 }
 unmatched = buffer[match_len];
}
//---------------------------------------------------------
// компрессия
void encode()
{
 while(!eof(in_file))
 {
  find_match();
  archive.putbits(match_pos, OFFS_LN);
  archive.putbits(match_len, LEN_LN);
  if (match_len < BUF_LEN)
   archive.putbits(unmatched, BYTE_LN);
  
  for (int i = 0; i < match_len; i++)
   add_dict(buffer[i]);
  if (match_len < BUF_LEN)
   add_dict(unmatched);
 }
 archive.putbits(0, BYTE_LN);
 archive.flush();
}
//---------------------------------------------------------
// декомпрессия
void decode()
{
 char c;
 int i;
 for(;;)
 {
  match_pos = archive.getbits(OFFS_LN);
  if (match_pos == 0) break;
  match_len = archive.getbits(LEN_LN);
  memcpy(buffer, dict + dict_pos - match_pos, match_len);
  write(out_file, buffer, match_len);
  for (i = 0; i < match_len; i++)
   add_dict(buffer[i]);
  if (match_len < BUF_LEN)
  {
   c = archive.getbits(BYTE_LN);
   add_dict(c);
   write(out_file, &c, 1);
  }
 }
}
//---------------------------------------------------------
// главная процедура
int _tmain(int argc, _TCHAR* argv[])
{
 // проверка аргументов
 if (argc < 4)
 {
  printf("Usage:\nLZ77 e in out - encode in to out");
  printf("\nLZ77 d in out - decode in to out\n");
  return -1;
 }

 // открытие входного и выходного файлов
 in_file = open(argv[2], _O_BINARY | _O_RDWR, 
  _S_IREAD | _S_IWRITE);
 out_file = open(argv[3], _O_BINARY | _O_WRONLY | _O_CREAT
  | _O_TRUNC, _S_IREAD | _S_IWRITE);

 if (stricmp(argv[1], "e") == 0) // компрессия
 {
  archive.assign_write(out_file);
  encode();
 }
 else if (stricmp(argv[1], "d") == 0) // декомпрессия
 {
  archive.assign_read(in_file);
  decode();
 }
 else printf("Nothing to do\n");
 
 close(in_file);
 close(out_file);

 return 0;
}