2017年5月27日 星期六

使用 doxygen 產生程式文件

這應該是個過時的題目,相關的文件已經滿天飛了,不過最近程式寫得肥了,又是和其他人的合作項目,總不能老是這樣打開 Office Word 寫文件(掩面),然後程式跟文件老是不同步,還是把註解改好用 doxygen 產生文件省事些,順帶得就寫個文章記錄一下。
doxygen 是一套文件產生程式,會自動 parse 原始碼、標頭檔等,搭配設定的模版,自動產生不同種類的文件,如 manpage, html , latex…。
要用 doxygen 第一步是先安裝 doxygen,這在 unix 下配上套件管理員應該跟喝水一樣簡單,略過不提。

doxygen -g <config-file>
產生設定檔,預設的名字會是 Doxyfile

下一步要編輯設定檔,我比較過預設設定,大概要改下面這些地方:

  • PROJECT_NAME:當然要改成自己的名字
  • OUTPUT_DIRECTORY:我設定在 doc 資料夾,並且把 doc 資料夾加到 .git 中
  • OUTPUT_LANGUAGE:設定語言
  • EXTRACT_ALL:設成 YES,這樣才會解析所有的檔案,否則必須要用 \file 或 @file 定義過的檔案才會被解析,否則它只會解析 .h 檔
  • INPUT:用空白分隔的輸入檔案或資料夾,我是 src 資料夾
  • FILE_PATTERNS:設定要分析的檔案,這裡我只保留 .c 跟 .h
  • EXCLUDE:把不需要的資料夾剔掉,因為我有一個測試的 test 資料夾,所以把它加上去
  • GENERATE_*:設定要輸出的格式,我只選擇輸出 html ,設定 GENERATE_HTML 是 YES

為了在程式中加上更多資訊,可以在程式碼裡面為函式寫註解,我是使用下列的型式:
/*!
 *
 */
另外搭配以下幾個註解命令:
\brief 可以提供一行描述,簡短敘述這個函式的功能
\see 關鍵字,可以產生連結跳轉去其他的內容
\param 參數描述,有符合原始碼內的參數名稱,在排版上會自動上色並縮排
\return 對回傳值的描述
在 \brief 之後空一行,其它的內容則會歸為長敘述中,如果沒空行的話這些內容都會被濃縮成一行歸在 brief 裡面,所以,一個完整的函式註解如下:
/*!
 *
 * \brief dest = src xor dest
 *
 * do xor on src buffer and dest buffer, store result in dest buffer
 * \param src, dest buffer to xor
 * \param len buffer size both buffer should have enough space for len
 * \return none
 *
 */
int32_t xor2(
  uint8_t *src,
  uint8_t *dest,
  uint32_t len)

接著就可以下
doxygen config_file
產生文件,文件會在 doc/html 中
話說新一代的程式語言好像都自帶文件產生器,如 golang 的 godoc,rust 也有 rustdoc,也許 doxygen 這樣的東西,未來也用不太到了?

Doxygen Manual:
http://www.stack.nl/~dimitri/doxygen/manual/index.html

2017年5月16日 星期二

如何調整 virtualbox 虛擬硬碟檔案的大小

故事是這樣子的,一直以來我都是用 Archlinux 作為我的作業系統,因為在碩士班要跑的模擬用的是 windows 版的ADS,做投影片要用到 M$ Office,於是就裝了一個 Virtualbox ,裡面跑 Win 7。
最近wannacry 勒索軟體肆虐,我才驚覺原來我 virtual box 裡的 win 7 已經超級久沒有更新了,結果是卡到 win 7 的一個 update bug,一更新它就卡在check update 上出不來了,後面搜尋了一段時間,先手動裝了幾個 update 才開始更新,這部分用<windows 7 check update stuck>當關鍵字還不少搜尋結果。
因為累積的一籮筐的更新,要下載的檔案大小超過1 GB,然後…嗯…我的 virtualbox 劃給 windows 的磁碟就滿了(._.),幸好我用的是vdi格式可以動態調整磁碟大小,之前就有調整過一次,這次做個筆記方便下次查找。

https://forums.virtualbox.org/viewtopic.php?f=35&t=50661
開頭就有說了,一定要是 vdi 的虛擬硬碟檔案,首先要先備份一下 vdi 檔,以免調整用量的時候出錯,把整個虛擬磁碟毀了,備份完之後,使用下面的指令,vdi 檔的路徑建議用絕對路徑,size 的單位是 MB,我多劃 5 GB 的空間給它,總共是 40 GB。
vboxmanage modifyhd /media/datadisk/win7.vdi --resize 40960
要注意這個指令似乎只能調大不能調小,所以不要不小心劃太多。

