https://github.com/yohhoy/picopdec

実装方針

• RGB24形式のみサポート（RGBA32形式に追加対応）
• PPM形式出力のみ（macOSなら直接表示可／Windowsは別途ビューアが必要）
• Interlaced PNG imageは無視
• Deflate/dynamic Huffman codesのみサポート（fixed Huffman+no-compressedに追加対応）

実装順序

• PNGフォーマットのチャンク構造解析
  • ファイルシグニチャ(8byte)検査
  • IHDR, IDAT, IENDチャンクのみ解釈
  • PLTEやその他チャンクは読み飛ばす
  • CRC(4byte)は読捨て可
• ZLIBストリーム構造解析
  • 先頭ヘッダ(2-6bytes)は読捨て可
  • 末尾ADLER32チェックサム(4byte)読み取り
• Deflateストリームデコード
  • ビット単位読み取り処理を実装
  • BFINAL/BTYPE, HLIT/HDIST/HCLEN解釈
  • ハフマン符号長→ハフマン符号表構築を実装
  • HCLENから「符号長ハフマン符号表」を構築
    • 固定テーブルを用いたHCLEN順序並び替え
  • 「符号長ハフマン符号表」を用いてHLIT, HDISTを読み取り
    • 固定テーブルを用いたランレングス処理
  • HLITから「リテラル／長さハフマン符号表」を構築
  • HDISTから「距離ハフマン符号表」を構築
  • 「リテラル／長さハフマン符号表」を用いてシンボルを読み取り
    • リテラルと終端マーカの処理
    • 固定テーブルを用いて「長さ情報」を読み取り
    • 固定テーブルと「距離ハフマン符号表」を用いて「距離情報」を読み取り
    • 「長さ情報」＋「距離情報」を用いてスライドコピー処理
• PNGフィルタ画像復元
  • 左ピクセル／上ラインピクセル参照時の境界処理
  • Peath予測フィルタを実装
  • ラップアラウンド処理(% 256/& 0xff)
• PPMファイル出力

デバッグのヒント

• IDATチャンク：Deflateブロック境界とは無相関
• CRC：IENDチャンクCRC == 0xae426082
• ビット読取：00001000 00000010から10bit読取ると値520（RFC1951例示）
  • ビット読取順は非直感的（バイト単位BigEndian かつ ビット単位LSB→MSB）
• ハフマン符号表構築：RFC1951に2件のサンプル例示あり
• 各種ハフマン符号表：重複しない瞬時復号可能な符号集合
  • 瞬時復号可能 == ある符号は他符号の接頭辞ではない
  • ハフマン符号表の壊れ方をみながらKIAIデバッグ
• Deflateデコード：出力バイト数=(画像幅×3 + 1)×画像高さ（RGB24の場合）
  • ハフマン符号：1ビットづつ読取り（結果的にビット逆順となる）
  • それ以外：nビットのパターン読取り（ビット正順）
  • ビット読取り長さに要注意（固定長テーブルのミス）
  • スライドコピー処理はDeflateブロック境界を越えてよい
  • デコード結果のADLER32チェックサム検証
• テストPNGファイルを準備
  • ImageMagickでPNGエンコードパラメータを微調整可能
  • 画像の壊れ方をみながらKIAIデバッグ
  • たまには前段（Deflateデコード）も疑う

おまけ

• Python言語による実装で 300 SLOC 程度の規模（print文除外）。
• 外部Zlib/Deflateデコーダライブラリを利用するなら難易度は1/5～1/10になりそう（体感）
  • ソースコードの約 6 割がZlib/Deflateデコード関連
  • 市中PNGファイルにDeflate fixed Huffman code blockやno-compressed blockは滅多に登場しない気がする。
• 画像サイズは100x100前後がおススメ。大きい画像はデバッグ辛いだけ。