feat(content): post /posts/2023-04-01/implementation-of-minimal-png-image-encoder/

1 files changed, 607 insertions, 0 deletions

diff --git a/content/posts/2023-04-01/implementation-of-minimal-png-image-encoder.xml b/content/posts/2023-04-01/implementation-of-minimal-png-image-encoder.xml
new file mode 100644
index 0000000..67dfad8
--- /dev/null
+++ b/content/posts/2023-04-01/implementation-of-minimal-png-image-encoder.xml
@@ -0,0 +1,607 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<article xmlns="http://docbook.org/ns/docbook" xmlns:xl="http://www.w3.org/1999/xlink" version="5.0">
+  <info>
+    <title>PNG 画像の最小構成エンコーダを実装する</title>
+    <abstract>
+      PNG 画像として valid な範囲で最大限手抜きしたエンコーダを書く。
+    </abstract>
+    <revhistory>
+      <revision>
+        <date>2023-04-01</date>
+        <revremark>公開</revremark>
+      </revision>
+    </revhistory>
+  </info>
+  <section xml:id="intro">
+    <title>はじめに</title>
+    <para>
+      この記事では、PNG 画像として valid な範囲で最大限手抜きしたエンコーダを書く。
+      PNG 画像に対応したビューアであれば読み込めるが、圧縮効率については一切考えない。
+      また、実装には Go 言語を使うが、Go の標準ライブラリにあるさまざまなアルゴリズム (PNG 画像に関係する範囲だと、zlib や CRC32、Adler-32 など) は使わない。
+    </para>
+  </section>
+  <section xml:id="basic-structure-of-png">
+    <title>PNG ファイルの基本構造</title>
+    <para>
+      PNG ファイルの基本構造は次のようになっている。
+    </para>
+    <orderedlist>
+      <listitem>PNG signature</listitem>
+      <listitem>IHDR chunk</listitem>
+      <listitem>任意個の chunk</listitem>
+      <listitem>IEND chunk</listitem>
+    </orderedlist>
+    <para>
+      Chunk には画像データを入れる IDAT chunk、パレットデータを入れる PLTE chunk、テキストデータを入れる tEXt chunk などがあるが、
+      今回は最小構成ということで IDAT chunk (と IHDR chunk と IEND chunk) のみを用いる。
+    </para>
+    <para>
+      次節で、それぞれの具体的な構造を確認しつつ実装していく。
+    </para>
+  </section>
+  <section xml:id="implement-png-encoder">
+    <title>PNG のエンコーダを実装する</title>
+    <para>
+      以下のソースコードをベースにする。
+      今回 PNG のデコーダは扱わないので、読み込みには Go の標準ライブラリ <literal>image/png</literal> を用いる。
+    </para>
+    <programlisting language="go" linenumbering="unnumbered">
+      <![CDATA[
+      package main
+
+      import (
+      	"image"
+      	_ "image/png"
+      	"io"
+      	"os"
+      )
+
+      func main() {
+      	inFile, err := os.Open("input.png")
+      	if err != nil {
+      		panic(err)
+      	}
+      	defer inFile.Close()
+
+      	img, _, err := image.Decode(inFile)
+      	if err != nil {
+      		panic(err)
+      	}
+
+      	outFile, err := os.Create("output.png")
+      	if err != nil {
+      		panic(err)
+      	}
+      	defer outFile.Close()
+
+      	writePng(outFile, img)
+      }
+
+      func writePng(w io.Writer, img image.Image) {
+      	width := uint32(img.Bounds().Dx())
+      	height := uint32(img.Bounds().Dy())
+      	writeSignature(w)
+      	writeChunkIhdr(w, width, height)
+      	writeChunkIdat(w, width, height, img)
+      	writeChunkIend(w)
+      }
+      ]]>
+    </programlisting>
+    <para>
+      以降は、<literal>writeSignature</literal> や <literal>writeChunkIhdr</literal> などを実装していく。
+    </para>
+    <section xml:id="implement-png-encoder--png-signature">
+      <title>PNG signature</title>
+      <para>
+        PNG signature は、PNG 画像の先頭に固定で付与されるバイト列で、8 バイトからなる。
+      </para>
+      <orderedlist>
+        <listitem>0x89</listitem>
+        <listitem>0x50 (ASCII コードで「P」)</listitem>
+        <listitem>0x4E (ASCII コードで「N」)</listitem>
+        <listitem>0x47 (ASCII コードで「G」)</listitem>
+        <listitem>0x0D (ASCII コードで CR)</listitem>
+        <listitem>0x0A (ASCII コードで LF)</listitem>
+        <listitem>0x1A (ASCII コードで EOF)</listitem>
+        <listitem>0x0A (ASCII コードで LF)</listitem>
+      </orderedlist>
+      <para>
+        CRLF や LF は、送信中に改行コードの変換が誤っておこなわれていないかどうかを検知するのに使われる。
+      </para>
+      <para>
+        <literal>writeSignature</literal> の実装はこちら:
+      </para>
+      <programlisting language="go" linenumbering="unnumbered">
+        <![CDATA[
+        import "encoding/binary"
+
+        func writeSignature(w io.Writer) {
+        	sig := [8]uint8{
+        		0x89,
+        		0x50, // P
+        		0x4E, // N
+        		0x47, // G
+        		0x0D, // CR
+        		0x0A, // LF
+        		0x1A, // EOF (^Z)
+        		0x0A, // LF
+        	}
+        	binary.Write(w, binary.BigEndian, sig)
+        }
+        ]]>
+      </programlisting>
+      <para>
+        <literal>encoding/binary</literal> パッケージの <literal>binary.Write</literal> を使い、固定の 8 バイトを書き込む。
+      </para>
+    </section>
+    <section xml:id="implement-png-encoder--structure-of-chunk">
+      <title>Chunk の構造</title>
+      <para>
+        IHDR chunk に進む前に、chunk 一般の構造を確認する。
+      </para>
+      <orderedlist>
+        <listitem>Length: chunk data のバイト長 (符号なし 4 バイト整数)</listitem>
+        <listitem>Chunk type: chunk の種類を示す 4 バイトからなる名前</listitem>
+        <listitem>Chunk data: 実際のデータ。0 バイトでもよい</listitem>
+        <listitem>CRC: chunk type と chunk data の CRC (符号なし 4 バイト整数)</listitem>
+      </orderedlist>
+      <para>
+        CRC (Cyclic Redundancy Check) は誤り検出符号の一種。Go 言語では <literal>hash/crc32</literal> パッケージにあるが、今回はこれも自前で実装する。PNG の仕様書に C 言語のサンプルコードが載っている (<link xl:href="https://www.w3.org/TR/png/#D-CRCAppendix">D. Sample CRC implementation</link>) ので、これを Go に移植する。
+      </para>
+      <programlisting language="go" linenumbering="unnumbered">
+        <![CDATA[
+        var (
+        	crcTable         [256]uint32
+        	crcTableComputed bool
+        )
+
+        func makeCrcTable() {
+        	for n := 0; n < 256; n++ {
+        		c := uint32(n)
+        		for k := 0; k < 8; k++ {
+        			if (c & 1) != 0 {
+        				c = 0xEDB88320 ^ (c >> 1)
+        			} else {
+        				c = c >> 1
+        			}
+        		}
+        		crcTable[n] = c
+        	}
+        	crcTableComputed = true
+        }
+
+        func updateCrc(crc uint32, buf []byte) uint32 {
+        	if !crcTableComputed {
+        		makeCrcTable()
+        	}
+
+        	c := crc
+        	for n := 0; n < len(buf); n++ {
+        		c = crcTable[(c^uint32(buf[n]))&0xFF] ^ (c >> 8)
+        	}
+        	return c
+        }
+
+        func crc(buf []byte) uint32 {
+        	return updateCrc(0xFFFFFFFF, buf) ^ 0xFFFFFFFF
+        }
+        ]]>
+      </programlisting>
+      <para>
+        できた <literal>crc</literal> 関数を使って、chunk 一般を書き込む関数も用意しておこう。
+      </para>
+      <programlisting language="go" linenumbering="unnumbered">
+        <![CDATA[
+        func writeChunk(w io.Writer, chunkType string, data []byte) {
+        	typeAndData := make([]byte, 0, len(chunkType)+len(data))
+        	typeAndData = append(typeAndData, []byte(chunkType)...)
+        	typeAndData = append(typeAndData, data...)
+
+        	binary.Write(w, binary.BigEndian, uint32(len(data)))
+        	binary.Write(w, binary.BigEndian, typeAndData)
+        	binary.Write(w, binary.BigEndian, crc(typeAndData))
+        }
+        ]]>
+      </programlisting>
+      <para>
+        仕様どおり、<literal>chunkType</literal> と <literal>data</literal> から CRC を計算し、<literal>data</literal> の長さと合わせて書き込んでいる。
+        PNG では基本的に big endian を使うことに注意する。
+      </para>
+      <para>
+        準備ができたところで、具体的な chunk をエンコードしていく。
+      </para>
+    </section>
+    <section xml:id="implement-png-encoder--ihdr-chunk">
+      <title>IHDR chunk</title>
+      <para>
+        IHDR chunk は最初に配置される chunk である。次のようなデータからなる。
+      </para>
+      <orderedlist>
+        <listitem>画像の幅 (符号なし 4 バイト整数)</listitem>
+        <listitem>画像の高さ (符号なし 4 バイト整数)</listitem>
+        <listitem>
+          ビット深度 (符号なし 1 バイト整数)
+          <itemizedlist>
+            <listitem>1 色に使うビット数。1 ピクセルに 24 bit 使う truecolor 画像では 8 になる</listitem>
+          </itemizedlist>
+        </listitem>
+        <listitem>
+          色タイプ (符号なし 1 バイト整数)
+          <itemizedlist>
+            <listitem>0: グレースケール</listitem>
+            <listitem>2: Truecolor (今回はこれに決め打ち)</listitem>
+            <listitem>3: パレットのインデックス</listitem>
+            <listitem>4: グレースケール + アルファ</listitem>
+            <listitem>6: Truecolor + アルファ</listitem>
+          </itemizedlist>
+        </listitem>
+        <listitem>
+          圧縮方式 (符号なし 1 バイト整数)
+          <itemizedlist>
+            PNG の仕様書に 0 しか定義されていないので 0 で固定
+          </itemizedlist>
+        </listitem>
+        <listitem>
+          フィルタ方式 (符号なし 1 バイト整数)
+          <itemizedlist>
+            PNG の仕様書に 0 しか定義されていないので 0 で固定
+          </itemizedlist>
+        </listitem>
+        <listitem>
+          インターレース方式 (符号なし 1 バイト整数)
+          <itemizedlist>
+            今回はインターレースしないので 0
+          </itemizedlist>
+        </listitem>
+      </orderedlist>
+      <para>
+        今回ほとんどのデータは決め打ちするので、データに応じて変わるのは width と height だけになる。コードは次のようになる。
+      </para>
+      <programlisting language="go" linenumbering="unnumbered">
+        <![CDATA[
+        import "bytes"
+
+        func writeChunkIhdr(w io.Writer, width, height uint32) {
+        	var buf bytes.Buffer
+        	binary.Write(&buf, binary.BigEndian, width)
+        	binary.Write(&buf, binary.BigEndian, height)
+        	binary.Write(&buf, binary.BigEndian, uint8(8))
+        	binary.Write(&buf, binary.BigEndian, uint8(2))
+        	binary.Write(&buf, binary.BigEndian, uint8(0))
+        	binary.Write(&buf, binary.BigEndian, uint8(0))
+        	binary.Write(&buf, binary.BigEndian, uint8(0))
+
+        	writeChunk(w, "IHDR", buf.Bytes())
+        }
+        ]]>
+      </programlisting>
+    </section>
+    <section xml:id="implement-png-encoder--idat-chunk">
+      <title>IDAT chunk</title>
+      <para>
+        IDAT chunk は、実際の画像データが格納された chunk である。IDAT chunk は deflate アルゴリズムにより圧縮され、zlib 形式で格納される。
+      </para>
+      <section xml:id="implement-png-encoder--idat-chunk--zlib">
+        <title>Zlib</title>
+        <para>
+          まずは zlib について確認する。おおよそ次のような構造になっている。
+        </para>
+        <orderedlist>
+          <listitem>固定で 0x78 (符号なし 1 バイト整数)</listitem>
+          <listitem>固定で 0x01 (符号なし 1 バイト整数)</listitem>
+          <listitem>データ</listitem>
+          <listitem>データの Adler-32</listitem>
+        </orderedlist>
+        <para>
+          最初の 2 バイトにも意味はあるが、PNG では固定で構わない。
+        </para>
+        <para>
+          Adler-32 も CRC と同じく誤り検出符号である。こちらも zlib の仕様書に C 言語でサンプルコードが記載されている (<link xl:href="https://www.rfc-editor.org/rfc/rfc1950#section-9">9. Appendix: Sample code</link>) ので、Go に移植する。
+        </para>
+        <programlisting language="go" linenumbering="unnumbered">
+          <![CDATA[
+          const adler32Base = 65521
+
+          func updateAdler32(adler uint32, buf []byte) uint32 {
+          	s1 := adler & 0xFFFF
+          	s2 := (adler >> 16) & 0xFFFF
+
+          	for n := 0; n < len(buf); n++ {
+          		s1 = (s1 + uint32(buf[n])) % adler32Base
+          		s2 = (s2 + s1) % adler32Base
+          	}
+          	return (s2 << 16) + s1
+          }
+
+          func adler32(buf []byte) uint32 {
+          	return updateAdler32(1, buf)
+          }
+          ]]>
+        </programlisting>
+        <para>
+          「データ」の部分には圧縮したデータが入るのだが、真面目に deflate アルゴリズムを実装する必要はない。Zlib には無圧縮のデータブロックを格納することができるので、これを使う。本来は、データの圧縮効率の悪いランダムなデータをそのまま格納するためのものだが、今回は deflate の実装をサボるために使う。
+        </para>
+        <para>
+          1 つの無圧縮ブロックには 65535 (2<superscript>16</superscript> - 1) バイトまで格納できる。それぞれのブロックは次のような構成になっている。
+        </para>
+        <orderedlist>
+          <listitem>最終ブロックなら 1、そうでなければ 0 (符号なし 1 バイト整数)</listitem>
+          <listitem>ブロックのバイト長 (符号なし 2 バイト整数)</listitem>
+          <listitem>ブロックのバイト長の 1 の補数、あるいはビット反転 (符号なし 2 バイト整数)</listitem>
+          <listitem>データ (最大 65535 バイト)</listitem>
+        </orderedlist>
+        <para>
+          実際にこの手抜き zlib を実装したものがこちら:
+        </para>
+        <programlisting language="go" linenumbering="unnumbered">
+          <![CDATA[
+          func encodeZlib(data []byte) []byte {
+          	var buf bytes.Buffer
+
+          	binary.Write(&buf, binary.BigEndian, uint8(0x78))
+          	binary.Write(&buf, binary.BigEndian, uint8(0x01))
+          	blockSize := 65535
+          	isFinalBlock := false
+          	for i := 0; !isFinalBlock; i++ {
+          		var block []byte
+          		if len(data) <= (i+1)*blockSize {
+          			block = data[i*blockSize:]
+          			isFinalBlock = true
+          		} else {
+          			block = data[i*blockSize : (i+1)*blockSize]
+          		}
+          		binary.Write(&buf, binary.BigEndian, isFinalBlock)
+          		binary.Write(&buf, binary.LittleEndian, uint16(len(block)))
+          		binary.Write(&buf, binary.LittleEndian, uint16(^len(block)))
+          		binary.Write(&buf, binary.LittleEndian, block)
+          	}
+          	binary.Write(&buf, binary.BigEndian, adler32(data))
+
+          	return buf.Bytes()
+          }
+          ]]>
+        </programlisting>
+      </section>
+      <section xml:id="implement-png-encoder--idat-chunk--image-data">
+        <title>画像データ</title>
+        <para>
+          では次に、zlib 形式で格納するデータを用意する。PNG 画像は次のような順にスキャンする。
+          画像の左上のピクセルから同じ行を横にスキャンしていき、一番右まで到達したら次の行の左に向かう。
+          右下のピクセルまで行けば終わり。要は Z 字型に進んでいく。
+        </para>
+        <para>
+          また、それぞれの行の先頭には、圧縮のためのフィルタタイプを指定する。
+          ただ、今回はその実装を省略するために、常にフィルタ 0 (何も加工しない) を使う。
+        </para>
+        <para>
+          先ほどの <literal>encodeZlib</literal> も使って実際に実装したものがこちら:
+        </para>
+        <programlisting language="go" linenumbering="unnumbered">
+          <![CDATA[
+          func writeChunkIdat(w io.Writer, width, height uint32, img image.Image) {
+          	var pixels bytes.Buffer
+          	for y := uint32(0); y < height; y++ {
+          		binary.Write(&pixels, binary.BigEndian, uint8(0))
+          		for x := uint32(0); x < width; x++ {
+          			r, g, b, _ := img.At(int(x), int(y)).RGBA()
+          			binary.Write(&pixels, binary.BigEndian, uint8(r))
+          			binary.Write(&pixels, binary.BigEndian, uint8(g))
+          			binary.Write(&pixels, binary.BigEndian, uint8(b))
+          		}
+          	}
+
+          	writeChunk(w, "IDAT", encodeZlib(pixels.Bytes()))
+          }
+          ]]>
+        </programlisting>
+      </section>
+    </section>
+    <section xml:id="implement-png-encoder--iend-chunk">
+      <title>IEND chunk</title>
+      <para>
+        最後に IEND chunk を書き込む。これは PNG 画像の最後に配置される chunk で、PNG のデコーダはこの chunk に出会うとそこでデコードを停止する。
+      </para>
+      <para>
+        特に追加のデータはなく、必要なのは chunk type の <literal>IEND</literal> くらいなので実装は簡単:
+      </para>
+      <programlisting language="go" linenumbering="unnumbered">
+        <![CDATA[
+        func writeChunkIend(w io.Writer) {
+        	writeChunk(w, "IEND", nil)
+        }
+        ]]>
+      </programlisting>
+    </section>
+  </section>
+  <section xml:id="outro">
+    <title>おわりに</title>
+    <para>
+      最後に全ソースコードを再掲しておく。
+    </para>
+    <programlisting language="go" linenumbering="unnumbered">
+      <![CDATA[
+      package main
+
+      import (
+      	"bytes"
+      	"encoding/binary"
+      	"image"
+      	_ "image/png"
+      	"io"
+      	"os"
+      )
+
+      func main() {
+      	inFile, err := os.Open("input.png")
+      	if err != nil {
+      		panic(err)
+      	}
+      	defer inFile.Close()
+
+      	img, _, err := image.Decode(inFile)
+      	if err != nil {
+      		panic(err)
+      	}
+
+      	outFile, err := os.Create("output.png")
+      	if err != nil {
+      		panic(err)
+      	}
+      	defer outFile.Close()
+
+      	writePng(outFile, img)
+      }
+
+      func writePng(w io.Writer, img image.Image) {
+      	width := uint32(img.Bounds().Dx())
+      	height := uint32(img.Bounds().Dy())
+      	writeSignature(w)
+      	writeChunkIhdr(w, width, height)
+      	writeChunkIdat(w, width, height, img)
+      	writeChunkIend(w)
+      }
+
+      func writeSignature(w io.Writer) {
+      	sig := [8]uint8{
+      		0x89,
+      		0x50, // P
+      		0x4E, // N
+      		0x47, // G
+      		0x0D, // CR
+      		0x0A, // LF
+      		0x1A, // EOF (^Z)
+      		0x0A, // LF
+      	}
+      	binary.Write(w, binary.BigEndian, sig)
+      }
+
+      func writeChunkIhdr(w io.Writer, width, height uint32) {
+      	var buf bytes.Buffer
+      	binary.Write(&buf, binary.BigEndian, width)
+      	binary.Write(&buf, binary.BigEndian, height)
+      	binary.Write(&buf, binary.BigEndian, uint8(8))
+      	binary.Write(&buf, binary.BigEndian, uint8(2))
+      	binary.Write(&buf, binary.BigEndian, uint8(0))
+      	binary.Write(&buf, binary.BigEndian, uint8(0))
+      	binary.Write(&buf, binary.BigEndian, uint8(0))
+
+      	writeChunk(w, "IHDR", buf.Bytes())
+      }
+
+      func writeChunkIdat(w io.Writer, width, height uint32, img image.Image) {
+      	var pixels bytes.Buffer
+      	for y := uint32(0); y < height; y++ {
+      		binary.Write(&pixels, binary.BigEndian, uint8(0))
+      		for x := uint32(0); x < width; x++ {
+      			r, g, b, _ := img.At(int(x), int(y)).RGBA()
+      			binary.Write(&pixels, binary.BigEndian, uint8(r))
+      			binary.Write(&pixels, binary.BigEndian, uint8(g))
+      			binary.Write(&pixels, binary.BigEndian, uint8(b))
+      		}
+      	}
+
+      	writeChunk(w, "IDAT", encodeZlib(pixels.Bytes()))
+      }
+
+      func encodeZlib(data []byte) []byte {
+      	var buf bytes.Buffer
+
+      	binary.Write(&buf, binary.BigEndian, uint8(0x78))
+      	binary.Write(&buf, binary.BigEndian, uint8(0x01))
+      	blockSize := 65535
+      	isFinalBlock := false
+      	for i := 0; !isFinalBlock; i++ {
+      		var block []byte
+      		if len(data) <= (i+1)*blockSize {
+      			block = data[i*blockSize:]
+      			isFinalBlock = true
+      		} else {
+      			block = data[i*blockSize : (i+1)*blockSize]
+      		}
+      		binary.Write(&buf, binary.BigEndian, isFinalBlock)
+      		binary.Write(&buf, binary.LittleEndian, uint16(len(block)))
+      		binary.Write(&buf, binary.LittleEndian, uint16(^len(block)))
+      		binary.Write(&buf, binary.LittleEndian, block)
+      	}
+      	binary.Write(&buf, binary.BigEndian, adler32(data))
+
+      	return buf.Bytes()
+      }
+
+      func writeChunkIend(w io.Writer) {
+      	writeChunk(w, "IEND", nil)
+      }
+
+      func writeChunk(w io.Writer, chunkType string, data []byte) {
+      	typeAndData := make([]byte, 0, len(chunkType)+len(data))
+      	typeAndData = append(typeAndData, []byte(chunkType)...)
+      	typeAndData = append(typeAndData, data...)
+
+      	binary.Write(w, binary.BigEndian, uint32(len(data)))
+      	binary.Write(w, binary.BigEndian, typeAndData)
+      	binary.Write(w, binary.BigEndian, crc(typeAndData))
+      }
+
+      var (
+      	crcTable         [256]uint32
+      	crcTableComputed bool
+      )
+
+      func makeCrcTable() {
+      	for n := 0; n < 256; n++ {
+      		c := uint32(n)
+      		for k := 0; k < 8; k++ {
+      			if (c & 1) != 0 {
+      				c = 0xEDB88320 ^ (c >> 1)
+      			} else {
+      				c = c >> 1
+      			}
+      		}
+      		crcTable[n] = c
+      	}
+      	crcTableComputed = true
+      }
+
+      func updateCrc(crc uint32, buf []byte) uint32 {
+      	if !crcTableComputed {
+      		makeCrcTable()
+      	}
+
+      	c := crc
+      	for n := 0; n < len(buf); n++ {
+      		c = crcTable[(c^uint32(buf[n]))&0xFF] ^ (c >> 8)
+      	}
+      	return c
+      }
+
+      func crc(buf []byte) uint32 {
+      	return updateCrc(0xFFFFFFFF, buf) ^ 0xFFFFFFFF
+      }
+
+      const adler32Base = 65521
+
+      func updateAdler32(adler uint32, buf []byte) uint32 {
+      	s1 := adler & 0xFFFF
+      	s2 := (adler >> 16) & 0xFFFF
+
+      	for n := 0; n < len(buf); n++ {
+      		s1 = (s1 + uint32(buf[n])) % adler32Base
+      		s2 = (s2 + s1) % adler32Base
+      	}
+      	return (s2 << 16) + s1
+      }
+
+      func adler32(buf []byte) uint32 {
+      	return updateAdler32(1, buf)
+      }
+      ]]>
+    </programlisting>
+  </section>
+  <section xml:id="references">
+    <title>参考</title>
+    <itemizedlist>
+      <listitem><link xl:href="https://www.w3.org/TR/png">Portable Network Graphics (PNG) Specification (Third Edition)</link></listitem>
+      <listitem><link xl:href="https://www.rfc-editor.org/rfc/rfc1950">ZLIB Compressed Data Format Specification version 3.3</link></listitem>
+    </itemizedlist>
+  </section>
+</article>