矢沢久雄 グレープシティ アドバイザリースタッフ

 今回は,ちょっと高度なプログラムを紹介します。データを並び替える「ソート(整列)」と,データを見つける「サーチ(探索)」です。C言語などの高水準言語でソートやサーチのプログラムを作ったことがあるなら,それらがアセンブラでどのように記述されるか注目してください。高水準言語で記述されたプログラムも,コンパイルしてマシン語に変換されてから実行されます。そのマシン語をニーモニックで記述したものがアセンブラです。したがって,高水準言語で記述されたプログラムであっても,最終的には,ここで示すアセンブラのプログラムと同じ仕組みで動作しているのです。

●ソートを行うプログラム

 リスト1は,「基本選択法」と呼ばれるアルゴリズムを使って,データを昇順(小さい順)に並び替えるプログラムです。並び替えられる前のデータは,ラベルDATに格納された5つの数値です。昇順の基本選択法では,前から後ろに向かってデータを比較し,小さい方を前に出すことを繰り返します。コメントを参考にしながら,プログラムの流れを追ってみてください。

リスト1●基本選択法でデータを昇順にソートするプログラム

LADGR1,0;GR1に0を格納する
LADGR2,3;GR2に3を格納する
LADGR4,4;GR4に4を代入する
LBL1LADGR3,1,GR1;GR3にGR1+1の値を格納する
LBL2LDGR5,DAT,GR1;GR5にDAT+GR1番地のデータを格納する
LDGR6,DAT,GR3;GR6にDAT+GR3番地のデータを格納する
CPAGR5,GR6;GR5とGR6を比較する
JMILBL3;GR5<GR6なら交換処理をスキップする
STGR5,DAT,GR3;データを交換する
STGR6,DAT,GR1;データを交換する
LBL3LADGR3,1,GR3;GR3の値を+1する
CPAGR3,GR4;GR3とGR4を比較する
JPLLBL4;GR3>GR4ならLBL4にジャンプする
JMPLBL2;LBL2に戻って繰り返す
LBL4LADGR1,1,GR1;GR1の値を+1する
CPAGR1,GR2;GR1とGR2を比較する
JPLLBL5;GR1>GR2ならLBL5にジャンプする
JMPLBL1;LBL1に戻って繰り返す
LBL5RET;主プログラムに戻る
DATDC2,5,1,4,3;ソートの対象となるデータ

 もしもプログラムの流れを十分に追えなかったとしても,どうか心配しないでください。皆さんは,アセンブラのプログラムの流れを追うときに「現在どの行が実行されているのか」,「個々のレジスタは何のために使われているか」,「個々のレジスタの現在の値はいくつか」,「次にどの行が実行されるのか」ということに注目したはずです。この経験をしていただければOKです。

 コンピュータは,プログラムを解釈・実行する機械です。コンピュータには,現在の状態というものがあります。現在の状態を示すのは,CPUの持つレジスタの値です。プログラムの流れに応じてレジスタの値が変化して行くのです。これが,コンピュータの生の動きというものです。

 「個々のレジスタは何のために使われているか」を見抜くことは,特に重要です。高級言語では,iやmaxといった変数を使うところを,アセンブラでは汎用レジスタGR1~6を用いるからです。リスト1では,以下の目的でレジスタが使われています。このヒントをもとに,もう一度リスト1のプログラムの流れを追うことに挑戦してみてください。

GR1・・・0~3まで変化するループカウンタ
GR2・・・3を格納しておく(GR1の終了値)
GR3・・・GR1+1~4まで変化するループカウンタ
GR4・・・4を格納しておく(GR3の終了値)
GR5・・・(DAT+GR1)番地にあるデータ
GR6・・・(DAT+GR2)番地にあるデータ

 もう1つヒントをさし上げましょう。リスト1と同じ処理を行うプログラムをC言語で記述すると,リスト2のようになります。C言語では,変数を使ってデータを格納,比較,演算しますが,アセンブラではレジスタを使うわけです。ここでは,分かりやすいように,アセンブラのレジスタと同じ名前の変数名(gr1やgr2など)を使い,わざとアセンブラ風のスタイルでC言語のプログラムを記述しています。変なプログラムだと思うかもしれませんが,ちゃんと動作します。

リスト2●アセンブラ風に記述したC言語のプログラム

int dat[] = {2,5,1,4,3};/*ソートの対象となるデータ*/
int gr1,gr2,gr3,gr4,gr5,gr6;/*変数の宣言*/
gr1 = 0;/*GR1に0を格納する*/
gr2 = 3;/*GR2に3を格納する*/
gr4 = 4;/*GR4に4を代入する*/
LBL1:gr3 = gr1 + 1;/*GR3にGR1+1の値を格納する*/
LBL2:gr5 = dat[gr1];/*GR5にDAT+GR1番地のデータを格納する*/
gr6 = dat[gr3];/*GR6にDAT+GR3番地のデータを格納する*/
if (gr5 - gr6 < 0)/*GR5とGR6を比較する*/
goto LBL3;/*GR5<GR6なら交換処理をスキップする*/
dat[gr3] = gr5;/*データを交換する*/
dat[gr1] = gr6;/*データを交換する*/
LBL3:gr3 = gr3 + 1;/*GR3の値を+1する*/
if (gr3 - gr4 > 0)/*GR3とGR4を比較する*/
goto LBL4;/*GR3>GR4ならLBL4にジャンプする*/
goto LBL2;/*LBL2に戻って繰り返す*/
LBL4:gr1 = gr1 + 1;/*GR1の値を+1する*/
if (gr1 - gr2 > 0)/*GR1とGR2を比較する*/
goto LBL5;/*GR1>GR2ならLBL5にジャンプする*/
goto LBL1;/*LBL1に戻って繰り返す*/
LBL5:return;/*主プログラムに戻る*/

●サーチを行うプログラム

 リスト3は「線形探索」というアルゴリズムを使って,データをサーチするプログラムです。サーチの対象となるデータは,ラベルDATに格納された5つです。見つけたいデータは3です。3が見つかったら“FOUND!”という文字列をディスプレイに表示し,見つからなかったら“NOT FOUND!”という文字列をディスプレイに表示します。線形探索では,前から後ろに向かって1つずつデータを取り出し,それが見つけたいデータであるかどうかを調べることを繰り返します。コメントを参考にしながら,プログラムの流れを追ってみてください。

リスト3●線形探索でデータをサーチするプログラム

LADGR1,0;GR1に0を格納する(データの先頭位置)
LADGR2,4;GR2に4を格納する(データの末尾位置)
LADGR3,3;GR3に見つけたいデータを格納する
LBL1LDGR4,DAT,GR1;GR4にデータを読み出す
CPAGR4,GR3;読み出したデータと見つけたいデータを比較する
JZELBL2;見つかったらLBL2にジャンプする
LADGR1,1,GR1;GR1を+1する
CPAGR1,GR2;GR1とGR2を比較する
JPLLBL3;GR1>GR2ならLBL3にジャンプする
JMPLBL1;LBL1に戻って繰り返す
LBL2OUTSTR1,NUM1;ディスプレイにFOUND!と表示する
RET;主プログラムに戻る
LBL3OUTSTR2,NUM2;ディスプレイにNOT FOUND!と表示する
RET;主プログラムに戻る
DATDC2,5,1,4,3;ソートの対象となるデータ
STR1DC'FOUND!';見つかったときに表示する文字列
NUM1DC6;文字列の長さ
STR2DC'NOT FOUND!';見つからなかったときに表示する文字列
NUM2DC10;文字列の長さ

図1●線形探索でデータをサーチするフロー・チャート
 プログラムの流れを図示するときに「フロー・チャート(流れ図)」がよく使われます。アセンブラのプログラムの流れもフロー・チャートで図示できます。リスト3に示したプログラムのフロー・チャートは,図1[拡大表示]のようになります。ここでも,レジスタの現在の値に注目していることが分かるでしょう。興味のある人は,ソートのプログラムのフロー・チャートも書いてみてください。

 5回にわたってアセンブラの概要と基本的なプログラミング手法を紹介してきました。皆さんに「コンピュータとプログラムの本当の姿がわかり嬉しい気分になれた」と思っていただけたなら幸いです。興味がわいてきたので,もっと詳しく勉強したいとおっしゃるなら,情報処理技術者試験の中でも登竜門と言える「基本情報技術者試験」の参考書で勉強することをお薦めします。2進数や論理演算から,プログラミング,データベース,ネットワークまで,コンピュータの基礎知識を幅広くマスターできます。試験に関する詳細は,情報処理技術者センターのWebページ(http://www.jitec.jp/)をご覧ください。

 連載をお読みいただきありがとうございました。またお会いしましょう!