[펌] LZ 압축 알고리즘

블로그 > 김선우님의 블로그
http://blog.naver.com/ksw7998/100011413524

0. LZ 알고리즘을 소개하기 앞서

LZ77 압축 알고리즘은 1977년 Lempel과 Ziv가 고안해낸 알고리즘으로 LZ77, LZSS, LZ78, LZW 등 많은 변형이 존재합니다. 이 알고리즘을 모두 설명하는 것은 본 강좌의 목적에도 맞지 않고 분량만 늘어날 우려가 있어 LZ77과 LZSS에 대해서만 간략하게 설명하려 합니다. LZ78, LZW 등은 모두 기본적인 개념은 같으니 필요하신 분은 직접 찾아보시길 바랍니다. 게다가 이 강좌를 쓰는 필자조차도 저 알고리즘을 모두 알고 있는게 아닌데다가 사실 LZ77과 LZSS가 정말로 어떻게 다른지에 대해서도 정확히 알지 못합니다. -_-;;; 따라서 본 강좌의 내용이 LZ알고리즘을 설명하는 측면에서는 미흡할 가능성이 많으나 GBA에서 사용되는 알고리즘을 이해하는데는 무리가 없을 테니 걱정은 저리로 던져주세요.

1. LZ 알고리즘

전 강좌에서 RLE 알고리즘을 알아보았다. 연속되는 데이터가 많이 존재하는 경우 RLE방식도 상당히 높은 효율을 보여주기는 하나 abababab와 같이 같은 패턴이 연속되는 경우 RLE로는 압축을 할 수 가 없다. 따라서 이 경우 dictionary, 즉 사전 이라는 개념을 사용하여 압축하는 방법을 사용하면 높은 압축률로 압축하는 것이 가능해진다. dictionary는 정적 사전(static dictionary)와 동적 사전(dynamic dictionary)로 구분한다는 얘기를 어디선가 얼핏 들은 것 같기도 하나 확실치 않은 정보이니 그냥 잊으셔도 좋다. 어쨌든 abababaaaa라는 데이터가 존재할 경우 1. ab, 2. aaaaa 라고 정의하고 1112이라고 저장하면 데이터의 크기를 줄일 수가 있는데 LZ알고리즘은 이 개념으로부터 시작하게 된다.

2. 실제로 어떻게 적용하는가

1) LZ77

먼저 LZ알고리즘을 설명하기 전에 알아두어야 할 용어들이 있다. Input Stream, Coding Position, Lookahead Buffer, Window 이다. r'Arc 님께서 자유게시판에 올려주신 http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/ 의 설명에 따르면 각각은 다음과 같다.

Input Stream : 압축될 데이터들의 순차적 집합(sequence)
Coding Position : 이제 곧 압축할 데이터. Lookahead Buffer 시작 지점
Lookahead buffer : Coding Position 이후의 데이터의 순차적 집합
Window : Coding Position 이전의 데이터

먼저 설명만으로는 이해하기가 매우 난해하니 그림으로 설명하면 다음과 같다.

00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 14 15 ... => Input Stream
----------------------- | ================================
Window Coding Position Lookahead buffer

현재의 그림은 00 01 02 03 04 05 06 07 08 까지가 압축이 된 상태이고 09가 이제 곧 압축이 될 데이터들의 시작지점이며 09를 포함한 그 뒤의 데이터들이 lookahead buffer라는 것을 의미한다. 여기서 주의할 점은 window가 압축된 데이터를 의미하지 압축한 결과와는 다르다는 점이다. 이 점은 꼭 염두에 두어야 한다. Window의 데이터들이 압축된 결과는 다른 공간에 저장되어 있다고 생각해야 한다.

