mitsunari@cybozu labs

前回の結論のように, 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です.

今回はこんなところで.