The Art of Computer Programming を読む(3)

1.3.1の演習問題の続きから。

18.

与えられた下記プログラムを実行すると、コンピュータの内部状態(レジスタ・トグル・メモリ)がどうなるか、という問題。

 STZ 1
ENNX 1
 STX 1(0:1)
SLAX 1
ENNA 1
INCX 1
ENT1 1
 SRC 1
 ADD 1
DEC1 -1
 STZ 1
CMPA 1
MOVE -1,1(1)
 HLT 1

ちゃんと命令を追っていけば難しい問題ではないのだが、Knuth先生の解説はあまり親切とは言えず、私のように命令を追い間違えた時にどこに原因があるのか分からない。ひとつひとつ追ってみる。

STZ 1 : メモリの0001番地にゼロをストアする。

+----+-+--+--+--+--+--+
|0001|+| 0| 0| 0| 0| 0|
+----+-+--+--+--+--+--+

ENNX 1 : rXに1を符号反転エントリーする。

+----+-+--+--+--+--+--+
| rX |-| 0| 0| 0| 0| 1|
+----+-+--+--+--+--+--+
|0001|+| 0| 0| 0| 0| 0|
+----+-+--+--+--+--+--+

STX 1(0:1) : rXをメモリの0001番地の符号・1バイト目にストアする。ここで、私がストア命令を勘違いしていたのだが、ストア命令はフィールドで指定された数のバイトがレジスタの右側の部分から取り出され、必要に応じてシフトされ、メモリの指定された位置に挿入される。というわけで下記のようになる。

+----+-+--+--+--+--+--+
| rX |-| 0| 0| 0| 0| 1|
+----+-+--+--+--+--+--+
|0001|-| 1| 0| 0| 0| 0|
+----+-+--+--+--+--+--+

以下は私が犯した誤り

+----+-+--+--+--+--+--+
| rX |-| 0| 0| 0| 0| 1|
+----+-+--+--+--+--+--+
|0001|-| 0| 0| 0| 0| 0| # rXの1バイト目を0001の1バイト目にストアすると勘違いしている
+----+-+--+--+--+--+--+

SLAX 1 : rA, rXを1つの値と見て左に1バイトシフトする。rAの値は、rXからずれてきた最下位バイトを除き不定とする。rXの最下位バイトはシフト演算の仕様上0が入る。

+----+-+--+--+--+--+--+
| rA |?| ?| ?| ?| ?| 0|
+----+-+--+--+--+--+--+
| rX |-| 0| 0| 0| 1| 0|
+----+-+--+--+--+--+--+
|0001|-| 1| 0| 0| 0| 0|
+----+-+--+--+--+--+--+

ENNA 1 : rAに1を符号反転エントリーする。

+----+-+--+--+--+--+--+
| rA |-| 0| 0| 0| 0| 1|
+----+-+--+--+--+--+--+
| rX |-| 0| 0| 0| 1| 0|
+----+-+--+--+--+--+--+
|0001|-| 1| 0| 0| 0| 0|
+----+-+--+--+--+--+--+

INCX 1 : rXに1を加える。これでrXは4バイト目が繰り下がり0に、最下位バイトはこのコンピュータで1バイトで表現可能な最大数 (63以上99以下) が入る。以降、この数を b と表記する。

+----+-+--+--+--+--+--+
| rA |-| 0| 0| 0| 0| 1|
+----+-+--+--+--+--+--+
| rX |-| 0| 0| 0| 0| b|
+----+-+--+--+--+--+--+
|0001|-| 1| 0| 0| 0| 0|
+----+-+--+--+--+--+--+

ENT1 1 : rI1に1をエントリーする。

+----+-+--+--+--+--+--+
| rA |-| 0| 0| 0| 0| 1|
+----+-+--+--+--+--+--+
| rX |-| 0| 0| 0| 0| b|
+----+-+--+--+--+--+--+
| rI1|+|          0| 1|
+----+-+--+--+--+--+--+
|0001|-| 1| 0| 0| 0| 0|
+----+-+--+--+--+--+--+

SRC 1 : rA, rXを1つの値と見て右回転シフトする。

+----+-+--+--+--+--+--+
| rA |-| b| 0| 0| 0| 0|
+----+-+--+--+--+--+--+
| rX |-| 1| 0| 0| 0| 0|
+----+-+--+--+--+--+--+
| rI1|+|          0| 1|
+----+-+--+--+--+--+--+
|0001|-| 1| 0| 0| 0| 0|
+----+-+--+--+--+--+--+

ADD 1 : 0001の値をrAに加える。これにより、rAの最上位バイトが1バイトで表現できる数を超え、オーバーフロートグルがオンになる。

OVERFLOW : ON
+----+-+--+--+--+--+--+
| rA |-| 0| 0| 0| 0| 0|
+----+-+--+--+--+--+--+
| rX |-| 1| 0| 0| 0| 0|
+----+-+--+--+--+--+--+
| rI1|+|          0| 1|
+----+-+--+--+--+--+--+
|0001|-| 1| 0| 0| 0| 0|
+----+-+--+--+--+--+--+

