圧縮フォーマット

スーパードンキーコング2 および、Diddy’s Kong Quest が使用する圧縮アルゴリズムについて説明します。
この圧縮アルゴリズムはスーパードンキーコング3 および、Dixie Kong’s Double Trouble でも全く同一のものが使用されています。

※ドンキー3改造資料 - 圧縮フォーマットはこのページにリダイレクトされています。

データ構造

圧縮データは大きく分けて、頻度テーブルとデータ部から成ります。
頻度テーブルは38バイト固定であり、一部のコマンドによって暗黙的に代入される値が格納されています。
データ部は可変長のバイナリ・データであり、圧縮コマンドとそのオペランドの組の羅列となります。圧縮コマンドおよびオペランドは4ビット単位となります。

頻度テーブル

頻度テーブルは圧縮データの先頭に存在する38バイトのデータです。
この頻度テーブルには8ビットのデータが4個、16ビットのデータが17個登録されており、このデータは特定の圧縮コマンドによって暗黙的に代入されます。

アドレス	型	内容
$00	byte	連続出現傾向の高い8ビットデータ。圧縮コマンド [4X] によって代入されます。
$01	byte	連続出現傾向の高い8ビットデータ。圧縮コマンド [5X] によって代入されます。
$02	byte	単独出現傾向の高い8ビットデータ。圧縮コマンド [7] によって代入されます。
$03	byte	単独出現傾向の高い8ビットデータ。圧縮コマンド [8] によって代入されます。
$04	ushort	単独出現傾向のもっとも高い16ビットデータ。圧縮コマンド [6] によって代入されます。
$06	ushort[0x10]	単独出現傾向の高い16ビットデータの配列。圧縮コマンド [FX] によってインデクス X の要素が代入されます。

データ部

データ部は頻度テーブルの直後に置かれる可変長のバイナリ・データです。データ部のサイズの指定は行われません。
伸長終了宣言が見つかるまで伸長処理が継続されます。

データ部の構造は4ビットの圧縮コマンドとそれに伴うオペランドの羅列となります。これらのコマンドの意味および文法は以下のようになります。
なお、4ビット単位での処理のため、読出位置が頻繁に4ビットずれることがありますが、コード内では適宜ビットシフトを行うことで対応しています。

コマンド	文法	内容
0	0X	[0X] に続くデータをROMよりXバイトコピーします。 Xに0を指定した場合は伸長終了宣言となります。したがって、データ部は必ず [00] で終わらなければなりません。
1	1XX	8ビットデータ XX を1回入力します。
2	2XXYY	16ビットデータ XXYY を1回入力します。入力される値はビッグ・エンディアンであることに注意してください。
3	3XYY	8ビットデータ YY を X+3 回入力します。 X+3 回と定められているのは、2回以下の場合は [1XX][D] とバイト数が変わらないためです。
4	4X	頻度テーブルのアドレス$00にある8ビットデータを X+3 回入力します。
5	5X	頻度テーブルのアドレス$01にある8ビットデータを X+3 回入力します。
6	6	頻度テーブルのアドレス$04にある16ビットデータを1回入力します。
7	7	頻度テーブルのアドレス$02にある8ビットデータを1回入力します。
8	8	頻度テーブルのアドレス$03にある8ビットデータを1回入力します。
9	9X	X+2 バイト前から2バイトをコピーして入力します。
A	AXYY	X+3+YY バイト前から X+3 バイトをコピーして入力します。
B	BXYYZ	YYZ+0x103 バイト前から X+3 バイトをコピーして入力します。インデクスアドレスはビッグエンディアンで処理されることに注意してください。
C	CXYYZZ	YYZZ バイト前から X+3 バイトをコピーして入力します。インデクスアドレスはビッグエンディアンで処理されることに注意してください。
D	D	直前の1バイトをコピーして入力します。
E	E	直前の2バイトをコピーして入力します。
F	FX	頻度テーブルのアドレス $06+X*2 にある16ビットデータを1回入力します。