9장 압축 ① RLE·LZSS

게임은 왜 압축하나 쉽게

카트리지의 롬 칩은 비쌌습니다. 슈퍼 패미컴 게임은 대개 512KB–4MB였고, 칩이 한 단계 커질 때마다 카트리지 값이 올라갔습니다. 그래서 그림과 대사처럼 덩치 큰 자료를 줄여서 넣고, 쓸 때 WRAM이나 VRAM에 풀어 놓는 게임이 많습니다. 줄이는 것을 압축, 원래대로 되돌리는 것을 압축 해제(풀기)라고 합니다.

롬 해킹에서 압축은 두 번 문제가 됩니다. 먼저 찾을 때입니다. 화면에 보이는 그림이나 글자를 롬에서 바이트로 찾으려 해도 압축돼 있으면 같은 바이트가 롬에 없습니다. 다음은 고칠 때입니다. 한글로 다시 그린 그림을 넣으려면 게임이 푸는 방식 그대로 다시 압축해야 하고, 압축한 결과가 원래보다 길면 제자리에 들어가지 않습니다.

다행히 게임이 쓰는 압축은 대부분 몇 가지 단순한 생각의 변형입니다. 이 장은 그중 가장 흔한 두 가지, "같은 것이 이어지면 개수만 적기"(RLE)와 "앞에 나온 것이면 위치만 적기"(LZ 계열)를 다룹니다. 자주 나오는 글자에 짧은 부호를 주는 방식은 10장에서 봅니다.

RLE: 같은 바이트가 이어지면 개수만 쉽게

그림 자료에는 같은 바이트가 길게 이어지는 곳이 많습니다. 빈 칸은 모두 00이고, 한 색으로 칠한 면은 같은 바이트가 되풀이됩니다. 이것을 "00을 8번"처럼 값과 개수로 적는 방법이 RLE(run-length encoding, 반복 길이 부호화)입니다. 다만 반복되지 않는 곳까지 "1번"씩 적으면 오히려 길어지므로, 실제 형식은 "반복 묶음"과 "그대로 묶음"을 구별하는 머리 바이트를 둡니다.

게임보이 어드밴스·닌텐도 DS BIOS의 RLE 형식으로 10바이트를 머리말 4바이트 + 5바이트로 적기

머리 바이트의 맨 위 비트가 1이면 "다음 바이트 하나를 여러 번", 0이면 "다음 몇 바이트를 그대로"입니다. 반복은 3번 이상일 때만 이득이므로 길이에서 3을 빼고 적어, 7비트로 3–130번을 나타냅니다. 이렇게 "이득이 없는 짧은 경우는 아예 적지 않고 그만큼 길이를 당겨 적는" 요령은 뒤의 LZSS에도 똑같이 나옵니다. 0장의 IPS 패치에도 같은 바이트를 되풀이하는 RLE 레코드가 있습니다.

LZ: 앞에 나온 것을 다시 쓰기 쉽게

RLE는 같은 바이트가 바로 붙어 있어야만 줄입니다. 대사나 그림에는 "조금 떨어져서 또 나오는" 덩어리가 훨씬 많습니다. 1977년 지브(Ziv)와 렘펠(Lempel)이 낸 방법(LZ77)은 이런 덩어리를 "몇 칸 앞에서 몇 개를 다시 쓰라"는 짧은 지시로 바꿉니다. 오쿠무라 하루히코의 설명을 빌리면, 이 글에서 "compression"이라는 단어를 57글자 앞에서 이미 썼다면 단어를 다시 적는 대신 "57글자 뒤로 가서 11글자를 읽어라"라고 적는 것입니다.

두 번째 「가나다라」는 「5칸 앞에서 4글자」라는 지시 하나로 바뀝니다.

여기서 "몇 칸 앞"을 거리, "몇 개"를 길이라고 합니다. 푸는 쪽은 이미 풀어 낸 출력만 보면 되므로 따로 사전이 필요 없습니다. 출력 자체가 사전인 셈입니다. 다만 무한히 먼 곳까지 가리킬 수는 없어서, 거리를 적는 비트 수만큼 바로 앞 구간만 봅니다. 이 구간을 창(window)이라고 하고, 출력이 늘어나면 창도 함께 앞으로 미끄러지므로 슬라이딩 창이라고 부릅니다.

LZSS: 플래그 바이트로 둘을 섞기 쉽게

