当サイトの一部ページには、アフィリエイト・アドセンス・アソシエイト・プロモーション広告を掲載しています。

Amazonのアソシエイトとして、Security Akademeiaは適格販売により収入を得ています。

広告配信等の詳細については、プライバシーポリシーページに掲載しています。

消費者庁が、2023年10月1日から施行する景品表示法の規制対象(通称:ステマ規制)にならないよう、配慮して記事を作成しています。もし問題の表現がありましたら、問い合わせページよりご連絡ください。

参考:令和5年10月1日からステルスマーケティングは景品表示法違反となります。 | 消費者庁

RAM【Turing Complete編】

はじめに

いつもブログをご覧いただきありがとうございます。

コーストFIRE中のIPUSIRONです😀

IPUSIRONのプロフィールを見る

RAMステージ

RAMステージのゴールは、我々のコンピューターにRAMを組み込むことです。

RAMコンポーネント

RAMはコンポーネントとして用意されています。「IO」>「RAM」からRAMコンポーネントを選択できます。

RAMコンポーネントの入出力は次の通りです。

RAMのSettingsと入出力

左のSettingsでRAMのサイズとデータ幅を設定できます。デフォルトでは256バイト、データ幅は8ビットになっています。本ステージはこのままで問題ありません。

入力・Loadピン
・Saveピン
・Addressピン
・Save valueピン・・・4本用意されている。
出力・Output 1ピン
・Output 2ピン
・Output 3ピン
・Output 4ピン

RAMは256バイトのメモリーであり、どのバイトデータを扱うかアドレス指定します。RAMにロードあるいはセーブする場合は、RAMアドレスをレジスターにコピーします。

本ステージのテスト

[Next]ボタンや[Run]ボタンを押してみてください。Programコンポーネントから4バイトごと出力されていきます。

Programコンポーネントにはゼロ初期化されており、すべてが00hで埋まっています。つまり、毎回00 00 00 00hが処理されます。

・1バイト目が00h⇒オペコードはADD

・2バイト目が00h⇒計算対象(転送元)がREG 0の内容

・3バイト目が00h⇒計算対象(転送元)がREG 0の内容

・4バイト目が00h⇒計算結果(転送先)がREG 0

つまり、「REG 0←REG 0+REG 0」を実行しています。REG 0には最初0しか入っていないので、このADD演算を繰り返しても、結局0のままです。

ずっと変化しない処理を繰り返して、処理が終わりません。[Reset]ボタンを押して、テストを手動で停止させてください。

テストパターン

本ステージのテストでは、32回バイトデータが入力されるので、それを同じ順序で出力することがゴールとなります。

RAMに入力データを順番に記憶しておき、それを順番に出力するような回路とプログラムを作ることになります。

ただし、すべての入力を読み取る前に出力すると、テストは失敗するので注意してください。

RAMステージを解く

1:ナンバーフォーマットを符号なしに切り替える

流れているデータを見やすいように「Toggle number format」のアイコンを押して、ナンバーフォーマットを切り替えます。「+255」になると0~255で表現されます。

2:メモリーへのロード・セーブのオペコードを決める

メモリーへのロード・セーブのオペコードを自作することになります。

既存のオペコードについて復習しておきます。$x, y \in \{0,1\}$であり、1だと即値になります。

1バイト目オペコード処理内容
xy00 0000bADD引数1と引数2を加算した結果を転送先にセットする。
xy00 0001bSUB引数1から引数2を減算した結果を転送先にセットする。
xy00 0010bAND引数1と引数2をAND演算した結果を転送先にセットする。
xy00 0011bOR引数1と引数2をOR演算した結果を転送先にセットする。
xy00 0100bNOT引数1をビット反転した結果を転送先にセットする。
xy00 0101bXOR引数1と引数2をXOR演算した結果を転送先にセットする。
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 格納する場所
0REG 0
1REG 1
2REG 2
3REG 3
4REG 4
5REG 5
6カウンター
7転送元の場合は入力端子
転送先の場合は出力端子
演算系オペコードにおける計算データの取り出し・格納場所

