document

HTML5 & JavaScript side
twitter: @y_imaya

JavaScript のビット演算子に unsigned を期待してはいけない

はじめに

ビット演算を利用するケースでは unsigned を期待することが多いと思うのですが JavaScript ではその期待は捨てたほうが良いです。(ただし >>> 演算子を除く) ここではその具体例と対策、簡単な説明をしていきたいと思います。

具体例

ではさっそく、例として

0x12345678 ^ 0xFFFFFFFF

を見てみましょう。 (なぜ 32-bit かというと JavaScript のビット演算は 32-bit で行われるからです。)

0x12345678 は 2 進数表記にすると 0001 0010 0011 0100 0101 0110 0111 1000 になります。 これを XOR 0xFFFFFFFF で反転させるのですから、 下記のように計算して期待する値は 0xEDCBA987(=3,989,547,399) となるはずです。

   0001 0010 0011 0100 0101 0110 0111 1000
 ^ 1111 1111 1111 1111 1111 1111 1111 1111
 -----------------------------------------
   1110 1101 1100 1011 1010 1001 1000 0111

しかし、実際に実行してみると

-305419897
という値になります。そうです。signed なんです。 それだけならまだ分かりにくいだけで良いかも知れません。

しかし、以下の例コードを実行してみてください。

 (0x12345678 ^ 0xFFFFFFFF) === 0xEDCBA987 // false

これが通らないのはおかしいと思いませんか? (とは言っても、上記を展開すると -305419897 === 3989547399 となるので false となるのが当然なんですが。)

対策

上記の例を、あまり変更せずに通るようにするにはどうしたらよいかというと

((0x12345678 ^ 0xFFFFFFFF) >>> 0) === 0xEDCBA987 // true

とするだけです。 >>> 演算子は結果を unsigned で返すため、簡単な型変換に利用することができます。

説明

ここまで読んでも (0x12345678 ^ 0xFFFFFFFF) === 0xEDCBA987 は両方とも 16 進表記にすると 0xEDCBA987 なのに何故一致しないのか疑問に思う人もいるかもしれません。

ECMA-262 5.1 によると、ビット演算子は以下のような型変換を行うとされています。

演算子 参照した章 結果の型
~ 11.4.8 Bitwise NOT Operator ( ~ ) signed 32-bit integer
<< 11.7.1 The Left Shift Operator ( << ) signed 32-bit integer
>> 11.7.2 The Signed Right Shift Operator ( >> ) signed 32-bit integer
>>> 11.7.3 The Unsigned Right Shift Operator ( >>> ) unsigned 32-bit integer
&, ^, | 11.10 Binary Bitwise Operators signed 32 bit integer

また、JavaScript の数値は IEEE 754 であるとされています。( "4.3.19 Number value" より)

つまり、0x12345678 ^ 0xFFFFFFFF-305419897 という値は 32-bit integer ではなく、 ビット演算子によって signed 32-bit integer に変換されたのち IEEE 754 形式にされるため、 0xEDCBA987 = 3989547399 の IEEE 754 形式と一致しないというわけです。

LZSS における簡易 lazy matching 実装

はじめに

まず、LZSS とはどういったアルゴリズムなのかを簡単に説明します。
簡単な例をあげます。

"aiueoaiueoaiueo"

このような文字列が入力として与えられた時、"aiueo" の繰り返しに注目します。
2回目の "aiueo" は最初の "aiueo" からコピーするようにします。同様に3回目も同じようにします。
すると以下のように表すことができます。

"aiueo[5文字戻り,5文字分参照][10文字戻り,5文字分参照]"
(ここでは、これを簡単に "aiueo[5,5][10,5]" と表すことにします。)

この表現でもまだ無駄があります。
ここでは5文字分を一区切りとして使用していますが、"aiueoaiueo" 2つの重なりで表現した方が短くなります。

"aiueoaiueo....."
".....aiueoaiueo"


から

"aiueo[5,10]"

とすることができます。

なお、実際のデータでは LZSS は先頭ビットで長さ距離符号かそうでないかを判定するようにしています。
DEFLATE の実装では 0-255 (0x000-0x0FF) をリテラル、256-285 (0x100-0x11D) を記号として扱い、257-285とその後に続くデータで長さと距離を表しています。(256は終端記号)
また、DEFLATE ではそれぞれの範囲が、長さ 3-258, 距離 1-32768 と決められています。

LZ77 と LZSS の違い

