document

HTML5 & JavaScript side
twitter: @y_imaya

Zopfli を Emscripten で移植した際の備忘録

Emscripten で Zopfli を移植した際のメモを残します。
思ったより簡単に使えましたが、知らないとハマることも結構多かったです。

導入

自分の環境(Mac)では以下のような感じでやれば OK でした。この辺りは情報が豊富なので適当です。

  • JS Engine は NodeJS だけで良いっぽいです
  • 必要な環境は homebrew 環境なら brew install llvm だけ?
  • あとは emscripten を clone するだけ
    • clang, clang++ の位置が llvm-link と違う場合はシンボリックリンクを張るなどして合わせる

使い方

C プログラムから JS へ変換

$ emcc *.c -o hoge.js

ライブラリの場合

通常だとリンク時最適化(LTO)によりエントリポイント(main関数)から到達可能な関数以外は省略されてしまいます。
そこで emcc のオプションに -s LINKABLE=1 をつけることでリンク時最適化を無効にし、すべての関数がそのまま変換されるようにします。
なお、この状態で -O2 なども併用可能みたいなので積極的に使った方が良いです。
不要な関数の削除などは Closure Compiler での最適化時に行うこととします。

JS から C プログラムへのデータの受け渡し

Emscripten の C の関数呼び出し用のメソッドを使う場合

Emscripten で変換したコードには ccallccallFunc というメソッドがグローバルスコープに作られます。
このメソッドは何をするかというと、配列や文字列などを C の関数に渡すのは面倒な手順が必要なんですが、それを引き受けてくれます。
(何が面倒かというと、Emscripten 側の JavaScript コードでは独自にメモリ管理を行っているので、JS側からそちらのメモリアロケートやコピーを行わなくては行けなかったり、スタックの管理などやることが結構煩雑だったりします。)

ccall の使い方

ccall では C の関数名がそのまま使えます。ただし、Closure Compiler などで関数名が変わると呼べなくなったりします。

var num = ccall("hoge", "number", ["array", "string", "number", "number"], [array, string, 1, 2]);

第一引数は関数名、第二引数は戻り値の型、第三引数は引数の型、第四引数は引数となります。
ちなみにここで型として "number" というのを使っていますが、実際に有効なのは "array", "string" だけでそれ以外なら何でも数値として扱われるようです。

ccallFunc の使い方

ccall, ccallFunc は第一引数以外は同じです。
ccallFunc では第一引数が function オブジェクトとなります。

var num = ccallFunc(_hoge, "number", ["array", "string", "number", "number"], [array, string, 1, 2]);

ファイルを使う場合

  • Uint8Array などを仮想ファイルとして登録する
    • FS.createDataFile 参照
  • C のプログラム側では fread などでファイルから読み込む

JS 側で使い終わったファイルは FS.deleteFile を忘れずに。

JS 実装例
// parent, name, properties, canRead, canWrite
FS.createDataFile('/', 'data', new Uint8Array([1, 2, 3, 4]), 1, void 0);
C 実装例
int main(int argc, char argv[]) {
  const char *filename = "/data";
  FILE *fp;
  unsigned char *buffer;

  fp = fopen(filename, "r");
  buffer = malloc(1024);
  fread(buffer, 1, 1024, fp);

  return 0;
}

Closure Compiler による最適化と Export

そのままだと実行効率もファイルサイズも良くないため、Closure Compiler で最適化を行います。

実行スコープの制限

生成された JavaScript ファイルはグローバルスコープにだだ漏れなので Closure Compiler の output_wrapper でスコープを制限する。

--output_wrapper="(function() {%output%})();"

ただし、このままだと全てスコープ制限されてしまうので、必要なものはグローバルスコープに明示的に出してやる必要があります。
今回は Export 用の js ファイルを作成することにしました。
Closure Library に乗っかるなら goog.exportSymbol, 乗っかりたくない場合は window に代入すれば良いです。

// closure library
goog.exportSymbol('Hoge', Hoge);

// vanilla js
window['Hoge'] = Hoge;

キャストされた値のポインタ参照によるメモリ境界の不具合

Emscripten ではヒープ(実態は ArrayBuffer )を HEAP8, HEAP32 などでアクセスできるようにしています。
例えば、C でポインタの参照演算子を使用すると、unsigned char * のときは HEAP8, unsigned int * の時は HEAP32 で値を取得します。
ここでお気づきの方もいるかとは思いますが、ここに問題があって unsigned int * の場合は HEAP32[address >> 2] としてアクセスされるため、address が 4 の倍数でない場合はうまく動作しません。(4 で割ったあまりが切り捨てられている)

