Author Topic: recursive hanoi function with nasm  (Read 2737 times)

Offline zahit

  • New Member
  • Posts: 1
recursive hanoi function with nasm
« on: November 11, 2010, 08:55:14 AM »
hi all,

i've been trying to develop recursive hanoi function with nasm. I use this c code as sample.

Code: [Select]
void hanoi_rec(int n_disc, int head, int middle, int tail, int silent){
     if (n_disc == 1){
      if(silent != 1)
           printf("%d --> %d\n", head, tail);
     }
     else{
      hanoi_rec(n_disc -1, head, tail, middle, silent);
      if(silent != 1)
           printf("%d --> %d\n", head, tail);
      hanoi_rec(n_disc -1, middle, head, tail, silent);
     }
}

and here is my assembly code

Code: [Select]
global asm_hanoi_rec
asm_hanoi_rec:

push ebp
mov ebp, esp
mov eax, [ebp+8]
mov ebx, [ebp+24]
cmp eax, 1
jne L5
cmp ebx, 1
je L7
push dword[ebp+20]
push dword[ebp+12]
push han1
call printf
add esp, 12
jmp L7
L5:
     dec eax
     push ebx
     push dword[ebp+16]
     push dword[ebp+20]
     push dword[ebp+12]
     push eax
     call asm_hanoi_rec
     cmp ebx, 1
     je L6
     push dword[ebp+20]
     push dword[ebp+12]
     push han1
     call printf
     add esp, 12
L6:
     mov eax, [ebp+8]
     mov ebx, [ebp+24]
     dec eax
     push ebx
     push dword[ebp+20]
     push dword[ebp+12]
     push dword[ebp+16]
     push eax
     call asm_hanoi_rec
L7:
     mov esp, ebp
     pop ebp
     ret 20

It work fine but when it's finished a "stack smashing detected" error appears in the console, and the program is aborted. here is the error


*** stack smashing detected ***: ./exp2 terminated
======= Backtrace: =========
/lib/libc.so.6(__fortify_fail+0x50)[0x25e980]
/lib/libc.so.6(+0xe592a)[0x25e92a]
./exp2[0x8049341]
/lib/libc.so.6(__libc_start_main+0xe7)[0x18fce7]
./exp2[0x8048551]
======= Memory map: ========
00110000-00111000 rwxp 00000000 00:00 0
00174000-00175000 r-xp 00000000 00:00 0          [vdso]
00179000-002d0000 r-xp 00000000 08:01 133794     /lib/libc-2.12.1.so
002d0000-002d1000 ---p 00157000 08:01 133794     /lib/libc-2.12.1.so
002d1000-002d3000 r-xp 00157000 08:01 133794     /lib/libc-2.12.1.so
002d3000-002d4000 rwxp 00159000 08:01 133794     /lib/libc-2.12.1.so
002d4000-002d7000 rwxp 00000000 00:00 0
00781000-0079b000 r-xp 00000000 08:01 133437     /lib/libgcc_s.so.1
0079b000-0079c000 r-xp 00019000 08:01 133437     /lib/libgcc_s.so.1
0079c000-0079d000 rwxp 0001a000 08:01 133437     /lib/libgcc_s.so.1
008e3000-008e5000 rwxp 00000000 00:00 0
00ccf000-00cd0000 rwxp 00000000 00:00 0
00fa9000-00fc5000 r-xp 00000000 08:01 130831     /lib/ld-2.12.1.so
00fc5000-00fc6000 r-xp 0001b000 08:01 130831     /lib/ld-2.12.1.so
00fc6000-00fc7000 rwxp 0001c000 08:01 130831     /lib/ld-2.12.1.so
08048000-0804a000 r-xp 00000000 08:01 160376     /home/zahit/Documents/exp2
0804a000-0804b000 r-xp 00001000 08:01 160376     /home/zahit/Documents/exp2
0804b000-0804c000 rwxp 00002000 08:01 160376     /home/zahit/Documents/exp2
081c4000-081e5000 rwxp 00000000 00:00 0          [heap]
bfe48000-bfe69000 rwxp 00000000 00:00 0          [stack]
Aborted

can you find ot why? any help is much appreciated. thanks..

Offline Bryant Keller

  • Forum Moderator
  • Full Member
  • *****
  • Posts: 360
  • Country: us
    • About Bryant Keller
Re: recursive hanoi function with nasm
« Reply #1 on: November 11, 2010, 09:37:05 AM »
Without putting too much study into your code, I came up with this:
Code: [Select]
;; How is this being called? are you invoking this from C?
;; If so, this is a stdcall function, you should change the
;; prototype from cdecl to stdcall (this varies from compiler
;; to compiler)

global asm_hanoi_rec
asm_hanoi_rec:

push ebp
mov ebp, esp
mov eax, [ebp+8]
mov ebx, [ebp+24]
cmp eax, 1
jne L5
cmp ebx, 1
je L7
push eax ;; Save EAX for future use
push dword[ebp+20]
push dword[ebp+12]
push han1
call printf ;; EAX is trashed here..
add esp, 12
pop eax ;; Restore EAX
jmp L7
L5:
     push eax
     push ebx
     dec eax
     push ebx
     push dword[ebp+16]
     push dword[ebp+20]
     push dword[ebp+12]
     push eax
     call asm_hanoi_rec
     cmp ebx, 1
     je L6
     push dword[ebp+20]
     push dword[ebp+12]
     push han1
     call printf
     add esp, 12
L6:
;     mov eax, [ebp+8]
;     mov ebx, [ebp+24]
     pop ebx
     pop eax
     dec eax
     push ebx
     push dword[ebp+20]
     push dword[ebp+12]
     push dword[ebp+16]
     push eax
     call asm_hanoi_rec
L7:
     mov esp, ebp
     pop ebp
     ret 20

I haven't tested it to see if it corrects the error in question or not, I just thought I would point out a few things that were really popping out at me.

EDIT: Design wise, I would suggest trying to simply your procedure. maybe something like:
Code: [Select]
void hanoi_rec(int n_disc, int head, int middle, int tail, int silent){
if( n_disc != 1 ) {
hanoi_rec( n_disc -1, head, tail, middle, silent );
hanoi_rec( n_disc -1, middle, head, tail, silent );
}
if( silent != 1 ) printf( "%d --> %d\n", head, tail );
}

Which would result in:

Code: [Select]
[BITS 32]
[CPU 486]

extern printf
global _start

; C Version
;void hanoi_rec(int n_disc, int head, int middle, int tail, int silent){
; if( n_disc != 1 ) {
; hanoi_rec( n_disc -1, head, tail, middle, silent );
; hanoi_rec( n_disc -1, middle, head, tail, silent );
; }
; if( silent != 1 ) printf( "%d --> %d\n", head, tail );
;}

section .data

strFmt: DB "%d --> %d", 10, 0

section .text

_start:
xor eax, eax
push dword eax
push dword 3
push dword 2
push dword 1
push dword 5
call hanoi_rec

xor eax, eax
xor ebx, ebx
inc eax
int 80h

hanoi_rec:
%define _n_disc ebp + 8
%define _head ebp + 12
%define _middle ebp + 16
%define _tail ebp + 20
%define _silent ebp + 24

enter 0, 0

mov eax, [_n_disc]
cmp eax, 1
je .endif_1

dec eax

push dword [_silent]
push dword [_middle]
push dword [_tail]
push dword [_head]
push eax

push dword [_silent]
push dword [_tail]
push dword [_head]
push dword [_middle]
push eax

call hanoi_rec
call hanoi_rec

.endif_1:
mov eax, [_silent]
cmp eax, 1
je .endif_2

push dword [_tail]
push dword [_head]
push dword strFmt
call printf
add esp, (4 * 3)

.endif_2:
leave
ret

Regards,
Bryant Keller
« Last Edit: November 11, 2010, 10:07:32 AM by Bryant Keller »

About Bryant Keller
bkeller@about.me