klog/essay086

OSASK-WikiのKの落書きの過去ログ

• 本家：OSA:K
  • 過去ログにコメントしたい人も、本家のこめんと欄に突っ込んでください。
    • そのうちKによって下のこめんと欄に移動しますので。

UPX vs tek

• (2005.01.05-2005.01.06)
• ななしさんにファイルサイズが64KB未満で拡張子を.comにすればとりあえずなんでもUPXで圧縮できると教えてもらったので、その方法でいろいろ実験してみました。
• 実験対象は3つ用意しました。一つはmake46のnec98ディレクトリにある、vgadrv0.ask。もう一つは、OSASK ver.4.7にバンドルされているtest128.bmpをbim2binで-restoreしたものです（テキストばかりやってもしょうがないと思いましたので）。最後の一つは、同じくOSASK ver.4.7のkaos2c.helをbim2binで-restoreしたものです。
• 最初に結論を書くと、こんな感じです。
  • .com化する方法では、圧縮アルゴリズムは「NRV2B/10」というものになる。一方、win32の.exeだと、「NRV2D/10」がデフォルトだが、「NRV2B/10」も選べる。UPX自身の圧縮で比較したところでは、「NRV2D/10」のほうが、0.4%だけ圧縮率がよかった。
  • dos/com形式で「NRV2B/10」の場合、SFXルーチンは128バイトらしい。これは先頭に57バイト、末尾に71バイト。先頭の57バイトは主に圧縮データ＋展開ルーチンの上位転送、変数の初期値代入を行っている。末尾の71バイトは展開ルーチンのコアである。
    • 初期値代入が6バイトくらいなので、合計77バイトだ。このサイズは、UPXの圧縮率からすると絶賛に値する。
  • このヘッダサイズを差し引いた上でtek等と圧縮率を比較すると、

    圧縮率低い ← tek1 tek2 tek0 NRV2B/10 gzip stk5 tek5 → 圧縮率高い

  • となる。つまりUPXはtek2よりもよいが、gzipには勝てない。展開速度的にも、おそらくtek2とgzipの間であろう（tek2はLZOと同じくらいの速さなので）。これだけの圧縮率がありながら、わずか77バイトで展開ルーチンがかけるところは本当にすごい。展開速度と圧縮率という観点では、tekと同じくらいのバランスだと思う。
  • 基本的には安定したアルゴリズムでありその点は評価できる（dgcaは圧縮対象によって順位が乱高下しており、汎用性が乏しい）。ただ、LZ圧縮が効かない領域で大きくロスする性質があり、それが不安定要因になっている。

• 使ったupx： UPX 1.25w
  • 圧縮方法：拡張子を.comに変えて、--bestで圧縮。出てきたファイルのサイズから128を引く。

• SFXルーチン量の見積もり：
  • いくつかのファイルをUPXしてみると、どうも最初の出だしと末尾のいくらかが全く同じである。このヘッダとフッタがSFXルーチンであると見た。
  • そこでvgadrv0.askの最後の1バイトを0a→08に変更したものを用意し、どちらもUPXをかけ、FCコマンドで比較させてみた。これの狙いは、どこからフッタが始まっているのかを見極めることである。
  • 0x0039-0x3292が完全に一致したので、これ以外がヘッダとフッタであると考えられる。これはたかだか136バイトしかないので、aksaを使って逆アセンブルした。これにより、先頭のSFXルーチンは確かに0-0x38までであり、また末尾のSFXルーチンは0x329b-0x32e1であることを確かめた。合計で57+71=128バイトである。
  • このルーチンは16ビットモードで動くことを非常に意識しており、データが16bit単位になっていた。おそらくこれを32bit化しただけのものが「NRV2D/10」ではなかろうかと想像する。
  • またこれはコードを読んだから分かることだが、このルーチンはうまく圧縮できるデータに対してはなかなかよい圧縮率をたたき出せる代わりに、圧縮が効かない部分に差し掛かるとデータを1割以上も増加させてしまう。この観点でl2d3並みである。tek1やtek2やtek0やtek5にはそのような挙動はない。
    • こういう性質は、データの一部がうまく圧縮できなくても、圧縮できるところだけをきっちりと圧縮できるという安定性に直結する。upxでは、そういうデータを含んでいると、そこでサイズを増やしてしまうために、圧縮でがんばっても生きてこない。こういうのは、sarやtarで作ったアーカイブなどではたまに出現する。
    • 例：OSASK ver.4.7にバンドルしたkaodun01.bin（33219バイト）の前に、ヘッダとして16KBの0x00を付け加えたもの。
    • ヘッダは容易に圧縮できるが、本体のこれ以上の圧縮は困難であろう。

      format	無圧縮	upx	paq4	gzip	stk5	stk1	stk2	tek5	tek0
      サイズ	49603	36985	33397	33390	33364	33263	33257	33257	33251
      指標1	149.17	111.23	100.44	100.42	100.34	100.04	100.02	100.02	100.00
      指標2	-1.477	0.000	3.242	3.291	3.498	5.740	6.433	6.433	(inf)

• vgadrv0.askでの比較（テキストファイル）：

  format	無圧縮	tek1	tek2	tek0	yz2	upx	gzip	bzip2	dgca	LZMA	stk5	tek5	PPMd	paq4
  サイズ	64108	15580	14612	13976	13467	12898	12609	11958	11440	11402	11203	10996	9957	7992
  指標1	802.15	194.94	182.83	174.87	168.50	161.39	157.77	149.62	143.14	142.67	140.18	137.59	124.59	100.00
  指標2	-2.001	0.000	0.136	0.237	0.326	0.436	0.497	0.649	0.789	0.800	0.860	0.927	1.351	(inf)

• test128.bmpでの比較（ベタ画像ファイル）：

  format	無圧縮	yz2	dgca	tek1	tek2	tek0	upx	bzip2	PPMd	LZMA	gzip	stk5	tek5	paq4
  サイズ	8310	1344	1216	1128	993	924	887	877	846	829	746	712	666	422
  指標1	1969.2	318.43	288.15	267.30	235.31	218.96	210.19	207.82	200.47	196.45	176.78	168.72	157.82	100.00
  指標2	-2.147	0.000	0.149	0.267	0.479	0.608	0.685	0.706	0.777	0.818	1.046	1.157	1.329	(inf)

• kaos2c.helでの比較（汎用データ）：

  format	無圧縮	tek1	yz2	tek2	tek0	dgca	upx	bzip2	PPMd	gzip	LZMA	stk5	tek5	paq4
  サイズ	24012	4658	4239	3960	3801	3600	3506	3466	3331	3044	2877	2583	2514	2077
  指標1	1156.1	224.27	204.09	190.66	183.00	173.33	168.80	166.88	160.38	146.56	138.52	124.36	121.04	100.00
  指標2	-2.140	0.000	0.177	0.315	0.404	0.527	0.591	0.620	0.722	0.982	1.171	1.629	1.776	(inf)