Posted by Lawpig on 6月 01, 2017 | No comments

Android筆記 – 從DEX檔案格式看Dalvik的運作

Android筆記 – 從DEX檔案格式看Dalvik的運作

hlchou@mail2000.com.tw
by loda

記得剛投入系統軟體領域時,透過一些文章（當年Microsoft Systems Journal算是很補的技術雜誌.),知道DOS的MZ(以DOS開發者 Mark Zbikowski的縮寫命名)檔案格式,也藉此了解在DOS時代使用Memory Segment與.com跟.exe檔案的差異,隨後,Windows 3.1推出,NE(New Executable) 執行檔,VxD LE( Linear Executable)驅動程式與之後的Windows 9x/ME/NT/2000/XP 的PE(Portable Executable)檔案格式,是有志於了解動態函式庫DLL,Windows應用與核心跟反組譯Hacking時,所必備的基礎知識. 到了Linux/Unix的環境時,ELF(Executable and Linkable Format) 也是從事開發前,從反組譯工具,到了解系統運作時,可以深化系統觀點的知識背景.

也因此,在開發Android相關產品時,了解Dalvik DEX檔案格式,也應是個值得深入探究的資訊,並藉此了解在Dalvik系統的底層與檔案格式中,所提供的資訊,在評估系統改善項目時,這些資訊就能幫助我們有足夠的背景做出適當的判斷與設計建議.

同樣的,筆者會盡力確保所提供的訊息正確性,然可能因為Android本身的改版,與筆者有限的知識,若有不盡完美之處,也歡迎給予指教.

關心Android發展的人,也可以透過這個連結http://code.google.com/p/android/issues/list# 了解目前相關Issue的狀況,同時,也推薦一個很不錯的 Dalvik Talk “Android: Dalvik VM Internals — Google 2008 台北程式開發日” ,講者為程本中,目前是Android團隊的一員,Youtube網址是在http://www.youtube.com/watch?v=FsNKIo4bIro&feature=player_embedded#at=26 .

透過DEX檔案格式的支援,相比過去的作法,筆者認為可以有如下的好處

1, 同類型的String (例如: lang/…/string)可以只存在一份,然後透過 Index對應,節省為數可觀的儲存空間

2, 可以把屬於同一個應用的Class檔案,整合在同一個DEX檔案中,有利於儲存空間與個別應用的管理

3, 支援Optimized DEX格式,只要曾在載入或是安裝時執行過最佳化流程,就可以保留該次的結果,加速下一次的執行. (只限於驗證與最佳化, JIT每次只要重新啟動就會重新執行)

一個經過優化過的DEX檔案,前面會加上40bytes的ODEX檔頭,格式如下所示

typedef struct DexOptHeader {

u1 magic[8]; /* includes version number */

u4 dexOffset; /* file offset of DEX header */

u4 dexLength;

u4 depsOffset; /* offset of optimized DEX dependency table */

u4 depsLength;

u4 optOffset; /* file offset of optimized data tables */

u4 optLength;

u4 flags; /* some info flags */

u4 checksum; /* adler32 checksum covering deps/opt */

/* pad for 64-bit alignment if necessary */

} DexOptHeader;

我們可以透過辨認前面的Magic Code（例如用UltraEdit打開DEX檔案查看前8bytes)是否為 “dey\n036\0″,確認DEX檔案是否已經被最佳化過.而沒有被優化過的DEX 檔案檔頭Magic Code會直接就是 “dex\n035\0″,可供相關的DEX檔案處理機制判斷.

基本的 DEX檔頭如下所示,大小為112bytes.

typedef struct DexHeader {

u1 magic[8]; /* includes version number */

u4 checksum; /* adler32 checksum */

u1 signature[kSHA1DigestLen]; /* SHA-1 hash */

u4 fileSize; /* length of entire file */

u4 headerSize; /* offset to start of next section */

u4 endianTag;

u4 linkSize;

u4 linkOff;

u4 mapOff;

u4 stringIdsSize;

u4 stringIdsOff;

u4 typeIdsSize;

u4 typeIdsOff;

u4 protoIdsSize;

u4 protoIdsOff;

u4 fieldIdsSize;

u4 fieldIdsOff;

u4 methodIdsSize;

u4 methodIdsOff;

u4 classDefsSize;

u4 classDefsOff;

u4 dataSize;

u4 dataOff;

} DexHeader;

接下來就讓我們基於這些檔案欄位,進一步的加以說明.

計算Dex Checksum

Dex驗證Checksum時,如果該檔案已經被最佳化處理過,會先跳過前面40bytes的DexOptHeader,只取DexHeader之後的部份計算Checksum,首先,會把Dex檔案長度先減去sizeof(pHeader->magic) + sizeof(pHeader->checksum) (共12bytes),從這開始往後用alder32計算原本Dex檔案大小的值,將alder32的值與pHeader->checksum值比對,確認該Dex檔案是否有被修改過.

而經過最佳化過的檔案,會加上DexOptHeader檔頭,與在檔案尾部加上最佳化時所相依的Classes資訊,因此,ODEX的Checksum主要是針對Dex以外的部份,也就是最後面所針對最佳化而加上的訊息進行Checksum計算與比對,運作的機制為從ODEX檔頭往後加上pOptHeader->depsOffset的位置,與取得檔尾的位置,目前的實作為end=pOptHeader + pOptHeader->optOffset + pOptHeader->optLength,再透過alder32計算從depsOffset到ODEX檔案結束點的值與pOptHeader->checksum值比對,確認目前ODEX檔案區間是否有被修改過.

驗證目前的ODEX檔案,基本上,ODEX所加入的節區,是在原本的DEX檔案前加上40bytes的檔頭,與在DEX檔案最後加上最佳化相關資訊,而成為一個ODEX檔案.概念如下所示,未來是否會有變動,還請以Android最新的Source Code為依據.

ODEX		ODEX Header (DexOptHeader)
	DEX	DEX Header (DexHeader)
		DEX Body	pStringIds
			pTypeIds
			pProtoIds
			pFieldIds
			pMethodIds
			pClassDefs
			pLinkData
		ODEX Body (DexOptHeader.depsOffset)	pClassLookup
			pRegisterMapPool

如下所示為Dex檔案對應欄位的說明,

名稱	資料格式	說明
ODex Header		Optimized Dex檔頭
Dex Header	header_item	Dex檔頭 (請看下一個表格有更清楚的檔頭欄位說明)
string_ids	string_id_item[]	在dex檔案中所用到的UTF-16 LE字串識別ID（String Ids)列表,包括內部的命名(e.g., type descriptors) 或由程式碼所參考的字串常數物件.
type_ids	type_id_item[]	在dex檔案中所用的形態名稱識別ID(Type Ids)列表,包括檔案中所有參考到classes, arrays, or primitive types,不管是否有在這檔案中定義,只要有參考到的就會納入到此. 型態名稱也會對應到String ID Index.
proto_ids	proto_id_item[]	Class Method對應的Prototype IDs,在這會包括所有這個Dex檔案中參考的Prototype IDs.
field_ids	field_id_item[]	Class Field (變數Type)所對應的IDs,在這會包括所有這個Dex檔案中參考的 Field IDs.
method_ids	method_id_item[]	Class Method所對應的IDs,在這會包括所有這個Dex檔案中參考的 Method IDs. 在檔案中的排序方式會以Type Id為主,之後參考String ID,之後參考Proto ID.
class_defs	class_def_item[]	Class Definitions List可用來查詢每個Class Field/Method,Class Index,Access Flag相關訊息. 如果今天要去Dump所有Class/Method/Field的訊息時,Class Definitions List會是基本必要元素之一.
link_data	ubyte[]	用來支援Staticlly Linked的資料. (mmm,不過筆者手中沒有看到有支援這Section的檔案.)

如下所示為DEX檔頭對應欄位的說明,

Name	Format	Description
magic	ubyte[8] = DEX_FILE_MAGIC	屬於DEX檔頭的8bytes Magic Code “dex\n035\0″
checksum	uint	使用zlib 的adler32所計算的 32-bits CheckSum. 計算的範圍為DEX檔案的長度（Header->fileSize)減去8 bytes Magic Code與4 bytes CheckSum的範圍. 用來確保DEX檔案內容沒有損毀.
signature	ubyte[20]	SHA-1 signature (hash) 用來識別原本的DEX檔案 (被最佳化以前的DEX). SHA-1計算的範圍為DEX檔案的長度（Header->fileSize)減去8 bytes Magic Code,4 bytes CheckSum與 20bytes SHA-1的範圍. 用來識別最原本的DEX 檔案的唯一性. (所以被最佳化過後,這個SHA-1儘能用來識別原本的DEX檔案,而無法透過ODEX檔案計算回最原本的DEX檔案SHA-1值了).
file_size	uint	包含DEX Header與到DEX檔案的檔案長度 (in bytes).
header_size	uint = 0x70	用來記錄目前DEX Header的大小 (現有版本為0x70 bytes),可用來做為後續Header如果有改版時,最基本的檔頭欄位向前,向後相容的依據.
endian_tag	uint = ENDIAN_CONSTANT	預設值為Little-Endian,在這欄位會顯示32bits值 “0x12345678″. (ㄟ….應該在 Big-Endian處理器上,會轉為 “0x78563412”,才能表彰出這個值的意義)
link_size	uint	Link Section的大小,如果為0表示該DEX檔案不是靜態連結.
link_off	uint	用來表示Link Section距離Dex檔頭的Offset. 如果Link Size為0,此值也會為0.資料格式可以參考 struct DexLink.
map_off	uint	用來表示Map Item距離Dex檔頭的Offset. 如果為0,表示這DEX檔案沒有Map Item. 資料格式可以參考 struct map_list.
string_ids_size	uint	用來表示 String IDs List的總數.
string_ids_off	uint	用來表示String Ids List距離Dex檔頭的Offset. 如果String IDs Size為0,此值也會為0.資料格式可以參考 struct DexStringId.
type_ids_size	uint	用來表示 Type IDs List的總數.
type_ids_off	uint	用來表示Type IDs List距離Dex檔頭的Offset.如果type_ids_size為0這個值亦為0. 資料格式可以參考 struct DexTypeId.
proto_ids_size	uint	用來表示 Prototype IDs List的總數.
proto_ids_off	uint	用來表示Prototype IDs List距離Dex檔頭的Offset.如果proto_ids_size為0這個值亦為0. 資料格式可以參考 struct DexProtoId.
field_ids_size	uint	用來表示 Field IDs List的總數.
field_ids_off	uint	用來表示Field IDs List距離Dex檔頭的Offset.如果field_ids_size為0這個值亦為0. 資料格式可以參考 struct DexFieldId.
method_ids_size	uint	用來表示 Method IDs List的總數.
method_ids_off	uint	用來表示Method IDs List距離Dex檔頭的Offset.如果method_ids_size為0這個值亦為0. 資料格式可以參考 struct DexMethodId.
class_defs_size	uint	用來表示 Class Definitions List的總數.
class_defs_off	uint	用來表示Class Definition List距離Dex檔頭的Offset.如果class_defs_size為0這個值亦為0. 資料格式可以參考 struct DexClassDef.
data_size	uint	用來表示Data Section的大小. 並需為sizeof(uint) 的偶數倍. (所以就是 0,8,16…etc)
data_off	uint	用來表示Data Section距離Dex檔頭的Offset.

