PNGファイル爆発しろ！

まえがき

Web上で広く利用されるPNG(Portable Network Graphics)フォーマットは、デジタル画像を変化させずに小さいデータサイズへ変換する圧縮技術の一種です。PNGフォーマットはオリジナル画像を完全復元可能な可逆(lossless)圧縮ですから、JPEGフォーマットのように画像を歪めてしまう非可逆(lossy)圧縮ほどは小さくできません。それでもオリジナルのデジタル画像データの半分程度まではサイズ削減可能な画像圧縮アルゴリズムと言われています。^[1]

そげぶ

いいぜ　てめえが何でも思い通りに圧縮出来るってなら
まずはそのふざけた幻想をぶち壊す!!
（スペース都合によりAA省略）

本記事では、PNGフォーマットを画像データ圧縮(compress)用途で利用するのではなく、オリジナル画像データよりも遥かに巨大なPNGファイル を生成します。

PNGフォーマットでは任意のメタ情報を含めることが可能となっており、多量のメタ情報を含めれば巨大PNGファイルを簡単に作れてしまいます。そこで本記事では PNGフォーマット最小構成となる必須チャンクのみ を利用するレギュレーションとし、「1bitの無駄もない無駄に巨大なPNGファイル」生成を目指します。

本記事では必要に応じてPNGファイル構造やDeflate圧縮アルゴリズムの（部分的な）解説も行います。デジタル画像やハフマン符号に関する基礎知識は、拙著「週刊 JPEGデコーダをつくる」を参照ください。

画像データにはサイズ32×32、RGB形式の🐢アイコン画像データを利用します。PNGファイルの生成／加工には下記ツールを利用します：

• ImageMagickツール（基準PNG生成に利用）
• 自作PNG変換ツール（IDAT分割、自前Deflateエンコード）
• 自作PNGデコーダ（生成PNGファイル検査）

Step0 基準PNGファイル

まずはImageMagickツールを使って、基準となる最小構成PNGファイルを生成しておきます^[2]。オプション-quality 96により、IDATチャンク生成時にDeflate最大圧縮率（compression level=9）を指定しています。

$ magick source.png -quality 96 \
  -define png:exclude-chunk="cHRM,bKGD,tEXt,zTXt,tIME" \
  PNG24:0-original.png
$ ls -l
-rw-r--r--  1 yoh staff     2472  4  1 00:00 0-original.png

オリジナル画像（32×32 pixels, 24bit-RGB）のデータサイズは 32×32×3=3072 bytes ですから、PNGファイル0-original.pngのサイズ 2472 bytes はオリジナルに比べて約80％程度と期待通りにデータ圧縮が行われています。

ここで生成した最小構成PNGファイルは、PNGシグニチャと3種類のチャンクから構成されます。

• PNGシグニチャ：PNGフォーマットであることを示す固定長バイト列。
• IHDRチャンク：画像サイズやカラーフォーマットなどの属性情報。
• IDATチャンク：画像データ本体。ZLIB/Deflate圧縮バイト列。
• IENDチャンク：PNGフォーマット終端を示すマーカ。

PNGフォーマットではPNGシグニチャ（8 bytes）、IHDRチャンク（26 bytes）、IENDチャンク（12 bytes）のサイズは固定長とされるため、本記事ではIDATチャンクサイズを肥大化させる方針をとります。

Step1 Deflate非圧縮

手始めにIDATチャンクのペイロードを Deflate非圧縮（compression level=0） で再圧縮してみましょう。このときDeflateストリームは "非圧縮モードを表すヘッダ"＋"非圧縮データ長さ情報"＋"非圧縮データ列" から構成されます。

$ ./pngutil.py 0-original.png --recompress=0 1-nocomp.png
$ ls -l
-rw-r--r--  1 yoh staff     2472  4  1 00:00 0-original.png
-rw-r--r--  1 yoh staff     3172  4  1 00:00 1-nocomp.png

オリジナル画像サイズ 3072 bytes に対してPNGファイル1-nocomp.pngサイズ 3172 bytes と、オリジナルよりも僅かに大きいPNGファイルを生成できました。

これ以降はデータ圧縮率ならぬ「膨張率＝生成PNGファイルサイズ／オリジナル画像サイズ」を用いて評価します。Deflate非圧縮では 膨張率＝1.03 です。

