From a84908b7e8a0e2423afd6b836eccf27a420270b4 Mon Sep 17 00:00:00 2001 From: nsfisis Date: Wed, 20 Sep 2023 19:56:52 +0900 Subject: feat(blog/nuldoc): change content format from DocBook to NulDoc --- ...mplementation-of-minimal-png-image-encoder.ndoc | 604 +++++++++++++++++++++ 1 file changed, 604 insertions(+) create mode 100644 vhosts/blog/content/posts/2023-04-01/implementation-of-minimal-png-image-encoder.ndoc (limited to 'vhosts/blog/content/posts/2023-04-01/implementation-of-minimal-png-image-encoder.ndoc') diff --git a/vhosts/blog/content/posts/2023-04-01/implementation-of-minimal-png-image-encoder.ndoc b/vhosts/blog/content/posts/2023-04-01/implementation-of-minimal-png-image-encoder.ndoc new file mode 100644 index 00000000..2e288137 --- /dev/null +++ b/vhosts/blog/content/posts/2023-04-01/implementation-of-minimal-png-image-encoder.ndoc @@ -0,0 +1,604 @@ +--- +[article] +title = "PNG 画像の最小構成エンコーダを実装する" +description = "PNG 画像として valid な範囲で最大限手抜きしたエンコーダを書く。" +tags = [] + +[[article.revisions]] +date = "2023-04-01" +remark = "公開" +--- +
+
+ はじめに +

+ この記事では、PNG 画像として valid な範囲で最大限手抜きしたエンコーダを書く。 + PNG 画像に対応したビューアであれば読み込めるが、圧縮効率については一切考えない。 + また、実装には Go 言語を使うが、Go の標準ライブラリにあるさまざまなアルゴリズム (PNG 画像に関係する範囲だと、zlib や CRC32、Adler-32 など) は使わない。 +

+
+
+ PNG ファイルの基本構造 +

+ PNG ファイルの基本構造は次のようになっている。 +

+
    +
  1. PNG signature
    2. +
  2. IHDR chunk
    3. +
  3. 任意個の chunk
    4. +
  4. IEND chunk
    5. +
+

+ Chunk には画像データを入れる IDAT chunk、パレットデータを入れる PLTE chunk、テキストデータを入れる tEXt chunk などがあるが、 + 今回は最小構成ということで IDAT chunk (と IHDR chunk と IEND chunk) のみを用いる。 +

+

+ 次節で、それぞれの具体的な構造を確認しつつ実装していく。 +

+
+
+ PNG のエンコーダを実装する +

+ 以下のソースコードをベースにする。 + 今回 PNG のデコーダは扱わないので、読み込みには Go の標準ライブラリ image/png を用いる。 +

+ + + +

+ 以降は、writeSignature や writeChunkIhdr などを実装していく。 +

+
+ PNG signature +

+ PNG signature は、PNG 画像の先頭に固定で付与されるバイト列で、8 バイトからなる。 +

+
    +
  1. 0x89
    2. +
  2. 0x50 (ASCII コードで「P」)
    3. +
  3. 0x4E (ASCII コードで「N」)
    4. +
  4. 0x47 (ASCII コードで「G」)
    5. +
  5. 0x0D (ASCII コードで CR)
    6. +
  6. 0x0A (ASCII コードで LF)
    7. +
  7. 0x1A (ASCII コードで EOF)
    8. +
  8. 0x0A (ASCII コードで LF)
    9. +
+

+ CRLF や LF は、送信中に改行コードの変換が誤っておこなわれていないかどうかを検知するのに使われる。 +

+

+ writeSignature の実装はこちら: +

+ + + +

+ encoding/binary パッケージの binary.Write を使い、固定の 8 バイトを書き込む。 +

+
+
+ Chunk の構造 +

+ IHDR chunk に進む前に、chunk 一般の構造を確認する。 +

+
    +
  1. Length: chunk data のバイト長 (符号なし 4 バイト整数)
    2. +
  2. Chunk type: chunk の種類を示す 4 バイトからなる名前
    3. +
  3. Chunk data: 実際のデータ。0 バイトでもよい
    4. +
  4. CRC: chunk type と chunk data の CRC (符号なし 4 バイト整数)
    5. +
+

+ CRC (Cyclic Redundancy Check) は誤り検出符号の一種。Go 言語では hash/crc32 パッケージにあるが、今回はこれも自前で実装する。PNG の仕様書に C 言語のサンプルコードが載っている (D. Sample CRC implementation) ので、これを Go に移植する。 +

+ + > 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 + } + ]]> + +

+ できた crc 関数を使って、chunk 一般を書き込む関数も用意しておこう。 +

+ + + +