LZ77은 현재 Coding position이후의 lookahead buffer에서 window내의 데이터들과 같은 패턴을 갖는 데이터가 존재하는지 검사하고, 만약 window에 그런 데이터가 존재할 경우 Coding Position에서부터의 상대적인 위치와 크기를 표현하게 된다. 이 표현은 (A,B)라고 사용하도록 한다. (A,B)는 "Coding Position으로부터 A만큼 앞에서부터 B만큼의 데이터"를 의미한다. 그리고 Coding position으로부터 B번째의 데이터를 그대로 출력하고 Coding Position을 B+1 만큼 오른쪽으로 이동시킨다.

이제 예시를 통해 구체적인 압축 알고리즘을 알아보도록 하자. 설명의 편의를 위해 데이터는 알파벳으로 표현하도록 한다.

우선 Input Stream, 즉 압축하려고 하는 데이터가 다음과 같다고 생각하자.

A A B B C C D A A B B A A B B
| ===========================

먼저 해야할 일은 Coding Position 을 맨 처음 byte로 옮기는 일이다. 그러면 window에는 아무 데이터가 없고 coding position은 A가 되고 Lookahead buffer는 A A B B C C ... 이 될 것이다. Window에 아무 데이터가 없으므로 Lookahead buffer에서 window와 같은 패턴을 찾을 수 없고 따라서 (0,0)과 A를 출력하고 0+1, 즉 1만큼 coding position을 이동시킨다. 따라서 압축결과는 (0,0) A 가 된다.
_ _
A A B B C C D A A B B A A B B
- | ==========================

Output : (0,0) A

두번째 A가 Coding Position이 되는데 이 때 window에서 lookahead buffer와 같은 패턴 "A" 가 존재하므로 coding position 에서의 상대적인 위치와 그 길이를 저장하면 되는 것이다. 이 때 상대적인 위치는 왼쪽으로 몇 바이트인가 를 저장해주게 된다. 따라서 (1,1) 을 출력한 후 coding position으로부터 오른쪽으로 1번째 문자를 출력하고 1+1, 즉 2만큼 Coding position을 이동시킨다. 따라서 그 결과는 다음과 같다.
_ _
A A B B C C D A A B B A A B B
----- | ======================

Output : (0,0) A (1,1) B

lookahead buffer에서 window와 같은 패턴을 갖는지 검사한다. "B" 가 가장 긴 패턴이 되므로 (1,1)을 출력한 후 C를 출력하고 coding position 은 2만큼 이동시킨다.
_ _
A A B B C C D A A B B A A B B
--------- | =================

Output : (0,0) A (1,1) B (1,1) C

C도 마찬가지로 같은 패턴이 존재하므로 (1,1) D를 출력하고 coding position을 2만큼 이동시킨다.
_ _ _ _ _ _ _ _
A A B B C C D A A B B A A B B
-------------- | =============

Output : (0,0) A (1,1) B (1,1) C (1,1) D

AABB가 coding position으로부터 7만큼 앞에 길이 4만큼 같은 패턴을 가지므로 (7,4)를 입력하고 현재 Coding position으로부터 오른쪽으로 4번째의 data를 출력 후 coding position은 4+1=5만큼 이동시킨다.
_ _ _ _ _ _
A A B B C C D A A B B A A B B
------------------------ | ===

Output : (0,0) A (1,1) B (1,1) C (1,1) D (7,4) A

ABB가 현재 coding position으로부터 4번째 앞에 길이 3만큼 같은 패턴을 가지므로 (4,3)을 출력하면 압축이 끝나게 된다.
따라서 압축한 결과는 (0,0) A (1,1) B (1,1) C (1,1) D (7,4) A (4,3) 이다.

위의 압축한 결과를 해제하는 과정도 살펴보자. 이 때 중요한 점은 window에 들어가는 data가 압축을 푼 후의 data라는 점이다.

(0,0) A (1,1) B (1,1) C (1,1) D (7,4) A (4,3)
| ==================================
Output :

(0,0)을 읽고 0만큼 앞에 0만큼의 data를 출력한다. 즉, 아무것도 출력하지 않는다.

A (1,1) B (1,1) C (1,1) D (7,4) A (4,3)
| ================================
Output :

A를 출력한다.

A (1,1) B (1,1) C (1,1) D (7,4) A (4,3)
- | ===========================
Output : A

