入力用アセンブリの例と書き方

Mon, 04 Dec 2017 16:49:04 JST (11d)

更新情報

17/11/02 全ての例においてHALT命令に対応

アセンブリの書き方


本実験で制作したCPUのプログラミングには、アセンブリ言語を使用します。

このアセンブリ言語をアセンブによって機械語に変換することで、制作したCPUに入力、実行できるようになります。


このページでは、簡単なプログラムから始めてアセンブリ言語の書き方を練習していきます。

1つの例ごとに命令やテクニックを少しずつ増やしているので、例が進むにつれ自力で書くことに挑戦してみてもいいでしょう。

またどのアセンブリも基本的に説明のために書いてあるため、自信があれば短く、つまり最適化をしてみるのも楽しいと思います。


命令セットは教科書のものを利用しており、書式はMIPSというアセンブリ言語を参考にしています。

MIPSについてより詳しく知りたい人はこちら、要望があれば実験中にお貸しします。

アセンブルの仕方


アセンブリ言語を、アセンブを用いて機械語に変換することを、アセンブと言います。

本実験ではこちらfileas.plのアセンブラを使用してください。

例1.等差数列の和


1+2+3+4+5+6+7+8+9+10 を計算するプログラムです。

今回はループなどを使わず、単純に足し算をしていくことを考えます。

レジスタの0初期化

XORでソースレジスタに同じものを指定します。

(XORの動作…0,0や1,1→0、0,1や1,0→1)


ソースレジスタが同じことはそれぞれのビットが全て同じことを意味するので、0に初期化することができます。

レジスタの役割

アセンブリ言語では各レジスタに、0はゼロレジスタ、8~15は一時変数などと大まかな役割を決めて書くことが多いです。

本実験の範囲では31番以外のレジスタならどれを使ってもよいのですが、せっかくなのでMIPSをもとにレジスタ番号を決めていきます。


r0…定数の0(ゼロレジスタ)

r8…等差数列の公差を管理

r9…等差数列の和を管理

サンプルコード1

	#0の準備
	XOR	r0,	r0,	r0
	#1項めの計算
	ADDI	r8,	r0,	1
	ADD	r9,	r0,	r8
	#2項めの計算(以下繰り返し)
	ADDI	r8,	r8,	1
	ADD	r9,	r8,	r9
	ADDI	r8,	r8,	1
	ADD	r9,	r8,	r9
	ADDI	r8,	r8,	1
	ADD	r9,	r8,	r9
	ADDI	r8,	r8,	1
	ADD	r9,	r8,	r9
	ADDI	r8,	r8,	1
	ADD	r9,	r8,	r9
	ADDI	r8,	r8,	1
	ADD	r9,	r8,	r9
	ADDI	r8,	r8,	1
	ADD	r9,	r8,	r9
	ADDI	r8,	r8,	1
	ADD	r9,	r8,	r9
	#10項めの計算
	ADDI	r8,	r8,	1
	ADD	r9,	r8,	r9
	HALT

バイナリコード1

filesample1.bin

r9に55が出力されているはずです。

例2.フィボナッチ数列


フィボナッチ数列をn[16]まで計算するプログラムです。

プログラム的には、

	n[i+2] = n[i+1] + n[i];

を計算することを考えましょう。


今回の例での初項は、

	n[0] = 0;
	n[1] = 1;

とします。

メモリの利用

レジスタの数は多くはないため、プログラムによっては値を保存しきれない場合があります。

そのような時はレジスタの値を、より大容量のメモリに保存することでレジスタを空けることができます。


今回の例ではlwやswなどのメモリアクセス命令を利用してみましょう。

(もちろんフィボナッチの計算そのものには、n[i+1]とn[i]を保存する2つのレジスタがあれば十分です。)


lw命令とsw命令の使い方は以下のようになります。

	LW	[rs],	[rt],	[dpl]	#rtに、メモリのアドレスrs+dplの値を読みだす
	SW	[rs],	[rt],	[dpl]	#メモリのアドレスrs+dplに、rtの値を書き込む

rs…ベースアドレスを持つレジスタです。このレジスタこそが、ポインタの正体になります。

rt…LWであればメモリの値が読みだされるレジスタ、SWであればメモリに書き込む値を管理するレジスタです。

dpl…おそらくdisplacement(変位)の略で、ベースアドレスに加算する値になります。

レジスタの役割

r0…ゼロレジスタ


r8…n[i]を管理

r9…n[i+1]を管理

r10…n[i+2]を管理


