Реализация алгоритма RLE на C. Алгоритм сжатия RLE на C

September 9, 2018 01:00

Алгоритм RLE - простейший из всех алгоритмов сжатия. Принцип его работы заключается в кодировании повторов. Это значит, что последовательность одинаковых значений превращается в пару (количество, символ). Чтобы показать это наглядно, попробуем разобрать пример.

Дано: строка AAABCCC. Получить: сжатую строку.

Решение: 3AB3C.

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

#define RLE_BLOCK_SIZE 3
#define RLE_SIGN "RLE"
#define BYTES_FOR_DECIDE_SIGN 1000

// Реализация алгоритма RLE 


typedef struct rle_header {
    u_char rle[3];
    long file_size;
    u_char sign;
} RLEheader;


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

void fatal(const char *func_name) {
    if (func_name)
        fprintf(stderr, "[!]\t%s %s\n", func_name, strerror(errno));
    exit(EXIT_FAILURE);
}

u_char getsignRLE(void *buf, size_t size) {
    size_t values[256] = { 0 };
    size_t bytes_count = BYTES_FOR_DECIDE_SIGN;
    u_char current_byte;

    if (size < BYTES_FOR_DECIDE_SIGN) {
        bytes_count = size;
    }

    for (size_t i = 0; i < bytes_count; i++) {
        current_byte = *(char *)(buf + i);
        values[current_byte]++;
    }

    size_t min = 0;
    u_int16_t index_min = 0;

    for (u_int16_t i = 0; i < 256; ++i) {
        if (values[i] < min){
            min = values[i];
            index_min = i;
        }
    }

    return (u_char)index_min;
}

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

    if (fd == -1) {
        fatal("encodeRLE()");
    }

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

    u_char *buf = malloc(fs.st_size);

    if (buf == NULL) {
        close(fd);
        fatal("encodeRLE() File is too big.");
    }

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

    if (!strncmp((char*)((RLEheader*)buf)->rle, RLE_SIGN, strlen(RLE_SIGN))) {
        fprintf(stderr, "[!]\t%s %s\n", filename, "file already compressed with RLE!");
        free(buf);
        fatal(NULL);
    }

    u_char sign = getsignRLE(buf, fs.st_size);

    RLEheader header;
    header.file_size = fs.st_size;
    header.sign = sign;

    u_char *debuf = malloc(fs.st_size + sizeof(RLEheader));

    memcpy(&header, RLE_SIGN, strlen(RLE_SIGN));
    memcpy(debuf, &header, sizeof(RLEheader));
    long j = sizeof(RLEheader);

    u_char current, counter, block[RLE_BLOCK_SIZE] = { sign, 0, 0 };

    for (long i = 0; i < fs.st_size;) {
        current = buf[i];
        counter = 1;

        while (current == buf[++i] && i < fs.st_size && counter < 0xFF) {
            counter++;
        }

        if (counter > RLE_BLOCK_SIZE || current == sign) {
            block[1] = counter;
            block[2] = current;

            memcpy(debuf + j, block, RLE_BLOCK_SIZE);
            j += RLE_BLOCK_SIZE;

        } else {
            memcpy(debuf + j, buf + i - counter, counter);
            j += counter;
        }

        if (j >= fs.st_size) {                                  // если упакованый файл больше чем исходный - не пакуем
            printf("[*]\tIncompressible file. Destination size greater than source.\n");
            free(buf);
            free(debuf);
            exit(EXIT_SUCCESS);
        }
    }

    if ((fd = open(filename, O_WRONLY | O_TRUNC)) == -1) {
        free(buf);
        free(debuf);
        fatal("encodeRLE()");
    }

    write(fd, debuf, j);

    close(fd);
    free(buf);
    free(debuf);

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

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

    if (fd == -1) {
        fatal("decodeRLE()");
    }

    struct stat fs;
    fstat(fd, &fs);                                       // чтение размера упакованого файла

    u_char *buf = malloc(fs.st_size);
    read(fd, buf, fs.st_size);                            // запись файла в буфер
    close(fd);

    if (strncmp((char*)((RLEheader*)buf)->rle, RLE_SIGN, strlen(RLE_SIGN))) {
        fprintf(stderr, "[!]\t%s %s\n", filename, "not RLE compressed file!");
        free(buf);
        fatal(NULL);
    }

    u_char *ch_buf = buf + sizeof(RLEheader);             // указатель на начало данных
    u_char *debuf = malloc(((RLEheader*)buf)->file_size); // память под распакованый файл
    u_char sign = ((RLEheader*)buf)->sign;                // чтение сигнатуры

    for (long i = 0, j = 0; i < fs.st_size - (long)sizeof(RLEheader);) {
        if (ch_buf[i] == sign) {                                   // если встретилась сигнатура
            for (u_char k = 0; k < ch_buf[i + 1]; ++k, ++j)        // запись байт, указаных в блоке
                debuf[j] = ch_buf[i + 2];
            i += RLE_BLOCK_SIZE;
        } else {
            debuf[j++] = ch_buf[i++];
        }
    }

    fd = open(filename, O_WRONLY | O_TRUNC);

    if (fd == -1) {
        free(buf);
        fatal("decodeRLE()");
    }

    write(fd, debuf, ((RLEheader*)buf)->file_size);
    close(fd);

    free(buf);
    free(debuf);
}




int main(int argc, char *argv[])
{
    if (argc < 3) {
        usage(argv[0]);
    }

    if (!strncmp(argv[2], "--encode", strlen("--encode"))) {
        encodeRLE(argv[1]);                                         
    } else if (!strncmp(argv[2], "--decode", strlen("--decode"))) {
        decodeRLE(argv[1]);                                         
    }

    return 0;
}