数字の入出力ができるようになりました。
次は四則演算の実装を考えます。
いろいろな方法がありますが今回はスタックを用いた方法を採用します。
68系の命令体系はスタックを再現するのに有利だからです。
スタックを使った計算方法
「2＋3×4」の場合、スタックの動きは下図のようになります。
- 「2」をスタックにプッシュします
- 「3」をスタックにプッシュします
- 「4」をスタックにプッシュします
- 「4」と「3」をポップし乗算します。結果の「12」をプッシュします
- 「12」と「2」をポップし加算します。結果の「14」をプッシュします
「（2＋3）×4」の場合、スタックの動きは下図のようになります。
- 「2」をスタックにプッシュします
- 「3」をスタックにプッシュします
- 「3」と「2」をポップし加算します。結果の「5」をプッシュします
- 「4」をスタックにプッシュします
- 「4」と「5」をポップし乗算します。結果の「20」をプッシュします
演算子の優先順位をどのように実装するかはあとで考えることにして、まずはスタックの動きを実装してみることにします。
Dレジスタを数値、インデックスレジスタを仮想スタックポインタとすると、プッシュはインデックスレジスタを-2してstd 0,xしてあげれば再現できます。
ポップは今回の場合、必ず二つの数値をポップして演算後にプッシュしているので、まとめて実装することにします。
- すでに3つの数値がスタックされた初期の状態です。2バイト整数なのでインデックスレジスタのオフセットは2刻みです
- ldd 2,xで「3」をDレジスタに代入、addd 0,xでDレジスタと「4」を加算します。結果をstd 2,xでひとつ下のスタックにストアします。
- inx, inxでインデックスレジスタを現在のスタックトップに持ってきます
足し算と引き算
加減算はHD6301/3であればびっくりするほど簡単です。
ADD: ldd 2,x
addd 0,x
inx
inx
std 0,xSUB: ldd 2,x
subd 0,x
inx
inx
std 0,x上図ではストアしてからスタックポインタを+2しましたが、プリインクリメントに変更しました。
今回は行いませんが、演算後にVフラグをチェックすればオーバーフロー判定も簡単です。
掛け算
16bit × 16bitの乗算は答えが32bitになってしまうのですが、今回は答えも16bitに統一します。
ほとんどオーバーフローしてしまいますが割り切ることにします。
HD6301/3には8bit乗算命令mulがありますので、こちらを使うことにします。
上図のように8bitずつ掛け算していって32bitの答えを出します。最後に上位16bitを取り去ると16bitの答えが求められます。
本来乗算は符号のチェックをしなければならないのですが、16bitの範囲でオーバーフローしない、という条件下であれば下位16bitは自動的に符号付きの計算が成り立ちます。
MUL:
.Result .eq UR0
; B * D
ldaa 3,x ; 「B」をAレジスタに代入
ldab 1,x ; 「D」をBレジスタに代入
mul ; B * D
std <:Result ; 「B*D」を保存
; A * D
ldd 1,x ; 「D」をAレジスタに、「A」をBレジスタに同時に代入
mul ; A * D
addb <:Result ; 「A*D」の下位8bitをResultの上位8bitに加算
stab <:Result ; Resultの上位8bitを保存
; C * B
ldaa 0,x ; 「C」をAレジスタに代入
ldab 3,x ; 「B」をBレジスタに代入
mul ; C * B
addb <:Result ; 「C*B」の下位8bitをResultの上位8bitに加算
tba ; Resultの上位8bitをAレジスタに転送
ldab <:Result+1 ; Resultの下位8bitをBレジスタに転送
inx
inx
std 0,x こんな感じになりました。「A * C」は必要ないので計算そのものを行なっていません。
割り算
除算はちょっと大変です。
符号なしの割り算
13÷3（1101÷0011）を二進法の筆算で考えてみます。
方法は十進法の筆算と全く同じです。桁をずらしながら除数0011を引いていきます。
引けなければ0、引けたら1を置いていけば商0100と最後に剰余0001が求められます。
この手順を下記のように置き換えました。
A〜Dの記号は上の筆算に対応しています。
被除数の左右にあるWORKは同一のものです。
- 被除数のMSBをWORKのLSBにシフトします。その後、WORK0001から除数0011を引きます。引けないのでこの桁の商は0です。
- 被除数のMSBをWORKのLSBにシフトします。その後、WORK0011から除数0011を引きます。引けたのでこの桁の商は1です。WORKは0000になります。
- 被除数のMSBをWORKのLSBにシフトします。その後、WORK0000から除数0011を引きます。引けないのでこの桁の商は0です。
- 被除数のMSBをWORKのLSBにシフトします。その後、WORK0001から除数0011を引きます。引けないのでこの桁の商は0です。
結果、商0100（4）、剰余0001（1）が求められます。
この例では4bitなので4回繰り返しましたが、16bitであれば16回繰り返します。
あとはどのようにHD6301/3でこれを実装するかなのですが、HD6301/3はメモリを直接シフト可能なのでWORKをDレジスタとして、被除数・除数・商はメモリに割り当てればよさそうです。
被除数はシフトした後の空きビットは使用していません。
そこでインデックスレジスタを被除数に割り当て、引けるか引けないかの結果を順番に入れることで最終的にインデックスレジスタに商が入るようにしています。Dレジスタには剰余が入ります。
この方法だと操作するのはレジスタのみなのでかなり効率がいいですね。
符号なし除算ルーチン（div_uint）
これを踏まえて下記のように実装してみました。
div_uint:
.Divisor .eq UR0
.Counter .eq UR1H
ldab #16 ; Set the loop counterto 16.
stab <:Counter
ldd 0,x ; Is divisor Zero?
beq :err06 ; Yes. Zero divide error.
bpl :1 ; Set the divisor to absolute value.
coma
comb
addd #1
.1 std <:Divisor
ldd 2,x ; Set the dividend to absolute value.
bpl :2
coma ; Make 2's complement.
comb
addd #1
; // divide rutine
.2 xgdx ; Now, X = dividend
clra ; D = remainder & WORK = 0
clrb
.loop xgdx ; Shift the dividend to the left
asld
xgdx
rolb ; WORK's LSB <- dividend's MSB
rola
subd <:Divisor ; WORK - divisor
inx ; Set the quotient's LSB to 1.
bcc :3 ; Can you subtract divisor from WORK?
addd <:Divisor ; No. Undo WORK and -
dex ; - undo the quotient's LSB to 0.
.3 dec <:Counter
bne :loop
rts
.err06 ldaa #6 ; "Zero Divide"
jmp write_err_msg2,3行目はこのルーチンで使用する変数を別名設定しています。
4行目はゼロ除算のチェックです。ゼロでなければそのまま除数を絶対値に変換してメモリに保存しておきます。
13〜17行目で被除数を同じく絶対値に変換します。
19行目のxgdxでインデックスレジスタに被除数が代入されました。
20,21行目でDレジスタ（WORK）をクリアします。
22行目からがメインのループです。
22〜24行目で被除数（インデックスレジスタ）を左シフトします。xgdxで挟んでやることでインデックスレジスタでも多くの演算が可能になります。
そのままrolb, rolaを行なうと、被除数のMSBがWORK（Dレジスタ）のLSBにシフトします。
被除数のLSBが必ず0になることを覚えておいてください。
27行目でWORKから除数を引いています。
28行目はinxすることで被除数のLSBを1にセットしています。これは最終的に商のMSBになります。
29行目ではWORKから除数を引けたかどうか、キャリーフラグを見ています。
引けたら商のビットは1でいいのでそのまま32行目に進みます（上図”B”の状態）。都合よくWORKもゼロになっているはずです。
引けなかった場合は除数を足してWORKを元に戻します。さらにdexすることで被除数のLSBを0にセットします。
あとはこれを16回繰り返して終了です。
インデックスレジスタの被除数と商になり、DレジスタのWORKが剰余となりました。
符号付きの割り算
問題は符号付きの除算なのです。乗算は16bit×16bitの答えを16bitに限定することで符号の問題を回避しましたが、除算ではそうもいきません。
さらには負数の除算における剰余の求め方にはいくつかの方法がありますので、どれを採用するかで計算方法も変わってきます。
Wikipediaの剰余演算の記事によると、主な方法は以下の3つです。
- 剰余は自然数
- 7÷3 ＝ 商 2、剰余 1
- －7÷3 ＝ 商－3、剰余 2
- 7÷－3 ＝ 商－2、剰余 1
- －7÷－3 ＝ 商 3、剰余 2
- 剰余は除数の符号と同一
- 7÷3 ＝ 商 2、剰余 1
- －7÷3 ＝ 商－3、剰余 2
- 7÷－3 ＝ 商－3、剰余－2
- －7÷－3 ＝ 商 2、剰余－1
- 剰余は被除数の符号と同一
- 7÷3 ＝ 商 2、剰余 1
- －7÷3 ＝ 商－2、剰余－1
- 7÷－3 ＝ 商－2、剰余 1
- －7÷－3 ＝ 商 2、剰余－1
A.の方法はユークリッド除法といって数学的に一般的なのだそうです。
B.の方法はMathematica、R、Python、Rubyなどで採用されています。
C.の方法はC++やJAVA、GO、Swift、VBAなど多数の言語で採用されています。MSX-BASICもこの方法です。
実装するのはC.が単純に符号反転するだけなので簡単そうですが、今回はMathematicaとRに採用されているB.の方法にチャレンジしてみます。
符号なし除算ルーチンにフラグを追加する
B.の結果一覧を見ていると被除数の符号と除数の符号が一致していない時に絶対値が違っています。剰余の符号を除数に合わせるために商を1大きく（多めに割る）しなければならないわけです。そして商が変わることで剰余の値も変わってきます。
まとめると、被除数・除数ともに絶対値に変換して計算を行ない、計算結果に対して
- 商
- 被除数の符号と除数の符号が一致していないときには1足して符号反転する
- ただし、除数がゼロの場合は1は足さない
- 剰余
- 被除数の符号と除数の符号が一致していないときには除数の絶対値から剰余の絶対値を引く
- その結果を除数と同じ符号にする
- ただし、除数がゼロの場合は剰余もゼロ
商、剰余それぞれに符号フラグが必要になりそうです。
.or $80
QuoSignFlag .bs 1 ; Quotient sign flag
RemSignFlag .bs 1 ; Remainder sign flag
Divisor .bs 2
div_uint:
.Counter .eq UR0H
ldd 0,x ; Is divisor Zero?
beq :err06 ; Yes. Zero divide error.
clrb
stab <QuoSignFlag ; Clear the quotient sign flag.
stab <RemSignFlag ; Clear the remainder sign flag.
ldab #16 ; Set the loop counterto 16.
stab <:Counter
; // Judgment of the sign of the remainder.
ldd 0,x ; Is the divisor Negative?
bpl :1 ; No. Go to next
inc <RemSignFlag ; Yes. Set the remainder sign flag.
; // Judgment of the sign of the quotient.
.1 eora 2,x ; dividend xor divisor
anda #$80
beq :2 ; Either one is negative?
inc <QuoSignFlag ; Yes. Set the quotient sign flag.
; // Set the divisor to absolute value.
.2 ldd 0,x ; Is the divisor negative?
bpl :3 ; No.
coma ; Yes. Set the divisor to absolute value.
comb
addd #1
.3 std <Divisor
; // Set the dividend to absolute value.
ldd 2,x ; Is the dividend negative?
bpl :4 ; No.
coma ; Yes. Set the dividend to absolute value.
comb
addd #1
; // divide rutine
.4 xgdx ; Now, X = dividend
clra ; D = remainder & WORK = 0
clrb
.loop xgdx ; Shift the dividend to the left
asld
xgdx
rolb ; WORK's LSB <- dividend's MSB
rola
subd <Divisor ; WORK - divisor
inx ; Set the quotient's LSB to 1.
bcc :5 ; Can you subtract divisor from WORK?
addd <Divisor ; No. Undo WORK and -
dex ; - undo the quotient's LSB to 0.
.5 dec <:Counter
bne :loop
rts
.err06 ldaa #6 ; "Zero Divide"
jmp write_err_msgこちらが符号判定を追加したルーチンです。
QuoSignFlagとRemSignFlagを追加しました。また、乗除の補正にも使用するので除数を保存しておくメモリ（Divisor）も独立して確保しました。
16〜18行目では除数の符号を調べて剰余符号フラグ（RemSignFlag）を設定します。
20〜23行目では被除数の符号と除数の符号のXORを取り、商符号フラグ（QuoSignFlag）に反映させています。
その後の処理は変更していません。
DIV: bsr div_uint
xgdx ; D <- Quotient X <- Remainder
tst <QuoSignFlag ; Is the quotient sign flag plus?
beq :end ; Yes. Return.
cpx #0 ; Is the remainder 0?
beq :sign ; Yes. Make 2's complement.
addd #1 ; No. Quotient + 1.
.sign coma ; Make 2's complement.
comb
addd #1
.end inx
inx
std 0,xこちらは商を求めるルーチンです。
div_uintを呼び出した後、xgdxでDレジスタに商が入るように入れ替えます。
3行目では符号反転が必要かどうかフラグをチェックしています。必要なければ今の値がそのまま答えになります。
5行目では剰余がゼロかどうかチェックします。ゼロであれば符号反転のみ行ないます。
ゼロ以外であれば+1した後に符号反転を行ないます。
.or $80
Remainder .bs 2
MOD: bsr div_uint
std <Remainder ; Is the remainder 0?
beq :end ; Yes. Return.
tst <QuoSignFlag ; No. Is the quotient sign flag plus?
beq :sign ; Yes. Go to judgment of the sign.
ldd <Divisor
subd <Remainder
.sign tst <RemSignFlag ; Is the remainder sign flag plus?
beq :end
coma ; No. Make 2's complement.
comb
addd #1
.end inx
inx
std 0,xこちらは剰余を求めるルーチンです。
div_uintを呼び出した後、Dレジスタの内容（剰余）をゼロページのRemainderにストアしておきます。
このストアによってゼロフラグが変化しますので、これを利用して剰余がゼロかどうかチェックします。ゼロであれば今の値（0）が答えになります。
7行目では商の符号反転フラグをチェックしています。
商の符号反転が必要ということは剰余の補正も必要になるので、9,10行目で除数の絶対値から剰余の絶対値を引いています。
11行目では剰余の符号反転が必要かどうかフラグをチェックしています。
フラグが立っていれば符号反転を行ないます。
以上でスタックを使用した四則演算は終了です。
コメント