PUSH and POP【Turing Complete編】
目次
はじめに
いつもブログをご覧いただきありがとうございます。
コーストFIRE中のIPUSIRONです😀
PUSH and POPステージ
PUSH and POPステージのゴールは、LEGアーキテクチャーの回路にスタック回路を組み込み、以下の動作をするプログラムを作ることです。
・入力が0なら、スタックからPOPする。
・入力が0でないなら、そのデータをスタックにPUSHする。
PUSH and POPステージを解く
次の2つに分けて作業を進めましょう。
・スタック回路を組み込む
・スタック操作のプログラムを作る
テストがうまくいかない場合は、ハードウェアとソフトウェアのどちらに問題があるかを絞り込む必要があります。
スタック回路を使えるようにする
The Stackステージをクリアしているので、CUSTOMからSTACKコンポーネントを使えます。
しかし、"Pins overlap"というメッセージが出ています。グレーアウトされて、コンポーネントを使えない状態になっています。
※使える状態になっていたら、次のステップに進んでください。
いったんComponent Factoryステージに移動して、STACKコンポーネントを調べてみます。
Level mapからアクセスしてもよいですが、左上のアイコン群にある「Component Factory」アイコン（スパナアイコン）を押せば一発で移動できます。
Component Factoryステージに移動したら、「Switch schematic」アイコンから"STACK"を選びます。STACKコンポーネントの内部回路が表示されます。回路自体はThe Stackステージで作成したものです。
“2 input/output components are in the same square. The custom component will be unusable since 2 pins can’t overlap."という警告文が出て、コンポーネントとして使用不可の状態になっています。
下にある"Component preveiw"の位置に、コンポーネントのイラストが表示されます。回路にあるすべての入出力端子が、Component preveiwに反映されている必要があるのです。
回路にはPOP端子、PUSH端子、VALUE端子、OUTPUT端子があります。これらの端子を選択すると、ラベル名とラベルの方向を変更できます。Component previewの表示が変わるので好みで調整してください。例えば、Component previewでは出力ピンのラベルがOUTPUTなので、それに合わせておきましょう。
問題は、POP端子とPUSH端子が接近しすぎて、あるいは回路を表す矩形に重なっていて、Component previewにすべてのピンが表示されていないことです。POP端子をちょっとずらすと、警告文が消えました。それと同時にComponent previewに両方のピンが表示されます。
※隣接しなければよいだけなので、ずらすというより離すといったほうが正しいでしょう。
これですべての入出力端子がコンポーネントのピンとして出てきたわけです。全体的にラベルを見やすいように、次のように向きを調整しました。
※PUSHピンとPOPピンを上にしましたが、左にしたければ調整してください。
| 入出力端子 | ラベルの方向（Label direction） | ラベル名（Label text） |
|---|---|---|
| PUSH端子 | 上（Up） | PUSH |
| POP端子 | 上（Up） | POP |
| VALUE端子 | 下（Down） | VALUE |
| OUTPUT端子 | 右（Right） | OUTPUT |
PUSH and POPステージの戻って、CUSTOMからSTACKコンポーネントが使えるようになっていることを確認します。問題なければ、次に進みましょう。
PUSH操作とPOP操作のオペコードを定義する
既存のオペコード一覧
PUSH操作とPOP操作のオペコードを新たに定義することになりますが、既存のオペコードと重複してはいけません。改めて既存のオペコードの一覧をここで示します。
| 1バイト目 | オペコード | 処理内容 |
|---|---|---|
| xy00 0000b | ADD | 引数1と引数2を加算した結果を転送先にセットする。 |
| xy00 0001b | SUB | 引数1から引数2を減算した結果を転送先にセットする。 |
| xy00 0010b | AND | 引数1と引数2をAND演算した結果を転送先にセットする。 |
| xy00 0011b | OR | 引数1と引数2をOR演算した結果を転送先にセットする。 |
| xy00 0100b | NOT | 引数1をビット反転した結果を転送先にセットする。 |
| xy00 0101b | XOR | 引数1と引数2をXOR演算した結果を転送先にセットする。 |
| 0001 0000b（＝16d） | LOAD_RAM | REG 5内のデータを指定アドレスとして、RAMにロードする（読み込む）。 |
| 0001 0001b（=17d） | SAVE_RAM | REG 5内のデータを指定アドレスとして、RAMにセーブ（保存）する。 |
| 0010 0000b（=32d） | IF_EQUAL | 引数1と引数2が一致したら、指定のアドレスにジャンプする。 |
| 0010 0001b（＝33d） | IF_NOT_EUQAL | 引数1と引数2が不一致なら、指定のアドレスにジャンプする。 |
| 0010 0010b（＝34d） | IF_LESS | 引数1が引数2より小さいなら、指定のアドレスにジャンプする。 |
| 0010 0011b（＝35d） | IF_LESS_OR_EQUAL | 引数1が引数2以下なら、指定のアドレスにジャンプする。 |
| 0010 0100b（＝36d） | IF_GREATER | 引数1が引数2より大きいなら、指定のアドレスにジャンプする。 |
| 0010 0101b（＝37d） | IF_GREATER_OR_EQUAL | 引数1が引数2以上なら、指定のアドレスにジャンプする。 |
| 指定の際に使う値 | 取り出す場所 or 格納する場所 |
|---|---|
| 0 | REG 0 |
| 1 | REG 1 |
| 2 | REG 2 |
| 3 | REG 3 |
| 4 | REG 4 |
| 5 | REG 5 |
| 6 | カウンター |
| 7 | 転送元の場合は入力端子 転送先の場合は出力端子 |
追加するオペコード一覧
上から3ビット目の桁が空いていますが、「スタックはRAMを代用すること」「RAM系オペコードが2つしかなく余裕があること」から、今回は4ビット目が1のビット列として定義します。
| 1バイト目 | オペコード | 処理内容 |
|---|---|---|
| 0001 0010b（＝18d） | PUSH | スタックにPUSHする。 |
| 0001 0011b（＝19d） | POP | スタックからPOPする。 |
1命令は4バイトで構成されていました。
今回追加するPUSHとPOPのフォーマットは、それぞれLOAD_RAM、SAVE_RAMと同様とします。
スタックを使う場合、メモリーのアドレスをユーザー（プログラム開発者）側は指定しません。スタックポインターにすべて任されます。
スタック回路を組み込む
1：STACKコンポーネントを配置する
STACKコンポーネントをキャンバスに配置します。RAMコンポーネント周辺の空き領域に配置すればよいでしょう。
※STACKコンポーネントはスタック専用のRAMを内蔵しており、LEGアーキテクチャーの回路にあるRAMを使うわけではありません。
2：STACKコンポーネントをワイヤリングする
RAM周辺の回路はすでにできあがっているので、ワイヤリングするだけです。
RAMコンポーネントの左側の3 Bit decoderの3番ピンと4番ピンを用います。PUSHのときに3番ピンがON、POPのときに4番ピンがONになります。
残りは、VALUEピンとOUTPUTピンだけになります。SAVE_RAMの場合は、RAMコンポーネントにアドレスと書き込むためのバイトデータを渡します。対して、スタックの場合は内部にスタックポインター（アドレス用のレジスター）とRAMがあります。つまり、PUSHの際に、外部から渡すのは書き込むためのバイトデータだけです。
PUSHで使うバイトデータの転送元は、SAVE_RAMとまったく同じ指定でした。つまり、RAMコンポーネントのSave valueピンにつながっているワイヤーに直結すればよいのです。
後は、メモリーからデータを取り出す操作が残っています。LOAD_RAMではRAMからバイトデータが読み込まれて、指定の転送先に届きます。対して、POPの場合もまったく同じ指定で転送先に届いて欲しいので、RAMコンポーネントのOutput 1ピンにつながっているワイヤーに直結させます。
完成した回路が次になります。
スタック用のプログラムを作る
1：プログラムを設計する
これから作るプログラムは、次の機能を持つ必要があります。
・入力が0なら、スタックからPOPする。
・入力が0でないなら、そのデータをスタックにPUSHする。
それではプログラムを設計してみましょう。ポイントは次の3つだけです。
・比較に使う定数0をレジストリーに用意する。
・入力端子からくるバイトデータをレジストリーに保存してから、0と一致するか否かを判定する。
・POPで得たバイトデータは出力端子から送出する。
以上を踏まえてプログラムを組みます。
| No. | アドレス | 1バイト目 | 2バイト目 | 3バイト目 | 4バイト目 | 処理内容 |
|---|---|---|---|---|---|---|
| 1 | 00h | 0000 0101b（=5d） ※XOR | 0000 0011b（＝3d） ※REG 3 | 0000 0011b（＝3d） ※REG 3 | 0000 0011b（＝3d） ※REG 3 | 比較用の定数0をREG 3に用意する。 ※Conditionモードの命令は即値が使えないので、定数をレジスターに保存しておく必要がある。 |
| 2 | 04h | 0100 0000b（=64d） ※ADDかつImmediateモード | 0000 0111b（＝7d） ※入力端子 | 0000 0000b（＝0d） ※即値 | 0000 0001b（＝1d） ※REG 1 | 入力端子からくるバイトデータをREG 1に保存する。 ※ADD命令で代用している。 |
| 3 | 08h | 0010 0000b（=32d） ※IF_EQUAL | 0000 0001b（＝1d） ※REG 1 | 0000 0011b（＝3d） ※REG 3 | 0001 0100b（＝20d） ※アドレス14h | REG 1とREG 3（0固定）を比較して、一致したら指定アドレスにジャンプする。 |
| 4 | 0Ch | 0001 0010b（＝18d） ※PUSH | 0000 0001b（＝1d） ※REG 1 | 1111 1111b（＝255d） ※未使用 | 1111 1111b（＝255d） ※未使用 | REG 1をスタックにPUSHする。 |
| 5 | 10h | 0010 0000b（=32d） ※IF_EQUAL | 0000 0011b（＝3d） ※REG 3 | 0000 0011b（＝3d） ※REG 3 | 0000 0100b（＝4d） ※アドレス04h | 指定アドレスに無条件ジャンプ。 ※IF_EQUALで代用している。 |
| 6 | 14h | 0001 0011b（＝19d） ※POP | 1111 1111b（＝255d） ※未使用 | 1111 1111b（＝255d） ※未使用 | 0000 0111b（＝7d） ※出力端子 | スタックからPOPして、出力端子に送る。 |
| 7 | 18h | 0010 0000b（=32d） ※IF_EQUAL | 0000 0011b（＝3d） ※REG 3 | 0000 0011b（＝3d） ※REG 3 | 0000 0100b（＝4d） ※アドレス04h | 指定アドレスに無条件ジャンプ。 |
2：プログラムを実装する
1つの4バイト命令をハンドアセンブルすると4つの10進数値が得られます。アセンブリーエディターにそれらを羅列していき、プログラムを完成させます。
# 命令1
5
3
3
3
# 命令2
64
7
0
1
# 命令3
32
1
3
20
# 命令4
18
1
255
255
# 命令5
32
3
3
4
# 命令6
19
255
255
7
# 命令7
32
3
3
4
3：テストする
テストにパスすると、ステージクリアになります。
※テストパターンは4つあります。
1行に4バイト分を記述して見やすくする【別解】
今までプログラムを記述する際、1バイトごとに改行していました。
実のところ、スペース区切りで書いたり、途中で改行を入れても問題ありません。
4バイト命令という都合上、1行に4バイト分、そして1バイトごとに空白で区切ることで、より見やすくなります。また、設計時に作った表とも見比べやすくなります。
5 3 3 3
64 7 0 1
32 1 3 20
18 1 255 255
32 3 3 4
19 255 255 7
32 3 3 4
プログラムの右側にあるグレーの数字に注目してください。1行で4ずつ増えています。つまり、行番号ではなく、行頭のアドレス値の10進数であることがわかります。