2018年03月14日

(H29A-FE-PM12)平成29年秋基本情報午後(問12)ソフトウェア開発(アセンブラ)


目次・平成29年秋基本情報の解答解説

公式サイト
午後問題PDF
午後解答PDF

問1は必須問題。全員が解答する。
問2〜問7は選択問題、6問中4問を選択して解答する。
問9〜問13は選択問題、5問中1問を選択して解答する。

問12:ソフトウェア開発(アセンブラ):ビット列の検索・置換

それほど複雑なロジックを使っているわけではないが、効率的な解き方が思いつかない。二つのプログラムを最初から最後まで読まなければならないので面倒な部分はある。時間はかかるが、右寄せ左寄せを間違えなければ十分満点の取れる問題と思う。

難易度:普通


設問1)a.

下記のように行ごとのコードの意味を考える。

aは14行目で、ある演算を行い一致がある場合にゼロとなってFOUNDへ分岐するということが15行目の注釈からわかっている。検索するビット列βはGR2にある。また検索されるビット列のうちビット列βと同じ長さ分のビットをマスクしたものがGR7にある。同じときにゼロにするのだから、GR2 XOR GR7や、GR2 - GR7 のような演算が考えられる。選択肢にあるオ「XOR GR7,GR2」が適当。

    b.

またbの20行目は、19行目の論理左シフトの結果で分岐を行う。その条件が成立しなかった場合にはループ先頭LPに分岐するが、成立した場合にはNEXTに分岐する。18,19および22行目で行っているのはコメントにあるとおり「αを1ビット左シフト」。18行目はαの上位語を1ビット左シフト、19行目はαの下位語を1ビット左シフト、そして22行目はαの上位語の末尾の1ビットに1をセットする処理。であれば、このNEXTに来るのは19行目のα下位語の最上位ビットが1であった場合で、すなわちSLLで最上位ビットが1の場合にオーバーフローフラグがセットされる。よって、OVが1の時にNEXTに分岐する命令が入る。これはエ「JOV NEXT」

29秋FE-PM12A.png

《プログラム1》
【レジスタの使い方:入力】
GR1……αが格納されている領域の先頭アドレス
GR2……β
GR3……βの長さn(1≦n≦16)

【レジスタの使い方:出力】
GR0……最初に一致する部分ビット列の先頭のビット位置p、一致がなければ-1を
αの先頭はビット位置0

【レジスタの使い方:作業用】
GR6……ビットマスク
GR4……αの上位16ビット
GR5……αの下位16ビット
GR1……ループカウンタ

【コードの説明(行ごと)】
01) 開始
02) レジスタ退避
03) GR0←-1(一致しなかったときの返値を準備)
04) GR6←#FFFF
05) 論理右シフト(例えばn=4の場合)
 1111_1111_1111_1111 → 0000_1111_1111_1111
06) ビット反転 (例えばn=4の場合)
 1111_0000_0000_0000
07) GR4……αの上位16ビット
08) GR5……αの下位16ビット
09) GR1←32
10) GR1←32 - n:繰り返し回数
11) GR3←32 - n

LP:
12) GR7←GR4(αの上位16ビット)
13) GR7の上位 n ビットのみを残す。
14) GR7とGR2(β)を比較して一致なら0になる。★(a)オ XOR GR7,GR2
15) 一致ならFOUNDへ
16) GR1 - 1
17) マイナスなら一致なしで終了
18) αの上位16ビットを1ビット左シフト
19) αの下位16ビットを1ビット左シフト
20) オーバーフローがあればNEXTへ。★(b) エ JOV NEXT
21) LPヘ
22) GR4αへ下位16ビットの最上位ビットをセット
23) LPへ

FOUND:
24) GR3 - GR1(p)
25) GR0←GR3(p)

FIN:
26) レジスタ復帰
27) 戻る
28) 終了


設問2)

行番号4〜6では、

4) LD GR6,=#FFFF
5) SRL GR6,0,GR3
6) XOR GR6,=#FFFF

上位 n ビット1、それ以下のビットを0にする処理。

最上位ビットだけが1の#8000をセットしたあと、n - 1ビット右論理シフトすると、上位 n ビットだけが 1 だけになる。GR3に n が入っている。

A) LD GR6,=#8000
B) SRA GR6,-1,GR3


設問3)c.

29秋FE-PM12B.png


ONL1は「一致する部分ビット列が1語目だけのとき」なので、ONL2は一致する部分ビット列が2語目だけのときの処理である。S1を呼ぶときに下記レジスタの設定を行う。
GR1にαの1語目ないし2語目
GR2にその語の何ビット目から置き換えるか。
GR4にγ
GR6にビットマスク
コメントでは、「GR2 ← p - 16」とあるが、13行目から分岐してきた場合にはGR3に「16 - p」が入っている(11行目のコメントから)。「SUBA GR2,GR3」で、GR2に「p - 16」が入るためには、GR2には0が入っている必要がある。よって29行目の c は、GR2を0にするような処理。cの解答群からイ「LD GR2,=0」のみ。

    d.

37行目で操作対象語を取り出し、41行目で置き換え後の語を書き戻している。
38行目は 1 と 0 のXORは 1 、1と1のXORは0であるからマスクを反転している。すなわちここまで置き換え対象ビット範囲が 1 で、それ以外がすべて 0 であったのがその逆、置き換え対象ビット範囲が 0 で、それ以外が1になる。

