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
うまくいっているようだ.

2015年9月16日水曜日

ARMのプログラム技法

数日前のブログではARMのアセンブリ言語でカレンダーのプログラムcalを書いてみた. 今回はおなじラズパイで動くBCPLで同様のプログラムを書こう. (ARMのプログラム技法という題は多少おかしいが.)

BCPLはMartin Richardsが1967年頃に設計した言語である. その元はケンブリッジ大学とロンドン大学がコンパイラ記述用に開発したCPLで, Combined Programming Languageの略である. そのBasic版がBCPLということになっている. またBCPLからC言語が生まれたこともよく知られている.

BCPLをケンブリッジで開発した後, Martin RichardsはMITのProject MACに滞在したので, MITでもBCPLは使えるようになった. 私がBCPLに出逢ったのは1973年から1年MITにいた時であった.

BCPLは最初の設計から50年近く経ったが, まだ保守されているのに驚く.

下のcal.bはBCPLでcalを書いたリストである.



ARMのcalとほとんど同じに出来ているので, それを読む注釈と思って眺めて欲しい. 00行目 C言語のinclude のようなものだ.
02行目 C言語のmain()のようなものだ. ただVALOF { ... RESULTIS ..} の形に なっている.
03行目 変数yearとmonthを定義. BCPLには型がない. 初期値もこう書く流儀らしい.
04行目 他の変数も定義
05,06行目 配列の定義 VEC 11で0から11まで12個の場所が取れる. 初期値の設定は 別にやるらしい. 14行目から18行目で設定した.
08行目から13行目 yearとmonthを引数から取り込むにはこう書くらしい.
19行目 Gregorio暦では週日は400年で繰り返すから, 西暦を400で割った剰余r400だけ を考えることにする.
21行目まで r400を100, 4で割った商と剰余を求める.
22行目 r100≠0をBCPLではr100¬=0と書いたりするが, ASCIIには¬がなく, ~=0でもいいようだ.
23行目 閏年ならrsの1月と2月, msの2月の値を修正する.
24行目 aはその月の1日の週日. nは1週間を数える変数である.
25行目 1日のある週の最初から6週目の最後までFOR分で繰り返す.
26〜28行目 1日から月末までの日なら出力する. それ以外なら空白を出力.
29,30行目 nを下げ0になったら改行する.
31行目 0を持って帰る.

これを実行するには, raspberrypi:~$でcintsysに入る

0.030> bcpl cal.b to cal
bcpl cal.b to cal

BCPL (10 Oct 2014) with simple floating point
Code size =   436 bytes of 32-bit little ender Cintcode
0.110> cal 2015 9
cal 2015 9
        1  2  3  4  5
  6  7  8  9 10 11 12
 13 14 15 16 17 18 19
 20 21 22 23 24 25 26
 27 28 29 30

0.020> cal 2015 10
cal 2015 10
              1  2  3
  4  5  6  7  8  9 10
 11 12 13 14 15 16 17
 18 19 20 21 22 23 24
 25 26 27 28 29 30 31

0.020> 
とまぁこんな具合に動く.

2015年9月10日木曜日

ARMのプログラム技法

前回のブログでCalのプログラムの核心の部分がうまく書けることが分かったので, 全体を書いてみた. やや長いが興味があれば追ってみて欲しい.

プログラム0


行00 .data ここからデータ領域という指示
行01,02 年と月を格納する場所 4バイトずつ
行03 1月から順に次の年初の曜日とその月の1日の曜日の差 12月は31日なので 4週と3日余るが, -3mod7=4のような値のリスト. 以下rsという
行04 各月の長さ. 以下msという
行05〜09 scanf, printfの書式
行10 プログラム部分の開始
行11〜17 除算サブルーチン r0をr1で割り商をr0, 剰余をr1に置く

プログラム1