Zopfli では LZ77(LZSS) の最長一致を探す際に、unsigned char * の入力データを size_t が 8 バイトの時は size_t * にキャストして 8 バイトずつ、unsigned int * が 4 バイトの時は unsigned int * にキャストして 4 バイトずつ比較して高速化を試みています。
zopfli.js で使用している Zopfli では、ここの処理が上記の問題に当たっていたため Zopfli のこの最適化を行わないように変更してあります。

emscripten_heap_access

なお、この不具合の起こるヒープへのアクセスは emcc-s SAFE_HEAP=1 オプションをつけることで検出できます。
自分はこのオプションを知らずに自力で調べて大変苦労しました。

Zopfli を Emscripten をつかって JavaScript に移植しました

はじめに

Zopfli が公開されてから zlib.js の Deflate 処理と比較したいなーと思っていたので、 Emscripten を使って JavaScript に移植してみました。
Emscripten を使うのは初めてのためいろいろ手間取りましたが、とりあえず動作するようになったのでご報告です。

zopfli.js

というわけで、JavaScript に移植したものを以下の場所で公開しています。
もし良ければご利用ください。
使い方は zlib.js と似せています。

zlib.js を使って簡単なテストも行っていますので使用できないほどのバグはないかと思いますが、何かあればお知らせください。

デモ

せっかく移植したので、Web ブラウザでファイル圧縮するデモを作成しました。
ちょっと Zopfli の圧縮率を見てみたいという場合に便利かもしれません。
また、言うまでもありませんがかなり処理が重いので覚悟してください。

  • http://imaya.github.com/zopfli.js/
    • Web Workers, File API, Typed Array などの機能を使っていますので最近の Web ブラウザで見てください
    • 圧縮したファイルのダウンロードに download 属性を使っています

また、おまけで前回書いた PNG の IDAT を再圧縮する機能も移植しました。

おわりに

始める前は Emscripten + Zopfli とか重すぎて使い物にならないと思っていたのですが、思ったよりも高速に動作したため状況次第では使える場合もありそうな気がします。
また、現段階では Emscripten 用のパフォーマンスチューニングを行っていないので、さらに性能が向上できる可能性もあります。

Zopfli を使って PNG の再圧縮を行ってみた

はじめに

Google から Deflate 互換の圧縮アルゴリズム実装 Zopfli が公開されました。
「Deflate 互換ってどういうこと?」って方もいると思いますので簡単に説明します。

  • 符号アルゴリズムは同じ(LZSS + Huffman符号)
  • RFC では、 LZSS はこんな感じで Huffman 符号はこんな感じと大体のやり方が書かれている
  • RFC に書かれている方法とは異なる手法でより最適な LZSS + ハフマン符号化を行うのが今回の Zopfli

Kflate との比較

PNG の圧縮界隈では、一部で Kflate と呼ばれる Deflate 互換実装が圧縮効率の良いものが知られています。
(この実装は PNGOUT として PNGGauntlet や ImageOptim で使用されている)

今回は ImageOptim と比較することで Zopfli と Kflate の圧縮性能の比較を行いたいと思います。

比較方法

  1. ImageOptim で圧縮最適化を行う
  2. 最適化を行った PNG ファイルの IDAT チャンクを展開し、Zopfli で圧縮しなおした IDAT チャンクに置き換える
  3. ファイルサイズの比較を行う

また、Zopfli ではパラメータで最適化を調整できるのだが、今回の検証ではすべて 15(デフォルト値) と 1000 で行います。
コマンドラインオプションの説明ではこの数値が高い方が圧縮率が高いとされています。

結果

画像ImageOptimZopfli (i=15)Zopfli (i=1000)
617618618
953956957
1,4101,4121,412
2,2632,2392,247
4,3144,1024,103
1,631,5061,630,4751,630,471

最適化画像はこちらから確認できます

ほとんど Zopfli (i=15) が最小になっています。
iterations が大きいほど圧縮率が高くなるはずですが、あまり変わらないようです。

実装

今回の検証では以下のコードを書いて使いました。
C言語で仕事してたこともあるのに全然書けなくなってて死にたくなりました。
結構適当なのでそのまま使うのは自己責任でどうぞ。

https://gist.github.com/imaya/5064438

おわりに

というわけで、簡単にですが Zopfli を使った PNG の再圧縮を検証してみました。
Kflate が優秀なため正直あまり期待していなかったのですが、互角の性能だと言えると思います。
今後はこの実装を活用したツールも出てくるのではないでしょうか。

