Levels in Renderscript（超訳）
Levels in RenderscriptというRenderscriptを解説した記事が本家に上がったので、久々に超訳。誤訳などあればご指摘を。
ICSではRenderscript(RS)がアップデートされた。いくつかの新しい機能が加えられ、アプリケーションで計算を簡単に高速化出来るようになっている。大量の処理が必要な大きなデータバッファがある場合、計算の高速化のためにRSは興味深い。この例ではレベル／サチュレーション処理をビットマップに施してみる。
この場合、サチュレーションはすべてのピクセルと色行列のかけ算として実装され、レベルはいくつかの演算で実装されるのが常套だ。
1. 入力レベルの調整
2. ガンマ補正
3. 出力レベルの調整
4. 有効値へのクランプ
単純な実装はこのようになる。
for (int i=0; i < mInPixels.length; i++) {
float r = (float)(mInPixels[i] & 0xff);
float g = (float)((mInPixels[i] >> 8) & 0xff);
float b = (float)((mInPixels[i] >> 16) & 0xff);
float tr = r * m[0] + g * m[3] + b * m[6];
float tg = r * m[1] + g * m[4] + b * m[7];
float tb = r * m[2] + g * m[5] + b * m[8];
r = tr;
g = tg;
b = tb;
if (r < 0.f) r = 0.f;
if (r > 255.f) r = 255.f;
if (g < 0.f) g = 0.f;
if (g > 255.f) g = 255.f;
if (b < 0.f) b = 0.f;
if (b > 255.f) b = 255.f;
r = (r - mInBlack) * mOverInWMinInB;
g = (g - mInBlack) * mOverInWMinInB;
b = (b - mInBlack) * mOverInWMinInB;
if (mGamma != 1.0f) {
r = (float)java.lang.Math.pow(r, mGamma);
g = (float)java.lang.Math.pow(g, mGamma);
b = (float)java.lang.Math.pow(b, mGamma);
}
r = (r * mOutWMinOutB) + mOutBlack;
g = (g * mOutWMinOutB) + mOutBlack;
b = (b * mOutWMinOutB) + mOutBlack;
if (r < 0.f) r = 0.f;
if (r > 255.f) r = 255.f;
if (g < 0.f) g = 0.f;
if (g > 255.f) g = 255.f;
if (b < 0.f) b = 0.f;
if (b > 255.f) b = 255.f;
mOutPixels[i] = ((int)r) + (((int)g) << 8) + (((int)b) << 16)
+ (mInPixels[i] & 0xff000000);
}
このコードはビットマップがすでにロードされていて、処理のために整数配列に移されていることを想定している。ビットマップはすでにロードされているので、これは簡単だ。
mInPixels = new int[mBitmapIn.getHeight() * mBitmapIn.getWidth()];
mOutPixels = new int[mBitmapOut.getHeight() * mBitmapOut.getWidth()];
mBitmapIn.getPixels(mInPixels, 0, mBitmapIn.getWidth(), 0, 0,
mBitmapIn.getWidth(), mBitmapIn.getHeight());
データ処理のループが終われば、描画のためにビットマップに戻すことも簡単だ。
mBitmapOut.setPixels(mOutPixels, 0, mBitmapOut.getWidth(), 0, 0,
mBitmapOut.getWidth(), mBitmapOut.getHeight());
フィルター本体の定数計算や、（ボタンなどの）コントロールの制御、画像表示などのコードを含めて、アプリケーション全体のコード量は232行程度になる。手元の実機では800x423の画像処理におおよそ140-180msecかかる。
もしこれで十分でなかったらどうする？
画像処理のコア部分をRSに移植するのはとても簡単だ。上記のピクセル処理本体をRSで実装しなおすとこうなる。コードはhttp://code.google.com/p/android-renderscript-samples/source/browse/Levelsにある。
void root(const uchar4 *in, uchar4 *out, uint32_t x, uint32_t y) {
float3 pixel = convert_float4(in[0]).rgb; // 3要素ベクトル
pixel = rsMatrixMultiply(&colorMat, pixel); // ライブラリ関数
pixel = clamp(pixel, 0.f, 255.f); // ライブラリ関数
pixel = (pixel - inBlack) * overInWMinInB; // ベクトル演算
if (gamma != 1.0f)
pixel = pow(pixel, (float3)gamma); // ライブラリ関数
pixel = pixel * outWMinOutB + outBlack; // ベクトル演算
pixel = clamp(pixel, 0.f, 255.f); // ライブラリ関数
out->xyz = convert_uchar3(pixel); // ライブラリ関数
}
コード行数が極端に少なくて済むのは、浮動小数点のベクトルや行列演算、フォーマット変換があらかじめ組み込まれているからだ。また、ループが存在しないことに着目して欲しい。
準備のためのコードは、スクリプトをロードする必要があるので、ほんの少し複雑になる。
mRS = RenderScript.create(this);
mInPixelsAllocation = Allocation.createFromBitmap(mRS, mBitmapIn,
Allocation.MipmapControl.MIPMAP_NONE,
Allocation.USAGE_SCRIPT);
mOutPixelsAllocation = Allocation.createFromBitmap(mRS, mBitmapOut,
Allocation.MipmapControl.MIPMAP_NONE,
Allocation.USAGE_SCRIPT);
mScript = new ScriptC_levels(mRS, getResources(), R.raw.levels);
このコードはRSのコンテキストを生成している。続いて、2つのメモリアロケーションをこのコンテキストを使って生成し、ビットマップデータのRS用コピーを保持する。最後にデータ処理のためにスクリプトをロードする。
ソースコードには、他にもいくつか小さなコードの塊があり、定数に変更があった時に計算し直してスクリプトへコピーしている。グローバル変数はスクリプトからリフレクションされているので、簡単に行える。
mScript.set_inBlack(mInBlack);
mScript.set_outBlack(mOutBlack);
mScript.set_inWMinInB(mInWMinInB);
mScript.set_outWMinOutB(mOutWMinOutB);
mScript.set_overInWMinInB(mOverInWMinInB);
先に述べたように、すべてのピクセルを処理するためのループがない。ビットマップデータを処理し、結果をコピーするRSコードはこうなる。
mScript.forEach_root(mInPixelsAllocation, mOutPixelsAllocation);
mOutPixelsAllocation.copyTo(mBitmapOut);
最初の行はスクリプトと入力アロケーションを取り出して、結果を保持する出力アロケーションを設定している。たったこれだけで、ネイティブにコンパイルされたバージョンのスクリプトを、アロケーションに入っているすべてのピクセルに対して、1つづつ一度だけ呼び出す。しかし、Dalvikの実装とは異なり、プリミティブ（コンパイルされたスクリプト）は自動的に複数のスレッドを生成して処理を行う。ネイティブコードの効率と合わさることで、大きなパフォーマンス向上を生んでいる。ガンマ関数のありなしで計算コストが大きく異なるので、両方の結果を下に示す。
800x423の画像
| Device | Dalvik | RS | Gain |
| Xoom | 174ms | 39ms | 4.5x |
| Galaxy Nexus | 139ms | 30ms | 4.6x |
| Tegra 30 device | 136ms | 19ms | 7.2x |
ガンマ補正を加えた場合の800x423の画像
| Device | Dalvik | RS | Gain |
| Xoom | 994ms | 259ms | 3.8x |
| Galaxy Nexus | 787ms | 213ms | 3.7x |
| Tegra 30 device | 783ms | 104ms | 7.5x |
ゲインが大きいほど、簡単なコーディングで得られる見返りが大きいことを示す。
訳注: Xoom, GN, Tegra 3というのは理にかなった選択。
Xoom: 2コア、VFP3
GN: 2コア、NEON
Tegra 3: 4コア、NEON
Tegra 30というのは、単なる記憶違いもしくはTegra 3が正式名称になるまえに30と呼び習わしていたのかもしれない。
DevQuiz 2011 - スライドパズル
DevQuiz 2011 - 一人ゲーム
解答晒し。やや長いのでpatebin。
- まず、ロボット的に最短に近い手数を出す。（ruledengine）
- 奇数かつ5で割り切れる数が1以上なら、取り除く（evalremove5）
- それ以外は半分
- 繰り返せば最短に近い手数が出そう
- ロボットが出した手数まで全探索（walkaroundengine）
- 単純な2分木探索
- 取り除かれた数字には-1をいれておくことで、配列のコピーを避ける
DevQuiz 2011 - Go
解答晒し。誰が書いても似た様になるだろうけど。
１つだけ疑問。オリジナルのCountColorの引数がpngになっていたけど、image/pngをimportした時に、名前が衝突してpng.Decode()が呼び出せない。io.Readerの変数名がpngというのも気持ち悪いのでsrcに変更したけど、本当はどうすべきだったのか*1。
package main import ( "fmt" "io" "strings" "image" "image/png" /* add more */ ) func rgbaToInt(s image.Color) uint32 { r, g, b, a := s.RGBA() i32 := r + g<<8 + b<<16 + a<<24 return i32 } func CountColor(src io.Reader) int { hash := make(map[uint32] int) dec, e := png.Decode(src) if e != nil { fmt.Println(e) return -1 } for y := dec.Bounds().Min.Y; y < dec.Bounds().Max.Y; y++ { for x := dec.Bounds().Min.X; x < dec.Bounds().Max.X; x++ { color := dec.At(x, y) if hash[rgbaToInt(color)] != 1 { hash[rgbaToInt(color)] = 1 } } } return len(hash) } /* これらの関数は提出時に自動挿入されます。 */ func main() { png := GetPngBinary() cnt := CountColor(png) fmt.Println(cnt) }
google-preftoolsでプロファイリング
DevQuizのスライドパズルでプロファイラを使ってみたのでメモ。
google-perftools*1はUbuntuにパッケージがある。
$ sudo apt-get install google-perftools
pprofコマンドはgoogle-pprof。gddslideが今回のターゲット。
$ export CPUPROFILE=prof.out $ LD_PRELOAD=/usr/lib/libprofiler.so.0 ./gddslide $ google-pprof --dot gddslide prof.out > prof.dot $ dot -T png prof.dot > prof.png
これでPNGファイルになる。線形検索をしているので、それが大半という結果。どうしてくれようか。
Build済みmasterツリーでのrepo sync
いつも通りAndroidのソースツリーをrepo syncしてみたら、masterツリーでerrorが出た。
error: You have local changes to 'android/avd/hw-config-defs.h'; cannot switch branches.
error: external/qemu/: platform/external/qemu checkout d02b30ee5bfc925dd8e031c193c17672e500fd18
こんなファイルをいじった記憶はない。何が違うかgit diffしてみた。
$ git diff diff --git a/android/avd/hw-config-defs.h b/android/avd/hw-config-defs.h index bb523d5..c3f3f41 100644 --- a/android/avd/hw-config-defs.h +++ b/android/avd/hw-config-defs.h @@ -197,7 +197,7 @@ HWCFG_INT( "hw.lcd.density", 160, "Abstracted LCD density", - "Must be one of 120, 160 or 240. A value used to roughly describe the densit y + "Must be one of 120 / 160 / 240 / 213/ 320. A value used to roughly describe
意味がわからないよ。headで見てみた。
/* this file is automatically generated from 'hardware-properties.ini' * DO NOT EDIT IT. To re-generate it, use android/tools/gen-hw-config.py' */
ということらしい。gitのログをWeb*1で確認したら、該当ファイルが消されてた。ダメ元で
$ pushd external/qemu $ git reset --hard HEAD is now at 83c8f4e Merge "Fix -audioand -no-audio processing." $ popd $ repo sync Fetching projects: 100% (183/183), done.
でresetしてみたら、正常にsync出来た。ということでメモ。
