How to change x86_32 nasm fibonacci to x86_64?

Question

Here is a code

cat fibonacci.asm 
fibonacci:
push    EBP         ; Retrieve parameter and put it
push    EBX         ; Save previous parameter
mov     EBP,ESP     ; into EBX register
add     EBP,12      ;
mov     EBX,[EBP]   ; EBX = Param

cmp     EBX,1       ; Check for base case
jle     base        ; It is base if (n <= 1)

lea ecx,[ebx-1]
push ecx            ; push N-1
call    fibonacci   ; Calculate fibonacci for (EBX - 1)
pop ecx             ; remove N-1 off the stack

push eax            ; save the result of fibonacci(N-1)
lea ecx,[ebx-2]
push ecx            ; push N-2
call    fibonacci   ; Calculate fibonacci for (EBX - 2)
pop ecx             ; remove N-2 off the stack
pop ecx             ; ecx = fibonacci(N-1)
add eax,ecx         ; eax = fibonacci(N-2) + fibonacci(N-1)

jmp end
base:               ; Base case
mov EAX,1           ; The result would be 1

end:
pop     EBX         ; Restore previous parameter
pop     EBP         ; Release EBP
ret

It was compiled well

nasm -f elf -o fibonacci.o fibonacci.asm

but not linked

ld -arch x86_64 fibonacci.o -o fibonacci_a
ld: i386 architecture of input file `fibonacci.o' is incompatible with i386:x86-64 output
ld: warning: cannot find entry symbol _start; defaulting to 0000000000400080

how to change it and compile in x64 ubuntu ? i really need this for tests purposes :)

also i was tried this variation

nasm -f elf64 fibonacci_64.asm && ld -arch x86_64 fibonacci_64.o -o fab && ./fab

not worked..

For starters, your base pointer and stack pointer in x86_64 become RBP and RSP, (instead of EBP and ESP). — Ken P, Sep 28 '15 at 18:16
More importantly, the System V ABI (used by most POSIXly systems on x86-64) uses registers to pass the first couple of arguments to functions. This'll require quite a bit of change to work on 64-bit. — EOF, Sep 28 '15 at 18:24
You realize this implementation does a boatload of redundant work, right? It's fine as a teach-yourself-recursive-functions-in-asm exercise, but that's all. :P At every step, you compute F(n-1) and F(n-2) independently, instead of saving F(n-2) as part of computing F(n-1). `add rax, rbx / add rbx, rax` computes the series. You might find [my asm implementation](http://stackoverflow.com/a/32661389/224132) interesting, which stores the whole sequence into a dest array. It could just return the last. rkhb also posted a O(log(n)) algorithm for F(n) as another answer on that question. — Peter Cordes, Sep 28 '15 at 22:33
@ Peter Cordes, I need this realisation for speed up testing, it's special made to do redundant work. I just need to run it on 64 — Oleg Abrazhaev, Sep 29 '15 at 11:06

rkhb · Accepted Answer · 2015-09-29T14:18:50.303

First step: Where the assembler complains with "error: instruction not supported in 64-bit mode" you have to change a 32-bit-register to the corresponding 64-bit-register, e.g. EBP to RBP.

Second step: Every PUSH consumes now 8 bytes instead of 4 bytes. Operations on stack have to be doubled, e.g. add RBP,24 instead of add EBP,12.

Third step: Don't forget the caller, e.g. a printf and an exit now follow the "System V AMD64 ABI" calling convention in Linux and the Windows-64 calling convention in Windows. You find examples here on SO.

This one works on Linux:

DEFAULT rel

section .text
GLOBAL _start
_start:

    push qword 30               ; -> 1346269
    call fibonacci
    add rsp, 8

    call write_eax

    mov edi, 0                  ; return 0 (success)
    mov eax, 60                 ; sys_exit
    syscall

fibonacci:
    push rbp
    push rbx

    mov rbp, rsp
    add rbp, 24
    mov ebx, [rbp]

    cmp     EBX,1       ; Check for base case
    jle     base        ; It is base if (n <= 1)

    lea ecx,[ebx-1]
    push rcx
    call    fibonacci   ; Calculate fibonacci for (EBX - 1)
    pop rcx

    push rax
    lea ecx,[ebx-2]
    push rcx
    call    fibonacci   ; Calculate fibonacci for (EBX - 2)
    pop rcx
    pop rcx
    add eax,ecx         ; eax = fibonacci(N-2) + fibonacci(N-1)

    jmp end
    base:               ; Base case
    mov EAX,1           ; The result would be 1

    end:
    pop rbx
    pop rbp
    ret

write_eax:
    mov rsi, rsp                ; Keyword: Red Zone (https://en.wikipedia.org/wiki/Red_zone_%28computing%29)

    sub rsi, 1
    mov byte [rsi], `\n`        ; Line feed

    mov ecx, 10                 ; Divisor

    .L1:
    xor edx, edx
    div ecx                     ; EDX:EAX / ECX -> EAX, remainder EDX
    or dl, 0x30                 ; Convert remainder to ASCII
    sub rsi, 1
    mov [rsi], dl               ; Store remainder reversed on the stack
    test eax, eax
    jne .L1

    mov rdx, rsp                ; RDX: message string length
    sub rdx, rsi
    mov rdi, 1                  ; RDI=1: stdout
    mov eax, 1                  ; sys_write
    syscall                     ; /usr/include/x86_64-linux-gnu/asm/unistd_64.h

    ret

nasm -f elf64 fibonacci_64.asm && ld -arch x86_64 fibonacci_64.o -o fab && ./fab 4 ld: warning: cannot find entry symbol _start; defaulting to 0000000000400080 Segmentation fault (core dumped) — Oleg Abrazhaev, Sep 29 '15 at 11:17
@OlegAbrazhaev: Not my fault. It's an issue with your caller. Take a look at my extended code. Issues with the command line parameter are stuff enough for a new question with a full [MCVE](http://stackoverflow.com/help/mcve). — rkhb, Sep 29 '15 at 14:24
your version works. But could you please help to fix my version above? Or they are the same? — Oleg Abrazhaev, Mar 28 '17 at 05:36
@OlegAbrazhaev: The procedure `fibonacci` is the same but "x64ized". Therefore it's not state-of-the-art but working. The surrounding code is needed to get a working 64-bit program. Or do you want to assemble and link a 32-bit source to a 32-bit program in a 64-bit environment and get trouble? — rkhb, Mar 28 '17 at 06:42

score 2 · Answer 2 · answered Sep 28 '15 at 22:38

2

To assemble and link a stand-alone program on AMD64 linux, you can either gcc -nostartfiles, or

yasm -f elf64 foo.asm && ld foo.o -o foo

ld's default arch is the native one, i.e. amd64.

You didn't post any error messages from your 2nd command line, so IDK which part went wrong, or if it assembled fine and then segfaulted at runtime because you truncated 64bit pointers to 32bit.

answered Sep 28 '15 at 22:38

Peter Cordes

328,167
45
605
847

1

@Oleg: that doesn't make any sense at all. `nasm -f elf64` should make a 64bit object file (same as yasm), but the `ld` error you pasted was from the obvious problem of trying to link a 32bit ELF object into a 64bit executable. Are you sure you tried exactly what you wrote in the question? – Peter Cordes Sep 29 '15 at 11:26

How to change x86_32 nasm fibonacci to x86_64?

2 Answers2