MC6800のプログラミングテクニック(29) ループ処理(3)

前回までstrcmp,strchrの例を見てきた。今回はmemchrの話。

str系の関数は文字列末 ‘\0’ を検出するが、mem系関数では領域のサイズを渡す。

そのため、2バイト演算が下手なMC6800ではループ終了検出がややこしくなる。

void *memchr(void *s,int c,size_t n)
{
  while (n--) {
    if (*(unsigned char *)s == (unsigned char)c) {
      return s;
    }
    s++;
  }
  return NULL;
}

アセンブラで素直に書いてみる

探したい文字はAccBに入っているものとする。わかりやすさを優先して、サイズチェックにもIXレジスタを使ってみよう。

n,s はゼロページにあるとする。インデックスアクセスだとstxできないので、スタック以外に置く必要がある。

ループ内は 4+5+4+4+4+5+4+5+4 = 41cyc である。IXをポインタとカウンタに使っていて、切り替えるのに9cycずつ かかるのが遅い原因。

6809や68HC11/12ならIYレジスタが使えるので 楽だけど、MC6800ではどうしようもない。

古代の人々は割り込み禁止にしてSPを使うという荒技を使っていたけど、さすがに現代で使うのは 憚(はばか)られる。

  bra start
loop:
  inx
  stx s
start:
  ldx n
  beq end
  dex
  stx n
  ldx s
  cmpb 0,x
  bne loop
found:
  ldab s+1
  ldaa s
  rts
end:
  clrb
  clra
  rts

IXレジスタはポインタに専念させる

IXを2つの用途に使っていて、切り替えだけで合計18cycも使っているのは いかにも遅い。

AccAが空いているので、0チェックにはAccAを使ってみよう。endに来る時点でAccAは0なので、clraは省略できる。

ループ内は 4+3+4+3+4+6+6+5+4 で 39cyc である。苦労した割に減っていない。

n– の処理のために dec の拡張アドレッシングを使っているのも遅い原因。decやincにはゼロページアクセスが無いので仕方がない。

  ldx s
  dex
loop:
  inx
start:
  ldaa n+1
  bne skip
  oraa n
  beq end
  dec n
skip:
  dec n+1
  cmpb 0,x
  bne loop
found:
  ldab s+1
  ldaa s
  rts
end:
  clrb
; clra
  rts

律儀に2バイト単位で減らさなくても良いのでは？

n– は ほとんどの場合下位バイトだけ減っていて、桁下がりが発生するときだけ上位バイトを減らす。

上位バイトが減るタイミングで 0チェックをすれば速くなるはずだ。

ただし　decでは0になったことは検出できるが、桁下がりは検出できない（Cが変わらないから）。

あらかじめ1を足しておいて、チェックのタイミングを変えてやる。Cで書くと:

  n++;
  while (--n) {
    :
  }

演算はバイト単位なので要注意。下位を減らして0になったら上位を減らし、上位が0になったのを検出する必要がある。

1つずらすために$0101を足してやる。

高速化のために下位バイトはAccAに入れておこう。

ループ内の実行時間は分岐の有無によって変わる。4+2+4+(6+4 or 0)+5+4=28 or 19cycである。ずいぶん速くなった。

カウンタを減らす操作は n+1回実行されるので、nが小さいときはオーバーヘッドが気になる。

  ldaa n+1
  inca
  inc n
    :
   ldx s
　 dex
loop:
  inx
  deca
  bne skip
  dec n
  beq end
skip:
  cmpb 0,x
  bne loop
found:
    :
end:

n==0を特別扱いすれば、decのタイミングは後ろに移動できる

dec操作がn+1回実行されるのは、n==0のときもチェックが走るからだ。

n==0は最初に判断するようにすれば、1回減らせる。

  if (n==0) {
    return NULL;
  }
  do {
    :
  } while (--n);

単に$0100を足してしまうと、nの下位バイトが$00のときにおかしくなるので注意。

256回ループのつもりで、$0200にすると512回実行される。下位が$00のときは上位はそのままでないといけない。

ループ内の実行時間は同じ。decはループ回数分だけ実行される。

一見すると前処理が大きく見えるが 実際のmemchrでは共通化部分があるので、それほど大きくない。

  ldaa n+1
  oraa n
  beq end
  ldaa n+1
  beq notadd
  inc n
notadd:
  ldx s
　dex
loop:
  inx
  cmpb 0,x
  beq found
  deca
  bne loop
  dec n
  bne loop
end:
    :
found:

終了アドレスでループ末を判定

終了アドレス e=s+n をあらかじめ計算しておけば、ループカウンタは不要になる。

void *memchr(void *s,int c,size_t n)
{
  void *e = s+n;

  while (s!=e) {
    if (*s == (unsigned char)c) {
      return s;
    }
    s++;
  }
  return NULL;
}

ループ内部は 4+4+4+5+4 = 21cyc である。cpxとdecaの差だけ遅くなるが、シンプルでわかりやすい。

  ldaa s+1
  adda n+1
  staa e+1
  ldaa s
  adda n
  staa n
   :
  dex
loop:
  inx
  cpx n
  beq end
  cmpb 0,x
  bne loop
found:
    :
end: