基本情報技術者 2011年 春期 午後 問12
次のアセンブラプログラムの説明及びプログラムを読んで、設問1〜3に答えよ。
〔プログラム1の説明〕
連続する16語に格納した16×16ドットの白黒の図形を、時計回りに90度回転する副プログラムROTATEである。図形の回転の実行例を図1に示す。このとき、1ドットを1ビットで表し、白は0、黒は1が格納されている。
(1) 図形を表す16語の先頭アドレスはGR1に設定されて、主プログラムから渡される。
(2) 回転した結果の図形を格納する領域の先頭アドレスはGR2に設定されて、主プログラムから渡される。
(3) 元の図形と回転した図形は、異なる領域に格納される。
(4) 副プログラムから戻るとき、汎用レジスタGR1〜GR7の内容は元に戻す。
設問1：
問題文を見る プログラム1中のに入れる正しい答えを、解答群の中から選べ。
解答群
ア：LAD GR1,-1,GR1
イ：LAD GR1,1,GR1
ウ：LAD GR2,-1,GR2
エ：LAD GR2,1,GR2
オ：LAD GR5,-1,GR5
カ：LAD GR5,1,GR5
模範解答
a：カ、b：イ
解説
解答の導き方
この問題では、元の図形と回転後の図形を、それぞれ連続した16語に格納します。1語には16ビットがあり、図形の1行分を表します。空欄には、処理中の元データと結果データのアドレスを、次の処理対象へ進める命令が入ります。
まず、プログラムがどのレジスタを何に使っているかを確認します。レジスタとは、処理中の値を一時的に置いておく場所です。
- GR1：元の図形のうち、現在処理している語のアドレス
- GR2：回転後の図形の先頭アドレス
- GR5：結果の領域のうち、現在処理している語のアドレス
プログラムの冒頭では、GR3に16を設定しています。外側のループでは、元の図形の16語を1語ずつ処理します。
外側のループの先頭では、次の処理をしています。
- GR4に16を設定する
- GR5にGR2を設定する
- GR6に、GR1が指す語の内容を読み込む
ここで、GR5を毎回GR2に戻していることが重要です。1つの元データを処理する間に、結果の領域の16語を順番に処理するためです。
内側のループでは、GR5が指す結果の語をGR7に読み込み、右に1ビットずらします。また、元データをGR6に読み込んで左に1ビットずらします。左にずらしたとき、元データの最上位ビットが外に出ると、オーバフロー（計算などで扱える範囲から値がはみ出したことを示す状態）が発生します。JOVは、その状態かどうかを調べる命令です。オーバフローがあれば、GR7の最上位ビットを1にし、結果の語として格納します。
処理した結果の語を格納した後は、次の結果の語へ進まなければなりません。GR5は、結果の領域の先頭アドレスであるGR2から始まり、内側のループを1回行うごとに次の語へ進みます。
LAD GR5,1,GR5
LADは、指定したアドレスを計算してレジスタに設定する命令です。この命令では、GR5を1増やします。内側のループで結果の領域を順番にたどる必要があるので、aにはカが入ります。
内側のループを16回行うと、現在の元データ1語に対応する結果の領域16語を処理し終えます。次は元の図形の次の語を処理するため、GR1を1増やします。
LAD GR1,1,GR1
この処理は内側のループが終わった後に行います。GR1は元の図形の語を順番に指すアドレスだからです。したがって、bにはイが入ります。
GR2は結果の領域の先頭アドレスとして保ち、外側のループのたびにGR5をGR2に戻しています。このため、GR2ではなく、実際に結果の領域をたどるGR5を内側のループで進めます。
誤りやすいポイント
- GR2を増やすと考えてしまうことがあります。GR2は結果の領域の先頭アドレスとして使い続けます。処理位置を進めるのはGR5です。
- GR1を内側のループで増やすと考えてしまうことがあります。内側のループでは、1つの元データに対して結果の領域の16語を処理します。元データの次の語へ進むのは、内側のループが終わった後です。
- GR5は外側のループの先頭でGR2に戻されます。したがって、内側のループが終わってGR5が結果の領域の末尾側を指していても、次の外側のループでは先頭から処理できます。
FAQ
Q: GR5は、内側のループでどのように変化しますか？
A: 最初は結果の領域の先頭を指します。結果の語を処理して格納するたびに1増え、16語を順番に処理します。
A: 最初は結果の領域の先頭を指します。結果の語を処理して格納するたびに1増え、16語を順番に処理します。
Q: なぜGR1を増やすのは、内側のループの後なのですか？
A: 1つの元データを読み込んだ後、そのデータを使って結果の領域の16語を処理するためです。16語の処理が済んでから、元の図形の次の語へ進みます。
A: 1つの元データを読み込んだ後、そのデータを使って結果の領域の16語を処理するためです。16語の処理が済んでから、元の図形の次の語へ進みます。
Q: JOVは何を調べていますか？
A: 直前のシフトでオーバフローが発生したかを調べています。元データから最上位ビットが押し出されたとき、そのビットを結果の語に反映します。
A: 直前のシフトでオーバフローが発生したかを調べています。元データから最上位ビットが押し出されたとき、そのビットを結果の語に反映します。
関連キーワード: アセンブリ言語、汎用レジスタ、アドレス計算、シフト演算、オーバフロー、ループ制御
設問2：
問題文を見る 行番号9を次のとおりに変更し、図1の回転前を元の図形として実行した。実行結果の図形として正しい答えを、解答群の中から選べ。
SRL GR6,1
解答群
模範解答
ウ
解説
解答の導き方
この設問では、行番号9の命令を「SLL GR6,1」から「SRL GR6,1」に変えたとき、図形がどう変わるかを考えます。
まず、図形の1行は1語で表されています。ビット15が左端、ビット0が右端です。また、白は0、黒は1です。
プログラムは、元の図形の1行分をGR6に読み込み、16個のビットを順に調べます。そのたびに、結果の領域にある対応する語を更新します。シフト命令で外へ押し出されたビットが1なら、JOVでONに進み、ORで結果の語のビット15を1にします。つまり、元の図形の黒いドットを結果にも反映します。
ここで、行番号9の変更が重要です。
- 変更前の「SLL GR6,1」は、GR6のビット15から順に外へ押し出します。
- 変更後の「SRL GR6,1」は、GR6のビット0から順に外へ押し出します。
ビット15は元の図形の左端、ビット0は右端です。結果の語を格納する位置は順番に進むため、変更後は元の図形の右端から左端へ読み取った順に、結果の行が作られます。
そのため、通常の回転結果と比べると、結果の行の並びが上下逆になります。図1の通常の回転結果を行のまとまりごとに逆順にすると、次のようになります。
この並びは解答群のウと一致します。
誤りやすいポイント
- 「SRL GR6,1」に変えると、元の図形を読む順番が逆になります。ビット15から読むのではなく、ビット0から読みます。
- 変わるのは結果の行の並びです。結果の各行のビットの並びまで左右逆になるわけではありません。
- 「黒は1、白は0」です。ORでビット15を1にする処理は、黒いドットを結果に記録するためのものです。
FAQ
Q: SRLは何をする命令ですか？
A: 論理シフト命令の一つです。ここでは、ビットを右へずらし、右端のビットを外へ出します。その外へ出たビットが1かどうかを、後続のJOVで判定します。
A: 論理シフト命令の一つです。ここでは、ビットを右へずらし、右端のビットを外へ出します。その外へ出たビットが1かどうかを、後続のJOVで判定します。
Q: なぜ結果の行が上下逆になるのですか？
A: 元の図形の各列を調べた順に、結果の行が順番に作られるためです。読み取る方向を右端から左端に変えると、結果の行も逆順になります。
A: 元の図形の各列を調べた順に、結果の行が順番に作られるためです。読み取る方向を右端から左端に変えると、結果の行も逆順になります。
Q: ビット15を1にするのはなぜですか？
A: 結果の語に、元の図形から取り出した1ビット分を加えるためです。黒いドットは1なので、取り出したビットが1なら、ORでビット15を1にします。
A: 結果の語に、元の図形から取り出した1ビット分を加えるためです。黒いドットは1なので、取り出したビットが1なら、ORでビット15を1にします。
関連キーワード: 論理シフト、オーバフローフラグ、ビット演算、ビットマップ、配列走査
設問3：
問題文を見る プログラム1中の行番号3、4をプログラム2に置き換えて、16×16ドットの図形のうち左上のn×nドットの部分だけを時計回りに90度回転するプログラムとした。左上の8×8ドットの部分だけを回転した実行例を図2に示す。
値n（1 ≦ n ≦ 16）はGR3に設定されて主プログラムから渡される。
置換え後のプログラムは、まず、回転の対象とならないドット（元の図形の上n語の右(16−n)ビットと下(16−n)語の全ビット）を結果の領域の適切な場所に複写する。その後、左上のn×nドットの部分を回転して結果の領域に格納する。
プログラム2中のに入れる正しい答えを、解答群の中から選べ。
cに関する解答群
ア：SLL GR0,-1,GR3
イ：SLL GR0,0,GR3
ウ：SRL GR0,-1,GR3
エ：SRL GR0,0,GR3
dに関する解答群
ア：JMI LOOP1
イ：JNZ LOOP1
ウ：JPL LOOP1
エ：JZE LOOP1
模範解答
c：イ、d：ア
解説
解答の導き方
この設問では、回転しない部分を先に結果の領域へ移し、その後で左上の ドットを回転します。空欄 c は、回転しない部分を一時的にどの位置へ移すか、d は、その複写を何回行うかを決める命令です。
まず c を考えます。問題文では、値 はGR3に設定されるとあります。また、SHIFTの処理では、元の図形の1語をGR0に読み込んでから、c の命令を実行しています。
SLLは論理左シフト（ビット列を左へずらし、空いた位置に0を入れる処理）です。GR0の内容を ビット左へずらすには、ずらす量が となる命令を選びます。そのため、c は SLL GR0,0,GR3 です。
なぜ左へずらすのでしょうか。回転対象は各語の左側にある ビットで、回転しない部分は右側の ビットです。左へ ビットずらすと、回転対象のビットは左端から押し出され、回転しない部分は一時的に語の左側へ移ります。その後の回転処理で結果の語を右へずらしながら回転後のビットを入れると、一時的に移した部分が右側へ戻り、回転しない部分を元の位置に残せます。
次に d を考えます。GR7には、最初に が設定されています。これは、回転対象の下にある語の数です。COPYでは、GR7を1減らしてから分岐を判定し、分岐しなければ元の図形の1語を結果の領域へ複写します。
たとえば、 の場合は、GR7が次のように変化します。
このように、GR7が負になったときにLOOP1へ進めば、下の 語をちょうど複写できます。負かどうかを判定する命令はJMIなので、d は JMI LOOP1 です。
誤りやすいポイント
- SLLとSRLの向きを取り違えないようにします。SLLは左、SRLは右へビットをずらします。この箇所では回転しない部分を一時的に左側へ移すため、SLLを使います。
- GR3には が入っています。SLL GR0,0,GR3では、ずらす量が となるため、 ビットのシフトになります。
- GR7はSUBAの後に判定します。 が0になった時点ではまだ複写し、次に負になった時点で終了します。JZEでは、GR7が0になった時点で終了してしまい、最後の1語を複写できません。
- の場合、複写する語数は です。最初のSUBAでGR7が負になるので、JMIによって複写を行わず回転処理へ進めます。
FAQ
Q: JNZ LOOP1ではいけないのですか？
A: JNZは、GR7が0以外なら分岐します。たとえばGR7が2から1になった時点で分岐してしまい、複写を続けられません。必要なのは、GR7が負になったときだけ分岐するJMIです。
A: JNZは、GR7が0以外なら分岐します。たとえばGR7が2から1になった時点で分岐してしまい、複写を続けられません。必要なのは、GR7が負になったときだけ分岐するJMIです。
Q: なぜ回転しない部分を先にシフトしておくのですか？
A: 回転処理では、結果の語を右へずらしながら回転後のビットを入れていきます。回転しない部分を先に左へ移しておけば、その右シフトによって元の位置へ戻せます。
A: 回転処理では、結果の語を右へずらしながら回転後のビットを入れていきます。回転しない部分を先に左へ移しておけば、その右シフトによって元の位置へ戻せます。
Q: のときも同じ処理でよいのですか？
A: はい。回転しない語は 語なので、COPYでは複写せず、すぐに回転処理へ進みます。
A: はい。回転しない語は 語なので、COPYでは複写せず、すぐに回転処理へ進みます。
関連キーワード: 論理シフト、ビット演算、インデックス修飾、条件分岐、ループ制御
