前陣子的GBA模擬器實作戰實又中離了,跳回了今年二月有小摸的JVM實作嘗試,當時的進度大概到剖析class檔,了解一下class大概結構,parse出一些初步的東西後就沒繼續下去了,到最近又重回jvm研究.
JVM這一東西,其實可以分成好幾個層面和區塊來看待,如果要寫出最基本的JVM概念雛形,而且能跑些東西的,我現在是做到了,真的說起來並沒有多難,不過如果要完整實作JVM所有的功能部分,以我來說來得下一些功夫,至於寫好後如果要再討論到校能改善議題.記憶體使用效率等等,那就可以說真的昰一門專的研究了,光是初步實作jvm到能跑些簡單demo的階段,應該只能算是學習JVM的運作機制原理.
目前跑起來有些感想,有人說JVM像是一個硬體的模擬器或是虛擬機器,像是一個軟體製作的CPU一樣,我得說我有點持反對的看法,與其說它像是一個軟體的處理器,我倒覺得它比較像是處理程序罷了,真的把它視為硬體來看待分類的話,它歸納於stack machine,跟多數一般我們所認知的處理器register machine差異很大(我想你能說得出來,列舉出來所聽聞的cpu都是register machine).....
stack machine真正硬體上的實作,以聞名的來說很少,運作效率來說肯定不可能比register machine好,為何? 撇開軟體虛擬的不談,即使是真正硬體上的實機也是一樣,原因是stack machine在進行一些資料處理或是運算實,免不了得把資料一下子放到stack,一下子從stack內取出,這一來一往,縱然是最簡單的加減乘除,實際運作步驟就是多register machine的處理方式相當多倍.
回到軟體實作的jvm虛擬機,我真的很懷疑這東西如果真的硬體具現化的話能不能達成或是好不好達成,估計很多部分的功能得刪減,但因為我非硬體專業,這邊就不多評論.
整個JVM的運作分成很多環節,最起步驟,你得把class file的內部結構給k完,並且設計出一套資料結構來放置parse出來的class內容,classfile的內容簡單來說就是一大堆的資料結構,一層包著一層,parse的撰寫方法如果剛開始沒規劃好,對全盤沒了解清楚的話,很容易在parse階段就失敗,但有耐性的話,其實parse並不會太複雜,最主要是說class的資料結構是一層包著一層的,有些資料結構裡面有塞著相同的資料結構,所以在parse的時候某些部分一定要用遞迴的方式比較好處理.
大概就是一堆定義拉...描述拉....分成好幾個節區,還有很多屬性的描述項目,說真的如果只是寫短一點的程式,像是hello world或是迴圈教學的demo,那些定義.描述等等等程式碼bytecode以外的東西可能還比bytecode份量還多, bytecode碼本身並不是唯一的主角,而bytecode碼很多部分的運作也需要搭配那些定義.描述的資料.
如果你能把class檔完整parse完畢,載入到你建立的資料結構內,那開頭最重要的第一步就完成了,再接下去是了解jvm在運作的記憶體模型和stack為主的處理方式,我得說以我實作到現在,我直接感受到的昰JVM的記憶體模型和管理其實才是真正的重頭大戲,bytecode本身反來沒那麼複雜,bytecode所用的opcode為固定一個byte,最多256個指令,但實際上目前還沒那麼多,不到210個,這210個opcode基本上就spec怎麼描述,你了解後照作而已,而且很多的動作都很相似,只是處理的資料類型不同而已,因此真正實作比較需要花功夫的還是JVM記憶體模型的了解.
這邊就只講最基本的部分,jvm因為是stack base,因此所有操作幾乎都離不開跟stack的關係,運作一個method有幾個最重要的主角, 1.PC(program counter) 2.操作 stack 3.local varible array , pc不用談就是指執行bytecode實後處理到位置哪裡的記錄 , 而local varible array 的角色有點像是register mchine的registers,舉個例子來說
public void test(int a, int b , int c)
{
int d = 23;
.............................
}
其中船地參數 a b c 和method裡面配置的 d , 這四個數會依序被放入到 local varible array 內,然後接下來的操作過程,就是一步一步把 local varible array 內的 item 塞入到 操作stack中,一下子push . 一下子又pop 來回好幾次 ,最後算出結果.........就是這樣.
跟一般硬體的pc不同,每進入到一個method內,它都有自己獨立的pc,當然也有自己獨立的資料區域,所以如果在method中又進入method,就又會有另一份 pc . stack . local varible array ,我們可以把這獨立的記憶體資料結構視為是一個frame stack,因為可能method裡面會呼叫method,然後重複進入,形成遞迴的行為,所以stack frame也是會動態增加的,每進入method,stack frame就隨之新增,到離開後stack frame就被pop移出.
(其實也沒特別需要去實作frame stack...一般程式語言遞迴處裡下去就好,效果一樣的)
上面說的只是jvm的一個運作部分,還有共享資料區域等等不少沒談到,因為也還沒實作到,而建立物件.繼承.多thread那幾塊也還沒去摸到.....看來看去都是記憶體管理的學問比較重.
跟我當初所想像的不同,撰寫JVM比較不那麼像真正在寫硬體或是遊戲主機的模擬器,反來比較像是了解一門學問或是軟體處裡的方法,class檔的運作也不同於遊戲 rom , 與其實說class像是機械碼這種東西,還不如說它比較像是描述或是定義,連CODE的部分在JVM內也被這樣看待成是屬性描述的一部分罷了....
如果真的有硬體實作版的JVM,我比較好奇能夠實做到哪種程度,畢竟有些比較適合用軟體去呈現.
說真的了解內容後,對JVM的興趣反來降低一些,也許會到某種程度後到一段落.
跟jvm相比LLVM更接近於真正硬體上的概念,以後有空再來看看.
2015年9月27日 星期日
2015年9月8日 星期二
邏輯移位(Logical shift)與算術移位(Arithmetic shift)
https://en.wikipedia.org/wiki/Logical_shift (邏輯移位)
https://en.wikipedia.org/wiki/Arithmetic_shift (算數移位)
這又是以前學生時代有學過的觀念,但後來又還回去的東西...
溫習一下....因為這在arm指令模擬中不少地方都得用到.
簡單來說邏輯移位不管左右移,一律都是把多出來的位數塞零.
而算術運算左移跟邏輯移位一樣塞零,右移需要考慮到singed的屬性,假若最高位是1,則填補1,最高位是0,則填補0.
簡單扼要....
要注意的是,要確定好自己語言的位移運算到底是怎麼運作,否則結果可能跟所想不同.
c# wiki中有提到 :
Some languages, such as the .NET Framework and LLVM, also leave shifting by the bit width and above "unspecified" (.NET) or "undefined" (LLVM). Others choose to specify the behavior of their most common target platforms, such as C Sharp (programming language) which specifies the x86 behavior.
目前在微軟x86平台上不管是邏輯還是算數移位, 一律都是以 << 和 >> 來當 左右移位運算符號,邏輯跟算數的差異在於被平移的數字以 singed 還是 unsigned 來表示 , 如果被平移的數是unsigned的,則會進行邏輯平移,如果被平移的數是signed則會進行算數平移.
ex.
int a = 1234;
int b = 6;
int r = a >> b ; (邏輯平移運算)
===
uint a = 1234 ;
int b = 6 ;
uint r = a >> 6 ; (算數平移運算)
應該多數狀況是通用,但不保證其他少數個別平台或是個別實作也是一樣的狀況.
https://en.wikipedia.org/wiki/Arithmetic_shift (算數移位)
這又是以前學生時代有學過的觀念,但後來又還回去的東西...
溫習一下....因為這在arm指令模擬中不少地方都得用到.
簡單來說邏輯移位不管左右移,一律都是把多出來的位數塞零.
而算術運算左移跟邏輯移位一樣塞零,右移需要考慮到singed的屬性,假若最高位是1,則填補1,最高位是0,則填補0.
簡單扼要....
要注意的是,要確定好自己語言的位移運算到底是怎麼運作,否則結果可能跟所想不同.
c# wiki中有提到 :
Some languages, such as the .NET Framework and LLVM, also leave shifting by the bit width and above "unspecified" (.NET) or "undefined" (LLVM). Others choose to specify the behavior of their most common target platforms, such as C Sharp (programming language) which specifies the x86 behavior.
目前在微軟x86平台上不管是邏輯還是算數移位, 一律都是以 << 和 >> 來當 左右移位運算符號,邏輯跟算數的差異在於被平移的數字以 singed 還是 unsigned 來表示 , 如果被平移的數是unsigned的,則會進行邏輯平移,如果被平移的數是signed則會進行算數平移.
ex.
int a = 1234;
int b = 6;
int r = a >> b ; (邏輯平移運算)
===
uint a = 1234 ;
int b = 6 ;
uint r = a >> 6 ; (算數平移運算)
應該多數狀況是通用,但不保證其他少數個別平台或是個別實作也是一樣的狀況.
2015年9月3日 星期四
ARM指令碼解碼技巧 進階取巧篇
剛好有看到這篇 http://imrannazar.com/ARM-Opcode-Map ,雖然不知道確切的原理(應該跟邏輯層的設計方式有關係) , 但 arm 32bits指令只要靠bits 27~20與7~4就可判斷指令格式,thumb的則為bits 15~12與 11~8 .
平平是RISC,為啥MIPS就沒這麼麻煩...
以32bits來說共需12bits成判斷,thumb要靠8bits.
如果把判斷特徵位元可能的狀況列表出來,thumb至多不會超過256狀況,arm多了不少為 4096狀況,但因為某些位元已經固定住了,實際case會少上不少,不過若是人工手動撰寫,還是一件相當麻煩的事情.
因此以我個人來說,我的處理方式是借用程式,自己建立了兩個表單(arm跟thumb版),表單是把可能的格式列出(判斷特徵位元),列出幾個範例 (以arm 32bits為範例)
ps由於這樣的表格無法表現出位元之間相互的依存關係,所以讓後面的行數規則建立出來的items覆蓋前面的分類,也就是說前面若建立出 xxx 是某格式的指令 , 後面又同樣出現了 xxx 是某另一格式的指令,會以後來的為主.
000*****0**1;Data Processing
000********0;Data Processing
001*********;Data Processing
00010*000000;MRS
00*10*10****;MSR
000000**1001;Multiply
00001***1001;Multiply Long
00010*001001;Single Data Swap
000100100001;Branch and Exchange
000**0**1011;Halfword Data Transfer : Register Offset
000**0**1101;Halfword Data Transfer : Register Offset
000**0**1111;Halfword Data Transfer : Register Offset
000**1**1011;Halfword Data Transfer : Immediate Offset
000**1**1101;Halfword Data Transfer : Immediate Offset
000**1**1111;Halfword Data Transfer : Immediate Offset
010*********;Single Data Transfer
011********0;Single Data Transfer
011********1;Undefined
100*********;Block Data Transfer
101*********;Branch
110*********;Coprocessor Data Transfer
1110*******0;Coprocessor Register Operation
1110*******1;Coprocessor Register Transfer
1111********;Software Interrupt
0.1代表必定的固定位元,*代表有0或1兩種可能,這一串 0 . 1 . * 由 bits 27~20 與 bits 7~4 所構成,程式自動去列出表單格式所有可能,生成switch裡面的 case 項目.
case ...: case ..: case ...: ..............
{
}
break;
case...: case ...: case ...: ............................
{
}
break;
.
.
.
.
.
.
因此抓到指令後只要把特定的位元抓出來串列,透過這程式自動匯出的switch來判斷,就自然而然能進行解碼,不需要再一堆if else 因為多重判斷而減低解碼效率了.
解碼僅需幾個流程,抓指令,把指令特定幾個位元抓出串連,switch串連的數值,解碼完成.
不過像是 Data Processing 的切分出格式後,後續還要進一步抓opcode來判斷要做啥記算.
以上給有興趣的人參考.
平平是RISC,為啥MIPS就沒這麼麻煩...
ARM指令碼解碼技巧 ARM處理篇
ARM指令並沒有一個固定長度與位置的opcode碼,告訴你這指令為何.要做那些處理,但相對的ARM指令可以區分成幾種制式的格式 , 官方Datasheet資料有列出 32bits長度的ARM指令格式與16bits thumb格式(arm的16bits指令稱為thumb),
要解碼arm的指令,跟之前z80或是6502不同,由於沒有一個明確的opcode告知,我們能做的是判斷指令為何種格式,走這種途徑的處理方式當然只能用很多 if else 連續判斷一些條件,來拆解格式,每種格式在特定的幾個地方都會有固定不變的位元設定,我們只要按照那些於特定地點的位元特徵,就可以拆解判斷出為何種格式的指令.
通常如果沒有對ARM每一個指令格式有深入了解,第一個會遇到的問題就是,某些指令格式似乎會有模稜兩可的問題,這也是解ARM指令最討厭的地方,也是入門者剛開始會遇到的最主要問題.
cpu指令一定不會有一個指令,各自表述的情況發生,那ARM是怎麼回事?
其實關鍵就在於不能光看格式表的資料,還得深入指令各位元相互存在的關係,也就是說雖然某幾個位元不是固定位元,理論上填入0或是1都可以,但實際上某幾個位元會跟著某指令某位元的設定而有特定的形式,如果沒有按照幾個特定形式,它就轉成別的指令格式了.
也就是說這些看似模凌兩可的指令格式,其實都有嚴謹的關係規則,剛好避開重覆解釋的衝突.
這種做法是滿巧妙的,但相對的程式處理自然複雜,需要對指令格式的規則有深入的了解,用if else 好幾個複合而且連續的判斷去拆解出正確的解指令格式解碼.
這邊列出期中幾個arm 32bits的特殊衝突狀況...
thumb 16bits的特殊衝突狀況.....
但......也有比較快的方式,可以避開始用一堆if else...下面繼續談到
要解碼arm的指令,跟之前z80或是6502不同,由於沒有一個明確的opcode告知,我們能做的是判斷指令為何種格式,走這種途徑的處理方式當然只能用很多 if else 連續判斷一些條件,來拆解格式,每種格式在特定的幾個地方都會有固定不變的位元設定,我們只要按照那些於特定地點的位元特徵,就可以拆解判斷出為何種格式的指令.
通常如果沒有對ARM每一個指令格式有深入了解,第一個會遇到的問題就是,某些指令格式似乎會有模稜兩可的問題,這也是解ARM指令最討厭的地方,也是入門者剛開始會遇到的最主要問題.
cpu指令一定不會有一個指令,各自表述的情況發生,那ARM是怎麼回事?
其實關鍵就在於不能光看格式表的資料,還得深入指令各位元相互存在的關係,也就是說雖然某幾個位元不是固定位元,理論上填入0或是1都可以,但實際上某幾個位元會跟著某指令某位元的設定而有特定的形式,如果沒有按照幾個特定形式,它就轉成別的指令格式了.
也就是說這些看似模凌兩可的指令格式,其實都有嚴謹的關係規則,剛好避開重覆解釋的衝突.
這種做法是滿巧妙的,但相對的程式處理自然複雜,需要對指令格式的規則有深入的了解,用if else 好幾個複合而且連續的判斷去拆解出正確的解指令格式解碼.
這邊列出期中幾個arm 32bits的特殊衝突狀況...
- Single Data Transfer與Undefined 按照格式表會產生重覆衝突, 但 Single Data Transfer bit 25 與 bit 4 之間的可能關係,剛好會避開Undefined的重覆衝突.
- Data Processing與PSR Transfer 按照格式表會產生重覆衝突,但Data Processing中bit 24~24操作碼的TST.TEQ.CMP.CMN必定得設定bit 20為1,若bit 20不為1,則釋譯為PSR Transfer(MRS或MSR).
- Single Data Swap 與 Halfword Data Transfer 按照格式表會產生重覆衝突,但 Halfword Data Transfer的 bit 6與5 若為 00 則解釋為Single Data Swap .
thumb 16bits的特殊衝突狀況.....
- Format 1: move shifted register 與 Format 2: add/subtract 兩指令格式有重疊,格式1 bit(12,11)不能為 (1,1) , 以此來區分
- Format 16: conditional branch 與 Format 17: software interrupt 格式16 cond 不能為1111 , 以此來區分,
但......也有比較快的方式,可以避開始用一堆if else...下面繼續談到
ARM指令碼解碼技巧 基本介紹篇
這邊的解碼並不是指邏輯電路層的解碼處理(但如果開發者專業背景有涉及這最底層的硬體設計知識,對於開發相當有幫助),而是指指令碼如何透過模擬器來正確解譯(這指令要以啥方式來解讀,然後它要做那些事情).
早在8bits CISC微處理器像 z80 或是 6502 , 解碼是相當簡單的事情,因為它們的格式相當固定簡單,通常是一個byte的opcode搭配上後面幾個bytes的參數合成一個最基本的指令,
[opcode][參數1][參數1] (共3byte)
[opcode][參數1][參數2] [參數3](共4byte)
每一次抓取指令單元,先抓地一個byte,判讀opcode,看看後面還要抓幾個byte構成完整指令,之後pc更新(加上opcode和參數所佔的空間之後的位址就是下一個要抓的opcode),再繼續相同的流程.
目前看過三種流程的判讀方式,用 if elseif elseif ..... esle 許多條件判斷來做為每次處理的方式
if ( opcode 是否為 #1)
{
執行#1的處理
}
elseif ( opcode 是否為#2 )
{
執行#2的處理
}
.
.
.
.上頭似乎是最差的方式....不過隨著後來cpu指令格式的複雜,有時後類似的處理是必要的
接著使改用 switch (opcode) { case #1: ...... 的方式
switch ( opcode)
{
case 0:
執行 #0 的處理
break;
case 1:
執行#1的處理
break;
.
.
.
.
}
還有一種跟switch很類似 , 就是 array 裡頭放置 function 的進入 point ,以8 bits 的 cpu來說, opcode為1byte,共有255種可能,宣告一個array放入對應的function進入點,解碼opcode和處理只要呼叫 array[opcode編號] 即可.
效能上 [通常] 以switch或是 function array 會比較好,但實際處理效能,可能還是得測試,撇開校能比較 , function array 的處理概念相對是比較進階一點的方式.
很多時候單一opcode還不夠,某些指令會由主opcode跟子opcode所構成,第一個opcde跟你說你可能接下來會做哪些事情,第二個子opcode才明確跟你說是哪些事情中的第幾件事情.
8bits cise 微處理器相對來說解碼簡單很多.
而ARM的解碼則相對複雜 !
早在8bits CISC微處理器像 z80 或是 6502 , 解碼是相當簡單的事情,因為它們的格式相當固定簡單,通常是一個byte的opcode搭配上後面幾個bytes的參數合成一個最基本的指令,
[opcode][參數1][參數1] (共3byte)
[opcode][參數1][參數2] [參數3](共4byte)
每一次抓取指令單元,先抓地一個byte,判讀opcode,看看後面還要抓幾個byte構成完整指令,之後pc更新(加上opcode和參數所佔的空間之後的位址就是下一個要抓的opcode),再繼續相同的流程.
目前看過三種流程的判讀方式,用 if elseif elseif ..... esle 許多條件判斷來做為每次處理的方式
if ( opcode 是否為 #1)
{
執行#1的處理
}
elseif ( opcode 是否為#2 )
{
執行#2的處理
}
.
.
.
.上頭似乎是最差的方式....不過隨著後來cpu指令格式的複雜,有時後類似的處理是必要的
接著使改用 switch (opcode) { case #1: ...... 的方式
switch ( opcode)
{
case 0:
執行 #0 的處理
break;
case 1:
執行#1的處理
break;
.
.
.
.
}
還有一種跟switch很類似 , 就是 array 裡頭放置 function 的進入 point ,以8 bits 的 cpu來說, opcode為1byte,共有255種可能,宣告一個array放入對應的function進入點,解碼opcode和處理只要呼叫 array[opcode編號] 即可.
效能上 [通常] 以switch或是 function array 會比較好,但實際處理效能,可能還是得測試,撇開校能比較 , function array 的處理概念相對是比較進階一點的方式.
很多時候單一opcode還不夠,某些指令會由主opcode跟子opcode所構成,第一個opcde跟你說你可能接下來會做哪些事情,第二個子opcode才明確跟你說是哪些事情中的第幾件事情.
8bits cise 微處理器相對來說解碼簡單很多.
而ARM的解碼則相對複雜 !
溢位跟進位 (overflow & carry)
不知道多少人跟我一樣從學校畢業已久,出社會後因為工作難再碰到一些以前學過的東西,所以久而久之很多東西慢慢忘光光....但寫模擬器最重要的是很多基礎的硬體觀念,了解得越深越多越好,無奈就是很多計概.計組的東西已經還給學校了,要自已重新K回來.
寫模擬器一定會碰到處理器旗幟狀態的處理,這其中又以 溢位 跟 進位 最容易讓人混淆,查了一些資料後,總算釐清. 在此推建 http://www.mouseos.com/arch/Overflow.html 這連結內的解說.
在了解溢位跟進位前,2的補數觀念一定要有才能繼續.
(下面說的是連結內的例子)
簡單來說 , carry 發生在兩數計算結果已經超過數字二進位長度所能表示範圍,這是一件事情.
而overflow發生在兩數計算所得最後結果因為2補數表示範圍關係,造成正負號屬性錯誤,這叫溢位.
4bits長度以2補數來表示一個數字 +7 => 0111 , (+7) + (+7) = 1110 ,變成 -2 , 產生溢位 (超過4bits的2補數能表示範圍),但並沒有產生進位.
(-4) + (-1) = -5 結果正確,但是產生超過4bits位數範圍的晉升.
歸納簡單來說,進位是指針對超過位元容納長度而言這事情(ex.原本4bit,計算完多出一位元到第5bits去),而溢位是指針對超過2補數能表示的正確計算結果範圍而言,超過2補數能表事的結果未必代表產生進位 (ex.沒超過原本4bits範圍,但結果已經不正確,像是正數加正數,變負數,負數加負數變正數的情況).
寫模擬器一定會碰到處理器旗幟狀態的處理,這其中又以 溢位 跟 進位 最容易讓人混淆,查了一些資料後,總算釐清. 在此推建 http://www.mouseos.com/arch/Overflow.html 這連結內的解說.
在了解溢位跟進位前,2的補數觀念一定要有才能繼續.
(下面說的是連結內的例子)
簡單來說 , carry 發生在兩數計算結果已經超過數字二進位長度所能表示範圍,這是一件事情.
而overflow發生在兩數計算所得最後結果因為2補數表示範圍關係,造成正負號屬性錯誤,這叫溢位.
4bits長度以2補數來表示一個數字 +7 => 0111 , (+7) + (+7) = 1110 ,變成 -2 , 產生溢位 (超過4bits的2補數能表示範圍),但並沒有產生進位.
(-4) + (-1) = -5 結果正確,但是產生超過4bits位數範圍的晉升.
歸納簡單來說,進位是指針對超過位元容納長度而言這事情(ex.原本4bit,計算完多出一位元到第5bits去),而溢位是指針對超過2補數能表示的正確計算結果範圍而言,超過2補數能表事的結果未必代表產生進位 (ex.沒超過原本4bits範圍,但結果已經不正確,像是正數加正數,變負數,負數加負數變正數的情況).
訂閱：
文章 (Atom)
