Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

平成29年度秋季基本情報午後問12

平成29年度秋期 基本情報技術者試験(FE)の午後問題12(アセンブラ, CASL)は、連続する2語から成るビット列αの中から、別のビット列βと一致する部分ビット列を検索し、βと同じ長さの別のビット列γで置き換えるプログラムに関する問題でした。

設問1

空欄a

12 LP      LD   GR7,GR4
13         AND  GR7,GR6
14         (空欄a)
15 JZE     FOUND        ; 一致あり

12行目で、検索対象の文字列をGR7に取り込み、13行目でビット列βの長さ分GR7に取り出します。 15行目で、ZF(ゼロフラグ)が1の場合、つまり14行目の演算結果が0の場合FOUND処理にジャンプするので、GR7とビット列β(GR2)が一致すれば0、一致しなければ非0になるような演算を選ぶことになります。

空欄b

18         SLL  GR4,1   ; αを1ビット左シフト
19         SLL  GR5,1
20         (空欄b)
21         JUMP LP
22 NEXT    OR   GR4,=#0001
23         JUMP LP

18行目から23行目は2語からなるビット列αを次の検索処理のためにお膳立てをする処理です。まず、18行目で1語目を左へ1ビット論理シフトし、同様に19行目で2語目も左へ1ビット論理シフトしています。このとき、オーバフローが発生すると、1語目の最後尾に1を追加する処理が必要になりますが、その処理がNEXT部ということになります。よって、OF(オーバーフローフラグ)が1のとき、NEXTへジャンプするという処理を選ぶことになります。

設問2

4         LD   GR6,=#FFFF ; マスク作成
5         SRL  GR6,0,GR3
6         XOR  GR6,=#FFFF

GR3には、検索対象ビット列βのビット長nが格納してあります。例えば、GR3が5のとき、5行目の処理でGR6は5ビット論理右シフトするので#07FFとなり、6行目で#F800となります。

LD       GR6,=#8000

のあとに、GR6を#F800とするには、GR6を4ビット算術右シフトすればよいことになります。

設問3

空欄c

29 ONL2    (空欄c)
30         SUBA GR2,GR3   ; GR2 <- p-16
31         LAD  GR1,1,GR1 ; 操作対象を2語目にして、
32         CALL S1        ; 2語目の処理

ONL2の処理にやってくるときは、置き換え対象ビット列γが2語目にあるときです。例えば、置き換えたいビット位置の先頭が24の場合、4行目の処理でGR2が24、10行目の処理でGR3が16ですから、

11         SUBA GR3,GR2

の処理を経てGR3には16-24=-8が格納された状態で、29行目の処理に移ることになります。30行目の処理でGR2には、2語目の左から何ビット目かという値を格納するには、空欄cでGR2に0を設定しておけばよいということになります。

空欄d

35 S1      SRL GR4,0,GR2  ; γの調整
36         SRL GR6,0,GR2  ; マスクの調整
37 S2      LD  GR2,0,GR1  ; 操作対象語の取出し
38         XOR GR6,=#FFFF
39         AND GR2,GR6
40         (空欄d)
41         ST  GR2,0,GR1

置き換え対象ビット列が8ビット目から始まるとき、GR2に8が設定されていることになります。 今、

  • GR4にはγとして#A000
  • GR6に、#0FFF

とすると、35行目でGR4が#00A0となり、36行目でGR6が#00F0になります。38行目でXOR演算を行うことにより、GR6が#FF0Fとなります。GR2には、37行目の処理により置き換え前のビット列が格納されていますので、GR2=#CCCCとすると、39行目のAND演算により、GR2は#CC0Cになります。これで置き換えたいビット部分列を0に置き換えることができましたので、40行目で、γを調整したもの(GR4)をセットすればよいことになります。

設問4

β:11011は、1語目の14,15ビット目から2語目の0〜2ビット目にマッチします。23行目は2語目用マスクの調整処理であり、2語目は0〜2ビット目にマッチすることから、#E000となります。

感想

10数年ぶりに基本情報技術者試験CASLの問題を解いてみました。プログラムを読む前に自分だったらこうやって解くだろうから、こんな処理をやっている所があるはずだなどと考えてから解いてみると面白いですね。ビット遊びをしているような感覚で楽しく取り組めました。

高校生に基本情報技術者試験をクリアさせようと考えたとき、表計算, C, Javaなどの選択肢がありますが、CASLの命令語数の少なさを考えると、やはりメリットはあるのかなと思います。今年の授業でCASLを取り入れてみましたが、各命令の動作を覚えて終わりというのではなく、過去問演習ができるくらいまで取り組めるといいなと思います。