Step1のDelfate非圧縮までは専用プログラムを必要とせず、ImageMagickツールのみで同等PNGファイルを生成できます。

$ magick 0-original.png -define png:compression-level=0 \
  -define png:exclude-chunk="cHRM,bKGD,tEXt,zTXt,tIME" 1-nocomp.png

Step2 IDATチャンク分割

じつはPNGフォーマットは複数個のIDATチャンクから構成されてもよく、PNGデコーダは全IDATチャンクのペイロードを結合してからZLIB/Deflateデコードを行う仕様になっています。

一般的なPNGエンコーダは単一IDATチャンク構成または数Kbyte単位のIDATチャンク分割することがありますが、ここでは最小単位つまり Deflateストリームを1byte毎にIDATチャンク分割 してデータサイズを増大させます。下図のようにペイロードデータ 1byte につき1個のIDATチャンクを構成するため、IDATチャンク分割により 13倍 のサイズ膨張効果が得られます。

$ ./pngutil.py 0-original.png --recompress=0 --split-idat=1 2-nocomp-split.png
$ ls -l
-rw-r--r--  1 yoh staff     2472  4  1 00:00 0-original.png
-rw-r--r--  1 yoh staff     3172  4  1 00:00 1-nocomp.png
-rw-r--r--  1 yoh staff    40540  4  1 00:00 2-nocomp-split.png

Deflate非圧縮とIDATチャンク分割の併用によりサイズ 40540 bytes、ついにファイルサイズが1桁繰り上がりました。これは 膨張率＝13.2 に相当します。

Step3-4 Deflate非圧縮ブロック分割

Deflateアルゴリズムは内部的に "ブロック" 単位でエンコード／デコードする仕様となっており、ZLIB/Deflateバイト列を複数Deflateブロックから構成できます。一般的なエンコーダでは単一ブロックないし数ブロック分割しか行いませんが、ここでは最大限データ量を増やすため 圧縮前データ1byte毎に1個のDeflate非圧縮ブロック(non-compressed block)へと分割 します。

たとえば3byteの文字PNG（16進表記 50 4e 47）をDeflate非圧縮ブロック分割エンコードすると、下図24bytesのZLIB/Deflateバイト列へと変換されます。ZLIBヘッダ（先頭2bytes）とADLER-32チェックサム（末尾4bytes）を除いた部分がDeflateビットストリームとなり、エンコード前データ1bytesにつき1つのDeflate非圧縮ブロックを構成します。

Deflate非圧縮ブロック分割はIDATチャンクペイロードを対象したものであり、IDATチャンク分割と併用できます。

$ ./pngutil.py 0-original.png --bloat                3-bloat.png
$ ./pngutil.py 0-original.png --bloat --split-idat=1 4-bloat-split.png
$ ls -l
-rw-r--r--  1 yoh staff     2472  4  1 00:00 0-original.png
-rw-r--r--  1 yoh staff     3172  4  1 00:00 1-nocomp.png
-rw-r--r--  1 yoh staff    40540  4  1 00:00 2-nocomp-split.png
-rw-r--r--  1 yoh staff    18687  4  1 00:00 3-bloat.png
-rw-r--r--  1 yoh staff   242235  4  1 00:00 4-bloat-split.png

Deflate非圧縮ブロック分割のみ適用した3-bloat.pngは 18687 bytesにすぎませんが、IDATチャンク分割を組み合わせた4-bloat-split.pngは 242235 bytesとなります。ファイルサイズの桁数がさらに繰り上がり、膨張率＝78.8 となりました。

一度冷静になってオリジナル画像サイズ（32×32 pixels, 24bit-RGB）を思い起こしてください。ここに来てファイルサイズ 242 Kbytes のPNGファイルを手に入れました。

Step5-6 Deflate動的ハフマン符号ブロック分割

ZLIB/Deflateアルゴリズムのデファクト実装として知られるzlibライブラリでは、入力バイト列に対して最小サイズのDeflateビットストリームを生成するために、最良のハフマン符号表を構築する動的ハフマン符号ブロック(dynamic Huffman codes block)を生成します。

さて、本記事の目的を覚えていますか？もし入力バイト列に対して 最悪なハフマン符号表 を構築すれば、最大サイズのDeflateビットストリームを生成できるはずです。先Stepと同様に 圧縮前データ1byte毎に1個のDeflate動的ハフマン符号ブロック分割 しましょう。