r11…n[0]のメモリアドレスを管理(つまりint *n;、C言語でいうint型のポインタになります))

サンプルコード2

	#0の準備
	XOR	r0,	r0,	r0
	#n[0]のアドレスを初期化
	ADDI	r11,	r0,	512
	#n[0],n[1]の準備と保存
	ADDI	r8,	r0,	0
	SW	r8,	0(r11)
	ADDI	r9,	r0,	1
	SW	r9,	4(r11)
	#n[2]の計算と保存
	ADD	r10,	r8,	r9
	SW	r10,	8(r11)
	
	#n[3]の計算と保存(以下定数以外繰り返し)
	#n[i+1],n[i]の準備
	LW	r8,	4(r11)
	LW	r9,	8(r11)
	#n[i+2]の計算と保存
	ADD	r10,	r8,	r9
	SW	r10,	12(r11)
	LW	r8,	8(r11)
	LW	r9,	12(r11)
	ADD	r10,	r8,	r9
	SW	r10,	16(r11)
	LW	r8,	12(r11)
	LW	r9,	16(r11)
	ADD	r10,	r8,	r9
	SW	r10,	20(r11)
	LW	r8,	16(r11)
	LW	r9,	20(r11)
	ADD	r10,	r8,	r9
	SW	r10,	24(r11)
	LW	r8,	20(r11)
	LW	r9,	24(r11)
	ADD	r10,	r8,	r9
	SW	r10,	28(r11)
	LW	r8,	24(r11)
	LW	r9,	28(r11)
	ADD	r10,	r8,	r9
	SW	r10,	32(r11)
	LW	r8,	28(r11)
	LW	r9,	32(r11)
	ADD	r10,	r8,	r9
	SW	r10,	36(r11)
	LW	r8,	32(r11)
	LW	r9,	36(r11)
	ADD	r10,	r8,	r9
	SW	r10,	40(r11)
	LW	r8,	36(r11)
	LW	r9,	40(r11)
	ADD	r10,	r8,	r9
	SW	r10,	44(r11)
	LW	r8,	40(r11)
	LW	r9,	44(r11)
	ADD	r10,	r8,	r9
	SW	r10,	48(r11)
	LW	r8,	44(r11)
	LW	r9,	48(r11)
	ADD	r10,	r8,	r9
	SW	r10,	52(r11)
	LW	r8,	48(r11)
	LW	r9,	52(r11)
	ADD	r10,	r8,	r9
	SW	r10,	56(r11)
	LW	r8,	52(r11)
	LW	r9,	56(r11)
	ADD	r10,	r8,	r9
	SW	r10,	60(r11)
	#n[16]の計算と保存
	LW	r8,	56(r11)
	LW	r9,	60(r11)
	ADD	r10,	r8,	r9
	SW	r10,	64(r11)
	HALT

バイナリコード2

filesample2.bin

メモリの576番地に987が出力されているはずです。

例3.エラトステネスの篩


素数を求めるプログラムです。

あらかじめ自然数nを与え、n以下の素数をすべて求めます。

今回の例では、メモリに保存することで求めた、と呼ぶことにし、n = 100としてサンプルを用意しました。


アルゴリズムは以下のようになっています。

  • 要素を100個持つ配列変数flagを用意
  • flagの各要素が1であれば素数、0であれば素数でない、として扱います
  • flagの全要素を1(true)に初期化
  • はじめは全て素数であると仮定します
  • flag[0]とflag[1]に0を代入
  • 0と1は素数の定義には含まれないので除きます
  • 判定用の変数divを用意して1ずつ加算、flag[divのi( > 1)倍]に0を代入
  • 処理のちょっとした高速化のため、divが素数でない場合は何もせずにさらに1を加算します
  • divが50を超えた場合は判定終了
  • 2倍すると100を超えてしまった場合と言い換えることもできます

アセンブリでのfor文

配列変数flagの初期化や変数divの加算には、C言語におけるfor文のような処理ができると便利です。

ここで、for文がどのようにアセンブリに変換されるか、まさにコンパイラで行われる処理を考えてみましょう。

	for(i = 0; i < max; i++) {
		[プログラム]
	}

このfor文は、i < maxを満たす限り[プログラム]を実行するという記述になります。

アセンブリ言語ではif文に似たジャンプ命令しか使えないので、これらの命令をうまく組み合わせて書き換えていきます。


書き換え後は図のようになります。

assembly_0.png

どうしてこのように並ぶのかを詳しく考えるため、for文を書き換える流れを以下に紹介します。


