スタックで遊ぶ
これはEsolang Advent Calendar 2011(http://atnd.org/events/22463)の6日目の記事です。
難解言語でもなんでもないのですが、少しC言語でスタックをいじって遊んでみました。
いじるものといっても変数とリターンアドレスしか無いので、今回はリターンアドレスを戻してループ（再帰）を再現してみました。
この記事のソースコードはUbuntu11.04,gcc4.5.2でのみ動作確認しました。もしかしたらこの記事のソースをコンパイルしても動かないこともあるかもしれません。ご了承ください。
階乗
再帰といえば階乗です。まずは階乗を実装してみました。
#include <stdio.h> void factorial(int n) { int a[1]; if(n < 1) { return; } a[0x2] -= 0xc; --a[0x8]; a[0x9] *= n; } int main(void) { int n; int result = 1; int t; printf("input a number:"); scanf("%d", &n); t = n; factorial(t); printf("%d! = %d\n", n, result); return 0; }
実行結果は以下のとおりです。
input a number:8 8! = 40320
ちなみに、実行ファイルをgdbでdisassembleしたものと最初にfactorialが呼ばれた直後のスタックの内容が以下です。
main
(gdb) disas main Dump of assembler code for function main: 0x08048441 <+0>: push %ebp 0x08048442 <+1>: mov %esp,%ebp 0x08048444 <+3>: and $0xfffffff0,%esp 0x08048447 <+6>: sub $0x20,%esp 0x0804844a <+9>: movl $0x1,0x1c(%esp) 0x08048452 <+17>: mov $0x8048570,%eax 0x08048457 <+22>: mov %eax,(%esp) 0x0804845a <+25>: call 0x8048338 <printf@plt> 0x0804845f <+30>: mov $0x8048580,%eax 0x08048464 <+35>: lea 0x14(%esp),%edx 0x08048468 <+39>: mov %edx,0x4(%esp) 0x0804846c <+43>: mov %eax,(%esp) 0x0804846f <+46>: call 0x8048348 <__isoc99_scanf@plt> 0x08048474 <+51>: mov 0x14(%esp),%eax 0x08048478 <+55>: mov %eax,0x18(%esp) 0x0804847c <+59>: mov 0x18(%esp),%eax 0x08048480 <+63>: mov %eax,(%esp) 0x08048483 <+66>: call 0x8048414 <factorial> 0x08048488 <+71>: mov 0x14(%esp),%edx 0x0804848c <+75>: mov $0x8048583,%eax 0x08048491 <+80>: mov 0x1c(%esp),%ecx 0x08048495 <+84>: mov %ecx,0x8(%esp) 0x08048499 <+88>: mov %edx,0x4(%esp) 0x0804849d <+92>: mov %eax,(%esp) 0x080484a0 <+95>: call 0x8048338 <printf@plt> 0x080484a5 <+100>: mov $0x0,%eax 0x080484aa <+105>: leave 0x080484ab <+106>: ret End of assembler dump.
factorial
(gdb) disas factorial Dump of assembler code for function factorial: 0x08048414 <+0>: push %ebp 0x08048415 <+1>: mov %esp,%ebp 0x08048417 <+3>: sub $0x10,%esp 0x0804841a <+6>: cmpl $0x0,0x8(%ebp) 0x0804841e <+10>: jle 0x804843e <factorial+42> 0x08048420 <+12>: mov 0x4(%ebp),%eax 0x08048423 <+15>: sub $0xc,%eax 0x08048426 <+18>: mov %eax,0x4(%ebp) 0x08048429 <+21>: mov 0x20(%ebp),%eax 0x0804842c <+24>: sub $0x1,%eax 0x0804842f <+27>: mov %eax,0x20(%ebp) 0x08048432 <+30>: mov 0x24(%ebp),%eax 0x08048435 <+33>: imul 0x8(%ebp),%eax 0x08048439 <+37>: mov %eax,0x24(%ebp) 0x0804843c <+40>: jmp 0x804843f <factorial+43> 0x0804843e <+42>: nop 0x0804843f <+43>: leave 0x08048440 <+44>: ret End of assembler dump.
最初にfactorialが呼ばれた直後のスタック（入力は8）
(gdb) x/32x $ebp 0xbffff688: 0xbffff6b8 0x08048488 0x00000008 0xbffff6a4 0xbffff698: 0x0028bff4 0xbffff6b8 0x0015ed35 0x00000008 0xbffff6a8: 0x00000008 0x00000001 0x080484b0 0x00000000 0xbffff6b8: 0xbffff738 0x00145e37 0x00000001 0xbffff764 0xbffff6c8: 0xbffff76c 0x0012e414 0xffffffff 0x0012cff4 0xbffff6d8: 0x0804824b 0x00000001 0xbffff720 0x0011da31 0xbffff6e8: 0x0012dad0 0xb7fffb48 0x00000001 0x0028bff4 0xbffff6f8: 0x00000000 0x00000000 0xbffff738 0x7f063c5a
最大公約数
最大公約数(Greatest Common Divisor)を求めるプログラムも作ってみました。
#include <stdio.h> void gcd(int m, int n) { int a[1]; if(m < n) { m ^= n; n ^= m; m ^= n; } if(n <= 0) { a[0xc] = m; return; } a[0x2] -= 0x14; a[0xd] = m % n; a[0x0e] = n; } int main(void) { int a, b; int result; int m, n; printf("Input two numbers:"); scanf("%d %d", &a, &b); m = a; n = b; gcd(m, n); printf("gcd(%d, %d) = %d\n", a, b, result); return 0; }
実行結果は次のとおり。
Input two numbers:12 18 gcd(12, 18) = 6
階乗と同じく、実行ファイルをgdbでdisassembleしたものと最初にgcdが呼ばれた直後のスタックの内容が以下です。
main
(gdb) disas main Dump of assembler code for function main: 0x08048463 <+0>: push %ebp 0x08048464 <+1>: mov %esp,%ebp 0x08048466 <+3>: and $0xfffffff0,%esp 0x08048469 <+6>: push %ebx 0x0804846a <+7>: sub $0x3c,%esp 0x0804846d <+10>: mov $0x80485b0,%eax 0x08048472 <+15>: mov %eax,(%esp) 0x08048475 <+18>: call 0x8048338 <printf@plt> 0x0804847a <+23>: mov $0x80485c3,%eax 0x0804847f <+28>: lea 0x1c(%esp),%edx 0x08048483 <+32>: mov %edx,0x8(%esp) 0x08048487 <+36>: lea 0x20(%esp),%edx 0x0804848b <+40>: mov %edx,0x4(%esp) 0x0804848f <+44>: mov %eax,(%esp) 0x08048492 <+47>: call 0x8048348 <__isoc99_scanf@plt> 0x08048497 <+52>: mov 0x20(%esp),%eax 0x0804849b <+56>: mov %eax,0x2c(%esp) 0x0804849f <+60>: mov 0x1c(%esp),%eax 0x080484a3 <+64>: mov %eax,0x28(%esp) 0x080484a7 <+68>: mov 0x28(%esp),%eax 0x080484ab <+72>: mov %eax,0x4(%esp) 0x080484af <+76>: mov 0x2c(%esp),%eax 0x080484b3 <+80>: mov %eax,(%esp) 0x080484b6 <+83>: call 0x8048414 <gcd> 0x080484bb <+88>: mov 0x1c(%esp),%ecx 0x080484bf <+92>: mov 0x20(%esp),%edx 0x080484c3 <+96>: mov $0x80485c9,%eax 0x080484c8 <+101>: mov 0x24(%esp),%ebx 0x080484cc <+105>: mov %ebx,0xc(%esp) 0x080484d0 <+109>: mov %ecx,0x8(%esp) 0x080484d4 <+113>: mov %edx,0x4(%esp) 0x080484d8 <+117>: mov %eax,(%esp) 0x080484db <+120>: call 0x8048338 <printf@plt> 0x080484e0 <+125>: mov $0x0,%eax 0x080484e5 <+130>: add $0x3c,%esp 0x080484e8 <+133>: pop %ebx 0x080484e9 <+134>: mov %ebp,%esp 0x080484eb <+136>: pop %ebp 0x080484ec <+137>: ret End of assembler dump.
gcd
(gdb) disas gcd Dump of assembler code for function gcd: 0x08048414 <+0>: push %ebp 0x08048415 <+1>: mov %esp,%ebp 0x08048417 <+3>: sub $0x10,%esp 0x0804841a <+6>: mov 0x8(%ebp),%eax 0x0804841d <+9>: cmp 0xc(%ebp),%eax 0x08048420 <+12>: jge 0x8048434 <gcd+32> 0x08048422 <+14>: mov 0xc(%ebp),%eax 0x08048425 <+17>: xor %eax,0x8(%ebp) 0x08048428 <+20>: mov 0x8(%ebp),%eax 0x0804842b <+23>: xor %eax,0xc(%ebp) 0x0804842e <+26>: mov 0xc(%ebp),%eax 0x08048431 <+29>: xor %eax,0x8(%ebp) 0x08048434 <+32>: cmpl $0x0,0xc(%ebp) 0x08048438 <+36>: jg 0x8048442 <gcd+46> 0x0804843a <+38>: mov 0x8(%ebp),%eax 0x0804843d <+41>: mov %eax,0x2c(%ebp) 0x08048440 <+44>: jmp 0x8048461 <gcd+77> 0x08048442 <+46>: mov 0x4(%ebp),%eax 0x08048445 <+49>: sub $0x14,%eax 0x08048448 <+52>: mov %eax,0x4(%ebp) 0x0804844b <+55>: mov 0x8(%ebp),%eax 0x0804844e <+58>: mov %eax,%edx 0x08048450 <+60>: sar $0x1f,%edx 0x08048453 <+63>: idivl 0xc(%ebp) 0x08048456 <+66>: mov %edx,%eax 0x08048458 <+68>: mov %eax,0x30(%ebp) 0x0804845b <+71>: mov 0xc(%ebp),%eax 0x0804845e <+74>: mov %eax,0x34(%ebp) 0x08048461 <+77>: leave 0x08048462 <+78>: ret End of assembler dump.
最初にgcdが呼ばれた直後のスタック（入力は12 18)
(gdb) x/32x $ebp 0xbffff678: 0xbffff6c8 0x080484bb 0x0000000c 0x00000012 0xbffff688: 0xbffff69c 0x08048304 0x0028bff4 0x08049ff4 0xbffff698: 0xbffff6c8 0x00000012 0x0000000c 0x0028c324 0xbffff6a8: 0x00000012 0x0000000c 0x0015ed35 0x0011ea50 0xbffff6b8: 0x080484fb 0x0028bff4 0x080484f0 0x00000000 0xbffff6c8: 0xbffff748 0x00145e37 0x00000001 0xbffff774 0xbffff6d8: 0xbffff77c 0x0012e414 0xffffffff 0x0012cff4 0xbffff6e8: 0x0804824b 0x00000001 0xbffff730 0x0011da31
for, while, do, goto, 再帰を使わずに反復処理ができました。ちょっと反則臭いですが。
