各種圧縮アルゴリズムと解凍ルーチンの性能を評価する


img
ここ最近さまざまな圧縮アルゴリズムを Z80 など下位 CPU への実装するのが流行っているようなので
P6 での実装テストとともにベンチマークを行ってみた。



■ 物 置


比較グラフはこのページの一番下。
このテストは P6 用だが、基本的に Z80 RAM to RAM 汎用のつもり。

unpackbench_20190831.zip ソース付きテストコード

不特定の圧縮バイナリを展開する目的ではなくベンチマークが目的なので、このソースを流用する前に必ずオリジナルを参照すること。
気が向いたら新しめのアルゴリムを追記するかも。独自の実装で良い成果が出たらテストコードも追記 or 差し替える予定。

P6 で圧縮を必要とするのは、おおむね「無駄にでかい VRAM」のデータだと思うので、以下の画像をサンプルとして使用する。



左が 160x200 サイズに縮小、右が P6 向け 16(15) 色にそれを減色したもの。
アルゴリズムによって向き不向きがあるだろうから一概にこれで測れるとは思わないが、結果がわかりやすいので。

データは格納方法によって4種類のバイナリに分別した。

1)16色=4bpp を L プレーンと H プレーンに分割する。2bpp * 2 プレーンの、どノーマルなやりかた。
2)2ドットを 1byte の上下に格納する 4bpp データ。展開がめんどい。
3)1)の縦方向の格納。
4)2)の縦方向の格納。

縦方向格納はとくにデータが画像であるという性質に依存するが、ものは試しということで。
縦スキャン(プロット)方向については上から下へ行った後、下から上へ蛇行するような感じでやったほうが多少オトクかもしれないが、今回はパス。
圧縮とは関係ないが、普通にフルスクリーン描画する場合でも、横x縦で描画するより縦x横の方が速い。40x200 と 200x40 の差が出る。

2〜4についてはは圧縮率を見るのが主目的。
たいていの処理は、展開時に「前回バラしたデータを参照してコピーする」という処理が挟まる関係で、展開したデータを L, H プレーンに分けたり
縦→横方向に加工したりすると参照がかなり面倒になる。なので今回はバッファを用意している。現実問題 P6 でこれはコストが高い。

また、2〜4のプロットは筆者の PSET ルーチンのやる気次第なのもあって速度はあまり参考にならない。
実際、P6 では展開の速度がどうという話よりもディスク等からのロード時間(と入れ替え)が問題の大半であろうから、圧縮率を重視する意味はある。


テストした圧縮アルゴリズムは、なるべく大元のオリジナルを使用しているが、派生・改良版があるものがある。
筆者が独自に実装した exo3 なども、それら改良版の方が性能がいいものがあるので、差し替えると結果が変わってくるだろう。

