GIGAMIX DM-SYSTEM2
BPE圧縮の展開機能
updated: May 6, 1998

  1. 概要
    1. "Byte Pair Encoding"とは
    2. 圧縮対象について

  2. DMシステム2からの利用方法
    1. BPE圧縮データを作る
    2. 圧縮データの展開
    3. COPY形式CGの展開
    4. 展開方向付き・COPY形式CGの展開
    5. ロジカルオペレーション付き・COPY形式CGの展開

  3. 使用上の注意
    1. データの圧縮について
    2. データの展開について

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

  5. BPEフォーマット・仕様
    1. ヘッダ
    2. 圧縮データ

第1章 概要

1.1 "Byte Pair Encoding"とは

 「C MAGAZINE(ソフトバンク刊)」にて紹介された、新しい圧縮アルゴリズムです。

 隣同士のデータの組み合わせ(2バイト)を1バイトに圧縮して「辞書」を作ります。以後、既に使われた組み合わせのデータは「辞書」から、新たに見つけた組み合わせは「辞書」を作って…の繰り返しとなります。

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

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


1.2 BPE圧縮のメリット

 BPE圧縮は他の圧縮アルゴリズムと決してひけを取らない圧縮率を誇っております。さすがにLZ法を超える圧縮率は出せませんが、あと少しでLZ法と肩を並べる程度の圧縮率が期待できます。

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

 CGから見た圧縮率から言えば、特にscreen 8以上のCGの圧縮率が良く、MAG形式のようにタイルパターンに頼らずとも圧縮率が期待できます。また、COPY形式の矩形CGデータは矩形のまま圧縮でき、展開時にロジカルオペレーションと展開方向を指定することができます。TPSETしながら展開する等、夢は膨らみます(笑)。

 BPE圧縮は可逆圧縮(データが100%復元する)ですので、CG以外のデータでも有効利用できます。VRAMの他に「RAMへの展開機能」も用意しましたので、BGMデータやマシン語等のバイナリデータ、テキスト、その他何でも指定されたメモリへガンガン展開できます。


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

2.1 BPE圧縮データを作る

 まず、圧縮しないことには話になりませんね。

 BPE圧縮ツールは3種類あります。マシンに併せてご利用下さい。

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

DM-BPE encoder
EBPESET.LZH (23KB)
MSX用BPEエンコーダ&デコーダ
BPEMSX.LZH (13KB)

2.2 圧縮データの展開

RAM及びVRAMに配置されたBPE圧縮データを展開します。 事前にBPE圧縮データを所定のアドレスへ配置しておく必要があります(配置されていない場合は、エラーを出します)。 アドレスの先頭に @ を付けるとVRAMを指定することになります。 10000h(64KB)以上のVRAMを指定する場合は10進数で指定してください。(16進数ではOverflowでエラーになります) アドレスの指定は変数でもOKです。計算式も書けます。

sample program
EXT.LZH (8KB)

2.3 COPY形式CGの展開

圧縮したデータがCOPY形式のCGデータに限り、書式はこのように変わります。 VRAMは全てのページが縦に256ドットずつ繋がっているものと考えます。y座標に256以上の数値を入れると、他のページへいきなり展開できたりします。

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

COPY形式特有の方向指定で、反転処理しながら矩形データを展開。

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

BASICのcopy文と同等のロジカルオペレーションをかけつつ、データを展開。特にTPSETによる重ね合わせは便利。

sample program
EXTCOPY.LZH (4KB)

第3章 使用上の注意

3.1 データの圧縮について

  1. BPEフォーマットはデータ圧縮に大変時間がかかります。あのPentiumプロセッサを用いても数秒はかかる為、MSX2/2+ではあまりにも遅くて暴走しているように見える場合があります(^^;。しばらく我慢してみてください。

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

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

3.2 データの展開について

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

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

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

  4. MSXエミュレータfMSXの中でも、AT互換機版(fMSX-DOS)Mac版(fMSX for Mac)など、本家UNIX版のソースを引き継いだものはそのVDPエミュレーションに致命的なバグがある為、残念ながら今のところBPE展開機能をご利用できません。ニュースグループcomp.sys.msxを通じてfMSXの作者さんへバグ報告を行いましたので、近日中にリリースされるであろう最新バージョンでは問題なく動作すると思います。多分。


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

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

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

      No. データ形式の内容拡張子(デフォルト)

      0その他(RAMへ転送するベタデータ)
      1BGMデータ.MGS .BGM
      2SEDRVに対応したSEテーブル.SE
      3RAMへ転送するバイナリーデータ.OBJ .BIN
      4DM-PALETに対応したパレットテーブル .PLn .BPn
      8VRAMへ転送するベタデータ.SCn .SRn
      9COPY形式のCGデータ.PIn .GLn
      10 PCMデータ.PCM .PCP

      ※データ形式は圧縮ツールのオプション指定で変更も可能です。


    第5章 BPEフォーマット・仕様

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


    5.1 ヘッダ(3 bytes 又は 7 Bytes)

    通常の場合COPY形式CGファイル


    +0〜+1 "Bp"+0〜+1 "Bp"
    +2識別コード (ID) +2識別コード (ID)
    +3〜 圧縮データ+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)になる
                                      ※この情報は無くても構わない
    

    5.2 圧縮データ

    0FFh: 終了コード

    圧縮方法について、詳しくは佐野友則@早稲田大さんの「解説・BPE圧縮」をご覧ください。

    http://www.human.waseda.ac.jp/~j96b0759/bpe/

    [Back]
    Copyright (c) 1998 GIGAMIX, All rights reserved.