PNGのデコーダ実装を目指す (1) ファイルとチャンクの構造

PNGファイルから画像データを読み取って描画するプログラムの実装を目指して、PNGの仕様を学んでいく。

以下にPNGの仕様書があるので、これを参考にする。
[Portable Network Graphics (PNG) Specification (Third Edition)](https://www.w3.org/TR/png-3/)

今回は、PNGファイルとその中のチャンクの構造に注目する。

# PNGデータで用いる整数

[7.1 Integers and byte order](https://www.w3.org/TR/png-3/#7Integers-and-byte-order)

PNGデータにおける整数は、ビッグエンディアン (上位バイトが先、下位バイトが後) で格納する。
指定が無い場合、整数は符号なしである。
符号付き整数は、2の補数表現を用いる。
PNGにおける4バイトの符号なし整数では、$2^{31}-1$ 以下の値のみを扱う。

# PNGファイルの構造

[5.1 PNG datastream](https://www.w3.org/TR/png-3/#5Introduction)

PNGファイルは、先頭にPNGシグネチャを持ち、その後にチャンクが連続して配置される構造になっている。

PNGシグネチャ ([PNG signature](https://www.w3.org/TR/png-3/#3PNGsignature)) は、以下の8バイトである。

```
89 50 4E 47 0D 0A 1A 0A
```

このPNGシグネチャはPNGデータの開始を表すとともに、以下のような転送時のエラーを検出しやすくしている。

* 各バイトのうちトップビットを省いた7ビットしか転送しない
* 改行コードが変換される (CRLF (0D 0A) → LF (0A)、LF → CRLF)
* EOF (1A) を受信した時点で受信が止まる

なお、仕様書では、PNGのデータ一式のことを、以下の場合なども考慮した「ファイル」より一般的な言葉として「データストリーム」(datastream)と呼んでいる。

* データが1個のファイルとしてではなく、ファイルの一部として格納されている場合
* 生成したデータをファイルに保存せず、直接 (on the fly) 利用する場合

# チャンクの構造

[5.3 Chunk layout](https://www.w3.org/TR/png-3/#5Chunk-layout)

それぞれのチャンクは、データサイズ・チャンクの種類・チャンクデータ・CRC32をこの順で並べた構造になっている。

|要素|説明|
|---|---|
|データサイズ|4バイトの整数で「チャンクデータ」のバイト数を表す。<br>データサイズ・チャンクの種類・CRC32のバイト数は含めない。|
|チャンクの種類|ASCIIの英アルファベット4文字 (4バイト) で、チャンクの種類を表す。<br>大文字か小文字かには、それぞれのバイトごとに意味がある。(後述)|
|チャンクデータ|0バイト以上のバイト列である。<br>構造はチャンクの種類ごとに定義される。|
|CRC32|4バイトで、「チャンクの種類」と「チャンクデータ」をこの順で<br>結合したデータのチェックサムである。(計算方法は後述)<br>「データサイズ」は計算に含めない。|

## チャンクの種類の大文字・小文字の意味

[5.4 Chunk naming conventions](https://www.w3.org/TR/png-3/#5Chunk-naming-conventions)

チャンクの種類の各バイトには、ASCII (ISO646) の英アルファベット (大文字または小文字) を用いる。
各バイトにはそれぞれ以下の意味があり、大文字 (ビット5が0) はオフ、小文字 (ビット5が1) はオンを表す。

|位置|意味|
|---|---|
|1 (最初のバイト)|補助的フラグ|
|2|プライベートフラグ|
|3|予約|
|4 (最後のバイト)|コピー安全フラグ|

### 1バイト目：補助的フラグ

このフラグがオフ (大文字) の場合、このチャンクは**必須チャンク** (critical chunks) である。
このタイプのチャンクは画像を正常に表示するために必要である。
このタイプの未知のチャンクがある場合、安全に解釈できない情報が画像に含まれていることをユーザに知らせるべきである。

このフラグがオン (小文字) の場合、このチャンクは**補助チャンク** (ancillary chunks) である。
このタイプのチャンクは、画像を意味がある形で表示するために必ずしも必要ではない。
このタイプの未知のチャンクがある場合、無視して画像を表示しても安全である。

### 2バイト目：プライベートフラグ

[12.10.1 Use of private chunks](https://www.w3.org/TR/png-3/#12Use-of-private-chunks)

このフラグがオフ (大文字) の場合、このチャンクは**パブリックチャンク** (public chunks) である。
このタイプのチャンクは、W3C が定義するために予約されている。

このフラグがオン (小文字) の場合、このチャンクは**プライベートチャンク** (private chunks) である。
このタイプのチャンクは、エンコーダが他のアプリケーションによる解釈が不要な情報を格納するのに使用できる。

### 3バイト目：予約

このフラグは、将来の拡張用に予約されている。
今のバージョンの仕様では、このフラグはオフ (大文字) でなければならない。

### 4バイト目：コピー安全フラグ

[14.2 Behaviour of PNG editors](https://www.w3.org/TR/png-3/#14Ordering)

このフラグがオフ (大文字) の場合、このチャンクは**画像データに依存**している。
**必須チャンクに**何らかの変更 (追加・削除・データの変更・順序の変更など) を加えた場合、このタイプの**未知のチャンク**を出力のPNGデータに**コピーしてはいけない**。
(**既知のチャンク**であれば、画像の変更内容に合わせた新しい内容のチャンクを出力してもよい)
変更を行ったのが**補助チャンクのみ**の場合、このタイプの未知の**補助チャンク**を出力のPNGデータにコピー**してもよい**。
(そのため、別の補助チャンクのデータに依存した補助チャンクを作ってはいけない)
(未知の**必須チャンク**がある場合は処理を中止するべきであり、コピーするかを検討する対象ではない)
このタイプの**未知のチャンク**をコピーする際、**必須チャンクとの位置関係を変えてはいけない**。この範囲内であれば、他の補助チャンクとの位置関係は変えてもよい。

このフラグがオン (小文字) の場合、未知のチャンクであっても、(必須チャンクを含む) 他のデータの変更の有無にかかわらず、このチャンクを出力のPNGデータに**コピーしてもよい**。
このタイプの**未知のチャンク**をコピーする際、`IDAT` チャンクの前にあったチャンクを `IDAT` チャンクの後ろに配置すること、および逆に `IDAT` チャンクの後ろにあったチャンクを `IDAT` チャンクの前に配置することは許されない。それ以外の位置関係の変更はすべて許される。

コピーするのが**既知のチャンク**であれば、位置関係についてはそのチャンク固有のルールにのみ従えばよい。上記の汎用ルールに従ってもよい。

## CRC32の計算方法

[5.5 CRC algorithm](https://www.w3.org/TR/png-3/#5CRC-algorithm)

[V.42 : Error-correcting procedures for DCEs using asynchronous-to-synchronous conversion](https://www.itu.int/rec/T-REC-V.42-200203-I/en)
の 8.1.1.6.2 32-bit frame check sequence で定義された計算方法で、32ビットの値を計算する。

多項式

$$
x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^8+x^7+x^5+x^4+x^2+x+1
$$

を用いて生成する。値のLSBが $x^{31}$ の項に対応する。
初期値は `0xFFFFFFFF` とし、データ中の各バイトをLSBからMSBに向かって処理する。
すべてのバイトの処理後、計算した値のビットNOT (ビット反転) をとる。
計算結果はビッグエンディアン (MSBが最初) で格納する。

計算方法の定義は「データを多項式で割った余りをとる」となっており、(すくなくとも筆者にとっては) わかりにくいが、要は各バイトについて以下の手順を行えばよいようである。

1. 現在の値と処理を行うバイトの値 (をゼロ拡張した値) の xor (排他的論理和) を計算し、新しい「現在の値」とする
2. 1バイトは8ビットなので、以下の操作を8回繰り返す
   1. 「現在の値」を1ビット右論理シフトし、新しい「現在の値」とする
   2. 1の右論理シフトであふれたビットが1であれば、多項式の $x^{32}$ の項を除いた部分を表す値と現在の値の xor を計算し、新しい「現在の値」とする

```python
value = 0xFFFFFFFF
data = b"IEND"

for c in data:
    value ^= c
    for _ in range(8):
        lsb = value & 1
        value >>= 1
        if lsb:
            value ^= 0b1110_1101_1011_1000_1000_0011_0010_0000

value ^= 0xFFFFFFFF

assert value == 0xAE426082
```

テーブルを用いて効率よく計算することもできる。
自分が過去に書いた記事も参考に。
[PNGで使うCRC32を計算する #crc - Qiita](https://qiita.com/mikecat_mixc/items/e5d236e3a3803ef7d3c5)

# 定義済みチャンク

[4.8.2 Chunk types](https://www.w3.org/TR/png-3/#4Concepts.FormatTypes)
[5.6 Chunk ordering](https://www.w3.org/TR/png-3/#5ChunkOrdering)

仕様書には、以下のチャンクが定義されている。

## 必須チャンク

必須チャンクは以下の順番で配置する。

|ラベル|役割|
|:-:|---|
|`IHDR`|画像の幅や高さなどの情報を格納する|
|`PLTE`|画像のパレットを格納する|
|`IDAT`|圧縮された画像データを格納する|
|`IEND`|PNGデータの終端を表す|

### IHDRチャンク

[11.2.1 IHDR Image header](https://www.w3.org/TR/png-3/#11IHDR)
[5.8 Private field values](https://www.w3.org/TR/png-3/#sec-field-value-extensibility)

PNGデータの最初 (PNGシグネチャの直後) に1個だけ配置する。

以下のデータ (整数) をこの順番で格納する。

|データ|バイト数|役割|
|---|:-:|---|
|幅|4|画像の横方向のピクセル数|
|高さ|4|画像の縦方向のピクセル数|
|ビット深度|1|サンプル1個を何ビットで表すか|
|色タイプ|1|色データの形式|
|圧縮方法|1|画像データの圧縮アルゴリズム|
|フィルタ方法|1|画像データの変換形式|
|インターレース方法|1|画像データの順序|

幅および高さは正でなければならない。(0 であってはならない)

色タイプは以下が定義され、それぞれ使用可能なビット深度、および　`PLTE` チャンクの有無が決まっている。

|色タイプ|意味|ビット深度|PLTEチャンク|
|:-:|---|---|:-:|
|0|グレースケール|1, 2, 4, 8, 16|禁止|
|2|フルカラー|8, 16|任意|
|3|インデックスカラー|1, 2, 4, 8|必須|
|4|グレースケール (透明度あり)|8, 16|禁止|
|6|フルカラー (透明度あり)|8, 16|任意|

* グレースケール
  * 各ピクセルを明るさを表す1個のサンプルで表す。
* フルカラー
  * 各ピクセルを赤、緑、青それぞれの明るさをこの順番で表す3個のサンプルで表す。
* インデックスカラー
  * 各ピクセルをパレット上の位置を表す1個のサンプルで表す。
* グレースケール (透明度あり)
  * 各ピクセルを明るさと不透明度をこの順番で表す2個のサンプルで表す。
* フルカラー (透明度あり)
  * 各ピクセルを赤、緑、青、不透明度をこの順番で表す4個のサンプルで表す。

圧縮方法は、以下が定義されている。

|値|意味|
|---|---|
|0|32,768バイトを上限とするスライド窓を用いたdeflate圧縮|
|128以上|プライベート値 (独自形式や実験用)|

フィルタ方法は、以下が定義されている。

|値|意味|
|---|---|
|0|5種類の基本フィルタ形式による適応的フィルタリング|
|128以上|プライベート値 (独自形式や実験用)|

インターレース方法は、以下が定義されている。

|値|意味|
|---|---|
|0|インターレースなし|
|1|Adam7|
|128以上|プライベート値 (独自形式や実験用)|

### PLTEチャンク

[11.2.2 PLTE Palette](https://www.w3.org/TR/png-3/#11PLTE)

存在する場合、`IHDR` チャンクの後、`IDAT` チャンクの前に配置する。
複数配置してはいけない。

パレットの1要素は、赤、緑、青それぞれを1バイトで表した3バイトである。
(画像データのビット深度が16ビットの場合でも、パレットでは1サンプルを8バイトで表す)
パレットは、このような3バイトの組を1～256要素並べたものである。
要素数はデータサイズにより表し、データサイズが3の倍数でない場合はエラーである。
パレットのすべての要素が画像で使われていなくてもよい。すべての要素が異なる必要もない。

色タイプが3 (インデックスカラー) のときは、`PLTE` チャンクは必須である。
最初の要素がサンプルの値0、次の要素がサンプルの値1、…と対応する。
要素の数は、設定されたビット深度で表現できる最大数 (たとえば、4ビットなら$2^4 = 16$個) を超えてはいけない。
要素数が最大より少ないことは許され、このときサンプルの値が存在しない要素に対応する場合はエラーになる。

色タイプが2 (フルカラー) または6 (フルカラー (透明度あり)) の場合、`PLTE` チャンクを置くかは任意である。
存在する場合、画像をそのまま表示できないときに行う量子化で用いる色の集合のヒントを表す。
(この情報は、`PLTE` ではなく `sPLT` チャンクで表すことが推奨されている)

### IDATチャンク

[11.2.3 IDAT Image data](https://www.w3.org/TR/png-3/#11IDAT)
[12.8 Compression](https://www.w3.org/TR/png-3/#12Compression)

圧縮された画像データを格納する。

データは複数の `IDAT` チャンクに分割してもよい。
`IDAT` チャンクが複数ある場合、それらの間に他のチャンクを挟んではいけない。
空 (データが0バイト) の `IDAT` チャンクがあってもよい。

最後の `IDAT` チャンクのデータの最後の部分に、画像データとして使われないバイト列が存在する可能性がある。
デコーダはこのような余計なバイト列を無視するべきである。

### IENDチャンク

[11.2.4 IEND Image trailer](https://www.w3.org/TR/png-3/#11IEND)

最後に1個配置し、PNGデータの終端を表す。データは空である。

## 補助チャンク

以下の補助チャンクが定義されている。
ここでは、それぞれの詳細は省略する。

### 透過情報

`IDAT` チャンクの前に配置する。
`PLTE` チャンクが存在する場合、その後に配置する。
高々1個のみ配置することができる。

|ラベル|役割|
|:-:|---|
|[`tRNS`](https://www.w3.org/TR/png-3/#11tRNS)|透過色またはパレットの不透明度を表す|

### 色空間情報

`IDAT` チャンクの前に配置する。
`PLTE` チャンクが存在する場合、その前に配置する。
それぞれ高々1個ずつのみ配置することができる。
`iCCP` チャンクと `sRGB` チャンクを両方配置してはいけない。

|ラベル|役割|
|:-:|---|
|[`cHRM`](https://www.w3.org/TR/png-3/#11cHRM)|RGB それぞれの 1931 CIE x,y 色度と、白色点を表す|
|[`gAMA`](https://www.w3.org/TR/png-3/#11gAMA)|ガンマ値を表す|
|[`iCCP`](https://www.w3.org/TR/png-3/#11iCCP)|ICC プロファイルを格納する|
|[`sBIT`](https://www.w3.org/TR/png-3/#11sBIT)|画像の各サンプルで実際に使われているビット数を表す|
|[`sRGB`](https://www.w3.org/TR/png-3/#srgb-standard-colour-space)|画像が sRGB 色空間に準拠していることと、レンダリングの目的を表す|
|[`cICP`](https://www.w3.org/TR/png-3/#cICP-chunk)|画像の処理に用いるビデオ形式の情報を表す|
|[`mDCv`](https://www.w3.org/TR/png-3/#mDCv-chunk)|コンテンツ生成時の Mastering Display Color Volume を表す|
|[`cLLi`](https://www.w3.org/TR/png-3/#cLLi-chunk)|HDR (high dynamic range) コンテンツの性質を表す|

### テキスト情報

(他のチャンクの制約を満たす範囲で) どこに配置してもよい。
それぞれ複数配置してもよい。

|ラベル|役割|
|:-:|---|
|[`tEXt`](https://www.w3.org/TR/png-3/#11tEXt)|Latin-1 のテキスト情報を格納する|
|[`zTXt`](https://www.w3.org/TR/png-3/#11zTXt)|圧縮された Latin-1 のテキスト情報を格納する|
|[`iTXt`](https://www.w3.org/TR/png-3/#11iTXt)|UTF-8 のテキスト情報 (圧縮可) を格納する|

### タイムスタンプ情報

(他のチャンクの制約を満たす範囲で) どこに配置してもよい。
高々1個のみ配置することができる。

|ラベル|役割|
|:-:|---|
|[`tIME`](https://www.w3.org/TR/png-3/#11tIME)|画像の最終更新日時 (UTC) を表す|

### アニメーション (APNG) 情報

[4.9 APNG: frame-based animation](https://www.w3.org/TR/png-3/#apng-frame-based-animation)

ここでは配置の制約は省略する。
互換性のため、プライベートチャンクを表す名前で定義されている。

|ラベル|役割|
|:-:|---|
|[`acTL`](https://www.w3.org/TR/png-3/#acTL-chunk)|アニメーションの情報を格納する|
|[`fcTL`](https://www.w3.org/TR/png-3/#fcTL-chunk)|フレームの情報を格納する|
|[`fdAT`](https://www.w3.org/TR/png-3/#fdAT-chunk)|フレームの画像データを格納する|

### その他の情報

`IDAT` チャンクの前に配置する。
`bKGD` は、`PLTE` チャンクが存在する場合、その後に配置する。
`hIST` は、`PLTE` チャンクの後に配置する。(`PLTE` チャンクが存在する場合のみ配置してよい)
`sPLT` 以外は、高々1個のみ配置することができる。(`sPLT` は複数配置してもよい)

|ラベル|役割|
|:-:|---|
|[`bKGD`](https://www.w3.org/TR/png-3/#11bKGD)|画像表示時のデフォルトの背景色を表す|
|[`hIST`](https://www.w3.org/TR/png-3/#11hIST)|パレットの各要素のだいたいの使用頻度を表す|
|[`pHYs`](https://www.w3.org/TR/png-3/#11pHYs)|ピクセルの物理サイズまたはアスペクト比を表す|
|[`sPLT`](https://www.w3.org/TR/png-3/#11sPLT)|推奨パレットを表す|
|[`eXIf`](https://www.w3.org/TR/png-3/#eXIf)|Exif プロファイルを格納する|

# PNGのデコーダ実装を目指すシリーズ

* (1) ファイルとチャンクの構造
* [(2) zlib (deflate) 圧縮データ](https://qiita.com/mikecat_mixc/items/aa0bb543775f01391563)