ちなみに、よく LZ77 と書かれているものは LZSS であることが多いのですが、違いについて一応書いておきます。
LZ77 では先ほどの簡易表現の最後に「不一致だった場合は不一致文字」を追加して、上記の例は以下のように表現されます。

"a[0,0,i][0,0,u][0,0,e][0,0,o][5,10]"

不一致に関しても符号化しているため、長くなってしまうのが欠点でそれを短縮したのが LZSS という位置づけです。

lazy matching

先ほどの例は簡単な例なので特に悩む点はありませんでしたが、以下のような例はどうでしょうか。

"bcdefghijklmnabcabcdefghijklmn"

一般的な実装では、左から順に一致を見ていくようになっているので

"bcdefghijklmnabcabcdefghijklmn"
"bcdefghijklmnabc[3,3][17,11]"

となります。しかし、もっと短い表現があります。

"bcdefghijklmnabcabcdefghijklmn"
"bcdefghijklmnabca[17,13]"

です。長さと距離の符号よりもリテラルの方が短いビットで表現できるため、こちらのほうが短くなります。

lazy matching とは、前の例で [3,3] を見つけた時点で「保留」しておき、より長いものが見つかった場合はそちらを採用するようにします。
今回実装したのは、以下のようなアルゴリズムです。

 1. [3,3]を見つけたら「保留」にする。
 2. 次の位置でマッチした場合(上記の例の場合 [17,13] )、「保留」のマッチの一致長と比較する。
 3. 「保留」のマッチの方が長ければ今回のマッチはなかったことにして戻り、「保留」のマッチを採用する。
    現在のマッチの方が長ければ、前回のマッチは捨て前回の位置はリテラルとして扱い、現在のマッチを採用する。

これにより、圧縮率が上昇するようになっています。
ただし、「最長一致」の探索が増えているため、負荷は上昇します。
そのため、一般的な実装では圧縮レベルによって「lazy matching を行うかどうか判定する一致長」を変えて、ある程度長い一致ならば lazy matching せずに採用するといった工夫がされています。

JavaScript ネイティブの実装で apply を利用しない方が良いケース

はじめに

JavaScript ネイティブのメソッドには JavaScript エンジンごとの微妙な違いによってクロスブラウザではないものもあります。 apply もその一つです。 ここでは、apply で利用されることの多い Array.prototype.push, Array.prototype.unshift, Math.max, Math.min を対象に、なぜ利用しないほうが良いのかを書きます。

RangeError を投げる実装

Google Chrome 15 と Safari 5 では apply の第二引数の length が規定値以上になったところで RangeError 例外を投げます。 (この規定値は手元の Google Chrome 15 では 130,827 個、 Safari 5 では 65,537 個 でした。) なお、ここでは RangeError を投げる仕様がただしいかどうかはこの場では問題にしません。

速度

一般的にネイティブ実装の方が高速であると考えがちですが、速度を測ってみると必ずしもそうではないケースがあります。 以下の jsdo.it のコードはここで対象とするメソッドの実行速度を計測します。

for-loop vs apply (push, unshift, max, min) - jsdo.it - share JavaScript, HTML5 and CSS

Google Chrome 15

Google Chrome 15 で実行した結果、以下のような結果になりました。

  for-loop apply etc1 etc2
push 16ms 20ms - 18ms
unshift 8466ms 21ms 79ms 19ms
Math.max 6ms 20ms - -
Math.min 4ms 24ms - -

各項目の説明については jsdo.it の説明(とコード)を読んでいただくとして、unshift を除いた結果では for-loop による実装の方が高速に動作しています。 もちろん、計測誤差もあるので必ずしも for-loop にすることで高速になるとは言えませんが、少なくとも apply から for-loop の実装に変えたところで誤差レベルの損失であると言えます。

Safari 5

Safari 5 で実行した結果、以下のような結果になりました。

  for-loop apply etc1 etc2
push 265ms 174ms - 521ms
unshift 614ms 213ms 837ms 579ms
Math.max 27ms 105ms - -
Math.min 31ms 161ms - -

Array.prototype.pushArray.prototype.unshift に関しては apply が最速で、それ以外は若干微妙な気がします。 ただ、Safari 5 において RangeError が出るサイズは 65,537 以上と Chrome よりも出やすい環境なので、 やはり unshift 以外は for-loop で unshift は 分割 apply が良さそうです。

どうするべきか

Array.prototype.push, Math.max, Math.min に関しては for-loop による実装におきかえる事で、RangeError 例外の発生を考慮しないで済むようになります。

