The Art of Computer Programming を読む(4)

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

26.

ブートストラッピング問題。

MIXの場合は、カードから起動時の処理を読み込むという処理が組み込まれている (GOボタン)。したがって、この最初に読み込むカードに、「カードを読み込む」という処理、つまりカードローディングルーティンを書いておく必要がある。

現代のコンピュータで言えば、MBR (Master Boot Record) に書かれている処理のようなものだろうか。自分が今まで書いたこともないような処理だったので新鮮に感じた。

処理の概要

カードデッキは、
・ローディングルーティンが書かれたカード
・インフォメーションカードが複数枚
・転送カードが1枚
のものがあるということだ。

大まかな処理の流れは下記のようになるだろう。

カード読取機は、必ず1回で16ワード、80文字を読む。1枚のカードには80文字までパンチできると考えられる。

最初、ローディングルーティンがパンチされたカードは1枚だけかと勘違いし、
「どうやったらこんなロジックが16ワードでおさまるんだ？不可能じゃないか？」
と思って唸っていたが、Knuth先生の回答を見たところあっさり二枚のカードが使われていた。そりゃそうですよね。

カードの種類分け

カードにパンチできない文字種の関係で、CMP, ENT, INC, DECなどが使えない。
分岐のためにジャンプは必要なので、比較対象の値とSUBして結果がゼロかどうかをJAZでチェックする、という方法をとる。だいたい以下のような感じになる。

LDA 0016
SUB 0015
JAZ 0014

転送カードのパース

転送カードのフォーマットは以下のようになっている。

TRANS0nnnn

これを、例えば0048-0063番地に読み込むと、以下のように文字コードとして読まれる (cn は n の文字コードとする)。

+----+-+--+--+--+--+--+
|0048|+|23|19|01|15|22|
+----+-+--+--+--+--+--+
|0049|+|30|cn|cn|cn|cn|
+----+-+--+--+--+--+--+
|0050|+|00|00|00|00|00|
+----+-+--+--+--+--+--+
...

転送カードかインフォメーションカードかを見分けるために、比較対象の値を比較用にどこかに持っておく必要がある。ローディングルーティン用カードにパンチしておく必要があるだろう。

ちなみにKnuth先生の解答を見たところ、転送カードの6文字目がゼロであることを分岐に利用していた。インフォメーションカードの6文字目は1以上7以下である。これが賢い方法だ。

ジャンプ先の番地は、NUMで変換してからメモリ中にストアする必要がある。NUMで適切に変換するには、rA, rXが以下の状態になっていなければならない。

+----+-+--+--+--+--+--+
| rA |+|00|00|00|00|00|
+----+-+--+--+--+--+--+
| rX |+|00|cn|cn|cn|cn|
+----+-+--+--+--+--+--+

普通に考えると、

LDA 0049(0:0)
LDX 0049(2:5)

のようなことをやるのだが、(2:5) = 2*8+5 = 21 であるため、この文字をカードにパンチできない。したがって (2:5) フィールド指定は使えないというトラップがある。

結局、rAにロードした値を、Aを1バイト左シフトしてからAXとして6バイト右シフトするということをやる。

ジャンプ先は0064番地にストアすることにすると、転送カードのパースロジックは以下のようになる。

 LDA 0049
 SLA 1    # 左シフトして6文字目を削除
SRAX 6    # 7-10文字目がrXに入るように右シフト
 NUM 0    # rAにジャンプ先アドレスが入る
 STA 0064 # ジャンプ先アドレスを格納
 JMP 0064 # ジャンプ。これで本体プログラムが開始される

インフォメーションカードのパース

基本的には、読み込んでストア先にストアしていくというのをカードに指定されたワード数だけ繰り返す。

ただし、カードにパンチできる文字の制約から、INC, DEC命令が使えない。1を足す・1を引くという処理を自分で書く必要がある。

この辺りで半分ギブアップしかかっていたのでKnuth先生の解答を見たところ、7-10文字目を入手するために書いた SLA 1 のバイトから1を入手して、これを使って計算するということをしていた。賢い。

ストア先アドレスの先頭を、転送カードと同じく0064番地に格納することにする。インフォメーションカードの読み込みバッファを走査するためのインデックスをrI2にやらせる。ストア先アドレスはrI3に格納する。

 LDA 0049
 SLA 1        # この番地を =1= と書く
SRAX 6   
 NUM 0        # この番地を =0= と書く
 STA 0064
 LD2 =0=(0:2) # LD2 <- 0
 LD3 0064     # LD3 <- ストア先アドレス
 LDA 0050,2   # この番地を =2= と書く
 LDX 0051,2
 NUM 0
 STA 0,3(1:5) # 符号以外をストア先アドレスに格納
 LDA =2=(3:3) # =2= のインデックスバイト 2 をロード
 ST2 0065
 ADD 0065
 STA 0065
 LD2 0065     # rI2 <- rI2 + 2

……まあこんな感じで、途中で挫折してしまった。自力で考えるにはかなりハードルが高い。

とは言え、自分で頭をひねってからKnuth先生の模範回答を見ると、自分ができなかったところの工夫のしどころがわかって勉強にはなったと思う。Knuth先生の模範解答の自分なりの理解・解説も余力があれば書いてみたい。

1.3.1はこれくらいにして、次回は1.3.2 MIXアセンブリ言語に入る。