enLZ77  LZ77 부호
deLZ77  LZ77 부호로부터의 복호

LZ77 부호
    long enLZ77(unsigned char *code, long clen,
                unsigned char *text, long tlen);

LZ77 부호로부터의 복호
    long deLZ77(unsigned char *text, long tlen,
                unsigned char *code, long clen);

LZ77 부호 함수에 대해
    code  (입출력) LZ77 부호를 격납하는 배열
    clen  (입력) 배열 code의 길이
    text  (입력) 텍스트를 격납하는 배열
    tlen  (입력) 배열 text의 길이

LZ77 부호로부터의 복호 함수에 대해
    text  (입출력) 텍스트를 격납하는 배열
    tlen  (입력) 배열 text의 길이
    code  (입력)  LZ77 부호를 격납하는 배열
    clen  (입력) 배열 code의 길이

LZ77 부호 함수에 대해
    LZ77 부호의 길이. encode에 실패했을 때는 -1L.

LZ77 부호로부터의 복호 함수에 대해
    텍스트의 길이. 복호에 실패했을 때는 -1L.

#define F       128           /* 최장 일치 캐릭터 라인의 길이의 상한 */
#define LOG2F   7             /* 2^7 = 128 */
#define N0      4096
#define LOG2N   12            /* 2^12 = 4096 */

#define N       (N0+F)        /* 슬라이드창의 크기 */

long enLZ77(unsigned char *code, long clen,
            unsigned char *text, long tlen)
{
    int      i, j;
    int      w, l, x;
    int      ww, ll;
    long     len;
    unsigned char *wintop, *winbrk;
    unsigned char *texttop, *textend;
    unsigned char prewin[N0];
    static int bit0[12] =
           {~1,~2,~4,~8,~16,~32,~64,~128,~256,~512,~1024,~2048};
    static int bit1[12] =
           { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048};

    for (i = 0; i < N0; i++) prewin[i] = 0;

    wintop = prewin; winbrk = wintop + N0;
    texttop = text;  textend = text + tlen;
    for (i = 7, len = 0; ; ) {
        unsigned char *wp;

        if (texttop >= textend) break;

        /* 최장 일치 캐릭터 라인을 찾아낸다 */
        w = l = 0;
        for (wp = wintop, ww = 0; ww < N0; ww++) {
            if (wp == winbrk) wp = text;
            if (*wp++ == *texttop) {
                unsigned char *p, *q;

                for (p = wp, q = texttop+1, ll = 1; ll < F; ll++) {
                    if (p == winbrk) p = text;
                    if (q == textend || *p++ ! = *q++) {
                        if (ll >= l) {
                            w = ww;
                            l = ll;
                        }
                        break;
                    }
                }
            }
        }
        x = *(texttop + l);

        /* 최장 일치 캐릭터 라인의 개시 위치를 출력 */
        for (j = LOG2N-1; j >= 0; j--) {
            if (w & bit1[j]) *code |= bit1[i];
            else             *code &= bit0[i];
            if (i-- == 0) {
                code++;
                if (++len > clen) return -1L;
                i = 7;
            }
        }

        /* 최장 일치 캐릭터 라인의 길이를 출력 */
        for (j = LOG2F-1; j >= 0; j--) {
            if (l & bit1[j]) *code |= bit1[i];
            else             *code &= bit0[i];
            if (i-- == 0) {
                code++;
                if (++len > clen) return -1L;
                i = 7;
            }
        }

        /* 최장 일치 캐릭터 라인의 다음의 문자를 출력 */
        for (j = 7; j >= 0; j--) {
            if (x & bit1[j]) *code |= bit1[i];
            else             *code &= bit0[i];
            if (i-- == 0) {
                code++;
                if (++len > clen) return -1L;
                i = 7;
            }
        }

        /* 슬라이드창을 뒤로 비켜 놓는다 */
        texttop += ++l;
        if (wintop + l >= winbrk) wintop = text + (l - (winbrk-wintop));
        else wintop += l;
    }
    if (i < 7) len++;
    return (len > clen) ?  -1L : len;
}

long deLZ77(unsigned char *text, long tlen,
            unsigned char *code, long clen)
{
    int      i, j;
    int      w, l, x;
    unsigned char *wintop, *winbrk, *texttop;
    unsigned char prewin[N0];
    long     c, len;
    static int bit1[12] =
           { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048};

    if (clen <= 0) return -1;

    for (i = 0; i < N0; i++) prewin[i] = 0;
    wintop = prewin; winbrk = wintop + N0;
    texttop = text;

    for (i = 7, len = 0, c = 1; ; ) {
        unsigned char *wp;

        w = l = x = 0;
        /* 최장 일치 캐릭터 라인의 개시 위치 */
        for (j = LOG2N-1; j >= 0; j--) {
            if (*code & bit1[i]) w |= bit1[j];
            if (i-- == 0) {
                code++;
                if (++c > clen) return -1L;
                i = 7;
            }
        }
        /* 최장 일치 캐릭터 라인의 길이 */
        for (j = LOG2F-1; j >= 0; j--) {
            if (*code & bit1[i]) l |= bit1[j];
            if (i-- == 0) {
                code++;
                if (++c > clen) return -1L;
                i = 7;
            }
        }
        /* 최장 일치 캐릭터 라인의 다음의 문자 */
        for (j = 7; j >= 0; j--) {
            if (*code & bit1[i]) x |= bit1[j];
            if (i-- == 0) {
                code++;
                ++c;
                i = 7;
            }
        }

        /* 캐릭터 라인을 복호 한다 */
        if ((wp = wintop + w) >= winbrk) wp = texttop + (w - (winbrk-wintop));
        for (j = l; j > 0; j--) {
            if (wp == winbrk) wp = texttop;
            *text++ = *wp++;
        }

        len += l++;
        
        if (c >= clen) break;

        /* 슬라이드창을 뒤로 비켜 놓는다 */
        *text++ = x;
        if (wintop + l >= winbrk) wintop = texttop + (l - (winbrk-wintop));
        else wintop += l;

        len++;
    }
    return len;
}

LZ77 부호에서는, 현재 부호를 실시하고 있는 문자를 포함한 캐릭터 라인을 슬라이드창이라고 불러, 그 중에 있는 캐릭터 라인이 참조의 대상이 된다. 또, 부호어는, m, l, x 로부터 된다 2 진수로 나타낸다.

m: 슬라이드창에 있는 최장 일치 캐릭터 라인의 위치
l: 슬라이드창에 있는 최장 일치 캐릭터 라인의 길이
x: 최장 일치 캐릭터 라인의 다음의 문자

캐릭터 라인이 슬라이드창에 존재하지 않았던 경우는 m = 0, l = 0 으로 한다. 또, 스 놀이 기구창이 부호어를 출력할 때마다, l+1 문자분 다음의 캐릭터 라인에 비켜 놓는다.

이와 같이, 최장 일치 캐릭터 라인을 과거의 텍스트로부터 찾아내고(사전의 참조라고도 말한다), 그 개시 위치와 길이를 부호어로서 사용하는 것이, LZ77 부호의 특징이다. 개시 위치와 길이에 관한 표현의 방법이나 최장 일치 캐릭터 라인의 탐색의 방법에 따라, 몇개의 바리에이션이 존재하고 있다.