From 4f46d262e6967c9c638b40f3b0246d21b7a9b9dc Mon Sep 17 00:00:00 2001 From: nsfisis Date: Wed, 9 Apr 2025 20:29:15 +0900 Subject: feat(blog/nuldoc): rebuild --- .../index.html | 190 +++++++-------------- 1 file changed, 65 insertions(+), 125 deletions(-) (limited to 'vhosts/blog/public/posts/2023-04-01/implementation-of-minimal-png-image-encoder') diff --git a/vhosts/blog/public/posts/2023-04-01/implementation-of-minimal-png-image-encoder/index.html b/vhosts/blog/public/posts/2023-04-01/implementation-of-minimal-png-image-encoder/index.html index 11831bdf..502a7e3a 100644 --- a/vhosts/blog/public/posts/2023-04-01/implementation-of-minimal-png-image-encoder/index.html +++ b/vhosts/blog/public/posts/2023-04-01/implementation-of-minimal-png-image-encoder/index.html @@ -52,51 +52,42 @@
-

はじめに

+

はじめに

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

-
-

PNG ファイルの基本構造

+

PNG ファイルの基本構造

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

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

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

-

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

-
-

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

+

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

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

- 
package main
 
@@ -137,59 +128,46 @@
 	writeChunkIend(w)
 }
-

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

-
-

PNG signature

+

PNG signature

- PNG signature は、PNG 画像の先頭に固定で付与されるバイト列で、8 バイトからなる。 + 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)
-

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

-

- writeSignature の実装はこちら: + writeSignature の実装はこちら:

- 
import "encoding/binary"
 
@@ -207,40 +185,32 @@
 	binary.Write(w, binary.BigEndian, sig)
 }
-

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

-
-

Chunk の構造

+

Chunk の構造

- IHDR chunk に進む前に、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 バイト整数)
-

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

- 
var (
 	crcTable         [256]uint32
@@ -278,11 +248,9 @@
 	return updateCrc(0xFFFFFFFF, buf) ^ 0xFFFFFFFF
 }
-

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

- 
func writeChunk(w io.Writer, chunkType string, data []byte) {
 	typeAndData := make([]byte, 0, len(chunkType)+len(data))
@@ -294,91 +262,91 @@
 	binary.Write(w, binary.BigEndian, crc(typeAndData))
 }
-

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

-

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

-
-

IHDR chunk

+

IHDR chunk

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

-
  1. 画像の幅 (符号なし 4 バイト整数)
    2. -
  2. 画像の高さ (符号なし 4 バイト整数)
    3. -
  3. - ビット深度 (符号なし 1 バイト整数) +

    + ビット深度 (符号なし 1 バイト整数) +

    • 1 色に使うビット数。1 ピクセルに 24 bit 使う truecolor 画像では 8 になる
    4. -
  4. - 色タイプ (符号なし 1 バイト整数) +

    + 色タイプ (符号なし 1 バイト整数) +

    • 0: グレースケール
      • -
    • 2: Truecolor (今回はこれに決め打ち)
      • -
    • 3: パレットのインデックス
      • -
    • 4: グレースケール + アルファ
      • -
    • 6: Truecolor + アルファ
    5. -
  5. - 圧縮方式 (符号なし 1 バイト整数) +

    + 圧縮方式 (符号なし 1 バイト整数) +

      - PNG の仕様書に 0 しか定義されていないので 0 で固定 +
    • + PNG の仕様書に 0 しか定義されていないので 0 で固定 +
    6. -
  6. - フィルタ方式 (符号なし 1 バイト整数) +

    + フィルタ方式 (符号なし 1 バイト整数) +

      - PNG の仕様書に 0 しか定義されていないので 0 で固定 +
    • + PNG の仕様書に 0 しか定義されていないので 0 で固定 +
    7. -
  7. - インターレース方式 (符号なし 1 バイト整数) +

    + インターレース方式 (符号なし 1 バイト整数) +

      - 今回はインターレースしないので 0 +
    • + 今回はインターレースしないので 0 +
-

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

- 
import "bytes"
 
@@ -396,45 +364,36 @@
 }
-
-

IDAT chunk

+

IDAT chunk

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

-
-

Zlib

+

Zlib

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

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

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

-

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

- 
const adler32Base = 65521
 
@@ -453,37 +412,29 @@
 	return updateAdler32(1, buf)
 }
-

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

-

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

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

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

- 
func encodeZlib(data []byte) []byte {
 	var buf bytes.Buffer
@@ -511,21 +462,17 @@
 }
-
-

画像データ

+

画像データ

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

-

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

-

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

- 
func writeChunkIdat(w io.Writer, width, height uint32, img image.Image) {
 	var pixels bytes.Buffer
@@ -544,17 +491,14 @@
-
-

IEND chunk

+

IEND chunk

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

-

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

- 
func writeChunkIend(w io.Writer) {
 	writeChunk(w, "IEND", nil)
@@ -562,13 +506,11 @@
-
-

おわりに

+

おわりに

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

- 
package main
 
@@ -746,14 +688,12 @@
 }
-
-

参考

+

参考