2017-12-12

最大公約数と最小公倍数を求める～2/3 素因数分解を利用する～

数学

最大公約数と最小公倍数を求める～1/3 割れるだけ割ってみる～
最大公約数と最小公倍数を求める～2/3 素因数分解を利用する～ ←この記事
最大公約数と最小公倍数を求める～3/3 ユークリッドの互除法を利用する～

ここでは 素因数分解 を使って
最大公約数と、最小公倍数を求める方法を勉強する

素因数分解を利用する
参考にした書籍/サイトさん

素因数分解を利用する

前の記事の事前知識で述べた通り、2 以上の数は素数1つ、またはいくつかの素数の掛け合わせによって表現できる

ここで、2 以上のある数を $X$
それから抽出できる素因数を $p$ としたとき
それらの関係を

${\hspace{6pt}}X=p_1{\times}p_2{\times}p_3{\times}p_4{\cdots}$

のような掛け算の式で表現することを 素因数分解 と呼ぶ

f:id:DarkCrowCorvus:20171202081223j:plain

この素因数分解を使って2つの値の最大公約数と最小公倍数を求める。

■求め方..
2つの値を素因数分解する。

見つかった素因数のうち、同じ素因数を指数を使ってまとめる。
2つの数の素因数分解の結果は、どちらも次の通りに表現できるようになるはず

${\hspace{6pt}}X=(p_1)^{r1}{\times}(p_2)^{r2}{\times}(p_3)^{r3}{\times}(p_4)^{r4}{\cdots}$

f:id:DarkCrowCorvus:20171202205657j:plain

その後、2つの式を縦に並べて、同じ素因数の「指数が小さい方」を片側に、「指数が大きい方」をもう片側に寄せる。

f:id:DarkCrowCorvus:20171202222530j:plain
なおここでは、片方にあって、もう片方にはない素因数が存在する場合、
ない方の式でその素因数を $(p_i)^{0}$ のように表現する

そうしてできた指数の小さい方を集めた式の答えが 2つの数の 最大公約数
指数の大きい方を集めた式の答えが 2つの数の 最小公倍数 になる

f:id:DarkCrowCorvus:20171202222557j:plain

素因数分解の一意性

これの理解のために、
先に「素因数分解の一意性」について知っておきたい

■ 素因数分解の一意性とは...

ある数を素因数分解するとき、素因数の並び順を考慮しないとするならば、それを表す式はただ一通りしか存在しない..という定理

またこの「素因数分解の一意性」の理解のために、先に「ユークリッドの補題」について知っておきたい

■ ユークリッドの補題とは...

ある2つの数の積 $ab$ を、
ある数 $p$ で割り切ることができるならば、

$p$ は $a$ と $b$ の
少なくともどちらか一方を割り切ることができる…という定理

この定理は一見アタリマエのように見える。数学ではこれを 自明である というらしいのだけど、実際のところこれは自明ではないらしい。

この証明のために、先に「ベズーの補題」という定理を知る必要があるらしい...が、これ以上細かく見ていくと、本題から離れすぎて何の記事だかよくわからなくなりそう。
今回は単に「そういった定理があるからユークリッドの補題は成り立つ」とだけ覚えておいて、先に進みたい。

■ 証明 (素因数分解の一意性)

ある数を素因数分解した結果が、2通りになる可能性があるとする

f:id:DarkCrowCorvus:20171203152058j:plain

${\hspace{6pt}}X=p_1{\times}p_2{\times}p_3{\cdots}{\times}p_n$
$\hspace{16pt}=q_1{\times}q_2{\times}q_3{\cdots}{\times}q_m \hspace{15pt}_{(n \leq m)}$

ここで、片方の素因数分解「 $p_1{\times}p_2{\cdots}$ 」の中に含まれる、
素因数 $p_1$ に着目してみる。

左辺の $X$ は $p_1$ を素因数にもつ。
よって $p_1$ の倍数であるため、
$X$ は $p_1$ によって、割りきることができる $\cdots$ ①

もう片方の素因数分解「 $q_1{\times}q_2{\cdots}$ 」は、
同じ $X$ を成す掛け算の式である。

さきほどの「ユークリッドの補題」の定理に従うならば、①によってそのもう片方の素因数分解の中に、 $p_1$ で割り切れる素因数が存在するはずである。

f:id:DarkCrowCorvus:20171203152128j:plain