for文のカッコを最初から見ていくと、1つめのi = 0は[プログラム]の前に必ず実行されるので、そのまま出力します。


2つめのi < maxは[プログラム]が実行されるための条件です。

これは1ループ目から実行されるため、i = 0を表すアセンブリの次の行、[プログラム]の先頭行にジャンプ命令を置きます。

i < maxの場合は[プログラム]が実行され、i >= maxの場合はfor文の次の行にジャンプする必要があります。

よって[プログラム]の次の行にラベル0を用意し、先ほど置いたジャンプ命令でラベル0を指定します。

なお、この例を実現できる命令はbleしか存在しないため、図のように条件がmax <= iに書き換わることに注意してください。


3つめのi++はループ後に実行されればよいので、[プログラム]の最終行として追加します。


これで終わり、のように思えますが、このままでは1度分岐しただけで[プログラム]の次の行に処理が移ってしまいます。

きちんとループを実行するため、ループの先頭に戻る処理を付け加えましょう。

アセンブリで行をさかのぼるにはジャンプ命令を使用するため、[プログラム]の先頭行にラベル1を用意します。

そして[プログラム]の最終行にラベル1へのジャンプ命令を追加することで、for文からアセンブリ言語への変換が終了します。

アドレスの表現

今回の例ではflag[i]のようにflagの値を参照しますが、これは、

	LW	[flag],	0([i])

のように書くことはできません。


なぜかを考えるために、レジスタのバイト数に関して考えてみましょう。

基本的に1バイトは8ビットとして扱われるので、レジスタの扱いは4バイトということになります。

よって先ほどのflag[i]は、アセンブリでは以下のように書けばよいことがわかります。

	LW	[flag],	0([i*4])


この時コンパイラでは、初めからiに4をかけた状態で処理する場合もあれば、メモリの参照時だけ4をかけるように処理することもあります。

今回のサンプルでは、iのループでは初めから4をかけ、divのループではメモリの参照時に4をかけるようにしました。

2つの処理の間で、命令数がどう変わるかなどを比較してみてください。

シフトによる掛け算割り算

アドレスの表現の都合上4をかける必要が出てきますが、今回の実験では掛け算を行う命令が存在しません。

これには、シフトと呼ばれるビット演算、特に以下のような左シフトを利用することで実現します。

	11(3)	→	110(6)
	101(5)	→	1010(10)

厳密な定義ではありませんが、左シフトとは2進数のビットを1つずつ左にずらし、空いた1ビット目に0を代入する操作です。

そしてこの左シフトを行った前と後で、10進数の値が2倍になっていることが確認できると思います。


この左シフトはsll命令によって実現することができます。 値の4倍、つまり2の2乗倍を行いたいので、今回の例ではsllに定数2を与えています。


逆に右シフトを行うと、切り捨てにはなりますが2で割ることが可能です。 右シフトには論理右シフトであるsrl命令と、算術右シフトであるsra命令があります。


基本的に論理シフトは空いたビットに0を代入する操作ですが、算術シフトの場合は最上位ビットの値を空いたビットにコピーします。 これらの違いは以下のように、最上位ビットを符号と考えた場合の10進数表現で確認できます。

	1_010(-6)	→	0_101(5)	//論理右シフト
	1_010(-6)	→	1_101(-3)	//算術右シフト

このように、論理右シフトでは割り算が成り立たないのに対し、算術右シフトでは2で割ることができています。

C言語のようなソースコード

今回の例では処理が比較的複雑になるため、参考までにモデルとなるソースコードを以下に紹介します。 これをうまくアセンブリで表現することが、最終目標になります。

	int i;
	int flag[100];	//要素を100個持つ配列変数flagを用意
	
	for (i = 0; i < 100; i++) {
		flag[i] = 1;	//flagの全要素を1(true)に初期化
	}
	
	//flag[0]とflag[1]に0を代入
	flag[0] = 0;
	flag[1] = 0;
	
	//判定用の変数divを用意して1ずつ加算、flag[divのi( > 1)倍]に0を代入
	int div;
	
	for (div = 2; div < 51; div++) {	//divが50を超えた場合は判定終了
		if (flag[div] == 0) {
			div++;
			continue;
		}
	
		for (i = div * 2; i < 100; i = i + div) {
			flag[i] = 0;
		}
	}
	
	for (i = 2; i < 100; i++) {
		if (flag[div] != 0) {
			flag[i] = i;	//素数の実際の値を書き込む
		}
	}

レジスタの割り当て

r24,r25はr8~15同様一時変数に利用されるレジスタです。


r0…ゼロレジスタ


