前回の続きです。今回はコンピュータシステムの理論と実装（以下、nand2tetris本）の12章のオペレーティングシステムを実装してみました。
- 今回のコード
- 概要
- 1. Memory（メモリ操作）
- 2. Array（配列操作）
- 3. Math（基本的な演算）
- 4. String（文字列操作）
- 5. Output（スクリーンへのテキスト出力）
- 6. Screen（スクリーンへのグラフィック出力）
- 7. Keyboard（キーボード入力）
- 8. Sys（プログラム実行関連）
- 9. All（Pongゲームによる総合テスト）
- まとめ
今回のコード
下記、タグv0.0.5になります。
下記で動かせます。
git clone -b v0.0.5 https://github.com/nihemak/nand2tetris.git cd nand2tetris # download nand2tetris environment ./setup.sh # test all ./test.sh
概要
今回はオペレーティングシステムにあたる部分（Jack OS）のJack言語による実装です。書籍に従ってクラスごとに単独で実装・テスト確認していきました。最後に全てのコードを結合して総合テストとしてPongゲームを動作させての確認しました。
使い方はtest12.shを参照。
全体を通してエラーコードは書籍の表9-1に従っています。
1. Memory（メモリ操作）
ソースコードは12/1_Memory/Memory.jackです。
ここでは下記を実装しました。
- function void init()
- function int peek(int address)
- function void poke(int address, int value)
- function int alloc(int size)
- function void deAlloc(Array o)
alloc・deAllocについては実装が楽な first-fit アルゴリズムを採用しました。ちなみに今回はdeAllocした領域を freeList の先頭に戻すようにしているのでallocでの空き領域の探索で早い段階で性能に影響が出るかもしれないです*1。あとフラグメンテーション解消のケアは今回してないです。
2. Array（配列操作）
ソースコードは12/2_Array/Array.jackです。
ここでは下記を実装しました。
- function Array new(int size)
- method void dispose()
Memory.allocとMemory.deAllocのラッパーになってます。
3. Math（基本的な演算）
ここでは下記を実装しました。
- function void init()
- function int multiply(int x, int y)
- function int divide(int x, int y)
- function int sqrt(int x)
- function int max(int a, int b)
- function int min(int a, int b)
- function int abs(int x)
- function boolean bit(int x, int j)
ほぼほぼ書籍のアルゴリズムに従っています。ポイントは乗算の計算コストが高いためできるだけ加算で行う工夫をしているところです。このあたりはだいぶ可読性が犠牲になっています。
4. String（文字列操作）
ソースコードは12/4_String/String.jackです。
ここでは下記を実装しました。
- constructor String new(int maxLength)
- method void dispose()
- method int length()
- method char charAt(int j)
- method void setCharAt(int j, char c)
- method String appendChar(char c)
- method void eraseLastChar()
- method int intValue()
- method void setInt(int val)
- function char newLine()
- function char backSpace()
- function char doubleQuote()
内部実装では文字のArrayを使用しています。数値と文字列を変換するintValue・setIntは歯応えがありました。
5. Output（スクリーンへのテキスト出力）
ソースコードは12/5_Output/Output.jackです。
ここでは下記を実装しました。
- function void init()
- function void initMap()
- function void create(int index, int a, int b, int c, int d, int e, int f, int g, int h, int i, int j, int k)
- function Array getMap(char c)
- function void moveCursor(int i, int j)
- function void printChar(char c)
- function void printString(String s)
- function void printInt(int i)
- function void println()
- function void backSpace()
- function void displayChar(char c)
カーソル操作と文字画像出力で実際の描画はScreenクラスを使いました。スクロールは最低限テストプログラムの出力と一致していればOKとしてほぼ実装せず雑な感じです。
6. Screen（スクリーンへのグラフィック出力）
ソースコードは12/6_Screen/Screen.jackです。
ここでは下記を実装しました。
- function void init()
- function void clearScreen()
- function void setColor(boolean b)
- function void drawPixel(int x, int y)
- function void drawHorizontalLine(int x1, int x4, int y)
- function void drawLine(int x1, int y1, int x2, int y2)
- function void drawRectangle(int x1, int y1, int x2, int y2)
- function void drawCircle(int x, int y, int r)
メモリマップされたScreenの領域を読み書きすることで描画を行いました。
書籍の通り実装したところあまりにも描画が重たかったため最適化としてdrawHorizontalLine（水平線描画）を追加しました。この関数では描画を「x1->x2」「x2->x3」「x3->x4」の３区間に分けて「x2->x3」を1ワード分の16ピクセル単位で描画して描画ループ処理を削減しました*2。そしてclearScreenやdrawRectangleなどの内部で使うようにしました。結果として高速化しましたが、それでも描画はまだまだ重いのでもっと最適化を考えた方が良いと思います。
7. Keyboard（キーボード入力）
ソースコードは12/7_Keyboard/Keyboard.jackです。
ここでは下記を実装しました。
- function void init()
- function char keyPressed()
- function char readChar()
- function String readLine(String message)
- function int readInt(String message)
メモリマップされたKeyboardの領域を読み書きすることでキー取得を行いました。
8. Sys（プログラム実行関連）
ここでは下記を実装しました。
- function void init()
- function void halt()
- function void wait(int duration)
- function void error(int errorCode)
initはプログラム開始時に呼ばれるので他のOKコードのinitとエントリポイントのMain.main呼び出しを行いました。
waitはdurationに応じてループ回数を増やす原始的なものでループ回数は実行するシステム環境依存で調整するみたいです。書籍のリファレンス実装が１durationあたり50回ループになっていたので今回はとりあえず合わせました。
9. All（Pongゲームによる総合テスト）
最後にここまで実装してきたJack OSを全て結合して*311章のPongゲームが動くことを確認しました。
cp -r ./nand2tetris/projects/11/Pong 12/9_All/ && \ cp -r 12/1_Memory/Memory.jack 12/9_All/Pong/ && \ cp -r 12/2_Array/Array.jack 12/9_All/Pong/ && \ cp -r 12/3_Math/Math.jack 12/9_All/Pong/ && \ cp -r 12/4_String/String.jack 12/9_All/Pong/ && \ cp -r 12/5_Output/Output.jack 12/9_All/Pong/ && \ cp -r 12/6_Screen/Screen.jack 12/9_All/Pong/ && \ cp -r 12/7_Keyboard/Keyboard.jack 12/9_All/Pong/ && \ cp -r 12/8_Sys/Sys.jack 12/9_All/Pong/ && \ ./nand2tetris/tools/JackCompiler.sh 12/9_All/Pong # ./nand2tetris/tools/VMEmulator.sh # 12/9_All/Pong/
結果は無事に動きました！（わーい）ただScreenクラスのせいでだいぶスローです。。さらなる最適化が必要そうです。
まとめ
長かったコンピュータシステムの理論と実装の実装も今回でおしまいです*4。せっかくおもちゃでもCPUからコンパイラ、OSまで１通り作ってみるイメージが持てたので次はもう少し本格的なものづくりに挑戦してみたいですね。今時？だとFPGAでRISC-Vとかかな。低レイヤを気ままに楽しもうと思います。