(1,1)을 읽고 1만큼 앞에서 1개의 data를 출력한다. 1만큼 앞에서 1개의 data는 A이므로 window에는 A가 들어가게 된다.

A A B (1,1) C (1,1) D (7,4) A (4,3)
--- | ========================
Output : A A

B를 출력한다.

A A B (1,1) C (1,1) D (7,4) A (4,3)
------ | ====================
Output : A A B

(1,1)을 읽고 1만큼 앞에서 1개의 data를 출력한다. B를 출력하고 window에는 B가 들어가게 된다.

A A B B C (1,1) D (7,4) A (4,3)
------- | ==================
Output : A A B B

C를 출력한다.

A A B B C (1,1) D (7,4) A (4,3)
--------- | =============
Output : A A B B C

(1,1)을 읽고 1만큼 앞에서 1개의 data를 출력한다. C를 출력하고 window에는 C가 들어가게 된다.

A A B B C C D (7,4) A (4,3)
------------ | ===========
Output : A A B B C C

D를 출력한다.

A A B B C C D (7,4) A (4,3)
-------------- | ======
Output : A A B B C C D

(7,4)를 읽고 7만큼 앞에서 4개의 data, 즉 A A B B를 출력하고 window에 A A B B를 넣는다.

A A B B C C D A A B B A (4,3)
--------------------- | ====
Output : A A B B C C D A A B B

A를 출력한다.

A A B B C C D A A B B A (4,3)
------------------------ |
Output : A A B B C C D A A B B A

(4,3)을 읽고 4만큼 앞에서 3개의 data, 즉 A B B를 출력하고 window에 A B B를 넣는다.

A A B B C C D A A B B A A B B
------------------------------ |
Output : A A B B C C D A A B B A A B B

위에서 압축한 데이터와 같음을 알 수 있다. 이 과정이 LZ77알고리즘이 data를 압축하고 해제하는 과정이다. 복잡한 과정인 듯 하나 차근차근 생각해보면 그리 어렵지 않으니 이해가 되지 않은 분은 다시 한번 따라가면 금방 이해할 수 있을 것이다. 여기서 문제 하나. DATA의 양이 매우 방대해질 경우 lookahead buffer와 window는 어떻게 해야 할까? 같은 pattern을 찾는 일이 사람이 눈으로 직접 찾기에는 그리 어렵지 않은 일이나 같은 pattern을 찾는 알고리즘은 그 계산에 상당히 많은 시간을 필요로 한다. 따라서 보통 LZ알고리즘을 사용할 때는 lookahead buffer와 window의 크기를 제한하고 사용한다. 만약 window의 크기는 4이고 lookahead buffer의 크기는 3이라면 압축하는 중의 한 과정은 다음과 같아진다.

A A B B C C D A A B B A A B B
------- | =====

Output : (0,0) A (1,1) B (1,1) C

이 때 window와 lookahead buffer는 각각 queue로서 동작하게 된다. queue가 뭔지 모르는 사람은 queue, FIFO로 검색해보면 쉽게 그 설명을 찾을 수 있다.
GBA에서는 0x12의 lookahead buffer와 0x1000의 window를 사용하는 것으로 알려져 있다. 직접 확인해본 결과가 아니니 정확한 값이 아니라면 연락바란다.

@. 헉헉.. LZ77 알고리즘 생각보다 설명하기가 매우 힘들군요 -_-;; 몇 시간째 썼다 지웠다 하는 중에 좀 괜찮으려나 하는 설명만 뽑아서 정리했습니다. 이 과정에서 매끄럽지 않은 문장이 생길 수 있으니 그럴 경우 코멘트 달아주세요.

@2. LZ 알고리즘은 2부로 나눕니다;;; 2부에서는 LZSS는 어떻게 다른가 와 GBA에서는 어떻게 저장하는가를 다룰 생각입니다.