從Class 查找Method,Field與相關的Types,Prototype與String.

接下來,我們以實際的例子,從Class來查找相關的資訊,讓各位可以對DEX中所包含的資料與結構更有感覺.

首先,我們知道DEX檔案可以是一個包含多個Classes檔案的集合,也因此在進行Class分析前,要先從DEX檔頭classDefsSize欄位取得目前DEX檔案所包含的Classes總數,在知道總數後,我們便可以選擇所要解析的是第幾個Class,接下來筆者假設要Dump出第五個Class的資料,就以如下的 struct 並以距離Dex檔頭pHeader->classDefsOff的距離,取出第五個DexClassDef的資料.

typedef struct DexClassDef {
u4 classIdx; /* index into typeIds for this class */
u4 accessFlags;
u4 superclassIdx; /* index into typeIds for superclass */
u4 interfacesOff; /* file offset to DexTypeList */
u4 sourceFileIdx; /* index into stringIds for source file name */
u4 annotationsOff; /* file offset to annotations_directory_item */
u4 classDataOff; /* file offset to class_data_item */
u4 staticValuesOff; /* file offset to DexEncodedArray */
} DexClassDef;

再來參考 DexClassDef中classDataOff欄位,得到對應Class Data距離DEX檔頭的位置,並以如下struct讀出DexClassDataHeader 的資料,

typedef struct DexClassDataHeader {
u4 staticFieldsSize;
u4 instanceFieldsSize;
u4 directMethodsSize;
u4 virtualMethodsSize;
} DexClassDataHeader;

並以Unsigned LEB128的方式,讀出值,驗證該值格式正確的方式為,如果讀出後的指標跟原本距離5 bytes (LEB128可編碼為1-5bytes),就確認該Usigned LEB128第5個bytes是否有使用超過4bits (ptr[4] > 0x0f,根據Unsigned LEB128編碼,第5個bytes只會用到前4bits). 如果超過,就返回驗證失敗.

若驗證無誤,就會以Unsigned LED128編碼方式,把前四個Unsigned LEB128值讀出來,對應到 DexClassDataHeader中的 staticFieldsSize, instanceFieldsSize, directMethodsSize與 virtualMethodsSize,並以上述static/instance Field與direct/virtual Method的個數和所對應的struct DexField與DexMethod用下列的DexClassData配置記憶體記錄Class Data檔頭與其對應的Field/Method資料.

typedef struct DexClassData {
DexClassDataHeader header;
DexField* staticFields;
DexField* instanceFields;
DexMethod* directMethods;
DexMethod* virtualMethods;
} DexClassData;

之後,依序以Unsigned LEB128編碼讀出 staticFields與instanceFields 的fieldIdx/accessFlags , directMethods/ virtualMethods的methodIdx/accessFlags/codeOff. 筆者把ClassData資料排列的方式透過表格對應如下,由於Unsigned LEB128所編碼的32bits整數值長度會介於1-5bytes間,實際要以幾個Bytes來表示個別的Unsigned LEB128,需根據Decode的內容為主.

長度	對應的結構
4個Unsigned LEB128	typedef struct DexClassDataHeader { u4 staticFieldsSize; u4 instanceFieldsSize; u4 directMethodsSize; u4 virtualMethodsSize; } DexClassDataHeader;
2個Unsigned LEB128 *staticFieldsSize	typedef struct DexField { u4 fieldIdx; /* index to a field_id_item */ u4 accessFlags; } DexField;
2個Unsigned LEB128 * instanceFieldsSize	typedef struct DexField { u4 fieldIdx; /* index to a field_id_item */ u4 accessFlags; } DexField;
3個Unsigned LEB128 *directMethodsSize	typedef struct DexMethod { u4 methodIdx; /* index to a method_id_item */ u4 accessFlags; u4 codeOff; /* file offset to a code_item */ } DexMethod;
3個Unsigned LEB128 * virtualMethodsSize	typedef struct DexMethod { u4 methodIdx; /* index to a method_id_item */ u4 accessFlags; u4 codeOff; /* file offset to a code_item */ } DexMethod;

取得上述 DexClassDef與Class Data後,我們會得到相關的Class/Field/Method Index,接下來就透過這些Index取得對應的字串.

首先把Class Index透過Dex Header中的typeIdsOff以struct DexTypeId取得對應Index的DexTypeId的值,

typedef struct DexTypeId {
u4 descriptorIdx; /* index into stringIds list for type descriptor */
} DexTypeId;

再把取得的descriptorIdx透過Dex Header中的stringIdsOff以struct DexStringId取得對應descriptorIdx 的DexStringId 的值,

typedef struct DexStringId {
u4 stringDataOff; /* file offset to string_data_item */
} DexStringId;

距離Dex檔頭 stringDataOff就是對應字串所在位置.

DexClassDef (classIdx/superclassIdx)->Type Id Index (DexTypeId)->Desceiptor Id Index(DexStringId)->StringDataOffset

有關Class/Method/Field對應的accessFlags Bit意義如下表

Access Flag Bit	Class	Method	Field
0x000001	PUBLIC	PUBLIC	PUBLIC
0x000002	PRIVATE	PRIVATE	PRIVATE
0x000004	PROTECTED	PROTECTED	PROTECTED
0x000008	STATIC	STATIC	STATIC
0x000010	FINAL	FINAL	FINAL
0x000020	?	SYNCHRONIZED	?
0x000040	?	BRIDGE	VOLATILE
0x000080	?	VARARGS	TRANSIENT
0x000100	?	NATIVE	?
0x000200	INTERFACE	?	?
0x000400	ABSTRACT	ABSTRACT	?
0x000800	?	STRICT	?
0x001000	SYNTHETIC	SYNTHETIC	SYNTHETIC
0x002000	ANNOTATION	?	?
0x004000	ENUM	?	ENUM
0x008000	?	MIRANDA	?
0x010000	VERIFIED	CONSTRUCTOR	?
0x020000	OPTIMIZED	DECLARED_SYNCHRONIZED	?

如果Class Definition中的interfacesOff不為0,則以 struct DexTypeList在距離Dex檔頭interfacesOff的位置讀取出Interface的資訊.

typedef struct DexTypeList {
u4 size; /* #of entries in list */
DexTypeItem list[1]; /* entries */
} DexTypeList;

Class對應的Interfaces 總數為 size,在之後依據size個數,銜接對應的 struct DexTypeItem內容,

typedef struct DexTypeItem {
u2 typeIdx; /* index into typeIds */
} DexTypeItem;

如同取得Class Description字串一樣,透過DexTypeItem會取得Type IDs Index,之後依循如下的流程,取得Interface Name (以framework.jar為例,Class “android/os/Binder” 有如下Interface “android/os/IBinder”,或Class “android/accessibilityservice/IEventListener” 有如下Interface “android/os/IInterface”)

Interface Index(DexTypeItem)->Type Id Index (DexTypeId)->Desceiptor Id Index(DexStringId)->StringDataOffset

以Method為例,會以每個Method struct DexMethod 中的methodIdx,透過Dex檔頭的methodIdsOff,以struct DexMethodId,取出該Method對應的Class Index/Prototype Index/Name Index (可以看到…都是透過Index,只要其中有越多同名的字串,就可以節省越多的儲存空間成本).

typedef struct DexMethodId {
u2 classIdx; /* index into typeIds list for defining class */
u2 protoIdx; /* index into protoIds for method prototype */
u4 nameIdx; /* index into stringIds for method name */
} DexMethodId;

透過Name Index (nameIdx)取得字串示意如下

Method Index(DexMethod)->Method Ids Offset (DexMethodId)->Name Index->Desceiptor Id Index(DexStringId)->StringDataOffset

而Prototype Index (protoIdx)會透過Dex檔頭的protoIdsOff,以struct DexProtoId取出有關Prototype的相關資訊,

typedef struct DexProtoId {
u4 shortyIdx; /* index into stringIds for shorty descriptor */
u4 returnTypeIdx; /* index into typeIds list for return type */
u4 parametersOff; /* file offset to type_list for parameter types */
} DexProtoId;

其中如果 parametersOff不為0,則會以距離Dex檔頭parametersOff距離,以struct DexTypeList並根據size 取得TypeList總量,而 DexTypeItem中的 typeIdx就會在對應到每個函式Method參數所對應的Type Index,並可由此取得最後的參數名稱.

typedef struct DexTypeList {
u4 size; /* #of entries in list */
DexTypeItem list[1]; /* entries */
} DexTypeList;

