PNG イメージを自力でパースしてみる ~4/6 非圧縮とzlib編~
ここまでのあらすじ
PNG イメージを自力でパースしてみる ~1/6 予備知識編~
PNG イメージを自力でパースしてみる ~2/6 Deflateの基本と固定ハフマン編~
PNG イメージを自力でパースしてみる ~3/6 カスタムハフマン編~
前回、前々回でDeflateの「固定ハフマン」と「カスタムハフマン」について触れた。ここでは残るブロックタイプの「非圧縮」と、Deflateを利用した圧縮フォーマットの「zlib」についてを紹介。
予備知識
これからの説明を読む前に 予備知識が必要かも
バイトオーダー
あたりまえとは存ずるものの...
1バイト (8ビット) 単体では、256種類までの数値を表現できる。それより広い範囲の数値を扱いたい場合には、一般的に連続した複数のバイト並びを利用することで、それを実現する
ここで、表現したい値を その連続したバイト並びに対して、
どのような順で収めるのかを、ルールとして定めたものを
バイトオーダー または エンディアン と呼ぶ。
うち、実際によく利用されるのは以下の2つ
リトルエンディアン
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バイト?)
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バイト)
なお、データ中の各々の要素は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 圧縮で使用したスライド窓のサイズを表す値が設定される。
実際にはスライド窓のサイズを としたとき、
によって求まる値を、この 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) と呼ぶ。
zlibの圧縮プログラムと解凍プログラムはそれぞれ、自身のアプリケーションに合った任意の数のプリセット辞書を保有する。
圧縮時にプリセット辞書を使ったならば、FDICTに「1」を設定し、DICTIDに使ったプリセット辞書を識別するためのIDを設定する。通常ここには、プリセット辞書に対して、後述のAdler-32を施した結果の値を使用する。
解凍時には、FDICTを見て「1」であるならば、後に現れる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 のチェックサムと比較し、値が一致していれば、"圧縮データが壊れていない" ということを確認することができる。
サンプル
ここまでのサンプルプログラム
VC2015でのみ動作確認済み。
残念ながらプリセット辞書には対応できてない。
参考にしたサイトさん
RFC 1950 ZLIB Compressed Data Format Specification version 3.3 日本語訳 - futomi's CGI Cafe
RFC 1951 DEFLATE Compressed Data Format Specification version 1.3 日本語訳 - futomi's CGI Cafe
SWFバイナリ編集のススメ番外編 (zlib 伸張) 前編 | GREE Engineers' Blog