Gigamix DM-SYSTEM2

BPE圧縮の展開機能

updated:

第1章 概要

Byte Pair Encoding(BPE)とは

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

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

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

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

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

Byte Pair Encoding(BPE)の特徴

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

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

Takashi Kobayashi @nf_ban 返信先: @nf_banさん 実機(FS-A1ST)でフロッピーディスクからデータ読み込み+BPE展開する動画。やっぱりR800モードは速いです。
BPE展開のサンプル動画(MSX turbo R利用時)

Takashi Kobayashi @nf_ban 返信先: @nf_banさん MSX2とDMシステム2によるSCREEN8画像のBPE展開サンプル動画
BPE展開のサンプル動画(MSX2利用時)
Download DSK(84KB)
Run TRUTH.DSK on WebMSX

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

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

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

第2章 DMシステム2での使用方法

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 になります。

EBPE.EXEは、Windows 95/98の「MS-DOSプロンプト」からでも実行できます。

EBPE32.EXEは、Win32環境(32bit/64bit版 Windows)の「コマンド プロンプト」上で実行します。

Windows 10以降の「コマンド プロンプト」でEBPE32.EXEを実行すると、一部の環境ではセキュリティソフトによってBPEデータの出力後に即削除される現象が発生する ようです。後述のバッチファイルでは削除される現象が発生しない ようです。

コマンドオプション

コマンドオプション 一覧表
-h ヘルプメッセージを表示します
-b# 辞書のバッファサイズを変更します(# ← 256~32768)
-i# DMシステム2のデータ形式を直接指定します(# ← 16進数で)
-m 出力ファイルにMSXのBSAVEヘッダを付けません
-m- 出力ファイルにMSXのBSAVEヘッダを付けます(デフォルト設定)
-a 辞書のバッファサイズを自動調整します
-a- 辞書のバッファサイズ自動調整を行いません(デフォルト設定)
-v 圧縮時の状況を詳細表示します
※出力ファイルの拡張子を省略した場合の拡張子は .BPE になります。

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

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

※MSX-DOS版 EBPE.COMの最大バッファサイズは 8192 です。
※MSX-DOS版 EBPEMSX.COMの最大バッファサイズは 12288 です。

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

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

 A>EBPE -a -b32768 hogehoge.dat

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

※MSX-DOS版 EBPE.COM・EBPEMSX.COM では -aオプションが利用できません。

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

Win32用のBPEエンコーダが作れたので、90年代当時は実行したくなかった「辞書バッファサイズを手動でちまちま変えて圧縮作業を繰り返しファイルサイズが一番小さなものを採用する」という行為を今のCPU(Core i7)でブン回してみたら1分で結果が出るのでこの強引な手法が最適解になってしまった2021年。 — Takashi Kobayashi (@nf_ban) 2021年1月3日
バッチファイルの概要

Windowsのコマンドプロンプトを使って、MSXのSCREEN7 BSAVE画像からDMシステム2のBPE圧縮データを作る https://www.gigamix.jp/ds2/ds2bpe.html 手順の動画 ※字が小さいのでPCで見てください pic.twitter.com/Lv2ORvGYb7 — Takashi Kobayashi (@nf_ban) 2022年7月30日
バッチファイルを起動してデータを作成する動画

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

 以下のテキストデータを各種テキストエディタへコピーし、バッチファイル(拡張子 .BAT)としてファイル保存してください。

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と圧縮対象ファイルとバッチファイルを同じフォルダへ配置したうえで、コマンド プロンプトよりバッチファイルを実行してください。

C>EBPEBAT <圧縮対象ファイル>

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

C>dir <ファイル名(8文字)>.* /OS

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

BPE圧縮データの展開

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

CALL EXT(展開元アドレス,展開先アドレス)
ex.) CALL EXT(&HD800,&HC000)  ← D800h(RAM)に配置した圧縮データを C000h(RAM)へ展開

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

BLOAD "hogehoge.bpe",,&HD800  ← BPE圧縮データをD800h(RAM)にロードする
CALL LOAD("hogehoge.bpe",&H3800,7)  ← BPE圧縮データを3800h(RAM)にロードする

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

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

CALL EXT(&HD800,@0)  ← D800h(RAM)に配置した圧縮データを 0000h(VRAM)へ展開
CALL EXT(@&H4000,&HC000)  ← 4000h(VRAM)に配置した圧縮データを C000h(RAM)へ展開

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

CALL EXT(@65536!,@98304!)  ← 10000h(VRAM)に配置した圧縮データを 18000h(VRAM)へ展開

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

