程式語言 - GNU - C/C++ - LZ77 Compress

main.c

#include <fcntl.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <zlib.h>

#define MAX_BUF_SIZE (32 * 1024 * 1024)

char lz[MAX_BUF_SIZE] = {0};
char file[MAX_BUF_SIZE] = {0};
char unlz[MAX_BUF_SIZE] = {0};

uint32_t lz77_compress(uint8_t *src, uint32_t slen, uint8_t *dst)
{
    uint8_t plen = 0, tlen = 0;
    uint16_t ppos = 0, tpos = 0, optr = 0;
    uint32_t cptr = 0, osize = 0, cpos = 0, oref = 0, lkb = 0, lka = 0;

    *((uint32_t*)dst) = slen;
    cptr = osize = 4;

    for (cpos = 0; cpos < slen; cpos++) {
        ppos = 0;
        plen = 0;
        for (tpos = 1; (tpos < 4096) && (tpos <= cpos); tpos++) {
            lkb = cpos - tpos;
            lka = cpos;
            for (tlen = 0; src[lka++] == src[lkb++]; tlen++) {
                if (tlen == 15) {
                    break;
                }
            }
            if (tlen > plen) {
                ppos = tpos;
                plen = tlen;
                if (plen == 15) {
                    break;
                }
            }
        }
        cpos += plen;
        if (plen && (cpos == slen)) {
            optr = (ppos << 4) | (plen - 1);
            oref = cpos - 1;
        }
        else {
            optr = (ppos << 4) | plen;
            oref = cpos;
        }
        *((uint32_t*)(dst + cptr)) = optr;
        cptr += 2;
        *(dst + cptr++) = *(src + oref);
        osize += 3;
    }
    return osize;
}

uint32_t lz77_decompress(uint8_t *src, uint8_t *dst)
{
    uint8_t plen = 0;
    uint16_t iptr = 0, ppos = 0;
    uint32_t cptr = 0, cpos = 0, poff = 0, usize = 0;

    usize = *((uint32_t*)src);
    cptr = 4;

    for (cpos = 0; cpos < usize; cpos++) {
        iptr = *((uint32_t*)(src + cptr));
        cptr += 2;
        ppos = iptr >> 4;
        plen = iptr & 15;
        if (ppos) {
            for (poff = cpos - ppos; plen > 0; plen--) {
                dst[cpos++] = dst[poff++];
            }
        }
        *(dst + cpos) = *(src + cptr++);
    }
    return cpos;
}

int main(int argc, char **argv)
{
    int r = 0;
    int fd = -1;

    fd = open("test.bin", O_RDONLY);
    r = read(fd, file, sizeof(file));
    close(fd);
    printf("file length: %d\n", r);

    r = lz77_compress(file, r, lz);
    fd = open("test.lz77", O_CREAT | O_WRONLY, 0644);
    write(fd, lz, r);
    close(fd);
    printf("compress length: %d\n", r);

    r = lz77_decompress(lz, unlz);
    fd = open("test.unlz77", O_CREAT | O_WRONLY, 0644);
    write(fd, unlz, r);
    close(fd);
    printf("decompress length: %d\n", r);
    return 0;
}

編譯、執行

$ gcc main.c -o main
$ echo "123" > test.bin
$ ./main
    file length: 4
    compress length: 16
    decompress length: 4

$ cat test.unlz77
    123