better gyp

programming build

仕事でごりごり gyp を使って早くも３年になる。いくつか個人的に痒いところを修正して公開してみた。


修正は以下のとおり。

  1. Android: 非 cygwin でもビルドできるようにした
    1. android: Fix path separator for non-cygwin Windows ndk-build. · 22e62bd · okumura/gyp
  2. Android: *.so をビルドするときの name mangling 規則を緩められるようにした
    1. android: Allow targets to have not strict unmangled names by android_unm... · 0a70b36 · okumura/gyp
  3. Windows: MIDL オプションの ValidateParameters、GenerateTypeLibrary をサポートした
    1. win: Allow support MIDL ValidateParameters and GenerateTypeLibrary. · 879936b · okumura/gyp


ここを見てちゃんとやれば本流に取り込んでもらえるかな？

faster octree color quantization

programming practice algorithm

256色画像全盛期はとっくに過ぎ去った感がありますが、今回は画像を256色以下に減色するという話です。減色された画像の画質を向上させる方法として誤差拡散法がありますが、今回はそれはやりません。


減色する方法は大昔から研究されていて有名なものがいくつかあります。

  • 均等量子化法 (uniform quantization)
    • RGB888などをRGB332などにマッピングする
    • 高速、単純、簡易、だが画質は低い
  • 頻度法 (popularity algorithm)
    • 画素の出現頻度からパレットを作成する
    • 画質はいまいち
  • 中央値分割法 (median cut algorithm)
    • 一時は最強と呼ばれていた手法
    • 色空間を二分していく
    • 複雑だが割と高速で割ときれい
    • 色空間はRGBよりもYCbCrで分割する方がよいはず
  • 八分木 (octree algorithm)


今回はoctreeをやります。画質を追求するのはImage Magickなどがやっていますので、速度を追求してみましょう。octreeの計算量は、画像の横幅をW、縦幅をH、深さをDとすると、O(W*H*D)となります。試した限りだと、octreeだと深さが4〜5程度で画像を人が認識するには十分な画質が得られますが、いかんせんループ回数が多すぎます。ピクセル処理なのにボクセル処理してるみたいな計算量です。

量子化ループの最適化その１

octreeのループ処理のコードを見ると、同じ画素に対しては全く同じ処理が繰り返されるということが分かります。これを利用した最適化を考えます。画像のヒストグラムを求めることができれば、画像の色数分だけのループで済みそうですね。画像の色数Cは、必ずC<=W*H以下になるので、計算量は必ず最適化前よりも小さくなります。


画像の色数分だけループする方法に処理を書き換えるには、画像のヒストグラムを求める必要があります。画像の画素をソートすることで画像のヒストグラムを求めることができますが*1、ソートは割とコストがかかるので高速化には使えません*2。よって、真面目にヒストグラムを計算する方が良さそうです。しかし、真面目にヒストグラムを計算すると大量にメモリが必要になります。RGB888で、ヒストグラムの各要素を符合なし整数で管理すると、2^24*4で64MBものメモリが必要になってしまいます。最近の端末やサーバなら余裕な気もしますが、長いことクライアントアプリを作ってきた私の感覚的にはメモリを使い過ぎですし、色数が1677万色もあると最悪で65536x65536の画像に相当する処理をやらないといけなくなるので高速化できるのかが不安になってきます。というわけで、精度を落とすことを考えてみましょう。

  • RGB888 -> 2^24*4 -> 64MB (65536x65536程度の画像に相当する)
  • RGB777 -> 2^21*4 -> 8MB (2896x2896程度の画像に相当する)
  • RGB666 -> 2^18*4 -> 1MB (1024x1024程度の画像に相当する)
  • RGB565 -> 2^16*4 -> 256KB (512x512程度の画像に相当する)
  • RGB555 -> 2^15*4 -> 128KB (362x362程度の画像に相当する)
  • RGB444 -> 2^12*4 -> 16KB (128x128程度の画像に相当する)


感覚的にRGB666程度なら精度的にも速度的にも空間的にもよさそうですね。実際に試してみたところ、手元のマシンで処理時間を30〜50ミリ秒程度から10ミリ秒以下まで削減できました。いいですね。しかし、高速化前と結果が異なります。高速化前の方が画質がいいです。これは高速化+RGB888でやっても高速化前の画質に劣ります・・・。せっかくのoctreeが台無しで残念ですね。

量子化ループの最適化その２

ノードキャッシュ

octreeは動的に八分木のノードに使うメモリを確保・破棄します。確かに空間的な効率はいいです。単発呼び出しなら。ただし、繰返し呼び出すとメモリの断片化が起こってOSにあまり優しくない気がします。優しくないのは紳士的ではありませんので、優しくできないかを考えてみましょう。小さいメモリの確保・破棄が連続すると断片化が発生しやすいですが、確保・破棄がなければ断片化は発生しません。ノードをプールしておけばいいわけですね。ではいくつプールしておけばいいでしょうか？これは八分木の深さによります。それぞれの深さのノードがいくつ存在しうるかを考えてみましょう。

  • 深さ 0 -> ノード数 1
  • 深さ 1 -> ノード数 8
  • 深さ 2 -> ノード数 64
  • 深さ 3 -> ノード数 512
  • 深さ 4 -> ノード数 4096 (4K)
  • 深さ 5 -> ノード数 32768 (32K)
  • 深さ 6 -> ノード数 262144 (256K)
  • 深さ 7 -> ノード数 2097152 (2MB)
  • 深さ 8 -> ノード数 16777216 (16MB)


上で深さ4〜5で十分な画質が得られると書いたので、深さ4までキャッシュすることを考えてみましょう。深さ4までのノードを連続したアドレス空間に配置するために、順序付けを考えてみましょう。例えばこんな感じです。

  • 深さ 0 -> 0
  • 深さ 1 -> 1〜8 (1+n)
  • 深さ 2 -> 9〜72 (1+(1+n)*8 = 1+8+8*n)
  • 深さ 3 -> 73〜584 (1+8+(1+n)*64 = 1+8+64+64*n)
  • 深さ 4 -> 585〜4680 (1+8+64+(1+n)*512 = 1+8+64+512+512*n)


これで深さに応じた順序付けができました。簡単ですね。

パレットインデクス付の最適化

上記の処理で高速にパレットが生成できるようになりましたが、実際に減色された画像を得るには生成したパレットと画像を対応付ける必要があります。この画素はパレットでいうとどの色だ、という処理ですね。octreeは全ての画素を処理するまでパレットが決定されないので、効率的な逆引きが難しいのです。何の前提条件もない場合、近似色計算は画素毎にパレットの全エントリとの色空間の距離を調べて最も距離が小さいものを選択していくという処理になります。計算量はパレットのエントリ数をPとするとO(W*H*P)となります。またボクセル処理みたいになってます。ボクセル処理は禁止です。感覚的には、画素からハッシュ的にパレットのインデクスを求めることができれば高速に処理できそうな気がします。

*1:http://d.hatena.ne.jp/izariuo440/20120320/1332212854

*2:私が試した限りでは、ソートだけで最適化前のoctreeの処理よりも時間がかかってしまいましたが、画素数によってはソートの方が速いかもしれません

gyp でネイティブコードプロジェクトのビルドを多環境に対応させる

build programming

今回は「gyp でネイティブコードプロジェクトのビルドを多環境に対応させる」です。私がやっていることをメモしておきます。

背景

私は Windows のコードをよく書いていました。ある時から Android、Windows Mobile、Linux、Mac OS X、iOS でも動くように意識して書くようになりました。すぐに、コードをビルドするための各種設定ファイルを用意するのが面倒になりました。Visual Studio、Xcode、Makefile、Android NDK 用 Makefile・・・やっていられませんね。

ビルドツール巡り・・・cmake、scons、waf、そして gyp へ

