基本情報技術者 2017年 秋期 午後 問12

解答の導き方

誤りやすいポイント

• aでは、ANDで候補部分を取り出す処理と、βとの一致を判定する処理を区別します。ANDは候補部分を抜き出すためにすでに13行目で使われています。一致判定には、違いがあると1になるXORを使います。
• βの長さが$n$ビットでも、GR2の残りのビットは0です。そのため、候補側もマスクで不要なビットを0にしてから比べます。
• bのJOVが判断するのは、直前のGR5の左シフトで外へ出たビットです。GR4の左シフトで出たビットではありません。
• JMIは負かどうかを調べる命令、JOVはオーバフローフラグが立っているかを調べる命令です。役割を混同しないようにします。

FAQ

解答の導き方

• 「LD GR6,=#FFFF」で、GR6を16個の1で埋めます。
• 行番号5の「SRL GR6,0,GR3」で、GR3に入っている$n$だけ右へ論理シフトします。SRL（Shift Right Logical：空いた左側を0で埋める右シフト）なので、左側に$n$個の0ができます。
• 行番号6の「XOR GR6,=#FFFF」で、全ビットを反転します。XOR（Exclusive OR：排他的論理和）は、相手が1のビットを反転させる演算です。

• シフト前：1111111111111111
• 右へ5ビットシフトした後：0000011111111111
• 全ビットを反転した後：1111100000000000

誤りやすいポイント

• SRAとSRLを取り違えないようにします。SRAは左端のビットを補い、SRLは左側を0で埋めます。今回は左端の1を増やす必要があるため、SRAを使います。
• GR3には$n$が入っているため、シフト数を$n$にすると1が$n+1$個になります。必要なシフト数は$n-1$です。
• 「=#8000」は1個だけ1のビット列です。最初からマスクが完成しているのではなく、算術シフトで必要な数の1を増やします。

FAQ

解答の導き方

1. BSRHから一致位置を受け取ります
   プログラム2では、BSRHを呼び出した後の「LD GR2,GR0」で、検索結果の位置をGR2に移しています。BSRHは、一致位置をGR0に返し、一致しない場合は−1を返します。
   次の「JMI FIN」は、GR2が負の値なら置換処理を行わずに終了する命令です。したがって、この先では一致した場合を考えます。以降、GR2には一致位置$p$が入っています。
2. 一致位置がどの語にあるかを調べます
   GR3には長さ$n$が入っていますが、10行目で16に置き換え、11行目でGR2を引いています。その結果、GR3には「16 − $p$」が入ります。これは、ビット位置$p$から1語目の末尾までに残っているビット数です。
   この値と長さ$n$を比べることで、一致部分の位置を次のように判定しています。

   判定	一致部分の場所
   $p<16$かつ$16-p<n$	1語目と2語目にまたがる
   $p<16$かつ$16-p\ge n$	1語目だけにある
   $p\ge 16$	2語目だけにある

   2語目だけにある場合は、GR3の値「16 − $p$」が0以下になります。そのため、12行目と13行目からONL2へ進みます。
3. cで、2語目の中での位置を計算します
   ONL2に進んだとき、GR2には$p$、GR3には「16 − $p$」が入っています。30行目の「SUBA GR2,GR3」の後、GR2を「$p-16$」にしたいとコメントにあります。
   そのためには、GR2をいったん0にしてからGR3を引きます。
   $0-(16-p)=p-16$
   したがって、cには「LD GR2,=0」を入れます。これにより、GR2には2語目の先頭を0としたときの一致位置が入ります。2語目の処理に移る前に、この位置を計算しているということです。
4. dで、置換するビットをγにします
   プログラムでは、最初に「GR6,=#FFFF」からマスク（処理するビット範囲を選ぶためのビット列）を作っています。GR3を$n$として右にずらした後、全ビットを反転することで、上位$n$ビットが1のマスクになります。γも左詰めで設定されるため、γのビットとマスクは同じ位置にそろっています。
   S1では、γとマスクを一致位置に合わせてずらします。その後、S2では次の処理を行います。
   • 38行目でマスクを反転します。
   • 39行目のAND（両方のビットが1のときだけ1にする演算）で、置換範囲のビットを0にし、それ以外のビットを残します。
   • 40行目で、置換範囲にγのビットを加えます。
   置換範囲をいったん0にしてからγを加える必要があります。そうすれば、γに0がある位置も、元のビットが残らず正しく0になります。ここでは、どちらかのビットが1なら1にするOR（論理和）を使います。
   したがって、dには「OR GR2,GR4」を入れます。
5. 2語にまたがる場合も同じ処理を使います
   一致部分が1語目と2語目にまたがる場合、プログラムはまず1語目を処理します。その後、γとマスクを2語目用に調整し、GR1を次の語のアドレスに進めてから2語目を処理します。
   2語目だけにある場合も、cで求めた「$p-16$」を使ってγとマスクをその語の中の位置に合わせます。どちらの場合も、S2が置換するビット範囲だけをγに置き換える仕組みです。

誤りやすいポイント

• cでGR2に16を設定すると、「16 − (16 − $p$) = $p$」となり、求めたい「$p-16$」にはなりません。GR2を0にしてからGR3を引くことで、目的の値になります。
• cの計算に使うGR3は$n$ではありません。10行目と11行目の処理後は、「16 − $p$」です。
• dをANDにすると、γのビットが0の位置で、置換範囲を0にした値がそのまま残ります。γのビットを反映するにはORが必要です。
• ORだけでは、γの0の位置に元のビットが残る可能性があります。そのため、先にマスクを反転してANDを行い、置換範囲を0にしています。

FAQ

解答の導き方

• 1語目の#FFF3：1111111111110011
• 2語目の#7FFF：0111111111111111

• 行番号6：GR6は#FFFF
• 行番号7：GR3は$n=5$なので、GR6を論理右シフトします。論理右シフトは、右にずらした分の左側を0で埋める処理です。結果は#07FFです。
• 行番号8：#FFFFとのXOR（同じ位置のビットが異なるときに1にする演算）を行い、結果は#F800です。

誤りやすいポイント

• BSRHの戻り値$p$はGR0に設定されます。プログラム2の行番号4でGR2に移されるため、以降のGR2は検索位置として使われます。
• 行番号11のGR3は$n$ではなく、$16-p$の値です。この問題では$16-14=2$です。
• 行番号19のS1ではGR4とGR6が一度右シフトされますが、行番号20～21で保存した値に戻されます。行番号23の計算には、戻された#F800を使います。
• 行番号23は右シフトではなく左シフトです。また、16ビットから左にはみ出たビットは残りません。

FAQ