r8…変数iを管理(初めから4倍) r9…変数divを管理


r10…配列変数flagのアドレスを管理 r11…配列変数flagの要素を管理

r14…代入、計算用の変数を管理 r15…配列変数の計算時のアドレスを管理


r24…iのfor文の上限を管理(初めから4倍) r25…divのfor文の上限を管理

サンプルコード3

		#ゼロレジスタの用意
		XOR	r0, r0,	r0
	
		#変数iの用意
		ADDI	r8,	r0,	0
	
		#要素を100個持つ配列変数flagを用意
		#配列変数flagのアドレスを初期化
		ADDI	r10,	r0,	512
	
		#配列変数flagの要素を初期化する定数
		ADDI	r14,	r0,	1
	
		#i = 0の変換
		ADDI	r8,	r0,	0
		#iの上限となる定数
		ADDI	r24,	r0,	400
	
	#flagの全要素を1(true)に初期化
	FOR0S:					#for (i = 0; i < 100; i++)
		#i < 100(100 <= i)の変換
		BLE	r24,	r8,	FOR0E
	
		#forブロック内
		ADD	r15,	r8,	r10
		SW	r14,	0(r15)
	
		#i++の変換
		ADDI	r8,	r8,	4
		J	FOR0S
	
	FOR0E:
		#flag[0]とflag[1]に0を代入
		SW	r0,	0(r10)
		SW	r0,	4(r10)
	
		#判定用の変数divを用意して1ずつ加算、flag[divのi( > 1)倍]に0を代入
		#div = 2の変換
		ADDI	r9,	r0,	2
		#divの上限となる定数
		ADDI	r25,	r0,	51
	
	FOR1S:					#for (div = 2; div < 51; div++)
		#divが50を超えた場合は判定終了
		#div < 51(51 <= div)の変換
		BLE	r25,	r9,	FOR1E
	
		#divのforブロック内
		#シフト演算で4倍
		SLL	r14,	r9,	2
		ADD	r15,	r10,	r14
		LW	r11,	0(r15)
		BNE	r0,	r11,	IF0E	#if (flag[div] == 0)
	
		#ifブロック内
		ADDI	r9,	r9,	1
		J	FOR1S
	
	IF0E:
		#i = div * 2の変換(アドレスのためさらに4倍)
		SLL	r14,	r9,	3
		ADD	r8,	r0,	r14
		#iの上限となる定数
		ADDI	r24,	r0,	400
	
	FOR2S:					#for (i = div * 2; i < 100; i = i + div)
		#i < 100(100 <= i)の変換
		BLE	r24,	r8,	FOR2E
	
		#forブロック内
		ADD	r15,	r8,	r10
		SW	r0,	0(r15)
	
		#i = i + divの変換(アドレスのため4倍)
		SLL	r14,	r9,	2
		ADD	r8,	r8,	r14
		J	FOR2S
	
	FOR2E:
		#div++の変換
		ADDI	r9,	r9,	1
		J	FOR1S
	
	FOR1E:
		#素数をメモリに保存
		#i = 0の変換
		ADDI	r8,	r0,	8
		#iの上限となる定数
		ADDI	r24,	r0,	400
	
	FOR3S:					#for (i = 2; i < 100; i++)
		#i < 100(100 <= i)の変換
		BLE	r24,	r8,	FOR3E
	
		#iのforブロック内
		ADD	r15,	r8,	r10
		LW	r11,	0(r15)
		BEQ	r0,	r11,	IF1E	#if (flag[div] != 0)
	
		#ifブロック内
		#シフト演算で1/4
		SRA	r14,	r8,	2
		ADD	r15,	r8,	r10
		SW	r14,	0(r15)
	
	IF1E:
	
		#i++の変換
		ADDI	r8,	r8,	4
		J	FOR3S
	
	FOR3E:
		HALT

バイナリコード3

filesample3.bin

メモリの520番地に2、524番地に3…のように素数が出力されているはずです。

例4.モンテカルロ法円周率


円周率を計算するプログラムです。

1辺2^16bitの正方形にランダムで点をプロットして、半径2^16の四分円の内か外かを判定します。

プロットはn回、四分円の内と判定された数はmとし、mを16進数で表す10進数で表します。


今回の例ではメモリに保存することで求めた、と呼ぶことにし、n = 400としてサンプルを用意しました。

もし円周率が正しく得られるのであれば、半径をrと考えて以下のような比が考えられます。

	n→r^2 = 400
	m→r^2 * π / 4 = 400 * π / 4 = π * 100