実際に3bytesの文字PNGをDeflate動的ハフマン符号ブロック分割エンコードすると、下図にある875bytesのZLIB/Deflateバイト列へと変換されます。もはや意味不明に聞こえるかもしれませんが、この方式を用いると元データ 1byte = 8bits に対して 2316 bits までサイズが膨張しています。^[3]

全てのビットにはそれぞれ意味があり、1ビットでも壊れるとたった3bytesの元データは復元不可能となります。内訳を知りたい奇特な方のために書いておくと、ブロックヘッダ＝3bits、ハフマン符号表＝2283bits、ペイロード＝15bits×2シンボル から構成されています。完全理解を望む方は続編記事「PNGファイル爆発しろ！ 〜詳細解説編〜」を参照ください。

Deflate動的ハフマン符号ブロック分割もまたIDATチャンクペイロードを対象としたものですから、もちろんIDATチャンク分割と併用可能です。(;・`д・́)...

$ ./pngutil.py 0-original.png --explode                5-explode.png
$ ./pngutil.py 0-original.png --explode --split-idat=1 6-explode-split.png
$ ls -l
-rw-r--r--  1 yoh staff     2472  4  1 00:00 0-original.png
-rw-r--r--  1 yoh staff     3172  4  1 00:00 1-nocomp.png
-rw-r--r--  1 yoh staff    40540  4  1 00:00 2-nocomp-split.png
-rw-r--r--  1 yoh staff    18687  4  1 00:00 3-bloat.png
-rw-r--r--  1 yoh staff   242235  4  1 00:00 4-bloat-split.png
-rw-r--r--  1 yoh staff   898671  4  1 00:00 5-explode.png
-rw-r--r--  1 yoh staff 11682027  4  1 00:00 6-explode-split.png

Deflate動的ハフマン符号ブロック分割のみ適用5-explode.png時点で 898671 bytes、IDATチャンク分割を組み合わせた最終PNGファイル6-explode-split.pngは 11682027 bytes。ファイルサイズは一気に2桁も繰り上がり、とうとう膨張率＝3802 に到達しました。

この巨大なファイルはPNGフォーマットに完全準拠しており、あらゆる画像ビューアで表示可能なPNGファイルとなっています。

おわりに

本記事では 32×32 pixelsのアイコン画像に対して 11 Mbytesを越えるPNGファイルを手に入れました。当然ながら各種PNGファイルはファイルサイズ 2472 bytesの最小構成PNGファイルと全く同じアイコン画像として表示されます。ディスク容量や通信帯域を無駄遣いする以外になんの意味もありません。

最後になりましたが、より大きな画像データに対してDeflate動的ハフマン符号ブロック分割（2316/8＝289.5倍）とIDATチャンク分割（13倍）を適用した場合のPNGファイルサイズを机上シミュレーションしておきます。

• VGA(640×480)：約 3.2 Gbytes
• SVGA(800×600)：約 5.0 Gbytes
• FHD(1920×1080)：約 21.8 Gbytes
• ...これ以上はやめておきましょうか

脚注

1. PNGフォーマットに限らず、可逆圧縮アルゴリズムによるデータ削減率は入力データに依存するため、圧縮後データサイズの事前予測は原理的に不可能です。一般論としてはフルカラー写真など複雑な画像に対してはサイズ削減効果が小さく、べた塗りイラストなど単調な画像に対しては大幅なサイズ削減効果が得られます。

2. ImageMagicツールのデフォルト動作では、タイムスタンプ情報などのメタ情報が出力PNGファイルへと書き込まれます。本記事のレギュレーション遵守のためには、-define png:exclude-chunk=...により補助チャンク(Ancillary chunks)出力を抑止する必要があります。

3. Deflateビットストリームは文字通りビット列から構成されるため、バイト単位での図示ではブロック境界を正確に表現できません。例えばdynamic Huffman codes block#0と#1の境界はcf位置にありますが、厳密には下位4bit(f)はblock#0に上位4bit(c)はblock#1に属します。いささか直感に反する順序となるのは、Deflate仕様におけるビット単位I/Oが1byte内では右端ビット→左端ビットの順に行われるためです。