EDSACのイニシャルオーダーがわからない日記

EDSACのイニシャルオーダーはテープから1文字ずつ読んでそれを機械語の形にアセンブルしてメモリに記録していくプログラムで、いわば「元祖アセンブラ」なんだ。で、面白いのでそれを実装していたのだけども、ここがよくわからない


http://www.cl.cam.ac.uk/~mr/edsacposter.pdf

これは10進法でテープに書かれているアドレスの数値を読んで、前の桁を10倍して新しい桁を足して、をやっている部分。
あらかじめメモリに10 << 11を入れておいて、前の桁にそれを掛けて、さらに << 5してから次の桁を足して、とやっている。合計で「10 << 16」を掛けていることになる。ところがこのマシン、ビット幅が17ビットで、加算レジスタ(AB)はは17ビットを2つ、間に1ビットのpaddingを挟んだ35ビットなんだ。だから18ビットシフトしないと上の半分で10倍になるところまで来ない。

実例を交えてもう一度説明すると、前回読んだ値が1だとする。

m[1] == 00000000000000001

そうすると10 << 11を掛けたら

00000000000000000 0 00101000000000000

で、5個シフトしても

00000000000000010 1 00000000000000000

ここで上半分に次の数値2をたそうとするんだけども本当はその時に上半分は1010になってなきゃいけないと思うのに2ビットほど足りない。

2ビットずれるような誤解っていうと「ビットシフトはパディングビットを使わない」+「最上位ビットは符号ビットでシフトの時には使わない」の合わせ技くらいしか思いつかないんだけど、かなり無理のある解釈のような気がする。なにが正解なんだろう。

        • -

追記。他の実装 ( http://www.cl.cam.ac.uk/users/mr/Edsac/edsac.tgz )を参考にしてみたが、どう見ても加算レジスタ(ABC)の71ビット全体をシフトしているようにしか見えないなぁ。

AND shl(bits) BE
{ { a0, a1, a2, a3, a4 := a0<<1, a1<<1, a2<<1, a3<<1, a4<<1
    UNLESS (bits&1)=0 BREAK
    bits := bits>>1
  } REPEAT

  a0 := a0 + (a1>>15) & #x7FFF
  a1 := a1 + (a2>>15) & #x7FFF
  a2 := a2 + (a3>>15) & #x7FFF
  a3 := a3 + (a4>>15) & #x7FFF
  a4 := a4            & #x7FF0
}

5ビットシフトしているところを7ビットシフトに書き換えちゃえば期待通りに動くと思うけども、そもそものコードが5ビットシフトで正しいとすると僕の処理系の実装の側が間違っているわけだからそういうワークアラウンドをしても後でまたシフトを使っているところで死ぬだろうしなぁ。

        • -

「7ビットシフトに書き換えちゃえばここに関しては期待通り動くはず」という僕の解釈が事実かどうかを検証する必要があると思ったので試しに書き換えてみた。結果、テープから読んだ平方数を求めるプログラムがちゃんと100回のループを行なってZSで正常終了するようになった。だから「アドレスの読み込み部は7ビットシフトに書き換えると正しい挙動」まではOK。んでもってその正常終了したプログラムの出力結果の数値がデタラメなので、やっぱりシフトかなにかこのあたりで使っている演算について実際のマシンとは異なる挙動をしているのだろう。シフトを書き換えると簡単に直るからシフトが原因じゃないかと思っているのが視野狭窄で、問題は別の場所にあるのかもしれないなぁ。

        • -

そうか、わかった。間違っているのは掛け算だ。そう考えると5ビットシフトである理由がすんなり説明できる。「10<<11を掛ける」と聞いて僕は暗黙に「整数の掛け算」だと思い込んだけども、これ符号付きの固定小数点数なんだな。 http://www.dcs.warwick.ac.uk/~edsac/Software/EdsacTG.pdf を参照。

00101 0 0000000000 0は
+.01010...

そうすると、これに+.000...001を掛けた結果はその1の場所より5ビット下に01010と並ぶことになる。これを5ビットシフトすれば結果的に「整数の10を掛ける」が実現できる。

        • -

イニシャルオーダーによってメモリ上に読まれたパターンが全部一致することが確認できた。めでたしめでたし。しかし読んだコードの実行結果にはまだ誤りがあるから別のバグが残ってるんだろうなー。