モードでいうと、Calulationモード、Conditionモード、Immediateモードは実装済みです。残っているのは、Copyモードになります。Copyモードがあれば、入力端子から与えられたバイトデータをレジスターに直接記憶させられます。しかし、「CalulationモードのADD」と「即値の00h」を組み合わせれば、実質的に同様のことを実現できてしまいます。

例えば、入力端子からくるバイトデータをREG 5に保存したければ、次の命令をProgramコンポーネントに書き込めばよいのです。

1バイト目2バイト目3バイト目4バイト目
ADD入力端子0(即値)REG 5
0100 0000b0000 0111b(=7d)0000 0000b0000 0101b(=5d)
入力端子⇒REG 5

同様にして、出力端子から送出することもできます。

1バイト目2バイト目3バイト目4バイト目
ADDREG50(即値)出力端子
0100 0000b0000 0101b(=5d)0000 0000b0000 0111b(=7d)
REG 5⇒出力端子

本ステージは、Programコンポーネントの「Edit memory」ボタンを押すと、アセンブリーエディターが立ち上がります。左の"Assembly codes"の下の[Add]ボタンを押すと、命令を定義できます。

本ステージのテストをパスするためには、入力端子から来たバイトデータをレジスターにいったん記憶して、それをメモリーにセーブすることになります。すべてのデータを読み込んだら、順番通りにロードして、出力端子から送出します。

「入力をレジスターに保存する処理」「レジスターから出力する処理」については既存のオペコードで実現できることは説明しました。

残されているのは、「レジスターのバイトデータをRAMにセーブする」「RAMのバイトデータをレジスターにロードする」という2つの処理になります。

ここではRAMにセーブ・ロードするためのレジスターは、REG 5固定とします。

※固定にすることで、プログラムの柔軟性は失われますが、回路が簡単になります。

既存のオペコードと被らないここと、回路を設計しやすくすることを考慮して、次の2つのオペコードを追加します。

1バイト目オペコード処理内容
0001 0000b(=16d)LOAD_RAMREG 5内のデータを指定アドレスとして、RAMにロードする(読み込む)。
0001 0001b(=17d)SAVE_RAMREG 5内のデータを指定アドレスとして、RAMにセーブ(保存)する。
追加する2つのオペコード

メモリーのアドレスを指定する必要があります。

1バイト目2バイト目3バイト目4バイト目
オペコード
LOAD_RAM
なしなし転送先(0~7)
0001 0000b(=16d)1111 1111b(未割り当て用)1111 1111b(未割り当て用)【例】出力端子
0000 0111b
ロード命令のフォーマット
1バイト目2バイト目3バイト目4バイト目
オペコード
SAVE_RAM
転送元(0~7)なしなし
0001 0001b(=17d)【例】入力端子
0000 0111b
1111 1111b(未割り当て用)1111 1111b(未割り当て用)
※例えば、0000 0000bを指定すると、REG 0に書き込み処理が走ってしまうので、もしこうした入力を想定するなら防止回路が必要です。
セーブ命令のフォーマット

本ステージの一番のテーマであるRAM用のセーブ命令とロード命令については以上になります。

3:RAMを組み込む

RAMコンポーネント周辺を実装します。その結果が次の通りです。

RAMコンポーネントのLoadピンとSaveピンは3 Bit decoderの出力ピンから取ります。3 Bit decoderの出力ピンはどれか1つだけONになります。つまり、RAMコンポーネントにLaodピンとSaveピンの両方がONになることはありません(両方がOFFになることはある)。

RAMコンポーネントのAddressピンは、REG 5のOutputピンと直結します。途中にスイッチは不要です。

RAMコンポーネントのSave valueピンは4つありますが、今回は1バイトずつ扱うので、1つのピンしか使いません。命令語の2バイト目に対応するワイヤーとつながります。その際、8 Bit Muxコンポーネントの後で接続しました。

RAMコンポーネントのOutputピンは4つありますが、これについても1つのピンしか使いません。レジスターの入力側のワイヤーに接続します。ただし、直結してしまうとショートするので、途中にスイッチを入れます。LoadピンがONのときだけスイッチをONにするわけです。

4:バグを修正する

Conditionモードのとき、ジャンプ先アドレスとして7d以下が指定される可能性があります。Conditionモードではカウンターから入力してアドレスを上書きすべき状況であり、レジスターの内容は変わる必要はありません。

