Zenn
⚗️

PNGファイル爆発しろ！ 〜詳細解説編〜

2023/05/01に公開
png
アルゴリズム
画像処理
tech

https://twitter.com/yohhoy/status/1643639248413921280?conversation=none

Deflateアルゴリズム 超簡易紹介

PNGフォーマットではZLIB/Deflateアルゴリズムを用いて画像データを可逆圧縮します。Deflateアルゴリズムの技術仕様は RFC 1951: DEFLATE Compressed Data Format Specification version 1.3 にて規定されており、本編記事では同仕様に準拠しつつ最長サイズとなるDeflateビットストリームを生成しました。

ここでは本編で用いた「Deflate動的ハフマン符号ブロック分割」の理解に必要となる最低限の部分解説を行います。ハフマン符号に関する基礎知識は、拙著「週刊 JPEGデコーダをつくる」を参照ください。

Deflateブロック構造

DeflateアルゴリズムはLZ77アルゴリズムとハフマン符号とを組み合わせた、汎用のデータ可逆圧縮アルゴリズムです。Deflateビットストリームは複数ブロックから構成され、3種類のブロック種別からデータ圧縮方式を選択できます。

  • 非圧縮ブロック(non-compressed block)：データをそのまま格納する
  • 固定ハフマン符号ブロック(fixed Huffman codes block)：Deflate仕様で定義される固定的なハフマン符号表を用いて圧縮する
  • 動的ハフマン符号ブロック(dynamic Huffman codes block)：ハフマン符号表を格納しておき同表を用いてデータ圧縮する

各ブロックのヘッダ部は、1bitの最終ブロックフラグ(BFINAL)と2bitsのブロック種別(BTYPE)の計3bitsから構成されます。最終ブロックフラグは、文字通りDeflateビットストリームにおける最終ブロックであることを示します。

通常のPNGファイルはデータサイズ最小化を主目的としますから、高効率かつオーバーヘッド最小となる単一動的ハフマン符号ブロック構成が一般的でしょう（BFINAL=1, BTYPE=10/動的ハフマン符号ブロック）。

ハフマン符号表表現

ハフマン符号表の本質は、変換前データのシンボル(symbol)と変換後の符号(code)との対応表です。例えば変換前データが5種類のアルファベットA〜Eから構成されうる場合、下記のようなシンボル－符号対応表が考えられます。この対応表ではアルファベットDには符号を割り当てない、つまり変換前データにDが含まれないことを意味します。

シンボル 符号 符号長
A 110 3
B 0 1
C 111 3
D (N/A) 0
E 10 2

Deflateビットストリームにおけるハフマン符号表表現では「シンボル順に割り当てる符号長リスト」のみを格納します。Deflateデコーダは符号長リストから一定のアルゴリズムに基づいてハフマン符号表を復号します。

この対応表ではシンボルリスト[A, B, C, D, E]に対して符号長リスト[3, 1, 3, 0, 2]となり、1符号長あたり2bitsを割り当てたビット列11 01 11 00 10(10 bits)がハフマン符号表表現となります。さらに変換対象のシンボル数が可変個となる場合、シンボル数の情報もDeflateビットストリーム中に含める必要があります。

動的ハフマン符号ブロック

Delflateビットストリームの動的ハフマン符号ブロックは、3種類のハフマン符号表(HCLEN, HLIT, HDIST)のシンボル数と符号長リスト、およびハフマン符号表を用いて符号化されたビット列から構成されます。＠は1符号長あたりの割り当てbit幅を表します。

  • HCLEN：符号長ハフマン符号表（シンボル数＝4〜19, 符号長＝0〜7＠3bits）
  • HLIT：リテラル／長さハフマン符号表（シンボル数＝257〜286, 符号長＝0〜15＠0〜7bits）
  • HDIST：距離ハフマン符号表（シンボル数＝1〜30, 符号長＝0〜15＠0〜7bits）

