PNG イメージを自力でパースしてみる～4/6 非圧縮とzlib編～

ここまでのあらすじ

PNG イメージを自力でパースしてみる～1/6 予備知識編～
PNG イメージを自力でパースしてみる～2/6 Deflateの基本と固定ハフマン編～
PNG イメージを自力でパースしてみる～3/6 カスタムハフマン編～

前回、前々回でDeflateの「固定ハフマン」と「カスタムハフマン」について触れた。ここでは残るブロックタイプの「非圧縮」と、Deflateを利用した圧縮フォーマットの「zlib」についてを紹介。

予備知識
- バイトオーダー
  - リトルエンディアン
  - ビッグエンディアン
非圧縮 (BTYPE:00)
zlib
サンプル
参考にしたサイトさん

予備知識

これからの説明を読む前に予備知識が必要かも

バイトオーダー

あたりまえとは存ずるものの...
１バイト (8ビット) 単体では、256種類までの数値を表現できる。それより広い範囲の数値を扱いたい場合には、一般的に連続した複数のバイト並びを利用することで、それを実現する

ここで、表現したい値をその連続したバイト並びに対して、
どのような順で収めるのかを、ルールとして定めたものを
バイトオーダー または エンディアン と呼ぶ。

うち、実際によく利用されるのは以下の２つ

リトルエンディアン

0x1234ABCD (305,441,741)
0x12	0x34	0xAB	0xCD
↓	↓	↓	↓
0xCD	0xAB	0x34	0x12

この並びの規則に従う場合、数値の下位バイトほど、先頭に出現するよう収められる。

Deflate 圧縮データ中に含まれる多バイト長データは、このリトルエンディアンの並びの規則に従って出現する。

ビッグエンディアン

0x1234ABCD (305,441,741)
0x12	0x34	0xAB	0xCD
↓	↓	↓	↓
0x12	0x34	0xAB	0xCD

ネットワークバイトオーダーとも呼ばれる。
この並びの規則に従う場合、数値の上位バイトほど、先頭に出現するよう収められる。

後に解説する zlibデータ中に含まれる多バイト長のデータは、このビッグエンディアンの並びの規則に従って出現する。

非圧縮 (BTYPE:00)

Deflate で定義されている圧縮タイプのうちの一つ。

このブロックに含まれるデータは圧縮されない。圧縮がむしろ逆効果になってしまうような小さなデータに対しては、このタイプを使う。

非圧縮ブロック中には、以下の要素が順番に整列している。

ヘッダー情報 (前々回の記事で紹介済み)
パディング
LEN：非圧縮データのバイト数 (2バイト)
NLEN：LENの補数 (2バイト)
非圧縮データ (～65,535バイト?)

f:id:DarkCrowCorvus:20170108132252j:plain

2. パディング

メモリ上に展開されたとき、LENより以降のデータは、必ずバイト境界から始まるようになっている。パディングは、ヘッダー情報 (BFINAL、BTYPE) を読み出してから、それより後に現れる直近のバイト境界位置までの間に詰められる。

このデータにそれ以上の役割はないので、読み飛ばすか、読んでそのまま捨ててしまって構わない。

3. LEN：非圧縮データのバイト数

このブロックに含まれている非圧縮データの、バイト数を表す値がこの中に収められる。最大で 65,535 (0xffff) まで設定可能。

このデータはリトルエンディアンの並びで記録されている

4. NLEN：LENの補数

ここには LENの全ビットの0,1を反転した"補数"の値が設定される。

データが壊れていないかをチェックするためのものなんだろうか...?

NLENの全ビットの0,1を反転させたものが LENと一致するか、
LEN + NLEN = 0xffff になるか、

一応、このどちらかで、バイト長の値に誤りがないかをチェックできる。

このデータもリトルエンディアンの並びで記録されている

5. 非圧縮データ

ここに非圧縮状態のデータがそのまま収められる。データサイズはLENに設定されている通り。

zlib

あぁ、なんかうまくいかないと思った... pngのIDATの中身って、Deflate圧縮のデータがそんまま入ってるわけじゃないのか、zlibのヘッダとフッタを取り除かなければならぬ、
— ﾛｳﾞｽﾀﾝｸﾞ=ﾊﾟｼﾌｨｹｲﾅｽ (@DarkCrowCorvus) 2016年7月9日

PNGの圧縮データ部には、Deflateではなく、zlib というのを使っているそうだった。ここにきてようやく気付く。

実際にはそのzlibの中で、Deflateが扱われているので、「PNGはDeflate圧縮を使っている」といっても、あながち間違いではないとは思うのだけど...

構成

zlib 中には以下の要素が順番に整列している

CMF (Compression Method and flags)
1.1. CM：圧縮方式 (4ビット)
1.2. CINFO ：圧縮情報 (4ビット)
FLG (FLaGs)
2.1. FCHECK：CMF/FLGチェックビット (5ビット)
2.2. FDICT：プリセット辞書の利用有無 (1ビット)
2.3. FLEVEL：このデータの圧縮レベル (2ビット)
DICTID：プリセット辞書識別ID (存在しない場合あり 4バイト)
圧縮データ
Adler-32 (4バイト)

f:id:DarkCrowCorvus:20170109143630j:plain

なお、データ中の各々の要素はDeflateと同様、
アドレスの小さい順のビット番号の小さい順に並ぶ。

また、前述していたとおり、圧縮データ部を除く、zlib中の多バイトで表現される数値はすべてビッグエンディアンの並びで記録されているということに注意すること。

1.1. CM：圧縮方式
CM：Compression method

ここには、zlibがどの圧縮方式を利用しているかの情報が 4ビット長で収められる。
CM = 8 だった場合、それがDeflate圧縮を利用したzlibであるということを示す。

なお、CM = 8 以外の値は、現状扱われていない。とりあえず今は「8を読み出せれば正しい」とだけ覚えておけば問題ないはず..

1.2. CINFO：圧縮情報
CINFO：Compression info

CM = 8 のとき、ここには Deflate 圧縮で使用したスライド窓のサイズを表す値が設定される。

実際にはスライド窓のサイズを $n$ としたとき、
$log_2(n)-8$ によって求まる値を、この 4ビット長の中に収める。

なお、ここに設定できる値は 0～7 の値のうちいずれかで、利用できるスライド窓のサイズは最小で256バイト、最大で32,768バイトというのが決められている。

ちなみに、符号化時にどのサイズのスライド窓を利用したとしても、復号時には最大サイズ (32,768) のスライド窓が用意できれば困ることはない。細かな実装が面倒なら CINFO ≤ 7 であるかだけをチェックすれば、後は考慮しなくてもかまわない。

2.1. FCHECK：CMF/FLGチェックビット
FCHECK：Flag check bits?

1. CMF と 2. FRG を連結した計16ビット長からなるデータの表す値が、31の倍数になるよう、調節するために設定される。復号するとき、この結果が31の倍数にならない場合は、データが壊れていることを示唆する。

2.2. FDICT：プリセット辞書の利用有無
FDICT：Flag dictionaly?

このビットに「1」が設定されている場合は、プリセット辞書 (後述) を利用して解凍を行うべきであることを示す。またこれが「1」に設定されている場合は、後に 3. DICTID が出現する。

2.3. FLEVEL：このデータの圧縮レベル
FLEVEL：Flag level?

データの圧縮がどの程度の精度で行われたかを表す値が、2ビット長で収められる。
CM = 8 の場合、以下のいずれかの値が設定される。

０ - 最速のアルゴリズムを使った
１ - 速めのアルゴリズムを使った
２ - デフォルトのアルゴリズムを使った
３ - 最遅だが、最大限に圧縮するアルゴリズムを使った