ここで、 $p_1$ によって割り切れる素因数 $q_1$ が見つかったとする。

$q_1$ は素因数。つまり 1 か自身と同じ数でしか割り切ることができない。そして事前知識で述べたとおり、1 は素数に含まれないため、素因数分解の中に 1 が現れることはない

よってこの要件を満たす $q_1$ は「 $q_1=p_1$ 」ということになる。
「 $p_2,p_3{\cdots}$ 」についても、同じくそれらと一致する「 $q_2,q_3{\cdots}$ 」を見つけられるはず

f:id:DarkCrowCorvus:20171203152212j:plain

次に $p_1{\cdots}p_n$ すべてに一致する $q_1{\cdots}q_n$ を見つけられた後、まだ片方の素因数分解の中に $q_{n+1}{\cdots}q_m$ が残る場合があるかを考えてみる

${\hspace{6pt}}X=p_1{\times}p_2{\times}p_3{\cdots}{\times}p_n$
$\hspace{16pt}=q_1{\times}q_2{\times}q_3{\cdots}{\times}q_m \hspace{15pt}_{(n \leq m)}$

この式を満たすためには、片方の式に余分に存在する素因数 $q_{n+1}{\cdots}q_m$ は全て 1 でなければならない。しかし前述のとおり、1 が素因数分解の中に含まれるのは不適である。

f:id:DarkCrowCorvus:20171203152234j:plain

よって双方の素因数の数は一致する $(n=m)$
どちらか一方が多かったり、少なかったりする場面は存在しない

これらを踏まえて、上記 2つの素因数分解の式は一致する。
素因数分解の結果は、その並び順を考慮しないならば一意になる。

自分なりに解釈 (最大公約数)

2つの数の素因数分解の結果、素因数の指数が小さい (または等しい) ほうを集めた式から、最大公約数が求められる。

その式に含まれる素因数は、元の2つの数と比べてどれも指数が小さい、または等しくなるため、前述の事実に従って、その式から成る数は、2つの数にとっての約数 (公約数) になる

またその式から成る数が、2つの数の公約数であるためには、式中のどの素因数の指数もそれ以上大きくすることができない。

たとえば、今よりも大きな公約数を作ろうとする時、その数の少なくとも1つ以上の素因数の指数は、もとの公約数の同じ素因数の指数よりも大きくなる

しかし、どの素因数の指数が今より大きくなっても、もとの2つの数のうち、少なくともどちらか一方の同じ素因数の指数よりも大きくなってしまう

f:id:DarkCrowCorvus:20171205010943j:plain

前述の事実「約数なら素因数の指数がどれも小さいか等しい」を満たさなくなるため
その一方、あるいは両方の約数になることができず、結果公約数ではなくなる

素因数の指数が小さい (または等しい) ほうを集めた式から成る数について、結局それより大きな公約数を作ることはできないため、それが 2つの数にとっての最大公約数になる

自分なりに解釈 (最小公倍数)

2つの数の素因数分解の結果、素因数の指数が大きい (または等しい) ほうを集めた式から、最小公倍数が求められる

その式に含まれる素因数は、もとの2つの数と比べてどれも指数が大きいか、または等しい。一つ上の項で解説した事実に従い、もとの2つの数はその式から成る数の約数、よってその式から成る数はもとの2つの数の倍数 (公倍数) になる

またその式から成る数が、2つの数の公倍数であるためには、式中のどの素因数の指数も今より小さくすることができない。

理屈は上の項で説明したのと大体同じ。
今よりも小さな公倍数を作れないため、結果それが 最小公倍数 になる

3つ以上の数の最大公約数と最小公倍数

どちらも考え方は 2つの数に対して求めた時とあまり変わらない。

3つ以上の数をそれぞれ素因数分解して、その中から各素因数の指数が一番小さいものを寄せた式から、最大公約数 を求められる

また、各素因数の指数が一番大きなものを寄せた式から、最小公倍数 を求められる

f:id:DarkCrowCorvus:20171205090754j:plain

参考にした書籍/サイトさん

書籍
なっとくする群・環・体 (Amazon)

素因数分解の一意性

素因数分解の一意性とその証明について | 高校数学の美しい物語

最小公倍数/最大公約数
最大公約数と最小公倍数

３つ以上の数の公倍数・公約数｜算数をしよう｜ACTABA