CALL EXT(-16384,VAL("&H"+A$)*256+4096)

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

元データをVRAMに配置し展開先もVRAMを指定する場合、スクリーンモードはSCREEN5以上(ビットマップモード)を指定してください。SCREEN4以下ではVDPの仕様により正常に展開できません(実機やopenMSXでは正常に動作しませんが、WebMSXでは動作してしまいます。もしVRAM→VRAMで動くならそれは偶然なのであてにしないでください)。SCREEN4以下のスクリーンモードでVRAMへBPE展開する場合は、元データをRAMに配置してください

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

COPY形式CGデータの展開

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

CALL EXTCOPY(展開元アドレス,x座標,y座標)
ex.) CALL EXTCOPY(@32768,64,0)  ← 8000h(VRAM)に配置した矩形圧縮データを(64,0)へ展開

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

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

CALL EXTCOPY(@32768,64,578)  ← 8000h(VRAM)に配置した矩形圧縮データを(64,578)の座標(=ページ2の(64,64))へ展開
※COPY形式は展開番地を指定するわけではありませんので、x座標、y座標に @ を付けても無効になります。

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

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

CALL EXTCOPY(展開元アドレス,x座標,y座標,方向)
ex.) CALL EXTCOPY(@32768,64,64,2)  ←(64,64)を起点に上下反転して矩形圧縮データを展開
方向の一覧表
0 通常(基点は左上、右下へ展開)
1 左右反転(基点は右上、左下へ展開)
2 上下反転(基点は左下、右上へ展開)
3 左右+上下反転(基点は右下、左上へ展開)

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

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

CALL EXTCOPY(展開元,x座標,y座標,方向),ロジカルオペレーション
ex.) CALL EXTCOPY(@32768,64,64,2),TPSET  ← TPSETで展開
ex.) CALL EXTCOPY(@32768,64,64,2),TXOR  ← TXORで展開

第3章 使用上の注意

データの圧縮について

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

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

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

データの展開について

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

第4章 圧縮時のデータ形式の分類

 DMシステム2のBPE圧縮は「バイナリシステム」と組み合わせることにより、データの自動展開と即利用が指定できます。

 圧縮時にデータ形式が認識されるものは以下の通りです。

データ形式の分類一覧表
No. データ形式の内容 拡張子(デフォルト)
0 その他(RAMへ転送するベタデータ)
1 BGMデータ .MGS .BGM
2 SEDRVに対応したSEテーブル .SE
3 RAMへ転送するバイナリーデータ .OBJ .BIN
4 DM-PALETに対応したパレットテーブル .PLn .BPn
8 VRAMへ転送するベタデータ .SCn .SRn
9 COPY形式のCGデータ .PIn .GLn
10 PCMデータ .PCM .PCP
※データ形式は圧縮ツールのオプション指定で変更も可能です。

第5章 BPE形式ヘッダの仕様

 DMシステム2で採用しているBPE圧縮フォーマットは「ヘッダ」「実データ」の2部に分けられます。ヘッダには圧縮時のデータ形式や展開サイズなどの重要な情報が格納されています。

ヘッダ(3 bytes 又は 7 Bytes)

通常の場合のヘッダ
+0~+1 "Bp"
+2 識別コード(ID)
+3~ 圧縮データ
COPY形式CGデータのヘッダ
+0~+1 "Bp"
+2 識別コード(ID)
+3~+4 横サイズ(2バイト)
+5~+6 縦サイズ(2バイト)
+7~ 圧縮データ

識別コード(ID)

  b7 b6 b5 b4 b3 b2 b1 b0
  × S S S V n n n
     ~~~~~~~~ ~~~~~~~~~~~ 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)になる
                                  ※この情報は無くても構わない

謝辞

 Win32版は TAKEDA, toshiyaさんの MS-DOS Playerを用いて作成しました。ソフト資産を継承できる有益なアプリに感謝いたします。→ http://takeda-toshiya.my.coocan.jp/msdos/

 MS-DOS Player上で EBPE.EXE を実行する場合は以下のようになります。

C>msdos -e EBPE [.<出力ファイルの拡張子>] [-|/<options>] <圧縮ファイル>
C>msdos -cEBPE32.EXE -e -x EBPE.EXE ←Win32環境用コマンドを作成

BPE以外の有用な圧縮・展開ソリューション

2021年現在、Z80で実行可能かつBPE以上に高性能な圧縮アルゴリズムが存在します。こちらのプロダクトとDMシステム2を組み合わせていただくのも有用かと思います。


[Back]トップページへ