encode.c

#include <stdint.h>
#include <string.h>

#include "lzss.h"

static uint8_t window[N];

void encodeLZSS(const uint8_t* pSrc, uint32_t srcSize, uint8_t* pDest, uint32_t* pEncodedSize)
{
    uint8_t* pOut = pDest;
    *pOut++ = (srcSize >>  0) & 0xFF;
    *pOut++ = (srcSize >>  8) & 0xFF;
    *pOut++ = (srcSize >> 16) & 0xFF;
    *pOut++ = (srcSize >> 24) & 0xFF;

    memset(window, 0, sizeof(window));
    int r = N - F;
    uint32_t i = 0;

    while (i < srcSize) {
        uint8_t flag = 0;
        uint8_t chunk[2 * 8];
        int chunkLen = 0;

        for (int m = 0x80; m != 0 && i < srcSize; m >>= 1) {
            unsigned matchLen = 0, matchOffset = 0;

            for (int j = 1; j < N; j++) {
                int len = 0;
                while (len < F && j > len && (i + len) < srcSize
                        && window[(r - j + len) & (N - 1)] == pSrc[i + len]) {
                    len++;
                }
                if (len > matchLen && len > 2) {
                    matchOffset = (r - j) & (N - 1);
                    matchLen = len;
                    if(len == F) {
                        break; // Found a long enough match
                    }
                }
            }

            if (matchLen > 2) {
                unsigned b1 = matchOffset & 0xFF;
                unsigned b2 = ((matchOffset >> 4) & 0xF0) | ((matchLen - 3) & 0x0F);
                chunk[chunkLen++] = b1;
                chunk[chunkLen++] = b2;

                for (int k = 0; k < matchLen; k++) {
                    window[r++] = window[(matchOffset + k) & (N - 1)];
                    r &= (N - 1);
                }
                i += matchLen;
            } else {
                flag |= m;
                chunk[chunkLen++] = window[r++] = pSrc[i++];
                r &= (N - 1);
            }
        }

        *pOut++ = flag;
        memcpy(pOut, chunk, chunkLen);
        pOut += chunkLen;
    }

    if (pEncodedSize) {
        *pEncodedSize = (uint32_t)(pOut - pDest);
    }
}