2017-11-26

最大公約数と最小公倍数を求める～1/3 割れるだけ割ってみる～

数学

最大公約数と最小公倍数を求める～1/3 割れるだけ割ってみる～ ←この記事
最大公約数と最小公倍数を求める～2/3 素因数分解を利用する～
最大公約数と最小公倍数を求める～3/3 ユークリッドの互除法を利用する～

何となく読んでいた数学系の本で
最大公約数と最小公倍数という単語を見つけた。

たしかこれって習ったのは小学生のころだったはず…
ただどうやって求めるものなのかもう覚えていなかった。

なんだか悔しくなったのでこの際きっちり復習してみる。
完全に自分のための記事。

事前知識
割れるだけ割ってみる
参考にした書籍/サイトさん

事前知識

倍数

ある数を2倍、3倍...のように
何倍かしてできる数をその数の倍数という

ある2つの数に共通する倍数をその2つの数の公倍数という
その挙げられる公倍数のうち最も小さい数を 2つの数の最小公倍数という

約数

ある数が掛け算によって求められるとき、
その掛け算に使った "元の数" は約数と呼ばれる

ある2つの数に共通する約数をその2つの数の公約数という
その挙げられる公約数のうち最も大きな数を 2つの数の最大公約数という

素数

自然数の中で、1 か自分自身の数でしか割ることができない数は素数と呼ばれる。

2 以上の数は、必ず素数１つ、もしくはいくつかの素数の掛け合わせによって表現できる。ここでこの掛け合わせに使った "元の素数" は素因数と呼ばれる

1 は例外的に素数には含まれない。 1 が素数に含まれてしまう場合、例えば素因数分解の結果にいくつでも ×1 を置けてしまう不都合が生じる
( 素因数分解についてはこの次の記事で紹介 )

割れるだけ割ってみる

2つの数を共通して割れそうな数 (公約数) を見つけて、
その公約数で2つの数を割る

結果からまだ公約数が見つかるなら、
その公約数でまた2つの数を割る...のように割り算を繰り返す。

f:id:DarkCrowCorvus:20171213004258j:plain

2つの数の中に、2以上の公約数を見つけられなくなるまで割り切ったところで、それまでに出た公約数すべての積を求めると、それが最大公約数になる

また、公約数すべての積に "割り残りの 2つの数" を掛けることで、最小公倍数が求まる。

f:id:DarkCrowCorvus:20180710004933p:plain

小学校で習うらしいのだけど、まったく記憶に残っていない。

自分なりに解釈 (最大公約数)

2つの数をある公約数で割った結果からまだ公約数が見つかるのであれば、その公約数とそれまでに見つけられた公約数との積によって、より大きな公約数を作れることがある

f:id:DarkCrowCorvus:20171128002248j:plain

2 以上の公約数が見つけられなくなるまで、この「公約数を見つけては割る」を繰り返すと、割り残った2つの数には 1 しか公約数が残されない

1 を取ってそれまでに見つけられた公約数 (の積) に掛けても、もうそれよりも大きな公約数を作ることはできない

よって、2 以上の公約数がなくなるまで 2つの数に対する割り算を繰り返した末に、その中で見つけられた公約数すべての積を求めるとそれが最大公約数になる

自分なりに解釈 (最小公倍数)

見つけられた公約数すべての積に、割り残りの数 2つを掛けた結果が、元々の数2つの最小公倍数になる

"見つけられた公約数すべての積" を、ここでは $G$ と呼ぶことにしてみる

f:id:DarkCrowCorvus:20180716201227p:plain
※ "最大公約数" とは呼ばないことにする。というのも最小公倍数を求めるときの "公約数すべての積" は 場合によって 最大公約数と一致しないことがある

① 割り残りの数 2つを $a,b$ と表すならば、上で述べた最小公倍数を求める掛け算は $aGb$ のように表現できる
( $a{\times}G{\times}b$ ... "×"は省略できる)

②「元々の数」は、 $G$ (公約数すべての積) を、 $a,b$ (割り残りの数) にそれぞれ掛けることで各々復元することができる

f:id:DarkCrowCorvus:20180716210304p:plain

② の「元々の数」2つをそれぞれ $A,B$ と表し、
① の最小公倍数を成す掛け算を整理すると

${\hspace{6pt}}(aG)b=Ab$ つまりそれは $A$ の $b$ 倍
${\hspace{6pt}}a(Gb)=aB$ つまりそれは $B$ の $a$ 倍

よってこれは元々の数 $A$ の倍数であり、元々の数 $B$ の倍数。
つまりこの掛け算によって求まる数は、元々の数 $A,B$ の公倍数になることがわかる

f:id:DarkCrowCorvus:20180716211728p:plain

また、これがきちんと最小公倍数になる。

まず、2 以上の公約数が見つからなくなるまで割られた後の 2つの数 $a,b$ は、言い換えるならば、お互いに共通する素因数がなくなるまで割られた後の 2つの数である。

先ほどの掛け算 $aGb$ について、

$aG=A$ である。ここでたとえば、 $aG$ 側をそのままに、 $b$ を 1ずつ減少させることによって、 $A$ の倍数であることを維持しつつ、 $B$ の倍数にもなるより小さな公倍数

${\hspace{6pt}}aG(b-n){\hspace{10pt}}$ ただし $b \gt (b-n) \gt 0$

を作れないかを考えてみる。

f:id:DarkCrowCorvus:20180718090610p:plain

$Gb=B$ である。このことから、 $aG(b-n)$ が $B$ の倍数になるためには、 $G$ を除いた $a(b-n)$ が $b$ の倍数になる必要がある。

そのためには $(b-n)$ によって失われるであろう「 $b$ を成すために必要な素因数」を $a$ 側が持っていないといけない
※「素因数分解の一意性」という定理によってこの理屈に至る。詳しくは次の記事で紹介

しかし前述の通り、 $a,b$ はお互いに共通する素因数がなくなるまで割られた後の数である。したがって $b$ を構成するために必要な素因数は $a$ 側から一切得られず、 $aG(b-n)$ は $B$ の倍数にはなれない

よって $aGb$ においてそれが $A$ と $B$ との公倍数であるためには、今よりも $b$ を小さくすることはできない。

f:id:DarkCrowCorvus:20180723001036p:plain

f:id:DarkCrowCorvus:20180723001053p:plain
$a$ を減少させる $(a-n)Gb$ によって、より小さい公倍数を見つけようとする試みも、同様に無効である。

結局 $aGb$ よりも小さい数は、元々の2つの数 $A,B$ のどちらか片方の倍数にはなりうるが、公倍数になることはできない。

見つけられた公約数すべての積 $G$ に割り残り 2つの数 $a,b$ を掛けた結果が、たしかに最小公倍数ということになる。

3つ以上の数の最大公約数と最小公倍数

f:id:DarkCrowCorvus:20171201001955j:plain

3つ以上の数の最大公約数を求める場合、その 3つ以上の数すべてを共通して割れる数 (公約数) を見つけて割り、また見つけて割りを繰り返す。

割り切ったそれらの数すべてに共通する 2 以上の公約数を見つけられなくなったところで、それまでに出現した公約数すべての積を求めれば、それがその3つ以上の数に対する最大公約数になる

f:id:DarkCrowCorvus:20171201005900j:plain
一方、3つ以上の数の最小公倍数を求める場合、割り算の仕方は、最大公約数を求めるときと若干異なる。

3つ以上の数に対して前述の割り算の繰り返し、それらすべてに共通する公約数を見つけられなくなっても、そのうちのどれか2つ以上の数の中にまだ公約数を見つけられるのであれば、それらの数に対して見つけられた公約数による割り算を行う

この割り算を、どの数の組み合わせからも、2 以上の公約数を見つけられなくなるまで繰り返す。その結果、出現した公約数すべてと、割り残った数すべてとの積を求めれば、それが 3つ以上の数に対する最小公倍数になる

参考にした書籍/サイトさん

書籍
なっとくする群・環・体 (Amazon)

最小公倍数/最大公約数
最大公約数と最小公倍数

３つ以上の数の公倍数・公約数｜算数をしよう｜ACTABA

2017-02-12

PNG イメージを自力でパースしてみる～5/6 PNGフォーマット編～

PNG

ここまでのあらすじ

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

zlibを解凍するプログラムが一通り完成した。いよいよPNGファイルのパースに挑戦してみる。

PNGフォーマット
- シグネチャ
- チャンク
チャンクの種類
PNGイメージのパース
- フィルタリング処理
サンプル
参考にしたサイトさん

PNGフォーマット

PNGファイルの中身は、以下のような構成になっている

シグネチャ
チャンク (IHDR)
チャンク
　⋮
チャンク (IEND)

チャンクは１ファイルにつき、必要な数だけ作られる。

このチャンクのかたまりの中で、IHDRのチャンク (後述) は必ず先頭に出現し、
IENDのチャンク (後述) は必ず末尾に出現する。

シグネチャ

ファイルの先頭に必ず出現し、このファイルがPNGファイルであることを示す 8バイト長のデータ。すべてのPNGファイルは共通して、以下の値の並びを保有する。

10進 (16進)：

137 (89)

80 (50)

78 (4e)

71 (47)

13 (0d)

10 (0a)

26 (1a)

10 (0a)

PNGファイルをロードするプログラムは、まず初めにファイルの先頭 8バイトを読み出し、このシグネチャの並びと一致するかどうかで、対象が確かに PNGファイルであるかどうかをチェックする必要がある

ちなみにこの並びの中に現れる各値は、それぞれ以下のような役割を持つ

10進	16進	ASCII文字	役割
137	89	\221	ASCII文字として表現できない値。ファイルに必ず非ASCII文字を含むことで、テキストファイルとして間違えてロードされてしまう可能性を減らす。
80	50	P	自身のフォーマット名を表す
78	4e	N
71	47	G
13	0d	\r	"改行文字"として解釈されてしまい、システムによって勝手に「\r」や「\n」に置き換えられたりしないかを検出するために利用される
10	0a	\n
26	1a	\032	Control-z文字。ファイルの中身をテキストとして読み出し表示させようとしたDOSコマンドを停止させる
10	0a	\n	"改行文字"として解釈されてしまい、システムによって勝手に「\r」や「\r\n」に置き換えられたりしないかを検出するために利用される

チャンク

PNGファイル中に現れる各チャンクは、共通して以下のような構造になっている

Length	4バイト
Chunk Type	4バイト
Chunk Data	Length バイト
CRC	4バイト

1. Length（データのサイズ）

このチャンクの Chunk Data 部のサイズ (バイト数) を表す値をここに4バイト長で格納する。最小で「0」最大で「 $2^{31}-1$ 」までの値を収められる

2. Chunk Type（チャンクの種類）

このチャンクの種類を表す、アルファベット4文字のデータがここに格納される

3. Chunk Data（データ）

Length が「0」ではない場合、このチャンクの種類に関連したデータが、この場所に格納される。

4. CRC（crc32チェックサム）

CRC32チェックサムアルゴリズムを使って算出された値を、ここに4バイト長で格納する。ここの詳しい解説は、次回の記事で行うことにする。

なお、PNGファイル中に現れるこれら多バイト長の数値データはすべてビッグエンディアンの並びになっている。これらの数値データを読み出す際には、その読み出したデータのバイト並びに気を付けること。

チャンクの種類

PNGで利用できるチャンクの種類 (Chunk Type) を以下にざっと書き並べてみる

Chunk Type	説明	必須
IHDR	ヘッダ情報	〇
PLTE	パレット	〇
IDAT	イメージデータ	〇
IEND	終端	〇
tRNS	透過
cHRM	色度と白色点
gAMA	イメージガンマ
iCCP	埋め込みICCプロファイル
sBIT	主要ビット
sRGB	標準的なRGB色空間
tEXt	テキストデータ
zTXt	圧縮テキストデータ
iTXt	国際テキストデータ
bKGD	背景色
hIST	画像のヒストグラム
pHYs	ピクセル寸法
sPLT	推奨パレット
tIME	最終更新時刻

これすべてに対応しようとすると、さすがに途中で心が折れそう..
今回は必須チャンクに分類されるもののうち、

IHDR(ヘッダ情報)
IDAT(イメージデータ)
IEND(終端)

の３つのみに対応することにしてみる。

IHDR (ヘッダ情報)

Length	4バイト
Chunk Type ： "IHDR"	4バイト
Chunk Data	計 13バイト
・Width	4バイト
・Height	4バイト
・Bit Depth	1バイト
・Color Type	1バイト
・Compression Method	1バイト
・Filter Method	1バイト
・Interlace method	1バイト
CRC	4バイト

シグネチャを読み出した後、チャンクのかたまりの先頭に必ず現れるチャンク。
データ部は、以下の要素で構成される

1. Width （イメージの横幅）
2. Height（イメージの縦幅）

画像の縦横のピクセル数の値がそれぞれ4バイト長で収められる。

3. Bit Depth（ビット深度）

ピクセルの色要素「R」「 G」「 B」のそれぞれ、またはパレット番号 (今回は取り扱わない) が何ビット長で記録されているかを表す値が、ここに 1バイト長で収められる。

なお、後の Color Type の値によって、この場所に設定できる値が異なってくる

4. Color Type（カラータイプ）

PNGイメージのカラータイプを表す値が、ここに1バイト長で収められる。
ここに設定される値は、以下のビットフラグの組み合わせによって形成される

1（001）：パレット使用　　 (0なら不使用)
2（010）：カラー使用　　　(0ならグレースケール)
4（100）： αチャンネル使用 (0なら不使用)

ただし、このうち実際に使用することのできるフラグの組み合わせは、いくつかに限られている。使用が可能な Color Type と対応する使用が可能な Bit Depth との一覧を以下に示す

Color Type	Bit Depth	説明
0（000）	1, 2, 4, 8, 16	グレースケール
2（010）	8, 16	RGBカラー
3（011）	1, 2, 4, 8	インデックスカラー(要PLTEチャンク)
4（100）	8, 16	グレースケール＋ αチャンネル
6（110）	8, 16	RGBカラー＋ αチャンネル

5. Compression Method（圧縮方法）

画像データの圧縮のために、どのようなアルゴリズムを利用したかを表す値を、ここに 1バイト長で収める。「0」が設定されている場合、自身の画像データが、Deflate によって圧縮されたことを表す。

なお、０以外の値は、現状扱われることがない。とりあえず今は「0を読み出せれば正しい」と覚えていれば問題ないはず

6. Filter Method（フィルタ方法）

圧縮前の画像データに対して、どのような事前処理を行ったかを表す値を、ここに 1バイト長で収める。「0」が設定されている場合、画像データに対して、圧縮前にフィルタリング処理 (後述) が施されることを表す。

なお、０以外の値は、現状扱われることがない。こちらもとりあえずは「0を読み出せれば正しい」と覚えておけば問題ないはず

7. Interlace Method（インタレース）

画像データのピクセル要素の出現規則を表す値を、ここに 1バイト長で収める。
「0」ならインタレースなし、「1」ならインタレースありとなる。

画像データにおけるインタレースとは、画像データ中のピクセル要素をそのままの順で出現させるのではなく、飛び飛びで出現させるようにする手法のこと。

うち、インタレースありの PNGイメージは、以下の図に示す通りに処理される。

f:id:DarkCrowCorvus:20170120234812g:plain

これによる利点は、画像データを読み始めた早い段階で、おおざっぱな画像の全体像がわかるということ。初めにモザイク調で表示させ、読み込みが進み次第、徐々に鮮明になるように画像を表示させることができるようになる。

なお、今回は残念ながら実装が面倒だったのでインタレースに対応していない。
気が向いたらそのうち..

IDAT (イメージデータ)

Length	4バイト
Chunk Type ： "IDAT"	4バイト
Chunk Data （画像データ）	Length バイト
CRC	4バイト

実際に画像を構成するピクセル要素またはパレット番号の連なりからなるデータが、このチャンクの中に収められる。

このとき、収められる画像データには、フィルタリング処理 (後述) と zlibによる圧縮が施される。zlibについては、前回の記事で紹介済み。

なお、このIDATチャンクは、ファイル中にいくつでも出現してかまわないことになっている。その場合、それらのIDATチャンクは必ず１か所に連続して出現する。

IEND (終端)

Length	4バイト
Chunk Type ： "IEND"	4バイト
CRC	4バイト

チャンクのかたまりの末尾に、必ず現れるチャンク。
自身を読み出した地点がファイルが終わりであることを示す。

なお、IENDチャンクはデータ部を持たない。
Lengthには常に０に設定される。

PNGイメージのパース

対応できるチャンクを IHDR, IDAT, IEND に限った場合、これから以下に示す手順で、PNGイメージから、画像を構成するピクセルデータを引っ張りだすことができる

シグネチャ一致チェック
チャンク読み出し
IDATチャンクの zlib圧縮データを解凍
解凍したデータのフィルタリングを解く

1. シグネチャ一致チェック