지시 하나를 적는 데 2바이트가 든다면, 1–2바이트짜리 일치는 그냥 그대로 적는 편이 짧습니다. 1982년 스토러(Storer)와 시만스키(Szymanski)가 이 점을 다듬은 방식을 흔히 LZSS라고 부르고, 1988년 오쿠무라가 PC-VAN에 올린 프로그램과 1989년에 공개한 LZSS.C가 널리 퍼졌습니다. 게임에서도 이와 거의 같은 형식을 흔히 만납니다. LZSS의 출력은 "그대로 1바이트"와 "복사 지시"가 섞인 줄입니다. 둘을 구별하려고 항목 8개마다 플래그 바이트 하나를 앞에 둡니다. 플래그의 비트 하나가 항목 하나의 종류입니다.

드래곤볼 Z 초오공전 두 편이 그림을 압축한 형식은 이렇습니다.

처음 2바이트: 풀었을 때의 크기(작은 자리 먼저).
그다음부터 플래그 바이트 하나와 항목 8개가 되풀이됩니다. 플래그는 아래 비트(비트 0)부터 씁니다.
플래그 비트가 1이면 바이트 하나를 그대로 출력합니다.
0이면 2바이트를 작은 자리 먼저 읽은 16비트 값(워드)입니다. 위 12비트가 거리, 아래 4비트에 3을 더한 것이 길이입니다.

복사 항목 89 00을 거리와 길이로 나누기

실제 롬에서 꺼낸 바이트로 확인해 봅시다. 돌격편 일본판의 타이틀 화면에서 글자가 그려진 배경 층(BG3)의 타일은 $B7:9EB1(파일 0x1B9EB1)에 압축돼 있고, 첫 14바이트는 아래와 같습니다. 플래그 DC는 2진수로 1101 1100이라 아래 비트부터 읽으면 0, 0, 1, 1, 1, 0, 1, 1입니다. 항목 8개가 복사, 복사, 그대로 셋, 복사, 그대로 둘이라는 뜻입니다.

60 13크기$1360 = 4,960바이트로 풀림
DC플래그1101 1100
2F 01복사거리 18, 길이 18
F0 00복사거리 15, 길이 3
01그대로
0F그대로
3F그대로
89 00복사거리 8, 길이 12
1F그대로
FF그대로

첫 복사는 출력이 아직 하나도 없는데 18칸 앞을 가리킵니다. 이 형식은 출력 시작보다 앞을 모두 0으로 읽기 때문에, 이 항목 하나가 00 18개가 됩니다. 셋째 복사는 거리가 8인데 길이가 12라서, 가져오는 도중에 방금 쓴 바이트까지 다시 읽습니다. 이렇게 거리보다 긴 복사는 짧은 무늬를 되풀이하는 RLE 노릇을 합니다. 아래 도구로 한 항목씩 따라가 보세요.

예 ha ha ha ha ha! BANANA BANANA 돌격편 타이틀 그림 첫머리

직접 적은 글(40바이트까지)

15바이트 글이 9바이트가 됩니다. 넷째 항목은 아직 다 쓰지 않은 칸까지 겹쳐 베낍니다.

압축된 바이트 (9바이트)

0F크기
00크기
17플래그
68그대로
61그대로
20그대로
38복사
00복사
21그대로

플래그 비트 (1 = 그대로 1바이트, 0 = 복사 2바이트)

아직 아무것도 읽지 않았습니다.

출력 (15바이트)

068h
161a
220␣
368h
461a
520␣
668h
761a
820␣
968h
1061a
1120␣
1268h
1361a
1421!

가져온 곳 방금 쓴 곳 시작보다 앞(0)

한 단계씩 읽으면

처음 2바이트는 풀었을 때의 크기입니다: $000F = 15바이트.
플래그 바이트 17 = 00010111. 아래 비트(비트 0)부터 뒤따르는 항목 8개의 종류를 알려 줍니다.
비트 0 = 1 → 그대로 1바이트 68(h). 출력 0번 칸에 그대로 씁니다.
비트 1 = 1 → 그대로 1바이트 61(a). 출력 1번 칸에 그대로 씁니다.
비트 2 = 1 → 그대로 1바이트 20(␣). 출력 2번 칸에 그대로 씁니다.
비트 3 = 0 → 복사: 워드 $0038에서 거리 = $003 = 3, 길이 = 8 + 3 = 11. 출력 3번 칸부터 3칸 앞(0번 칸)에서 11바이트(68 61 20 68 61 20 68 61 20 68 61)를 가져옵니다. 가져올 곳과 쓸 곳이 겹쳐서, 방금 쓴 바이트를 다시 읽으며 반복합니다.
비트 4 = 1 → 그대로 1바이트 21(!). 출력 14번 칸에 그대로 씁니다.

더 깊이창, 겹치는 복사, 시작 앞의 0, 압축이 하나로 정해지지 않는 이유

