Mae向きなブログ

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

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

平成21年度秋季 基本情報技術者試験(FE)の午後問題12(アセンブラ言語CASL)は、

  • ビット列Aの特定のビット位置(p+1)からのqビットをビット列Bのqビットに置き換える副プログラムREPLACE

に関する問題でした。

ポイント

  • 空欄aに関する「AND GR2,=#000F」が55を16で割った余りであること
  • 12〜17行目の間にシフト命令が何個も出てきますが、12行目のSRAでは、符号ビットが1の場合、シフトによってできたスペースには1が入ること

に注意をする必要があると思います。

プログラム例

設問1の値でシミュレーションできるようにプログラムを作成してみました。ビット列Aは6語とも#FFFFが格納されています。

実行結果

作成したプログラムを「CASLシミュレータ(CASL II 対応)」で実行してみました。#000B番地からのビット列Aのうち第4,5語目がビット列Bによって置換えられています。

f:id:rahaema:20181210183105p:plain

平成21年度春季基本情報午後問12

平成21年度春季 基本情報技術者試験(FE)の午後問題12(アセンブラ言語CASL)は、

  • 32ビットの乗算

に関する問題でした。

2009h21h_fe_pm_qs.pdf

設問1

空欄a

ポイントは、SRL命令を実行したとき、

  • OFにはレジスタから最後に送り出されたビットの値が設定される
  • ZFが1のときは、ラベルFINの処理を行う

ということでしょうか。OFが1のときは、乗数の一番右側のビットが1ということなので、加算処理を行うことになります。

空欄b

空欄bの前行で、下位16ビットの加算処理が行われています。このとき、オーバフローが発生した場合には、上位16ビットに対してけた上げの処理が必要となります(ラベルADJ1の処理)。

空欄c

被乗数(32ビット)の下位16ビットを1ビット左にシフトします。このときオーバフローが発生した場合は、被乗数(32ビット)の上位16ビットに対してけた上げ処理を行います(ラベルADJ2の処理)。

実行結果

作成したプログラムを「CASLシミュレータ(CASL II 対応)」で実行してみました。被乗数#12345678に対して、乗数2で計算してみた結果が以下です。アドレス#000B,#000C番地に2倍した値が格納されています。

f:id:rahaema:20181202131253p:plain

設問2

空欄d

空欄dの前行で、GR2に被乗数の上位16ビットが格納されているメモリのアドレスが格納されましたので、被乗数x乗数上位語の計算に向けて、GR2に乗数上位語を設定します。空欄dの次の行は、このままCALL MULSを呼び出してしまうと、せっかく計算した積(A)の結果が上書きされて無くなってしまうことを防ぐための処理です。

空欄e

空欄eの後の行では、GR6に対する加算処理に向けて準備をするのですが、積(B)の結果がラベルSVに格納されていますので、GR3を使って積(B)の下位16ビットをGR6にLDします。

実行結果

検算がしやすいように、被乗数を#12345678、乗数を#00010001として実行してみました。本来なら、#123468AC5678ですが、下位32ビットはちゃんと計算できていることがわかります。

f:id:rahaema:20181202131308p:plain

約束の海

山崎豊子の本に没頭したのは、2011年から2012年にかけて。かねてより本書には興味を持っていましたが、未完のままになっているとのことで読むことに躊躇いがあったのですが、読んでみて本当によかったと思います。

この物語を通して何を訴えたかったのか、また物語の内容もさることながら、80歳を超えてなお新しいことに挑戦し続けるその姿勢に感銘を受けました。

約束の海

約束の海

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

平成22年度秋季 基本情報技術者試験(FE)の午後問題12(アセンブラ言語CASL)は、

  • ビット列の並びを逆転させるプログラム

に関する問題でした。

設問1

ポイントは、SRL命令を実行したとき、

  • OFにはレジスタから最後に送り出されたビットの値が設定される
  • ZFが1のときは、ラベルFIN2の処理を行う

ということでしょうか。

実行結果

作成したプログラムを「CASLシミュレータ(CASL II 対応)」で実行してみました。#0005番地に格納されている値(#B3D1)が実行後は#8BCDになっています。

  • 実行前

