BPE圧縮の展開機能

Byte Pair Encoding（BPE）とは

　「月刊 C MAGAZINE」1997年11月号(ソフトバンク刊)にて紹介された、1990年代当時は非常に高速な展開処理が可能であったデータ圧縮アルゴリズムです。

　原理としては、隣同士のデータの組み合わせ(2バイト)を1バイトに圧縮して「辞書」を作成、既に使われた組み合わせのデータを「辞書」で符号化、新たに見つけた組み合わせを「辞書」に加えて…の繰り返しとなります。

　圧縮されたデータは必ず辞書のバッファが含まれています。バッファサイズは可変であり、組み合わせが少ない単純なデータは辞書のバッファを減らすことで実ファイルのサイズを減らすことができます。逆に組み合わせが多い複雑なデータは辞書のバッファを増やすことで多くの組み合わせに対応させ、実ファイルのサイズを減らすことができます。

　辞書のバッファサイズはユーザーが調節できます。データ毎に最適なバッファサイズを見つけて、圧縮ファイルのサイズを最小限に抑えましょう。

Byte Pair Encodingの理論については以下の文献をご参照ください。

• 原文: C/C++ Users Journal Vol.15, No.9 Philip Gage 　→ http://www.pennelynn.com/Documents/CUJ/HTML/94HTML/19940045.HTM
• 日本語: C MAGAZINE 1997年11月号 太田純 訳「ランダムアクセスが可能なデータ圧縮技法」 　→ https://www.amazon.co.jp/dp/B00KLPFSGA
• Wikipedia - バイト対符号化 　→ https://ja.wikipedia.org/wiki/%E3%83%90%E3%82%A4%E3%83%88%E5%AF%BE%E7%AC%A6%E5%8F%B7%E5%8C%96

Byte Pair Encoding（BPE）の特徴

　BPEは展開スピードを重要視したアルゴリズムであり、1990年代当時は他のアルゴリズムでは到底真似できない非常に高速な展開速度を叩き出していました。展開後32KBになるデータをわずか0.5秒(turboR, R800-DRAMモード時)で展開すると言えば、その高速ぶりが理解できるものと思われます。

　BPEは展開スピードの速さに加え、90年代当時に利用されていた他の圧縮アルゴリズムと決してひけを取らない圧縮率を誇っていました。さすがにLZ法を超える圧縮率は出せませんが、あと少しでLZ法と肩を並べる程度の圧縮率が期待できます。

BPE展開のサンプル動画

　BPEはデータが100％復元する「可逆圧縮」のアルゴリズムですので、あらゆるデータに有効利用できます。当クラブが想定している用途は主に画像圧縮ですが、ビットマップデータの圧縮では特にSCREEN8以上のCGの圧縮率が良くなり、MAG形式のようにタイルパターンに頼らずとも圧縮率が期待できます。

　当クラブ独自の実装として、DMシステム2では以下の機能があります。

1. 圧縮データを配置するメモリはRAM・VRAMのどちらでも有効、展開先のメモリについてもRAM・VRAMのどちらでも任意のアドレスへ展開できます。BGMデータやマシン語等のバイナリデータ、テキスト等なんでも指定されたメモリへ高速にデータ展開できます。
2. COPY形式の矩形CGデータは矩形のまま圧縮し、DMシステム2上での展開時にロジカルオペレーションと展開方向を指定できます。下から上方向へ重ね合わせ(TPSET)で展開する等、夢が膨らみます(笑)。

BPE圧縮データを作る

　アプリは4種類あります。ハードウェア環境に併せてご利用ください。アプリは ダウンロードのページ で入手してください。

• MSX-DOS(CP/M)版 EBPE.COM（version 0.30）
• MSX-DOS版 EBPEMSX.COM（version 0.95, 佐野友則さん制作)
• MS-DOS汎用版 EBPE.EXE（version 0.43）
• Win32版 EBPE32.EXE（version 0.43）

　各種コマンドラインから以下のパラメータを指定し、コマンドを実行してください。