ビルド設定ファイルを自動生成するためのビルドツールを探してみるとすぐにいくつか出てきました。半年ほど cmake と scons を並行運用していましたが、その中で気に入らない点が出てきました。

  1. ビルドはできるが Visual Studio、Xcode などのプロジェクトファイルが生成できない
    1. scons、waf などはこれ
  2. Visual Studio、Xcode のプロジェクトファイルが生成できるが中身がイマイチ
    1. cmake では、include ディレクトリがなぜか絶対パスだったりした
  3. プロジェクト間の設定の共有がイマイチ
    1. Android NDK の export の概念に相当するものがあったりなかったり
  4. Android NDK に対応していない
    1. 当時は cmake、scons、waf どれも対応してませんでした

この辺をすべてうまく対応してくれたのが、gyp*1 です。gyp は Google Chrome をはじめとした Google 製クライアントプログラムを中心に利用実績があります*2。Google 日本語入力のベースである mozc なんかもそうですね。node.js*3、その中で動いている v8*4、libuv なんかも gyp でビルドされるようになっています。ただし、gyp のスクリプトはPython 2.4 だと動かない*5ので、Cent OS など Python 2.4 が既定の環境では地味に辛いのですが、手でビルド設定ファイルを書くことに比べればささいな問題です。

gyp をプロジェクトに配置する

gyp はただの Python スクリプト群です。New BSD ライセンスなので、自分のプロジェクトに組み込んでしまうのが楽かもしれません。私の場合は、node.js を参考に以下のようにして運用しています。

  1. $PROJECT_ROOT/tools/gyp
    1. gyp 一式を配置する
  2. $PROJECT_ROOT/build/common.gypi
    1. 各プロジェクトの共通設定を書く
      1. Visual Studio のプロジェクト設定、Xcode のプロジェクト設定など
  3. $PROJECT_ROOT/configure.py
    1. gyp を呼び出してプロジェクトファイルを生成するスクリプトを書く
  4. $PROJECT_ROOT/README.md
    1. ビルド手順を書く

Android NDK 向けのテコ入れ

gyp が生成した Android NDK 用の Makefile でビルドすると、やたらと長いファイル名になってしまうので、私は以下のファイルを一部修正してファイル名が短くなるようにしています。

  1. $PROJECT_ROOT/tools/gyp/pylib/gyp/generator/android.py
    1. ComputeAndroidModule で return self.target するようにしている

まとめ

この記事には具体例がありませんが、Github の node.js のコードが何よりも雄弁です。

*1:https://code.google.com/p/gyp/

*2:gyp は Google Chrome などを他環境でビルドするための作られたもので、以前は scons でビルドされていました

*3:以前は waf でビルドされていました

*4:以前は scons でビルドされていました

*5:with など新しい構文を使っているため

tiny hash table

practice programming algorithm

Cでコードを書いているとハッシュテーブル*1が欲しくなることが多々あります。というわけで小さいのを書いてみました。

ハッシュテーブルについて

ハッシュテーブルは、あるキーをハッシュ関数を使ってマッピングし、それに対応する値を関連付けるためのデータ構造です。連想配列として使われたり、ハッシュマップと呼ばれたりもします。ハッシュ関数によってキーをインデックスに変換し（これをハッシュと呼ぶ）、それに対応する配列の要素（スロットまたはバケツと呼ばれる）に値を入れておきます。そこそこメモリを使いますが、その分高速に動作します。


探索において、木構造などの二分探索をベースとした実装では、キーの比較回数がlog2(N)となりますが、ハッシュテーブルでは大抵これよりも小さくなります。比較回数がこれよりも多くなるような状況、つまり衝突が多発する状況では、衝突が多発しないようなハッシュ関数を選択するか、バケツを大きくするか、木構造など二分探索をベースとした実装を用いるなどの回避策があります。ほぼWikipediaな内容ですみません。

thtblの特徴

  • ハッシュ関数は自分で用意する
  • キーバリューは分けずに自分で管理する
  • 内部にコピーを持たずにポインタによる参照のみ行う
  • 線形探査型(linear-probing)のオープンアドレス法(open-addressing)による衝突回避を行う
  • 多分環境依存しない
  • バケツが溢れそうでも自動伸長しない
  • バケツのサイズは素数ではなく2のNä¹—
  • 巡回や前要素削除が遅い

