BPE圧縮の展開機能

概要
1. Byte Pair Encoding（BPE）とは
2. BPEの特徴
DMシステム2での利用方法
使用上の注意
1. データの圧縮について
2. データの展開について
圧縮時のデータ形式の分類
BPE形式ヘッダの仕様
謝辞

第1章概要

Byte Pair Encoding（BPE）とは

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

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

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

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

BPEの特徴

Takashi Kobayashi @nf_ban 返信先: @nf_banさん MSX2とDMシステム2によるSCREEN8画像のBPE展開サンプル動画

BPE展開のサンプル動画 on twitter

Takashi Kobayashi @nf_ban 返信先: @nf_banさん実機(FS-A1ST)でフロッピーディスクからデータ読み込み＋BPE展開する動画。やっぱりR800モードは速いです。

BPE展開のサンプル動画 on twitter

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

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

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

　当クラブ独自の実装として、DMシステム2では「VRAMの任意のアドレスへの展開機能」の他に「RAMへの展開機能」もございますので、BGMデータやマシン語等のバイナリデータ、テキスト等なんでも指定されたメモリへ高速にデータ展開できます。また、COPY形式の矩形CGデータは矩形のまま圧縮し、DMシステム2上での展開時にロジカルオペレーションと展開方向を指定できます。下から上方向へ重ね合わせ(TPSET)で展開する等、夢が膨らみます(笑)。

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

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

Exomizer（圧縮率に有利） → https://bitbucket.org/magli143/exomizer/wiki/Home
LZEe（展開速度に有利） → https://github.com/uniabis/lzee
BARGAIN（MSXに特化） → https://www.vector.co.jp/soft/dl/other/msx/se179373.html

第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）

※EBPE.EXEはWindows 95/98のMS-DOSプロンプトからでも実行できます。
※EBPE32.EXEは、Win32環境(32bit/64bit版 Windows)のコマンドプロンプト上で実行します。

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

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

　出力ファイルの拡張子を省略した場合の拡張子は .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オプションが利用できません。

圧縮データの展開

　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)

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

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

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で展開

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

第3章使用上の注意

データの圧縮について

　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展開機能をご利用できない場合があります。

第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
  × Ｓ Ｓ Ｓ Ｖ ｎ ｎ ｎ
     ~~~~~~~~ ~~~~~~~~~~~ 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/

謝辞

　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環境用コマンドを作成

トップページへ