平成29年度秋季 基本情報技術者試験（FE）
午後 問12 アセンブラ

【レジスタの値】の（10）は、10進数を表します。

……ところで、アセンブラの問題をトレースするとき、1語16ビットのビット列をどのようにメモしていけばよいでしょうか？
16個の0と1を全部書いていたら長くて時間がかかりますし、間違えやすくもなります。
そこで私は、上記【レジスタの値】のように、同じ値が数個以上並ぶ部分は「……」で書くようにしています。
「……」は、そのすぐ左の値（上の例では1）がずっと並んでいることを表しています。
ここのGR6は全部1ですから、「1……」と書いてもよいことになります。
……もっとよい方法があれば、ぜひご教授ください。

【レジスタの値】GR6 = 0001……1

……GR6への連続的な処理から見て、また次の行に新しいコメントが付いていることから見て、どうやら4行目の「マスク作成」はここで完成したようです。
ということは、コメントが付いた行は、そのコメントの処理が「そこで始まる」ことを示しているだけで、その処理は複数行にわたることもある、ということになります。

【レジスタの値】GR4 = 0101 0……0（←αの1語目）

【レジスタの値】GR5 = 1111……1（←αの2語目）

【レジスタの値】GR1 = 32（10）

【レジスタの値】GR1 = 29（10）

【レジスタの値】GR3 = 29（10）

【レジスタの値】GR7 = 0101 0……0（←αの1語目）

最初の空欄です。
13行目までを読んだだけでは埋められませんので、先を見てみます。

となって、0になりませんから、15行目でラベル FOUND には跳ばず、そのまま16行目に入ることになります。

βが3ビットだった場合、30回行われるようです。
ということは、カウンタの上限は（32 - n + 1）= 30回に設定しておかなければならないのではないでしょうか？
GR1に設定されたのは（32 - n）= 29でしたから、これだと1回少なくなってしまいそうですよね。
この回数のズレはどのように処理するのか？
続きを見てみましょう。

「JMI FIN」は「16行目の処理結果がマイナスなら、ラベル FIN にジャンプせよ」という命令です。
上の疑問はこれで解決しました。
カウンタ変数29で30回繰り返すためには、1で終わるのではなく、0で終わればよいわけです。
つまり、カウンタ0（＝今の設定では30回目の処理）の回はそのまま処理を続け、それが終わってカウンタ-1になった時点で処理を終わらせればよいのです。
ここにはその命令「カウンタがマイナスになったら終わり」が書かれています。
……ラベル FIN を「終わり」と断定してしまいましたが、FEの場合、ラベル FIN はほぼ終了処理の箇所に貼られていると考えて間違いありません。

【レジスタの値】GR4 = 1010 0……0（←αの1語目の1ビット左論理シフト）

【レジスタの値】GR5 = 1111 1……0（←αの2語目の1ビット左論理シフト）

二つ目の空欄です。
先を見てみます。

「JUMP LP」は「ラベル LP にジャンプせよ」という命令です。
ここから12行目のラベル LP に跳ぶということは、以前通過した行に戻る、つまりループということになりますので、LP は、やはりループ開始位置を示すラベルだったようです。
さて、18行目と19行目は、ビット列αを1ビット左に論理シフトする命令でした。
この行の JUMP 命令から見て、18～20行目は次のループの準備処理と見てよさそうです。
1語目と2語目を左シフトして、あとは何をすれば次のループに進めるのでしょうか？
検索ビット列βはGR2に左詰めで格納されています（残りのビットは0埋め）。
これとαのビット列を左から順に比較していくためには、18、19行目で行ったように、αを1ビットずつ左シフトして、毎回検索開始位置を左端に持っていけばよさそうです。
ところが、ここで一つ問題が出てきます。
αは「連続する2語」なのであり、前の16ビットと後ろの16ビットは繫がっていないのです。
ということは、2語目の左端が1だった場合、左シフトするとその1はこぼれ落ちてなくなってしまいます（下図1回目の赤字ビット参照）。
そうなったときは、1語目の右端に1を足しておかねばなりません（下図2回目の赤字ビット参照）。
20行目の空欄 b にはその処理が入りそうです。

設問 1 空欄 b の選択肢を見ると、ラベル NEXT に進むか FOUND に進むかの二通りに分かれます。
FOUND は、15行目で見たように、βと同じビット列が「見つかった場合」に進む行のラベルでしたから、除外してしまってよさそうです。
「19行目で1がこぼれ落ちた場合＝オーバーフローした場合、ラベル NEXT に進む」選択肢は、エ「JOVNEXT」です。
念のためにジャンプ先も見ておきましょう。

【レジスタの値】GR4 = 1010 0……1

これで空欄は二つとも埋まりましたが、処理の終わりまで確認しましょう。

2行上と同じ命令ですね。
ということは、2語目の左シフトがオーバーフローした場合、22行目の処理だけをプラスしてからループ2回目に入る、ということになります。

【レジスタの値】GR7 = 1010 0……1

【レジスタの値】GR7 = 1010 0……0

【レジスタの値】GR7 = 0000……0

今回は14行目の結果が0、すなわち「一致あり」ですので、ラベル FOUND にジャンプします。