ファイル先頭の 8バイトを読み出し、前述したシグネチャの並びと一致するかどうかをチェックする。

一致しなかった場合、そのファイルが PNGイメージではない、もしくは、ファイルを正しく読み出すことができないため、エラーとみなして、テキトウに処理を終了する。

2. チャンク読み出し

以下を IEND チャンクが出現するまで繰り返す

チャンクのLength (4バイト) を読み出す
Chunk Typeの4文字 (4バイト) を読み出す
Lengthが 0 でなければ、そのバイト数分だけ Chunk Dataを読み出す
CRC (4バイト) を読み出す

くどいようではあるけれど、今回は IHDR, IDAT, IEND のチャンクのみに対応する。それ以外のチャンクに遭遇しても、中身を考慮せずそのまま読み飛ばすことにする。

2.1. IHDRチャンク読み出し

シグネチャ並びの直後に出現。この場所に記録されている情報は、後に画像データを復元したり、ピクセル要素を抽出したりするために必要になる

なお、Color Typeが「3」である場合、ファイル中に PLTEチャンクが出現し、画像データはパレット番号によって構成される。

対応チャンク 3つ縛りの制限下では、このフォーマットに対応することができない。今回に限っては、これをエラーとみなしてテキトウに処理を終了することにする。
実装はたぶんまたそのうち...

2.2. IDATチャンクの読み出し

前述した通り、圧縮された実画像データがここに格納されている。

なお、このチャンクが複数出現する場合は、チャンクが出現した順番にChunk Data部のデータを連結する

3. IDATチャンクのzlib圧縮データを解凍

IDATチャンクから得られた Chunk Data 部
またはそれら複数を結合したデータに対して、zlibによる解凍を行う。

フィルタリング処理

PNGファイルに収められる画像データは、zlibによって圧縮される前に、その圧縮効率を上げる目的で フィルタリング という事前処理が施される

PNGイメージをパースする際、zlib解凍を行った後それを本来の画像データに戻すために、そのデータのフィルタリングを解く必要がある

現在、フィルタリングには、以下の 5種類のアルゴリズムが利用されている

番号	フィルタ名	説明
0	None	フィルタなし
1	Sub	隣接する左ピクセル色との差分
2	Up	隣接する上ピクセル色との差分
3	Average	左と上のピクセルの平均色との差分
4	Paeth	左、上、左上のピクセルのうち次回出現しそうな色との差分

これらのフィルタリングアルゴリズムは、画像の各水平ラインごとに行われる

フィルタタイプ０：None

該当する画像の水平ラインの先頭に「0」を表す数値を 8ビット長で付加する
先頭に 8ビット付加する以外には、水平ラインに対して特になにも行わない。

f:id:DarkCrowCorvus:20170209000242j:plain

ちなみに、ビット深度が 8 に満たないとき (BitDepth=1,2,4)
各水平ラインの末端がバイト境界になっていなかった場合は、次に出現するバイト境界の地点までの間にパディングが詰められるみたい

次の水平ラインの先頭ビットは必ず、その直近のバイト境界の位置から始まる

f:id:DarkCrowCorvus:20170207233748j:plain

フィルタタイプ１：Sub

該当する画像の水平ラインの先頭に「1」を表す数値を 8ビット長で付加する。
PNGイメージ中に収められるこの水平ライン上の各ピクセルの値は、左隣のピクセルの値との差分値になる。

f:id:DarkCrowCorvus:20170209000256j:plain

なお、差の結果は非負の 0～255（00～FF）の範囲に収まるよう丸められる。
　※例えば差の結果が負数の場合 [-1, -2, -3] は [255, 254, 253] のような通りになる。

また先頭のピクセルについては、左隣に参照できるピクセルがないため、左隣のピクセル値 = 0 として扱う

ここまでを見たとおり、フィルタリング処理自身は、データを圧縮するような作用を持っていない。しかも各水平ラインの先頭に、フィルタを識別するための 8ビットを付与するため、このままではむしろデータサイズを増やしてしまうだけのように見える。

ただしこのフィルタリング処理には、その後に続くDeflate の、圧縮効率を底上げするという機能がある。

実際には、Noneを除く 4種類のフィルタリングを使って、PNGイメージ中の値に偏りや同じ値並びを出現させることを行う。

このようにデータを変換することで、Deflateによるハフマン符号化、およびLZ77符号化がうまく働く機会が増えるため、データをより小さく圧縮できるようになる。