@3. 허프만 압축을 사용하는 롬을 찾지 못해 허프만 압축은 기본적인 원리만 소개할 생각입니다. 허프만 압축을 사용하는 롬을 발견하시면 제보(-_-;;) 부탁드립니다.

0. 저번 강좌를 올린지 어느새 일주일이나 지나버렸군요 -.-;;; 울트라에딧만으로 대사를 모두 한글화하려니 노가다가 장난이 아니라 그냥 직접 툴을 만들자 라는 생각에 VC++을 좀 붙들고 있었더니 밀린 숙제와 레포트덕에 시간이 전혀 안나더라구요;;;; 기다리신 분들(-_-;; 있나요;;;;) 죄송합니다. 저번 강좌에 이어 LZSS 들어가겠슴다~

2) LZSS

LZSS알고리즘은 LZ77과 거의 모든 알고리즘이 동일하다. 차이점이 있다면 LZ77에서의 단점을 보완했다는 점이다. LZ77은 알다시피 ((포인터,길이) 데이터) 와 같은 형태가 반복되는 구조로 되어있다. 저번 강좌에서 직접 주어진 데이타를 압축한 결과에서 볼 수 있듯이 임의의 데이터에 대해 압축을 시도했을 때 (0,0)과 같은 형태가 자주 입력될 것이란 걸 예상할 수 있고, (1,1)이나 (2,2)는 실제로는 전혀 압축이 되지 않는다는 점도 알 수 있을 것이다. 데이터를 저장할 때 (포인터,길이) 정보가 약 두바이트 내지는 세바이트 정도가 되는데 이 정보를 이용하여 압축을 푼 결과가 1~2바이트 뿐이라면 전혀 압축되지 않은 데다 오히려 더 많은 공간을 차지하게 되는 경우도 있다. 따라서 LZSS에서는 LZ77에서의 이러한 단점을 보안하여 좀 더 높은 압축률을 갖게 된 알고리즘이다.
우선 (0,0)과 같은 (포인터,길이) 가 저장되지 않게 하기 위해 LZSS에서는 key byte 내지는 separator를 사용하는 경우가 많다. key byte는 GBA의 자체압축에서 사용하고 separator의 경우 구현의 간단함으로 인해 필자가-_- 자주 사용하는 방식이다. 다만 separator의 경우 데이터 자체에 separator와 같은 데이터가 존재하는 골때리는 경우가 생기므로 그래픽 자료에는 적합하지 않으나 텍스트 데이터에는 사용하지 않는 문자가 존재하기 마련이므로 separator의 사용이 용이하다. 허나 강좌의 목적이 GBA에서 사용하는 압축방법을 소개하는데 있고 하니 key byte로 표현하는 방법을 설명하도록 한다.
또한 압축을 풀었을 때 그 실제적인 크기가 (포인터, 길이) 정보보다 작은 경우를 막기 위해 LZSS에서는 최소길이를 정해놓고 패턴의 길이가 이 최소길이보다 클 경우에는 압축을 시도하도록 되어 있다. 이 min_length는 알고리즘을 구현하는 프로그래머에 의해 정해지며 (포인터,길이)정보가 실제적으로 몇 바이트를 이용하여 저장되는가에 따라 정해지게 된다.

우선 간단하게 LZSS는 어떤 방식으로 인코딩, 디코딩하는지에 대해 알아보도록 하자. 참고로 압축,해제하는 과정을 인코딩, 디코딩으로 표현하는 경우가 대부분이므로 가능한한 encoding, decoding으로 병행하여 표현하도록 하니 참고하도록 하자.

저번강좌에서도 압축하는데 사용했던 데이터를 이용하여 압축하는 과정을 살펴보도록 하자. 우선 주어진 데이터들을 lookahead buffer에 모두 저장한 후, coding position을 이동시켜가며 압축을 하도록 한다. 이 점은 LZ시리즈에서 대부분 변하지 않는 기본적인 방식이므로 저번 강좌를 다시 확인하여 lookahead buffer, coding position, sliding window 등의 용어를 정확히 알도록 하자. 그리고 예제에서 사용하는 최소길이는 2로 정하도록 한다.

