JSでPNGファイルを「直接」生成する

jsでpngを作りたいときcanvasなどのAPIを使う方法が一般的
しかし配列にあるデータからpngを作りたい場合
`canvasを用意→ループでfillRect→toBlob`
の手順を踏む必要があり簡単な画像の場合はコストが高くつく
今回はpngの構造を把握してバイナリを直接書くことでpngファイルを生成してみる

# 動機

Workerスレッドで計算したデータを最終的にimgタグで画面に表示したい
OffscreenCanvasは使いたくないのでImageDataでメインスレッドに転送してcanvasに描いてimgに起こしていた
これではWorkerスレッドの意味がないのでWorkerスレッドでurlまで完結する画像生成が欲しかった

WorkerスレッドでOffscreenCanvasを使わずにPNGを描けたらいいよねということ

# PNGを知る

## PNGとは

可逆圧縮を用いた画像フォーマット
可逆圧縮にはdeflateを用いている

## ファイル構造

- 基本的にビッグエンディアン
- ファイル構造
    - ファイルヘッダ
    - チャンク
    - チャンク
    - ...
    - チャンク

### ファイルヘッダ

8byteの固定のデータ
PNGファイルであることの確認とファイルの破損の検出のためのもの

```text
89 50 4e 47 0d 0a 1a 0a
```

### チャンク

ファイルヘッダ以外のすべてのデータはチャンクの中に存在する
チャンクは数種類あるが構造は共通

- length ( 4 byte )
    - dataの長さをビッグエンディアンで
- chunk type ( 4 byte )
    - IHDR, IDATなどのチャンク名
- data ( n byte )
    - 任意のデータ
- CRC32 ( 4 byte )
    - データの破損を検出するためのデータ
    - chunk type + dataのCRC32をビッグエンディアンで
    - zipファイルの生成に全く同じものを使ったのでこれを流用した

https://qiita.com/McbeEringi/items/5acc1f940ff7504f7e16


代表的なチャンクを以下に挙げる
幾つかは設置が必須のチャンク( * )であり必ず含める必要がある

#### IHDR *

設置が必須のチャンク
画像の基本的な情報を格納する

- Width ( 4 bytes )
    - 画像の幅
- Height ( 4 bytes )
    - 画像の高さ
- Bit depth ( 1 byte )
    - 1ピクセルを表すのに用いるビット数を表す
- Color type ( 1 byte )
    - 色の扱い方
- Compression method ( 1 byte )
    - 常に0
- Filter method ( 1 byte )
    - 常に0
- Interlace method ( 1 byte )
    - インターレス(Adam7)を使用する(1)か否(0)か

Color typeとBit depthは使用できる値とその組み合わせが決まっている
| Color type | Bit depth |機能|説明|
|:-:|:-:|:-:|:-:|
| 0 | 1,2,4,8,16 | グレースケール|ピクセルの明るさを{Bit depth}bitで表現 |
| 2 | 8,16 | TrueColor|ピクセルの色(RGB)を{Bit depth}*3byteで表現 |
| 3 | 1,2,4,8 | インデックス|パレット(PLTEチャンク)で定義した色を参照 |
| 4 | 8,16 | アルファ付き グレースケール | ピクセルの明るさと透明度(GA)を{Bit depth}*2bitで表現 |
| 6 | 8,16 | アルファ付き TrueColor |ピクセルの色と透明度(RGBA)を{Bit depth}*4byteで表現 |

```text
00 00 00 0d 49 48 44 52 0 0 0 20 0 0 0 20 2 3 0 0 0 0e 14 92 67
length----- chunk_type- width--- height-- - - - - - CRC32------
13          I  H  D  R  32       32       2bit indexed
```

#### PLTE

インデックスモードで用いる色をRGBで列挙
順番がそのままインデックス番号になる

```text
00 00 00 03 50 4c 54 45 ff 00 ff 34 e0 e6 ba
length----- chunk_type- data---- CRC32------
3           P  L  T  E  #ff00ff
{0:#ff00ff}なパレットの定義
```

#### tRNS

透明度を指定したい場合に使う
グレースケールモードとTrueColorモードにおいてはここで指定した色が透明になる
インデックスモードにおいては透明度を列挙することで各インデックス番号における透明度を指定できる
透明度をIDATに書けるモードにおいては使用できない

```text
00 00 00 01 74 52 4e 53 80 ad 5e 5b 46
length----- chunk_type- da CRC32------
1           t  R  N  S  
インデックス番号0の色の透明度を0x80に設定
```

#### IDAT *

設置が必須のチャンク
zlibで圧縮した画像データを持つチャンク
一つのファイルに複数個のIDATチャンクを含めることができる
詳しくは後述

```text
00 00 00 06 49 44 41 54 00 01 23 00 45 67 e1 c9 7f 1b
length----- chunk_type- data------------- CRC32------
6           I  D  A  T
```

#### IEND *

設置が必須のチャンク
ファイルの終端であることを示すチャンク
これ以降のデータは読み込まれない
データは常に空でありどのファイルでも以下の通り