次に示す回路が完成版になります。「Conditionモードでない」かつ「4バイト目に7d以下」の場合に、レジスターのSaveが動作するようにしています。

※本当はこのステージではなく、Conditionalsステージで気づくべきでしたが、テストにパスしてしまいました。

5:RAMをリンクする【省略可】

Programコンポーネントの「Link components」アイコンを押して、8番にRAMをリンクします。

アセンブリーエディターのLinked componentsのところに、「8 RAM」が追加されました。

RAMがアクセスしているデータを確認できればよいのですが、残念ながらそうはなりませんでした。

6:プログラムを実装する

回路はできあがったので、RAMに連続でセーブしてから、連続でロードするプログラムを実装します。

No.アドレス1バイト目2バイト目3バイト目4バイト目処理内容
100h1100 0000b(=192d)
※ADDかつImmediateモード
0000 0000b0010 0000b
(=32d)
0000 0100b
※REG 4
※読み込み回数(定数)をREG 4に保持しておく。Conditionモードでは即値を使えないため。
※32回入力されることは問題文として与えられている。
204h0001 0001b(=17d)
※SAVE_RAM
0000 0111b
※入力端子
1111 1111b(=255d)1111 1111b(=255d)入力端子⇒RAM
※この時点でREG 5は00hなので00h番地にセーブ。
308h0100 0000b(=64d)
※ADDかつImmediateモード
0000 0101b
※REG 5
0000 0001b
※即値
0000 0101b
※REG 5
REG 5のデータをインクリメントする。
※REG 5はアドレス用のカウンター。
40Ch0010 0010b(=34d)
※IF_LESS(Conditionモード)
0000 0101b
※REG 5
0000 0100b
※REG 4
0000 0100b
※ジャンプ先のアドレス
32未満なら指定アドレス04hにジャンプ。
※レジスタ群の番号とぶつかる可能性を考慮すること!
510h0000 0101b(=5d)
※XOR
0000 0101b
※REG 5
0000 0101b
※REG 5
0000 0101b
※REG 5
REG 5をゼロクリアする。
614h0001 0001b(=16d)
※LOAD_RAM
1111 1111b(=255d)1111 1111b(=255d)0000 0111b
※出力端子
RAM⇒出力端子
718h0100 0000b(=64d)
※ADDかつImmediateモード
0000 0101b
※REG 5
0000 0001b
※即値
0000 0101b
※REG 5
REG 5のデータをインクリメントする。
81Ch0010 0010b(=34d)
※IF_LESS(Conditionモード)
0000 0101b
※REG 5
0000 0100b
※REG 4
0001 0100b(=20d)
※ジャンプ先のアドレス
32未満なら指定アドレス14hにジャンプ。
作成したプログラム

5:プログラムを入力する

作ったプログラムをアセンブリーエディターで入力します。2進数で入力するので少々手間がかかりますが、逆にこれが自作CPUの醍醐味でもあるので楽しんでください。

1行に1バイトごと10進数を入力しておきます。

# 命令1
192
0
32
4

# 命令2
17
7
255
255

# 命令3
64
5
1
5

# 命令4
34
5
4
4

# 命令5
5
5
5
5

# 命令6
16
255
255
7

# 命令7
64
5
1
5

# 命令8
34
5
4
20

6:テストする

アセンブリーエディター上で[Next]ボタンを使って、ステップ実行してください。特にループ処理がうまくいっているかが肝となります。

右下のLinked componentsには、接続したレジスターやカウンターが保持する現在の値が表示されます。ステップ実行するたびに値が変わっていく様子がわかります。期待通りに動作しないときは、デバッグすることになりますが、その際に活躍します。

テストにパスすると、ステージクリアになります。

“Byte 0 is 251, not 1″(「0番目のバイトは241であり、1ではない」)というエラーメッセージが出たときは、241を想定しているのに、1になっていてエラーということです。配線ミスでなければ、スイッチが怪しいです。8 Bit Switchコンポーネントを使うべきところに、Switchコンポーネント(1ビット用)を使ってしまったときにこのエラーを見ました。
見た目が似ており、デバッグで流れているデータを調べて、このミスにようやく気づきました。