A A B B C C D A A B B A A B B
| ============================

window에 저장된 정보가 아무것도 존재하지 않으므로 A를 그대로 출력하고 이를 윈도우에 저장한다. 압축을 시작할 당시 (0,0)을 출력하는 LZ77과는 그 시작이 다르다는 것을 알 수 있을 것이다.

A A B B C C D A A B B A A B B
- | ==========================
Output : A

coding position이 두번째 A가 되었다. lookahead buffer에서 window와 같은 패턴을 찾을 수 있는가? A와 A가 같으니 같은 패턴을 찾을 수 있다 가 답이 되겠지만 LZSS에서는 min_length, 즉 예제에서의 2보다 작은 길이가 되므로 압축을 하지 않는다. 따라서 A를 그대로 출력하고 coding position을 한바이트 이동시킨다.

A A B B C C D A A B B A A B B
--- | ========================
Output : A A

B B C C D에 대해서는 앞의 A와 같은 과정을 거친다. 즉, 압축을 하지 않는다. 따라서 D까지 인코딩한 결과는 다음과 같다.

A A B B C C D A A B B A A B B
------------- | ==============
Output : A A B B C C D

자, window와 lookahead buffer를 살펴보자. 같은 패턴이 있는가? A A B B라는 같은 패턴이 존재하고 이 길이가 최소길이 이상이므로 이 때 비로소 lookahead buffer의 A A B B를 압축하도록 하게 되는 것이다. 압축할 때의 정보는 LZ77과 같이 (포인터, 길이)를 이용하도록 한다. A A B B가 7번째 앞에서부터 4바이트 같으므로 (7,4)를 저장하면 된다.

A A B B C C D A A B B A A B B
---------------------- | =====
Output : A A B B C C D (7,4)

역시 Lookahead buffer에 A A B B가 저장되어 있고 window에 A A B B가 두번 출현한다. 이 경우 어떤 패턴을 선택할 것인가에 대한 문제는 전적으로 프로그래머에게 달려있다. 사실 어느 패턴을 선택하든 그 결과는 같다. (11,4)로 표현하든 (4,4)로 표현하든 (p, len) 은 항상 일정한 크기를 차지하도록 되어 있기 때문이다. 여러 LZSS 알고리즘의 구현을 살펴본 결과 대부분의 경우 후자를 택하도록 되어 있으니 참고하도록 하자. 따라서 마저 압축하면 그 결과는 다음과 같다.

A A B B C C D A A B B A A B B
----------------------------- |
Output : A A B B C C D (7,4) (4,4)

(p, len)이 2byte를 차지한다고 생각하면 15 byte의 데이터를 압축한 결과가 11 byte로 압축되었음을 알 수 있다. LZ77로 같은 데이터를 압축했을 때의 결과가 몇 byte가 되는지를 직접 계산해보자. (p,len)이 5개, data가 5개이므로 15 byte로 LZ77에서보다 압축효율이 높아졌다는 것을 확인할 수 있을 것이다.

역시 LZ77에서와 같이 이 데이터를 이용하여 디코딩하는 과정을 살펴보도록 하자.

A A B B C C D (7,4) (4,4)
| ======================

A A B B C C D의 경우 전혀 압축되어 있지 않으므로 차례대로 한바이트씩 출력하고 coding position을 이동시키면 된다. 그 결과는 다음과 같다.

A A B B C C D (7,4) (4,4)
-------------- | =======
Output : A A B B C C D

(7,4)로 압축 정보가 나타났다. 7번째 앞쪽에서부터 4개의 데이터이므로 A A B B를 출력하고 window에도 A A B B 를 저장하도록 한다. 인코딩 알고리즘이 LZ77과 거의 다를바가 없었듯이 디코딩 알고리즘도 LZ77과 크게 다르지 않다.

A A B B C C D A A B B (4,4)
---------------------- | ==
Output : A A B B C C D A A B B