```text
00 00 00 00 49 45 4e 44 ae 42 60 82
length----- chunk_type- CRC32------
0           I  E  N  D
```

## zlib

zlibはdeflate圧縮アルゴリズムを用いたライブラリ + ヘッダとフッタの定義
吐かれるデータはヘッダ+deflateのブロックたち+フッタである

### ヘッダ

- CMF ( 1 byte )
    - `CMF=(CINFO&15)<<4|(CM&15)`
    - CINFO ( 4 bits )
        - 圧縮情報
        - deflateで使った窓のサイズを0~7であらわす
    - CM ( 4 bits )
        - 圧縮方式
        - 8がdeflateを表す
- FLG ( 1 byte )
    - `FLG=(FLEVEL&3)<<6|(FDICT&1)<<5|(FCHECK&31)`
    - FLEVEL ( 2 bits )
        - 圧縮に使ったアルゴリズムについて
        - 圧縮速度が`速 0~3 遅`
        - 圧縮結果が`大 0~3 小`
    - FDICT ( 1 bit )
        - プリセット辞書を使う(1)か否(0)か
    - FCHECK ( 5 bits )
        - データ破損チェック用
        - `(CMF<<8|FLG)%31==0`になるような数を入れる
- DICTID ( 4 bytes )
    - `FDICT==1`の場合に出現

今回は非圧縮ブロックを使うのでヘッダは`08 1d`になる

### deflate

圧縮したデータはPNGのチャンクと同じようにブロックという単位に区切られる
ブロックには数種類あり生のデータをそのまま入れられる非圧縮ブロックが存在する

#### 非圧縮ブロック

- flag ( 1 byte )
    - `flag=(BTYPE&3)<<1|(BFINAL&1)`
    - BTYPE ( 2 bits )
        - 非圧縮ブロックは0
    - BFINAL ( 1bit )
        - このブロックが最後のブロックの場合に1
- len  ( 2 bytes )
    - dataの長さを**リトルエンディアン**で
- nlen ( 2 bytes )
    - lenのビット反転
- data ( n bytes )
    - ここにデータが入る

`01 02 03`を2つの非圧縮ブロックに分けて入れる例
```text
00 01 00 fe ff 01
01 02 00 fd ff 02 03
   len-- nlen- data-
```

### adler32 (フッタ)

役割も長さもCRC32と同じ
圧縮前のデータから計算した結果をビッグエンディアンで格納
wikipediaを参考に実装した

```js
adler=data=>{
    let a=1,b=0,len=data.length,tlen,i=0;
    while(len>0){
        len-=(tlen=Math.min(1024,len));
        do{b+=(a+=data[i++]);}while(--tlen);
        a%=65521;b%=65521;
    }
    return(b<<16)|a;
}
```

## PNGの画像データ

deflateにかける前のデータ
圧縮効率を高めるため行毎にフィルターを定義できる

https://www.w3.org/TR/PNG-Filters.html

0が何もしていない生のデータを表す
フィルターの種類を表す数は行の先頭に付加する
データはIHDRで定義した通りに書く
例えば1pxあたり8bitでインデックス番号が

```text
0123
4567
````

の画像のデータはフィルター0を使用すると

```text
0 0 1 2 3 0 4 5 6 7
- ------- - -------
```

になる

# PNGを読む
GIMPにカラーモードをインデックスにした画像を圧縮レベル0のPNGで吐かせた
圧縮レベル0はdeflateの非圧縮ブロックを使う模様
![GIMPに吐かせたPNGのバイナリ解説](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/479627/46d672d5-3fd9-7da0-6711-f727bace6567.jpeg)

# PNGを書く

32*32ピクセルにCMYKをランダムにちりばめた画像を持つimgタグのPromiseを返すサンプル
asyncなのはimgタグの読み込み部分のみ

```js
const draw=()=>new Promise(f=>Object.assign(new Image(),{
    onload(){f(this);},
    src:((
        // CRC32
        crct=[...Array(256)].map((_,n)=>[...Array(8)].reduce(c=>(c&1)?0xedb88320^(c>>>1):c>>>1,n)),
        crc=(buf,crc=0)=>~buf.reduce((c,x)=>crct[(c^x)&0xff]^(c>>>8),~crc),
        // adler32
        adler=data=>{let a=1,b=0,len=data.length,tlen,i=0;while(len>0){len-=(tlen=Math.min(1024,len));do{b+=(a+=data[i++]);}while(--tlen);a%=65521;b%=65521;}return(b<<16)|a;},
        // ヘルパー
        be4=x=>[x>>>24&255,x>>>16&255,x>>>8&255,x>>>0&255],// 32bit -> ビッグエンディアン4bytes
        arr=x=>x.match(/[\da-f]{2}/g).map(x=>parseInt(x,16)),// hex文字列 -> 配列
        chunk=x=>[...be4(x.length-4),...x,...be4(crc(x))],// データ -> チャンク
        
        // 2bit*32*32のPNG画像データを用意
        img=[...Array(32)].flatMap(_=>[
            0,// フィルター
            ...[...Array(32/(8/2))].map(_=>Math.random()*255|0)// ランダムに
        ])
    )=>'data:image/png;base64,'+btoa(String.fromCharCode(
        ...arr('89 50 4e 47 0d 0a 1a 0a'),// PNGヘッダ
        ...chunk(arr('49 48 44 52  00 00 00 20 00 00 00 20  02 03 00 00 00')),// IHDR 32*32 2bit indexed
        ...chunk(arr('50 4c 54 45  00 ff ff  ff 00 ff  ff ff 00  00 00 00')),// PLTE CMYK
        ...chunk([// IDAT "IDAT" + zlib * 非圧縮ブロック
            0x49,0x44,0x41,0x54,
            0x08,0x1d, 1, ...(_=>[_>>>0&255,_>>>8&255,~_>>>0&255,~_>>>8&255])(img.length),
            ...img, ...be4(adler(img))
        ]),
        ...chunk(arr('49 45 4e 44'))// IEND
    )))()
}));
```

壊れていますと言われた場合は[pngcheck](http://www.libpng.org/pub/png/apps/pngcheck.html
)や[PNG file chunk inspector](https://www.nayuki.io/page/png-file-chunk-inspector)を使って確認すると良い

# 性能

canvasとOffscreenCanvasと今回のPNG生成をメインスレッドで1000*10回実行して比較
OffscreenCanvasにはtoDataURLが存在しないのでtoBlobで代用

```js
const
ctx=Object.assign(document.createElement('canvas'),{width:32,height:32}).getContext('2d'),
octx=new OffscreenCanvas(32,32).getContext('2d'),

plte=[[0,255,255,255],[255,0,255,255],[255,255,0,255],[0,0,0,255]],
cdraw=(
    img=[...Array(32)].flatMap(_=>[...Array(32)].flatMap(_=>plte[Math.random()*4|0]))
)=>new Promise(f=>Object.assign(new Image(),{
    onload(){f(this);},
    src:(
        ctx.putImageData(new ImageData(new Uint8ClampedArray(img),32),0,0),
        ctx.canvas.toDataURL()
    )
})),
ocdraw=(
    img=[...Array(32)].flatMap(_=>[...Array(32)].flatMap(_=>plte[Math.random()*4|0])),
    url
)=>new Promise(async f=>Object.assign(new Image(),{
    onload(){URL.revokeObjectURL(url);f(this);},
    src:(
        octx.putImageData(new ImageData(new Uint8ClampedArray(img),32),0,0),
        url=URL.createObjectURL(await octx.canvas.convertToBlob())
    )
}));

await[...Array(10)].reduce(a=>(async(
    n=[...Array(1000)],
    t0,
    log=x=>console.log(x,-t0+(t0=performance.now()))
)=>(
    await a,t0=performance.now()
    await Promise.all(n.map(_=> cdraw())),log('canvas'),
    await Promise.all(n.map(_=>ocdraw())),log('OffscreenCanvas'),
    await Promise.all(n.map(_=>  draw())),log('png asm')
))());
```

CPU: N100, RAM: 16GB
Windows11 Firefox 117.0.1 64bit

の環境で上記コードを実行した

<details>
<summary>実行結果</summary>

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/479627/29fcce03-89b5-61de-5163-f653fb93bc8c.png)

</details>

dataurlとObjectURLの差を確認するため全てObjectURLを使った場合も測定した

<details>
<summary>drawもcdrawもObjectURLを使った結果</summary>

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/479627/1e8f5a2b-9bb2-70a3-8d4b-400c2ee22556.png)

</details>

# 結論

- 今回のPNG生成は
    - canvasに対して約5倍高速
    - OffscreenCanvasに対して約1.5倍高速
- 知見
    - PNGエンコーダに圧縮は必須でない
        - 意外と楽に実装できた
    - OffscreenCanvasはそこそこ速い
        - canvasとかなりの差がある
        - メインスレッドでも


# 成果物
Minecraft BEのスライムチャンクを計算するやつ
今回の手法のおかげで2048**2=4194304チャンクの計算結果を2秒弱(iPad Air5)で一度に表示できるようになった

https://mcbeeringi.github.io/apps/mc/slime.html

スライムチャンクをそんなに一度に計算してどうするんだ
→ ベンチマークにする

# 参考資料

https://www.w3.org/TR/png/

http://www.libpng.org/pub/png/apps/pngcheck.html

https://ja.wikipedia.org/wiki/Portable_Network_Graphics

https://ja.wikipedia.org/wiki/Adler-32

https://www.setsuki.com/hsp/ext/png.htm

https://zenn.dev/yohhoy/articles/exploding-pngfile

https://kimaguresoft.blogspot.com/2019/03/png1.html

https://darkcrowcorvus.hatenablog.jp/entry/2017/01/09/014407

https://datatracker.ietf.org/doc/html/rfc1950

https://datatracker.ietf.org/doc/html/rfc1951

https://github.com/imaya/zlib.js/blob/develop/src/deflate.js