https://www.lifewire.com/how-to-open-disk-management-2626080
vdi 檔案加大之後,只是從 guest 那邊看到的磁碟變大,windows 內還沒有對應的調整,這裡要使用 windows 的 disk management:選控制台->系統及安全性->系統管理工具下有一個建立及格式化硬碟分割,可以把它想成 windows 版的 gparted。
打開之後的畫面大概像這樣,這是已經擴大分割之後的畫面,剛擴大完應該會在 C碟的後面看到另一個未使用的分區。
這時只需要在 C 碟上右鍵,選擇延伸磁碟區,把新加的空間劃給它即可,如此一來就完成了擴大磁碟的工作了。

話說 35 GB 都不夠用,win 7真的肥肥。
更新又這麼久,真的是珍惜生命,遠離 windows。

2017年5月1日 星期一

NAND2Tetris Part2

三月時看到coursera 上,Nand2Teris 第二部分終於開課了,同樣給它選修下去;最近剛把最後的 project 寫完,完成這門課程。
課程網址:
https://www.coursera.org/learn/build-a-computer
另外,這門結束之後,5/8 立刻有開下一個 session,有興趣的大家趕快 Enroll ,一起把電腦給看透透吧。

Nand2Tetris 2 的影片長度明顯比 season 1 長得多,光第一週的影片,要介紹Virtual Machine 概念,又要講解整個 memory layout, pointer access 的概念,第一週影片長達200 分鐘,還不算上 week 0 複習 Nand2Tetris 1 Machine Language 的部分。
另外 part 2 畢竟進到軟體的部分,作業都很吃軟體能力,像是實作 VMTranslator,編譯器,寫高階語言,也不像第一部分,有提供手爆作業給不會寫程式的人,如果沒有基本程式能力選修起來會有些難度。
作業我本來想延續上一個 part 1 都用rust 寫作業,後來…還是偷懶改用Python 寫了(yay,我魯我廢我不會寫 rust QQQQ。

讓我們帶過七週的課程內容:

第一週:

介紹整體 Nand2Tetris stack machine 的架構,整個 Nand2Tetris 都是執行在這種stack machine 上面,之所以用 stack machine 應該是因為相較 register machine,stack machine 還是好做一些,Memory 設定為:
0-4: SP, LCL, ARG, THIS, THAT
5-12: temp
13-15: general register
16-255: static variable
256: stack
2048: heap (以下暫時不用管)
16384: Screen
24576: Keyboard

在 part 1 的最後,我們可以把 assembly 像是 D=A 轉成機械碼 1101...,VM stack machine 程式碼比 assembly 再高階一些,我們可以直接寫stack 操作,例如 push ARG 1,把 Argument 1 推到 stack 的頂端,這樣高階的程式碼讓我們可以更簡單的實作複雜的行為。

作業是VMTranslator,也就是把剛才那些 push ARG 1 轉成一連串的 D=A, D=M 的assembly,寫作業時發現這份文件非常好用:
http://www.dragonwins.com/domains/getteched/csm/CSCI410/references/hack.htm

稍微卡的地方:
pop local 2 這條指令,因為我要先把 local 2 的位址算出來,這樣就需要 D, M, A 三個register (@2, D=A, @LCL, A=M, D=A+D),然後要取SP 的位址也需要三個 register (@SP, A=M, D=M),這樣就沒有地方可以存 pop 出來的東西了
解法是要用到 13-15 的 general purpose register,算出 local 2 位址之後,先塞進 @R13 裡面,取出stack top 放到D 之後就能直接用 @R13, A=M, M=D 將資料塞進 local 2 裡了。

對應課程:我其實不確定,編譯器一般不會是編譯成虛擬機 bytecode ,都是直接變成 bitcode;如果說是stack machine 的觀念的話,那就是虛擬機器了。

第二週:
VM 裡的 branching, function call
branch 很單純,一個影片就講完了;大部分的內容都在講 Function Call,這部分最複雜的也就是 Function call 跟 Return 的calling convention,作業也就實作這兩個功能:
Function Call 大致的內容如下:LCL (local) 對應一般機器上的 base pointer,SP 則是 stack pointer:

呼叫函式的部分:
Push argument
儲存return address, LCL, ARG, THIS, THAT 到 stack 上面
將 ARG 移動到stack 上存參數的位置
將 LCL 到stack 頂端
Jump
寫入Return label

函式本體的部分:
執行Push stack,留給 local 變數空間
函式本體

Return 部分:
將 LCL 儲存到 R13 (general purpose register) 中
將 Return address (LCL - 5) 儲存在 R14 中
複製 stack 頂端的 return value 到 ARG,要注意沒有參數的話,ARG 指向的位置就是 LCL-5 Return address,所以上面要先把 Return address 備份,不然沒有參數的話會被 return value 蓋掉。
將 SP 移到 ARG 的位置 (pop stack)
恢復 LCL, ARG, THIS, THAT
跳到 R14 的 return address

如此就完成了函式的呼叫與返回,有一點要注意的事,講義的部分沒有講很清楚:這週的作業有要寫bootstrap 的部分,他只寫要做到 SP=256; Call Sys.init,其實在Call Sys.init 的部分,也應該要把bootstrap 的 LCL, ARG, THIS, THAT 存到 stack 中,雖然 Sys.init 永遠不會 return,但在實作上還是要求這麼做。
另外我在寫的過程中,如上所述,函式return 時試著去調換 return value 寫入ARG 跟取出return address 的部分,結果就把 return address 蓋掉導致 \explosion/ 了,正好驗證那句:「你以為你會寫程式,假的!叫你用assembly 寫一個Fibonacci 都寫不出來」

對應課程:這周的對應課程我不甚肯定,calling convention 也許是作業系統,也許是編譯器的 code generation 吧,實際可能分散在下面幾堂課裡:
計算機結構、作業系統、計算機組織與組合語言、系統程式。

第三週:
Jack programming language

就是介紹 Jack 的設計,syntax, data struct 之類的怎麼設計的,因為Jack 比起什麼C++/Java 簡單非常非常多,說真的只要學過任何一種 programming language 的,這周應該都可以跳過去不用看。
對應課程:計算機程式。


第四週:

Jack language 的 parser,內容介紹 tokenizer 還有 parse 的基本原理,作業是實做 tokenizer 跟 parser,把 jack program parse 成一堆 token 然後寫到 xml 檔中,要產生 token 的xml ,還有parser 處理過,加上結構節點像是 WhileExpression 的 xml。
tokenizer 我一樣用 python 實作,regular expression 文件裡面有一節就是如何用 re 的 scanner 來寫一個 tokenizer,整個 jack language 的規則大概就是這樣,寫起來輕鬆寫意:
https://docs.python.org/3.2/library/re.html#writing-a-tokenizer
jackkeyword = ['class', 'constructor', 'method', 'function', 'int',
  'boolean', 'char', 'void', 'var', 'static', 'field', 'let', 'do',
  'if', 'else', 'while', 'return', 'true', 'false', 'null', 'this']
tokenSpec = [
  ('comment', r'//[^\n]*|/\*(\*(?!\/)|[^*])*\*/'),
  ('integerConstant', r'\d+'),
  ('symbol', r'[+\-*\/\&\|\<\>\=\~\(\)\{\}\[\]\.\,\;]'),
  ('identifier',  r'[A-Za-z_][A-Za-z_0-9]*'),
  ('stringConstant', r'\"([^"]*)\"'),
  ('newline', r'\n'),
  ('space', r'[ \t]+'),
]

parser 部分我寫了個class ,對各種狀況寫函式來處理,寫得超級醜,文法檢查和輸出的部分都混在一起了,整個 parser 都是用土砲打造而成,正符合下面這句話:
「我一直以為我會寫程式…假的!連個 jack compiler 都寫不出來。」
那個 code 實在是太醜了,決定還是不要公開…,但相較在網路上找到一些人的實作,連文法檢查都沒有,我是覺得我寫得還是很有誠意啦XD
https://github.com/kmanzana/nand2tetris/tree/master/projects/10

對應課程:無疑問的就是編譯器的上半學期


第五週:
Code Generation

上週實作的編譯器只能輸出 xml ,這周要直接把 jack 轉成 VM code,影片就是一步步教你,當遇到運算符號要怎麼處理,呼叫函式要怎麼處理。它的class 沒有 inheritance 所以…嗯,也不用處理 virtual table 的問題,其實滿簡單的。
我覺得收獲最大的,是學到怎麼處理物件 method 的call,其實也就是把指向物件的記憶體位址塞進函式的第一個參數,然後在進到 method 的時候先把這個參數塞進 THIS,這樣就能用 THIS[n] 來取用物件的 data member 了。
這裡也會知道,上面實作時遇到的 THIS, THAT,其實分別對應物件跟陣列,要用物件的 data member 就用 THIS[n] 去取,陣列的內容則用 THAT[n],這樣只需要把記憶體位址存到 THIS, THAT 裡面,就能取用物件和陣列了。

下面是一些實作的筆記:
Jack language 裡面沒有 header/linker 的概念,編譯的時候是以一個 class 為單位在編譯,所以如果裡面出現呼叫其他class 的函式,例如 do obj.foo(),我們只能把它們當成「合法」的程式來產生 code,就算沒有這個 class 或是函式還是可以編譯
但沒有最後一步將所有 vm file link成一個檔案,而是模擬器個別 load 所有的 vm 檔,自然不會像 C/C++ 的 linker ,在最後階段回報 undefined reference to class name/function name 的錯誤。

因為parser 已經把整個程式碼變成 AST了,code generate的部分,只需要把對應的函式寫好,大抵就會動了;沒實作的地方,我發現與其寫 pass 不如直接 raise NotImplementedError,這樣一編譯遇到沒實作的地方,程式就直接 crash 並指出是哪個地方沒有實作;而無論是 parser 還是 code generation, expr->term->factor 這部分的變化是最多元的,這部分處理完,各個 statement 的部分都可以輕鬆對付。

然後…它的模擬程式其實有點兩光,如果選用 program flow 模擬的話會非常慢,依它的建議要把它選成 No Animation,可是這個模式無法編輯記憶體的內容;正確步驟是:load 程式,編譯記憶體,選成 No Animation 執行。
另外,No animation 下,所有對記憶體的操作,都要按下停止模擬才會反映出來,不知道這點的我一直以為我 code generate 哪裡寫錯了lol。

這次作業會需要 call 到一些 library 提供的函式,請參考官方的文件:
http://www.nand2tetris.org/projects/09/Jack%20OS%20API.pdf
例如,要產生字串的話,要用 String.new, String.appendChar 兩個方法,大致如下:
push constant num_of_character
call String.new 1 // 1 argument
for char in string:
  push constant ord(char)
  call String.appendChar 2 //first is string, second is character
最後的 compiler 總共 1000 行左右…覺得實作超糟,都用了python 怎麼還會寫得這麼肥?

對應課程:編譯器的下半學期


第六週:

作業系統,或者稱 Library 或是 runtime 應該比較恰當,總之就是 jack 中,會用到一些 Keyboard, Screen, Math 之類的函式,在之前都是用預先編譯好的模組來執行,現在則要自己用 jack 實作這些功能。這次的影片也高達 230 分,到最後一個 module 連教授都忍不住大叫:Yeah, the last module~~

理論上是用 jack 這樣的高階語言來寫,以為有高階語言就沒事了嗎,錯!
jack 他X 的有夠難寫,少了一個 do, return 什麼的程式就炸給你看(沒有return 它的函式就會一路執行到下一個函式 lol),因為它沒有 operator precedance 所以該加括號的地方也要加,宣告也無法和賦值寫在一起,我大概照他設計的內容,寫完Math 跟 Memory 之後才比較抓到該怎麼寫。
作業寫起來都滿有挑戰性的,像是 Memory.jack 就要用 linked-list 來實作的記憶體管理(用這破破的語言XD)。

作業不止是在考驗寫 jack ,同時也在驗證上一次寫的 compiler ,測試過程中我找到好幾個 compiler 相關的錯誤,像是函式的參數沒處理好,不該傳入 this 的時候傳入 this,讓我在Output 文字的地方 de 了很久的 bug。
這種錯真的超級麻煩,你不一定知道是高階語言寫錯還是compiler 錯…,有時要追著模擬器一步步執行,才能知道是哪裡錯了。這次真的是體會到:好的編譯器帶你上天堂,壞的編譯器帶你住套房。

對應課程:作業系統、系統程式
有一些些的演算法概念(例如乘法要怎麼實作才會快),但份量極少所以不列上好了。

第七週:
這週只是提點一些 Nand2Tetris 可以加強的部分,像是:
在硬體中實作乘法除法來加速,這樣就不需要 library 的函式支援。
在硬體中實作位元運算(左移右移)
如何自己實作模擬器的 built-in chip

另外也公佈可能會有的 Nand2Tetris part 3,如何真的在 FPGA 上實作這台電腦

--

末語:
大推這門課,課程中 Shimon 講課的速度都滿慢的(我都開 1.3-1.4 倍速在聽課),不會太難聽懂。
第二部分相較之下實在太難,覺得還是稍微有碰過程式再來學會比較好,第一部分就沒這問題(也許可以說:電機系的不用修第一部分,資工系的不用修第二部分XDD)修完整部 Nand2Tetris ,對數位電路到組成電腦都有一些概念,第二部分更是讓你看透程式到底怎麼編譯、執行,這點可能即使是資工本科生都不一定全盤了解。
同時,修這門課對我來說也有一點點復健的作用,從簡單的東西入手給自己一點信心:原來,我也是會寫程式,寫得出一些些可以用的東西呢。

僅引用課程講義最後一節的文字:
In CS, God gave us Nand, everything else was done by humans.
神給了我們反及閘,於是我們打造一台電腦。
另外還有影片中教授引用的這段:
We shall not cease from exploration, and the end of all our exploring will be to arrive where we started and know the place for the first time." - T. S. Eliot
作為這門課的總結。