同時,函式Method的返回值型態會透過 returnTypeIdx來反查. 舉framework.jar中Class android/os/IBinder一個有4個參數的Method “transact”例子為例,Method參數(ILandroid/os/Parcel;Landroid/os/Parcel;I)會由左而右,透過 DexTypeList中的list依序往後擺放.

Method參數左 I	DexTypeItem list[0]
Landroid/os/Parcel;	DexTypeItem list[1]
Landroid/os/Parcel;	DexTypeItem list[2]
Method參數右 I	DexTypeItem list[3]

並透過returnTypeIdx取得該函式Method返回值的形態字串 Z. 我們可以看到,這些型態的表述方式,跟透過JNI介面,要由C程式調用Java函式時,所描述的Java函式的形態是一致的(請自行參考JNI中對於Type Signature的說明,例如:http://journals.ecs.soton.ac.uk/java/tutorial/native1.1/implementing/method.html ).而 shortyIdx則直接對應到String Index.

有關Method所對應的ByteCode位置,則可透過struct DexMethod中的codeOff取得struct DexCode,這struct中會包含Method函式中所用到的Registers總數(registersSize),Method所包含的參數個數(insSize),Method實作中用來做為呼叫其他Method帶入參數的Registers個數(outsSize),Method實作中Try/Catch的個數(triesSize),以16bits為單位的Method實作指令集個數(insnsSize)與最後真正Method的實作內容(insns).

typedef struct DexCode {
u2 registersSize;
u2 insSize;
u2 outsSize;
u2 triesSize;
u4 debugInfoOff; /* file offset to debug info stream */
u4 insnsSize; /* size of the insns array, in u2 units */
u2 insns[1];
/* followed by optional u2 padding */
/* followed by try_item[triesSize] */
/* followed by uleb128 handlersSize */
/* followed by catch_handler_item[handlersSize] */
} DexCode;

Method中Try/Catch的資訊會透過struct DexTry取得,所在位置為 DexCode-> insns ByteCode實作的結尾（結尾位置為4bytes的倍數).

typedef struct DexTry {
u4 startAddr; /* start address, in 16-bit code units */
u2 insnCount; /* instruction count, in 16-bit code units */
u2 handlerOff; /* offset in encoded handler data to handlers */
} DexTry;

而有關Class變數Field的部份,會以每個Field struct DexField 中的fieldIdx ,透過Dex檔頭的fieldIdsOff,以struct DexFieldId,取出該Field對應的Class Index/Prototype Index/Name Index

typedef struct DexFieldId {
u2 classIdx; /* index into typeIds list for defining class */
u2 typeIdx; /* index into typeIds for field type */
u4 nameIdx; /* index into stringIds for field name */
} DexFieldId;

如同前述對Method資訊的解析,classIdx可以作為所屬Class 的 Type Index,而typeIdx可以作為Field本身型態的Type Index,最後nameIdx則做為Field名稱的Sreing ID Index.

DEX SHA-1 Signature

DEX檔頭會帶一個160-bits 的SHA-1簽名,主要功能是用來識別最佳化前的DEX檔案,作為最佳化前DEX檔案唯一的識別碼,一旦DEX檔案有經過最佳化或Byte-Swapped(如果把Little-Endian的Dex放到Big-Endian環境執行),該SHA-1值就會無法被計算回來,該值的意義主要只用於識別而非驗證檔案是否有被修改.

計算SHA-1簽名的方式為,把Dex檔案長度先減去sizeof(pHeader->magic) + sizeof(pHeader->checksum) + kSHA1DigestLen (8 bytes Magic Code,4bytes Checksum與20 bytes SHA-1 Digest),然後再透過SHA-1計算Dex檔案數值. 只要該檔案有經過最佳化,計算的結果就會與原本的簽名不同.

Dalvik虛擬器的ByteCode指令格式

參考Android文件,筆者在這表述方式為,每個[]都代表一個16bits值,由低位元到高位元,op等於一個8bits的指令碼,A/B/C/D/E/F/G/H 代表一個4bits的數值,可用來代表暫存器 0-15或是數值. 或是兩個AA/BB/CC/DD/EE/FF/GG/HH代表一個8bits的數值,表彰暫存器0-255或是數值.. 或是4個AAAA/BBBB/CCCC/DDDD/EEEE/FFFF/GGGG/HHHH代表一個16bits的數值.

指令集格式	語法	範例
[op|ØØ]	Op	[0000] nop
[op|B|A]	Op vA, vB	[0110] move v0, v1 [0760] move-object v0, v6
	Op vA, #+B	[1214] const/4 v4, #int 1 // #1
[op|AA]	Op vAA	[0a02] move-result v2
	Op +AA	[28ec] goto 0030 // -0014
