MC6800で16bit整数の平方根を求める
Z80での高速な平方根処理: ＰＩＣマイコンは面白い にZ80で平方根を高速に求める記事があった。
記事で参照されているRetro Programming: A Fast Z80 Integer Square Rootにあったのは以下のようなルーチンだ。
注：Z80と挙動を合わせるために、変数をunsigned intにしています。cpu_counter()はその時点までの実行サイクルを表示する関数。
unsigned int isqrt( numb ) { unsigned int root = 0, bit = 0x4000; while ( bit != 0 ) { if ( root + bit <= numb ) { numb = numb - root - bit; root = root / 2 + bit; } else root /= 2; bit /= 4; } return root; } int main(int argc, char **argv) { unsigned int x; cpu_counter(); x = isqrt(20000); cpu_counter(); return x; }
MC6800のコンパイラで走らせて比較
ローカル変数版。6800ではスタックアクセスはインデックスレジスタ経由で行うしかなく、それが遅いです。
(-Osの方がサイズが大きいのは、余分なヘルパールーチンが付属しているから。これどうしようかな…）
| コンパイラ | 実行サイクル | バイト数 |
|---|---|---|
| CC6303 | 4313 | 1585 |
| Fuzix CC | 13440 | 715 |
| chibicc -O0 | 1336 | 569 |
| chibicc -O2 | 1333 | 566 |
| chibicc -Os | 1412 | 640 |
全てグローバル変数にしてみた。numbは関数の先頭で引数から代入するようにした。
どのコンパイラでも3割以上早くなります。
バイト数の差はアドレッシングモードの差ですね。indexedは2バイト、extendedは3バイト必要なので、少し大きくなります。
| コンパイラ | 実行サイクル | バイト数 |
|---|---|---|
| CC6303 | 2991 | 1632 |
| Fuzix CC | 9502 | 748 |
| chibicc -O0 | 1079 | 611 |
| chibicc -O2 | 1076 | 608 |
| chibicc -Os | 1155 | 686 |
Z80版に負けている
Retro Programming: A Fast Z80 Integer Square Rootでは、上記のCのアルゴリズムを使ったZ80用のルーチンがあります。そちらは 1005-1101 cycles とのことです。
サイクル数はほぼ同じですが、1980年ごろはZ80は4MHzクロック、MC6800は2MHzなので、実行速度では倍の差が付きます。
MC6800系の最新であるMC68HC11なら4MHzで動くし 命令に必要なクロック数も減っているのですが、それを言ったらZ80後継には33MHz版なんかもあるわけで。
ということで、アセンブラでどれぐらい早くなるか書いてみました。
chibiccでグローバル変数版をコンパイルして、出力されたコードに手を入れています。
これで728cyc, 632bytesです。だいたい7割程度のサイクル数。実行時間はZ80比1.5倍ぐらいでしょうか。遅い。
.setcpu 6800 .zp .export _numb _numb: .ds 2 .export _bit _bit: .ds 2 .export _root _root: .ds 2 ; .code .export _isqrt _isqrt: stab _numb+1 staa _numb ldx #0 stx _root ldab #<16384 ldaa #>16384 stab _bit+1 staa _bit bra L_begin_5 L_begin_4: lsr _root ror _root+1 addb _bit+1 adca _bit L_begin_5: subb _numb+1 sbca _numb bhi L_end_5 bcs L_thru_6 tstb bne L_end_5 L_thru_6: nega negb sbca #0 stab _numb+1 staa _numb ldab _root+1 ldaa _root addb _bit+1 adca _bit stab _root+1 staa _root lsr _bit ror _bit+1 lsr _bit ror _bit+1 ldx _bit bne L_begin_4 rts L_end_5: ldab _bit+1 ldaa _bit lsra rorb lsra rorb stab _bit+1 staa _bit ldab _root+1 ldaa _root ldx _bit bne L_begin_4 L_return_2: rts
考察
レジスタが少ないのが痛いです。Z80版は計算に使っている変数 root,bit,numb が全てレジスタに乗っているので速い。6800版ではいちいちメモリに書き戻す必要があります。
MC6800では16bit演算ができないのも痛いです。
また、以下の部分は、numb-root-bit が共通項として括り出せそうですが、比較演算のフラグを立てるには numb – (root+bit) としなければいけないので、一手間かかります。
MC6800アセンブラ版は(root+bit)-numb で比較を行って、そのあと2の補数をとってnumbを求めています。2の補数を取るのに6cycも かかります。
Z80版は減算の直前に ex de,hl を行って減数と被減数を入れ替えて対応していて、これは羨ましい限りです。
MC6809なら LDD root / ADDD bit / PSHD / LDD numb / SUBD ,S++ なのですが、それでもオーバーヘッドはあります。
if ( root + bit <= numb ) { numb = numb - root - bit;
以下の演算はLSR/ROR命令を使ってメモリ上だけでシフトできるのですが、MC6800のメモリシフト命令は遅いんですよね。0ページであっても6cyc必要です（合計24cyc）。
AccA,Bのシフトは1つ2cycなので、bit /=4 の部分は、lda/sta命令を入れてもAcc演算の方が速いです（22cyc）。
else root /= 2; bit /= 4;