document

HTML5 & JavaScript side
twitter: @y_imaya

#JSオジサンで Source Map について話してきました

JSオジサンという名前からしてダメそうな感じのイベントでLTしてきました。 内容については azu さんのまとめ(→ JSオジサンで現在のJavaScript ASTについて発表してきた )を見ると良いと思います。

LT5分なのに時間オーバーしたあげく枠のおかわりまでしてすみませんでした…。

おっさんたちが集まってわいわいLTするゆるふわイベントだと思って、
最近ちょっと触った Source Map の話でもするかーと思って申し込んだら予想外にガチ勢が多くいたため、こりゃもうちょっと資料ちゃんとしないと駄目かなと思ってページ増やしたら時間足りなくなってしまいました。

楽しいイベントだったので次回以降もあるならば、予定があえば参加していきたいです。

発表資料

zlib.js 0.2.0 をリリースしました

更新が必要な人

今回は Inflate のアルゴリズム部分のバグ修正となるので、過去のバージョンで Inflate を利用している方は更新する必要があります。

バグ詳細

このコミットの解説となります。

Deflate では、リテラルと長さ・距離符号(LZSS)をハフマン符号化して圧縮します。
ハフマン符号も辞書をそのまま格納するのではなく、符号の長さだけを格納することで更なるサイズ節約を行っています。
さらに、符号の長さもランレングス符号化を行って格納されます。

リテラルと長さ符号、距離符号は別々にハフマン符号化し、それぞれ RFC1951 では HLIT, HDIST と呼ばれています。
このように、別々の辞書を使ってハフマン符号化されるため、ランレングス符号化もそれぞれ別のコンテキストで行われるものだとおもっていたのですが、
どうやら、HLIT と HDIST を連続したものと扱いランレングス符号化するのが正しかったようです。

issue#29 の例でいうと、HLIT の符号長が

[..., 5, 3, 5, 6, 6, 4, 5, 7, 8, 8, 7]

となっていて、HDIST は以下のようになっていました。

[16, 16, 4, 7, 3, 7, 6, 7, 7, 6, 6, 6, 5, 6, 5, 4, 4, 4, 3, 4, 3, 4]

HDIST の 16 という値は「前の値を複数回コピーする」というもので、修正前の実装では初期値である 0 をコピーしてしまっていました。
これを今回の修正で、HLIT の最後の値である 7 をコピーすることで正常に展開することができるようになりました。
今までのテストで見つかっていなかったのが不思議ですが、あまり頻繁にあるケースではないのかもしれません。

Emscripten によって生成された asm.js 対応コードは本当に人間が書いたコードより速いのか?

はじめに

先日、いつものように Twitter 監視業務に勤しんでいたところ、下記のような発言を見かけました。

なるほど、機械によって生成された asm.js 対応のコードはどんなブラウザでも速いよという主張です。
自分は JavaScript で高速に動作するように注意して書いた zlib.js というのを作っていたので、zlib の展開処理でこの発言が本当か試してみることにしました。
zlib の展開処理というのは asm.js に向いていそうな処理ですし、ちょうど良いベンチマークになると思います。

zlib-asm vs zlib.js

比較には asm.js の zlib 実装として @ukyo さんの zlib-asm を採用しました。
ほかの zlib を Emscripten でビルドする系のプロジェクトはベンチマークコードも一緒に Emscripten でビルドしていて、ライブラリとしての単体利用が面倒くさそうだったからです。
その他、zlib-asm では Emscripten の生成したデフォルト状態のコードで遅い部分を最適化していて、もっとも良さそうな感じがしました。
(最初は asm.js が type error になって有効になっていなかったり最適化されていなかったのですが、連絡したらすぐに対応していただけました。ありがとうございます。)

zlib-asm 補足

zlib-asm は zlib のそのままのビルドではなく、zpipe という入出力を圧縮、展開するソフトウェアの Emscripten ビルドです。

zlib.js 補足

zlib.js は zlib の移植ではなく、JavaScript で(それなりに)高速に、ファイルサイズが小さくなるように開発しているライブラリです。
つまり、ここでの比較は zlib という仕様には従っているがまったく異なる実装の速度比較ということになります。

比較結果

比較用のページを用意しました。
手元の環境で実行した結果も貼っておきますが、自分でベンチマーク用のコードを見て実行してみるのが一番正確です。

Chrome 31

Filename Size Compressed zlib-asm
(Emscripten)
zlib.js
Author: imaya
alice29.txt148,48153,63420.55 ms10.76 ms
asyoulik.txt125,17948,8973.12 ms4.28 ms
cp.html24,6037,9611.06 ms0.46 ms
fields.c11,1503,1220.42 ms0.22 ms
grammar.lsp3,7211,2220.35 ms0.11 ms
kennedy.xls1,029,744203,99222.06 ms12.56 ms
lcet10.txt419,235143,1069.72 ms10.67 ms
plrabn12.txt471,162193,73015.06 ms10.04 ms
ptt5513,21656,4657.32 ms6.43 ms
sum38,24012,9901.23 ms0.64 ms
xargs.14,2271,7361.43 ms0.12 ms