[op|ØØ] [AAAA]	Op +AAAA	[2900 56ff] goto/16 0005 // -00aa
[op|AA] [BBBB]	op vAA, vBBBB	[0801 1a00] move-object/from16 v1, v26
	op vAA, +BBBB	[3805 f5ff] if-eqz v5, 002e // -000b
	op vAA, #+BBBB	[1306 0a00] const/16 v6, #int 10 // #a
	op vAA, #+BBBB0000 op vAA, #+BBBB000000000000	[1504 0100] (const/high16 vAA, #+BBBB0000) const/high16 v4, #int 65536 // #1 [1900 f07f] (const-wide/high16 vAA, #+BBBB000000000000) const-wide/high16 v0, #long 9218868437227405312 // #7ff0
	op vAA, type@BBBB op vAA, field@BBBB op vAA, string@BBBB	[1c00 090e](const-class vAA, type@BBBB ) const-class v0, [F // class@0e09 (sstaticop vAA, field@BBBB ) [1a02 dd0d](const-string vAA, string@BBBB ) const-string v2, “Class doesn’t implement Cloneable” // string@0ddd
[op|AA] [BB|CC]	op vAA, vBB, vCC	[2d00 0405](cmpkind vAA, vBB, vCC) cmpl-float v0, v4, v5
	op vAA, vBB, #+CC	[d804 0401](binop/lit8 vAA, vBB, #+CC ) add-int/lit8 v4, v4, #int 1 // #01
[op|B|A] [CCCC]	op vA, vB, +CCCC	[3376 1400] (if-test vA, vB, +CCCC ) if-ne v6, v7, 001a // +0014
	op vA, vB, #+CCCC	[d209 e803] 7(binop/lit16 vA, vB, #+CCCC ) mul-int/lit16 v9, v0, #int 1000 // #03e8
	op vA, vB, type@CCCCop vA, vB, field@CCCC	[2394 0a0e] (new-array vA, vB, type@CCCC ) new-array v4, v9, [I // class@0e0a [2049 c600] (instance-of vA, vB, type@CCCC) instance-of v9, v4, Ljava/io/Serializable; // class@00c6
	op vA, vB, fieldoff@CCCC
[op|ØØ][AAAAlo] [AAAAhi ]	op +AAAAAAAA	(goto/32 +AAAAAAAA)
[op|ØØ] [AAAA] [BBBB]	op vAAAA, vBBBB	(move-object/16 vAAAA, vBBBB )
[op|AA] [BBBBlo] [BBBBhi]	op vAA, #+BBBBBBBB	(const vAA, #+BBBBBBBB)
	op vAA, +BBBBBBBB	(packed-switch vAA, +BBBBBBBB )
	op vAA, string@BBBBBBBB	(const-string/jumbo vAA, string@BBBBBBBB)
[op|B|A] [CCCC] [E|D|G|F]	[B=5] op {vD, vE, vF, vG, vA}, meth@CCCC[B=5] op {vD, vE, vF, vG, vA}, type@CCCC[B=4] op {vD, vE, vF, vG}, kind@CCCC[B=3] op {vD, vE, vF}, kind@CCCC[B=2] op {vD, vE}, kind@CCCC[B=1] op {vD}, kind@CCCC[B=0] op {}, kind@CCCC and [B=5] op {vD, vE, vF, vG, vA}, vtaboff@CCCC[B=4] op {vD, vE, vF, vG}, vtaboff@CCCC[B=3] op {vD, vE, vF}, vtaboff@CCCC[B=2] op {vD, vE}, vtaboff@CCCC[B=1] op {vD}, vtaboff@CCCC	[7020 090a 2100] (invoke-kind {vD, vE, vF, vG, vA}, meth@CCCC) invoke-direct {v1, v2}, Ljava/lang/AssertionError;.<init>:(Ljava/lang/Object;)V // method@0a09 [2420 0a0e 6500] (filled-new-array {vD, vE, vF, vG, vA}, type@CCCC) filled-new-array {v5, v6}, [I // class@0e0a [f840 fb00 1032] +invoke-virtual-quick {v0, v1, v2, v3}, [00fb] // vtable #00fb [f830 fa00 1002] +invoke-virtual-quick {v0, v1, v2}, [00fa] // vtable #00fa [f820 d300 1000] +invoke-virtual-quick {v0, v1}, [00d3] // vtable #00d3
[op|B|A] [CCDD] [F|E|H|G]	[B=5] op {vE, vF, vG, vH, vA}, vtaboff@CC, iface@DD[B=4] op {vE, vF, vG, vH}, vtaboff@CC, iface@DD[B=3] op {vE, vF, vG}, vtaboff@CC, iface@DD[B=2] op {vE, vF}, vtaboff@CC, iface@DD[B=1] op {vE}, vtaboff@CC, iface@DD
[op|AA] [BBBB] [CCCC]	op {vCCCC .. vNNNN}, meth@BBBBop {vCCCC .. vNNNN}, type@BBBB (where NNNN = CCCC+AA-1, that is A determines the count 0..255, and C determines the first register) and op {vCCCC .. vNNNN}, vtaboff@BBBB (where NNNN = CCCC+AA-1, that is A determines the count 0..255, and C determines the first register)	[7609 6502 0000] invoke-direct/range {v0, v1, v2, v3, v4, v5, v6, v7, v8}, Landroid/view/animation/TranslateAnimation;.<init>:(IFIFIFIF)V // method@0265 [7701 7703 1100] invoke-static/range {v17}, Lcom/android/launcher2/AllApps3D$RolloRS;.access$400:(Lcom/android/launcher2/AllApps3D$RolloRS;)F // method@0377 method@2b49 [7803 8a00 1500] invoke-interface/range {v21, v22, v23}, Landroid/content/SharedPreferences;.getBoolean:(Ljava/lang/String;Z)Z // method@008a [f91b fc00 0400] +invoke-virtual-quick/range {v4, v5, v6, v7, v8, v9, v10, v11, v12, v13, v14, v15, v16, v17, v18, v19, v20, v21, v22, v23, v24, v25, v26, v27, v28, v29, v30}, [00fc] // vtable #00fc
[op|AA] [BBCC] [DDDD]	op {vDDDD .. vNNNN}, vtaboff@BB, iface@CC (where NNNN = DDDD+AA-1, that is A determines the count 0..255, and D determines the first register)
[op|AA] [BBBBlo] [BBBB] [BBBB] [BBBBhi]	op vAA, #+BBBBBBBBBBBBBBBB	[1807 ffff 0000 ffff 0000] const-wide v7, #double 0.000000 // #0000ffff0000ffff [1803 6d9c 2e3a 42ce 478e] const-wide v3, #double -0.000000 // #8e47ce423a2e9c6d

從dalvik指令集來看,比較像是CISC架構的指令集思維,每個指令基本單位為16bits,最長的指令需要80bits(10bytes)的長度,根據不同指令的需求,可以有16bits倍數的延伸,這跟ARM RISC架構下,會以固定32bits或16bits完成一個指令的設計取向有所不同. 反而比較接近x86 CISC架構下,指令可以根據設計有不同長度的延伸,例如下列x86指令1,2,7與11 bytes的例子

(1bytes)0×48 = dec eax

(2bytes)0×89 F9= mov ecx,edi

(7bytes)0x8B BC 24 A4 01 00 00 = mov edi,dword ptr [esp+000001A4h]

(11bytes)0×81 BC 24 14 01 00 00 FF 00 00 00 = cmp dword ptr [esp+00000114h],0FFh

Dalvik ByteCode與Sun ByteCode的進一步說明

Dalvik 虛擬器指令集最多可以支援256個暫存器,每個暫存器都會透過FP對應到一個32bits的記憶體位置,除了在指令執行階段會透過ARM暫存器(以目前Dalvik的實作,會用到R0,R1,R2,R3,R9與R10共6個暫存器)對應到Dalvik指令實作進行加速外,主要的Dalvik暫存器都是透過外部的記憶體來暫存,模擬為Dalvik虛擬器中的暫存器.

接下來,我們透過相同的Java函式呼叫程式碼,分別編譯為Dalvik ByteCode與Sun Java ByteCode進行比較,了解兩者在實現上的差異.

首先,以如下的函式呼叫為例

Main1(111); (函式原型void Main1(int A) )

在dalvik中,ByteCode的實現為

[1304 6f00] const/16 v4, #int 111 // #6f

[0800 2400] move-object/from16 v0, v36 //暫存器36指到TestAA Class Object本身

[0141] move v1, v4

[f820 f900 1000] +invoke-virtual-quick {v0, v1}, [00f9] // vtable #00f9

在sun Java中,ByteCode 實現為 (會把函式參數由左往右推入Stack)

11: aload_0 // 把區域變數 0 (指到TestAA Class Object本身) 推到Stack中

12: bipush 111 //Push 1 byte (111) 到Stack中

14: invokevirtual #58; //Method Main1:(I)V

不過以指令集個數而言,Dalvik Dx顯然做了沒有效率的轉譯,先把值放到v4暫存器,之後再轉給v1,其實可以直接轉譯為

const/16 v1, #int 111 // #6f

就可以省去1個 move指令 (共2bytes)

再以如下的函式呼叫為例

int v2=Main2(111,222); (函式原型為 int Main2(int A,int B))

在dalvik中,ByteCode的實現為

[1304 6f00] const/16 v4, #int 111 // #6f

[1305 de00] const/16 v5, #int 222 // #de

[0800 2400] move-object/from16 v0, v36 //暫存器36指到TestAA Class Object本身

[0141] move v1, v4

[0152] move v2, v5

[f830 fa00 1002] +invoke-virtual-quick {v0, v1, v2}, [00fa] // vtable #00fa

[0a1f] move-result v31 //把Return值存到暫存器31

在sun Java中,ByteCode 實現為 (會把函式參數由左往右推入Stack)

17: aload_0 // 把區域變數 0 (指到TestAA Class Object本身) 推到Stack中

18: bipush 111 //Push 1 byte (111) 到Stack中

20: sipush 222 //Push 2 byte (Short) (222) 到Stack中

23: invokevirtual #60; //Method Main2:(II)I

26: istore_2 //把return值存到區域變數 2

相比Sun的Java Code而言,還是多了兩次沒有必要的Move動作,浪費了2個指令共4個bytes的空間.可能是筆者對Google大師期待過高…..@_@,在比較Dex ByteCode的一些邏輯後,其實還是有待改善的部份,但不可否認的Dalvik整個實作,是一個很不錯的作品,值得有志於了解模擬器實作的人,花時間深入理解.

我們可以看到,在函式參數傳遞時,Dalvik會選擇以暫存器的方式傳遞,以便對應到底層實作時,可以透過處理器本身的暫存器加速指令集的效率,而Sun Java Vm的函數參數的傳遞,則是透過Stack,由左往右把函式參數推到Stack中 (跟C的由右往左推,是相反的).

在函式參數的返回值部分,Dalvik會透過暫存器返回,再由呼叫端儲存到自己的暫存器中(這點跟C 語言也是比較類似的),反之,Sun Java 虛擬器的函式返回值會放在Stack中,再由呼叫端從Stack取出放到本地的區域變數中.

ByteCode顧名思義指令集會以一個Byte的長度來定義,但是在Dalvik中,ByteCode的單位是以16bits為單位(Dalvik目前共有約230個指令集),通常第一個Byte為指令集,第二個Byte為使用的暫存器,一個基本指令集的描述,會需要16-bits (1byte 指令 + 1bytes暫存器),一個最簡單的例子就是

return-void = 0e00

return v1 = 0f01

return v2 = 0f02

return-object v1 = 1101

另一種組合就是32-bits的指令集組合,如下所示,可以用各4 bits代表目標與來源暫存器,與16bits的Offset.

+iput-quick v2, v3, [obj+0120] = f532 2001

+iput-quick v1, v3, [obj+0118] = f531 1801

+iput-quick v0, v1, [obj+0110] = f510 1001

+iput-object-quick v1, v0, [obj+00d8] = f701 d800

其次,還有48-bits的組合

+invoke-virtual-quick {v6, v5}, [00d1] = f820 d100 5600

+invoke-virtual-quick {v6, v2}, [00d3] = f820 d300 2600

+invoke-virtual-quick {v6, v3}, [0034] = f820 3400 3600

+invoke-virtual-quick {v2}, [01b7] = f810 b701 0200

參考Android文件,Dalvik ByteCode在設計初期,希望Machine Model 與 Calling Conventions能儘量接近於真實系統與C風格的Calling Conventions. Dalvik虛擬器為Register-Based,並會根據每個Method所需要的函式參數或是區域變數,在該Method被執行時,產生對應固定大小的Frame (這會供Dalvik Register使用). 每個Dalvik Register固定長度為32bits,相鄰的兩個Dalvik Register可以用來表示64bits的值.

函式如果有N個參數,在呼叫該函式時, 就會用到N個Register,來作為該函式的呼叫之用,而在函式內部的實作中,也會用到N個Register來操作所傳入的N個參數,只是上述的N個暫存器的對應,在呼叫端與函式內部的實作,不一定能直接對應. 如果參數為64bits (例如 double),就會一次用到兩個Register代表該64bits的函式參數. 目前Method所在的Class (也就是this),會是每個Method函式呼叫時的第一個參數.

Dalvik指令集中所帶的數值,都固定為16bits的unsigned型態,根據指令的不同,該指令16bits的描述中有的Bits可以被忽略,或是必須為0.對於透過32bits暫存器進行Mov的資料,並不會去確認資料是整數(int)或是浮點數(float). 站在指令集的角度,所對應的暫存器範圍不大於256(也就是說最多會用1bytes =8bits去描述一個暫存器,最大定義到0xff),而有些16-bits指令描述暫存器只會用到4bits(也就是說對這類指令暫存器最大只定義到0x0f).

有些Dalvik ByteCode指令所參考的資料為不定長度的內容,這些資料所在記憶體位置必須是4bytes Memory Alignment,例如:fill-array-data,或packed-switch,在不足4bytes Alignment的部份就會插入16bits Nop 指令作為Spacer,如下例子

0005: packed-switch v0, 00000012 // +0000000d

=>參考位於12的資料,由於要為4bytes Alignment,所以在11的位址插入2bytes的Spacer

…………………….

……………………..

0011: nop // spacer

0012: 0001 0200 1300 0000 0800 0000 0a00 … : packed-switch-data (8 units)

為解決原本Java ByteCode檔案格式中,重複字串所導致的儲存空間浪費,Dalvik Dex檔案格式,會建置String ID,Type ID,Prototype ID,Field ID,Method ID與Class ID的Tables,只要有重複的字串,就會透過String ID指到同一個Data區塊中,節省儲存空間

接下來讓我們以實際的Java程式碼,對應到Dalvik 與 Sun Java的ByteCode,比較其中實作的差異化,來了解兩者技術的不同,以下列程式碼為例

public void Main1(int A)

{

int vA;

int vB;

vA=A;

vB=A*2;

}

反組譯的Dalvik ByteCode為

000430: com.TestAA.TestAA.Main1:(I)V

0000: [0130] move v0, v3

0001: [da01 0302] mul-int/lit8 v1, v3, #int 2 // #02

0003: [0e00] return-void

其中,暫存器對應如下所示

0x0001 – 0x0004 reg=0 vA I

0x0003 – 0x0004 reg=1 vB I

0x0000 – 0x0004 reg=2 this Lcom/TestAA/TestAA;

0x0000 – 0x0004 reg=3 A I

而同樣的程式碼,如果用Java ByteCode呈現如下

0: iload_1 //load 函式參數A

1: istore_2 //store 到區域變數vA

2: iload_1 //load 函式參數A

3: iconst_2 //設定常數 2

4: imul //把 A*2

5: istore_3 //store 到區域變數vB

6: return //return void.

LocalVariableTable:

Start Length Slot Name Signature

0 7 0 this Lcom/TestAA/TestAA;

0 7 1 A I

2 5 2 vA I

6 1 3 vB I

我們可以看到Dalvik ByteCode的實作比較簡潔,Code Size為8bytes,總共用了三個指令,而原本Stack-Based的Java ByteCode所需Code Size為7bytes,總共用了7個指令,需要比較多的load/store動作,無法像是Dalvik Register-Based的實作,以仿似一般處理器使用暫存器的方式,用三個指令就把原本Java代碼中的邏輯完成.

接下來,我們增加函式的參數,並修改return值為int,如下程式碼

public int Main2(int A,int B)

{

int vA;

int vB;

vA=A;

vB=A*2+B;

return vA+vB;

}

反組譯的Dalvik ByteCode為

000448: com.TestAA.TestAA.Main2:(II)I

0000: [0140] move v0, v4

0001: [da02 0402] mul-int/lit8 v2, v4, #int 2 // #02

0003: [9001 0205] add-int v1, v2, v5

0005: [9002 0001] add-int v2, v0, v1

0007: [0f02] return v2

其中,暫存器對應如下所示

0x0001 – 0x0008 reg=0 vA I

0x0005 – 0x0008 reg=1 vB I

0x0000 – 0x0008 reg=3 this Lcom/TestAA/TestAA;

0x0000 – 0x0008 reg=4 A I

0x0000 – 0x0008 reg=5 B I

而同樣的程式碼,如果用Java ByteCode呈現如下

0: iload_1

1: istore_3

2: iload_1

3: iconst_2

4: imul

5: iload_2

6: iadd

7: istore 4

9: iload_3

10: iload 4

12: iadd

13: ireturn

LocalVariableTable:

Start Length Slot Name Signature

0 14 0 this Lcom/TestAA/TestAA;

0 14 1 A I

0 14 2 B I

2 12 3 vA I

9 5 4 vB I

接下來,我們把函式參數增為三個,並修改return值為double,如下程式碼

public double Main3(int A,int B,int C)

{

int vA;

int vB;

vA=A+3;

vB=A*2+B*3+C*4;

return (double)vA+vB;

}

反組譯的Dalvik ByteCode為

000468: com.TestAA.TestAA.Main3:(III)D

0000: [d800 0703] add-int/lit8 v0, v7, #int 3 // #03

0002: [da02 0702] mul-int/lit8 v2, v7, #int 2 // #02

0004: [da03 0803] mul-int/lit8 v3, v8, #int 3 // #03

0006: [b032] add-int/2addr v2, v3

0007: [da03 0904] mul-int/lit8 v3, v9, #int 4 // #04

0009: [9001 0203] add-int v1, v2, v3

000b: [8302] int-to-double v2, v0

000c: [8314] int-to-double v4, v1

000d: [cb42] add-double/2addr v2, v4

000e: [1002] return-wide v2

而同樣的程式碼,如果用Java ByteCode呈現如下

0: iload_1

1: iconst_3

2: iadd

3: istore 4

5: iload_1

6: iconst_2

7: imul

8: iload_2

9: iconst_3

10: imul

11: iadd

12: iload_3

13: iconst_4

14: imul

15: iadd

16: istore 5

18: iload 4

20: i2d

21: iload 5

23: i2d

24: dadd

25: dreturn

接下來,我們把函式參數增為26個,並修改return值為int,如下程式碼

public int Main4(int A,int B,int C,int D,int E,int F,int G,int H,int I,int J,int K,int L,int M,int N,int O,int P,int Q,int R,int S,int T,int U,int V,int W,int X,int Y,int Z)

{

int vA;

int vB;

vA=A+B+C+D+E+F+G+H+I+J+K+L+M+N+O+P+Q+R+S+T+U+V+W+X+Y+Z;

vB=A*1+B*2+C*3+D*4+E*5+F*6+G*7+H*8+I*9+J*10+K*11+L*12+M*13+N*14+O*15+P*16+Q*17+R*18+S*19+T*20+U*21+V*22+W*23+X*24+Y*25+Z*26;

return vA+vB;

}

反組譯的Dalvik ByteCode為

000498: com.TestAA.TestAA.Main4:(IIIIIIIIIIIIIIIIIIIIIIIIII)I

0000: [9002 0506] add-int v2, v5, v6

0002: [b072] add-int/2addr v2, v7

0003: [b082] add-int/2addr v2, v8

0004: [b092] add-int/2addr v2, v9

0005: [b0a2] add-int/2addr v2, v10

0006: [b0b2] add-int/2addr v2, v11

0007: [b0c2] add-int/2addr v2, v12

0008: [b0d2] add-int/2addr v2, v13

0009: [b0e2] add-int/2addr v2, v14

000a: [b0f2] add-int/2addr v2, v15

000b: [9002 0210] add-int v2, v2, v16

000d: [9002 0211] add-int v2, v2, v17

000f: [9002 0212] add-int v2, v2, v18

0011: [9002 0213] add-int v2, v2, v19

0013: [9002 0214] add-int v2, v2, v20

0015: [9002 0215] add-int v2, v2, v21

0017: [9002 0216] add-int v2, v2, v22

0019: [9002 0217] add-int v2, v2, v23

001b: [9002 0218] add-int v2, v2, v24

001d: [9002 0219] add-int v2, v2, v25

001f: [9002 021a] add-int v2, v2, v26

0021: [9002 021b] add-int v2, v2, v27

0023: [9002 021c] add-int v2, v2, v28

0025: [9002 021d] add-int v2, v2, v29

0027: [9000 021e] add-int v0, v2, v30

0029: [da02 0501] mul-int/lit8 v2, v5, #int 1 // #01

002b: [da03 0602] mul-int/lit8 v3, v6, #int 2 // #02

002d: [b032] add-int/2addr v2, v3

002e: [da03 0703] mul-int/lit8 v3, v7, #int 3 // #03

0030: [b032] add-int/2addr v2, v3

0031: [da03 0804] mul-int/lit8 v3, v8, #int 4 // #04

0033: [b032] add-int/2addr v2, v3

0034: [da03 0905] mul-int/lit8 v3, v9, #int 5 // #05

0036: [b032] add-int/2addr v2, v3

0037: [da03 0a06] mul-int/lit8 v3, v10, #int 6 // #06

0039: [b032] add-int/2addr v2, v3

003a: [da03 0b07] mul-int/lit8 v3, v11, #int 7 // #07

003c: [b032] add-int/2addr v2, v3

003d: [da03 0c08] mul-int/lit8 v3, v12, #int 8 // #08

003f: [b032] add-int/2addr v2, v3

0040: [da03 0d09] mul-int/lit8 v3, v13, #int 9 // #09

0042: [b032] add-int/2addr v2, v3

0043: [da03 0e0a] mul-int/lit8 v3, v14, #int 10 // #0a

0045: [b032] add-int/2addr v2, v3

0046: [da03 0f0b] mul-int/lit8 v3, v15, #int 11 // #0b

0048: [b032] add-int/2addr v2, v3

0049: [da03 100c] mul-int/lit8 v3, v16, #int 12 // #0c

004b: [b032] add-int/2addr v2, v3

004c: [da03 110d] mul-int/lit8 v3, v17, #int 13 // #0d

004e: [b032] add-int/2addr v2, v3

004f: [da03 120e] mul-int/lit8 v3, v18, #int 14 // #0e

0051: [b032] add-int/2addr v2, v3

0052: [da03 130f] mul-int/lit8 v3, v19, #int 15 // #0f

0054: [b032]: add-int/2addr v2, v3

0055: [da03 1410] mul-int/lit8 v3, v20, #int 16 // #10

0057: [b032] add-int/2addr v2, v3

0058: [da03 1511] mul-int/lit8 v3, v21, #int 17 // #11

005a: [b032] add-int/2addr v2, v3

005b: [da03 1612] mul-int/lit8 v3, v22, #int 18 // #12

005d: [b032] add-int/2addr v2, v3

005e: [da03 1713] mul-int/lit8 v3, v23, #int 19 // #13

0060: [b032] add-int/2addr v2, v3

0061: [da03 1814] mul-int/lit8 v3, v24, #int 20 // #14

0063: [b032] add-int/2addr v2, v3

0064: [da03 1915] mul-int/lit8 v3, v25, #int 21 // #15

0066: [b032] add-int/2addr v2, v3

0067: [da03 1a16] mul-int/lit8 v3, v26, #int 22 // #16

0069: [b032] add-int/2addr v2, v3

006a: [da03 1b17] mul-int/lit8 v3, v27, #int 23 // #17

006c: [b032] |: add-int/2addr v2, v3

006d: [da03 1c18] mul-int/lit8 v3, v28, #int 24 // #18

006f: [b032] add-int/2addr v2, v3

0070: [da03 1d19] mul-int/lit8 v3, v29, #int 25 // #19

0072: [b032] add-int/2addr v2, v3

0073: [da03 1e1a] mul-int/lit8 v3, v30, #int 26 // #1a

0075: [9001] [0203] add-int v1, v2, v3

0077: [9002 0001] add-int v2, v0, v1

0079: [0f02] return v2

而同樣的程式碼,如果用Java ByteCode呈現如下

0: iload_1

1: iload_2

2: iadd

3: iload_3

4: iadd

5: iload 4

7: iadd

8: iload 5

10: iadd

11: iload 6

13: iadd

14: iload 7

16: iadd

17: iload 8

19: iadd

20: iload 9

22: iadd

23: iload 10

25: iadd

26: iload 11

28: iadd

29: iload 12

31: iadd

32: iload 13

34: iadd

35: iload 14

37: iadd

38: iload 15

40: iadd

41: iload 16

43: iadd

44: iload 17

46: iadd

47: iload 18

49: iadd

50: iload 19

52: iadd

53: iload 20

55: iadd

56: iload 21

58: iadd

59: iload 22

61: iadd

62: iload 23

64: iadd

65: iload 24

67: iadd

68: iload 25

70: iadd

71: iload 26

73: iadd

74: istore 27

76: iload_1

77: iconst_1

78: imul

79: iload_2

80: iconst_2

81: imul

82: iadd

83: iload_3

84: iconst_3

85: imul

86: iadd

87: iload 4

89: iconst_4

90: imul

91: iadd

92: iload 5

94: iconst_5

95: imul

96: iadd

97: iload 6

99: bipush 6

101: imul

102: iadd

103: iload 7

105: bipush 7

107: imul

108: iadd

109: iload 8

111: bipush 8

113: imul

114: iadd

115: iload 9

117: bipush 9

119: imul

120: iadd

121: iload 10

123: bipush 10

125: imul

126: iadd

127: iload 11

129: bipush 11

131: imul

132: iadd

133: iload 12

135: bipush 12

137: imul

138: iadd

139: iload 13

141: bipush 13

143: imul

144: iadd

145: iload 14

147: bipush 14

149: imul

150: iadd

151: iload 15

153: bipush 15

155: imul

156: iadd

157: iload 16

159: bipush 16

161: imul

162: iadd

163: iload 17

165: bipush 17

167: imul

168: iadd

169: iload 18

171: bipush 18

173: imul

174: iadd

175: iload 19

177: bipush 19

179: imul

180: iadd

181: iload 20

183: bipush 20

185: imul

186: iadd

187: iload 21

189: bipush 21

191: imul

192: iadd

193: iload 22

195: bipush 22

197: imul

198: iadd

199: iload 23

201: bipush 23

203: imul

204: iadd

205: iload 24

207: bipush 24

209: imul

210: iadd

211: iload 25

213: bipush 25

215: imul

216: iadd

217: iload 26

219: bipush 26

221: imul

222: iadd

223: istore 28

225: iload 27

227: iload 28

229: iadd

230: ireturn

彙整上述四個函式的Java與反組譯結果,我們可以發現

1, Dalvik虛擬器所配置的暫存器個數會以資料總數為依據,每個暫存器寬度為32bits. 且除函式參數與區域變數外,暫存器會配合執行需求重複利用.

2, Dalvik虛擬器暫存器並不像是C或是ARM原生程式一樣,有固定的函式參數推入的機制或是會使用的暫存器(C語言在X86為Stack由右往左推或是ARM用R0-R3暫存器來傳遞函式參數),而是根據資料的長度決定

stackReq = method->registersSize * 4 // params + locals

+ sizeof(StackSaveArea) * 2 // break frame + regular frame

+ method->outsSize * 4; // args to other methods

比較Stack-Based與Register-Based VM記憶體與指令實作的方式

透過JDK所編譯出來的Java Class檔案,會包含如下的資訊

LocalVariableTable:

Start Length Slot Name Signature

0 38 0 this Lcom/testAA/testAA;

0 38 1 A I

0 38 2 B I

0 38 3 C I

5 33 4 vA I

18 20 5 vB I

用來描述每一個函式參數或區域變數對應到Stack Frame中的位置,以如下Main3 Method時做為例

public class testAA extends Activity {

int gA;

int gB;

…..

public double Main3(int A,int B,int C)

{

int vA;

int vB;

vA=A+3;

vB=A*2+B*3+C*4;

gA=vA;

gB=vB;

return (double)vA+vB;

}

….

}

對應到Main3的呼叫端實作

double v3=Main3(111,222,333);

在呼叫端的Java ByteCode實現為

27: aload_0

28: bipush 111

30: sipush 222

33: sipush 333

36: invokevirtual #62; //Method Main3:(III)D

39: dstore_3

我們可以看到參數由左往右推入堆疊中,參照Stack Frame中的位置,可以看到Stack Frame Slot 0會擺放函式參數的第一個變數(也就是Class本身 this),依此類推把函式參數放置完後,再配置Method中對應的區域變數,同樣由宣告的順序開始擺放到Stack Frame Slot中.

每個Slot中所包含的變數,都會包含該變數對應到ByteCode所需存在的行數起點與終點,參考上述 LocalVariableTable的描述,Slot 1 (函式參數A)會在ByteCode第0行前存在,在第38行結束使用.

0: iload_1

1: iconst_3

…..

36: dadd

37: dreturn

或根據 LocalVariableTable描述,Slot 4 (區域變數vA)會在ByteCode第5行前存在,在第38行結束使用.

…..

3: istore 4

5: iload_1

….

30: iload 4

32: i2d

33: iload 5

35: i2d

36: dadd

37: dreturn

Slot 5 (區域變數vB)會在ByteCode第18行前存在,在第38行結束使用.

………………..

16: istore 5

18: aload_0

19: iload 4

……………….

32: i2d

33: iload 5

35: i2d

36: dadd

37: dreturn

如下所示對Class內部變數的寫入是透過指令 putfield,先把Class本身推入Stack,再把vA (Slot4)值推入Stack,之後透過 ” putfield #27″,把vA寫入Class中的Constant pool Index=27中.

18: aload_0

19: iload 4

21: putfield #27; //Field gA:I

最後會呼叫dreturn,把返回的double數值,從目前所在的Stack Frame中取出,放到呼叫端的Stack Frame中,回到呼叫端後,再呼叫dstore從呼叫端的Stack Frame中放到呼叫端對應變數所在的Slot中.

藉由上述說明,我們可以了解Sun Java對函式參數,區域變數與返回值對應到Stack Frame中的操作,接下來讓我們比對Dalvik在這部份的記憶體行為.

首先,我們可以看到Main3會具備如下的Locals Table

locals :

0x0002 – 0x0013 reg=0 vA I

0x000b – 0x0013 reg=1 vB I

0x0000 – 0x0013 reg=6 this Lcom/testAA/testAA;

0x0000 – 0x0013 reg=7 A I

0x0000 – 0x0013 reg=8 B I

0x0000 – 0x0013 reg=9 C I

在對應到呼叫端的實作,

00060a: 1304 6f00 |001f: const/16 v4, #int 111 // #6f

00060e: 1305 de00 |0021: const/16 v5, #int 222 // #de

000612: 1306 4d01 |0023: const/16 v6, #int 333 // #14d

000616: 0800 2400 |0025: move-object/from16 v0, v36

00061a: 0141 |0027: move v1, v4

00061c: 0152 |0028: move v2, v5

00061e: 0163 |0029: move v3, v6

000620: f840 fb00 1032 |002a: +invoke-virtual-quick {v0, v1, v2, v3}, [00fb] // vtable #00fb

000626: 0b20 |002d: move-result-wide v32

同樣的,Dalvik中會去描述每一個暫存器在Dalvik ByteCode行數所存在的範圍,並不是每個區域變數都會從頭到尾被需要.同時,在寫入Class內部的變數時,則是透過指令 iput-quick操作.

[f560 b000] +iput-quick v0, v6, [obj+00b0]

[f561 b400] +iput-quick v1, v6, [obj+00b4]

我們可以看到,在Dalvik中,會從右到左為順序去把參數推到Stack Frame中(也可以參考指令OP_INVOKE_VIRTUAL_QUICK的實作流程.),也因此,指到Class本身的this,會變成是最靠區域變數的最後一個函式參數,並以此去對應到被呼叫函式中所對應的Register編號. 區域變數則由最後宣告的變數,放在Register最大值,最先宣告的區域變數對應到Register最小值. 從Stack Frame把Dalvik暫存器對應到記憶體的角度來看,其實這跟Sun Java把函式參數,區域變數跟返回值對應到Stack Frame Slot的意義是一樣的,雖然Dalvik指令最多可以定址到256個暫存器,但這些暫存器在記憶體中儲存的位置還是對應到Stack Frame中,同樣的,在Sun Java實作中,如果今天有數量較多的區域變數或是函式參數,一樣都是對應到Stack Frame中的Slot,這就如同Dalvik是對應到Stack Frame中對應的暫存器位置(每個都是32-bits)在操作與記憶體成本上是可以一致的(不過我沒看過Sun Java的實作Source Code,只是從反組譯與行為來推測).

從Dalvik以Register Based實作虛擬器的角度來看,最大的效能改善應該不是來自於記憶體或是Stake Frame的改善,而是來自於要達到同樣目的時,Register Based指令集可以比Stack Based虛擬器指令集更加的精簡 (前提是Android DX也要能產生出對應有效率的Sun Java ByteCode -> Dalvik ByteCode轉譯,真的發揮Register Based虛擬器的優勢),舉如下的例子來說

如果要把值寫入到Class中的變數gA,在Sun Java ByteCode實作為

aload_0

iload 4

putfield #27; //Field gA:I

共三個指令,而在Dalvik ByteCode中只要一個指令就好

iput-quick v0, v6, [obj+00b0]

同樣的,如果要做區域變數vA等於函式參數A的動作 “vA=A”,在Sun Java ByteCode實作為

iload_1 (Load A to Stack Frame)

istore_3 (Store value from Stack Frame to vA)

共2個指令,而在Dalvik ByteCode中只要一個指令就好

move v0, v4 //v0=vA and v4=A

我們可以看到Register-Based在指令集的效率上可以比較高,效能的好壞會在於Android以Java實作的DX轉譯工具,這工具如何把Sun Java ByteCode轉譯為Dalvik ByteCode,會不會有其他如本文之前所提到的,產生出沒有效率的Dalvik ByteCode代碼,會是影響Android執行效率的關鍵.

雖然Dalvik ByteCode最小成本為16bits,比起Sun Java ByteCode最小可以為8bits高,但實際上以目前ARM處理器Bus與對外部記憶體的寬度至少都是32-bits來看,存取一個16bits跟8bits值對External Memory Bus成本基本上是一樣的. 減少指令的用量,應該會比減少指令長度來的對效能有所助益.

Register Map Area

在DEX檔案中,會有每一個Method實作時,所需用到的暫存器數量,函式參數總數,用來呼叫其它函式所用到的暫存器總數,與指令集總個數(以16bits為單位),格式如下所示

registers : 10 (包含函式參數,區域變數與中間資料搬移時所會用到的暫存器個數加總)

ins : 4 (Method函式參數用到的暫存器個數 =>都會加上第一個參數指到Class Object 本身)

outs : 3 (Method 中呼叫其它函式所用到的暫存器總數)

insns size : 31 16-bit code units (以16bits為單位,統計這個Method所佔用的指令總長度)

Dalvik虛擬器一個最大的特徵就是不同於過去其他Java VM為 Stack-based的VM,它是一個Register-based的VM,在對應到ARM處理器的實作時,可以透過原生處理器的暫存器進行優化. 同時,在Dalvik ARM的實作中有些ARM處理器暫存器已經被Dalvik 虛擬器本身,gcc編譯器或是ARM的Calling Convention所使用,如下就列出有被指定使用的暫存器儘供參考.

ARM暫存器	識別名稱	說明
R0/R1/R2/R3/R9/R10		這6個ARM暫存器,是在實現Dalvik指令時,會被使用的ARM暫存器.
R4	rPC	interpreted program counter, used for fetching instructions (Dalvik預定用途)
R5	rFP	interpreted frame pointer, used for accessing locals and args (Dalvik預定用途)
R6	rGLUE	MterpGlue pointer (Dalvik預定用途)
R7	rINST	first 16-bit code unit of current instruction (Dalvik預定用途)
R8	rIBASE	interpreted instruction base pointer, used for computed goto (Dalvik預定用途)
R11	fp	Used by gcc (unless -fomit-frame-pointer is set)
R12	ip	ARM Intra-Procedure-call scratch register
R13	sp	ARM Stack Pointer
R14	lr	ARM Link Register
R15	pc	ARM Program Counter

Dalvik 虛擬器,主要會讓虛擬器的暫存器與資料對應到ARM的R0,R1,R2,R3,R9與R12共6個暫存器,作為Dalvik Register-Based虛擬器執行與加速之用.可參考如下例子

.L_OP_CONST_WIDE: /* 0x18 */

/* File: armv5te/OP_CONST_WIDE.S */

/* const-wide vAA, #+HHHHhhhhBBBBbbbb */

FETCH(r0, 1) @ r0<- bbbb (low)

FETCH(r1, 2) @ r1<- BBBB (low middle)

FETCH(r2, 3) @ r2<- hhhh (high middle)

orr r0, r0, r1, lsl #16 @ r0<- BBBBbbbb (low word)

FETCH(r3, 4) @ r3<- HHHH (high)

mov r9, rINST, lsr #8 @ r9<- AA

orr r1, r2, r3, lsl #16 @ r1<- HHHHhhhh (high word)

FETCH_ADVANCE_INST(5) @ advance rPC, load rINST

add r9, rFP, r9, lsl #2 @ r9<- &fp[AA]

GET_INST_OPCODE(ip) @ extract opcode from rINST

stmia r9, {r0-r1} @ vAA<- r0/r1

GOTO_OPCODE(ip) @ jump to next instruction

基本的DEX檔案中會包括如下的Register對應到行數存在的範圍,

com.testAA.testAA.MainX:(I)V

0000: [0130] move v0, v3

0001: [da01 0302] mul-int/lit8 v1, v3, #int 2 // #02

0003: [f520 b000] +iput-quick v0, v2, [obj+00b0]

0005: [f521 b400] +iput-quick v1, v2, [obj+00b4]

0007: [0e00] return-void

locals :

0x0001 – 0x0008 reg=0 vA I

0x0003 – 0x0008 reg=1 vB I

0x0000 – 0x0008 reg=2 this Lcom/testAA/testAA;

0x0000 – 0x0008 reg=3 A I

這會表示,暫存器v0對應到區域變數vA,存在範圍從1-8 ByteCode指令行數.而v3對應到函式參數A,存在範圍從0-8 ByteCode指令行數.

為了達到更有效率的系統加速,Dalvik提供了針對處理器的Register Map機制,主要是在Dex檔案進行Verification時,同步的根據每個指令集的行為,對應到目前要執行的處理器的暫存器使用,使得最後在運作時,相關的變數,Method與Class都已經根據暫存器的使用與長度而有對應的排列,因為是在Verification中進行的,也就是說只有ODEX檔案格式中才會包含這個區塊,參考Android的文件,有加入Register Map資訊的ODEX檔案,可能會比原本的DEX檔案多出25%的儲存需求,也因此Android在dalvik/vm/analysis/RegisterMap.c中其實也有實作JIT版本的Register Map,以便搭配Trace-JIT的機制,既希望可以達到Register Map的目標,又希望可以達到Trace-JIT節省記憶體需求的優勢,目前已筆者手中的程式碼來看,這個機制目前尚未啟用,且也有可能Android未來會移除這部份的程式碼實作.

如果Dalvik VM在啟動時有加上 “-Xgenregmap”參數,之後在進行DEX檔案的最佳化時就會呼叫函式dvmGenerateRegisterMaps (實作在dalvik/vm/analysis/RegisterMap.c),在ODEX檔案中產生RegisterMap,執行中,會先配置4MB的記憶體區塊,然後呼叫函式writeMapsAllClasses,writeMapsAllMethods,writeMapForMethod,computeRegisterMapSize產生Register Map資訊.

參考dalvik/vm/analysis/RegisterMap.c中函式dvmGenerateRegisterMapV的實作,

regWidth = (vdata->method->registersSize + 7) / 8;

regWidth長度每一個bit都會對應到每一個Method中所用到的暫存器. 如果,一個函式用到四個暫存器(V0,V1,V2與V3),其中V1跟V3屬於RegTypeUninit,在第0行會用到V1,此時的RegisterMap內容值會為b0010=0x02 (bit 1會設為1). 在第4行會用到V3,則RegisterMap會為b1010=0x0a (bit 1與bit3會設為1),目前RegisterMap會根據所用到的暫存器順序,對應到regWidth長度(in bytes)中每一個bit值. 設定為1的bit,所對應的暫存器值,會是需要在運作時,進行初始化的暫存器.

此外,在設定dalvik.vm.dexopt-flags 時加入m=y,也可以開啟 Register Map最佳化參數

setprop dalvik.vm.dexopt-flags v=a,o=v,m=y

(或是把dalvik.vm.dexopt-flags= v=a,o=v,m=y 加入到開機Property參數檔中亦可)

Dalvik的Register Map主要用來表示哪一個Register的Type屬於kRegTypeUninit或是大於kRegTypeMAX(實作程式碼可以參考dalvik/vm/analysis/RegisterMap.c中的函式outputTypeVector),在實際的執行上,例如以下的暫存器會屬於kRegTypeUninit. (Uninitial–在執行時期才指定對應的值)

1,對應到Class Object所用到的暫存器

2,Return Class Object所用到的暫存器

舉實際的例子來說,

com.htc.android.worldclock.widget.NumberTableView.TableAdapter.getItem:(I)Ljava/lang/Object;

0000:invoke-static {v2}, Ljava/lang/Integer;.valueOf:(I)Ljava/lang/Integer; // method@0a4e

0003:move-result-object v0

0004:return-object v0

locals :

0x0000 – 0x0005 reg=1 this Lcom/htc/android/worldclock/widget/NumberTableView$TableAdapter;

0x0000 – 0x0005 reg=2 position I

由於v1暫存器符合條件,所以第0行的RegisterMap為b0010=0x02

由於第四行透過v0返回Class物件參考且v1符合條件,所以第四行的RegisterMap為b0011=0x03

參考Register Map結果如下

#1: 0x00061628 getItem

0: 02

4: 03

再舉如下的例子來說明

com.htc.android.worldclock.widget.MyScrollView.<init>:(Landroid/content/Context;Landroid/util/AttributeSet;)V

0000: const/4 v0, #int 0 // #0

0001: invoke-direct {v1, v2, v3, v0}, Lcom/htc/android/worldclock/widget/MyScrollView;.<init>:(Landroid/content/Context;Landroid/util/AttributeSet;I)V // method@0902

0004: return-void

locals :

0x0000 – 0x0005 reg=1 this Lcom/htc/android/worldclock/widget/MyScrollView;

0x0000 – 0x0005 reg=2 context Landroid/content/Context;

0x0000 – 0x0005 reg=3 attrs Landroid/util/AttributeSet;

暫存器v1,v2,v3都指向對應的Class Object而返回值為void,所以行數1與4對應的RegisterMap為b1110=0x0e

參考Register Map結果如下

#1: 0x00061564 <init>

1: 0e

4: 0e

再舉如下的例子來說明

com.htc.android.worldclock.TimeZonePicker.SimpleSearchModule.access$1300:(Lcom/htc/android/worldclock/TimeZonePicker$SimpleSearchModule;Ljava/lang/String;)Landroid/database/Cursor;

0000: invoke-direct {v1, v2}, Lcom/htc/android/worldclock/TimeZonePicker$SimpleSearchModule;.coreSearch:(Ljava/lang/String;)Landroid/database/Cursor; // method@06fc

0003: move-result-object v0

0004: return-object v0

locals :

0x0000 – 0x0005 reg=1 x0 Lcom/htc/android/worldclock/TimeZonePicker$SimpleSearchModule;

0x0000 – 0x0005 reg=2 x1 Ljava/lang/String;

v1與v2暫存器符合條件,都指向對應的Class Object,所以第0行的RegisterMap為b0110=0x06

由於第四行透過v0返回Class物件參考且v1與v2符合條件,所以第四行的RegisterMap為b0111=0x07

參考Register Map結果如下

#1: 0x0005fad8 access$1300

0: 06

4: 07

由上述舉例,我們可以知道Register Map可以表示每一個Class中的每一個Method所用到的暫存器有哪一個是尚未被初始化而必須要在執行階段解決Class Object相對位址的,藉此可以在Dalvik虛擬器載入DEX檔案執行時,透過 Regfister Map知道每一個函式Method中對應的哪一個暫存器是需要在執行階段解決對應位置的,藉此讓虛擬器可以在執行階段優化處理,加速執行的效率.

Register Map在Optimized DEX檔案中的資料格式為.

(有關Virtual Method與Direct Method分別的總數,會透過Class Definition中的classDataOff值,對應到struct DexClassDataHeader中的virtualMethodsSize與 directMethodsSize取得)

欄位屬性	長度	說明
Class and Method Information	4bytes	Number of Classes
	4bytes * Number of Classes	Classes Data Offset
	…………. ………………………. (4 bytes Class Offset)…… …………..
	2 bytes	Method Count for the Class包含Direct Methods與Virtual Methods的總數 (不超過2^16)
	2 bytes	two pad bytes follow methodCount
Direct Methods	1 byte	Direct Methods RegMapFormat kRegMapFormatNone (addrWidth = 0;) kRegMapFormatCompact8 (addrWidth = 1;) kRegMapFormatCompact16 (addrWidth = 2;) kRegMapFormatDifferential
	1 byte	regWidth
	2 byte	NumEntries (不超過2^16)
	0 , 1 or 2 bytes	指令Address (以 addrWidth為依據)
	1 bytes * regWidth	Register 長度
Virtual Methods	1 byte	Virtual Methods RegMapFormat kRegMapFormatNone (addrWidth = 0;) kRegMapFormatCompact8 (addrWidth = 1;) kRegMapFormatCompact16 (addrWidth = 2;) kRegMapFormatDifferential
	1 byte	regWidth
	2 byte	NumEntries (不超過2^16)
	0 , 1 or 2 bytes	指令Address (以 addrWidth為依據)
	1 bytes * regWidth	Register 長度

Dex檔案的資料型態

LEB128(Little-Endian Base 128) 是一個可將signed與unsigned 32bits整數資料編碼為可變長度資料的格式,主要是參考DWARF3(除錯檔案格式)的標準而來(參考網址http://dwarfstd.org/Dwarf3Std.php ). 每一個LEB128編碼的資料長度可為1到5bytes,用以表示一個32-bits的整數值.對singed LEB128來說,最後一個bytes,的最高bit會用來表示該32-bits值的正負.

以如下2bytes Unsigned LEB128數值為例

0x90 20

Bitwise diagram of a two-byte LEB128 value

First Byte

Second Byte

1

Bit6

Bit5

Bit4

Bit3

Bit2

Bit1

Bit0

0

Bit13

Bit12

Bit11

Bit10

Bit9

Bit8

Bit7

第1個byte 0x90 & 0x80 不為0,表示尚未到結尾

第2個byte 0x20 & 0x80 為0,表示到結尾

所以Unsigned LEB128結果為 0x90&0x7f + (0x20&0x7f) <<7 = 0x1010

以如下3 bytes Unsigned LEB128數值為例

0xd4 df 04

Bitwise diagram of a three-byte LEB128 value

First Byte

Second Byte

Third Byte

1

Bit6

Bit5

Bit4

Bit3

Bit2

Bit1

Bit0

1

Bit13

Bit12

Bit11

Bit10

Bit9

Bit8

Bit7

0

Bit20

Bit19

Bit18

Bit17

Bit16

Bit15

Bit14

第1個byte 0xd4 & 0x80 不為0,表示尚未到結尾

第2個byte 0xdf & 0x80 不為0,表示尚未到結尾

第3個byte 0x04 & 0x80 為0,表示到結尾

所以Unsigned LEB128結果為 0xd4&0x7f + (0xdf&0x7f) <<7 + (0x04&0x7f) <<14= 0x012fd4

以如下4 bytes Unsigned LEB128數值為例

0xb8 84 80 01

Bitwise diagram of a fourth-byte LEB128 value

First Byte

Second Byte

Third Byte

Fourth Byte

1

Bit6

Bit5

Bit4

Bit3

Bit2

Bit1

Bit0

1

Bit13

Bit12

Bit11

Bit10

Bit9

Bit8

Bit7

1

Bit20

Bit19

Bit18

Bit17

Bit16

Bit15

Bit14

0

Bit27

Bit26

Bit25

Bit24

Bit23

Bit22

Bit21

第1個byte 0xb8 & 0x80 不為0,表示尚未到結尾

第2個byte 0x84& 0x80 不為0,表示尚未到結尾

第3個byte 0x80 & 0x80 不為0,表示尚未到結尾

第4個byte 0x01 & 0x80 為0,表示到結尾

所以Unsigned LEB128結果為 0xb8&0x7f + (0x84&0x7f) <<7 + (0x80&0x7f) <<14 + (0x01&0x7f) <<21 = 0x200238

以如下1 bytes Signed LEB128數值為例

0x1c

第1個byte 0x1c & 0x80 為0,表示到結尾

所以Signed LEB128結果為 ((0x1c&0x7f )<< 25) >> 25 = 0x1c

以如下2 bytes Signed LEB128數值為例

0x8e 04

Bitwise diagram of a two-byte LEB128 value

First Byte

Second Byte

1

Bit6

Bit5

Bit4

Bit3

Bit2

Bit1

Bit0

0

Bit13

Bit12

Bit11

Bit10

Bit9

Bit8

Bit7

第1個byte 0x8e & 0x80 不為0,表示尚未到結尾

第2個byte 0x04 & 0x80 為0,表示到結尾

所以Signed LEB128結果為 ((0x8e&0x7f + (0x04&0x7f) <<7)<< 18) >> 18 = 0x020e

以如下3 bytes Signed LEB128數值為例

0xd1 db 7e

Bitwise diagram of a three-byte LEB128 value

First Byte

Second Byte

Third Byte

1

Bit6

Bit5

Bit4

Bit3

Bit2

Bit1

Bit0

1

Bit13

Bit12

Bit11

Bit10

Bit9

Bit8

Bit7

0

Bit20

Bit19

Bit18

Bit17

Bit16

Bit15

Bit14

第1個byte 0xd1 & 0x80 不為0,表示尚未到結尾

第2個byte 0xdb & 0x80 不為0,表示尚未到結尾

第3個byte 0x7e & 0x80 為0,表示到結尾

所以Signed LEB128結果為 ((0xd1&0x7f + (0xdb&0x7f) <<7 + (0x7e&0x7f) <<14) << 11) >> 11= (0x1add1 << 11)>>11 = 0xffffadd1

LEB128的形態還包括了Unsigned LEB128p1,編碼的方式為將要編碼的32-bits值加一後,依循Unsigned LED128方式編碼為1-5 bytes的結果,解碼時,則將1-5bytes Unsigned LEB128的值,解回32bits值後減一,則可還原原本32-bits值的結果.

參考Android文件有如下表格,可以清楚表達 Singed LEB128,Unsigned LEB128與Unsigned LEB128p1 的差別

編碼後的結果	Signed LEB128	Unsigned LEB128	Unsigned LEB128p1
0x00	0	0	-1
0x01	1	1	0
0x7f	(0xffffffff) = -1	127	126
0x80 7f	(0xffffff80)= -128	16256	16255

其他變數型態列表如下

型態名稱	說明
byte	8-bit signed int
ubyte	8-bit unsigned int
short	16-bit signed int, little-endian
ushort	16-bit unsigned int, little-endian
int	32-bit signed int, little-endian
uint	32-bit unsigned int, little-endian
long	64-bit signed int, little-endian
ulong	64-bit unsigned int, little-endian
sleb128	signed LEB128
uleb128	unsigned LEB128, variable-length (see below)
uleb128p1	unsigned LEB128 plus 1, variable-length (see below)

MUTF-8 (Modified UTF-8) Encoding

一個標準的UTF-8編碼的格式如下所示 （也可以參考網頁 )http://en.wikipedia.org/wiki/UTF-8

Bits	Last code point	Byte 1	Byte 2	Byte 3	Byte 4	Byte 5	Byte 6
7	U+007F	0xxxxxxx
11	U+07FF	110xxxxx	10xxxxxx
16	U+FFFF	1110xxxx	10xxxxxx	10xxxxxx
21	U+1FFFFF	11110xxx	10xxxxxx	10xxxxxx	10xxxxxx
26	U+3FFFFFF	111110xx	10xxxxxx	10xxxxxx	10xxxxxx	10xxxxxx
31	U+7FFFFFFF	1111110x	10xxxxxx	10xxxxxx	10xxxxxx	10xxxxxx	10xxxxxx

Dex所遵循的語言編碼機制為MUTF-8,跟UTF-8的差異在於

1,只有1,2,3 bytes三種編碼長度,也就是說MUTF-8是專為UTF-16編碼設計的,最長支援16bits Unicode,也因此,不像UTF-8 可支援4,5,6 bytes長度編碼.

2,空字元(NULL)不以0x00編碼,而是兩個bytes 0xc0 0x80,可確保在編碼的字串中,不會有0x00出現,也可避免在例如C語言的處理時,造成字串被截斷.(C語言以0x00做為字串的結尾).

3,由於Java中的字串都是以UTF-16為單位(JNI C Code中為UTF-8),也因此在大於16bits Unicode以上的編碼(例如:U+10000 – U+10ffff ),就會需要兩個Java字元(16bits)來表示,反應到MUTF-8中,就會變成兩個3bytes的編碼. (對應到UTF-8中為4bytes).

Android文件中也提到,MUTF-8類似於CESU-8(都是針對UTF-16設計的編碼),並支援surrogate pairs,相關資訊可以參考CESU-8 Wiki (http://en.wikipedia.org/wiki/CESU-8 ).

結語

本文主要只涉及筆者認為值得說明的DEX檔案格式內容,然Android還在持續的進版中,對應到實作的正確性,還請以各位手中的Source Code為主. 感謝!