• A>EBPE [.<出力ファイルの拡張子>] [-|/<options>] <圧縮ファイル>
• C>EBPE32 [.<出力ファイルの拡張子>] [-|/<options>] <圧縮ファイル>

　出力ファイルの拡張子を省略した場合の拡張子は .BPE になります。

BPE圧縮のレビュー on twitter

コマンドオプション

バッファサイズの指定オプション(-b#)

　辞書のバッファサイズを任意指定します。(256～32768)　省略するとデフォルト設定の 4096（バイト）になります。

自動調整オプション(-a)

　辞書のバッファサイズを自動で調整します。

のように -aオプションを指定すると、辞書のバッファサイズを 512,1024,2048,4096,8192,16384,32768 と変更しつつ圧縮した結果一番圧縮率の高いものを選択します。

Windows向け：辞書バッファサイズの総当たりバッチファイル

　昨今のWindows PCは非常にメモリが豊富で高速に動作しますので、1990年代当時は実行したくなかった「辞書バッファサイズを手動でちまちま変えて圧縮作業を繰り返しファイルサイズが一番小さなものを採用する」という行為が非常に手軽になりました。

ebpe32 .256 -b256 %1
ebpe32 .512 -b512 %1
ebpe32 .1K -b1024 %1
ebpe32 .2K -b2048 %1
ebpe32 .3K -b3072 %1
ebpe32 .4K -b4096 %1
ebpe32 .5K -b5120 %1
ebpe32 .6K -b6144 %1
ebpe32 .7K -b7168 %1
ebpe32 .8K -b8192 %1
ebpe32 .9K -b9216 %1
ebpe32 .10K -b10240 %1
ebpe32 .11K -b11264 %1
ebpe32 .12K -b12288 %1
ebpe32 .13K -b13312 %1
ebpe32 .14K -b14336 %1
ebpe32 .15K -b15360 %1
ebpe32 .16K -b16384 %1
ebpe32 .AUT -a %1

　上記のバッチファイルを仮に EBPEBAT.BAT と命名し、EBPE32.EXEと圧縮対象ファイルとバッチファイルを同じフォルダへ配置したうえでコマンドプロンプトよりバッチファイルを実行します。

　バッチ処理では、バッファサイズ256バイトから16KバイトまでBPE圧縮を繰り返し実行します。1分ほど待つとファイル名は同じで拡張子が異なる複数の圧縮データが作成されてバッチ処理が終了しますので、ファイルサイズの一番小さなものを採用する(それ以外は捨てる)ことで、最大級の圧縮効率が得られます。自動調整オプションを設定するよりもサイズが小さくなる場合もありますので、ぜひお試しください。

　なお、採用した圧縮データファイルは、拡張子を「.BPE」へリネームしておくことをおすすめします。

BPE圧縮データの展開

　RAMまたはVRAMに配置されたBPE圧縮データを展開します。

　なお、あらかじめBPE圧縮データを所定のアドレスへ配置しておく必要があります(配置されていない場合は、エラーを出します)。

BPE圧縮データファイルはデフォルト設定では開始アドレス0000hからのBSAVEヘッダを付けた状態で保存されます。0000h以外のアドレスへロードするにはオフセット値を設定します。

　指定のアドレスの先頭に 「@」を付けるとVRAMを指定することになります。

　なお、10000h以上(後半64KB)のVRAMを指定する場合は10進数で指定してください。(16進数ではOverflowでエラーになります)

　アドレスの指定は変数でもOKです。計算式も書けます。

Download TRUTH.LZH(80KB) | ZIP(79KB) | DSK(720KB)


Download EXT.LZH(31KB) | ZIP(31KB) | DSK(720KB)

COPY形式CGデータの展開

　圧縮したデータがCOPY形式のCGデータに限り、書式はこのように変わります。

　矩形圧縮データ以外を CALL EXTCOPY で使用するとエラーになります。逆に矩形圧縮データを CALL EXT で使用してもエラーになります。BPE圧縮データには圧縮前のデータ形式が記述してあり、展開時にこのパラメータを読んでいます。

VRAMは全てのページが縦に256ドットずつ繋がっているものと考えます（0～511 または 0～1023）。y座標に256以上の数値を入れると、ページ0以外のページへ展開できたりします。

2.4 展開方向付き・COPY形式CGの展開

　COPY形式のCGデータ限定機能で、展開方向を指定しながら矩形データを展開します。

2.5 ロジカルオペレーション付き・COPY形式CGの展開

　BASICのCOPY文と同等の「ロジカルオペレーション」をかけながら矩形データを展開します。特に「TPSET」による重ね合わせは便利。

Download EXTCOPY.LZH(27KB) | ZIP(27KB) | DSK(720KB)

データの圧縮について

　Byte Pair Encodingの圧縮技法は、データ圧縮処理に大変時間がかかります。特にMSX2/2+ではあまりにも遅くて暴走しているように見える場合があります。佐野友則さん制作の EBPEMSX.COM は当クラブのものより高速化されていますので、MSX実機では佐野さんのアプリをおすすめします。

　BPE圧縮アプリ毎に圧縮結果(ファイルサイズ)が異なることがありますが、展開されるデータに支障はありません。

　1997年6月にBPE圧縮の仕様を若干変更しました。旧仕様ではアルゴリズム上のミスで正常に展開できないデータを作る場合があり、新仕様を搭載したDMシステム2(97/06/01以降)では旧仕様のBPEデータが正常に展開できません。旧仕様のBPEデータを新仕様のシステムで利用するには、佐野友則さんのBPE補正ツール「FIXBPE」でこの問題が回避できます。

データの展開について

　展開先アドレスは元データを潰さない限り自由です。むしろ展開中のデータの上にそのデータを展開するなど、元データを絶対に潰さないよう展開先アドレスと展開されるサイズには十分気を配ってください。最悪の場合、マシンが永久ループ状態したり暴走することがあります。

　元データがVRAMに配置されている場合、SCREEN5以上のスクリーンモードでないと正常に展開できないことがあります(VDPの仕様です)。

　VRAM-VRAM間のBPE展開では展開先への書き込みにVDPコマンドを利用しているため、SCREEN5・SCREEN6では128バイト、SCREEN7以上では256バイト単位のアドレスしか指定できません。1バイト単位の微妙な転送が必要な場合は、とりあえず別の部分に展開し、CALL BLOCK等で目的の場所へ転送するなどの工夫で解決してください。

　UNIX版「fMSX」のソースから派生した一部のMSXエミュレータではVDPエミュレーションに致命的なバグがある為、BPE展開機能をご利用できない場合があります。

ヘッダ(3 bytes 又は 7 Bytes)

識別コード(ID)

  b7 b6 b5 b4 b3 b2 b1 b0
  × Ｓ Ｓ Ｓ Ｖ ｎ ｎ ｎ
     ~~~~~~~~ ~~~~~~~~~~~ bit3～0 識別コード(0～15)
         |                        ※b3はVRAMへ展開するフラグ
         |                 0      ベタRAMデータ  (.DAT .TXT等)
         |                 1      BGMデータ      (.BGM .MGS)
         |                 2      SEデータ       (.SE)
         |                 3      RAM用バイナリー(.OBJ .BIN)
         |                 4      パレットデータ (.PLn .BPn)
         |                 5～7   予約
         |                 8      ベタVRAMデータ (.SCn .SRn)
         |                 9      COPY形式CG     (.PIn .GLn)
         |                10      PCMデータ      (.PCM .PCP)
         |                11～15  予約
         |
         +--------------- bit6～4 スクリーンモード(5～12:-5した値)
                                  VRAMのCGデータ(識別コード8,9)のみ有効
                                  sc4以下の場合は0(sc5)になる
                                  ※この情報は無くても構わない

圧縮データ

0FFh: 終了コード

　具体的な圧縮方法について、詳しくは佐野友則さんの「解説・BPE圧縮」をご覧ください。→ http://www.human.waseda.ac.jp/~j96b0759/bpe/