zlib.js で PKZIP が扱えるようになりました (0.1.4リリース)

zlib.js 0.1.4 の変更点

zlib.js 0.1.4 を先ほどリリースしました。
主要な変更点は PKZIP の圧縮、展開サポートです。
ただし、PKZIP で扱える圧縮形式は STORE (無圧縮) と DEFLATE のみとなっています。
また、暗号化は現在未対応です。

https://github.com/imaya/zlib.js

PKZIP 使用例

なにか分かりやすい使用例があった方が良いと思ったので作りました。
以下のページでデモを公開しています。 (Google Chrome 推奨)

http://imaya.github.com/demo/zip/

簡単な説明

zip_demo

ファイルを選択したあと Download ボタンをクリックすると、Web Worker 上で選択した各ファイルのダウンロードと zlib.js での圧縮を行い、メインスレッドに渡します。
メインスレッドでは Blob や createObjectURL に対応している環境や Blob URL の取り扱いができる環境では Blob URL を作成し、そうでない環境では Data URL を作成します。
現在は Google Chrome しか対応していないようですが、download 属性に対応している場合は A 要素を生成して download 属性をつけ、それにその場で作成した click イベントを dispatch することで名前を指定して保存を実現しています。
他の環境では location.href で生成した URL をわたすことでダウンロードさせています。

所感

この例では、クライアントサイドのみで ZIP ファイルのダウンロードを実現しています。
ふつう、圧縮処理というのは圧縮の負荷の方がたかいのでサーバ上でこのような処理を行うと CPU 負荷が増大してしまいます。
しかし、この処理をクライアント上で行う事によって、サーバでは静的なファイルの取り扱いのみ行えば良いのでサーバ1台あたりでさばけるユーザの数を増やす事が出来ます。

ただし、使用している API が割と新しめのものが多かったり、保存するファイル名の指定ができる環境が限られているなどの問題もあるため、現状で実用的に使用するにはそれぞれの API などの polyfill を用意するなどなんらかの工夫が必要になると思います。

追記: 2013/02/10 23:10

先ほどリリースした zlib.js 0.1.4 ですが、PKZIP 構築時の DEFLATE 圧縮する際に本来ならば圧縮前の CRC32 が必要なところを圧縮後の CRC32 を計算してしまうというバグがありました。 このバグは致命的であると判断し、問題を修正した 0.1.5 をリリースしました。 今後はそちらをお使いください。zip.min.js および PKZIP 構築時以外ではこのバグの影響はありません。

0.1.4 を使用している場合でも、いくつかのアーカイバでは CRC32 のチェックを行わないため問題の起こらないケースもあります。また、CompressionMethod に STORE (無圧縮)を指定している場合も問題ありません。

バグの報告をしてくださった @stakamur さん、どうもありがとうございました。

ファイルサイズを考慮した Canvas の保存

こんにちは、18 日以降の Graphical Web Advent Calendar が空いているので、場をつなぐ意味も込めて簡単な記事を投稿させていただきます。
先日の記事では PNG の仕様について書きましたが、その知識をさっそく生かす事ができます。

また、この記事では HTMLCanvasElement を省略して Canvas と表記させていただきます。

Canvas#toDataURL()

さて、一般的に Canvas の描画状況を保存しようと思うと、Canvas#toDataURL メソッドを使用すると思います。
ですが、このメソッドで保存された画像がどのようになっているかご存知の方はあまりいないと思います。

まずは、以下のコードで簡単な Canvas 描画を行ってみます。

function draw1(targetId) {
    var target = document.getElementById(targetId);
    var canvas = document.createElement('canvas');
    var ctx = canvas.getContext('2d');

    ctx.fillStyle = 'rgb(0, 0, 0)';
    ctx.fillRect(0, 0, canvas.width, canvas.height);
    target.src = canvas.toDataURL();
}

これを行うと、以下のような画像が表示されます。

Chrome でこの画像を保存し、IHDR を見てみると以下のようになっています。

Width300
Height150
BitDepth8
ColourTypeTruecolor_with_alpha (6)
CompressionMethodDeflate (0)
FilterMethodBasic (0)
InterlaceMethodNone (0)

使用している色が限られているのに、Truecolour with alpha で保存されています。
Canvas#toDataURL メソッドでは、全ての画像が Truecolour with alpha になってしまうようです。
これは大きな無駄となります。