DEC1 -1 : rI1を(-1)だけ減らす、つまりINC1 1と同じ。

OVERFLOW : ON
+----+-+--+--+--+--+--+
| rA |-| 0| 0| 0| 0| 0|
+----+-+--+--+--+--+--+
| rX |-| 1| 0| 0| 0| 0|
+----+-+--+--+--+--+--+
| rI1|+|          0| 2|
+----+-+--+--+--+--+--+
|0001|-| 1| 0| 0| 0| 0|
+----+-+--+--+--+--+--+

STZ 1 : メモリの0001番地に正のゼロをストアする。

OVERFLOW : ON
+----+-+--+--+--+--+--+
| rA |-| 0| 0| 0| 0| 0|
+----+-+--+--+--+--+--+
| rX |-| 1| 0| 0| 0| 0|
+----+-+--+--+--+--+--+
| rI1|+|          0| 2|
+----+-+--+--+--+--+--+
|0001|+| 0| 0| 0| 0| 0|
+----+-+--+--+--+--+--+

CMPA 1 : rAの値をメモリの0001番地の値と比較する。比較結果の主語はrAのコンテンツである。今回はEQUALなので主語は関係ないが、LESS / GREATER の場合は主語に注意する必要がある。つまり、 rA < CONTENTS(0001)ならLESSが、rA > CONTENTS(0001)ならGREATERが設定されるということである。

OVERFLOW : ON
COMPARE  : EQUAL
+----+-+--+--+--+--+--+
| rA |-| 0| 0| 0| 0| 0|
+----+-+--+--+--+--+--+
| rX |-| 1| 0| 0| 0| 0|
+----+-+--+--+--+--+--+
| rI1|+|          0| 2|
+----+-+--+--+--+--+--+
|0001|+| 0| 0| 0| 0| 0|
+----+-+--+--+--+--+--+

MOVE -1,1(1) : メモリの-1番地をrI1で修飾した値を1回rI1で指定された番地に移動する。メモリの-1番地をrI1で修飾すると結果は1となるため、結局メモリの0001番地の値を1回0002番地へ移動することになる。rI1は、移動した回数だけ増えるため、3となる。

OVERFLOW : ON
COMPARE  : EQUAL
+----+-+--+--+--+--+--+
| rA |-| 0| 0| 0| 0| 0|
+----+-+--+--+--+--+--+
| rX |-| 1| 0| 0| 0| 0|
+----+-+--+--+--+--+--+
| rI1|+|          0| 3|
+----+-+--+--+--+--+--+
|0001|+| 0| 0| 0| 0| 0|
+----+-+--+--+--+--+--+
|0002|+| 0| 0| 0| 0| 0|
+----+-+--+--+--+--+--+

NUM 1 : 1は無視される。rA, rXを一つの十進数の文字表現の文字コードと見て、その数値をrAにセットする。文字コードは下一桁の一致だけ見るので、この値は10000である。10000は、どんなMIXコンピュータでも2バイトでは表現できず3バイトで表現できるので、rAの下位3バイトが10000の表現に使われる。

OVERFLOW : ON
COMPARE  : EQUAL
+----+-+--+--+--+--+--+
| rA |-| 0| 0|   10000|
+----+-+--+--+--+--+--+
| rX |-| 1| 0| 0| 0| 0|
+----+-+--+--+--+--+--+
| rI1|+|          0| 3|
+----+-+--+--+--+--+--+
|0001|+| 0| 0| 0| 0| 0|
+----+-+--+--+--+--+--+
|0002|+| 0| 0| 0| 0| 0|
+----+-+--+--+--+--+--+

CHAR 1 : 1は無視される。rAの値を十進数の文字列としてその文字コードをrA, rXに格納する。

OVERFLOW : ON
COMPARE  : EQUAL
+----+-+--+--+--+--+--+
| rA |-|30|30|30|30|30|
+----+-+--+--+--+--+--+
| rX |-|31|30|30|30|30|
+----+-+--+--+--+--+--+
| rI1|+|          0| 3|
+----+-+--+--+--+--+--+
|0001|+| 0| 0| 0| 0| 0|
+----+-+--+--+--+--+--+
|0002|+| 0| 0| 0| 0| 0|
+----+-+--+--+--+--+--+

HLT 1 : コンピュータを停止する。

というわけで、最終状態は上記の通り。

一問解いただけなのにとても長くなってしまった。ブートストラッピング問題はまた次回。


この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

ksk

哲学者でも科学者でもない素人が、哲学とか科学とか科学哲学とかを考えながら本を読む。

TAOCP読書メモ

Donald E. Knuth博士の The Art of Computer Programming の読書メモ。 アスキードワンゴ社から出ている日本語訳を読んでいます。 https://asciidwango.jp/post/122327235600/the-art-of...
コメントを投稿するには、 ログイン または 会員登録 をする必要があります。