#include <fcntl.h> //нужна для открытия и закрытия файла
#include <string.h>
#include <sys/stat.h> //хранит ключи открытия и закрытия файла

class BFILE // Класс для ввода-вывода
{
    int handle; // хранится открытый файл
    unsigned char buffer, mask; // буфер, маска
public:
    void aread(int h); // связывание для чтения
    void awrite(int h); // связывание для записи
    void SetZero(); // заполнение нулями

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

    void putbits(int val, int n); // запись n битов
    int getbits(int n); // чтение n битов
};

// заполнение нулями
void BFILE::SetZero()
{
    for (int i = 0; i < 7; i++) putbit(0);
}

// связывание для записи
void BFILE::awrite(int h)
{
    handle = h;
    buffer = 0;
    mask = 128;
}

// связывание для чтения
void BFILE::aread(int h)
{
    handle = h;
    buffer = 0;
    mask = 0;
}

//чтенние бита
bool BFILE::getbit()
{
    if ((mask >>= 1) == 0) //побитовый сдвиг 1 вправо
    {
        read(handle, &buffer, 1); //считываем из файла один символ из буфера
        mask = 128;//двоичное 10000000
    }
    return (buffer & mask) != 0;
}

// запись бита
void BFILE::putbit(bool val)
{
    if (val) buffer |= mask;
    if ((mask >>= 1) == 0) //побитовый сдвиг 1 вправо
    {
        write(handle, &buffer, 1); // записываем в файл один символ из буфера
        buffer = 0;
        mask = 128;//двоичное 10000000
    }
}

// запись n битов
void BFILE::putbits(int val, int n)
{
    int m = 1;
    for (int i = 0; i < n; i++)
    {
        putbit((val & m) != 0);
        m <<= 1; //побитовый сдвиг 1 влево
    }
}

// чтение n битов
int BFILE::getbits(int n)
{
    int result = 0;
    for (int i = 0; i < n; i++)
        result |= getbit() << i;
    return result;
}

#define BUF_LEN 15 //максимальная длина буфера
#define DICT_LEN 256 //максимальная длина словаря

int input;  // входной файл
int output; // выходной файл
BFILE pfile;

/*
 Сделаем буфер на 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; //позиция в словаре

/*
 Возвращает позицию 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; //сравнение данных в src и sub
    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(input, &buffer[match_len], 1); //считываем один символ из файла
        if (eof(input)) 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(input)) //пока не дойдем до конца файла
    {
        find_match(); // поиск совпадения в словаре
        pfile.putbits(match_pos, 8); //заполняем 8 бит
        pfile.putbits(match_len, 4); //заполняем 4 бита
        if (match_len < BUF_LEN) // если длина совпадения меньше длины буфера
            pfile.putbits(unmatched, 8);

        for (int i = 0; i < match_len; i++)
            add_dict(buffer[i]); //добавление в словарь буфера
        if (match_len < BUF_LEN) // если длина совпадения меньше длины буфера
            add_dict(unmatched); //добавление в словарь несовпавшего
    }
    pfile.putbits(0, 8);
    pfile.SetZero(); //заполняем нулями
}

// декомпрессия
void decode()
{
    char c;
    int i;
    for(;;)
    {
        match_pos = pfile.getbits(8); //получаем 8 бит
        if (match_pos == 0) break; //если нет совпадений, то переходим к следующей итерации
        match_len = pfile.getbits(4); //получаем 4 бита
        memcpy(buffer, dict + dict_pos - match_pos, match_len); //копируем данные
        write(output, buffer, match_len); //записываем раскодированные данные
        for (i = 0; i < match_len; i++)
            add_dict(buffer[i]); //добавление в словарь
        if (match_len < BUF_LEN) // если длина совпадения меньше длины буфера
        {
            c = pfile.getbits(8);
            add_dict(c); //добавление символа в словарь
            write(output, &c, 1); //записываем раскодированный символ
        }
    }
}

int main()
{
// открытие входного и выходного файлов
    input = open("in.txt", _O_BINARY | _O_RDWR, _S_IREAD | _S_IWRITE); //ключи открытия файла
    output = open("out.txt", _O_BINARY | _O_WRONLY | _O_CREAT | _O_TRUNC, _S_IREAD | _S_IWRITE); //ключи открытия файла

    pfile.awrite(output); // связывание файла (assign)
    encode(); // кодирование

    close(input);
    close(output);

    // открытие входного и выходного файлов
    input = open("out.txt", _O_BINARY | _O_RDWR, _S_IREAD | _S_IWRITE); //ключи открытия файла
    output = open("data.txt", _O_BINARY | _O_WRONLY | _O_CREAT | _O_TRUNC, _S_IREAD | _S_IWRITE); //ключи открытия файла

    pfile.aread(input); // связывание файла (assign)
    decode(); // кодирование

    close(input);
    close(output);

    return 0;
}