uniabis 氏によるこちらのページ (URL: https://uniabis.net/pico/msx/z80packer/) (GitHub) を参考に。

各個別アルゴリズムの「+GIF 画像」をクリックすると GIF アニメ再生。これは method.1 の展開速度を見るものである。



Raworiginalcompressedpercentage
method.18000
8000
8000
8000
100%
100%
method.216000 1600100%
method.38000
8000
8000
8000
100%
100%
method.416000 16000100%

GIF 画像1
raw(生)データ。無圧縮で展開方向が違うだけなのでサイズは全て 16000byte である。
GIF 画像ではバッファを用いずにディスクから直接 VRAM にロードしている。
他のものとの比較するならバッファにロードしたあと、LDIR の速度で見ないといけないのだが、P6 において生データをバッファリングする人は居ない(断言)ので。
なお、このページの最後の比較グラフは LDIR で計測してある。


Exomizer3originalcompressedpercentage
method.18000
8000
4819
5854
60.2%
73.1%
method.216000 800050.0%
method.38000
8000
4445
5611
55.5%
70.1%
method.416000 753047.0%

GIF 画像1
Exomizer3 (URL:https://github.com/antoniovillena/deexo)
バージョンが 2 から 3 になってビットストリームフォーマットやオプション類が変わってしまっている。
現状、ソースコードには 2 系と 3 系が含まれていて "opt" が付くものが 3 系である(が、現状 github の 3 系デコーダはバグがある模様)。
"b" は "backward" のことで、最後尾から先頭に向かって圧縮(展開)する。
圧縮バイナリと展開先がオーバーラップしてしまう場合に、圧縮バイナリを上書きしながら展開するために使う。

圧縮率は良好。ソースは筆者の独自実装だが展開速度がいまひとつでサイズも大きめなので差し替えた方が良いかも。
Exomizer は 2 系 3 系ともに 156byte のテーブル用ワークを必要とする。

こんな感じで圧縮。raw オプションを付けると -P7 -T0 が暗黙で指定されるらしい。

> exomizer raw hoge.bin -o hoge.exo



Exomizer2originalcompressedpercentage
method.18000
8000
4820
5854
60.2%
73.1%
method.216000 800150.0%
method.38000
8000
4445
5611
55.5%
70.1%
method.416000 753147.0%

GIF 画像1
Exomizer2。Exo3 との比較用として。
見て分かるとおり、圧縮率には差が無い。
simple 版を使用。圧縮オプションは以下の通り。simple 版でない方は -c が不要。-P0 を付けるのを忘れずに。
これに限った話ではないけれど、256byte 境界のワークを必要とするものは地味に取り回しがキツいかも。

> exomizer raw -P0 -c hoge.bin -o hoge.exo



LZ4originalcompressedpercentage
method.18000
8000
6626
7417
82.8%
92.7%
method.216000 1115469.7%
method.38000
8000
6016
7083
75.2%
88.5%
method.416000 1038164.8%

GIF 画像1
LZ4。(URL:https://lz4.github.io/lz4/)

幅広く使われている。Z80 だけでなく 8088、6502、65c816、68k などなど様々な実装がある。拙作 GBZ80 版も。
圧縮率はたいしたことないが展開速度がやたら速いのが特徴。

圧縮が効くかどうかは対象にもよるが、あまり期待しない方が良い。

LZ4 は拙作ストリームローダーもあるが今回は未使用 → R&D ページ。
これは自己書き換えを使ったものだが、無くてもなんとかなる。
メモリ空間に余裕の無い 8bit マシンでは、展開速度は多少落ちるものの、ストリームローダーがあれば使わない理由はないのであった方が嬉しい。

圧縮は以下の通り。-9 は少しでも圧縮率を高めるためのオプション。普通に lz4.exe にドラッグ&ドロップでも良い。

> lz4 -9 hoge.bin



LZ48originalcompressedpercentage
method.18000
8000
6435
7249
80.4%
90.6%
method.216000 1182973.9%
method.38000
8000
5823
6902
72.7%
86.2%
method.416000 1093168.3%

GIF 画像1
LZ48。(URL:http://www.cpcwiki.eu/forum/programming/lz48-cruncherdecruncher/)

名前から分かるとおり LZ48/LZ49 は LZ4 の派生版である。
8bit マシンで使うには冗長と思われる部分を弄ってチューニングしたもの。コピーオフセットに 2byte も要らんやろ、とかそういう発想。

LZ4 と比べてもさらに速い。速度特化なら lz4 のリプレースになり得る。
が、圧縮率 80%〜90% の場合は、ほぼ ldir の速度なのであまり参考にならないかも。

オリジナルの lz4 と違ってドラッグ&ドロップで圧縮できない。

> lz48 -i input.bin -o output.lz48



LZ49originalcompressedpercentage
method.18000
8000
6314
7155
78.9%
89.4%
method.216000 1083067.6%
method.38000
8000
5668
6790
70.8%
84.8%
method.416000 1001862.6%

GIF 画像1
LZ49。(URL:http://www.cpcwiki.eu/forum/programming/lz48-cruncherdecruncher/)

別に LZ48 より LZ49 の方が良いわけではなく、上に書いた「コピーオフセットに 2byte も要らんやろ → いや 9bit くらいは要る」という違い。
LZ4 含め、三種ともに圧縮率に大きな違いは無い。
解凍ルーチンは整形以外にオリジナルから微妙に弄ってある。

LZ48/LZ49 は Z80 用の圧縮ルーチンも提供されている。


ZX7originalcompressedpercentage
method.18000
8000
5436
6364
67.9%
79.5%
method.216000 912357.0%
method.38000
8000
4840
6013
60.5%
75.1%
method.416000 831151.9%

GIF 画像1
ZX7。(URL:http://www.cpcwiki.eu/forum/programming/zx7-cruncher-(from-spectrum-world)/)

バランスが取れている。Exomizer より圧縮率は低いが展開速度は速い。
展開に際してテーブルやワークエリアが必要ないのは有利な点だと思う。

解凍ルーチンはサイズ・速度別に 3 種提供されている。今回は mega 版を使用。サイズは大きいが一番速い。
サイズが小さい方がいい場合は 69byte の standard 版で。

ZX7 は ZX7b という派生版もある。(URL:https://github.com/antoniovillena/zx7b)



PMA(pm2)originalcompressedpercentage
method.18000
8000
5248
6144
65.6%
76.8%
method.216000 857653.6%
method.38000
8000
4608
5760
57.6%
72.0%
method.416000 793649.6%

GIF 画像1
pma。(URL:http://www.asahi-net.or.jp/~am9y-mn/fswlist.htm)
MSX や CP/M でよく使われた形式。
書庫機能なども備えているが、単体ファイルのメモリへの解凍という部分だけに限っても他のアルゴリズムよりサイズがかなり大きい。
いち圧縮フォーマットとして見た場合、様々な観点から別の形式を使った方がいいと思う。
用途が違うのでそもそも比較するのが無意味なのだが。

ファイルヘッダは lharc などの level0 と同じようだ。
pma と lh5 についてはテスト用実行バイナリのみとする。ほぼ丸パクリなので。

現状、PMA ファイルを作るなら CP/M エミュレータで作るのが一番速いと思う。

> cpm.exe pmarc2.com hoge.pma hoge.bin



LZH(lh5)originalcompressedpercentage
method.18000
8000
5132
5988
64.1%
74.8%
method.216000 857853.6%
method.38000
8000
4628
5631
57.8%
70.3%
method.416000 791249.4%

GIF 画像1
lzh(lh5)。
pma よりも更にコードサイズが大きく必要なワークエリアサイズも多い。

圧縮は LHA255.EXE を使用。

> msdos lha.exe a hoge.lzh hoge.bin



hrustoriginalcompressedpercentage
method.18000
8000
5218
6162
65.2%
77.0%
method.216000 874154.6%
method.38000
8000
4621
5722
57.7%
71.5%
method.416000 801850.1%

GIF 画像1
hrust。(URL:https://code.google.com/archive/p/mhmt/source/default/source)
ZX-Spectrum 方面のツールらしい。Z80 用には MegaLZ と Hrust の解凍ルーチンが提供されており、それを使用した。
ヘッダなし(-zxh なし)、かつ SP レジスタを使わないものを選んだが、これは少しばかり遅いらしい。そのかわり割り込み耐性がある。
プログラムを見ると、フェッチが ld r,(ix+0) なのが確かに残念な感じではある。

圧縮率は ZX7 より少し良い。速度も遅くてこれなら十分だと思う。ワークを使わずレジスタだけで完結するのも○。

> mhmt-base -hst hoge.bin



MegaLZoriginalcompressedpercentage
method.18000
8000
5210
6212
65.1%
77.6%
method.216000 886555.4%
method.38000
8000
4652
5818
58.1%
72.7%
method.416000 809950.6%

GIF 画像1
MegaLZ。
hrust と同じツールを使用。
-hst の部分を -mlz にするだけで良い。
hrst より展開ルーチンサイズが小さい。

> mhmt-base -mlz hoge.bin



LZEoriginalcompressedpercentage
method.18000
8000
5632
6671
70.4%
83.3%
method.216000 954459.6%
method.38000
8000
5057
6269
63.2%
78.3%
method.416000 866354.1%

GIF 画像1
LZE。(URL:http://gorry.haun.org/pw/?lze)
ダウンロードリンクが切れているかも。
全体の中でも中段グループの真ん中に位置しているバランス型。比較対象は LZSA2 になるか。

改良版が存在する→>https://github.com/uniabis/lzee
こちらは圧縮フォーマット自体を見直しているようで、エンコーダから別になっている。



LZSA1originalcompressedpercentage
method.18000
8000
6205
7148
77.5%
89.3%
method.216000 1051465.7%
method.38000
8000
5495
6686
68.6%
83.5%
method.416000 954759.6%

GIF 画像1
LZSA1。(URL:https://github.com/emmanuel-marty/lzsa)

LZSA1 は LZ4 のリプレースを狙ったもので、圧縮率・速度ともによりよい結果を出している。
自己書き換えも無いし、後ろ向き展開も出来る。6502/8088 版も提供されている。拙作 GBZ80 版も。
速度優先なら LZSA1、圧縮率優先なら LZSA2 と使い分けするといいかもしれない。

> lzsa.exe -f1 -r hoge.bin hoge.lzsa1



LZSA2originalcompressedpercentage
method.18000
8000
5660
6654
70.7%
83.1%
method.216000 925857.8%
method.38000
8000
4966
6187
62.0%
77.3%
method.416000 836052.2%

GIF 画像1
LZSA2。URL などは同じ。これも 6502/8088 版の他、拙作 GBZ80 版がある。

こちらは ZX7 のリプレースを目指したもので圧縮率を向上しながら ZX7 以上の速度を謳っている。
全体の中でも中段グループの真ん中に位置しているバランス型。

LZSA は比較的新しいのもあって活動が活発である。もしかしたら今後 LZSA3... となっていくのかもしれない。

エンコードは -f1 オプションを -f2 にするだけである。

> lzsa.exe -f2 -r hoge.bin hoge.lzsa2




Pletteroriginalcompressedpercentage
method.18000
8000
5405
6333
67.5%
79.1%
method.216000 911456.9%
method.38000
8000
4842
6016
60.5%
75.2%
method.416000 831351.9%

GIF 画像1
Pletter。(URL:http://www.xl2s.tk/)
MSX 関連らしい。全く未知だった。
バイナリの途中から長さを指定して圧縮する機能があるなどユニークである。

圧縮率はそこそこ。ワークも使わない。
展開ルーチン自体も小さいが、サイズを犠牲にすればもう少し速くなりそうな気もする。

> pletter hoge.bin



Shrinkleroriginalcompressedpercentage
method.18000
8000
4872
5776
60.9%
72.2%
method.216000 815250.9%
method.38000
8000
3976
5052
49.7%
63.1%
method.416000 685642.8%

GIF 画像1
Shrinkler。(URL:https://github.com/askeksa/Shrinkler)
元は AMIGA 環境のツールらしい。Z80 版は 68k アセンブラからの移植のようだ。
(URL:https://cpcrulez.fr/applications_tools_cruncher_shrinkler_Z80.htm)

圧縮率が高い。4 を 7-Zip の LZMA2 最高圧縮で処理すると 7273byte(45.4%) なのでいかに高圧縮か分かる。
そしてこの遅さである。256byte 境界の大型ワーク 3072byte・裏レジスタ・未公開命令・自己書き換えまで駆使してこれ。
16bit*16bit=32bit の乗算などが特に重そうな印象。オリジナルと 64KB 環境のスケール感の違いが色々と見受けられる。
しかし解凍ルーチン自体はそこそこコンパクトなので用途次第といったところか。8bit 特化版とかあれば・・・。

ZX7b のページに shr8k という別実装版(?)がある。(URL:https://github.com/antoniovillena/zx7b)
差し替え用にソースは入れてあるが、速度の差はあまり無い。

オプションには生バイナリデータとして扱うために -d をつける。
圧縮時に表示がうるさいので -p も付けると吉。

> shrinkler -d -p hoge.bin hoge.shr



BitBusteroriginalcompressedpercentage
method.18000
8000
5503
6421
68.7%
80.2%
method.216000 930758.1%
method.38000
8000
4919
6079
61.4%
75.9%
method.416000 851253.2%

GIF 画像1
BitBuster Extreme。(URL:https://cpcrulez.fr/applications_tools_cruncher_bitbuster_extreme_Z80.htm)
CPC 方面で知った。MSX でも使われていたとか。
元々 BitBuster 1.2 というものがあり、Extreme はそのバリアントである模様。
改変箇所は先頭 4byte にあった元のファイルサイズを削ったものらしい。
この記事で取り上げるものは、出来るだけ元の版に準拠したいのだが、どうにも探しきれなかったので・・・。

自己書き換えなし・ワーク不要だが裏レジスタを使っているのが競合より不利かもしれない。
あと、圧縮が若干遅い気がする。

> pack hoge.bin



aPLiboriginalcompressedpercentage
method.18000
8000
5417
6368
67.7%
79.6%
method.216000 911556.9%
method.38000
8000
4810
5969
60.1%
74.6%
method.416000 829451.8%

GIF 画像1
aPLib。基本的には最近(?)の CPU や高級言語で動くものらしい。
オリジナル版と圧縮ツールは(URL:http://www.ibsensoftware.com/products_aPLib.html)にある。
Z80 版解凍ルーチンは(URL: http://cngsoft.livejournal.com/268202.html)

古いツールを使えばヘッダがつかないバイナリが出力できたのだけど、新しめの v1.1.1 だと 24byte(?) のヘッダが付くようになっている。
TI 電卓などへの移植例もあったようだ。

フラグで逆方向展開もできるようになっている。未公開命令使用・自己書き換えなし・ワーク不要。
フェッチが ld r,(ix+0) なのが地味に痛い。

> appack c hoge.bin hoge.apk



Pucrunchoriginalcompressedpercentage
method.18000
8000
5293
6266
66.1%
78.3%
method.216000 893355.8%
method.38000
8000
4852
6004
60.6%
75.0%
method.416000 828151.7%

GIF 画像1
Pucrunch。(URL:https://github.com/mist64/pucrunch)
元は C64 のツールらしい。6502 版のソースがオリジナル。
URL で示したサイトが本家だと思う(自信ない)。ここに含まれる Z80 版ソースは GB 用なので注意。
圧縮ツールと Z80 版解凍ルーチンは (URL:https://cpcrulez.fr/applications_tools_cruncher_PUCrunch_Z80.htm)で入手した。

GB 関係の重鎮が前世紀に GBZ80 向けに移植を行っていたようだ。流石。
Z80 版はその再移植になっていて、それゆえコードサイズと速度に少し難がある。
SMS 版への移植もあり。(URL:http://www.smspower.org/maxim/SMSSoftware/Compressors)
GB/SMS はコードが ROM にあることが前提になっているので自己書き換えできない。RAM 領域にワークを設定するようになっている。

-h でオプション一覧が出る。
圧縮はちょっとわかりにくいので注意。以下の通り。

> pucrunch -d -c0 hoge.bin hoge.puc



以上。
やはり注目株は EXO, ZX7, LZSA あたりだろうか。海外のフォーラムでもよく話題に上っているようだった。
LZ4 は速度の目安として一つのスタンダードになっているようだ。

ほかに比較的新しめのフォーマットでいうと、以下のようなものがある(が Z80 版は今のところ無さそう)
LZF https://github.com/ning/compress
LZ5(Lizardに改名) https://github.com/inikep/lizard
LZO http://www.oberhumer.com/opensource/lzo/

話題性や開発の活発さというのも一つの指標になるし、それ以外にもコードベースが ROM か RAM か、裏レジスタや未公開命令は使うのか、
ワークサイズはどれくらいか、自己書き換えはありか、ライセンスは、などなど圧縮率などの数字だけ見ていては分からない部分が多々あるので、
どれが良いというのは一概には言えない。



圧縮効率と速度のグラフ。method.4 を基準に計測。raw は純粋な 16000bytes の ldir の速度。shrinkler がぶっちぎりで遅いので見づらい。
右上に近いものほどバランスが良い。



▲ TOP