mitsunari@cybozu labs

JavaScriptでSHA-1を計算するライブラリを作りました．

○特長
webでよく見られるいくつかの同種のライブラリに比べて4～6倍ほど高速に計算します．

○ダウンロード(download)
sha1.js

○仕様
ASCII文字列を渡すとそのSHA-1を計算して16進数文字列で返します．
文字列に漢字などが含まれている場合は二つ目の引数にCybozuLabs.SHA1.BY_UTF16を指定してください．UTF16として処理します．

○使い方1
var str = CybozuLabs.SHA1.calc("abc");
if (str == "a9993e364706816aba3e25717850c26c9cd0d89d") {
...
}
○使い方2
var str = CybozuLabs.SHA1.calc("あ", CybozuLabs.SHA1.BY_UTF16);

○ライセンス
修正BSDライセンスにしたがいます．

○動作環境
Windows Xp + IE6, Firefox, Mac OS X + Safariで動作確認をしています．

○ベンチマーク
var msg = "MD5abZRVSXZVRcasdfasdddddddddddddddds+BNRJFSLKJFN+SEONBBJFJXLKCJFSE)RUNVXDLILKVJRN)#NVFJ)WVFWRW#)NVS$Q=$dddddddddddddWV;no9wurJFSE)RUNVXDLILKVJRN)#NVFJ)WVFWRW#)NVS$Q=$dddddddddddddWV;no9wurJFSE)RUNVXDLILKVJRN)#NVFJ)WVFWRW#)NVS$Q=$dddddddddddddWV;no9wurJFSE)RUNVXDLILKVJRN)#NVFJ)WVFWRW#)NVS$Q=$dddddddddddddWV;no9wuraddddddasdfasdfd";
という文字列に対してSHA-1の計算を100回ループしたときの処理時間を測定しました．
比較対象はPaj's Home: CryptographyとJavaScript でハッシュアルゴリズムで公開されているライブラリです．

環境:Windows Xp Sp2 Core2Duo 2.66GHz 2GB memory
IE6:
test1 my lib
time = 0.94msec
test 2 pajhome
time = 9.22msec
test 3 JavaScript でハッシュアルゴリズム
time = 6.1msec

Firefox:
test 1 my lib
time = 2.19msec
test 2 pajhome
time = 11.87msec
test 3 JavaScript でハッシュアルゴリズム
time = 9.22msec

幅はありますが4～6倍程度高速に計算されていることが分かります．

前回の結論のように, JavaScriptにおいては計算の重たい部分を展開したもの勝ちです. 一昔前のCコンパイラに対するようなものですね.
無論, やり過ぎたら読みにくいしメンテしづらいですが変わることのないライブラリなら許容範囲は広いでしょう.

ここではsha1.jsで使われている展開以外のテクニック(?)をあげてみます.

・32bitラップアラウンド

高度な JavaScript 技集では次のコードが使われていました.

function MD5_number(n) {
  while (n < 0)
    n += 4294967296;
  while (n > 4294967295)
    n -= 4294967296;
  return n;
}

他のwebページでも似たコードを見かけました. もしかしたら昔の処理系に対応したものの名残が広まっているのかもしれませんが, 0とorして正しく32bit整数になる処理系にとっては殆ど無意味です. もし入力値に負数を許容するとしても

function round(x)
{
    x |= 0;
    if (x < 0) x += 4294967296;
    return x;
}

で十分でしょう. ただし, SHA-1で定数値に負数を含まないようにしておけばif()は不要です. ついでにsha1.jsなどではA + B + Cをround(round(A + B) + C)のように演算ごとにroundを呼ぶ必要もありません. 削れるところは削りましょう.

・32 = 16 + 16?

分割してみるで述べたようにFxでは32bit整数を分割するほうが高速に動作する可能性があります.
素直に実装するならここは二つの16bit整数のペアとするでしょう.
もちろんそれで全然問題ありませんが, SHA-1には5bit右回転と1bit右回転がたくさんでてきます.
5bit右回転は

function rotL5(x)
{
    return (x << 5) | (x >>> 27);
}

ですから, 16bit x 2のバージョンではxを上位16bitのxH, 下位16bitのxLとに分割すると,

    var t = ((xL << 5) & 0xffff) | ((xH >>> 11);
    xH = ((xH << 5) & 0xffff) | (xL >>> 11);
    xL = t;

となります. しかし, ここを 32 = 5 + 27 (xHが上位5bit, xLが下位27bit)と分ければどうなるでしょうか.

    var t = xH | ((xL & 0x3fffff) << 5);
    xH = xL >>> 22;
    tL = t;

となり, 論理演算が8回から4回と半分に減りました. もちろん5 + 27に分けても1bit右回転は論理演算が8回必要ですが, 片方が半分になるだけでもうれしいです. なお, 逆に32 = 1 + 31に分けるのもあるのか? と思われるかもしれませんが, もともと30bit整数未満にしたかったわけですからその選択はありません.

またSHA-1の演算の中で5回連続足し算がでてきますが, 27bit整数の場合は8回加算しても2³⁰を超えませんから問題ありません(この文の意図は解りにくいかな).

・16bit整数のnot

単に~xとしてしまうと上位16bitに1が立ってしまいます. ~x & 0xffffとしてもよいですが, 入力値が65536未満であることを利用すれば 65535 - x でOKです.

今回はこんなところで.

1年ほど前に作ったsha1.jsをgoogle Chrome上でベンチマークをとってみました(Win Xp@Core2Dup 2.6GHz)．
結果はpajhomeさんの実装では20倍以上もの凄まじい速度向上がありましたが，もともと最適化していた私ものものはあまり速くなっていません．
これはループアンロールなどの(つまらない)努力は不要になるということで，すばらしいことです．
ただ数値計算に限っては，もともと十分に最適化されていればIE6と大きく変わるものでもないとも言えます．
ちなみにC++でのSHA-1では0.0056msecでした．まだ100倍ほどの開きはあるようです．

ところでchromeのJIT部分で使ってるassembler-ia32.ccなんかみるとxbyak使ってほしいなとか思ったり．x86-64への対応が簡単になると思いますがいかがでしょう．

	my SHA-1	pajhome	JavaScriptでハッシュアルゴリズム
IE6	0.94msec	10.47msec	6.25msec
Firefox 3.0.1	0.63msec	2msec	1.39msec
Chrome	0.55msec	0.44msec	0.65msec