png identify とは

JavaScript で書かれた、PNG ファイルの様々な情報を表示するウェブブラウザ上で動作するアプリケーションです。(Chrome 16.0.912.77, Firefox 9.0.1 で動作確認) PNG, ZLIB の圧縮率向上をはかる際に、自分の求める詳細な情報を表示するツールが見当たらなかったので作成しました。

使い方

http://imaya.github.com/png.identify/
上記のページを開き、そのページに PNG ファイルをドラッグアンドドロップするだけです。

どんな情報を表示する？

まずはざっと一覧で。

• ファイル名
• イメージヘッダ
• チャンク
• パレット
• フィルタ
• イメージデータ圧縮関係

イメージヘッダ情報

PNG の IHDR チャンクの情報を表示します。

チャンク

すべてのチャンクの位置とサイズ、CRC32ハッシュ値を表示します。

パレット

PLTE チャンクがある場合はパレットの詳細を表示します。

フィルタ

画像で使用されているフィルタを表示します。 複数フィルタのフィルタが混在している場合は、各フィルタの割合と全てのフィルタを表示します。

イメージデータ圧縮関係

IDAT チャンクで利用されている ZLIB に含まれるブロックの圧縮前と圧縮後のサイズと割合を表示します。

制限

• 一度のドラッグアンドドロップで1つのファイルしか使えません。
• Typed Array, Drag and Drop API, File API の使えるブラウザじゃないと動作しません。
• Web Workers などは使っていないので、スペックによってはスクリプトの停止ダイアログが出るかもしれません。

使用ライブラリ

png.js: https://github.com/devongovett/png.js

ソースコード

GitHub リポジトリ: https://github.com/imaya/png.identify
ライセンスは MIT License です。

はじめに

最近のコミットで最長一致探索部分を書きなおしたらシンプルになったのでメモ替わりに書いておきます。

まず、DEFLATE では chained hash table を使用することが推奨されています。 LZ77 関連では処理の高速化に関していろいろ特許があるようなので、今のところ特許問題のでていないこの方法を使用しています。

chained hash table とは、連続する 3 Byte をハッシュのキーとして辞書を持ち、 ハッシュキーの値に該当位置を記録しておくことで、高速に LZ77 の長さ距離符号の判定を行うことができます。 (なぜ 3 Byte をハッシュキーにするかというと、DEFLATE の長さ距離符号の長さの最小が 3 Byte だからだと思います。)

chained hash table を利用したとしても、わかるのは「最低でも 3 Byteは一致している」ので、 複数の候補があった場合はそこから最長のものを絞り込んでいかなければいけません。

最長一致探索

そこで、複数の「最長一致候補」から最長のものを探索する仕組みが必要になります。 以前はちょっと凝ろうとしたことをして、逆に複雑になった上にロクな出来ではなかったので、 今回以下のようなシンプルな方式に修正しました。

最長候補は常に 1 つだけ

以前は最長候補は探索処理の最後まで持っておき、最後に場合によって切り替えられるようにしていました。 ただ、あまり意味がなかったので今回は常に 1 つだけ持っておくようにしました。 この時、最長マッチ長が同じ候補が複数あった場合にどちらを選択するか決定するルールが必要なので、 「マッチ長が同じだった場合は後方(現在の位置と近い)ものを採用する」というようにしました。

なぜ後方のものを採用するかというと、長さ距離符号にした際に距離符号を短くできることがあるからです。 (extra bits はハフマン符号化の対象にならない。下記に長さによる extra bits の長さを示します。)

これにより無駄な配列関連の処理がばっさり減らせました。

基本は左から 1 Byte ずつ比較処理

以前はちょっと凝ろうとしたことをして複雑になってました。 すでに修正済みなので簡単にどういったことをやっていたか説明すると、例えば以下のようなマッチ候補があった時に

　"abcdefghijklmnop" ...

以下のように一定の長さに分割します。（実際に分割するわけではなく意味上の区切りですが）

  "abcdefgh" "ijklmnop" ...

そして、下記のように後方から比較していました。

  ".......h"
  "......g."
  ".....f.."
  "....e..."
  .
  .

これは何がしたかったのかというと、 chained hash table によって前 3 Byte の一致がしているのはわかっているので、 そこから絞り込む際 4 Byte 一致してるものというのは比較的多いのではないかと考えました。 （ LZ77 で圧縮可能なデータというのは偏りがあるため）

同様に 5 Byte, 6 Byte ... と見ていくよりも末尾から見ていく方が速く候補を落とせると考え、実際一定の速度向上はしました。

今回の実装では、そのへんをばっさりとやめ「基本は」左から1文字ずつ見ていくようにしました。 ただ、全ての候補を1つずつ単純に左から見ていくのも素直すぎるので、今回は以下のような仕組みを加えています。

現在までの最長マッチの長さを記録しておき、次の候補は現在の最長マッチ分右に移動し、そこから左に向かって走査していき、すべて一致していたら最長マッチ以降のデータを右に向かって調べていきます。

例

以下の最長マッチ候補を例に説明します。

 -. "abcdefghijklmn" // データ
 1. "abcde123456789" // マッチ候補 1
 2. "abcdefgh123456" // マッチ候補 2
 3. "abcdef12345678" // マッチ候補 3
 4. "abcdefg1234567" // マッチ候補 4

 // chained hash table の参照で 3 Byte の一致
 -. "abc..........."
 1. "abc..........."

 // 右に向かって 1 Byte ずつ一致探索した結果 5 Byte が一致
 -. "abcde........."
 1. "abcde........."
 走査方向 → 
 最長一致: 5
 最長一致マッチ: 1

 // 次の候補も chained hash table から 3 Byte の一致
 -. "abc..........."
 2. "abc..........."

 // 5 Byte 目, 4 Byte 目 と確認
 -. "abc.e.........", "abcde........."
 2. "abc.e.........", "abcde........."
 走査方向 ←

 // 最長一致までの長さは全て一致したので右に走査していく
 -. "abcdefgh........"
 2. "abcdefgh........"
 走査方向 →
 最長一致: 8
 最長一致マッチ: 2

 // 次の候補も chained hash table から 3 Byte の一致
 -. "abc..........."
 3. "abc..........."

 // 8 Byte 目を確認するが一致しないので探索終了
 -. "abc....h....."
 3. "abc....2....."
 走査方向 ←

 // 次の候補も chained hash table から 3 Byte の一致
 -. "abc..........."
 4. "abc..........."

 // 8 Byte 目を確認するが一致しないので探索終了
 -. "abc....h....."
 4. "abc....1....."
 走査方向 ←

おわりに

もっと良い方法あったら教えて下さい。

はじめに

ビット演算を利用するケースでは 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

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

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

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

対策

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

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

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

説明

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

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

また、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 とはどういったアルゴリズムなのかを簡単に説明します。
簡単な例をあげます。

"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 せずに採用するといった工夫がされています。