(4,4)도 마찬가지로 4번째 앞에서부터 4개의 데이터, 즉 A A B B를 의미한다. 따라서 디코딩한 결과는 다음과 같다.

A A B B C C D A A B B A A B B
----------------------------- |
Output : A A B B C C D A A B B A A B B

디코딩한 결과와 원본 데이터를 비교해보도록 하자.

3. GBA에서는

이제 기본적인 LZ77과 LZSS의 encoding, decoding 알고리즘을 살펴보았으니 GBA에서는 어떻게 압축하고 저장하는가에 대해 알아보도록 한다. GBA의 bios call의 이름이 LZ77UnCompWram과 LZ77UnCompVram으로 LZ77알고리즘을 사용한 듯 보이나 실제적인 구조는 LZSS와 같다. 닌텐도의 계략인지-_- 어떤 이유에서인지는 알 수 없으나 데이터의 압축구조가 LZSS에 가까우므로 이 점 유념해두길 바란다.
그럼 GBA에서 사용한 LZSS알고리즘은 어떻게 데이터와 (p,len)을 구별할 수 있을까? 차근차근 읽어보신 분이라면 key byte를 이용한다고 하지 않았나? 라고 생각할 수 있을 테니 언제 그런 말을 했는지 기억나지 않으신 분은 이 문서에서 (3655, 480)가 어느 지점을 의미하는지 디코딩하여 다시 읽어보도록 하자.
key byte는 어떤 구조로 되어 있을까에 대한 답은 대략적인 데이터들이 어떤 덩어리로 엮여-_-져 있나를 먼저 아는 것이 이해가 빠를 것이라 생각한다. 그림으로 표현하면 데이터들의 뭉텡이는 다음과 같이 구성되어 있다.

┌──────┐┌─────┐┌───┐┌───┐┌───┐┌───┐
│header 4byte││key 1byte ││덩어리││덩어리││덩어리││덩어리│
└──────┘└─────┘└───┘└───┘└───┘└───┘
┌───┐┌───┐┌───┐┌───┐
│덩어리││덩어리││덩어리││덩어리│
└───┘└───┘└───┘└───┘
┌─────┐┌───┐┌───┐┌───┐┌───┐
│key 1byte ││덩어리││덩어리││덩어리││덩어리│
└─────┘└───┘└───┘└───┘└───┘
┌───┐┌───┐┌───┐┌───┐
│덩어리││덩어리││덩어리││덩어리│
└───┘└───┘└───┘└───┘
.
.
.

header는 RLE방식과 같다. LZ으로 압축했음을 표현하는 0x10과 디코딩한 데이터의 크기를 알리는 3byte가 header 4byte가 된다. 그 이후부터는 key byte와 8개의 덩어리가 연속되는데 이 덩어리는 key byte에서의 bit에 따라 (p,len)인지 압축되지 않은 데이터인지가 결정되게 되는 것이다.
1 byte는 8bit이므로 key byte가 0x00 이라면 0000 0000 을 의미하는데 이 때 앞에서부터의 각 1bit씩이 각 덩어리가 압축되어 있는지에 대한 정보를 담고 있는 것이다. 따라서 역시 그림으로 살펴보자면 key byte가 0x00일 경우 8개의 data가 존재한다는 것이고

┌──┐┌──┐┌──┐┌──┐┌──┐┌──┐┌──┐┌──┐┌──┐
│0x00││data││data││data││data││data││data││data││data│
└──┘└──┘└──┘└──┘└──┘└──┘└──┘└──┘└──┘

key byte가 0x33 (0011 0011)이라면 다음과 같다는 뜻이다.

┌──┐┌──┐┌──┐┌────┐┌────┐┌──┐┌──┐┌────┐┌────┐
│0x33││data││data││(p,len) ││(p,len) │ │data││data││(p,len) ││(p,len) │
└──┘└──┘└──┘└────┘└────┘└──┘└──┘└────┘└────┘