길이에 3을 더하는 이유

복사 항목은 2바이트에 플래그 비트 하나가 더 듭니다. 2바이트 일치를 복사로 적으면 그대로 적을 때(2바이트 + 플래그 비트 둘)와 거의 같고, 1바이트 일치는 오히려 길어집니다. 그래서 길이는 3부터만 쓰고, 4비트 값 0–15를 길이 3–18로 당겨 씁니다. 오쿠무라의 LZSS.C도 THRESHOLD 2, 최대 길이 18로 같습니다.

거리와 창의 크기

거리는 12비트라 1–4,095입니다. 거리 0은 "지금 쓰는 칸"을 가리켜 뜻이 없으므로, 툴킷은 거리 0이 나오면 깨진 자료로 보고 멈춥니다. 창이 4KB라서 한참 앞에 나온 무늬는 다시 쓰지 못합니다. 창을 키우면 거리를 적을 비트가 늘어 복사 항목이 길어지므로, 2바이트 항목에 12비트 거리와 4비트 길이를 나눠 담은 것은 그 사이의 타협입니다.

겹치는 복사는 한 바이트씩

거리보다 긴 복사가 제대로 되려면 한 바이트를 쓰고 나서 다음 바이트를 읽어야 합니다. 여러 바이트를 한꺼번에 옮기거나, 겹치는 구간을 안전하게 옮기도록 만든 복사 함수(C의 memmove 등)로 구현하면 결과가 달라집니다. 롬의 해제 루틴을 흉내 내는 도구를 직접 짤 때 가장 흔히 틀리는 곳입니다. 거리 1, 길이 18이면 직전 바이트 하나를 18번 되풀이하는 것과 같습니다.

시작 앞의 0

출력 시작보다 앞을 가리키는 복사를 어떻게 읽을지는 형식마다 다릅니다. 이 게임은 0으로 읽고, 오쿠무라의 LZSS.C는 창 4,096바이트 가운데 앞 4,078바이트(N − F)를 공백($20)으로 채우고 4,078번 칸부터 쓰기 시작합니다. 영문 텍스트라면 공백이 많아 첫머리부터 복사를 쓸 수 있습니다. 그림 자료는 빈 칸이 00이라 0으로 채우는 쪽이 유리합니다. 압축기를 직접 짤 때 이 초기값을 틀리면 첫머리에서 바로 어긋납니다.

같은 자료라도 압축 결과는 여러 가지

푸는 방법은 하나지만 압축하는 방법은 여럿입니다. 같은 길이의 일치가 여러 곳에 있으면 어느 거리를 고를지, 지금 짧게 복사하고 다음에 길게 복사하는 편이 나은지를 압축기가 정합니다. 돌격편 타이틀 타일을 풀었다가 툴킷으로 다시 압축하면 길이는 3,613바이트로 같지만 바이트는 다릅니다. 첫 항목부터 원래 자료는 "거리 18, 길이 18"이고, 툴킷은 가장 가까운 일치를 고르는 방식이라 "거리 1, 길이 18"입니다. 둘 다 00 18개로 풀리므로 게임에는 어느 쪽을 넣어도 됩니다. 그래서 다시 압축한 자료가 원본과 바이트까지 같은지가 아니라, 풀었을 때 같은지로 확인합니다.

툴킷의 압축기는 매번 가장 긴 일치를 고르는 단순한 방식(탐욕법)입니다. 다음 항목까지 내다보고 고르면 몇 퍼센트 더 줄기도 합니다. 넣을 자리가 몇 바이트 모자랄 때 기댈 수 있는 여지입니다.

게임마다 다른 LZSS 쉽게

"LZSS"라는 이름은 같아도 바이트를 놓는 방식은 게임과 기계마다 다릅니다. 처음 보는 게임의 압축을 풀 때는 아래 항목을 하나씩 확인하게 됩니다.

LZSS 세 가지 비교
항목	초오공전(이 장)	오쿠무라 LZSS.C	GBA·DS BIOS LZ77
머리말	크기 2바이트	없음(파일 끝까지)	4바이트(종류 $10, 크기 3바이트)
플래그 읽는 순서	아래 비트부터	아래 비트부터	위 비트부터
복사를 뜻하는 비트	0	0	1
위치	거리(워드의 위 12비트)	창 안의 절대 위치 12비트	거리 − 1(12비트)
길이	아래 4비트 + 3	둘째 바이트 아래 4비트 + 3	첫 바이트 위 4비트 + 3
시작 앞	0	공백($20)	정해 두지 않음