+ 仕様どおり、chunkType と data から CRC を計算し、data の長さと合わせて書き込んでいる。 + PNG では基本的に big endian を使うことに注意する。 +

+

+ 準備ができたところで、具体的な chunk をエンコードしていく。 +

+
+
+ IHDR chunk +

+ IHDR chunk は最初に配置される chunk である。次のようなデータからなる。 +

+
    +
  1. 画像の幅 (符号なし 4 バイト整数)
    2. +
  2. 画像の高さ (符号なし 4 バイト整数)
    3. +
  3. + ビット深度 (符号なし 1 バイト整数) +
      +
    • 1 色に使うビット数。1 ピクセルに 24 bit 使う truecolor 画像では 8 になる
      • +
    +
    4. +
  4. + 色タイプ (符号なし 1 バイト整数) +
      +
    • 0: グレースケール
      • +
    • 2: Truecolor (今回はこれに決め打ち)
      • +
    • 3: パレットのインデックス
      • +
    • 4: グレースケール + アルファ
      • +
    • 6: Truecolor + アルファ
      • +
    +
    5. +
  5. + 圧縮方式 (符号なし 1 バイト整数) +
      + PNG の仕様書に 0 しか定義されていないので 0 で固定 +
    +
    6. +
  6. + フィルタ方式 (符号なし 1 バイト整数) +
      + PNG の仕様書に 0 しか定義されていないので 0 で固定 +
    +
    7. +
  7. + インターレース方式 (符号なし 1 バイト整数) +
      + 今回はインターレースしないので 0 +
    +
    8. +
+

+ 今回ほとんどのデータは決め打ちするので、データに応じて変わるのは width と height だけになる。コードは次のようになる。 +

+ + + +
+
+ IDAT chunk +

+ IDAT chunk は、実際の画像データが格納された chunk である。IDAT chunk は deflate アルゴリズムにより圧縮され、zlib 形式で格納される。 +

+
+ Zlib +

+ まずは zlib について確認する。おおよそ次のような構造になっている。 +

+
    +
  1. 固定で 0x78 (符号なし 1 バイト整数)
    2. +
  2. 固定で 0x01 (符号なし 1 バイト整数)
    3. +
  3. データ
    4. +
  4. データの Adler-32
    5. +
+

+ 最初の 2 バイトにも意味はあるが、PNG では固定で構わない。 +

+

+ Adler-32 も CRC と同じく誤り検出符号である。こちらも zlib の仕様書に C 言語でサンプルコードが記載されている (9. Appendix: Sample code) ので、Go に移植する。 +

+ + > 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) + } + ]]> + +

+ 「データ」の部分には圧縮したデータが入るのだが、真面目に deflate アルゴリズムを実装する必要はない。Zlib には無圧縮のデータブロックを格納することができるので、これを使う。本来は、データの圧縮効率の悪いランダムなデータをそのまま格納するためのものだが、今回は deflate の実装をサボるために使う。 +

+

+ 1 つの無圧縮ブロックには 65535 (216 - 1) バイトまで格納できる。それぞれのブロックは次のような構成になっている。 +

+
    +
  1. 最終ブロックなら 1、そうでなければ 0 (符号なし 1 バイト整数)
    2. +
  2. ブロックのバイト長 (符号なし 2 バイト整数)
    3. +
  3. ブロックのバイト長の 1 の補数、あるいはビット反転 (符号なし 2 バイト整数)
    4. +
  4. データ (最大 65535 バイト)
    5. +
+

+ 実際にこの手抜き zlib を実装したものがこちら: +

+ + + +
+
+ 画像データ +

+ では次に、zlib 形式で格納するデータを用意する。PNG 画像は次のような順にスキャンする。 + 画像の左上のピクセルから同じ行を横にスキャンしていき、一番右まで到達したら次の行の左に向かう。 + 右下のピクセルまで行けば終わり。要は Z 字型に進んでいく。 +

+

+ また、それぞれの行の先頭には、圧縮のためのフィルタタイプを指定する。 + ただ、今回はその実装を省略するために、常にフィルタ 0 (何も加工しない) を使う。 +

+

+ 先ほどの encodeZlib も使って実際に実装したものがこちら: +

+ + + +
+
+
+ IEND chunk +

+ 最後に IEND chunk を書き込む。これは PNG 画像の最後に配置される chunk で、PNG のデコーダはこの chunk に出会うとそこでデコードを停止する。 +

+

+ 特に追加のデータはなく、必要なのは chunk type の IEND くらいなので実装は簡単: +

+ + + +
+
+
+ おわりに +

+ 最後に全ソースコードを再掲しておく。 +

+ + > 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) + } + ]]> + +
+
+ 参考 + +
+
-- cgit v1.2.3-70-g09d2