MC6800のプログラミングテクニック(12) 多バイト整数の比較
MC6800には豊富な分岐命令があって、1バイトの数値の大小を比較するのは簡単である、という話を前に書いた。
そのときに、2バイトの比較はやや面倒であると書いたが、多バイトだとどうだろうか？
実際に chibicc の long 部分のコードを書いていて考えたことを書く。
比較方法は２種類。上位桁から順次比較するか、引き算して判断するか
上位桁からの比較は人間がやっている方法である。5桁の数値なら、万の位、千の位、百、十、一 と比較して最初に不一致になったところで判断する。
引いて比較は、 A<B を A-B < 0 に置き換えて判断する。MC6800のcmp命令、MC6809のcmpd命令はこのための命令である。
CPUが自然に扱えるサイズの整数なら、cmpなりsubなりの減算をして判断すれば良いのだが、それを超える語長になると面倒になる。
16bit数値を比較してみよう。AccABと変数varを符号ありで比較、条件を <= とすると下記のコードになる。
引き算2回、上位バイトの判断に分岐2回、下位バイトの判断にtstbと分岐が1回である。冗長に感じる。
subb var+1 sbca var blt true ; 引いた結果は <0 か? bgt false ; 引いた結果は >0 か? tstb ; 上位は等しかったので下位を見る bne false ; 等しくなければ false true: ; <0 か == なので、true
条件が < や >= なら少し簡単になる。以下、< の場合。 LT/GE は引き算した結果の符号そのものであるので、BLT命令一発である。
下8bitを見るまでもない。
subb var+1 sbca var blt true ; 引いた結果は <0 か? false:
昔のMC6800のインタプリタ・コンパイラは、どのソフトも減算して判断していた。
上から比較（引かずに判断）
Fuzix-Compiler Kit の support6800/__cclteq.s （<=）で知った方法。上のバイトから比較していく。上が不一致ならそこで判断できる。
下位バイトの判断にtstbが要らない。速くて小さい。EtchedPixels氏 さすがである。
この方法は、16bitの場合は元の数値が壊れないので便利に使える。減算結果が有効に使える場合もあるが、限定的。
__cclteq: tsx suba 2,x blt false bgt true cclow: subb 3,x blo false true:
< の場合は、プログラムサイズは減算の方が短い。
速度は上位バイトだけで判断できる場合はこちらが速い。2バイト目まで見ると遅い。
プログラミングで扱う数値は大抵小さいので、差も小さい。2バイト目まで見ることが多いはずなので、速度差は微妙である。
__cclt: tsx suba 2,x bgt true bne false subb 3,x bhi true false:
左右を入れ替えられる場合
左右を入れ替えると効率化できる場合がある。
A<=B は B>=A と同じだが、A-B<=0、B-A>=0 と考えると、後者の方が判断が楽である（結果の正負で判断できる）。
コンパイラの場合は 可能なら入れ替えて LT/GEにすると良い。
多バイトの比較
以上のことを踏まえて、多バイトの場合の処理を考えてみよう。long （4バイト）は、CC6303やFuzix C Compilerでは下記のようになっている。
- longはゼロページに上位16bit、AccABに下位16bitを持つ
- この形式だと演算時に、AccABを退避・復帰する処理が発生することがある
- AccABから何かを引く処理は簡単だが、逆は難しい
- なので、引かずに上位から順次比較・判断する方が良い
zu2/chibicc-6800-v1: A Small C Compiler for MC6800 (fork from chibicc) を作る時は、別の方法にしてみた。やってみて不具合があったら反省する。
- longはゼロページに32bit全体を置く。AccABは空ける
- 処理はやや多くなるが、AccABの退避・復帰が不要になるので意外に差はでない
- 比較の際に、左右を入れ替えるのが簡単。従って全ての判断を LT/GE で統一できる
左右を入れ替えるのが楽なのは、コンパイラ作成を楽にする。しばらくこの方法で試してみたい。
実際のコードは以下のようになっている。subtl/sublt は4バイト引き算ルーチン。lt/gr/le/ge の判断が全て1命令（blt/bge）でできるのは嬉しいし、コードも読みやすい。
__lt32s: bsr __subtl ; TOS - @long blt __true bra __false __gt32s: bsr __sublt ; @long - TOS blt __true bra __false