f:id:DarkCrowCorvus:20170210084353j:plain

うち「フィルタタイプ 1：Sub」は、横方向にピクセル値の変化が小さい水平ラインに対して効果を発揮する

ここで、フィルタリング処理は、必ず 8ビット単位 で行われるということに注意。
このルールは他のフィルタタイプにも共通する

ビット深度が16であるPNGイメージにおいては、上位8ビット、下位8ビットの2つに分割し、別々にフィルタリング処理を施す

ビット深度が8未満のPNGイメージにNone以外のフィルタタイプを適用する場合は、事前に８ビットに伸長されるらしい...?　サンプルを見つけられなかったため、ちょっと確かではないのだけど..

なお、Subフィルタリングされたピクセルは、
ピクセル値＋左隣のピクセル値の 256による剰余
によって元の値に復元できる

フィルタタイプ２：Up

該当する画像の水平ラインの先頭に「2」を表す数値を 8ビット長で付加する。
PNGイメージ中に収められるこの水平ライン上の各ピクセルの値は、真上のピクセルの値との差分値になる。 f:id:DarkCrowCorvus:20170211232608j:plain

差の結果は非負の 0～255（00～FF）の範囲に収まるよう丸められる。
このルールについても、差を扱うすべてのフィルタタイプに共通する

「フィルタタイプ２：Up」は縦方向にピクセルの値の変化が小さい水平ラインに対して効果を発揮する

なお、Upフィルタリングされたピクセルは、
ピクセル値＋真上のピクセル値の 256による剰余
によって元の値に復元できる

フィルタタイプ３：Average

該当する画像の水平ラインの先頭に「3」を表す数値を 8ビット長で付加する。
PNGイメージ中に収められるこの水平ライン上の各ピクセルの値は、左隣のピクセル値と、真上のピクセル値との平均をとった値との差分値になる。

　filtered value ＝ current － ((left ＋ up) ÷ 2)

f:id:DarkCrowCorvus:20170212174810p:plain

差の結果は非負の 0～255（00～FF）の範囲に収まるよう丸められる。
また先頭のピクセルについては、左隣に参照できるピクセルがないため、
左隣のピクセル値を 0 として扱い、平均を求める

平均の計算には整数徐算を利用する。
徐算の結果は、値の小さいほうの整数に丸められる（小数点以下切り捨て）

「フィルタタイプ３：Average」は似たピクセル値が密集しているあたりの水平ラインに対して効果を発揮する

なお、Averageフィルタリングされたピクセルは、
ピクセル値＋左隣と真上のピクセル値の平均の 256による剰余
によって元の値に復元できる

フィルタタイプ４：Paeth

該当する画像の水平ラインの先頭に「4」を表す数値を 8ビット長で付加する。
PNGイメージ中に収められるこの水平ライン上の各ピクセルの値は、「Paeth」というアルゴリズムから得られる結果の値との差分値になる。

　filtered value ＝ current － $Paeth$ (left, up, upleft)

f:id:DarkCrowCorvus:20170212230424p:plain

差の結果は非負の 0～255（00～FF）の範囲に収まるよう丸められる

Paethアルゴリズムは、左、上、左上の 3つの隣接するピクセル値から、「この位置に来るであろうピクセル値が、上記 3つのピクセル値のうち、どれと一番近くなりそうか」を予測するために利用される。Alan W. Paethさんが考案した

実際には以下のように求める

int PaethPredictor(int a, int b, int c)
{
    // ┏━━┳━━┓
    // ┃ ｃ ┃ ｂ ┃
    // ┣━━╋━━┫
    // ┃ ａ ┃ ?? ┃
    // ┗━━┻━━┛
    int p = a + b - c;

    // pa = |b - c|　　　横向きの値の変わり具合
    // pb = |a - c|　　　縦向きの値の変わり具合
    // pc = |b-c + a-c|　↑ふたつの合計
    int pa = abs(p - a);    
    int pb = abs(p - b);    
    int pc = abs(p - c);    

    // 横向きのほうがなだらかな値の変化 → 左
    if (pa <= pb && pa <= pc)
        return a;

    // 縦向きのほうがなだらかな値の変化 → 上
    if (pb <= pc)
        return b;
        
    // 縦横それぞれ正反対に値が変化するため中間色を選択 → 左上        
    return c;
}