거리를 그대로 적는지 1을 빼고 적는지, 2바이트를 어느 쪽 먼저 읽는지(2장의 엔디안), 길이에 얼마를 더하는지 하나만 달라도 결과가 완전히 어긋납니다. 압축 해제 루틴을 디버거로 따라가며 이 값들을 하나씩 확인하는 것이 가장 확실합니다.

더 깊이돌격편의 해제 루틴을 읽어 보기

돌격편 일본판의 해제 루틴 $81:DF4F를 툴킷으로 역어셈블한 것에서 핵심만 옮겼습니다. 앞에서 본 형식이 그대로 코드에 들어 있습니다. 이때 A는 8비트, X·Y는 16비트이고, Y는 압축 자료를 읽는 위치, X는 $7E:8000부터 쓰는 출력 위치입니다.

81:DF68  LDX $0000,Y      ; 처음 2바이트 = 풀었을 때 크기
81:DF6B  STX $F0
81:DF74  LDA $F3          ; 남은 플래그 비트 수가 0이면
81:DF76  BNE $81DF82
81:DF78  LDA $0000,Y      ;   새 플래그 바이트를 $F2에
81:DF7B  STA $F2
81:DF7E  LDA #$08         ;   남은 비트 수 = 8
81:DF80  STA $F3
81:DF82  DEC $F3
81:DF84  LSR $F2          ; 아래 비트를 캐리로 밀어내고
81:DF86  BCC $81DF93      ; 0이면 복사로
81:DF88  LDA $0000,Y      ; 1이면 그대로 1바이트
81:DF8B  STA $7E8000,X
81:DF93  LDA $0000,Y      ; 복사: 첫 바이트의 아래 4비트
81:DF96  AND #$0F
81:DF98  INC A            ; + 2를 $F4에 (DEC/BPL로 + 3번 돈다)
81:DF99  INC A
81:DF9E  LDA $0000,Y      ; 16비트로 다시 읽어
81:DFA4  LSR A            ; 네 번 밀면 거리
81:DFAA  TXA              ; 출력 위치 − 거리
81:DFAB  SEC
81:DFAC  SBC $F6
81:DFAE  BPL $81DFCA      ; 음수면 그 칸 수만큼 0을 먼저 쓴다
81:DFD2  LDA $8000,Y      ; 한 바이트씩 가져와 쓰기
81:DFD5  STA $8000,X
81:DFDA  DEC $F4
81:DFDC  BPL $81DFD2
81:DFE0  CPX $F0          ; 크기만큼 썼으면 끝
81:DFE2  BCC $81DF74

LSR로 아래 비트부터 밀어내니 플래그는 아래 비트부터이고, BCC가 0일 때 복사로 가니 0이 복사입니다. 복사 갈래가 거리보다 앞(음수)을 만나면 $7E:8000 앞을 읽지 않고 00을 씁니다. 가져오는 반복문이 한 바이트를 쓰고 나서 다음 바이트를 읽기 때문에 겹치는 복사도 무늬를 되풀이합니다. 다른 게임의 해제 루틴도 이 몇 군데(플래그를 미는 방향, 갈라지는 조건, 길이에 더하는 값, 거리를 꺼내는 방법, 앞을 읽는 방법)만 확인하면 형식이 나옵니다.

각성편의 $80:9DA7과 돌격편의 $81:DFE7은 이 루틴을 부른 뒤 풀어 낸 타일마다 바이트 순서를 바꾸는 일을 하나 더 합니다. 압축 자료 안에서는 2bpp 타일 하나의 평면 0 여덟 줄과 평면 1 여덟 줄이 따로 모여 있고, 해제 뒤에 이것을 7장의 SNES 순서(줄마다 평면 0, 평면 1)로 엇갈려 놓습니다. 평면별로 모아 두면 같은 바이트가 더 길게 이어져 압축에 유리합니다. 그래서 압축만 풀어 타일로 그리면 줄무늬가 보입니다. 툴킷의 --planar 옵션이 이 순서 바꾸기를 합니다.

롬에서 압축된 곳과 푸는 코드 찾기 쉽게

화면에 보이는 그림을 krpatch snes tiles로 롬 전체에서 찾아도 나오지 않으면 압축을 의심합니다. 압축된 곳은 헥스 에디터로 보면 몇 가지 티가 납니다.

그림 자료답지 않게 바이트 값이 고르게 흩어져 있고, 긴 반복이 거의 없습니다.
앞 2–4바이트가 그럴듯한 크기(타일 몇백 개라면 수천 바이트)이고, 바로 뒤의 바이트를 플래그로 읽으면 그 뒤가 항목 경계에 딱 맞습니다.