工夫したところ

オープンアドレス法だと、ポインタの管理とは別に、その値が「空」「削除済み」「使用中」を区別する必要があります。ポインタと他にマーキング用のデータを用意するのは面倒だしメモリも使いそうで嫌だったので、ポインタのアドレッシングの仕組みを利用してポインタのみで管理することにしました。大抵のOSでは、カーネルランドとユーザランドでそれぞれアドレス空間が分かれています。以下のページを見ると、大抵のOSではカーネルランドが大きい番地を占めていることが分かります。


というわけで、以下のように区別することにしました。私はカーネルランドで動作するものは書かないので。

  • 空 → NULL
  • 削除済み → 0xffffffff または 0xffffffffffffffffLLU
  • 使用中 → 上記以外


GNU hashtabというハッシュテーブルライブラリも似たようなことをしていて、mallocなどは1を返さないという前提の元に実装されています。小さい番地は大抵何らかのアプリのスタックが使っているので、確かにその前提はたいてい成立するんでしょうね。

実行結果

いくつかのハッシュ関数、いくつかのバケツの大きさで衝突させまくりで挿入だけベンチマークをとってみました。衝突率の低さだけが性能の決定的要素ではなく、比較関数のコストも重要な要素だよ、ということがよく分かる結果になっていますね。

128
string
searches: 128, collisions: 204 (1.593750%)
0.000243 [sec]
zackw
searches: 128, collisions: 416 (3.250000%)
0.000212 [sec]
FNV-1a
searches: 128, collisions: 51 (0.398438%)
0.000214 [sec]

1024
string
searches: 1024, collisions: 5048 (4.929688%)
0.001869 [sec]
zackw
searches: 1024, collisions: 1920 (1.875000%)
0.001591 [sec]
FNV-1a
searches: 1024, collisions: 503 (0.491211%)
0.001523 [sec]

8192
string
searches: 8192, collisions: 43510 (5.311279%)
0.013948 [sec]
zackw
searches: 8192, collisions: 51554 (6.293213%)
0.012849 [sec]
FNV-1a
searches: 8192, collisions: 3827 (0.467163%)
0.011939 [sec]

16384
string
searches: 16384, collisions: 849376 (51.841797%)
0.042020 [sec]
zackw
searches: 16384, collisions: 38040 (2.321777%)
0.024676 [sec]
FNV-1a
searches: 16384, collisions: 6266 (0.382446%)
0.024592 [sec]

32768
string
searches: 32768, collisions: 1692528 (51.651855%)
0.083191 [sec]
zackw
searches: 32768, collisions: 23370 (0.713196%)
0.047768 [sec]
FNV-1a
searches: 32768, collisions: 17951 (0.547821%)
0.049201 [sec]

65536
string
searches: 65536, collisions: 2047008 (31.234863%)
0.141463 [sec]
zackw
searches: 65536, collisions: 121870 (1.859589%)
0.098748 [sec]
FNV-1a
searches: 65536, collisions: 45944 (0.701050%)
0.100855 [sec]

1048576
string
searches: 1048576, collisions: 30468520 (29.057045%)
2.362834 [sec]
zackw
searches: 1048576, collisions: 3814406 (3.637701%)
1.755987 [sec]
FNV-1a
searches: 1048576, collisions: 515284 (0.491413%)
1.933815 [sec]

その他

実装にあたり参考にしたページなど。

*1:http://en.wikipedia.org/wiki/Hash_table

画像の色数を求めたりヒストグラムを作るためのソートをいろいろ実装してみた

algorithm practice programming

画像の色数を求めるにはハッシュ的なものを使うよりもソートした方が速いという話です。


また、ヒストグラムを高速に作ろうとすると色の深度に応じてメモリを食います。RGBそれぞれが8ビットだと64MBほどメモリを食います。対してソートでやろうとすると、画素数分だけで済むのでメモリ的にも優しいです。