基本的に圧縮アルゴリズムは、圧縮が完了するまでの速さを重視すると圧縮率が落ち、逆に圧縮率を重視すると、圧縮が完了するまでに時間がかかる。

ここに設定される値は例えば、あるzlibのデータの圧縮率を上げるために、そのデータへの再圧縮を試みたいとき、それの結果、圧縮率が上がるかどうかを評価するための指標となる。

ちなみにデータを解凍する上でこのデータは役に立たないため、読み飛ばしてしまっても構わない。

3. DICTID：プリセット辞書識別ID
DICTID：Dictionaly identifier

前述の FDICT に「1」が設定されている場合に限り、4バイトの長さで出現する。

ここには、プリセット辞書 (後述) に対してAdler-32 (後述) を施した結果、得られた値が設定される。解凍するプログラムはこれを見て、圧縮に使われたプリセット辞書を、自身が持っているかをチェックする。

4. 圧縮データ

CM = 8 であるとき、ここには Deflate 圧縮されたデータが収められる。解凍方法は、これまでの記事で紹介してきた通りだ。

プリセット辞書

LZ77 はその仕様により、圧縮のはじめはスライド窓の中身が空の状態である。そのため通常は、圧縮元のデータが小さかったり、または大きくても、はじめのほうに出現する羅列の圧縮には、あまり期待ができない。

しかし、特定のアプリケーションにおいて、どのような羅列が出現しやすいか事前にわかっていたならば、あらかじめその羅列をスライド窓にセットしておけば、それらのデータを圧縮できる機会が生まれ、結果的に全体的なデータサイズを減らすことができそうだ。

この通り、圧縮前に事前にスライド窓へ渡されるこの羅列のことを プリセット辞書 (Preset dictionary) と呼ぶ。

f:id:DarkCrowCorvus:20170108215754j:plain

zlibの圧縮プログラムと解凍プログラムはそれぞれ、自身のアプリケーションに合った任意の数のプリセット辞書を保有する。

圧縮時にプリセット辞書を使ったならば、FDICTに「１」を設定し、DICTIDに使ったプリセット辞書を識別するためのIDを設定する。通常ここには、プリセット辞書に対して、後述のAdler-32を施した結果の値を使用する。

解凍時には、FDICTを見て「１」であるならば、後に現れるDICTIDから、使われたプリセット辞書を特定し、そのプリセット辞書を使って解凍を行う。

Adler-32

任意のデータ列を「数値の並び」であるとみなしてこれの和を求め、結果をデータ列の末尾などに付与する。そのデータを受け取った側では同じ通り、データ列から和を求め、付与されていた和の値と一致するかをチェックする

これによって受け取るまでの途中でデータが壊れたりしていないかを、簡易的にチェックすることができる。

この考え方をベースとしたアルゴリズム、またはそれにより求まるチェック用の値のことを チェックサム (check sum) と呼ぶ。Adler-32 はそのチェックサムアルゴリズムの一種。 Mark Adlerさんが考案した

Adler-32は 2つの和の値 s1(2バイト)、s2(2バイト) からなる。
s1 は最初に「1」で初期化され、データ列の各値を先頭から順番に加算した結果を保持する。
s2 は最初に「0」で初期化され、s1にデータ列の値が加算されるたびに、そのs1の値を自身に加算した結果を保持する。

また双方ともに、加算されるたびに 65,521 との剰余によって上書きされ、計算の途中で桁あふれが起こらないようにされる。

結果的に求まる s1、s2を [s2, s1] の順番に連結することで、本来のAdler-32によるチェックサムが求まる。

zlibの解凍においては、4. 圧縮データ部を使って、Adler-32 チェックサムを算出する。その直後に現れる、圧縮データに含まれる 5. Adler-32 のチェックサムと比較し、値が一致していれば、"圧縮データが壊れていない" ということを確認することができる。