long longって、どうやって計算するの？

投稿記事 by **みけCAT** » 12年前

前の日記で、型による演算速度の実験をしました。
ここで素朴な疑問：レジスタは32ビットなのに、どうやって64ビットの演算をするの？
これがわかれば、多倍長計算の開発にもつながるかもしれない！な～んてね。（CV:大亀あすか）
というわけで、さっそく実験。
（ちゃららら）C/C++ to Assembly～～～！（CV：大山のぶ代）
カキカキ

CODE:

#include 

int main(void) {
	long long a;
	long long b;
	long long c;
	a=1234567890ll;
	b=9876543210ll;
	c=a*b;
	printf("%lld\n",c);
	c=b/a;
	printf("%lld\n",c);
	c=a+b;
	printf("%lld\n",c);
	c=b-a;
	printf("%lld\n",c);
	return 0;
}

ぽちっとな
・・・
( ﾟ∀ﾟ)つ【imulq,idivq,addq,subq】
▂▅▇█▓▒░(’ω’)░▒▓█▇▅▂ うわあああああああ

それはチートだろ…というわけでローカルのコンパイラ(gcc4.7.2)で試してみる。
上のコードでは混ざってしまいわかりにくいので、関数に分離したものをコンパイルする。

CODE:

long long add(long long a,long long b) {
	return a+b;
}

long long sub(long long a,long long b) {
	return a-b;
}

long long mul(long long a,long long b) {
	return a*b;
}

long long div(long long a,long long b) {
	return a/b;
}

long long mod(long long a,long long b) {
	return a%b;
}

► スポイラーを表示

CODE:

	.file	"lltest2.c"
	.text
	.globl	_add
	.def	_add;	.scl	2;	.type	32;	.endef
_add:
LFB0:
	.cfi_startproc
	pushl	%ebp
	.cfi_def_cfa_offset 8
	.cfi_offset 5, -8
	movl	%esp, %ebp
	.cfi_def_cfa_register 5
	pushl	%ebx
	subl	$20, %esp
	.cfi_offset 3, -12
	movl	8(%ebp), %eax
	movl	%eax, -16(%ebp)
	movl	12(%ebp), %eax
	movl	%eax, -12(%ebp)
	movl	16(%ebp), %eax
	movl	%eax, -24(%ebp)
	movl	20(%ebp), %eax
	movl	%eax, -20(%ebp)
	movl	-24(%ebp), %eax
	movl	-20(%ebp), %edx
	movl	-16(%ebp), %ecx
	movl	-12(%ebp), %ebx
	addl	%ecx, %eax
	adcl	%ebx, %edx
	addl	$20, %esp
	popl	%ebx
	.cfi_restore 3
	popl	%ebp
	.cfi_restore 5
	.cfi_def_cfa 4, 4
	ret
	.cfi_endproc
LFE0:
	.globl	_sub
	.def	_sub;	.scl	2;	.type	32;	.endef
_sub:
LFB1:
	.cfi_startproc
	pushl	%ebp
	.cfi_def_cfa_offset 8
	.cfi_offset 5, -8
	movl	%esp, %ebp
	.cfi_def_cfa_register 5
	pushl	%ebx
	subl	$20, %esp
	.cfi_offset 3, -12
	movl	8(%ebp), %eax
	movl	%eax, -16(%ebp)
	movl	12(%ebp), %eax
	movl	%eax, -12(%ebp)
	movl	16(%ebp), %eax
	movl	%eax, -24(%ebp)
	movl	20(%ebp), %eax
	movl	%eax, -20(%ebp)
	movl	-24(%ebp), %ecx
	movl	-20(%ebp), %ebx
	movl	-16(%ebp), %eax
	movl	-12(%ebp), %edx
	subl	%ecx, %eax
	sbbl	%ebx, %edx
	addl	$20, %esp
	popl	%ebx
	.cfi_restore 3
	popl	%ebp
	.cfi_restore 5
	.cfi_def_cfa 4, 4
	ret
	.cfi_endproc
LFE1:
	.globl	_mul
	.def	_mul;	.scl	2;	.type	32;	.endef
_mul:
LFB2:
	.cfi_startproc
	pushl	%ebp
	.cfi_def_cfa_offset 8
	.cfi_offset 5, -8
	movl	%esp, %ebp
	.cfi_def_cfa_register 5
	subl	$16, %esp
	movl	8(%ebp), %eax
	movl	%eax, -8(%ebp)
	movl	12(%ebp), %eax
	movl	%eax, -4(%ebp)
	movl	16(%ebp), %eax
	movl	%eax, -16(%ebp)
	movl	20(%ebp), %eax
	movl	%eax, -12(%ebp)
	movl	-4(%ebp), %eax
	movl	%eax, %edx
	imull	-16(%ebp), %edx
	movl	-12(%ebp), %eax
	imull	-8(%ebp), %eax
	leal	(%edx,%eax), %ecx
	movl	-16(%ebp), %eax
	mull	-8(%ebp)
	addl	%edx, %ecx
	movl	%ecx, %edx
	leave
	.cfi_restore 5
	.cfi_def_cfa 4, 4
	ret
	.cfi_endproc