そして39行目で、GR2とGR6のANDを取ることで置き換え対象ビットが0でそれ以外は置き換え前のビットとなった。置き換え対象ビット列はGR4にあるのでGR2とGR4の論理和を取ることで、目的の語が出来る。


《プログラム2》
【レジスタの使い方:入力】
GR1……αが格納されている領域の先頭アドレス
GR2……β
GR3……βの長さn(1≦n≦16)
GR4……γ

【レジスタの使い方:作業用】
GR0……(BSRH出力)最初に一致する部分ビット列の先頭のビット位置p、一致がなければ-1。αの先頭はビット位置0
GR2……最初に一致する部分ビット列の先頭のビット位置p
  サブルーチンS2ではビット列置換の作業用
GR3……16 - p
GR5……γの退避用
GR6……ビットマスク
GR7……ビットマスク退避用


【コードの説明(行ごと)】
01) 開始
02) レジスタ退避
03) BSRH呼出
04) GR2←GR0(ビット位置pをGR2へ)
05) マイナスなら(一致がなければ)終了
06) GR6←#FFFF
07) 論理右シフト 1111_1111_1111_1111 → 0000_1111_1111_1111
08) ビット反転 1111_0000_0000_0000
09) GR7←GR3(ビット列の長さ n )
10) GR3←16
11) GR3←16 - p
12) p > 16 すなわち一致する部分ビット列が2語目の場合にはONL2へ
13) p = 16 同上
14) GR3(16 - p ) : GR7 (n) 
15) GR3 < GR7 ビット列が2語にまたがる場合は、NEXTへ
16) 一致する部分ビット列が1語目だけならONL1へ

NEXT:(2語にまたがる場合の置き換え処理)
17) GR5←GR4 γを退避
18) GR7←GR6 マスクを退避
19) S1(1語目の処理)
20) GR4←GR5 γを復帰
21) GR6←GR7 マスクを復帰
22) GR4(γ)をGR3(16 - p)ビットだけ左論理シフト。
23) GR6(マスク)をGR3(16 - p)ビットだけ左論理シフト
24) GR1←GR1+1 α+1のアドレスを示す
25) S2(2語目の処理)
26) FIN 終了へ

ONL1:(1語目だけのとき)
27) S1 (1語目の処理)
28) FIN 終了へ

ONL2:
29) GR2 ← 0 ★c LD GR2,=0 イ
30) GR2 ← GR2 - GR3 /GR2←p - 16とコメントあり。ここでG3(16 - p)
31) GR1←GR1+1 α+1のアドレスを示す
32) S2 (2語目の処理)

FIN:
33) 終了

S1:
35) GR4(γ)をGR2(p)ビットだけ右論理シフト。
 置き換え文字γを置き換え先の先頭位置まで移動させる。
36) GR6(マスク)をGR2(p)ビットだけ右論理シフト

S2:
37) GR2←(GR1) αの操作対象語を読み出す
38) GR6(マスク)を反転
39) GR2のマスク部分(置き換え対象ビット部分)を0にする。
40) GR2とGR4を組み合わせる。★d OR GR2,GR4 →イ
41) (GR1)←GR2 GR2の内容をαへ書き戻す
42) リターン

設問4)

下記の場合を考える。

α:#FFF3(1111_1111_1111_0011)
  #7FFF(0111_1111_1111_1111)
β:(11011)2
n:5
γ:(11110)2

レジスタの中身は以下。

GR1:αのアドレス
GR2:(1101_1000_0000_0000)
GR3:5
GR4:(1111_0000_0000_0000)

1111_1111_1111_0011:0111_1111_1111_1111

ここで一致するはず。よって、p=14。

以下プログラム2のステップごとにレジスタの変化を見ていく。

03) GR0 ← 14
04) GR2 ← 14
05) マイナスなら(一致がなければ)終了FINへ ×
06) GR6←#FFFF
07) 5ビット論理右シフト GR6 ← 0000_0111_1111_1111
08) ビット反転 GR6 ← 1111_1000_0000_0000
09) GR7 ← 5
10) GR3 ← 16
11) GR3 ← 16 - 14 = 2(フラグSF=0, ZF=0, OV=0,)
12) p > 16 すなわち一致する部分ビット列が2語目の場合にはONL2へ ×
13) p = 16 同上 ×
14) GR3(2) : GR7 (5) 
15) GR3 < GR7 ビット列が2語にまたがる場合は、NEXTへ ○
16) 実行せず

NEXT:(2語にまたがる場合の置き換え処理)
17) GR5 ← (1101_1000_0000_0000)< γを退避
18) GR7 ← 1111_1000_0000_0000 マスクを退避
19) S1(1語目の処理)
20) GR4 ← (1101_1000_0000_0000) γを復帰
21) GR6 ← 1111_1000_0000_0000 マスクを復帰
22) GR4(γ)をGR3(2)ビットだけ左論理シフト。
GR4 ← (0110_0000_0000_0000)
23) GR6(マスク)をGR3(2)ビットだけ左論理シフト
GR6 ← (1110_0000_0000_0000)

よって #E000





posted by eienlearner at 01:18| 大阪 | Comment(0) | 情報処理技術者試験 | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。
※ブログオーナーが承認したコメントのみ表示されます。
×

この広告は180日以上新しい記事の投稿がないブログに表示されております。