より、このサンプルの出力は16進数で0000_0314となるはずです。


アルゴリズムは以下のようになっています。

Xorshiftと呼ばれる方法を、関数xor128として使い、乱数を生成

・上位16ビットと下位16ビットに分け、それぞれをx座標、y座標とします

・2乗を関数powで計算

・mを16進数で表現する10進数として出力

	例えばmが10進数の2521であれば、16進数の0010_0101_0010_0001(0x2521)のように出力

アセンブリでの関数

関数の呼び出しは、教科書の呼び出し規約に従い、命令を組み合わせることで実現します。

具体的に考えるため、サンプルの一部から関数powを呼び出す処理と、復帰する処理を以下に紹介します。

		#2乗を関数powで計算
		#pow(x)
		ADDI	r4,	r0,	r17
		SW	r8,	0(r29)
		ADDI	r29,	r29,	4
		JAL	_pow
		#スタックポインタの引き算(定数ではビットが足りないことに注意)
		ADDI	r14,	r0,	4
		SUBI	r29,	r29,	r14
		LW	r8,	0(r29)
		ADDI	r17,	r0,	r2
	_pow							#int pow(int a)
	
		…
	
		#ifブロック内
		ADD	r2,	r2,	r4
	
		…
	
		#return sum
		JR	r31

関数を呼び出してから復帰するまでの流れを、おおまかに確認してみましょう。

アドレスを移動するという意味で関数呼び出しを行っているのはJAL命令です。

JAL命令はr31に現在のプログラムカウンタに4を足したもの、つまり次の行のアドレスを保存します。

そしてプログラムカウンタを_powで表されるアドレスに書き換えることで、関数を呼び出します。


関数呼び出しで問題になるのは、いろいろな関数を呼び出すにつれ、レジスタが足りなくなってしまうことです。

よって保存すべきレジスタを判断し、レジスタの値をメモリに保存するのですが、SW命令がこれにあたります。

この時に保存するアドレスは、スタックポインタというレジスタで管理されます。


スタックポインタ、略してSPを利用した値の保存は図のようになります。

スタックは一般にアドレスが減る方向に進むことが多いのですが、この例では増える方向としました。

r8が保存された後でr29にrが足されることにより、4(r29)の部分が新しいSPでは0(r29)となります。

これにより呼び出した先の関数から新たに関数を呼び出しても、同じ書き方を行えます。


呼び出された先では、C言語でいうreturn文の働きを実現するため、戻り値をr2で管理します。

復帰をするときはJR命令を使うのですが、これにはr2を設定する機能などは特にありません。

JR命令は、関数の呼び出し時にJALが保存したr31のアドレスをプログラムカウンタに代入する命令です。


このような動作ののち、処理が関数呼び出しの次の行に戻ります。

初めにSPの値を戻さなくてはならないので、呼び出し時に足した分だけ引きます。

この時測地で計算をしたくなりますが、レジスタの値は32ビットなのでうまくいかないことに気を付けてください。

そして戻ったSPを基準に、LW命令を並べることによってレジスタの値を元に戻します。


以上の流れにより、アセンブリでの関数の動作が実現できたことになります。

2乗の計算

今回の実験では掛け算を扱う命令が存在しなかったので、2乗もビット演算を工夫することで行います。

2乗を行う関数powの記述の一部は、C言語のように表現すると以下のようになっています。

	//16ビットを上から1ビットずつ取り出す、掛け算のひっ算のような処理
	for (bit = 0x8000; bit; bit = bit >> 1) {
		//和をシフト
		sum = sum << 1;
	
		//ビットが1の時は加算、これは1倍を意味するが、その後のシフトにより調整される
		if (a16 & bit) {
			sum = sum +  a16;
		}
	}

まずforループですが、変数bitに代入している0x8000は1000_0000_0000_0000を意味しています。

bit = bit >> 1は右ビットシフトであり、最上位の1が最下位に向かって1ビットずつずれていくことになります。

判定部分のbitは、0がfalse、0でないものがtrueとなることを利用し、最上位の1が最下位を通り越したことを判定します。


sum = sum << 1をいったん飛ばして、if文に注目します。

a16 & bitは条件式ではなく、ビット演算であることに注意すると、これはa16のビットを取り出す操作になります。

for文同様ビットが0か1かでfalse、trueを判断し、1だった場合はsumにa16が加算されます。

if文をまとめると、nループ目にはa16の上からnビット目を取り出して、1だった場合は加算する処理になります。


ただし本来の目的は2乗を行うことであり、ただ加算するだけでは1倍となってしまうことに注意してください。