f:id:rahaema:20181118162020p:plain

  • 実行後

f:id:rahaema:20181118162125p:plain

設問2

LOOP1は、n語の並びを逆順にする処理(第1語と第n語の入れ替え、第2語と第n-1語の入れ替え、…)、LOOP2は各語それぞれについて設問1のREVRSを使ってビットの並びを逆転させていますね。

実行結果

#0007番地から「#B3D1,#8000,#0001」を設定して実行してみました。

  • 実行前

f:id:rahaema:20181118164853p:plain

  • 実行後

f:id:rahaema:20181118164940p:plain

設問3

プログラムの中に適切なコメントが記載されているので、GR1,GR2,GR3に具体的な値を設定して紙上でビット遊びをすることが大切なんだろうなと思います。ビット列が右に左に移動して、ANDしたりORするうちに望みのビット列が得られる様子は面白いですね。

解くためには,

  • 算術シフトと論理シフトの違い
  • 「XOR GR6,=#FFFF」はビット反転

ということを知っていればよいのではないでしょうか。

実行結果

#B3D1に対して、真ん中の8ビットが逆順になるように、pを4、qを8で実行してみました。

  • 実行前

f:id:rahaema:20181118170320p:plain

  • 実行後

f:id:rahaema:20181118170329p:plain

「低レイヤを知りたい人のためのCコンパイラ作成入門」を読んで(1)

コンパイラの仕組みについては学生時代に学んだ記憶はあるのですが、当時は難易度が高く思えて、今となっては字句解析して構文解析してという程度しか理解できていません。これまで何度も学び直しをしようと思ったもののハードルが高くて何度も跳ね返されてきました。

ひょんなことで、「低レイヤを知りたい人のためのCコンパイラ作成入門」を知ったのですが、読み始めるととても分かりやすくて、面白くて、また学んでみようかなと思えてきました。読みながら、実際に手を動かして作っているのですが、このオンラインブックは執筆中ということもあり、そのままでは動かない部分がありましたので、自分なりに動くように作成してみました。

以下は、「ステップ4:四則演算のできる言語の作成」までの内容です。おかしな記述などがあれば遠慮なくご指摘いただければと思います。

9cc.c

実行結果

$ make
cc     9cc.c   -o 9cc
$ make test
./test.sh
OK

先ごろ実施された「平成30年度秋季基本情報午後問8 - Mae向きなブログ」にも四則演算を行う問題が出題されていました。今回の方法と実行結果が同じになっています。当たり前といえば当たり前なのですが、うれしいですね。

$ ./9cc 2*(34-(5+67)/8) > tmp.s
$ gcc -o tmp tmp.s
$ ./tmp
$ echo $?
50

平成30年度秋季応用情報午後問3

平成30年度秋季 応用情報技術者試験(AP)の午後問題3は、ウェーブレット木に関する問題でした。

年齢だけは重ねているので、基本情報や応用情報技術者試試験で出題される、いろいろなアルゴリズムについて詳細は知らなくても、名前だけは聞いたことがあるものが今までは出題されていたのですが、ウェーブレット木というのは初耳のような気がします。

理解を深めるために問題を解いて、プログラムを作成してみました。

プログラム(h30a_ap_pm3.rb)

実行結果

問題文中で取り上げられている、文字列Pについて、

  • ウェーブレットの構築
  • 文字の出現回数を数える

を実行してみました。図1と同じようなウェーブレット木が構築でき、文字数も数えられているようです。

$ ruby h30a_ap_pm3.rb
#<struct Node
 key=342,
 left=#<struct Node key=24, left=nil, right=nil>,
 right=#<struct Node key=17, left=nil, right=nil>>
A : 3
C : 2
G : 3
T : 2

下町ロケット ヤタガラス

あいかわらず池井戸潤氏の本は面白いですね。今回も楽しく読了できました。本の中では、準天頂衛星ヤタガラスという名で登場しますが、現実には準天頂衛星みちびきが、2018年11月1日にサービスを開始したばかりのようです。いろんな方面で有効活用してもらいたいですね。

下町ロケット ヤタガラス

下町ロケット ヤタガラス