アンティーク・アセンブラ~Antique Assembler

第4回 "case" の事情

この記事を読むのに必要な時間:およそ 5 分

前回は条件分岐を行うためのEFLAGSレジスタと条件分岐命令について説明しました。

しかし,プログラミングにおける重要な制御構造でありながら,単純な条件分岐では実現できないものとして,C/C++言語で言うところのswitch構文があります。

今回は,このswitch構文について,アセンブラの視点から見てみましょう。

if分岐の限界

たとえば:

変数 "x" に格納された値が0, 1, 2, 3, およびそれ以外の場合に,それぞれ異なる処理を行いたい。

という状況で,あまり手馴れていない人の実装は往々にして以下のようになります。

リスト1 if 分岐による実装

if(x == 0){ .... }
else if(x == 1){ .... }
else if(x == 2){ .... }
else if(x == 3){ .... }
else{ .... }

上記の例は,「それ以外」を除いた条件が4つなので,まだ許容範囲と言えなくもないですが,条件の数がNに増えた場合の条件判定回数は:

  • 最悪の場合なら,常にN回の条件判定
  • 値が均等に分散している場合でも,平均してN/2回の条件判定

となります(もちろん変数 "x" の傾向次第ですが)ので,条件数Nが一定以上になる場合には,上記のようなif/elseを連ねる実装は妥当とは言えません。

情報工学的に言うなら計算量がO(n)となるのはよろしくない」といったところでしょうか。

このような場合,C/C++やそれに類する言語では,switch構文を使用するのが一般的です。

switch 構文を使用することで,リスト1の実装は以下のようになります。

リスト2 switchによる実装

switch(x){
  case 0:
    ....; break;
  case 1:
    ....; break;
  case 2:
    ....; break;
  case 3:
    ....; break;
  default:
    ....; break;
}

switch構文での実装の場合,変数 xの判定に要するコスト(=処理量)は,caseの数に関わりなく一定となりますので,if/elseを連ねた実装よりも効率的な処理が可能です。

※)
詳細は後述しますが,caseで列挙される値次第では,必ずしもこの前提は成立しません。

switch の動作原理

アセンブラでswitch構文を実現するには,どのように実装したら良いでしょうか?

判定対象の値(先述した例なら「変数x」)を列挙されたcaseごとに比較していたのでは,冒頭で示したif/elseを連ねる「駄目な実装」に逆戻りですから,実現には別な手段を考える必要があります。

switch構文の振る舞いをもう少し細かく見てみると,caseに列挙されている最小値をMIN,最大値をMAXとした場合:

  • 対象値がMINなら,"case MIN" 位置へ
  • 対象値がMIN + 1なら,"case MIN + 1" 位置へ
  • 対象値がMIN + 2なら,"case MIN + 2" 位置へ
  • ....(省略)....
  • 対象値がMAX - 1なら,"case MAX - 1" 位置へ
  • 対象値がMAXなら,"case MAX" 位置へ
  • それ以外なら,"default" 位置へ

というのがswitch構文に期待される処理です。

対象値がMIN~MAXの間の処理は,「値」とそれに対する「制御遷移先」の違いこそあれ,やっている処理は同一です。

これなら:

  1. xMIN ≦ x ≦ MAX か否かを判定
  2. 成立していないなら,default位置へ制御遷移
  3. xに応じて,対応する位置へ制御遷移

という手順に単純化できます。

「値に応じて,対応する位置」へと制御遷移させる処理は,値に対応する制御遷移位置の配列を,プログラム実装時点であらかじめ作っておくことで,単なる配列参照処理に落とし込むことができます。

対象値がMIN~MAXの間で連続していない場合に,配列参照で上手く機能するのか?

という疑問が出てくるかも知れません。しかし:

caseで列挙されていない値の場合はdefault位置へ制御遷移

で良いわけですから,上記の「制御遷移位置の配列」において,case列挙されていない値に対応する要素を,defaultを指すものに設定してやれば良いのです。

著者プロフィール

藤原克則(ふじわらかつのり)

Mercurial三昧の日々が嵩じて, いつの間にやら『入門Mercurial Linux/Windows対応』を上梓。凝り性なのが災いして,年がら年中アップアップな一介の実装屋。最近は仕事の縁が元で,OpenSolarisに入れ込む毎日。

コメント

コメントの記入