LFE2:
	.def	___divdi3;	.scl	2;	.type	32;	.endef
	.globl	_div
	.def	_div;	.scl	2;	.type	32;	.endef
_div:
LFB3:
	.cfi_startproc
	pushl	%ebp
	.cfi_def_cfa_offset 8
	.cfi_offset 5, -8
	movl	%esp, %ebp
	.cfi_def_cfa_register 5
	subl	$40, %esp
	movl	8(%ebp), %eax
	movl	%eax, -16(%ebp)
	movl	12(%ebp), %eax
	movl	%eax, -12(%ebp)
	movl	16(%ebp), %eax
	movl	%eax, -24(%ebp)
	movl	20(%ebp), %eax
	movl	%eax, -20(%ebp)
	movl	-24(%ebp), %eax
	movl	-20(%ebp), %edx
	movl	%eax, 8(%esp)
	movl	%edx, 12(%esp)
	movl	-16(%ebp), %eax
	movl	-12(%ebp), %edx
	movl	%eax, (%esp)
	movl	%edx, 4(%esp)
	call	___divdi3
	leave
	.cfi_restore 5
	.cfi_def_cfa 4, 4
	ret
	.cfi_endproc
LFE3:
	.def	___moddi3;	.scl	2;	.type	32;	.endef
	.globl	_mod
	.def	_mod;	.scl	2;	.type	32;	.endef
_mod:
LFB4:
	.cfi_startproc
	pushl	%ebp
	.cfi_def_cfa_offset 8
	.cfi_offset 5, -8
	movl	%esp, %ebp
	.cfi_def_cfa_register 5
	pushl	%ebx
	subl	$36, %esp
	.cfi_offset 3, -12
	movl	8(%ebp), %eax
	movl	%eax, -16(%ebp)
	movl	12(%ebp), %eax
	movl	%eax, -12(%ebp)
	movl	16(%ebp), %eax
	movl	%eax, -24(%ebp)
	movl	20(%ebp), %eax
	movl	%eax, -20(%ebp)
	movl	-16(%ebp), %eax
	movl	-12(%ebp), %edx
	movl	-24(%ebp), %ecx
	movl	-20(%ebp), %ebx
	movl	%ecx, 8(%esp)
	movl	%ebx, 12(%esp)
	movl	%eax, (%esp)
	movl	%edx, 4(%esp)
	call	___moddi3
	addl	$36, %esp
	popl	%ebx
	.cfi_restore 3
	popl	%ebp
	.cfi_restore 5
	.cfi_def_cfa 4, 4
	ret
	.cfi_endproc
LFE4:

読める！読めるぞ！
でも、本番の解析に取り掛かる前に、前提を確認しておきましょう。
まず、関数の引数の格納位置を確認します。
printfの前の処理から、関数の引数は前から順に%esp周辺に格納されそうなことがわかりますが、どの位置に格納されるのでしょうか。

CODE:

#include 

asm(
	"_zikken0:\n\t"
	"movl (%esp),%eax\n\t"
	"ret\n\t"
);
extern int zikken0(long long a);
asm(
	"_zikken1:\n\t"
	"movl 4(%esp),%eax\n\t"
	"ret\n\t"
);
extern int zikken1(long long a);
asm(
	"_zikken2:\n\t"
	"movl 8(%esp),%eax\n\t"
	"ret\n\t"
);
extern int zikken2(long long a);
asm(
	"_zikken3:\n\t"
	"movl 12(%esp),%eax\n\t"
	"ret\n\t"
);
extern int zikken3(long long a);

int main(void) {
	printf("%08x\n",zikken0(0x123456789abcdef0ll));
	printf("%08x\n",zikken1(0x123456789abcdef0ll));
	printf("%08x\n",zikken2(0x123456789abcdef0ll));
	printf("%08x\n",zikken3(0x123456789abcdef0ll));
	return 0;
}

実行結果はこうなりました。

CODE:

これから、引数の格納は4(%esp)から始まり、long long型の値は下位32ビットを先に格納することがわかります。
しかし、関数の先頭でpushlしていることから、%espがずれることが予想できます。
どっち向きにずれるのでしょうか？

CODE:

#include 

asm(
	"_pushkensyou:\n\t"
	"movl %esp,%eax\n\t"
	"pushl %ebp\n\t"
	"subl %esp,%eax\n\t" /* eax=eax-esp */
	"popl %ebp\n\t"
	"ret\n\t"
);

extern int pushkensyou(void);

int main(void) {
	printf("%d\n",pushkensyou());
	return 0;
}

このコードを実行すると「4」と表示されたことから、1回pushlしたあとの%espはpushlする前より4少ないことがわかります。
このことから、先ほどのコードのメモリの配置図はこのようになることがわかります。

CODE:

+--------+--------+--------+--------+--------+--------+
|[t0]    |[t1]    |[t2]    |[t3]    |[t4]    |[t5]    |
+--------+--------+--------+--------+--------+--------+
 -24(%ebp)-20(%ebp)-16(%ebp)-12(%ebp) -8(%ebp) -4(%ebp)

+--------+--------+--------+--------+--------+--------+
|        |        |[a1]    |[a2]    |[b1]    |[b2]    |
+--------+--------+--------+--------+--------+--------+
 %ebp     4(%ebp)  8(%ebp)  12(%ebp) 16(%ebp) 20(%ebp)

a1がaの下位32ビット、a2がaの上位32ビット、b1がbの下位32ビット、b2がbの上位32ビットです。
t0～t5は計算用領域のようです。

まずは、足し算。

CODE:

movl	8(%ebp), %eax
movl	%eax, -16(%ebp)  a1→t2
movl	12(%ebp), %eax
movl	%eax, -12(%ebp)  a2→t3
movl	16(%ebp), %eax
movl	%eax, -24(%ebp)  b1→t0
movl	20(%ebp), %eax
movl	%eax, -20(%ebp)  b2→t1
movl	-24(%ebp), %eax  b1→eax
movl	-20(%ebp), %edx  b2→edx
movl	-16(%ebp), %ecx  a1→ecx
movl	-12(%ebp), %ebx  a2→ebx
addl	%ecx, %eax       b1+a1→eax
adcl	%ebx, %edx       b2+a2+(b1+a1の繰り上がり)→edx

値のコピーに二度手間をかけていますが、筆算と同じです。
また、long long型の戻り値は%eaxに下位32ビット、%edxに上位32ビットが格納されることがわかります。

引き算も、足し算とほとんど同じです。

CODE:

//略(足し算と共通)
movl	-24(%ebp), %ecx  b1→ecx
movl	-20(%ebp), %ebx  b2→ebx
movl	-16(%ebp), %eax  a1→eax
movl	-12(%ebp), %edx  a2→edx
subl	%ecx, %eax       a1-b1→eax
sbbl	%ebx, %edx       a2-b2-(a1-b1の繰り下がり)→edx

筆算です。しかし、なぜ足し算の時は足す数と足される数が逆転していたのでしょうか？

次に、掛け算です。

CODE:

movl	8(%ebp), %eax
movl	%eax, -8(%ebp)     a1→t4
movl	12(%ebp), %eax
movl	%eax, -4(%ebp)     a2→t5
movl	16(%ebp), %eax
movl	%eax, -16(%ebp)    b1→t2
movl	20(%ebp), %eax
movl	%eax, -12(%ebp)    b2→t3
movl	-4(%ebp), %eax     a2→eax
movl	%eax, %edx         a2→edx
imull	-16(%ebp), %edx    b1*a2→edx
movl	-12(%ebp), %eax    b2→eax
imull	-8(%ebp), %eax     a1*b2→eax
leal	(%edx,%eax), %ecx  edx+eax→ecx
movl	-16(%ebp), %eax    b1→eax
mull	-8(%ebp)           eax*a1→edx,eax
addl	%edx, %ecx         ecx+edx→ecx
movl	%ecx, %edx         ecx→edx

一見複雑ですが、よく見ると次の式で計算していることがわかります。
(a1+a2*k)*(b1+b2*k)=a1*a2+(a1*b2+b1*a2)*k+(a2*b2)*k^2　ただしk=2^32
k^2の項は、64ビットの範囲を超えるので無視できることがわかります。

では、割り算を見てみましょう。

CODE:

movl	8(%ebp), %eax
movl	%eax, -16(%ebp)
movl	12(%ebp), %eax
movl	%eax, -12(%ebp)
movl	16(%ebp), %eax
movl	%eax, -24(%ebp)
movl	20(%ebp), %eax
movl	%eax, -20(%ebp)
movl	-24(%ebp), %eax
movl	-20(%ebp), %edx
movl	%eax, 8(%esp)
movl	%edx, 12(%esp)
movl	-16(%ebp), %eax
movl	-12(%ebp), %edx
movl	%eax, (%esp)
movl	%edx, 4(%esp)
call	___divdi3

(´･｀ ;) こ… これ…これは…………サブルーチンだあああああああああああ
┗(^o^)┛wwWww┏(^o^)┓ドコドコドコドコwwwWWWwwWwwwwW

剰余も同様にサブルーチンでした。

足し算と引き算の計算方法は多倍長計算に応用できそうですが、掛け算と割り算は無理そうです。
といっても足し算と引き算もインラインアセンブリを書く事になりますが…

ちなみに
コードは省略しますが、ビットAND、OR、XORは上位下位それぞれ演算するだけです。
シフト演算は、ほかのレジスタからシフトインできるshrdl、shldl命令があるようです。

ご清聴ありがとうございました。

【追記】
これが___divdi3の正体のようですね。解析はまたこんど…
http://www.ic.unicamp.br/~islene/2s2008 ... 2/divdi3.c

		8月 2025
日	月	火	水	木	金	土
					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