Firefox 25

Filename Size Compressed zlib-asm
(Emscripten)
zlib.js
Author: imaya
alice29.txt148,48153,6342.58 ms6.61 ms
asyoulik.txt125,17948,8971.72 ms4.69 ms
cp.html24,6037,9611.68 ms0.72 ms
fields.c11,1503,1220.55 ms0.27 ms
grammar.lsp3,7211,2220.42 ms0.15 ms
kennedy.xls1,029,744203,9927.01 ms16.51 ms
lcet10.txt419,235143,1065.21 ms7.7 ms
plrabn12.txt471,162193,7305.42 ms10.87 ms
ptt5513,21656,4653.05 ms5.2 ms
sum38,24012,9900.86 ms0.83 ms
xargs.14,2271,7360.46 ms0.41 ms

Safari 7.0

Filename Size Compressed zlib-asm
(Emscripten)
zlib.js
Author: imaya
alice29.txt148,48153,63416 ms4 ms
asyoulik.txt125,17948,8974 ms4 ms
cp.html24,6037,9611 ms1 ms
fields.c11,1503,1221 ms1 ms
grammar.lsp3,7211,2221 ms1 ms
kennedy.xls1,029,744203,99224 ms17 ms
lcet10.txt419,235143,10613 ms9 ms
plrabn12.txt471,162193,73016 ms11 ms
ptt5513,21656,4656 ms5 ms
sum38,24012,9902 ms1 ms
xargs.14,2271,7360 ms1 ms

傾向

asm.js が有効になっていないブラウザ(Chrome, Safariなど)では zlib.js が有利な結果になり、asm.js が有効になっているブラウザ(Firefox)では zlib-asm が有利な結果となりました。

まとめ

人間が書いた JavaScript でも機械の生成した asm.js 用のコードより速くなることもある。
あるいは、自分は人間ではなかった。

今回は人間で書いたコードのほうがasm.js非対応な環境では速くなることがありましたが、Emscriptenが出力するコードにはまだ非効率な部分が残っているため、これからもこの状況が続くとは限りません。
今後も見守っていこうと思います。

Canvas でカラーハーフトーン

はじめに

ネット上で Photoshop にはカラーハーフトーンというフィルタがあることを知って、面白そうなので実装してみました。
適当にググってカラーハーフトーンフィルタを使った画像を見ながら「多分こういうものだろう」と考えて実装したものなので Photoshop のものとは大きく異なる可能性があります。

カラーハーフトーンってなに

元々は網点という印刷まわりの技法のようですが、Photoshop のものは完全に画像の効果としてあつかった方が良いみたいです。
ネットで使用例を見た感じ、各色ごとに指定された角度の正方形に画像を分割して、色の多いところは大きく、少ないところは小さく円を描いて水玉模様みたいにする効果だと思います。

実装1: 独自実装(わりとゴリ押し)

(0, 0) から角度と正方形のサイズから dx, dy を計算してそれを加算していきます。
走査の改行は 90 度回転させた角度で同じように計算します。
この場合、斜めに進んで行くので Y 方向に加算していくだけでは走査に漏れが発生するため、X 方向に進ませた時 Y が 0 以下のときは Y を負の方向に進ませてみて描画できそうなら描画してさらに負の方向にすすませるということをしています。

scanline

描画すべきかどうかは、四隅の点のどれかが描画領域にはいっているかどうかで判定しています。

実装2: 行列を使った変換

回転行列を使って、全てのピクセルを矩形サイズで割った大きさの画像に縮小&回転させた画像に変換し、そこから元の大きさ・角度に逆変換することで上記のような走査ではなく、適切に処理できると考えました。

実際にやってみたところ、変換時に角度によっては微妙にピクセルがずれ、それを戻すと割と目立つ違いになってしまうので微妙な感じになってしまいました。
うまく変換する方法を思いつくまでこちらの方法はひとまず置いておこうと思います。

half

各色毎に回転・縮小して…

inverse

逆行列で元にもどします。

行列の計算は goog.math.Matrix という Closure Library のコードを使っています。

実装例

jsdo.it に置いておきました。
事前にグレイスケール化や二値化するフィルタをかけたり、カラーハーフトーンが終わった後に特定の色で塗りつぶしたりできるようになってます。

まとめ

Canvas + JavaScript は画像加工ツール

Canvasできれいな色相環を描画する

はじめに

JavaScript で Canvas を使っていると、HSV の Color Picker とか作りたくなって色相環を描画したくなることがよくあるとおもいます。
ここでは、自分の行っている色相環の描画方法を説明します。

準備

色相を扱うのために HSV 色空間を使います。HSV から RGB への変換は以下の function を用います。