하지만 가장 확실한 방법은 게임이 푸는 순간을 잡는 것입니다. 압축이 풀린 그림은 결국 VRAM이나 WRAM에 놓이므로, 거기서 거꾸로 따라갑니다.

풀린 자료가 놓인 곳에서 거꾸로 압축 자료와 해제 루틴을 찾는 순서

해제 루틴을 하나 찾으면 나머지는 쉽습니다. 그 루틴을 부르는 JSL을 롬 전체에서 찾으면 압축 자료를 쓰는 곳이 모두 나옵니다. 돌격편 일본판에서 JSL $81DF4F는 바이트로 찾으면 16곳이고, 그 가운데 하나는 $81:DFE7 안에 있어 따로 부르는 곳은 15곳입니다. 순서를 바꾸는 쪽의 JSL $81DFE7은 26곳입니다. 부르는 쪽은 대개 "주소 2바이트, 뱅크 1바이트, 크기 2바이트" 같은 항목 표에서 인자를 꺼내므로, 그 표가 압축 자료의 목록이 됩니다.

실제 패치에서 실제 패치에서

각성편: 다시 그린 로고가 더 짧게 압축돼 제자리에

각성편의 타이틀 화면에서 글자가 그려진 배경 층(BG3) 타일은 $89:9B9D에 이 장의 형식으로 압축돼 있습니다. 풀면 4,944바이트, 압축된 크기는 3,608바이트입니다. 해제 루틴은 $80:9CFA, 타일 순서까지 바꾸는 쪽은 $80:9DA7입니다. 「초오공전 각성편」 한글 로고를 그려 다시 압축하니 3,232바이트로 줄어 제자리에 들어갔습니다. 더 길어졌다면 같은 영역의 빈 곳(파일 0x4C801–0x4FFFF, 원본에서 모두 FF)으로 옮기고 위치를 적은 5바이트 항목(파일 0xD720)을 고치게 해 두었습니다.

돌격편: 같은 형식, 다른 주소

돌격편은 형식이 같아 각성편 도구를 주소만 바꿔 썼습니다. 해제 루틴은 $81:DF4F(A에 주소, X에 뱅크를 받아 WRAM $7E:8000에 풀고 크기를 $F0에 남김)이고, 작업 노트에 적혀 있던 $80:9CFA는 각성편의 주소였습니다. 돌격편 롬의 그 자리는 메뉴 커서 코드 한가운데입니다. 다시 압축한 결과 타일은 3,613바이트에서 3,237바이트로, 배치표($B7:BE7F)는 781바이트에서 779바이트로 줄어 둘 다 제자리에 넣었습니다.

두 게임 모두 "다시 압축한 것이 원래보다 길면 어디에 둘까"를 먼저 정해 두었다는 점이 중요합니다. 압축한 크기는 그림을 다 그려 봐야 알 수 있기 때문입니다.

직접 해 보기 직접 해 보기

툴킷으로 돌격편 일본판의 타이틀 타일과 배치표를 풀어 봅니다. 오프셋은 파일 오프셋(16진수)입니다.

$ krpatch lzss decode totsugeki-j.sfc 1B9EB1 title.bin
4960 bytes from 3613 compressed
$ krpatch lzss decode totsugeki-j.sfc 1BBE7F tilemap.bin
2048 bytes from 781 compressed
$ xxd -l 48 title.bin
00000000: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000010: 0000 0000 0001 0f3f 0000 0000 0001 0f3f  .......?.......?
00000020: 0000 0000 1fff f880 0000 0000 1fff ffff  ................

첫 줄(0x00–0x0F)은 모두 0이고, 둘째 줄 가운데의 01 0F 3F(0x15–0x17)가 위 도구의 그대로 항목 셋입니다. 그 뒤 12바이트 00 00 00 00 00 01 0F 3F 00 00 00 00(0x18–0x23)이 거리 8짜리 겹치는 복사입니다. 그림으로 보려면 --planar 옵션으로 순서를 바꿔 풀고 krpatch snes tiles로 그립니다. 반대로 고친 그림은 krpatch lzss encode로 압축합니다.

$ krpatch lzss decode totsugeki-j.sfc 1B9EB1 title-snes.bin --planar
4960 bytes from 3613 compressed
$ krpatch snes tiles title-snes.bin 0 1360 title.png --bpp 2
title.png
$ krpatch lzss encode title-snes.bin title.lz --planar
3613 bytes from 4960

다시 압축한 title.lz는 원본과 길이는 같지만 바이트는 다릅니다(위 「더 깊이」). 다시 풀어서 같은지 확인하는 습관을 들이면, 압축기를 바꿨을 때도 안심하고 넣을 수 있습니다.