Array.prototype.unshift に関しては for-loop にするととてつもなく遅くなることが前述の計測結果からわかりますので、適切なサイズのブロックに分けて apply を繰り返すという方法が良いと思います。 この際、ブロックサイズが適切じゃなかった( RangeError がでてしまう)事態に備えて、以下のようなコードにするのが良いのではないでしょうか。 ( * jsdo.it の unshift: etc2 のコードです)

function unshift_(dst, src) {
	var buffer = 0x8000, blocks, complete = false;

	while (!complete) {
		try {
			// block
			blocks = [];
			for (i = 0, l = src.length; i < l; i += buffer) {
				blocks.push(src.slice(i, i + buffer));
			}

			// unshift
			for (i = blocks.length - 1; i >= 0; i--) {
				Array.prototype.unshift.apply(dst, blocks[i]);
			}
			complete = true;
		} catch (e) {
			if (e instanceof RangeError) {
				buffer >>>= 1;
			} else {
				throw e;
			}
		}
	}

	return dst.length;
}

まとめ

apply を使う際に、第二引数に大きな配列が来る可能性のある場合は RangeError 例外を考慮したコードにした方が良い。 unshift 以外では for-loop に置き換えるのがオススメ。 unshift の場合は分割して apply するのがオススメ。

補足

Google Chrome と Safari での計測結果は各手法の差異を計るための物で、Chrome と Safari の実行条件(配列サイズと実行回数)は異なっています。

pure JavaScript の PNG エンコーダを作りました

出来ること

  • Canvas の PNG 出力
    • 仕様にあるチャンク全てに対応

ライセンス

MIT License

使用方法

 
var pngEncoder = new CanvasTool.PngEncoder(data, opt_params);
pngEncoder.convert();

  • data: CanvasPixelArray もしくは互換の配列
  • opt_params:
    {
      bitDepth: number,
      colourType: CanvasTool.PngEncoder.ColourType,
      compressionMethod: CanvasTool.PngEncoder.CompressionMethod,
      filterMethod: CanvasTool.PngEncoder.FilterMethod,
      filterType: CanvasTool.PngEncoder.BasicFilterType,
      interlaceMethod: CanvasTool.PngEncoder.InterlaceMethod,
      gamma: number;
      chrm: {
        whitePointX: number,
        whitePointY: number,
        redX: number,
        redY: number,
        greenX: number,
        greenY: number,
        blueX: number,
        blueY: number
      },
      splt: {
        name: string,
        num: number
      },
      srgb: CanvasTool.PngEncoder.RenderingIntent,
      sbit: Array.;
      iccp: Array,
      hist: boolean,
      phys: {
        x: number,
        y: number,
        unit: CanvasTool.PngEncoder.UnitSpecifier
      },
      time: Date,
      text: {
        keyword: string,
        text: string
      },
      ztxt: {
        keyword: string,
        text: string,
        compressionMethod: CanvasTool.PngEncoder.CompressionMethod
      },
      trns: boolean
    }
    
    ※詳細はソースコードのコメントを参照

戻り値は String (binary string)

デモ(jsdo.it)

Pure JS PNG Encoder - jsdo.it - share JavaScript, HTML5 and CSS

ダウンロード

GitHub のリポジトリからどうぞ。

pure JavaScript の Zlib, Deflate 実装を作りました

何故作ろうと思ったのか?

pure JS な PNG エンコーダを作成する際、ライセンスがクリアな Deflate 実装が見つけられなかった為。

出来ること

  • Zlib (RFC1950) 圧縮
    • 圧縮方法として Deflate (RFC1951) の以下のブロックに対応
      • 非圧縮
      • 固定ハフマン符号
      • 動的ハフマン符号(カスタムハフマンテーブル)

ライセンス

MIT License

使用方法

 Zlib.Deflate.compress(data[, opt_params]);
  • data: byte array もしくは string
  • opt_params:
    {
      compressionType: Zlib.Deflate.CompressionType.(NONE|FIXED|DYNAMIC)
    }

戻り値は Array (byte array)

デモ(jsdo.it)

Zlib Deflate 動作デモ - jsdo.it - share JavaScript, HTML5 and CSS

ダウンロード

GitHub のリポジトリからどうぞ。ただし、PNGエンコーダの一部となっていますので、個別で利用される方は最新版を minified したものを利用すると良いです。

問題点

lazy match 非対応なため、他のライブラリの高圧縮率設定と比べると若干圧縮性能が落ちるかも知れません。

謝辞

本ライブラリを作成するにあたって、id: n7shi さんの資料が大変参考になりました。ありがとうございました。

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