基本情報技術者 2017年 春期 午後 問12
次のアセンブラプログラムの説明及びプログラムを読んで、設問1〜3に答えよ。
〔プログラム1の説明〕
64ビット符号なし整数の加算を行う副プログラムADD64である。64ビット符号なし整数の主記憶への格納方法を、図1に示す。
(1) GR1及びGR2には、それぞれ次の内容が設定されて、主プログラムから渡される。
GR1、GR2：加算の対象となる二つの64ビット符号なし整数を格納する領域の先頭アドレス。各領域はそれぞれ連続した4語から成る。
ここで、GR1とGR2の値が等しい場合を除き、GR1とGR2が指し示す領域は重ならないものとする。
(2) 副プログラムADD64は、GR1に設定されたアドレスから始まる連続した4語の領域に、加算の結果を格納する。このとき、桁あふれは発生しないものとする。
(3) 副プログラムADD64から戻るとき、汎用レジスタGR1〜GR7の内容は元に戻す。
設問1：
問題文を見る プログラム1中のに入れる正しい答えを、解答群の中から選べ。
a, bに関する解答群
ア：AND GR5,=1
イ：CPL GR3,=0
ウ：CPL GR3,GR1
エ：CPL GR3,GR2
オ：LD GR5,=1
cに関する解答群
ア：JOV LOOP
イ：JUMP LOOP
ウ：JZE LOOP
模範解答
a：オ、b：ウ、c：イ
解説
解答の導き方
このプログラムは、2つの64ビット符号なし整数を、16ビットずつに分けて加算します。符号なし整数は、負の値を扱わない整数です。図1では、N番地に最上位16ビット、N+3番地に最下位16ビットが格納されています。
したがって、加算は最下位の部分から始め、桁上がりを次の上位の部分へ渡す必要があります。桁上がりとは、ある16ビットの部分の計算結果が以上になったとき、次の上位の部分に加える値です。
1. GR3とGR4は、最下位の部分を指しています
プログラムでは、次の処理でGR3とGR4にアドレスを設定しています。
- GR3には、GR1に3を加えたアドレスを設定します。
- GR4には、GR2に3を加えたアドレスを設定します。
各整数は「連続した4語」から成り、最下位16ビットは先頭アドレスから3番目後ろにあります。そのため、GR3とGR4は、それぞれ加算対象の最下位の部分を指します。
その後、GR3とGR4を1ずつ減らしていけば、最下位から上位へ向かって処理できます。
2. GR0で桁上がりを受け渡します
最初にGR0を0にしています。GR0は、前の部分から受け取った桁上がりを一時的に入れるレジスタです。最下位の部分を計算するときは、まだ前の部分がないため、桁上がりは0です。
各部分の加算では、次のように処理します。
3. aは、オーバフローが起きたことをGR5に記録します
GR5は各部分の計算の初めに0にされます。計算中にオーバフローが起きた場合は、その部分から次の上位の部分へ桁上がりを渡す必要があります。そのため、GR5を1にします。
選択肢では、GR5に1を設定する処理は「LD GR5,=1」です。これを2か所のaに入れることで、どちらの加算でオーバフローが起きても、GR5に桁上がりを記録できます。
GR5を最初に0にしているため、オーバフローがなかった場合は0のままです。加算後にGR5をGR0へ移すことで、次の上位の部分に桁上がりを渡せます。
なお、「桁あふれは発生しない」とあるのは、64ビット全体の計算結果が64ビットの範囲を超えないという意味です。途中の16ビットの加算ではオーバフローが起こることがあるため、aで桁上がりを処理しています。
4. bは、最上位の部分まで処理したかを調べます
GR3は最初にGR1+3を指し、その後1ずつ減ります。つまり、処理対象のアドレスはGR1+3、GR1+2、GR1+1、GR1の順に移ります。
現在の部分の結果を格納した後、GR3がGR1と等しいかを調べます。等しければ、GR1が指す最上位の部分まで処理し終えたため、終了します。この比較を行う処理が「CPL GR3,GR1」です。
比較する相手がGR2ではない点にも注意してください。GR2はもう一方の整数の先頭アドレスです。処理の終了を判断するには、結果を書き込む側の先頭アドレスであるGR1と比較します。
5. cは、次の部分の処理へ必ず進みます
最上位の部分でなければ、GR3とGR4を1ずつ減らし、次の上位の部分を処理します。この繰返しは、次の部分がある限り必ず続ける必要があります。
「JOV LOOP」はオーバフローがあった場合だけ、「JZE LOOP」は計算結果が0の場合だけ分岐します。どちらも、繰返しを必ず続ける処理ではありません。条件に関係なく戻る「JUMP LOOP」をcに入れます。
最後に、GR1が指す領域に加算結果を格納します。また、最初の「RPUSH」と最後の「RPOP」によって、GR1〜GR7の内容を元に戻します。
誤りやすいポイント
-
64ビットの加算を一度に行うと思い込むこと
このプログラムは、16ビットの部分ごとに加算し、桁上がりを受け渡します。 -
最上位の部分から加算を始めること
桁上がりは下位から上位へ伝わるため、最下位の部分から処理します。 -
オーバフローがなければGR5を1にすると思うこと
GR5は各回の初めに0になります。オーバフローが起きたときだけ1にすることで、桁上がりの有無を表します。 -
GR3とGR2を比較すること
繰返しの終了条件は、結果を書き込む領域の最後の部分まで処理したかどうかです。そのため、GR3と比較するのはGR1です。 -
「JOV LOOP」や「JZE LOOP」を繰返しに使うこと
どちらも条件が成立したときだけ分岐します。各部分を順番に処理するため、条件なしで分岐する命令が必要です。
FAQ
Q: なぜGR0を各部分の処理のたびに0にしないのですか？
A: GR0には、前の部分から渡された桁上がりを入れます。毎回0にすると、その桁上がりが失われます。最初の部分だけは前の部分がないため、最初に0にします。
A: GR0には、前の部分から渡された桁上がりを入れます。毎回0にすると、その桁上がりが失われます。最初の部分だけは前の部分がないため、最初に0にします。
Q: 2つの加算のどちらかでオーバフローが起きたら、なぜGR5を1にするのですか？
A: どちらの加算で起きた場合でも、次の上位の部分へ桁上がりを渡す必要があるためです。GR5が1であれば、次の回のGR0に桁上がりを渡せます。
A: どちらの加算で起きた場合でも、次の上位の部分へ桁上がりを渡す必要があるためです。GR5が1であれば、次の回のGR0に桁上がりを渡せます。
Q: なぜ最上位の部分を処理した後に終了するのですか？
A: 64ビットの整数は4語で構成されます。最下位から順に処理し、GR3がGR1と等しくなったとき、4つの部分をすべて処理し終えたと判断できます。
A: 64ビットの整数は4語で構成されます。最下位から順に処理し、GR3がGR1と等しくなったとき、4つの部分をすべて処理し終えたと判断できます。
関連キーワード: 符号なし整数、桁上がり、オーバフロー、レジスタ、条件分岐
設問2：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
GR1及びGR2に設定したアドレスから始まる連続した4語の領域に、図2のとおりに値を格納して副プログラムADD64を実行したとき、行番号7の命令を2回目に実行した後のGR0の値はdである。
dに関する解答群
ア：#0000
イ：#0001
ウ：#2E0C
エ：#2E0D
オ：#3F1D
カ：#3F1E
模範解答
d：エ
解説
解答の導き方
求めるのは、行番号7の命令を2回目に実行した直後のGR0です。GR0は計算途中の値を入れるレジスタ（CPUが一時的に値を置く場所）です。
図1では、N番地に「最上位16ビット」、N+3番地に「最下位16ビット」が格納されています。プログラムはGR3をGR1+3に設定してから、処理のたびにアドレスを1ずつ減らします。そのため、最下位の16ビットから順に加算します。
-
1回目の行番号7
- GR3はGR1+3を指し、図2の値は#A684です。
- GR0は行番号3で0に初期化されているため、行番号7の加算後はGR0が#A684になります。
-
1回目の行番号11と、その後の処理
- GR4もGR2+3を指しているので、行番号11では#B759を加えます。
- 加算結果は、#A684 + #B759 = #15DDDです。ただし、GR0に格納できるのは16ビット分なので、GR0には下位16ビットの#5DDDが残ります。
- 16ビットからあふれた分をキャリー（次の上位の桁に渡す値）として記録します。この加算ではキャリーが1です。
- 行番号16でそのキャリーがGR0に移され、GR0は#0001になります。
-
2回目の行番号7
- GR3は1つ前のアドレスに戻るため、GR1+2を指します。図2でこの位置の値は#2E0Cです。
- 行番号6で初期化されるのはGR5です。GR0は初期化されず、行番号16で移されたキャリー#0001を保持しています。
- したがって、2回目の行番号7では、GR0に#2E0Cを加えます。
この値は解答群のエです。
誤りやすいポイント
-
GR1の先頭から順に処理すると考えること
図1では最下位16ビットがN+3番地にあります。プログラムはGR1+3から始めるため、最下位の部分から処理します。 -
#15DDDがそのままGR0に入ると考えること
GR0に入るのは16ビット分の#5DDDです。あふれた分はキャリーとして別に扱われます。 -
行番号6でGR0も0に戻ると考えること
行番号6で0に設定されるのはGR5です。GR0には、直前の処理でGR5から移されたキャリーが残ります。
FAQ
Q: 2回目の行番号7で、GR0に#5DDDではなく#0001が入っているのはなぜですか？
A: 行番号15で#5DDDをメモリに格納した後、行番号16でGR0をGR5の値に置き換えるためです。GR5にはキャリーの#0001が記録されています。
A: 行番号15で#5DDDをメモリに格納した後、行番号16でGR0をGR5の値に置き換えるためです。GR5にはキャリーの#0001が記録されています。
Q: 2回目の行番号7では、GR2の値も加算しないのですか？
A: 行番号7は、GR3が指すGR1側の値を加算する命令です。GR2側の値は、行番号11で加算します。
A: 行番号7は、GR3が指すGR1側の値を加算する命令です。GR2側の値は、行番号11で加算します。
Q: なぜ下位16ビットから順に加算するのですか？
A: 下位の部分で発生したキャリーを、次の上位の部分の加算に使うためです。
A: 下位の部分で発生したキャリーを、次の上位の部分の加算に使うためです。
関連キーワード: 16進数、16ビット演算、キャリー、オーバーフロー、レジスタ
設問3：
問題文を見る 副プログラムADD64を使用して、32ビット符号なし整数の乗算を行う副プログラムMUL32を作成した。プログラム2中のに入れる正しい答えを、解答群の中から選べ。
〔プログラム2の説明〕
(1) 32ビット符号なし整数の主記憶への格納方法を、図3に示す。
(2) GR1〜GR3には、それぞれ次の内容が設定されて、主プログラムから渡される。
GR1、GR2：乗算の対象となる二つの32ビット符号なし整数を格納する領域の先頭アドレス。各領域はそれぞれ連続した2語から成る。
GR3：乗算結果となる64ビット符号なし整数を格納する領域の先頭アドレス。領域は連続した4語から成る。
ここで、GR1、GR2及びGR3が指し示す領域は互いに重ならないものとする。
(3) 副プログラムMUL32から戻るとき、汎用レジスタGR1〜GR7の内容は元に戻す。
e, fに関する解答群
ア：JMI LOWORD
イ：JNZ LOWORD
ウ：JPL LOWORD
エ：JZE LOWORD
オ：LAD GR2,TEMP
カ：LD GR2,=1
キ：LD GR2,GR3
ク：LD GR2,TEMP
模範解答
e：ア、f：オ
解説
解答の導き方
このプログラムは、32ビット符号なし整数の一方の値を、もう一方の値の各ビットに応じて足し合わせます。32ビット符号なし整数は負の値を扱わず、32個のビットで表す数です。
掛け算の考え方は、たとえば値を2進数で表し、各桁が1なら、その桁の位置に合わせた値を足すことです。プログラムでは、加算する値をTEMPに置き、ループのたびに2倍にして、桁の位置に合わせています。
1. GR5が表すビットの位置を確認します。
GR5はループカウンタで、0から31まで変化します。32ビットの値は、図3のように上位16ビットと下位16ビットに分けて格納されています。
GR5が0〜15なら、調べるビットは下位16ビットの中にあります。一方、GR5が16〜31なら、上位16ビットの中にあります。
2. eでは、GR5の値に応じて読む語を選びます。
該当部分では、まずGR6にGR5を設定し、16を引いています。つまり、GR6の値はGR5から16を引いた値です。
- GR5が0〜15なら、GR6は−16〜−1となり、負の値です。
- GR5が16〜31なら、GR6は0〜15となり、負ではありません。
JMIは、直前の計算結果が負のときに指定した場所へ移る命令です。そのため、負になる場合、つまりGR5が0〜15の場合にLOWORDへ移れば、下位16ビットを読み取れます。したがって、eにはアのJMI LOWORDが入ります。
LOWORDへ移らなかった場合は、すでに読み込まれている上位16ビットを使います。GR6はGR5から16を引いた値なので、上位16ビット内でのビット位置として使えます。
3. 読み取ったビットが1なら、TEMPの値を結果に足します。
読み取った語を右にシフトし、AND GR0,=#0001で最下位の1ビットだけを取り出します。JZE EXITLOOPは、そのビットが0なら加算を省略するための命令です。
ビットが1なら、GR1に結果の先頭アドレスGR3を設定し、GR2にTEMPの先頭アドレスを設定してADD64を呼び出します。ADD64は、GR1とGR2が指す64ビットの値を加算し、結果をGR1が指す領域に格納します。
4. fでは、TEMPを自分自身に加算するようにします。
ビットの処理後、GR5を1増やします。次のビットを調べるときには、TEMPの値を2倍にしておく必要があります。2倍にするには、TEMPの値をTEMP自身に足します。
このとき、すでにGR1にはLAD GR1,TEMPによってTEMPの先頭アドレスが設定されています。ADD64のもう一方の加算対象も同じTEMPにするため、GR2にもTEMPの先頭アドレスを設定します。したがって、fにはオのLAD GR2,TEMPが入ります。
LADはアドレスを設定する命令です。これに対してLD GR2,TEMPではTEMPに格納されている値を読み込むため、ADD64に渡すアドレスにはなりません。
誤りやすいポイント
- GR5が0〜15のときに下位16ビットを使う点を逆にしないようにします。16ビットずつに分かれているため、ビット位置が15以下なら下位側、16以上なら上位側です。
- eでは、GR5そのものではなく、GR5から16を引いた後の結果で条件分岐します。0〜15の場合に負になるため、JMIでLOWORDへ移ります。
- ADD64に渡すのは値そのものではなく、値が格納された領域の先頭アドレスです。TEMPを指定する箇所では、LDではなくLADを使います。
- 掛け算の各段階では、ビットが1のときだけ加算します。0のときは加算を省きますが、次のビットに進むためのTEMPの2倍処理は行います。
FAQ
Q: TEMPを毎回2倍にするのはなぜですか？
A: ループごとに調べるビットの位置が1つ上がるからです。ビット位置が1つ上がると、その位置に対応する値は2倍になります。
A: ループごとに調べるビットの位置が1つ上がるからです。ビット位置が1つ上がると、その位置に対応する値は2倍になります。
Q: GR1とGR2が同じTEMPを指してもADD64を使えるのですか？
A: 問題文では、GR1とGR2の値が等しい場合を除き、領域は重ならないとされています。TEMPを自分自身に加えるときはGR1とGR2が同じアドレスになりますが、この場合はADD64の仕様で許されています。
A: 問題文では、GR1とGR2の値が等しい場合を除き、領域は重ならないとされています。TEMPを自分自身に加えるときはGR1とGR2が同じアドレスになりますが、この場合はADD64の仕様で許されています。
Q: 読み取ったビットが0なら、TEMPの値を2倍にしなくてよいですか？
A: 2倍にする必要があります。加算を省略するのはそのビットに対応する値を結果に足す処理だけです。次のビットに対応する値を用意するため、TEMPはビットが0の場合も2倍にします。
A: 2倍にする必要があります。加算を省略するのはそのビットに対応する値を結果に足す処理だけです。次のビットに対応する値を用意するため、TEMPはビットが0の場合も2倍にします。
関連キーワード: 符号なし整数、2進数、シフト演算、条件分岐、加算命令
