講題：Android Game Engine 比較
講題：Be "Android"
講題：打造特製的 Android Toolchain延續筆者去年的紀錄「當 Compiler 遇上 Mobile」，最近我們又獲得一些進展，是在 Android 的 Dalvik 虛擬機器環境中，引入 pre-compiled class 的實驗，除了可改善執行時期的效能、記憶體使用量外，另外就是避免在「反組譯並修改 Android 應用程式實例」一文可見的資訊保護議題。
其實十幾年前，在 Java 平台中就有相當多團隊提出可行的方案，而世界上第一個開放原始碼的 Kaffe 虛擬機器專案，早在 1999 年即提出實做 "Kaffe/GCJ integration"，成功地將 GCJ (GCC for Java) 自 Java class/source 編譯得到的機械碼，當作 pre-compiled shared library，讓 Kaffee VM 讀取，預期可有效改善執行效能並縮減起始時間。GNU Classpath 專案主持人 Mark Wielaard 在 LWN 的文章 "GCJ - past, present, and future" 提到相關的歷史與技術背景，最早可回溯到 Cygnus solutions 時期 (RedHat 尚未併購) 的 GCJ 計畫提案 -- "A Gcc-based Java Implementation"。
為了降低實做的複雜度，筆者最早採用 LLVM 與 IcedTea 作為系統框架，不過一直到今年春節，整體進度還是陷入膠著的狀態。現在則引入 Java2C 搭配 PGO (Profile-Guided Optimization) 與統計模型，嘗試分析運行於 Dalvik VM 的 Android activity / system server，佔用系統資源最頻繁的項目，並預先編譯 (pre-compile) 這些 class/method，居中透過 JNI (Java Native Interface) 讓 Dalvik VM 存取。不過，實務上來說，不是將所有 class/method 都編譯為原生機械碼，就會帶來效能提昇，相反地，後者往往讓系統陷入更差的效能。目前 Eclair 裡面的 Dalvik VM 雖然沒有完整的 JIT compiler，但其 fast interpreter for ARM 的確做了頗多 threaded interpreter 的改進，考量到 I-cache, paging, 與 branch prediction，若我們不思量 Java / Android Dalvik 應用程式的執行時期行為，只是一味作編譯轉換，很可能只是編譯極少被執行，或者完全不會被執行到的程式碼，因此加重執行時期的負擔，而最該被優化的部份，受限於不完整的 source-to-source 轉換，有顧此失彼的疑慮。
於是，找出系統中最該被優化的部份，並考量到正確性與相容度，就是我們的首要研究議題，筆者採用知名的 SciMark 2.0 作為量化分析的指標。以下是在 Qualcomm MSM7x25 硬體平台 (arm1136j-s) 的效能評比，ARM11 的時脈是 528 MHz，ARM Linux 版本為 2.6.29.6-0xlab：
由上可見，在 SciMark 2.0 的各項評比中，Pre-compiled class 執行效能都較 Android Dalvik fast interpreter for ARM 給予一定程度的改良，並且透過 FDO (Feedback Directed Optimization)，大多可進一步給予提昇。這僅是初步的整合實驗數據，還需要更多分析與進行實做。
為了某個實驗的動機，我們評估反編譯 Android 應用程式的可行性，本文即是筆者的心得與實際的範例，僅供參考。就筆者的認知，目前還沒有針對 Android 的 DEX to Java source 反編譯工具，可實際處理一般的 Android 應用程式，多半要繞幾圈，還會得到不甚理想的結果，不過，smali 這個反組譯工具，已是可用了，只是得對付類似 Jasmin 語法的 Dalvik 組合語言。筆者打包了 smali 與 Frozen Bubble for Android，作為示範：
$ adb install -r FrozenBubble-orig.apk
當然，沒必要讓筆者置喙談如何玩這個經典遊戲，不過我們倒是想更改原本的行為。在進行之前，我們先來複習 Android APK 的建立，參考 "How to build Android application package (.apk) from the command line using the SDK tools + continuously integrated using CruiseControl." 一文，我們可從以下圖表知悉細部的流程：
假設我們完全無法取得原始程式碼，該如何進行呢？沒錯，就透過 smali，簡化繁瑣的流程，筆者包裝為 Makefile，所以只要先解開並反組譯：$ make extract這時候會看到兩個目錄：
smali-src$ find就忠實地依據 Java package 的方式呈現，檔名結尾是 ".smali"。筆者的修改目標是，讓一開始的關卡 (Level) 從第一關直接跳躍到第五關。在 smali 原始程式碼 (注意：這完全不同於 Java 原始程式碼，而是極為貼近 Dalvik VM 所接受的 DEX 檔案的組合語言形式) 搜尋 "Level" 字眼，可發現主要的分佈就落於兩個檔案：
./org/jfedor/frozenbubble/FrozenBubble.smali
./org/jfedor/frozenbubble/R$id.smali
./org/jfedor/frozenbubble/GameView.smali
./org/jfedor/frozenbubble/SoundManager.smali
./org/jfedor/frozenbubble/LaunchBubbleSprite.smali
./org/jfedor/frozenbubble/Compressor.smali
./org/jfedor/frozenbubble/R$attr.smali
./org/jfedor/frozenbubble/BubbleFont.smali
./org/jfedor/frozenbubble/PenguinSprite.smali
./org/jfedor/frozenbubble/GameView$GameThread.smali
./org/jfedor/frozenbubble/BubbleSprite.smali./org/jfedor/frozenbubble/R$string.smali
./org/jfedor/frozenbubble/R$drawable.smali
./org/jfedor/frozenbubble/ImageSprite.smali
./org/jfedor/frozenbubble/BubbleManager.smali
./org/jfedor/frozenbubble/GameScreen.smali
./org/jfedor/frozenbubble/R.smali
./org/jfedor/frozenbubble/R$layout.smali
./org/jfedor/frozenbubble/BmpWrap.smali./org/jfedor/frozenbubble/FrozenGame.smali
./org/jfedor/frozenbubble/Sprite.smali
./org/jfedor/frozenbubble/LevelManager.smali
./org/jfedor/frozenbubble/R$raw.smali
smali-src$ grep "\.method" org/jfedor/frozenbubble/LevelManager.smali倘若我們以 "goToFirstLevel" 一類的關鍵字，在 org/jfedor/frozenbubble/GameView$GameThread.smali 檔案中搜尋，可找出有具體的呼叫行為：
.method public constructor <init>([BI)V
.method private getLevel(Ljava/lang/String;)[[B
.method public getCurrentLevel()[[B
.method public getLevelIndex()I
.method public goToFirstLevel()V
.method public goToNextLevel()V.method public restoreState(Landroid/os/Bundle;)V
.method public saveState(Landroid/os/Bundle;)V
smali-src$ grep -r goToFirstLevel *由此更確定我們之前的猜想。其中組合語言寫為以下：
org/jfedor/frozenbubble/GameView$GameThread.smali: invoke-virtual {v2}, Lorg/jfedor/frozenbubble/LevelManager;->goToFirstLevel()V
org/jfedor/frozenbubble/LevelManager.smali:.method public goToFirstLevel()V
move-object/from16 v0, p0不要被貌似複雜的語法嚇到了，基本上掌握 Java 程式語言的原則 "Everything is Object" (不過仍有提供 primitive type)，組合語言仍會作 Java Object 的實體化 (instantialization)，Dalvik 本身是 Register-based Virtual Machine，而扣除 static/class method 外，Java 中所有的 method invocation 多為 virtual function (對應於 C++ 的觀點，才能更具體用機械方式思考)，所以組合語言的指令為 "invoke-virtual" (注意有連字號，此與 Java bytecode 不同)，"{v2}" 表示第一受者的 Register，此為 Object 本體。接著，與 Java bytecode 一樣，"Lorg/jfedor/frozenbubble/LevelManager;" 就表示 Java 層面的 class "org.jfedor.frozenbubble.LevelManager"，字母 "L" 即為 class 的識別，而 "->" 就很直觀了，自然是 method invocation，所以連貫來看，這一段組合語言的 Java 意思為：
iget-object v0, v0, Lorg/jfedor/frozenbubble/GameView$GameThread;->mLevelManager:Lorg/jfedor/frozenbubble/LevelManager;
move-object v2, v0
invoke-virtual {v2}, Lorg/jfedor/frozenbubble/LevelManager;->goToFirstLevel()V
objectLevelManager.goToFirstLevel();其中 objectLevelManager 是一個 class LevelManager 的實例/實體 (instance)。倘若需要在 method invocation 時，帶入參數，那麼前述的 "{v2}" 一般會被替換為 "{v0, v1, v2, ...} 的 register 列表。關於詳細的狀況，可參考 Dalvik 非官方說明，另外 smali 的 wiki 也提供一些範例，可多加利用。
const-string v3, "level"在上述程式碼列表中，"Lorg/jfedor/frozenbubble/LevelManager;-><init>" 表示呼叫 class LevelManager 的 constructor，也就是 "<init>"。注意到 method invocation 方式就不同了，是 "invoke-direct"，表示 class constructor，而這之前要有 "new-instance v3, Lorg/jfedor/frozenbubble/LevelManager;" 的組合語言指令宣告。
const/4 v4, 0x0
move-object/from16 v0, v25 move-object v1, v3
move v2, v4
invoke-interface {v0, v1, v2}, Landroid/content/SharedPreferences;->getInt(Ljava/lang/String;I)I
move-result p4
new-instance v3, Lorg/jfedor/frozenbubble/LevelManager;
move-object v0, v3
move-object/from16 v1, v22
move/from16 v2, p4 invoke-direct {v0, v1, v2}, Lorg/jfedor/frozenbubble/LevelManager;-><init>([BI)V
const-string v3, "level"顯然，Register v1 還被帶入到 android.content.Shared.Preference.getInt() method，而更早以前，其內含值被設定為 Register v3 的值，也就是常數字串 (const-string) "level"，這好像與我們的焦點不同。另外，像是 Register v22 這個編號較大的 register，表示 local variable，這點需要多留意，因為 Java 程式設計的規範來說，往往會將程式切割為若干 method，而 method 實做體中，又有極多的 local variable，於是往往可從組合語言反推 Java 原始碼的型態。
const/4 v4, 0x0
move-object/from16 v0, v25
move-object v1, v3
move v2, v4
invoke-interface {v0, v1, v2}, Landroid/content/SharedPreferences;->getInt(Ljava/lang/String;I)I
move-result p4
new-instance v3, Lorg/jfedor/frozenbubble/LevelManager;
move-object v0, v3
move-object/from16 v1, v22
move/from16 v2, p4
invoke-direct {v0, v1, v2}, Lorg/jfedor/frozenbubble/LevelManager;-><init>([BI)V
const-string v3, "level"這個 Register v4 的內含值 "0x0" 會指派到 Register v2 中，而讓我們似乎找到方向了，回頭看看 class org.jfedor.frozenbubble.LevelManager 的 constructor 宣告方式： (之前 grep 結果的第一行)
const/4 v4, 0x0
move-object/from16 v0, v25
move-object v1, v3
move v2, v4
invoke-interface {v0, v1, v2}, Landroid/content/SharedPreferences;->getInt(Ljava/lang/String;I)I
move-result p4
new-instance v3, Lorg/jfedor/frozenbubble/LevelManager;
move-object v0, v3
move-object/from16 v1, v22
move/from16 v2, p4
invoke-direct {v0, v1, v2}, Lorg/jfedor/frozenbubble/LevelManager;-><init>([BI)V
smali-src$ grep "\.method" org/jfedor/frozenbubble/LevelManager.smali其中 "public" 是 ACL (存取權限) 的宣告，而 constructor 的符號規範為 "<init>"，注意到括號 "(" 與 ")" 裡面的兩個大寫字母，表示接受兩個參數，對應的型態為：
.method public constructor <init>([BI)V
invoke-interface {v0, v1, v2}, Landroid/content/SharedPreferences;->getInt(Ljava/lang/String;I)I"p4" 用以保存 method invocation 之後的回傳值，顯然，Register v2 受到 p4 的指派，也就是被更動為 android.content.Shared.Preference.getInt() method 的回傳值，這存在不確定性，於是，我們乾脆一口氣改掉： (修改的部份會用井字號 "#" 作註解)
move-result p4
new-instance v3, Lorg/jfedor/frozenbubble/LevelManager;
move-object v0, v3
move-object/from16 v1, v22
move/from16 v2, p4
# Modified from 0x0 to 0x4"改好程式，當然要驗證，回到上一層目錄，透過 smali 提供的組譯器，重新產生 Dalvik DEX 輸出，為了簡化流程，筆者把 smali, apkbuilder, aapt, adb install 都一次整合進去，所以會直接讓 Android Emulator 生效，來看看我們的戰果吧：
const/4 v4, 0x4
move-object/from16 v0, v25
move-object v1, v3
move v2, v4
# Modified: removed the following 2 lines
# invoke-interface {v0, v1, v2}, Landroid/content/SharedPreferences;->getInt(Ljava/lang/String;I)I
# move-result p4
new-instance v3, Lorg/jfedor/frozenbubble/LevelManager;
move-object v0, v3
move-object/from16 v1, v22
# Modified: removed the following 1 line
# move/from16 v2, p4
invoke-direct {v0, v1, v2}, Lorg/jfedor/frozenbubble/LevelManager;-><init>([BI)V
注意到左下角，這表示我們成功了，完全不用取得 Java 原始程式碼，就可以作反組譯並且修改的動作。很多人從事 Android 移植，但連 Android Toolchain 都自行維護者，相對就少多了。筆者過去有幸在「台灣心」計畫中，從事建構於台灣自主 CPU 的軟體開發，嘗試從零到有，將 Android 移植到 Andes NDS32 架構，就涉及到 Toolchain 的更動。而維護 0xdroid 與對應 0xlab 的 GNU Toolchain，不免會迷失於眾多的原始程式碼，只好靜下心慢慢探索，沒想到因此挖掘到頗多「寶物」，本文簡記備忘使用。
Google 工程師 Jing Yu 於 Jan 18, 2010 提交一份修改 "Bring gcc-4.4.0 to up-to-date"，讓人摸不著頭緒，不過其對於 GCC 的 architecture 更動，追加了新項目，可參見檔案 gcc-4.4.0/gcc/config/linux-grtev1.h 。以下節錄開頭註解：
/* Definitions for Linux-based GRTE (Google RunTime Environment) version 1.這個以 Linux 為基礎的 GRTE 到底是什麼呢？沒獲得解答，只好在其 gcc spec 檔中探索，以下是相關的描述：
Copyright (C) 2009 Free Software Foundation, Inc.
Contributed by Chris Demetriou.
This file is part of GCC.
/* When GRTE links statically, it needs its NSS and resolver libraries這裡的 libc 看來是獨立的 C Library 實做，比較有趣的是 libnss 的部份。libnss 可透過外部的 module 作擴充，比方說 libnss-ldap 就是 "NSS module for using LDAP as a naming service"，而前述 gcc spec 提及當進行靜態編譯時，需要將所需的 module 一併連結，那麼，這系列 libnss_ 開頭的函式庫，顯然就是 GRTE (Google RunTime Environment) 所需的基礎建設。來看看有哪些特別的：
linked in as well. Note that when linking statically, these are
enclosed in a group by LINK_GCC_C_SEQUENCE_SPEC. */
#undef LINUX_GRTE_EXTRA_SPECS
#define LINUX_GRTE_EXTRA_SPECS \
{ "libc", "%{static:%(libc_static);:-lc}" }, \
{ "libc_p", "%{static:%(libc_p_static);:-lc_p}" }, \
{ "libc_static", \
"-lc -lnss_borg -lnss_cache -lnss_dns -lnss_files -lresolv" }, \
{ "libc_p_static", \
"-lc_p -lnss_borg_p -lnss_cache_p -lnss_dns_p -lnss_files_p -lresolv_p" },
沈寂的一段時間，現在 0xdroid 又恢復活躍的開發。正如稍早在 0xlab-devel 郵件討論區提及 "Return back to open source world"，我們陸續將之前開發的成果，貢獻到自由軟體的世界，環繞在 0xdroid 的項目有：
(0xdroid 的桌面與 Launcher)
(調整為直式顯示，符合原本 Android 的預期輸出假設)
目前支援 Android Donut 與 Eclair，在 0xdroid 即是 beagle-donut 與 beagle-eclair，需要搭配最新的 0xlab-kernel，對 DevKit8000 週邊做出更好的支援。以下是簡要的功能特徵描述：Android 2.0 (Eclair) 原始程式碼已於一個月前釋出，在目錄 system/core 下有個 libacc 的子項目，這是開發者修改自 Fabrice Bellard 的大作 OTCC (Obfuscated Tiny C Compiler)，以 C++ 與 Android 的執行時期函式庫重寫。libacc 的功能是提供給 Android 2.0 的 RenderScript 一個 C-like 語法的描述，如此一來，開發者可撰寫高效能的視覺效果與動畫，不過這部份並未完成，詳情可參考 "Android renderscript, more info' and an example application" 一文。
關於 libacc 的整合部份，可參考 frameworks/base/libs/rs 目錄下的兩個檔案：
libacc 的 Code generator 支援以下硬體架構：libacc$ make
g++ -I./include -DHAVE_PTHREADS -c acc.cpp
gcc -I./include -DHAVE_PTHREADS -c hashmap.c
gcc -I./include -DHAVE_PTHREADS -c logd_write.c
g++ -I./include -DHAVE_PTHREADS -c tests/main.cpp
g++ -I./include -DHAVE_PTHREADS -c tests/runtimeTest.cpp
g++ -o main \
acc.o \
hashmap.o \
logd_write.o \
main.o \
-ldl
g++ -o runtimeTest \
acc.o \
hashmap.o \
logd_write.o \
runtimeTest.o \
-ldl
其中 tests/data/hello.c 的內容為：libacc$ ./main -R tests/data/hello.c
Executing compiled code:
Hello, world
result: 0
若平台是 ARM 的話，還可以支援反組譯輸出，libacc 是 RenderScript 背後很重要的基礎建設，允許動態編譯 Android Graphics 的 RenderScript，輸出成機械碼並執行。參考檔案 tests/runtimeTest.cpp 可得知 RenderScript 的寫法，整個 libacc 可內嵌於程式中，比方說：libacc$ cat tests/data/hello.c
int main() {
printf("Hello, world\n");
return 0;
}
這個字串經過 libacc 的函式呼叫後，可得到以下的編譯與執行結果：const char* text = "void op_int(int a);\n"
"void op_float12(float a, float b, float c, float d,\n"
" float e, float f, float g, float h,\n"
" float i, float j, float k, float l);\n"
"void script() {\n"
" globalVar += 3;\n"
" op_int(123);\n"
" op_float12(1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0);\n"
"}\n";
目錄 tests 還包含可在 Android 環境執行的自動測試 Python script。 read onlibacc$ ./runtimeTest
Executing script:
op_int(123)
op_float12(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
After script globalVar = 20
最近 0xlab 的開發者持續改善 0xdroid，在 gitorious 的團隊排名維持在前五名的活躍程度，除了稍早提及針對 ARMv7 與底層軟體架構的改進外，0xdroid 也加入了對 Beagleboard / TI OMAP3 硬體更充分的支援。現在與多媒體處理相關的架構圖可參考以下：
紅色的部份是 Android 的 framework 層面 (Media framework, Media server)，而藍色則是實做 framework 所需服務的元件 (如 OpenCore)，剩下綠色的地方自然是 0xlab 關注、與硬體平台相關的元件，這裡簡要列出：
