LZ77 на C, реализация алгоритма LZ77 на C

September 6, 2018 21:08

LZ77 и LZ78 — алгоритмы сжатия без потерь, опубликованные в статьях израильских математиков Авраама Лемпеля и Яакова Зива в 1977 и 1978 годах. Эти алгоритмы — наиболее известные варианты в семействе LZ*, которое включает в себя также LZW, LZSS, LZMA и другие алгоритмы.

Оба алгоритма относятся к словарным методам, в отличие от других методов уменьшения избыточности, таких как RLE и арифметическое сжатие. LZ77 является алгоритмом со «скользящим окном», что эквивалентно неявному использованию словарного подхода, впервые предложенного в LZ78.

Основная идея алгоритма это замена повторного вхождения строки ссылкой на одну из предыдущих позиций вхождения. Для этого используют метод скользящего окна. Скользящее окно можно представить в виде динамической структуры данных, которая организована так, чтобы запоминать «сказанную» ранее информацию и предоставлять к ней доступ. Таким образом, сам процесс сжимающего кодирования согласно LZ77 напоминает написание программы, команды которой позволяют обращаться к элементам скользящего окна, и вместо значений сжимаемой последовательности вставлять ссылки на эти значения в скользящем окне.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys stat.h="">
#include <fcntl.h>
#include <errno.h>
#include <sys types.h="">
#include <stdint.h>

#define LZ77_SIGN "LZ77"



typedef struct lz77_block {
    u_char symbol;
    u_int16_t offset, count;
} __attribute__((packed)) lz_block;


typedef struct lz77_header {
    char sign[4];
    size_t unpacked_size;
} __attribute__((packed)) lz_header;

size_t lz77_encode(const char *src, size_t len, char *dst);

size_t lz77_decode(const char *src, size_t len, char *dst);

void lz77_encode_file(const char *filename);

void lz77_decode_file(const char *filename);

void lz77_decode_file(const char *filename) {
    int fd = open(filename, O_RDONLY);

    if (fd == -1) {
        fprintf(stderr,"[!]\tlz77_decode_file() %s\n", strerror(errno));
        exit(EXIT_FAILURE);
    }

    struct stat fs;
    fstat(fd, &fs);

    char *src_buf = malloc(fs.st_size);
    read(fd, src_buf, fs.st_size);
    close(fd);

    if (strncmp(((lz_header*)src_buf)->sign, LZ77_SIGN, strlen(LZ77_SIGN))) {
        fprintf(stderr, "[!]\tFormat file is not LZ77!\n");
        free(src_buf);
        exit(EXIT_FAILURE);
    }

    char *dst_buf = malloc(((lz_header*)src_buf)->unpacked_size);

    fd = open(filename, O_WRONLY | O_TRUNC);
    write(fd, dst_buf, lz77_decode(src_buf + sizeof(lz_header), fs.st_size - sizeof(lz_header), dst_buf));

    close(fd);
    free(src_buf);
    free(dst_buf);
}

void lz77_encode_file(const char *filename) {
    int fd = open(filename, O_RDONLY);

    if (fd == -1) {
        fprintf(stderr,"[!]\tlz77_encode_file() %s\n", strerror(errno));
        exit(EXIT_FAILURE);
    }
    struct stat fs;

    fstat(fd, &fs);
    char *src_buf = malloc(fs.st_size);

    read(fd, src_buf, fs.st_size);
    close(fd);

    if (!strncmp(((lz_header*)src_buf)->sign, LZ77_SIGN, strlen(LZ77_SIGN))) {
        fprintf(stderr, "[!]\tFile already compressed in LZ77!\n");
        free(src_buf);
        exit(EXIT_FAILURE);
    }

    char *dst_buf = calloc(fs.st_size, sizeof(lz_block));

    lz_header header;
    header.unpacked_size = fs.st_size;
    strncpy((char*)&header, LZ77_SIGN, strlen(LZ77_SIGN));

    size_t dst_len = lz77_encode(src_buf, fs.st_size, dst_buf);

    fd = open(filename, O_TRUNC | O_WRONLY);

    write(fd, &header, sizeof(lz_header));
    write(fd, dst_buf, dst_len);

    close(fd);

    free(src_buf);
    free(dst_buf);

    printf("[*]\tCompressed %0.2f %%\n", (float)dst_len / fs.st_size * 100);
}


size_t lz77_encode(const char *src, size_t len, char *dst) {

    lz_block *block = (lz_block*)dst;
    size_t count, save_i;

    for (size_t i = 0; i < len; ++i, ++block) {
        block->symbol = src[i];

        for (size_t j = (i / UINT16_MAX) * UINT16_MAX; j < i; ++j) {
            if (src[i] == src[j]) {
                save_i = i;

                do {
                    i++;
                    j++;
                } while (src[i] == src[j] && j != save_i);

                count = i - save_i;

                if (count > block->count) {
                    block->count = count - 1;
                    block->offset = i - j;
                }

                i = save_i;
            }
        }

        i += block->count;
    }

    return (char*)block - dst;
}


size_t lz77_decode(const char *src, size_t len, char *dst) {
    size_t dst_size = 0;                                                      // размер (он же индекс) в распакованой строке

    for (lz_block *i = (lz_block*)src; i < (lz_block*)src + (len / sizeof(lz_block)); ++i) {
        dst[dst_size++] = i->symbol;                                          // пишем из него первый символ, заодно двигаем указатель назначения
        memcpy(dst + dst_size, dst + dst_size - i->offset, i->count);         // копируем столько символов, сколько указано в блоке
        dst_size += i->count;
    }

    return dst_size;
}


void usage(const char *argv0) {
    printf("Usage:\t%s <filename> [--encode|--decode]\n", argv0);
    exit(EXIT_SUCCESS);
}


int main(int argc, char *argv[]) {

    if (argc != 3) {
        usage(argv[0]);
    }

    if (!strncmp(argv[2], "--encode", strlen("--encode"))) {
        lz77_encode_file(argv[1]);
    } else if (!strncmp(argv[2], "--decode", strlen("--decode"))) {
        lz77_decode_file(argv[1]);
    } else {
        usage(argv[0]);
    }

    return 0;
}