影像放大或是縮小這種filter議題探討,照理來說應該是數位影像處理古早時代的議題,如果研究生論文想以這為方向,肯定被打槍不用說.....但實際上這方面相關的處理真的是已經到技術成熟的飽和了嗎? 答案我覺得應該相反.....應該是說遇到技術瓶頸,雖然並不完善,但已經莫可奈何了...像是去噪這種古早時代的處理議題,不太可能會有人拿它來發表paper了,但無論怎麼去噪,看過各種方式,就是細節與噪之間的拉扯戰,搬東牆補西牆,只是看平衡的夠好不好,然後到一個程度後就難以再進步,而不是完善到不需要再進步.
電玩模擬器因為原生出的解析度偏低(特別是古早時代的主機或是掌機),會需要將圖像放大,但若單純把pixel用簡單的倍率規則填塞,則出現鋸齒或是醜陋的方塊感,所以一定需要filter去處理,而電玩的畫面的特性其實又跟其他影像不太相同,有自己一套適用的演算法去處理,但由於只是模擬放大,用比較理想的方式去填充pixel,因此一定還是會有不夠精緻之處.
電玩模擬器隨著發展,已經開發出不少種filter,目前考量到複雜度.精緻度.cpu負荷.效能,選擇了scalex . hqx .xbrz 這三套fiter來搭配,這三套嚴格說起來背後的概念都是接近的,計算pattern來選擇如何對應地填入適當的pixel.
scalex特色是演算法相當簡易,對cpu負荷相當低,畫質給人銳利.清晰(不會有原來以外的內插色),但有些粗糙..
HQX跟XBRZ兩套味道比較相似,差異是XBRZ在輪廓處理上似乎比較好,而運算負荷XBRZ則是最吃重.
但由於HQX跟SCALEX沒有官訂的6X演算法(SCALEX甚至只有2X跟3X),因此xbrz的6x對scalex跟hqx來說需要用3x * 2x 的方式去模擬,6x輸出效能反來輸xbrz一大截.
scalex不加入討論,本來就是偏低cpu使用.中庸畫質的filter , 而hqx 跟 xbrz則強調放大的高畫質.
實際上hqx 跟 xbrz 這兩套並沒有哪一套是絕對較佳,應該是說出來後的處理特色不同,牽涉到個人喜好的問題,有些部分 hqx 處理的比較合理,有些部分 xbrz處理的比較合理 (當然所謂的比較合理也牽涉到人的認知和風格問題) , 整體來說 我給xbrz比較高的分數,但xbrz在處理某些部分又顯得比hqx怪異...只能說因為填塞的那些pixel是無中生有的,那些無中生有的部分該怎樣去產生本身就有滿多爭議 (美與醜.正確性???) , 因此即便這兩套filter號稱高畫質 ,但改善的空間還是非常多.
但議題就是這樣,發展到一個程度後,通常就久久難以再突破,而不代表技術完善度已飽和,這也就代表如果你選這當論文,通常很難畢得了業.
2015年12月23日 星期三
2015年12月20日 星期日
April GameBoy Emulator 2015.12.18 更新
官方網站 https://dl.dropboxusercontent.com/u/61164954/project/AprGBEmu/index.htm
2015.12.18 版本說明
1. CPU指令模擬正確度大幅提升
2. 除原本ScaleX外,亦加入HQX與XBRz濾鏡. 詳細說明
3. 增加畫面放大5x(XBRz專屬)與6x(HQ6X CPU Loading較重)設定.
4. FPS效能大幅提升 ( rendering by native win32 gdi api ).
5. 相容性提升 (Rockman Word 4 & 5 可以正常進入關卡了).
6. 增加聲音輸出(實驗性質尚待改善).....
7.介面修改.configure ui
8. etc....
==
Future to do list (越上面處理優先權越高)
a.timing與中斷處理 正確度還需要改善
b.some gpu bug fixed
c.MBC 支援需要增加
d.音質改進
e.GBC.SGB 功能支援 (GBC功能尚不完善,固先將功能封鎖起來)
f.跨平台相容性
1. CPU指令模擬正確度大幅提升
2. 除原本ScaleX外,亦加入HQX與XBRz濾鏡. 詳細說明
3. 增加畫面放大5x(XBRz專屬)與6x(HQ6X CPU Loading較重)設定.
4. FPS效能大幅提升 ( rendering by native win32 gdi api ).
5. 相容性提升 (Rockman Word 4 & 5 可以正常進入關卡了).
6. 增加聲音輸出(實驗性質尚待改善).....
7.介面修改.configure ui
8. etc....
==
Future to do list (越上面處理優先權越高)
a.timing與中斷處理 正確度還需要改善
b.some gpu bug fixed
c.MBC 支援需要增加
d.音質改進
e.GBC.SGB 功能支援 (GBC功能尚不完善,固先將功能封鎖起來)
f.跨平台相容性
2015年11月2日 星期一
血淋淋的教訓與經驗
GB模擬器一直有一個問題,玩RockManWord5時候,選其中兩隻魔王會跳掉,重新回到開始畫面,一直不知道是哪環節出問題,因為有太多可能,還嘗試把人家的模擬器z80 CORE移放過來交叉比對,但花一堆時間還是找不到原因......懷疑是z80指令哪裡有小問題,最後謎底揭曉,當我把人家的opcode cycle table移放過來, cycle time改用別人table後就正常了....
原因是timing的正確性出問題.....但遊戲執行多數看似正常,就特定遊戲跳掉.....
總算解決了.這也就是說模擬器撰寫真的是任何小細節都得注意,否則debug起來真的是死都抓不到原因.....
目前還有一些bug讓我很不能忍受 , GPU的部分實作完有完全正確,有時候畫面怪怪的...timing應該還得再檢查修正,加上音效功能後,作一些整修和優化後,估計會再打包一版(先把GBC功能hide掉,那塊還很多問題...).
功能有限沒有關係,重點是正確無誤比較重要,一步一步用出完整的東西.
接下來就是gbc跟sgb和更多mbc實作功能支援的部分了.
其他想弄的東西先擱置...
原因是timing的正確性出問題.....但遊戲執行多數看似正常,就特定遊戲跳掉.....
總算解決了.這也就是說模擬器撰寫真的是任何小細節都得注意,否則debug起來真的是死都抓不到原因.....
目前還有一些bug讓我很不能忍受 , GPU的部分實作完有完全正確,有時候畫面怪怪的...timing應該還得再檢查修正,加上音效功能後,作一些整修和優化後,估計會再打包一版(先把GBC功能hide掉,那塊還很多問題...).
功能有限沒有關係,重點是正確無誤比較重要,一步一步用出完整的東西.
接下來就是gbc跟sgb和更多mbc實作功能支援的部分了.
其他想弄的東西先擱置...
2015年10月18日 星期日
C# 效能感想
會嘗試使用C#撰寫模擬器,有很多因素,
一方面這是我工作主要使用的語言,
二方面想看看 C# 是否能勝任模擬器的工作,
三方面是希望撰寫出方便教學與理解.移植的程式,不像C/C++很多地方與OS.硬體特性.函式庫有關係上的相連,如果移植有些地方都要花心思磨合一下,這也就是為何我盡量以.NET C#原生官方的資源為主,而沒使用到像是DirectX之類的第三方原件或是直接call win32 api等等做法(不過遊戲搖桿讀取有用到sharpdx,內部是包directx利用的).
這樣搞一搞之後,以現在普通的電腦來說,如果程式寫得還算適當,並且避開某些地雷寫法(C#某些物件導向的高階元件千萬別用,一切用最簡單的方式去做),然後在處理畫面部分,直接用指標去做處理(C#的BitMap物件很慘...一定得用指標直接去讀寫pixel value),整體跑起來其實也沒啥問題 (比較早期的2D遊戲主機,像是GB.GBC.FC.SFC.GBA等等之類的....) , 但這就僅止於跑起來ok而以,如果再加上像是畫面用filter倍率放大,一套用上比較複雜的演算法下去,fps馬上掉到60fps內,甚至一半都不到....
也就是說c# ok ,但僅止於ok而以.
如果真的要求完善完美,不然就是得call native,不然就是得借用dirextx wRapper直接使用硬體加速(GDI真的不適合當成動態畫面播放的媒介,特別是圖片大張時候,記憶體量一大,整個顯示速度就死翹翹),而放大即時的filter運算,c#也很不夠力....
所以c# ok ,但求完美部分關鍵得借用d2d.win32 api或是直接call c method去處理,有沒有發現一個問題? 如果這樣做,那不就跟當初理念違背? 如果跟os.硬體綁上,用c.c++不是更快? 恩...這的確就是一個矛盾的地方.
最後歸納起來,會用c#的原因,大概就最主要是funny和熟悉吧....
如果一開始追求一個寬裕的效能,而不僅止於ok的話,c/c++會是更好的選擇,前提是你熟習它們.
目前效能障礙在
1.real time image filter (如果是hq2x這套,光2x就死翹翹....)
2.bitmap投影速度 (GDI圖越大張,速度越慢)
有些c/c++的專案還會用組語更進階加速.
一方面這是我工作主要使用的語言,
二方面想看看 C# 是否能勝任模擬器的工作,
三方面是希望撰寫出方便教學與理解.移植的程式,不像C/C++很多地方與OS.硬體特性.函式庫有關係上的相連,如果移植有些地方都要花心思磨合一下,這也就是為何我盡量以.NET C#原生官方的資源為主,而沒使用到像是DirectX之類的第三方原件或是直接call win32 api等等做法(不過遊戲搖桿讀取有用到sharpdx,內部是包directx利用的).
這樣搞一搞之後,以現在普通的電腦來說,如果程式寫得還算適當,並且避開某些地雷寫法(C#某些物件導向的高階元件千萬別用,一切用最簡單的方式去做),然後在處理畫面部分,直接用指標去做處理(C#的BitMap物件很慘...一定得用指標直接去讀寫pixel value),整體跑起來其實也沒啥問題 (比較早期的2D遊戲主機,像是GB.GBC.FC.SFC.GBA等等之類的....) , 但這就僅止於跑起來ok而以,如果再加上像是畫面用filter倍率放大,一套用上比較複雜的演算法下去,fps馬上掉到60fps內,甚至一半都不到....
也就是說c# ok ,但僅止於ok而以.
如果真的要求完善完美,不然就是得call native,不然就是得借用dirextx wRapper直接使用硬體加速(GDI真的不適合當成動態畫面播放的媒介,特別是圖片大張時候,記憶體量一大,整個顯示速度就死翹翹),而放大即時的filter運算,c#也很不夠力....
所以c# ok ,但求完美部分關鍵得借用d2d.win32 api或是直接call c method去處理,有沒有發現一個問題? 如果這樣做,那不就跟當初理念違背? 如果跟os.硬體綁上,用c.c++不是更快? 恩...這的確就是一個矛盾的地方.
最後歸納起來,會用c#的原因,大概就最主要是funny和熟悉吧....
如果一開始追求一個寬裕的效能,而不僅止於ok的話,c/c++會是更好的選擇,前提是你熟習它們.
目前效能障礙在
1.real time image filter (如果是hq2x這套,光2x就死翹翹....)
2.bitmap投影速度 (GDI圖越大張,速度越慢)
有些c/c++的專案還會用組語更進階加速.
2015年10月12日 星期一
Linear feedback shift register，LFSR 模擬 white noise 輸出....
關於 線性反饋移位暫存器 介紹如下....
https://zh.wikipedia.org/wiki/%E7%BA%BF%E6%80%A7%E5%8F%8D%E9%A6%88%E7%A7%BB%E4%BD%8D%E5%AF%84%E5%AD%98%E5%99%A8
要先大概知道這是啥....
http://belogic.com/gba/channel4.shtml (雖然這以gameboy advance為教學,但這塊觀念部分與gb互通,實際上gba的sound系統有部分就是沿用gb硬體....)
總之gameboy sound channel 4 用來產生 "模擬" white noise 的輸出,什麼是white noise ??
https://en.wikipedia.org/wiki/White_noise
最簡單的結論就是white noise可以想像成一堆聲音的雜訊,像是廣播沒調準頻道或是傳統電視沒調整到有效頻道所發出的ㄘㄘ聲就是white noise的表現...可視為無規則性亂數產生的雜亂訊息.
這在gb上是channel 4的表現效果,不過gb的white noise並不是真正的完全的隨機亂數(如何用公式或一定的規則算法輸出亂數,滿高深的數學問題...,這邊是用硬體作簡單模擬輸出),而是利用LFSR產生的模擬輸出,由於離開學校久了...剛開始看這塊,真的看得一頭霧水,查了一些資料想了想後,才大概搞清楚這輸出的主要規則,但整個GB SOUND輸出模擬,還有很多地方搞不太懂(跟畫面同步的觀念和模式? 頻率與真正輸出取樣無法整倍數? 超過一般CD 44.1kHZ的超高頻是要怎樣處理?? ),這篇先整理這塊心得.
簡單來說就是 CHANNEL 4 有兩個輸出 模擬亂數的參數, 用 7個 或是 15個暫存器位移記算,來產生模擬亂數續列(之所以說模擬,是因為它的輸出其實是會循環的,不過之後都簡化成亂數輸出稱呼).
先以 7個暫存器的說明範例....
7個暫存器的狀態可以想像成7個連續的bits , bit 7 ~ bit 1 (最低位這邊以bit 1稱呼) ,初始化每個bit都為1,所以為1111111,每一次輸出亂數的過程經過底下幾個步驟
1.輸出最右端的bits當成亂數輸出續列
2.資料右移 >> 1 位,
3.最高位以 bit 1 與 bit 2 的 exor 運算結果填補
4.得到新的 7bits 序列 , 回去 步驟一循環運作
下面C#部分的範例code
byte LSFR = 0x7f; //init 1111111
for (int i = 0; i < 1024; i++) //執行 1024次
{
string b_str = Convert.ToString(LSFR, 2).PadLeft(7, '0');
listBox1.Items.Add(b_str + " " +LSFR.ToString()); //
byte b1 = (byte)(LSFR & 1);
byte b2 = (byte)((LSFR & 2) >> 1);
LSFR >>= 1;
LSFR |= (byte)((b1 ^ b2) << 6);
}
不過channel 4 , 我還有頻率對應輸出的規則沒搞懂...先這樣.
原本以為channel 4 應該是最好k的部分,相比下其實前面1.2.3還容易點.
印象中以前學生時候有學到LFSR這東西,但現在都忘光光了,補回,
ps.LFSR有各種實作的方式,大概都大同小異,這邊僅針對GB硬體的方式來處理,包括像是幾個暫存器,初始值.用哪2個位元來做EXOR填補都可以是變化之一.
比起模擬器cpu.gpu.mem等等實作,我覺得apu聲音輸出這塊對一般人來說最難搞懂,也最難完全實做正確.
https://zh.wikipedia.org/wiki/%E7%BA%BF%E6%80%A7%E5%8F%8D%E9%A6%88%E7%A7%BB%E4%BD%8D%E5%AF%84%E5%AD%98%E5%99%A8
要先大概知道這是啥....
http://belogic.com/gba/channel4.shtml (雖然這以gameboy advance為教學,但這塊觀念部分與gb互通,實際上gba的sound系統有部分就是沿用gb硬體....)
總之gameboy sound channel 4 用來產生 "模擬" white noise 的輸出,什麼是white noise ??
https://en.wikipedia.org/wiki/White_noise
最簡單的結論就是white noise可以想像成一堆聲音的雜訊,像是廣播沒調準頻道或是傳統電視沒調整到有效頻道所發出的ㄘㄘ聲就是white noise的表現...可視為無規則性亂數產生的雜亂訊息.
這在gb上是channel 4的表現效果,不過gb的white noise並不是真正的完全的隨機亂數(如何用公式或一定的規則算法輸出亂數,滿高深的數學問題...,這邊是用硬體作簡單模擬輸出),而是利用LFSR產生的模擬輸出,由於離開學校久了...剛開始看這塊,真的看得一頭霧水,查了一些資料想了想後,才大概搞清楚這輸出的主要規則,但整個GB SOUND輸出模擬,還有很多地方搞不太懂(跟畫面同步的觀念和模式? 頻率與真正輸出取樣無法整倍數? 超過一般CD 44.1kHZ的超高頻是要怎樣處理?? ),這篇先整理這塊心得.
簡單來說就是 CHANNEL 4 有兩個輸出 模擬亂數的參數, 用 7個 或是 15個暫存器位移記算,來產生模擬亂數續列(之所以說模擬,是因為它的輸出其實是會循環的,不過之後都簡化成亂數輸出稱呼).
先以 7個暫存器的說明範例....
7個暫存器的狀態可以想像成7個連續的bits , bit 7 ~ bit 1 (最低位這邊以bit 1稱呼) ,初始化每個bit都為1,所以為1111111,每一次輸出亂數的過程經過底下幾個步驟
1.輸出最右端的bits當成亂數輸出續列
2.資料右移 >> 1 位,
3.最高位以 bit 1 與 bit 2 的 exor 運算結果填補
4.得到新的 7bits 序列 , 回去 步驟一循環運作
下面C#部分的範例code
byte LSFR = 0x7f; //init 1111111
for (int i = 0; i < 1024; i++) //執行 1024次
{
string b_str = Convert.ToString(LSFR, 2).PadLeft(7, '0');
listBox1.Items.Add(b_str + " " +LSFR.ToString()); //
byte b1 = (byte)(LSFR & 1);
byte b2 = (byte)((LSFR & 2) >> 1);
LSFR >>= 1;
LSFR |= (byte)((b1 ^ b2) << 6);
}
不過channel 4 , 我還有頻率對應輸出的規則沒搞懂...先這樣.
原本以為channel 4 應該是最好k的部分,相比下其實前面1.2.3還容易點.
印象中以前學生時候有學到LFSR這東西,但現在都忘光光了,補回,
ps.LFSR有各種實作的方式,大概都大同小異,這邊僅針對GB硬體的方式來處理,包括像是幾個暫存器,初始值.用哪2個位元來做EXOR填補都可以是變化之一.
比起模擬器cpu.gpu.mem等等實作,我覺得apu聲音輸出這塊對一般人來說最難搞懂,也最難完全實做正確.
2015年10月5日 星期一
JVM 心得二 從arduino 談起
目前移植了非常精簡化的JVM版本到ARDUINO,其實只能算是一種技術概念驗證,不是什麼完整的東西,只實現了幾個opcode的指令集,大概足夠跑跑走馬燈範例,然後一些method呼叫native去達成,程式非常地小巧,目前只是個人嘗試,不算完整發展的專案,如果日後有發展的熱忱在,這東西應該會變成是一個可能在SD卡模組上動態載入程式的方式.
其實在arduino上跑jvm不太有啥好處,真正說來我覺得好處大概只有程式碼在單一大小於一定size前(至少一份要能夠載入運作),可以把程式切割成很多部分,放在SD卡上,隨時可以動態載入程式或是切換,達到某種SWAP的功能,而且變成也不需要燒錄步驟.
目前這樣的做法最大的問題其實是跟native call的對應,目前是依照範例對應寫死
https://123d.circuits.io/circuits/1074042-arduino-jvm
但這native call的index其實都不一定相同,這介面階口在轉換時要想辦法動態轉接一下.
關於這些以後有新的發展後再報告了.....
其實jvm這類stack machine有一個優點應該是說美感是我很欣賞的...那就是核心架構概念非常精簡,靠一個stack和一個array加上少少幾個opcode,就可以變化出許許多多的變化,如果把java 物件導向和比較複雜的部分去除,這stack vm真的相當好實作與移植,java的jvm複雜在物件導向相關功能的記憶體模型概念,但OPCODE的執行確相當簡單扼要....到有一種極簡的美感.
這類虛擬機雖然號稱跨平台,但這有很多前提.....在純運算邏輯處理的部分,到哪裡跑都一樣,但跟OS有關係.跟IO有關係的部分,它的呼叫就一定會用到原生的功能,到哪都可以跑的前提是,至少在原生呼叫的階口都保有相同的特性和完整實作,否則都是會出問題的.
其實在arduino上跑jvm不太有啥好處,真正說來我覺得好處大概只有程式碼在單一大小於一定size前(至少一份要能夠載入運作),可以把程式切割成很多部分,放在SD卡上,隨時可以動態載入程式或是切換,達到某種SWAP的功能,而且變成也不需要燒錄步驟.
目前這樣的做法最大的問題其實是跟native call的對應,目前是依照範例對應寫死
https://123d.circuits.io/circuits/1074042-arduino-jvm
但這native call的index其實都不一定相同,這介面階口在轉換時要想辦法動態轉接一下.
關於這些以後有新的發展後再報告了.....
其實jvm這類stack machine有一個優點應該是說美感是我很欣賞的...那就是核心架構概念非常精簡,靠一個stack和一個array加上少少幾個opcode,就可以變化出許許多多的變化,如果把java 物件導向和比較複雜的部分去除,這stack vm真的相當好實作與移植,java的jvm複雜在物件導向相關功能的記憶體模型概念,但OPCODE的執行確相當簡單扼要....到有一種極簡的美感.
這類虛擬機雖然號稱跨平台,但這有很多前提.....在純運算邏輯處理的部分,到哪裡跑都一樣,但跟OS有關係.跟IO有關係的部分,它的呼叫就一定會用到原生的功能,到哪都可以跑的前提是,至少在原生呼叫的階口都保有相同的特性和完整實作,否則都是會出問題的.
2015年9月27日 星期日
JVM 實作初步心得
前陣子的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更接近於真正硬體上的概念,以後有空再來看看.
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月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範圍,但結果已經不正確,像是正數加正數,變負數,負數加負數變正數的情況).
2015年1月28日 星期三
效率優化的高速處理
一般來說程式通常會被期待有優雅的結構化.物件化,有時候是基於可讀跟維護的需求,有時候是風格問題,但以我所知,一層又一層的結構化.物件化雖然對軟體設計.規劃和維護有幫助,但需要高速與效率處理時,結構化與物件化往往是不利的,雖然現在硬體快速,不同往年,不太需要錙銖計較,但如果真的遇到效能瓶頸,還是需要打破風格與慣例問題,特別是模擬器需要大量的計算,在某些部分的處理會是關鍵,每種語言的最佳化作法,可能跟語言或是編譯器.直譯器有些不同,但很多時候卻也是相通的,底下的一些經驗分享是以C#為主,但別語言或許也可通用(需要測試).
1.迴圈開展 :
這也是破壞結構優化處理速度的一個方式,通常跟畫面的輸出有關係,因為遊戲畫面是一個二微陣列,常常需要處理兩層式迴圈 ( for x 與 for y ) , 如果把一層展開,直接用hard code的方式 copy paste下去,效率提昇會非常非常多,展開兩層的方式如果再一定數量內 (tile 8x8共 64次上算尚可接受),效率會提升更多.
2.method開展 :
method的往返需要處理stack的push pop,以及數值傳遞,這些都需要花上處理的時間,而且所佔是相當高的,如果是存取頻繁的method,並且也只出現在幾個少數地方,而且method內的code並不多,可以考慮把method的內容提出,直接寫,不要再多一層method結構包覆.
3.不要使用語言提供的高階的物件 :
方便歸方便,但絕對是效能殺手,能夠避免用到就避免用到,另外一定要用到像是Bitmap,在set pixel 與 get pixel 也一定要用特殊方法去存取
參考 http://www.vcskicks.com/fast-image-processing.php
其實上面的優化還是不太夠, Color 這物件也要避免使用才對.
總之效能優化這事情,常常會跟優雅風格.結構化.物件化產生衝突,一般來說開發初期還是得注意到結構問題,但開發完成後如遇到瓶頸,就需要特殊手段來處理.
上面1.2.3都用過stopwatch測試過,差異非常大.
http://www.dotnetperls.com/optimization 這篇也是可以參考的一文.
其實模擬器需要處理的狀況,比較相似於編解碼器撰寫,C#的效能以現在的硬體條件來說,絕對可以處理過往比較舊的遊戲主機模擬(以我個人推測包括PS1,GBA本身,和它們之前主機都是OK的),只是在一些部分需要注意一下,過度層層結構化.物件化加上使用一堆高階的語言物件,會掛掉.
PS.VisualStudo編譯時開啟Optimize Code選項是基本常識了,另外在debug模式下執行也會降低效率,實測以非debug模式為主.
這篇只是初略寫,以後有更多心得和整理會繼續更新.
1.迴圈開展 :
這也是破壞結構優化處理速度的一個方式,通常跟畫面的輸出有關係,因為遊戲畫面是一個二微陣列,常常需要處理兩層式迴圈 ( for x 與 for y ) , 如果把一層展開,直接用hard code的方式 copy paste下去,效率提昇會非常非常多,展開兩層的方式如果再一定數量內 (tile 8x8共 64次上算尚可接受),效率會提升更多.
2.method開展 :
method的往返需要處理stack的push pop,以及數值傳遞,這些都需要花上處理的時間,而且所佔是相當高的,如果是存取頻繁的method,並且也只出現在幾個少數地方,而且method內的code並不多,可以考慮把method的內容提出,直接寫,不要再多一層method結構包覆.
3.不要使用語言提供的高階的物件 :
方便歸方便,但絕對是效能殺手,能夠避免用到就避免用到,另外一定要用到像是Bitmap,在set pixel 與 get pixel 也一定要用特殊方法去存取
參考 http://www.vcskicks.com/fast-image-processing.php
其實上面的優化還是不太夠, Color 這物件也要避免使用才對.
總之效能優化這事情,常常會跟優雅風格.結構化.物件化產生衝突,一般來說開發初期還是得注意到結構問題,但開發完成後如遇到瓶頸,就需要特殊手段來處理.
上面1.2.3都用過stopwatch測試過,差異非常大.
http://www.dotnetperls.com/optimization 這篇也是可以參考的一文.
其實模擬器需要處理的狀況,比較相似於編解碼器撰寫,C#的效能以現在的硬體條件來說,絕對可以處理過往比較舊的遊戲主機模擬(以我個人推測包括PS1,GBA本身,和它們之前主機都是OK的),只是在一些部分需要注意一下,過度層層結構化.物件化加上使用一堆高階的語言物件,會掛掉.
PS.VisualStudo編譯時開啟Optimize Code選項是基本常識了,另外在debug模式下執行也會降低效率,實測以非debug模式為主.
這篇只是初略寫,以後有更多心得和整理會繼續更新.
2015年1月26日 星期一
任天堂紅白機模擬器
任天堂紅白機 1983 年日本推出 , GameBoy 1989年推出,照理來說任天堂的硬體技術和複雜度應該會比較低,撰寫模擬器或許會比起寫GameBoy的簡單些,但事實並不是這樣.
也的確,任天堂紅白機除了因為有彩色輸出視訊的能力,因此跟GameBoy相比色彩的部分是進階一點點(也只有一點點,幾乎可以說是大同小異),其他的部分都簡單很多,特殊佔存器的數量少上不少,問題就是因為紅白機的構造簡單,換來是很多複雜的硬體處理規則,我覺得最主要有兩點是在撰寫紅白機模擬器相當棘手的部分(記憶體相關的問題與 ppu timing )
1.任天堂記憶體的部分映射規則很多,處理需要細心和了解夠透徹,另外Mapper種類繁多,如果有心要提高支援度,支援起來不是件小事情,記憶體映射又跟顯示的處理問題綁在一起.
2.任天堂因為CPU跟PPU兩塊是各自獨立的部分,視為兩個處理器,中間CPU透過記憶體佔存器溝通PPU,來讀寫PPU記憶體,這中間有滿複雜的規則.
3.因為ppu 跟 cpu獨自運作, timing處理起來反來比起GB更複雜,特別是FC的PPU運作方式,要把它timing的規則搞懂需要花點苦工和看你的悟性.
綜合以上,相比下撰寫GB模擬器還算是簡單一點的任務.
在 timing 跟 記憶體的問題處理上,最後我還是決定採用部分 poring 人家專案的方式來達成,以我現在的能力沒辦法在短時間內處理得很好和完全正確.
也的確,任天堂紅白機除了因為有彩色輸出視訊的能力,因此跟GameBoy相比色彩的部分是進階一點點(也只有一點點,幾乎可以說是大同小異),其他的部分都簡單很多,特殊佔存器的數量少上不少,問題就是因為紅白機的構造簡單,換來是很多複雜的硬體處理規則,我覺得最主要有兩點是在撰寫紅白機模擬器相當棘手的部分(記憶體相關的問題與 ppu timing )
1.任天堂記憶體的部分映射規則很多,處理需要細心和了解夠透徹,另外Mapper種類繁多,如果有心要提高支援度,支援起來不是件小事情,記憶體映射又跟顯示的處理問題綁在一起.
2.任天堂因為CPU跟PPU兩塊是各自獨立的部分,視為兩個處理器,中間CPU透過記憶體佔存器溝通PPU,來讀寫PPU記憶體,這中間有滿複雜的規則.
3.因為ppu 跟 cpu獨自運作, timing處理起來反來比起GB更複雜,特別是FC的PPU運作方式,要把它timing的規則搞懂需要花點苦工和看你的悟性.
綜合以上,相比下撰寫GB模擬器還算是簡單一點的任務.
在 timing 跟 記憶體的問題處理上,最後我還是決定採用部分 poring 人家專案的方式來達成,以我現在的能力沒辦法在短時間內處理得很好和完全正確.
2015年1月25日 星期日
談 tile 計算效率的優化處理
tile 在遊戲資料中可以視為是一個 8x8 pixels 的單位元素 (當然也可能有更大的組成) , 可以視為是一個組成畫面區塊的最基本要素,在任天堂紅白機或是GameBoy中一個 title 由兩個 16 Byte 的資料組成, 從兩個 16byte 的資料要處理解碼出 title 在遊戲主機中用的是硬體 pipline 設計去處理 , 因此雖然一個 tile 有 64個 pixel ,在硬體處理之下也僅只是一件一個步驟的事情 , 但由軟體模擬去處理可就不是這樣,算是相當耗費計算的工作 ( 64 * n 次動作 ),但通常來說 title 變動的頻率極低 , 多數是在換關卡等等之類的況下, 才會有tile 資料變動 , 因此多數會使用cache的技巧,也就是說 tile table(這些title會存放記錄在一個連續的記憶體區域,稱tile table ,但每台遊戲主機在稱呼上多少有著不同,但觀念是差不多的) 計算過一次 記錄下來結果, 之後除非再異動, 不然不會每次整個table都重算一次,這是一種cach的等級,比較進階的甚至會再細部到只處理table中某個位置tile的變動.
1.每次畫面存取 , 全部 table 裡的全部title重算一次 (loading最重,通常會造成嚴重效率問題)
2.每次畫面存取, 除非 table裡面的某些資料有異動,才會整個將table重算一次
3.每次畫面存取,僅只更新table裡面有異動的 title 部分.
(優化到啥程度,看各家本領,有時候優化過頭沒處理好,還會漏掉....)
通常一個還算能跑的模擬器,最少要達成 第二步驟的優化,除此外像是background title map也會進行cache優化 (簡稱BG MAP,一個二維陣列,每個位置紀錄放置哪個title來呈現出遊戲背景畫面).
如果以上聽模模糊糊,沒關係,再多看一些相關資料,就會通了.
上面是針對 tile cache的優化,但解 title 本身的計算處理優化又是另一個議題.
這邊我先假設讀者已經知道解 title 的方法 (也許以後再另行篇章撰寫),通常最少會有3曾迴圈
第一層迴圈 : 處理每個 tile , 好比說 title 有 256 個 , 迴圈就從 0 ~ 255
第二層迴圈 : tile的每一行 ,共有 8 行
第三層迴圈 : tile 的每一行中的每一個 pixel , 每行共 8個 pixel
我原本有想過說,tile算過後, table更新後,即使是最佳化的cache , 還是得針對有異動過的位置重算,如果算完能夠記錄住,直接搬移過來放置,不是就ok了? (話先說再前頭,這想法失敗)
每個 title 由 32 byte 組,共64bits,如果能建立一個索引關係,豈不是每次table更新,只要更新索引就好?
其實問題點就是這索引機制的設計,32BYTE 共 64bits,如果用 array 資料結構來 index ,這 64bits的資料量非常可怕 , 2^64 ,後來採用 C# 的 dictionary, key 就是由 64bits的 title 資料而來,value則是解出的 title 2維 pixles , 測試起來由於使用到比較進階複雜的資料結構物件,雖然免於重複計算,但光是建立索引的 key 和 從 dictionary 去撈取 value,本身就比解一個title的標準動作費時不少...... orz... 如果不靠 dictionary 物件呢? 自己建立特殊的資料結構 ? 想了又想....最主要的問題還是在於光是要生成這個 key 和建立mapping索引關係,到撈取資料,本身就有不少計算量,並沒有佔到便宜.....
原先的想法更單純,把所有 8x8 的可能性窮舉法算出來, 後來算一算後才知道不實際....
那靠多核心計算來當平行處理呢? 更慘....並不是任何計算處理靠平行和多核就一定能吃香,因為本身會有很多context switch , 這個會占用一定的時間,如果相對於計算任務來說, context switch 本身就超過計算時間,那並不划算,實測結果把 第三層 for 迴圈改成 平行處理的寫法下去,更慢..... orz.....
最後有明顯效果提升的,但也不是新花招的,大概就是迴圈展開這招,速度是提升,當然會多一點code的量,簡單來說就是把第三層的迴圈移除掉,直接把相同的code copy/paste 上 8次,並且將一些可以事先算好的東西先算好,出來的結果速度快了原來非常非常多倍......
這技巧是用空間換時間,並且事先把一些能夠前置處理掉的計算事先算好,少掉那些計算與每次回圈的counet判斷和 jump 的時間,效率就提升很多 , 至於把第二層環圈也移除掉呢 ? 效率會再提升多少,我不清楚,但的確也可以嘗試.... 不過就變成多了最少64倍的程使碼量就是,反正copy paste也不會太久.
結果最後還是繞回一個傳統.常見的老方法才是正解.
ps.如果有更好的技巧或是想法也歡迎分享
1.每次畫面存取 , 全部 table 裡的全部title重算一次 (loading最重,通常會造成嚴重效率問題)
2.每次畫面存取, 除非 table裡面的某些資料有異動,才會整個將table重算一次
3.每次畫面存取,僅只更新table裡面有異動的 title 部分.
(優化到啥程度,看各家本領,有時候優化過頭沒處理好,還會漏掉....)
通常一個還算能跑的模擬器,最少要達成 第二步驟的優化,除此外像是background title map也會進行cache優化 (簡稱BG MAP,一個二維陣列,每個位置紀錄放置哪個title來呈現出遊戲背景畫面).
如果以上聽模模糊糊,沒關係,再多看一些相關資料,就會通了.
上面是針對 tile cache的優化,但解 title 本身的計算處理優化又是另一個議題.
這邊我先假設讀者已經知道解 title 的方法 (也許以後再另行篇章撰寫),通常最少會有3曾迴圈
第一層迴圈 : 處理每個 tile , 好比說 title 有 256 個 , 迴圈就從 0 ~ 255
第二層迴圈 : tile的每一行 ,共有 8 行
第三層迴圈 : tile 的每一行中的每一個 pixel , 每行共 8個 pixel
我原本有想過說,tile算過後, table更新後,即使是最佳化的cache , 還是得針對有異動過的位置重算,如果算完能夠記錄住,直接搬移過來放置,不是就ok了? (話先說再前頭,這想法失敗)
每個 title 由 32 byte 組,共64bits,如果能建立一個索引關係,豈不是每次table更新,只要更新索引就好?
其實問題點就是這索引機制的設計,32BYTE 共 64bits,如果用 array 資料結構來 index ,這 64bits的資料量非常可怕 , 2^64 ,後來採用 C# 的 dictionary, key 就是由 64bits的 title 資料而來,value則是解出的 title 2維 pixles , 測試起來由於使用到比較進階複雜的資料結構物件,雖然免於重複計算,但光是建立索引的 key 和 從 dictionary 去撈取 value,本身就比解一個title的標準動作費時不少...... orz... 如果不靠 dictionary 物件呢? 自己建立特殊的資料結構 ? 想了又想....最主要的問題還是在於光是要生成這個 key 和建立mapping索引關係,到撈取資料,本身就有不少計算量,並沒有佔到便宜.....
原先的想法更單純,把所有 8x8 的可能性窮舉法算出來, 後來算一算後才知道不實際....
那靠多核心計算來當平行處理呢? 更慘....並不是任何計算處理靠平行和多核就一定能吃香,因為本身會有很多context switch , 這個會占用一定的時間,如果相對於計算任務來說, context switch 本身就超過計算時間,那並不划算,實測結果把 第三層 for 迴圈改成 平行處理的寫法下去,更慢..... orz.....
最後有明顯效果提升的,但也不是新花招的,大概就是迴圈展開這招,速度是提升,當然會多一點code的量,簡單來說就是把第三層的迴圈移除掉,直接把相同的code copy/paste 上 8次,並且將一些可以事先算好的東西先算好,出來的結果速度快了原來非常非常多倍......
這技巧是用空間換時間,並且事先把一些能夠前置處理掉的計算事先算好,少掉那些計算與每次回圈的counet判斷和 jump 的時間,效率就提升很多 , 至於把第二層環圈也移除掉呢 ? 效率會再提升多少,我不清楚,但的確也可以嘗試.... 不過就變成多了最少64倍的程使碼量就是,反正copy paste也不會太久.
結果最後還是繞回一個傳統.常見的老方法才是正解.
ps.如果有更好的技巧或是想法也歡迎分享
2015年1月14日 星期三
mirror memory
所謂的 mirror memory 在很多地方都看得到,簡單來說這種memory的特性是映射另一區域的記憶體 ,也就是說不論你是讀或是寫入某個記憶體,如果它是mirrir記憶體,那你同時也會寫入到另一個address的內容,至於為何會設計成這樣,背後應該有滿多設計上的考量因素,但細節我不是很了解,所以就不多揣測.
這邊要談的是 mirror memory 在模擬程式上的處理,看過一些處理方式.
1. 多 copy 一份到別位置 (寫入時候需要多偏移計算.指定和寫入的動作 ).
2. 透過計算,對應同一個address內容 ( read 時候需要多一個計算 ).
3. 事先將對應關係計算出來,寫入到table內 (read的時候和write需要經過各需要一次查詢動作)
哪個好壞? 這邊很難斷定,看用啥角度(追求效能? code的簡短? 結構化? ).看狀況(是寫入多還是讀取多,把cost高的放到比較少的運作去,但這得看實際狀況才知道).
我個人其實是比較喜歡 2 & 3 ,但每個人想法不同,這邊就看每個人自己的想法.
這邊要談的是 mirror memory 在模擬程式上的處理,看過一些處理方式.
1. 多 copy 一份到別位置 (寫入時候需要多偏移計算.指定和寫入的動作 ).
2. 透過計算,對應同一個address內容 ( read 時候需要多一個計算 ).
3. 事先將對應關係計算出來,寫入到table內 (read的時候和write需要經過各需要一次查詢動作)
哪個好壞? 這邊很難斷定,看用啥角度(追求效能? code的簡短? 結構化? ).看狀況(是寫入多還是讀取多,把cost高的放到比較少的運作去,但這得看實際狀況才知道).
我個人其實是比較喜歡 2 & 3 ,但每個人想法不同,這邊就看每個人自己的想法.
2015年1月6日 星期二
所謂的 illegal (unofficial) code
illegal 英文中是非法的.不合規定的意思,在這邊所謂的 illegal code 並沒有嚴重到所謂非法的涵義,而是指這個CPU操作瑪並沒有在官方技術文件上列出(所以也叫unofficial code),通常因為有一些不確定性,不是很建議使用,但可能有某些遊戲就正好使用到,因此illegal code的實作對於相容性有幫助,不過一般來說會用到的是少數,模擬器撰寫初期可以先省略不談.
至於為何會有這種 illegal code ? 有很多可能,以8 bit cpu來說,最少就可以有 256個操作碼(如果使用延伸碼可以更多,像z80中就可以用 0xCB 來當擴展, 其後面可以再加子操作碼), 並不是每一個 可能編碼的數字都有使用到,有些可能是為了編譯器留一手(純屬個人猜測).有些可能是為了未來預留.有些可能有某些不穩定的特性.有些會造成運作crash ,總之諸如此類的因素,沒有被列到官方文件中記載.
附帶一提的是,像是GameBoy用z80並不算是標準的z80,而紅白機用的6502也並不算是標準的6502,但大體上可以說是大同小異,只是在其中要特別注意到某些功能可能已經被移除.某些opcode的功能可能已經有變,這種差異性影響程度會更甚於illegal code有無被完整實作.
6502 opcode官方列出151個,但如果再加上illegal code,則有240多個,少掉的那幾個連illegal code可能也不算,會導致cpu 運作癱瘓(這種我覺得連illegal code都稱不上),這幾個是連實作都沒必要,而這些沒被官方列出來的opcode中很多的功能僅止是占用記憶體.時間與NOP而已.
PS.但因為公開測試ROM中,指令集測試連 illegal code都一起併入,為求測試完整性,因此我在實作中還是將非官方的部分實作進去.
訂閱：
文章 (Atom)