Deflateアルゴリズム理解においてはここが最難解かもしれません。リテラル／長さハフマン符号表(HLIT)と距離ハフマン符号表(HDIST)を表現する符号長リストもまた、符号長ハフマン符号表(HCLEN)を用いて圧縮表現されています。例えばHCLENのシンボル9と符号1011が対応するとき、HLIT符号長リスト中に登場するビット列1011は"符号長9"とデコードされます。...ついてこれてますか？

距離ハフマン符号表(HDIST)は最大30シンボル、リテラル／長さハフマン符号表(HLIT)では最大286シンボルにも上るため、データサイズを最小化すべくこのような二段階のデータ圧縮が行われるのです。なお、符号長ハフマン符号表(HCLEN)の符号長リストは素直なビット列で表現されます。

ナイーブ戦略による最悪ハフマン符号表

ここまでの知識を活用（悪用？）して、動的ハフマン符号ブロックの仕様限界までDeflateビットストリームを肥大化させましょう。単純に あらゆる数値を上限に振り切って しまえば最悪なハフマン符号表を構築できそうです。Bigger is better.

  • ブロックヘッダ：3bits固定
  • ハフマン符号表シンボル数x3種：5+5+4bits固定
  • 符号長ハフマン符号表(HCLEN)：最大シンボル数19×最大符号長7(3bits)
  • リテラル／長さハフマン符号表(HLIT)：最大シンボル数286×最大符号長15(7bits)
  • 距離ハフマン符号表(HDIST)：最大シンボル数30×最大符号長15(7bits)
  • ペイロード："圧縮前1byteのシンボル(15bits)"と"ブロック終端シンボル(15bits)"

内訳を知りたい奇特な方のために書いておくと、ブロックヘッダ＝3bits、ハフマン符号表＝2283bits、ペイロード＝15bits×2シンボル から構成されています。

本編で言及したハフマン符号表サイズ2283bitsをさらに詳細化すると、(5+5+4)+(19×3)+(286×7)+(30×7)bitsとなります。3種類のハフマン符号表表現、ペイロード部2シンボルのビット列は次の通りです。

  • HCLEN符号長リスト：111 111 ... 111 (19×3＝57bits)
  • HLIT符号長リスト：1111111 1111111 ... 1111111 (286×7＝2002bits)
  • HDIST符号長リスト：1111111 1111111 ... 1111111 (30×7＝210bits)
  • 圧縮前1byteのシンボル：0000000xxxxxxxx (15bits, シンボル=0〜255のいずれか)
  • ブロック終端シンボル：000000100000000 (15bits, シンボル＝256)

ね、簡単でしょう？（フラグ）

zlibライブラリと不完全ハフマン符号表

ナイーブ戦略を用いて生成したPNGファイルは、Deflateデコード処理をフルスクラッチ実装した自作PNGデコーダではデコード可能です。しかしデファクト実装zlibライブラリを利用するImageMagickやOS標準サムネイル表示機能では、不正なDeflateビットストリームと見なされてデコードに失敗してしまいます。

$ magick convert naive.png naive.ppm
convert: IDAT: invalid code lengths set `naive.png'.
convert: no images defined `naive.ppm'.

zlibライブラリの内部実装を調べたところ、ハフマン符号表の復号時に独自の妥当性チェックを行っており、上記メッセージは符号長ハフマン符号表(HCLEN)が不完全なケースで表示されるエラーでした。

HCLEN符号長リスト：111 111 ... 111 (19×3＝57bits)

ナイーブ戦略によるHCLEN符号長リスト＝[7, 7, ..., 7]から19シンボルのハフマン符号表を復号すると、符号リストは[0000000, 0000001, ..., 0010010]となります。zlibライブラリは7bits空間の次符号0010011から1111111が未使用である不完全ハフマン符号表と解釈し、このデータを不正なDeflateビットストリームと判断します。余計なことしやがって[1]

zlibライブラリによる妥当性チェックも理解はできます。データ圧縮を目的とするDeflateアルゴリズムのハフマン符号表において、符号割り当てに明らかな無駄がある異常データを事前検査したいのでしょう。単純に最大値を割り当ててゆくナイーブ戦略では、市中PNGデコーダから拒絶されてしまうと分かりました。[2]

Deflate動的ハフマン符号ブロック分割の要件