즉, 디코딩하는 과정은 요약하면 다음과 같다. key byte를 읽고, 데이타 덩어리를 8개를 읽는데 이 데이타 덩어리가 압축이 되었는가 되지 않았는가에 대한 정보를 key byte의 각 bit로부터 얻어 각각의 덩어리를 디코딩한 후 이를 출력하는 것이다. 이 때 GBA에서 min_length는 3을 이용한다. (p,len)은 두바이트로 이루어져 있는데 p와 len이 일정한 bit로 쪼개어져 저장되어 있다.

0000 0000 0000 0000
^^^^ ^^^^^^^^^^^^^^^
len pointer

즉, (p,len)을 의미하는 두 바이트 중, 앞 바이트에서의 상위 4비트가 len을 의미하고 앞 바이트에서의 하위 4bit와 뒷 바이트의 8bit가 pointer를 의미한다. 이 때 RLE와 마찬가지로 실제적인 패턴의 길이에서 3을 뺀 수치가 len에 저장되어 있고, 패턴의 위치에서 1을 뺀 수치가 pointer에 저장되어 있다. 무슨 말이냐면 압축된 데이터 덩어리가 0x30 0x01이라면 0011 0000 0000 0001 이므로 len은 0011+3, 즉 패턴의 길이가 3+3으로 6개이고 그 위치는 0000 0000 0001 +1, 즉 2번째 앞에서부터 라는 의미가 된다.

역시 실제적으로 예제를 통해 살펴보도록 하자. 나리키리2에서 메뉴 그래픽이 저장되어 있는 부분의 데이터는 다음과 같다.

10 00 10 00 10 F3 FF FF 30 01 4F 54 55 FF 01 E4
───── ─ ─ ─ ─ ── ─ ─ ─ ─ ─ ─
header k d d d (l,p) d d d d k d

EE EE FF E9 DD 1E 20 03 14 E4 DD EE 00 03 9E 50
─ ─ ─ ─ ─ ─ ── ─ ─ ─ ─ ── ─
d d d d d d (l,p) k d d d (l,p) d
. . .
의미를 갖는 그룹으로 묶고 그 밑에 key일 경우 k, data일 경우 d, 압축된 정보일 경우 (l,p)로 표현하였다. 앞에서 k의 각 bit가 데이타 덩어리가 압축이 되었는지 되지 않았는지를 결정한다고 했으므로 key byte를 2진법으로 표현하고 저 위의 구성이 맞나 직접 확인해보길 바란다.
이제 key byte가 어디에 있는지, 각각의 덩어리가 압축되었는지에 대한 여부도 알 수 있으므로 위의 데이터를 이용하여 압축을 풀어보도록 하자.

F3 FF FF는 압축이 되지 않았으므로 그대로 출력하고 30 01은 len=6, pointer=2이므로 window에서 두바이트 앞에서 6개의 문자를 의미하므로

F3 FF FF (6,2) 4F 54 55 FF
-------- | ===============
Output : F3 FF FF

F3 FF FF FF FF FF FF FF FF 4F 54 55 FF
-------------------------- | =========
Output : F3 FF FF FF FF FF FF FF FF

와 같이 디코딩할 수 있다. 뒤의 4F 54 55 FF는 압축되지 않았으므로 그대로 출력한다. 따라서 첫번째 key byte를 이용하여 8개의 덩어리를 디코딩한 결과는 F3 FF FF FF FF FF FF FF FF 4F 54 55 FF가 된다.

위의 데이터를 이용하여 디코딩한 결과는 다음과 같다. 직접 디코딩해보고 그 결과를 비교해보도록 하자.

F3 FF FF FF FF FF FF FF FF 4F 54 55 FF E4 EE EE
FF E9 DD 1E FF E9 DD 1E FF E4 DD EE FF E4 DD 9E

4. C로 표현하면 어떻게 될까?

RLE에 비해 소스가 길다. CowBite라는 GBA 에뮬레이터에서 가져온 소스이니 '필자가 직접 짠 소스면 도저히 믿을 수가 없을 것 같은데' 라면서 고개돌리는 저 분 안심하시라 -_-;;;; 이런 제길 -_-;;;
위의 알고리즘을 변경없이 그대로 적용한 코드이므로 알고리즘을 하나하나 따라가면서 소스를 한줄한줄 따라내려가면 될 것이다.