行19 主ルーチンの入り口, 帰り番地をr8へ退避する
行20 yearを入れる場所をr1へ
行21 monthを入れる場所をr2へ
行22 scanfの書式の番地をr0へ
行23 scanfを呼ぶ
行24 データ領域のベースアドレスをr3へ
行25 yearをr0へ
行26 400をr1へ
行27 除算
行28 400で割った剰余R400をr4へ
以下 R400を100と4で割った商と剰余を求める
行38 100で割った剰余を0と比較
それが0か否かにより, 400と4との剰余をr1に置く(条件つきmov)
行41 r1が0なら閏年(閏年の判定には100で割った剰余R100が0なら400で割った剰余R400が0, 0でないなら4で割った剰余R4が0かで判定できる)

プログラム2


行42〜47 r1=0なら閏年なので, rsの1月2月とmsの2月を修正する
行48〜58 その月の1日の週日(a)は(1+R400-Q100+Q4+rs[月])mod 7
行59 前回のブログのr5の値, 1-a
行60 前回のブログの#6に相当する値, 43-a
行62 前回のブログの#3に相当する値, その月の日数

プログラム3


出力用の値が設定できたので出力に移る.
行63,64 曜日の名を出力
行65 r4は1週間を数えるカウンタ
行66 日付が1より大きいか
行67 そうなら最後の日付より小さいか
行68 日付をr1に置く
行69,70 比較の結果でいづれかの書式をr0に置く
行72 日付を1増やす
行73 週のカウンタを減らす
行74〜76 1週間が終わったら改行しカウンタをリセット
行77,78 最後になっていなければl0へ戻る
行79 lrを戻す
行80,81 プログラムの戻り値を入れて終わる
行82〜87 定数の番地

このプログラムでは, データの場所にはラベルがあるが, プログラムの部分には殆どラベルが見られない. divmodはサブルーチンの入り口, mainはプログラム全体の入り口, あとカレンダー出力のループのl0があるだけである. 従ってジャンプ命令もほとんどない. そういうことではARMのアーキテクチャは気持ちがいいといえる.

このプログラムをRaspberry Piで動かすには,
as -o cal.o cal.s
gcc -o cal cal.o
./cal
で起動し
2015 9
のように年と月を入力すると
./cal
2015 9
 Su Mo Tu We Th Fr Sa
        1  2  3  4  5
  6  7  8  9 10 11 12
 13 14 15 16 17 18 19
 20 21 22 23 24 25 26
 27 28 29 30

とカレンダーが得られる.

このプログラムはhttp://www.iijlab.net/~ew/cal.sに置いてある.

2015年9月8日火曜日

ARMのプログラム技法

1ヶ月ほど前のブログで「数式お絵書き」を書いたのは, 手元のRaspberry PiでMathematicaが動いていたからだ.

Mathematicaも面白いが, Raspberry PiはそのCPUがARMなので, アセンブリ言語でプログラムを書くと, ARMのアーキテクチャがよく分るではないかと, 最近ではもっぱらアセンブリ言語のプログラムを書いている.

「ARM」という単語を最初に聞いたのは, 1995年頃の英国ケンブリッジでであったと思う. ケンブリッジ大学の計算機研究所のWilkes先生を訪ねたのだが, もう大学にもオリベッティの研究所にも出勤されてはいなかったので, オリベッティ研究所の所長のAndy Hopperさんに会って雑談している時, ARMといういいCPUがあるよと言われた. (この訪問のことは, bit 1996年1月号のaleph zeroに書いた.)

昨年8月, 偶然みつけたウェブページのことをツィッターに書いた.
50年ほど前にBCPLを開発したMartin Richardsが「青少年のためのRaspberry Pi上のBCPLプログラミング入門」を書いている(http://goo.gl/rXOKy2 ). 1つの言語に半世紀も情熱を持ち続けるとは見上げたもの. そのうち読んでみたい.
(「青少年のための...入門」と書いたのは, 元の題が「Young Persons Guide to BCPL Programming on the Raspberry Pi」であり, Benjamin Brittenの曲「The Young Person's Guide to the Orchestra」が日本では「青少年のための管弦楽入門」といわれているからだ.)

このツィートの後, 研究所でRaspberry Piを何個か購入し, 使えるようになってきた. またARMそのものにも興味も出てきた.



ARMでプログラムを書くに際して, 最低限の知識は次のようだ.

ArmはRiscだが, 命令幅が32ビットで, 水平型マイクロプログラムの様相を持つ. 16ビット命令のモードもある.

記憶装置とのデータ転送はldr, strだけ.

CMPがCPSR(Current Program Status Register, NZCVビット)をセットするほか, 加減乗算命令でも, addsのようにsを付けてCPSRをセットできる.

命令には, eq, ne, pl, miなど条件を付け, 実行するしないが指定できる.

このようなことを念頭に置いてプログラムを書く. その前後に指定された個数の空白を置き, aからbまでの数字を順に出力するにはどうするか. これはカレンダーのプログラムを書くときに必要になる. 例えば今年の9月のカレンダーは, cal 9 2015 で見ると
% cal 9 2015
   September 2015
Su Mo Tu We Th Fr Sa
       1  2  3  4  5
 6  7  8  9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30

なら, 先頭に2個の空白と最後に3個の空白を置き, 1から30まで印字するプログラムを書けばよい. いきなりプログラムではなく, テストプログラムとしては, 例えば前に3個, 後に2個の空白を置き, 1から3まで出力するプログラムは普通ならこうなろう.
(do ((i 0 (+ i 1))) ((= i 3)) (display "   "))
(do ((i 1 (+ i 1))) ((> i 3)) (display i))
(do ((i 0 (+ i 1))) ((= i 2)) (display "   "))
ARMの機能を活用するとこうなる.
.data
        .balign 4      /*4バイト境界を合わせる*/
a:      .word -2       /*出力する整数の初期値 2*/
ret:    .word 0        /*帰り番地の退避場所*/
s0:     .asciz ". *"   /*printfの書式*/
s1:     .asciz ".%2d"
s2:     .asciz "\n"
.text
        .balign 4
.global main
main:   ldr r0,reta    /*帰り番地を一時退避*/
        str lr,[r0]
        ldr r0,aa
        ldr r5,[r0]    /*出力する整数をr5へ*/
l0:     cmp r5,#1      /*出力する最初の数a*/
        rsbgts r0,r5,#3/*出力する最後の数b*/
        mov r1,r5      /*出力する数をr1へ*/
        ldrpl r0,s1a   /*書式0を使う*/
        ldrmi r0,s0a   /*書式1を使う*/
        bl printf      /*printfで出力*/
        add r5,r5,#1
 cmp r5,#6      /*終りの空白が済んだときのr5の値*/
 bmi l0
 ldr r0,s2a
 bl printf      /*書式2で改行を出力*/
 mov r0,#1      /*プログラムの返り値*/
        ldr r1,reta
        ldr lr,[r1]    /*帰り番地を復活*/
        bx lr

aa:     .word a
s0a:    .word s0
s1a:    .word s1
s2a:    .word s2
reta:   .word ret
想定通りの出力が得られる. (空白の様子が分かるように.や*が入っている.)
. *. *. *. 1. 2. 3. *. *
上のプログラムのミソは
l0:     cmp r5,#1      /*出力する最初の数a*/
        rsbgts r0,r5,#3/*出力する最後の数b*/
        mov r1,r5      /*出力する数をr1へ*/
        ldrpl r0,s1a   /*書式0を使う*/
        ldrmi r0,s0a   /*書式1を使う*/
        bl printf      /*printfで出力*/
        add r5,r5,#1
 cmp r5,#6
 bmi l0
のところだ. ラベルがl0:の行ではr5と1を比較, つまりr5から1を引く. r5が-2から0までは結果は負である. 次の行はこの結果が>0ならrsbつまり逆減算で, 3からr5を引き, 最後のsで結果をCPSRに置く. r5が3を超えると負になるわけだ.

次の行でr5を出力パラメータとしてr1へ置き, 前の計算の正負に従って書式をr0に置き, printfを呼ぶ.

r5は最後の数3を超えても増え続け, つまり空白を出力し続け, 6になるとcmpの結果が負ではなくなり, ループから抜ける.

要するに初めの空白部は, r5との比較が負で判定し, 終りの空白はr5と3を逆に引くことで, 範囲外をともに負にしている.

こんなことが出来るのはARMの命令が多様だからであった.