そんなわけで、ソートです。上記ではクイックソートを使ってますが、クイックソートが最善手とは限りません。最近はメモリが豊富なので、バケツソートや分布数え上げソートや基数ソートも十分実用的です。どれがいいだろう、というわけでいくつか試してみました。クイックソート、分布数え上げソート、基数ソートを手持ちのMac Book Airで試してみました。コードはこちら。


4バイトの符合なし整数をソートするという簡単なコードです。以下のソートを比べています。

  • 標準Cライブラリのクイックソート
  • 手書きのクイックソート
  • 分布数え上げソート（最後のコピー処理がmemcpy）
  • 分布数え上げソート（最後のコピー処理がforループ）
  • 分布数え上げソート（最後のコピー処理がmemcpy、ポインタを使ってループを少し最適化）
  • 基数ソート（バイト単位）
  • 基数ソート（バイト単位、ポインタを使ってループを少し最適化）
  • 基数ソート（バイト単位、ポインタを使ってループをさらに最適化）
  • 基数ソート（ワード単位）


結果としては、概ねワード単位の基数ソートが最も速かったです。つうわけで、画像処理ではワード単位の基数ソートを使うのがよさそうです。基数ソートは少しだけ工夫しました。基数ソートでは、普通は単位毎に結果をコピーするのですが、ダブルバッファリングすることでその手間をなくしました。画素数が大きくなればなるほど効いてくるはずです。以下は、Mac Book Air 2.13 GHz Intel Core 2 Duo, Memory 4 GB 1067 MHz DDR3で実行した結果です。まずは実機での結果。

QVGA 24bpp 320x 240 (size = 76800, range = 16777216)
qsort : 0.023937 [sec]
quick_sort : 0.022483 [sec]
counting_sort : 0.211722 [sec]
counting_sort2 : 0.146360 [sec]
counting_sort3 : 0.133482 [sec]
radix_sort : 0.006259 [sec]
radix_sort2 : 0.005574 [sec]
radix_sort3 : 0.005545 [sec]
radix_sort4 : 0.004007 [sec]

VGA 24bpp 640x 480 (size = 307200, range = 16777216)
qsort : 0.105436 [sec]
quick_sort : 0.092361 [sec]
counting_sort : 0.184831 [sec]
counting_sort2 : 0.184686 [sec]
counting_sort3 : 0.169230 [sec]
radix_sort : 0.025758 [sec]
radix_sort2 : 0.024495 [sec]
radix_sort3 : 0.023203 [sec]
radix_sort4 : 0.015684 [sec]

XGA 24bpp 1024x 768 (size = 786432, range = 16777216)
qsort : 0.288884 [sec]
quick_sort : 0.260471 [sec]
counting_sort : 0.274694 [sec]
counting_sort2 : 0.272200 [sec]
counting_sort3 : 0.257774 [sec]
radix_sort : 0.069239 [sec]
radix_sort2 : 0.066146 [sec]
radix_sort3 : 0.060907 [sec]
radix_sort4 : 0.040482 [sec]

Nexus S 24bpp 480x 800 (size = 384000, range = 16777216)
qsort : 0.134426 [sec]
quick_sort : 0.118140 [sec]
counting_sort : 0.198503 [sec]
counting_sort2 : 0.198470 [sec]
counting_sort3 : 0.182864 [sec]
radix_sort : 0.033405 [sec]
radix_sort2 : 0.031146 [sec]
radix_sort3 : 0.029891 [sec]
radix_sort4 : 0.019964 [sec]

Mac Book Air 24bpp 1440x 900 (size = 1296000, range = 16777216)
qsort : 0.492288 [sec]
quick_sort : 0.439028 [sec]
counting_sort : 0.376246 [sec]
counting_sort2 : 0.370595 [sec]
counting_sort3 : 0.353696 [sec]
radix_sort : 0.113894 [sec]
radix_sort2 : 0.110131 [sec]
radix_sort3 : 0.102530 [sec]
radix_sort4 : 0.069099 [sec]

iMac 24bpp 2560x1440 (size = 3686400, range = 16777216)
qsort : 1.493648 [sec]
quick_sort : 1.320081 [sec]
counting_sort : 0.833016 [sec]
counting_sort2 : 0.819314 [sec]
counting_sort3 : 0.810189 [sec]
radix_sort : 0.332729 [sec]
radix_sort2 : 0.316817 [sec]
radix_sort3 : 0.292213 [sec]
radix_sort4 : 0.200232 [sec]

同じマシンでWindows XP on Virtual Boxで実行した結果がこちら。

QVGA 24bpp 320x 240 (size = 76800, range = 16777216)
qsort : 0.016000 [sec]
quick_sort : 0.000000 [sec]
counting_sort : 0.485000 [sec]
counting_sort2 : 0.765000 [sec]
counting_sort3 : 0.719000 [sec]
radix_sort : 0.000000 [sec]
radix_sort2 : 0.031000 [sec]
radix_sort3 : 0.000000 [sec]
radix_sort4 : 0.016000 [sec]

VGA 24bpp 640x 480 (size = 307200, range = 16777216)
qsort : 0.093000 [sec]
quick_sort : 0.047000 [sec]
counting_sort : 0.687000 [sec]
counting_sort2 : 0.844000 [sec]
counting_sort3 : 0.828000 [sec]
radix_sort : 0.062000 [sec]
radix_sort2 : 0.047000 [sec]
radix_sort3 : 0.047000 [sec]
radix_sort4 : 0.047000 [sec]

XGA 24bpp 1024x 768 (size = 786432, range = 16777216)
qsort : 0.234000 [sec]
quick_sort : 0.188000 [sec]
counting_sort : 0.656000 [sec]
counting_sort2 : 0.781000 [sec]
counting_sort3 : 0.812000 [sec]
radix_sort : 0.188000 [sec]
radix_sort2 : 0.235000 [sec]
radix_sort3 : 0.171000 [sec]
radix_sort4 : 0.109000 [sec]

Nexus S 24bpp 480x 800 (size = 384000, range = 16777216)
qsort : 0.125000 [sec]
quick_sort : 0.063000 [sec]
counting_sort : 0.625000 [sec]
counting_sort2 : 0.719000 [sec]
counting_sort3 : 0.813000 [sec]
radix_sort : 0.047000 [sec]
radix_sort2 : 0.046000 [sec]
radix_sort3 : 0.047000 [sec]
radix_sort4 : 0.047000 [sec]

Mac Book Air 24bpp 1440x 900 (size = 1296000, range = 16777216)
qsort : 0.359000 [sec]
quick_sort : 0.282000 [sec]
counting_sort : 0.563000 [sec]
counting_sort2 : 0.906000 [sec]
counting_sort3 : 0.969000 [sec]
radix_sort : 0.297000 [sec]
radix_sort2 : 0.281000 [sec]
radix_sort3 : 0.250000 [sec]
radix_sort4 : 0.156000 [sec]

iMac 24bpp 2560x1440 (size = 3686400, range = 16777216)
qsort : 0.719000 [sec]
quick_sort : 0.766000 [sec]
counting_sort : 0.765000 [sec]
counting_sort2 : 1.234000 [sec]
counting_sort3 : 1.188000 [sec]
radix_sort : 0.797000 [sec]
radix_sort2 : 0.640000 [sec]
radix_sort3 : 0.563000 [sec]
radix_sort4 : 0.390000 [sec]


次は、画像処理向けの高速なmemcmp、memcpy、bzeroあたりをやってみましょうかね。

bswap

programming

今日のコード。Windows XPとMac OS X 10.6.8で動作することを確認しています。


バイナリプログラミングをやっていると、エンディアンに応じてバイトオーダーをひっくり返す（バイトスワップ）というのがよくあります。バイトスワップは高速にやろうと思うと中々厄介で、マクロにすると分かりづらいし、ライブラリ関数にするとインライン展開が効かなくなります。というわけでいい方法がないのか少しだけ調べてみました。


ここまでのまとめ。

  • x86というか80486では、CPUにbswap命令があるのでこれを使うとよい*1
  • htonl、htons、ntohl、ntohs関数を使うとbswap命令を使ってくれることがある
  • Visual Studioのstdlib.hにはバイトスワップのための関数群が容易されている*2
  • ヘッダにコードを書いてしまえばインライン展開が効く


なかなか面倒そうだな、ということが分かりました。でも、こんなよくあることは誰かがうまいことやってくれているはずです。ということでさらに調べてみると、以下のようなコードが見つかりました。


コードを眺めてみると以下のようになっているようです。

  • ARM、x86、x86_64の場合は専用のCPU命令を呼び出す
  • ヘッダにコードを書いてインライン展開が効くようにしている
  • 知らないCPUに対しては普通にCのコードを呼び出す


Cだけで書くならこんな感じでヘッダに書くのが定石みたいですね。まるで魔法のようですが、自分で計算してもコンパイルして実行してもちゃんと動きます。特に、bswap_32。右シフトも左シフトも論理和も論理積もすべて二回ずつなのでとても美しい感じがします。

static inline uint16_t bswap_16(uint16_t x) {
  return (x >> 8) | (x << 8);
}

static inline uint32_t bswap_32(uint32_t x) {
  x= ((x << 8) & 0xFF00FF00) | ((x >> 8) & 0x00FF00FF);
  return (x >> 16) | (x << 16);
}

static inline uint64_t bswap_64(uint64_t x) {
    union {
        uint64_t ll;
        uint32_t l[2];
    } w, r;
    w.ll = x;
    r.l[0] = bswap_32 (w.l[1]);
    r.l[1] = bswap_32 (w.l[0]);
    return r.ll;
}

bswap_32、普通に考えたらこうですよね。

static inline uint32_t bswap_32(uint32_t x) {
  return
		(((x & 0x000000ff) >> 0x00) << 0x18) |
		(((x & 0x0000ff00) >> 0x08) << 0x10) |
		(((x & 0x00ff0000) >> 0x10) << 0x08) |
		(((x & 0xff000000) >> 0x18) << 0x00);
}

んで、こうなって・・・

static inline uint32_t bswap_32(uint32_t x) {
  return
		((x & 0x000000ff) << 0x18) |
		((x & 0x0000ff00) << 0x08) |
		((x & 0x00ff0000) >> 0x08) |
		((x & 0xff000000) >> 0x18);
}

こうですよね。

static inline uint32_t bswap_32(uint32_t x) {
  return
		(x << 0x18) |
		((x & 0x0000ff00) << 0x08) |
		((x & 0x00ff0000) >> 0x08) |
		(x >> 0x18);
}

さっきのbswap_32よりも、論理和が一回多くなります。それだけですけど、それを減らせるってのがさっきのbswap_32のすごいところ。Graphic Gems Iにはこういうことが一杯書いてありそうだな。

Graphics Gems (Graphics Gems - IBM)

Graphics Gems (Graphics Gems - IBM)

*1:https://sites.google.com/site/instructionsx86/bswap

*2:http://msdn.microsoft.com/ja-jp/library/a3140177(v=vs.80).aspx

Topological sort

practice algorithm

トポロジカルソート*1を書いてみました。C言語、D言語、Lua、Rubyで。


トポロジカルソートが何に使えるかというと、makeの依存性解決などで使えます。yamakeというビルドシステムを作る上で、参考にしているシステムとしてninja*2のソースコードを見ていたのですが、自分でもできそうだと思ってやってみました。ninjaではトポロジカルソートっぽいことはやってませんが。


実装は簡単でしたが、依存性解決にトポロジカルソートが使えるということを探すまでに少し時間がかかりました。最初は循環参照検出*3のFloyd's cycle-finding algorithmにたどり着きましたが、makeの依存性のような二次のものには対応できないのでさらに探していたらなんとか見つかったという感じです。

*1:http://en.wikipedia.org/wiki/Topological_sorting

*2:http://martine.github.com/ninja/

*3:http://en.wikipedia.org/wiki/Cycle_detection