function hsvToRGB(hue, saturation, value) {
    var hi;
    var f;
    var p;
    var q;
    var t;

    while (hue < 0) {
        hue += 360;
    }
    hue = hue % 360;

    saturation = saturation < 0 ? 0
        : saturation > 1 ? 1
        : saturation;

    value = value < 0 ? 0
        : value > 1 ? 1
        : value;

    value *= 255;
        hi = (hue / 60 | 0) % 6;
        f = hue / 60 - hi;
        p = value * (1 -           saturation) | 0;
        q = value * (1 -      f  * saturation) | 0;
        t = value * (1 - (1 - f) * saturation) | 0;
    value |= 0;

    switch (hi) {
        case 0:
            return [value, t, p];
        case 1:
            return [q, value, p];
        case 2:
            return [p, value, t];
        case 3:
            return [p, q, value];
        case 4:
            return [t, p, value];
        case 5:
            return [value, p, q];
    }

    throw new Error('invalid hue');
}

距離で判別する

まず最初に思いつくのが、以下のような方法でしょう。

  1. x, y から中心となる点までの距離を計算する (三平方の定理)
  2. 距離が円の範囲内ならば、中心までの角度を計算する (Math.atan2)
  3. 角度から色相を計算し、RGBに変換して描画する

1の距離の計算ですが、距離の比較にしか使わないため、平方根を取らずに半径を二乗する事で高速化してもよいですね。
ただし、この場合アンチエイリアスなどがかからず、端の方がギザギザになってしまいます。

これを JavaScript で書くと以下のようなコードになります。

var width = 300;
var height = 300;
var canvas = document.createElement("canvas");
var ctx = canvas.getContext("2d");

canvas.width = width;
canvas.height = height;
document.body.appendChild(canvas);

// 円の外側の距離
var r1 = Math.min(canvas.width, canvas.height) / 2;
// 円の内側の距離
var r2 = r1 - 30;
// 中心
var cx = canvas.width / 2;
var cy = canvas.height / 2;

var imageData = ctx.getImageData(0, 0, width, height);
var pixelArray = imageData.data;

for(var x = 0; x < width; x++) {
    for(var y = 0; y < height; y++) {
        var d = (- cx) * (- cx) + (- cy) * (-cy);

        if(< r1 * r1 && d > r2 * r2) {
            var baseIndex = (* width + x) * 4;
            var hue = Math.atan2(- cx, y - cy) / Math.PI / 2 * 360;
            var color = hsvToRGB(hue, 1, 1);

            pixelArray[baseIndex  ] = color[0];
            pixelArray[baseIndex+1] = color[1];
            pixelArray[baseIndex+2] = color[2];
            pixelArray[baseIndex+3] = 255;
        }
    }
}

ctx.putImageData(imageData, 0, 0);

一度円を描画してアルファ値で描画対象か判別する

自分はこのギザギザが許せなかったので何か良い方法がないか考えたところ、一度適当な色の円を書いて、その場所に色を上書きしていく方法を思いつきました。

var width = 300;
var height = 300;
var canvas = document.createElement("canvas");
var ctx = canvas.getContext("2d");

canvas.width = width;
canvas.height = height;
document.body.appendChild(canvas);

// 円の外側の距離
var r1 = Math.min(canvas.width, canvas.height) / 2;
// 円の内側の距離
var r2 = r1 - 30;
// 中心
var cx = canvas.width / 2;
var cy = canvas.height / 2;

// 円を描く
ctx.arc(cx, cy, r1, 0, Math.PI * 2, true);
ctx.arc(cx, cy, r2, 0, Math.PI * 2, false);
ctx.fill();

そして、その描画された部分のアルファ値を見て色を上書きします。

var imageData = ctx.getImageData(0, 0, width, height);
var pixelArray = imageData.data;

for(var x = 0; x < canvas.width; x++) {
    for(var y = 0; y < canvas.height; y++) {
        var baseIndex = (* width + x) * 4;

        // 透明でなければ上書きする
        if(pixelArray[baseIndex + 3] > 0) {
            var hue = Math.atan2(- cx, y - cy) / Math.PI / 2 * 360;
            var color = hsvToRGB(hue, 1, 1);

            pixelArray[baseIndex  ] = color[0];
            pixelArray[baseIndex+1] = color[1];
            pixelArray[baseIndex+2] = color[2];
        }
    }
}

ctx.putImageData(imageData, 0, 0);

パフォーマンス

どちらの方法も手元の Chrome 28, Firefox 23 だと 9-14ms 程度だったので性能的な違いはあまりないと思います。

追記: 2013/08/16

CanvasRenderingContext2D#arc の endAngle を Math.PI * 2 より大きい整数である 7 としていましたが、Math.PI * 2 を超える値の扱いが safari でおかしくなるため、Math.PI * 2 に修正しました。

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