document

はじめに

JavaScript でバイナリから文字列を取り出したら Shift JIS だったなんてことよくありますよね。
そういう文字列もさっと表示したいことがあります。

読み込む方法はいくつかある

これらの文字列を読み込む方法はいくつかあって、自分が把握してるだけでも以下のものがあります。

1. Shift JIS と UTF-16 の対応表をつくる
   • ぽりごんさんの文字コード変換ライブラリ
2. Blob, File API を使って読み込む
   • 右京さんの javascriptのnative APIで任意の文字コードからutf8に変換
3. script, Data URL を使って変換

1, 2 の方法についてはそれぞれ解説や実装があるのですが、3 の方法については見当たらなかったので説明してみます。

準備

念のため 2 段階で文字コードの識別を試みます。

script 要素の charset 属性

script 要素には charset 属性というのがあって、この属性がセットされていた場合、指定された文字コードとして読み込みます。
仕様では Scripts in HTML documents(HTML4) や Scripts in HTML documents にかかれています。

Data URL

Data URL は The "data" URL scheme ( RFC2397 ) で定義されている、データを Web ページに埋め込むための URI Scheme です。
フォーマットはシンプルで

data:[<mediatype>][;base64],<data>

となっています。
このフォーマットの <mediatype> は以下のようなものになっています。

mediatype  := [ type "/" subtype ] *( ";" parameter )

ここから少し仕様を追っていくのが大変なので、簡単に説明すると mediatype には text/plain のような MIME Type だけではなく、text/plain; charset=Shift_JIS のように文字コードを指定する事ができます。
parameter の attribute と value について詳しく知りたい方は RFC2045 を参照してください。
ちなみに mediatype が指定されていない場合のデフォルト値は text/plain; charset=us-ascii となります。

変換を行う

script 要素と Data URL について説明したので、ここからそれを使って以下のように文字コードを変換します。

1. 変換前の文字列を文字列リテラルの文字列に変換する ( hoge という文字を 'hoge' という文字列に変換)
   • いくつかの文字は文字列リテラルとして正しくなるようにエスケープしてやる
     • バックスラッシュは \\
     • クオートは \x27
     • LF は \x0a
     • CR は \x0d
2. 変換後の文字列を受ける callback function を作る
   • 例えば以下のような感じです

   • function Callback(str) {
     console.log(str);
     }

3. 生成された文字列リテラルを引数にして callback function の呼び出しを行うスクリプト文字列を生成する

   • "Callback('hoge');"

4. 生成されたスクリプト文字列を Data URL に変換して script 要素で呼び出す
   • もちろん、Data URL と script は charset 指定する

欠点

script 要素の生成と追加を行っているので非同期でしか使えません。
同期で変換したい場合はぽりごんさんのライブラリを使うと良いと思います。

おまけ

これらをまとめてやってくれる azoth.js というのを作りました。
自分でやるのめんどくさいという人はどうぞ。

• azoth.js

ちなみに JavaScript の文字列 (UTF-16) から UTF-8 への変換と、UTF-8 からの変換は、escape/unescape, encodeURIComponent/decodeURIComponent で行う事ができるのでライブラリが必要なかったりします。

おわりに

一応簡単なテストなどもしていますが、もし考慮漏れなどありましたらお知らせください。

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 で変換したコードには ccall と ccallFunc というメソッドがグローバルスコープに作られます。
このメソッドは何をするかというと、配列や文字列などを 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 のこの最適化を行わないように変更してあります。

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

はじめに

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

zopfli.js

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

• https://github.com/imaya/zopfli.js

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

デモ

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

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

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

おわりに

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

はじめに

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 で行います。
コマンドラインオプションの説明ではこの数値が高い方が圧縮率が高いとされています。

結果

画像	ImageOptim	Zopfli (i=15)	Zopfli (i=1000)
	617	618	618
	953	956	957
	1,410	1,412	1,412
	2,263	2,239	2,247
	4,314	4,102	4,103
	1,631,506	1,630,475	1,630,471

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

• イラスト画像: 架空線 – AERIAL LINE - : 第1話 「うぶんちゅがやって来た！」:
  http://www.aerialline.com/comics/ubunchu/episode01
• © 瀬尾浩史

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

実装

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

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

おわりに

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