int LZ77UnComp(FILE *src, FILE *dst)
{
long header=0;
long outSize;
long bytesDecompressed=0;

long windowPtr=0;

long length;
long offset;

int mask;
int key;
int flag_byte;
int data_byte;

int *dest;

int i,j;
long k;

for(i=0;i<4;i++) {
header|=((fgetc(src))<<(8*i)); // 헤더를 읽는다.
}

outSize=header>>8;

dest=(int*)malloc(sizeof(int)*outSize); // 배열을 할당한다.

while(bytesDecompressed < outSize) {// 헤더에 나타난 길이만큼 압축을 푼다.
key = fgetc(src); // key를 읽고

mask = 0x80;
for(i=0; (i<8) && (bytesDecompressed<outSize);i++) {
if(key&mask) { // key에 해당하는 bit가 1이면
flag_byte=fgetc(src);
length=(flag_byte>>4)+3;
offset=(flag_byte&0x0F) << 8;
offset |= fgetc(src);
offset++; // (l,p)정보를 읽고

for(j=0;j<length;j++) {
data_byte=dest[windowPtr-offset];
dest[windowPtr]=data_byte;
windowPtr++;
bytesDecompressed++;
} // 디코딩한다.
}
else { // key에 해당하는 bit가 0이면
data_byte=fgetc(src);
dest[windowPtr]=data_byte;
windowPtr++;
bytesDecompressed++; // 그대로 출력한다.
}
mask=mask>>1;
}
printf("bytesDecompressed=%d\n",bytesDecompressed);
}

for(k=0;k<outSize;k++) {
fputc(dest[k],dst);
} // 배열을 파일에 저장
return 0;
}

@. bios call을 이용한 데이터 위주로 설명하다보니 역시 부족한 점이 많습니다. 료우트님 많이 기다리셨을 텐데 많이 도움되지 못해 죄송합니다. 허나 이미 분석해놓은신 내용이 좀 있으니 금방 압축을 풀어내실 수 있을 겁니다 !+_+!! 화이팅!!

@2. 어제 숙제를 하느라 밤을 샜습니다. 수면시간 2시간 -_-;;; 강의시간이 다가와 여러번 검토할 시간이 없음에도 불구하고 언능 올립니다. 수정할 사항이 있으면 코멘트 달아주세요 즉시 수정하겠습니다.

@3. Huffman 알고리즘... 아직 분석 시작도 안했거든요 -.-;;; 다음 강좌는 언제 올라갈지 모릅니다. 이번 주 내내 실험과 레포트와 숙제와 씨름하고 주말에 시간이 나면 대략 1,2주 쯤 후에나 올릴 수 있지 않을까 합니다.

@4. 압축데이터가 어디에 존재하는가 찾는법!!
VBA 개발자 버전을 받습니다. 일반 버전은 logging window가 제대로 동작하지 않으므로 꼭 dev 버전으로 받으세요. 해당 그래픽이 뜨기 전에 Ctrl+P로 일시정지 시킨 후 logging window를 켜고 SWI를 체크해줍니다. 그리고 Ctrl+N으로 한프레임씩 진행시키면서 타일 에디터와 맵 에디터를 관찰합니다. 타일 에디터나 맵 에디터에 수정을 원하는 그래픽이 뜨면 그 때 logging window에서 RLUncompVram이나 LZ77UnCompVram을 찾습니다. LZ77UncompVram 0x8... 0x6... 으로 나타나는데 이는 각각 롬에 저장된 주소와 압축이 해제될 장소를 뜻합니다. 이 때 주의할 점은 0x8333333 이면 롬을 HE로 열어 333333에 해당하는 주소를 찾아야 합니다. 왜 맨 앞의 8을 제거하느냐에 대한 답은 자세한 설명은 생략;;;;