nループ目は上からnビット目なので、本来であれば2^(16-n)がかかるべきです。

これを実現するのが先ほど飛ばしたsum = sum << 1になります。

例えばiループ目にif文が成立したとして、残りの16-iループで2倍が行われるため、2^(16-i)がかかったことになります。


以上のような操作により、変数の2乗がビット演算のみを用いて計算できたことになります。

16進数を用いた10進数の表現

今回の例では、出力mは16進数を用いて10進数のように表現します。

例えばmが10進数の830であれば、16進数で0000_1000_0011_0000(0x0830)と表現します。

これは16進数の1桁を10進数の1桁として扱うことになるため、ビット演算では4ビットが10進数の1桁となります。

出力部の一部をC言語のように表現すると、以下のようになっています。

	x = 0;		//16進数で表現する10進数
	for (i = 7; i >= 0; i--) {			//iは10進数における桁数
		y = 1;					//10進数を計算するための割る数
	
		//10のi乗を計算
		for (j = 0; j < i; j++) {
			y = (y << 3) + (y << 1);	//10をかける
		}
	
		//16進数は1文字4ビットより、10進数を1けたずらす
		x = x << 4;
	
		//引き算を利用した割り算
		while (m >= y) {
			m = m - y;
			x = x + 1;
		}
	}

iのfor文から見ていきますが、iは32ビットを4ビットずつ区切るための変数です。

これは16進数の1桁が4ビットのためであり、10進数の桁に対応しています。


次にjのfor文ですが、y = (y << 3) + (y << 1)をよく考えてみましょう。

y << 3はyの8倍であり、y << 1は2倍であるため、これはyの10倍を繰り返していることになります。

よってこのfor文を利用することで、yには10のi乗が代入されることになります。

ここで、10進数のi+1桁に対応することを確認してください。


2乗の計算と同様x = x << 4はいったん飛ばして、次のwhileループを考えます。

m = m - yは、先ほどのjのfor文により、mの10進数におけるi桁目が1引かれていることになります。

これがm < y、つまり引けなくなるまでループするため、mの10進数にi桁目の数だけxに1が加算される処理になります。

これは紛れもなく、mのi桁目がxに移されたことになります。


ここで飛ばしたx = x << 4を見てみると、xを4ビット左にシフトさせていることがわかります。

これは16進数の1桁分であり、16進数で表したmのi+1桁目が1桁ずれたことを意味します。

以上のような操作により、16進数を利用して10進数を表現できたことになります。

16桁を超える定数の定義

今回の実験のアセンブリでは、16ビットを超える数値を命令で扱うことはできません。

なので、アセンブ側で32ビットまでの数値を扱うことができるようになっています。

定数を利用する場合は、アセンブリ内に以下のように記述します。

	_x:
		.long	123456789		//10進数表示

これで、32ビット以上の数値を命令中で扱うことができます。

ただし_xは値そのものではなく、アドレスを表す数値であることに注意してください。

例えば定数の値を読み出したい場合は、

	ADDI	r8,	r0,	_x
	LW	r9,	0(r8)

のように記述することになります。

C言語のようなソースコード

今回の例でもモデルとなるソースコードを以下に、関数ごとに紹介します。

関数呼び出し以外は自力で記述できる範囲なので、余力があれば挑戦してみてください。


乱数生成を行う関数です。

式中の^は、XORを表す記号であることに注意してください。

アルゴリズムの詳細を知りたい場合は、こちらを参照してください。

	int xor128() {
		static int x = 123456789;
		static int y = 362436069;
		static int z = 521288629;
		static int w = 88675123; 
		int t;
	
		t = x ^ (x << 11);
		x = y;
		y = z;
		z = w;
		w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
		return w;
	}

引数aの2乗を行う関数です。

aが32ビットになっていますが、x座標とy座標で16ビットずつに分けて利用するため問題ありません。

	int pow(int a) {
		int a16 = a & 0xffff;	//下位16ビットの取り出し
	
		int bit;
		int sum = 0;
	
		//16ビットを上から1ビットずつ取り出す、掛け算のひっ算のような処理
		for (bit = 0x8000; bit; bit = bit >> 1) {
			//和をシフト
			sum = sum << 1;
	
			//ビットが1の時は加算、これは1倍を意味するが、その後のシフトにより調整される
			if (a16 & bit) {
				sum = sum +  a16;
			}
		}
	
		return sum;
	}

初めに実行される関数です。