たとえば WebStorage に保存するときなど、少しでもサイズを小さくするために Indexed Colour やグレイスケールで保存したい場合もあると思います。
ここから、Indexed Colour などで Canvas を保存する方法について説明します。

CanvasTool.PngEncoder

また自作ツールの宣伝で恐縮なんですが、だいぶ前に PNG エンコーダを JavaScript で自作したのでそれを利用します。
まだパフォーマンスの面などで問題はあるんですが、そこそこ使えると思います。

PNG byte-string の作成

このライブラリは以下のように使用します。

var encoder = new CanvasTool.PngEncoder(
    canvas,
    {
        bitDepth: 1,
        colourType: CanvasTool.PngEncoder.ColourType.GRAYSCALE
    }
);
var png = encoder.convert();

上記の描画例では、黒で塗りつぶしてるかそうでないかだけなので、ビット深度 1 のグレイスケール画像で保存します。
また、Indexed Colour で保存する場合は以下のようにします。

var encoder = new CanvasTool.PngEncoder(
    canvas,
    {
        bitDepth: 1,
        colourType: CanvasTool.PngEncoder.ColourType.INDEXED_COLOR
    }
);
var png = encoder.convert();

(注意: Indexed Colour では使用している色数が 2^bitDeph を超えていたら例外を投げます。色数がパレットの最大数を超えないように使用してください。)

単純に RGBA ではなく RGB で保存したい場合は以下のようにします。

var encoder = new CanvasTool.PngEncoder(
    canvas,
    {
        bitDepth: 8,
        colourType: CanvasTool.PngEncoder.ColourType.TRUECOLOR
    }
);
var png = encoder.convert();

ちなみにこのライブラリでは Truecolour などで bitDepth: 16 も指定できますが、元の色が bitDepth:8 のため意味はないでしょう。

Data URL への変換

変数 png は ByteString なので、これを DataURL で使用するには Base64 形式にエンコードします。(そのままで使える場合もあるのですが、ここでは省略します)
ByteString から Base64 へのエンコードは window.btoa が使える環境ではそれを使うのが最も簡単で高速です。
window.btoa が使えない環境では polyfill を使うのが良いと思います。

window.btoa を使うと、以下のようになります。

var dataUrl = 'data:image/png;base64,' + window.btoa(png);

動作例

実際に前述のコードをそれぞれ動かしてみます。

ビット深度 1 のグレイスケール画像

ビット深度 1 の Indexed Colour 画像

ビット深度 8 の Truecolour 画像

比較

生成した画像をダウンロードしてファイルサイズを比較してみます。( Google Chrome 23 で確認)

Canvas#toDataURL()GrayscaleIndexed ColourTruecolour
1,869106136543

一般的な画像での比較 (16:00追加)

例として使用している Canvas が適当すぎるので、一応きちんとした画像でも比較してみたいと思います。以下の画像を Canvas に drawImage して、それを保存します。

ubunchu01_01_small
  • 架空線 – AERIAL LINE - : 第1話 「うぶんちゅがやって来た!」:
    http://www.aerialline.com/comics/ubunchu/episode01
  • © 瀬尾浩史
  • 元の画像から 1/4 サイズにして 256 色に減色しています
  • いつもお世話になっております

Canvas#toDataURL()

CanvasTool.PngEncoder

Chrome 23 で試したところ、以下のような結果になりました。

Canvas#toDataURL()CanvasTool.PngEncoder
処理時間32 ms1,614 ms
サイズ161,78761,006

処理時間がかかりすぎていますが、CanvasTool.PngEncoder では WebWorkers でも(少し手を加えるだけで)利用可能なので、タイムアウトする可能性がある場合は WebWorkers の利用を考えてみるのも良いかもしれません。

また、今回ためした結果は PC なので Canvas#toDataURL メソッドは割と速く終わっていますが、モバイルなどでは毎フレーム実行するなどの激しい操作はまだ難しいと思います。

おわりに

いかがでしたでしょうか。
Canvas#toDataURL メソッドでは指定できない、PNG の細かい設定を行う事によりかなりの容量の節約ができるようになります。
今回はライブラリを使いましたが、簡単なPNGであれば自作も楽ですのでぜひ挑戦してみてください。

また、自力でエンコードは圧縮処理の都合上どうしても遅くなってしまうので、速さとサイズ、どちらを優先するか見極めて調整することが必要となります。

以上、何かの参考になれば幸いです。

記事検索
最新コメント
最新トラックバック
カテゴリ別アーカイブ
タグクラウド
QRコード
QRコード
  • ライブドアブログ