PNGファイルを名乗る以上、zlibライブラリを利用する市中PNGデコーダでデコード可能でなければお話になりません。改めてDeflate動的ハフマン符号ブロック分割に求められる要件を整理しましょう。

  • 圧縮前1byte毎に1個の動的ハフマン符号ブロックを構成する
  • 符号長ハフマン符号表(HCLEN)：最大シンボル数19×符号長0〜7(3bits)から完全ハフマン符号表を構築する
    • 後続HLIT, HDISTの符号長リストではHCLENにおいて"最大符号長7bits"で表現される符号長のみを利用する
  • リテラル／長さハフマン符号表(HLIT)：最大シンボル数286×符号長0〜15(7bits)から完全ハフマン符号表を構築する
    • 2種のシンボル（圧縮前1byte, ブロック終端）には"最大符号長15bits"を割り当てる
  • 距離ハフマン符号表(HDIST)：最大シンボル数30×符号長0〜15(7bits)から完全ハフマン符号表を構築する
    • （LZ77アルゴリズム未使用のため追加制約なし）

これらの要件をざっくりまとめると 3種の完全ハフマン符号表を構築しつつ、符号長リストとシンボル2種のbit幅を最大化する 必要があります。

完全最悪ハフマン符号表

そして、完成したものがこちらとなります（Pythonコード）。人の手による繊細で温かみのあるハフマン符号表となっております。[3]

b = (圧縮前1byte)
# 符号長ハフマン符号表(シンボル数19)
HCLEN = [7] * 16 + [1, 2, 3]
# リテラル／長さハフマン符号表(シンボル数286)
HLIT = [8] * 256 + [15] + [9, 10, 11, 12, 13, 14] + [0] * 23
HLIT[b] = 15
# 距離ハフマン符号表(シンボル数30)
HDIST = [0] * 30

この完全最悪ハフマン符号表は、次の設計方針に従って作られました。

  • 圧縮前1byteに合わせたリテラル／長さハフマン符号表(HLIT)を構築する
  • 符号長ハフマン符号表(HCLEN)：後続HLIT,HDIST設計制約を緩めるためシンボル0〜15に最大符号長7bitを割り当て、残りシンボルは完全性を満たすための調整用
  • リテラル／長さハフマン符号表(HLIT)：シンボル2種（圧縮前1byteb, ブロック終端256）のみ最大符号長15bitを割り当て、残りシンボルは完全性を満たすための調整用
  • 距離ハフマン符号表(HDIST)：全て符号長0とし空のハフマン符号表を構築

また完全最悪ハフマン符号表による符号ビット列は次のようになります。

  • HCLEN符号長リスト：111 ... 111 001 010 011 (19×3＝57bits)
    • 符号長0〜15の符号：[1110000, ..., 1111111]＠7bits
  • HLIT符号長リスト：符号長0～15＠7bitsからなるリスト (286×7＝2002bits)
  • HDIST符号長リスト：1110000 1110000 ... 1110000 (30×7＝210bits)
  • 圧縮前1byteのシンボル：111111111111110 (15bits)
  • ブロック終端シンボル：111111111111111 (15bits)

これでナイーブ戦略同様に 仕様限界までDeflateビットストリームを肥大化させつつ、市中PNGデコーダによってデコード可能な PNGファイルを生成できました。

多分これが一番大きいと思います

脚注

  1. 筆者の理解の範囲内では、zlibライブラリによるハフマン符号表の妥当性チェックは、Deflateアルゴリズムを記述するRFC1951に記載のない追加的な検査機構と解釈しています。万一、見落としがあるようでしたら教えてください。 ↩︎

  2. ハフマン符号表の妥当性チェックは、2003年リリース zlib v1.2.0 から導入されたようです。https://github.com/madler/zlib/commit/7c2a874e50b871d04fbd19501f7b42cff55e5abc ↩︎

  3. 実際には最初からこの完全最悪ハフマン符号表に辿りついた訳ではなく、試行錯誤を経た結果得られたものです。https://github.com/yohhoy/pngutil/commits/main/pngutil.py ↩︎

Discussion