return xは正確には実行せず、xをメモリに書き込むことで処理を完了したこととします。

	int main() {
		int i, j;
		int x, y;
		int m = 0;
	
		//四分円の内か外かを判定
		for (i = 0; i < 400; i++) {
			int xy = xor128();			//乱数を生成
	
			x = (xy >> 16) & 0xffff;		//上16桁を下16桁に取り出し
			y = xy & 0xffff;			//下16桁を取り出し
			if (pow(x) + pow(y) <= pow(0xffff)) m++;	//四分円内ならmを1加算
		}
	
		x = 0;		//16進数で表現する10進数、変数は再利用
		for (i = 7; i >= 0; i--) {			//iは10進数における桁数
			y = 1;					//10進数を計算するための割る数、変数は再利用
	
			//10のi乗を計算
			for (j = 0; j < i; j++) {
				y = (y << 3) + (y << 1);	//10をかける
			}
	
			//16進数は1文字4ビットより、10進数を1けたずらす
			x = x << 4;
	
			//引き算を利用した割り算
			while (m >= y) {
				m = m - y;
				x = x + 1;
			}
		}
	
		return x;
	}

レジスタの割り当て

関数呼び出しに伴うレジスタの扱いの違いに注意してください。

特に、r2,r3は関数の戻り値、r4~r7は引数、r16~r23は関数呼び出しの間も保存される一時変数を管理します。

またスタックポインタは、r29で管理します。


以下main関数以外は基本的に、main関数と異なる使い方をするレジスタの説明だけを書いています。


~main関数~


r0…ゼロレジスタ r2…関数の戻り値


r4…引数


r8…変数iを管理 r9…変数jを管理 r10…変数mを管理


r14…代入、計算用の変数を管理 r15…アドレスの計算結果を管理


r16…変数xyを管理 r17…変数xを管理 r18…変数yを管理


r24…iのfor文の条件を管理


r29…スタックポインタ


~xor128関数~


r2…関数の戻り値


r4…引数a


r11…変数tを管理


~pow関数~


r2…関数の戻り値


r8…変数bitを管理

サンプルコード4

		#ゼロレジスタの用意
		XOR	r0, r0,	r0
		#変数mの初期化
		ADDI	r10,	r0,	0
		#スタックポインタの初期化
		ADDI	r29,	r0,	1024
	
		#32bit定数の用意
		ADDI	r15,	r0,	512
		#static x
		LUI		r14,	1883
		ORI	r14,	r14,	52501
		SW	r14,	0(r15)
		#static y
		LUI		r14,	5530
		ORI	r14,	r14,	21989
		SW	r14,	4(r15)
		#static z
		LUI		r14,	7954
		ORI	r14,	r14,	15285
		SW	r14,	8(r15)
		#static w
		LUI		r14,	1353
		ORI	r14,	r14,	4915
		SW	r14,	12(r15)
		#static pow(0x7fff)
		LUI		r14,	16383
		ORI	r14,	r14,	1
		SW	r14,	16(r15)
	
		#i = 0の変換
		ADDI	r8,	r0,	0
		#iの上限となる定数
		ADDI	r24,	r0,	400
	
	FOR0S:						#for (i = 0; i < 400; i++)
		#i < 400(400 <= i)の変換
		BLE	r24,	r8,	FOR0E
	
		#forブロック内
		#Xorshiftと呼ばれる方法を、関数xor128として使い、乱数を生成
		JAL	_xor128
		ADD	r16,	r0,	r2
		SRL	r14,	r16,	16
		ANDI	r17,	r14,	65535
		ANDI	r18,	r16,	65535
	
		#オーバーフロー防止のため2でわる
		SRL	r17,	r17,	1
		SRL	r18,	r18,	1
	
		#2乗を関数powで計算
		#pow(x)
		ADD	r4,	r0,	r17
		SW	r8,	0(r29)
		#スタックポインタの引き算(定数ではビットが足りないことに注意)
		ADDI	r14,	r0,	4
		SUB	r29,	r29,	r14
		JAL	_pow
		ADDI	r29,	r29,	4
		LW	r8,	0(r29)
		ADD	r17,	r0,	r2
	
		#pow(y)
		ADD	r4,	r0,	r18
		SW	r8,	0(r29)
		ADDI	r14,	r0,	4
		SUB	r29,	r29,	r14
		JAL	_pow
		ADDI	r29,	r29,	4
		LW	r8,	0(r29)
		ADD	r17,	r2,	r17
	
		#mul16(0x7fff)のロード
		ADDI	r15,	r0,	528
		LW	r18,	0(r15)
		BLE	r18,	r17,	IF0E		#if (pow(x) + pow(y) <= pow(0x7fff))
	
		#ifブロック内
		ADDI	r10,	r10,	1
	
	IF0E:
		#i++の変換
		ADDI	r8,	r8,	1
		J	FOR0S
	
	FOR0E:
		#変数xの再利用
		ADDI	r17,	r0,	0
	
		#iを負の数として扱えないので、アセンブリではすべて1を加算して扱うものとする
		#i = 7[+1]の変換
		ADDI	r8,	r0,	8
		#iの下限となる定数
		ADDI	r24,	r0,	0
	
	#mを16進数で表現する10進数として出力
	FOR1S:						#(i = 7[+1]; i[+1] >= 0; i--)
		#i[+1] >= 0(i <= 0)の変換
		BLE	r8,	r0,	FOR1E
	
		#forブロック内
		#変数yの再利用
		ADDI	r18,	r0,	1
	
		#j = 0の変換
		ADDI	r9,	r0,	0
	
	FOR2S:						#for (j = 0; j < i[+1]; j++)
		#j < i[+1](i <= (j + 1))の変換
		ADDI	r14,	r9,	1
		BLE	r8,	r14,	FOR2E
	
		#forブロック内
		SLL	r14,	r18,	3
		SLL	r18,	r18,	1
		ADD	r18,	r14,	r18
	
		#j++の変換
		ADDI	r9,	r9,	1
		J	FOR2S
	
	FOR2E:
		SLL	r17,	r17,	4
	
	WHILE0S:					#while (m >= y)
		#m >= y(m < y)の変換
		BLT	r10,	r18,	WHILE0E
	
		#whileブロック内
		SUB	r10,	r10,	r18
		ADDI	r17,	r17,	1
	
		J	WHILE0S
	
	WHILE0E:
		#i[+1]--の変換
		ADDI	r14,	r0,	1
		SUB	r8,	r8,	r14
		J	FOR1S
	
	FOR1E:
		#return x(mul16(0x7fff)の隣に書き込み)
		ADDI	r15,	r0,	528
		SW	r17,	4(r15)
		J	END
	
	_pow:						#int pow(int a)
		#変数sumの初期化
		ADDI,	r2,	r0,	0
		#bit = 0x8000の変換
		ORI	r8,	r0,	32768
	
	FORPS:						#for (bit = 0x8000; bit; bit = bit >> 1)
		#bit(bit != 0)の変換
		BEQ	r0,	r8,	FORPE
	
		#forブロック内
		SLL	r2,	r2,	1
	
		AND	r14,	r4,	r8
		BEQ	r0,	r14,	IFPE		#if (a16 & bit)
	
		#ifブロック内
		ADD	r2,	r2,	r4
	
	IFPE:
		#bit = bit >> 1の変換
		SRL	r8,	r8,	1
		J	FORPS
	
	FORPE:
		#return sum
		JR	r31
	
	_xor128:					#int xor128()
		#_xの読みこみ
		ADDI	r15,	r0,	512
		LW	r14,	0(r15)
		#x ^ (x << 11)の計算
		SLL	r11,	r14,	11
		XOR	r11,	r11,	r14
		#_yの読み込み、_xへの書き込み(_xの次の行であることに注意、以下定数以外繰り返し)
		LW	r14,	4(r15)
		SW	r14,	0(r15)
		LW	r14,	8(r15)
		SW	r14,	4(r15)
		LW	r14,	12(r15)
		SW	r14,	8(r15)
		
		#(w ^ (w >> 19))の計算
		SRL	r2,	r14,	19
		XOR	r14,	r2,	r14
		#(t ^ (t >> 8))
		SRL	r2,	r11,	8
		XOR	r11,	r11,	r2
		XOR r2,	r11,	r14
		SW	r2,	12(r15)
	
		#return w
		JR	r31
	
	END:
		HALT

バイナリコード4

filesample4.bin

メモリの532番地に0x0315が出力されているはずです。

最終課題


実行後のクロック数がなるべく短くなるように、 パイプライン化、スーパースカラ化など、自分のアーキテクチャを改良してみてください。

バイナリコード

filesamplef.bin


添付ファイル: filesamplef.bin 55件 [詳細] filesample4.bin 59件 [詳細] filesample3.bin 66件 [詳細] filesample2.bin 57件 [詳細] filesample1.bin 61件 [詳細] fileas.pl 68件 [詳細] fileassembly_1.png 85件 [詳細] fileassembly_0.png 214件 [詳細]