2015年9月25日金曜日

ARMのプログラム技法

ARMには除算命令がないので, 前のブログCalの時はdivmodという簡単な除算サブルーチンを用意した. 通常はライブラリの除算ルーチンが組込まれるらしいが, 私としては除算サブルーチンを書くのが趣味の内だ.

2008年10月28日のブログに書いた「個人用電卓」の除算もそうだが, 私は剰余を除数と符号を合せる除算が好きなので, 今回も当然そういう設計にした.

400を15で割ると, 商は26, 剰余は10になる. では-15で割るときはどうするか. 商は-27, 剰余は-5とするのである. 通常割切れるときは剰余は0だが, これは正なので, 負数, 例えば-15で割ったときにはそういう剰余はでない. 剰余は-15になる.

400割る-20は商が-21, 剰余が-20とする. -21× -20=420, それに剰余が-20だから, 被除数は400というわけだ.

引き放し除算の方法はこうだ. ARMのレジスタは32ビットだが, 4ビットだと思って書いた図が下だ.

左は55割る7, 右は47割る7.



行0. 被除数が二進法で置いてある. それを左へ1ビットシフトする.
行1. 被除数と行2にある除数の符号を較べる.
行2. 符号が同じなら被除数から除数を引き, 異なれば足す.
行3〜12. 被除数を左へ1ビットシフトする.
シフトする前の被除数と除数の符号が同じなら被除数から除数を引き, 被除数の最下位に1を置く. 異なれば足す.
行13. 右のレジスタを2倍して1を足す. 左のレジスタに剰余. 右のレジスタに商がえられる. 剰余と除数の符号が異なれば, 剰余に除数を足し, 商から1を引く.

これと同じことをARMで実行したのが下のプログラムである.

プログラム0


行00 .data ここからデータ領域という指示
行02〜04 テストデータ
行05 printfの書式
行08 ここから除算サブルーチン. 被除数は上位がr1, 下位がr0, 除数がr2にある.
行08,09 r1,r0を繋げて左シフト. r0+r0をr0に置き, addsでキャリーをcpsrに 置く. adcでそのキャリーを足しながらr1+r1をr3に置く. adcsなので オーバーフローがあればセットする.
行10 被除数の左端の2ビットが01, 10だとオーバーフローが起き, bvsでジャンプ.
行11 除数と被除数の符号を較べる.
行12,13 符号が同じなら被除数から除数を引く, 異なれば足す.
行14 その加減算の前後の被除数の符号を較べる. 変っていなければオーバーフロー.
行16 カウンタr4に30をセット.
行17,18 被除数を1ビット左シフト.
行19 符号を較べる.
行20〜22 同じなら除数を引き, r0に1を足す. 異なれば足す.
行23,24 カウンタを減らす.
行25,26 補正
行27〜29 補正
行30 サブルーチンから帰る.
行31〜33 オーバーフローのとき, 除数が正なら-1, 負なら0を持って帰る.

プログラム1


これはドライバのプログラム.

クルティカルな例を実行したのがこれだ.

被除数            除数     商       剰余
3fffffff 7fffffff 7fffffff 7fffffff 7ffffffe
c0000000 80000000 7fffffff 80000000        0
c0000000 7fffffff 80000000 7fffffff ffffffff
3fffffff 80000000 80000000 80000000 80000000
Schemeで検算してみる.
(number->string
(+ (* #x7fffffff #x7fffffff) #x7ffffffe) 16)
=> 3fffffff7fffffff

(number->string
(* #x7fffffff #x-80000000) 16)
=> -3fffffff80000000 (= c000000080000000)

(number->string
(+ (* #x-80000000 #x7fffffff) -1) 16)
=> -3fffffff80000001 (= c00000007fffffff)

(number->string
(+ (* #x-80000000 #x-80000000) #x-80000000) 16)
=> 3fffffff80000000
うまくいっているようだ.

0 件のコメント: