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ファイルであることの確認とファイルの破損の検出のためのもの

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ファイルの生成に全く同じものを使ったのでこれを流用した

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

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で表現

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で列挙
順番がそのままインデックス番号になる

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に書けるモードにおいては使用できない

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チャンクを含めることができる
詳しくは後述

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 *

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

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つの非圧縮ブロックに分けて入れる例

00 01 00 fe ff 01
01 02 00 fd ff 02 03
   len-- nlen- data-

adler32 (フッタ)

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

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にかける前のデータ
圧縮効率を高めるため行毎にフィルターを定義できる

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

0123
4567

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

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

になる

PNGを読む

GIMPにカラーモードをインデックスにした画像を圧縮レベル0のPNGで吐かせた
圧縮レベル0はdeflateの非圧縮ブロックを使う模様

PNGを書く

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

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やPNG file chunk inspectorを使って確認すると良い

性能

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

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

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

実行結果

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

drawもcdrawもObjectURLを使った結果

結論

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

成果物

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

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

参考資料