GR3はループの上限回数でした。
GR1はカウンタ変数で、GR3と同じ値でスタートしてループ一回ごとに-1され、pはαの検索文字位置で、こちらは0からスタートして一回ごとに+1されます。
つまり、pは「GR1の減った値」に対応しているのです（GR1が1減ればpは1、GR1が2減ればpは2、といった具合）。
GR1が初期値からいくつ減ったのかは、初期値をずっと格納しているGR3から減算することで得られます。
従って、GR3 - GR1 = p という関係が成立するのですね。

【レジスタの値】GR0 = 1（10）

なお、先の説明（3）に「副プログラム BSRH から戻るとき、汎用レジスタGR1～GR7の内容は元に戻す」とありましたので、GR1～GR4は、このプログラム開始時に設定した値に戻されます。

【レジスタの値】GR2 = 14（10）

「4行目の処理がマイナスなら、ラベル FIN へジャンプせよ」というコマンドです。
GR0は、一致するビット列がない場合は「-1」が設定されるのでした。
つまり、αにβと一致するビット列がなかった場合は、ここでラベル FIN（おそらく終了処理）へ進みます。

【レジスタの値】GR6 = 1111 10……0

【レジスタの値】GR7 = 5（10）

【レジスタの値】GR3 = 16（10）

【レジスタの値】GR3 = 2（10）

「JMI ONL2」は「11行目の結果がマイナスなら、ラベル ONL2 にジャンプせよ」という命令です。
「JZE ONL2」は「11行目の結果が0なら、ラベル ONL2 にジャンプせよ」という命令です。
コメントに「一致する部分ビット列が2語目だけのとき」とあります（ということは、ONL は ONLY の略？）。
βと同じビット列がαの2語目だけに含まれるのは、pの値が16以上の場合です。
よって、（16 - p）が0以下になれば、βと同じ文字列は2語目に含まれる、ということになるわけですね。
今トレースしている値では（16 - p）が2ですから、ラベル ONL2 には跳ばずにそのまま下に進みます。

コメントにあるように「（16 - p）とnの比較」です。
（16 - p）が0かマイナスの場合は、この行には入らずラベル ONL2 にジャンプしますので、ここに入ったということは、（16 - p）は正の数ということになります。
それとβの長さnを比較していますね。

こうして図にしてみると分かりやすくなります。
（16 - p）の「16」という数字は、1語目の長さと考えるよりも、「2語目の先頭番号」と考えた方がよさそうです。
そうなると、（2語目の先頭番号 - p）、すなわち（16 - p）で「1語目の終端からpまでのビット数」が得られることになります（○囲みの数字）。
それがβの長さ（= n）より大きいか、あるいは同数であれば、一致ビット列は1語目に収まります（いちばん上と二番目の図）。
また、それがβの長さ（= n）より小さければ、1語目の終端からはみ出して2語目にまたがることになるわけです（三番目の図）。
今はn = 5、p = 14ですので、「2語にまたがる処理」となります。
16行目は飛ばし、17行目のラベル NEXT に入ります。

【レジスタの値】GR5 = 1111 0……0（←γのコピー）

【レジスタの値】GR7 = 1111 10……0（←マスクのコピー）

サブルーチン S1 を呼び出しています。
S1 は FIN ラベルよりも下、35行目に書いてあります。
コメントは「1語目の処理」ですから、1語目の、右端から2ビット分の処理をするのでしょう。
そちらにジャンプしましょう。

【レジスタの値】GR4 = 0……0011（←γの左2ビット分を右端に寄せたもの）
【レジスタの値】GR6 = 0……0011（←マスクの左2ビット分を右端に寄せたもの）

【レジスタの値】GR2 = 1111……0011

【レジスタの値】GR6 = 1……1100

【レジスタの値】GR2 = 1111……0000

空欄 d の方が c よりも先に来ました。
39行目までを読んだだけでは埋められませんので、先を見てみます。

【レジスタの値】GR2 = 1111……0011（←GR1のアドレスが指し示す1語目の領域もこの値に置き換えられた）

20行目に戻ります。

【レジスタの値】GR4 = 1111 00……0
【レジスタの値】GR6 = 1111 10……0

GR4とGR6を、GR3の値分だけ左に論理シフトしています。
GR3には（16 - p） = 2が格納されていたのでした。
1語目の処理では右シフトでしたが、2語目の処理では左シフトになっています。
一致ビット列が2語にまたがる場合、2語目の方の書き換えるべきビット列は、1語目とは逆に左端にあるからですね。

【レジスタの値】GR4 = 1100……0
【レジスタの値】GR6 = 1110……0

ここで設問4の答えが出ました。
この段階でのGR6の値は「1110 0000 0000 0000」= オ「#E000」です。

【レジスタの値】GR1 = #8001

【レジスタの値】GR2 = 0111……1

【レジスタの値】GR6 = 0001……1

【レジスタの値】GR2 = 0001……1

41行目のST命令で、その値を2語目のアドレス領域（#8001）に上書きしています。
42行目のRETで元の25行目に戻りますが、26行目はラベル FIN に跳んですぐ終了しますので、これでこの処理は終了です。

【レジスタの値】GR2 = 1101……1（←GR1のアドレスが指し示す2語目の領域もこの値に置き換えられた）

【レジスタの値】GR3 = -1（10）

空欄 c です。
先を見てみます。

……それにしても、この空欄 c を含む29・30行目のような方法は、アセンブラでは一般的なのでしょうか？
ごく普通に用いられる手法・発想だとしたら、私はまだまだ入門レベルの域を出ていないということになりそうです。