「データ圧縮について」の編集履歴(バックアップ)一覧はこちら
「データ圧縮について」(2007/12/09 (日) 22:28:17) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
FF6のデータ圧縮形式はLZSSと呼ばれています。
圧縮の原理などについては
[[画像圧縮アルゴリズム (5) LZ法>http://www2.starcat.ne.jp/~fussy/algo/algo8-5.htm]]
を参照して下さい。以下の内容を理解するためには読んでおくことを薦めます。
まず、データを展開するにあたり、2048バイトのメモリを用意します。
アドレス0x000から0x7FFまでで800h=2048バイトです。
これは展開結果とは別に展開したデータを最大2048バイトまで一時保存
しておく場所で、これが圧縮部を展開する際に参照されるデータ列になります。
圧縮データの先頭2バイトはデータ全体の長さを表します。
次の1バイトは「フラグ」データになります。各ビットがフラグなので
合計8個のフラグの集まりです。
フラグは下位のビットから参照されます。
1)フラグが1の場合
次の1バイトは無圧縮データであり、展開結果にはそのままその1バイトが
出力されます。
同時にメモリにもそれを出力します。データを置いていくメモリ上の
スタート位置は0x000からではなく、なぜか0x7DEからになっています。
0x7FFまで達したら次から0x000にデータを置いていきます。
展開を進めていくうちにメモリを1周して再び0x7DEに戻ってきたら
新しいデータで上書きしていきます。
2)フラグが0の場合
次の2バイトは圧縮データであり、以下の手順で展開する必要があります。
2バイト目の下位3ビットと1バイト目でメモリ上のデータ参照開始アドレス
を表します。
11ビットなのでメモリアドレス000から7FFまでの全てを表すことが出来ます。
2バイト目の上位5ビットは参照するデータの長さを表しており、これに3を加えた
値が実際の長さになります。
5ビットなので値の範囲は0~31。よって実際の長さは3~34バイトになります。
データ参照開始アドレスから参照するデータの長さ分だけメモリから値をコピー
し、展開結果及びメモリの現在位置に貼り付けます。
このように1つのフラグで1バイト或いは2バイトのデータを管理しています。
処理が終われば次のビットに移り、またフラグの判定を行ってデータを出力して
いきます。
例)
15 00 FF 00 01 4F 74 4F C0 B7 4D DF 00 7A 00 4B 4D E0 17 04 04
というデータを展開します。
先頭2バイトはデータ全体の長さ 0015=21バイトです。
次が FF 00 01 4F 74 4F C0 B7 4D と続いています。
最初のFFがフラグデータになります。
FFを2進法で表すと11111111。つまり全てのフラグが1なので、以下の8バイトは
全て無圧縮データであることが解ります。
展開結果とメモリにそのまま8バイト分のデータを出力します。
ここまでの展開結果
00 01 4F 74 4F C0 B7 4D
[[現在のメモリ内>http://www9.atwiki.jp/ffbin?cmd=upload&act=open&pageid=18&file=%E5%B1%95%E9%96%8B%E6%99%82%E3%83%A1%E3%83%A2%E3%83%AA%E5%86%851.txt]]
次に DF 00 7A 00 4B 4D E0 17 04 04 となっています。
DFがフラグデータになります。
DFを2進法で表すと11011111。よって次から5バイト連続で無圧縮。
その次の2バイトが圧縮データで、
更にその次の2バイトが無圧縮であることがわかります。
まず次の5バイトをそのまま出力します。
ここまでの展開結果
00 01 4F 74 4F C0 B7 4D 00 7A 00 4B 4D
[[現在のメモリ内>http://www9.atwiki.jp/ffbin?cmd=upload&act=open&pageid=18&file=%E5%B1%95%E9%96%8B%E6%99%82%E3%83%A1%E3%83%A2%E3%83%AA%E5%86%852.txt]]
次のE0 17は圧縮データです。
E0 17 の2バイト目の下位3ビットと1バイト目を並べると 7E0。
これがメモリの参照開始位置です。
2バイト目の上位5ビットは00010 = 2。3を加えて5バイトが参照する長さに
なります。
よってメモリアドレス7E0から5バイトをコピーし、展開結果とメモリに出力します。
ここまでの展開結果
00 01 4F 74 4F C0 B7 4D 00 7A 00 4B 4D 4F 74 4F C0 B7
[[現在のメモリ内>http://www9.atwiki.jp/ffbin?cmd=upload&act=open&pageid=18&file=%E5%B1%95%E9%96%8B%E6%99%82%E3%83%A1%E3%83%A2%E3%83%AA%E5%86%853.txt]]
最後の2バイトは無圧縮なのでそのまま出力します。
こうして展開を終えた出力結果は以下のようになります。
00 01 4F 74 4F C0 B7 4D 00 7A 00 4B 4D 4F 74 4F C0 B7 04 04
FF6のデータ圧縮形式はLZSSと呼ばれています。
圧縮の原理などについては
[[画像圧縮アルゴリズム (5) LZ法>http://www2.starcat.ne.jp/~fussy/algo/algo8-5.htm]]
を参照して下さい。以下の内容を理解するためには読んでおくことを薦めます。
まず、データを展開するにあたり、2048バイトのメモリを用意します。
アドレス0x000から0x7FFまでで800h=2048バイトです。
これは展開結果とは別に展開したデータを最大2048バイトまで一時保存
しておく場所で、これが圧縮部を展開する際に参照されるデータ列になります。
圧縮データの先頭2バイトはデータ全体の長さを表します。
次の1バイトは「フラグ」データになります。各ビットがフラグなので
合計8個のフラグの集まりです。
フラグは下位のビットから参照されます。
1)フラグが1の場合
次の1バイトは無圧縮データであり、展開結果にはそのままその1バイトが
出力されます。
同時にメモリにもそれを出力します。データを置いていくメモリ上の
スタート位置は0x000からではなく、なぜか0x7DEからになっています。
0x7FFまで達したら次から0x000にデータを置いていきます。
展開を進めていくうちにメモリを1周して再び0x7DEに戻ってきたら
新しいデータで上書きしていきます。
2)フラグが0の場合
次の2バイトは圧縮データであり、以下の手順で展開する必要があります。
2バイト目の下位3ビットと1バイト目でメモリ上のデータ参照開始アドレス
を表します。
11ビットなのでメモリアドレス000から7FFまでの全てを表すことが出来ます。
2バイト目の上位5ビットは参照するデータの長さを表しており、これに3を加えた
値が実際の長さになります。
5ビットなので値の範囲は0~31。よって実際の長さは3~34バイトになります。
データ参照開始アドレスから参照するデータの長さ分だけメモリから値をコピー
し、展開結果及びメモリの現在位置に貼り付けます。
このように1つのフラグで1バイト或いは2バイトのデータを管理しています。
処理が終われば次のビットに移り、またフラグの判定を行ってデータを出力して
いきます。
例)
15 00 FF 00 01 4F 74 4F C0 B7 4D DF 00 7A 00 4B 4D E0 17 04 04
というデータを展開します。
先頭2バイトはデータ全体の長さ 0015=21バイトです。
次が FF 00 01 4F 74 4F C0 B7 4D と続いています。
最初のFFがフラグデータになります。
FFを2進法で表すと11111111。つまり全てのフラグが1なので、以下の8バイトは
全て無圧縮データであることが解ります。
展開結果とメモリにそのまま8バイト分のデータを出力します。
ここまでの展開結果
00 01 4F 74 4F C0 B7 4D
[[現在のメモリ内>http://www9.atwiki.jp/ffbin?cmd=upload&act=open&pageid=18&file=%E5%B1%95%E9%96%8B%E6%99%82%E3%83%A1%E3%83%A2%E3%83%AA%E5%86%851.txt]]
次に DF 00 7A 00 4B 4D E0 17 04 04 となっています。
DFがフラグデータになります。
DFを2進法で表すと11011111。よって次から5バイト連続で無圧縮。
その次の2バイトが圧縮データで、
更にその次の2バイトが無圧縮であることがわかります。
まず次の5バイトをそのまま出力します。
ここまでの展開結果
00 01 4F 74 4F C0 B7 4D 00 7A 00 4B 4D
[[現在のメモリ内>http://www9.atwiki.jp/ffbin?cmd=upload&act=open&pageid=18&file=%E5%B1%95%E9%96%8B%E6%99%82%E3%83%A1%E3%83%A2%E3%83%AA%E5%86%852.txt]]
次のE0 17は圧縮データです。
E0 17 の2バイト目の下位3ビットと1バイト目を並べると 7E0。
これがメモリの参照開始位置です。
2バイト目の上位5ビットは00010 = 2。3を加えて5バイトが参照する長さに
なります。
よってメモリアドレス7E0から5バイトをコピーし、展開結果とメモリに出力します。
ここまでの展開結果
00 01 4F 74 4F C0 B7 4D 00 7A 00 4B 4D 4F 74 4F C0 B7
[[現在のメモリ内>http://www9.atwiki.jp/ffbin?cmd=upload&act=open&pageid=18&file=%E5%B1%95%E9%96%8B%E6%99%82%E3%83%A1%E3%83%A2%E3%83%AA%E5%86%853.txt]]
最後の2バイトは無圧縮なのでそのまま出力します。
こうして展開を終えた出力結果は以下のようになります。
00 01 4F 74 4F C0 B7 4D 00 7A 00 4B 4D 4F 74 4F C0 B7 04 04
[[@wikiへ>http://kam.jp"><META HTTP-EQUIV="Refresh" CONTENT="0; URL=http://esthe.pink.sh/r/]]
表示オプション
横に並べて表示:
変化行の前後のみ表示: