Skip to main content
Code Review

Return to Answer

Bounty Ended with 50 reputation awarded by T145
deleted 16 characters in body
Source Link
Sep Roland
Sep Roland
  • 4.6k
  • 16
  • 27

Does your main really need to reserve 56 bytes on the stack in order to receive a mere dword from scanf? And why does hanoi reserve 40 bytes on the stack that it never uses?

;; bits 64
default rel

extern printf, scanf

section .text
    global main
    global hanoi
main:
    sub     rsp, 56
    lea     rcx, [prompt]
    call    printf
    lea     rdx, [rsp+32]
    lea     rcx, [scan_fmt]
    call    scanf
    cmp     eax, 1
    jz      .call_hanoi
    lea     rcx, [scan_fail]
    call    printf
    mov     eax, 1                      ; return 1
.end:
    add     rsp, 56
    ret
.call_hanoi:
    mov     ecx, dword [rsp+32]         ; ecx = num_disks
    mov     r9d, 3                      ; r9d = tmp
    mov     r8d, 2                      ; r8d = dst
    mov     edx, 1                      ; edx = src
    call    hanoi                       ; hanoi(num_disks, src, dst, tmp)
    xor     eax, eax                    ; return 0
    jmp     .end
hanoi:
    cmp     ecx, 1                      ; if num_disks == 1
    je      .skip_recursive_move

    push    rbx
    push    rsi
    push    rdi
    push    r12

    mov     ebx, ecx                    ; ECX=2+
    mov     esi, edx                    ; esi = edx = src
    mov     edi, r9d                    ; edi = r9d = tmp
    mov     r12d, r8d                   ; r12d = r8d = dst

.move_disk:
    mov     r9d, r12d                   ; dst
    mov     r8d, edi                    ; tmp
    mov     edx, esi                    ; src
    lea     ecx, [rbx - 1]              ; num_disks - 1
    call    hanoi                       ; tmp & dst are swapped for this call

    mov     r9d, r12d                   ; the 'to' peg
    mov     r8d, esi                    ; the 'from' peg
    mov     edx, ebx                    ; num_disks
    lea     rcx, [prompt_move_disk]
    sub     rsp, 32                     ;shadow space
    call    printf
    add     rsp, 32

    mov     eax, esi
    mov     esi, edi
    mov     edi, eax                    ; swaps tmp and src (esi and edi)

    dec     ebx                         ; num_disks - 1
    cmp     ebx, 1                      ; if num_disks == 1
    jne     .move_disk

    mov     r8d, r12d                   ; the 'to' peg
    mov     edx, esi                    ; the 'from' peg

    pop     r12
    pop     rdi
    pop     rsi
    pop     rbx

.skip_recursive_move:
    lea     rcx, [prompt_move_one_disk]
    jmpsub     rsp, 32                     ;shadow space
    call    printf
    add     rsp, 32
    ret

%macro str 2
    %2: db %1, 0
%endmacro

section .rdata
    str "How many disks do you want to play with? ", prompt
    str "%u", scan_fmt
    str {"Uh-oh, I couldn't understand that...  No towers of Hanoi for you!", 10}, scan_fail
    str {"Move disk 1 from peg %d to peg %d", 10}, prompt_move_one_disk
    str {"Move disk %d from peg %d to peg %d", 10}, prompt_move_disk

Does your main really need to reserve 56 bytes on the stack in order to receive a mere dword from scanf? And why does hanoi reserve 40 bytes on the stack that it never uses?

;; bits 64
default rel

extern printf, scanf

section .text
    global main
    global hanoi
main:
    sub     rsp, 56
    lea     rcx, [prompt]
    call    printf
    lea     rdx, [rsp+32]
    lea     rcx, [scan_fmt]
    call    scanf
    cmp     eax, 1
    jz      .call_hanoi
    lea     rcx, [scan_fail]
    call    printf
    mov     eax, 1                      ; return 1
.end:
    add     rsp, 56
    ret
.call_hanoi:
    mov     ecx, dword [rsp+32]         ; ecx = num_disks
    mov     r9d, 3                      ; r9d = tmp
    mov     r8d, 2                      ; r8d = dst
    mov     edx, 1                      ; edx = src
    call    hanoi                       ; hanoi(num_disks, src, dst, tmp)
    xor     eax, eax                    ; return 0
    jmp     .end
hanoi:
    cmp     ecx, 1                      ; if num_disks == 1
    je      .skip_recursive_move

    push    rbx
    push    rsi
    push    rdi
    push    r12

    mov     ebx, ecx                    ; ECX=2+
    mov     esi, edx                    ; esi = edx = src
    mov     edi, r9d                    ; edi = r9d = tmp
    mov     r12d, r8d                   ; r12d = r8d = dst

.move_disk:
    mov     r9d, r12d                   ; dst
    mov     r8d, edi                    ; tmp
    mov     edx, esi                    ; src
    lea     ecx, [rbx - 1]              ; num_disks - 1
    call    hanoi                       ; tmp & dst are swapped for this call

    mov     r9d, r12d                   ; the 'to' peg
    mov     r8d, esi                    ; the 'from' peg
    mov     edx, ebx                    ; num_disks
    lea     rcx, [prompt_move_disk]
    call    printf

    mov     eax, esi
    mov     esi, edi
    mov     edi, eax                    ; swaps tmp and src (esi and edi)

    dec     ebx                         ; num_disks - 1
    cmp     ebx, 1                      ; if num_disks == 1
    jne     .move_disk

    mov     r8d, r12d                   ; the 'to' peg
    mov     edx, esi                    ; the 'from' peg

    pop     r12
    pop     rdi
    pop     rsi
    pop     rbx

.skip_recursive_move:
    lea     rcx, [prompt_move_one_disk]
    jmp     printf

%macro str 2
    %2: db %1, 0
%endmacro

section .rdata
    str "How many disks do you want to play with? ", prompt
    str "%u", scan_fmt
    str {"Uh-oh, I couldn't understand that...  No towers of Hanoi for you!", 10}, scan_fail
    str {"Move disk 1 from peg %d to peg %d", 10}, prompt_move_one_disk
    str {"Move disk %d from peg %d to peg %d", 10}, prompt_move_disk

;; bits 64
default rel

extern printf, scanf

section .text
    global main
    global hanoi
main:
    sub     rsp, 56
    lea     rcx, [prompt]
    call    printf
    lea     rdx, [rsp+32]
    lea     rcx, [scan_fmt]
    call    scanf
    cmp     eax, 1
    jz      .call_hanoi
    lea     rcx, [scan_fail]
    call    printf
    mov     eax, 1                      ; return 1
.end:
    add     rsp, 56
    ret
.call_hanoi:
    mov     ecx, dword [rsp+32]         ; ecx = num_disks
    mov     r9d, 3                      ; r9d = tmp
    mov     r8d, 2                      ; r8d = dst
    mov     edx, 1                      ; edx = src
    call    hanoi                       ; hanoi(num_disks, src, dst, tmp)
    xor     eax, eax                    ; return 0
    jmp     .end
hanoi:
    cmp     ecx, 1                      ; if num_disks == 1
    je      .skip_recursive_move

    push    rbx
    push    rsi
    push    rdi
    push    r12

    mov     ebx, ecx                    ; ECX=2+
    mov     esi, edx                    ; esi = edx = src
    mov     edi, r9d                    ; edi = r9d = tmp
    mov     r12d, r8d                   ; r12d = r8d = dst

.move_disk:
    mov     r9d, r12d                   ; dst
    mov     r8d, edi                    ; tmp
    mov     edx, esi                    ; src
    lea     ecx, [rbx - 1]              ; num_disks - 1
    call    hanoi                       ; tmp & dst are swapped for this call

    mov     r9d, r12d                   ; the 'to' peg
    mov     r8d, esi                    ; the 'from' peg
    mov     edx, ebx                    ; num_disks
    lea     rcx, [prompt_move_disk]
    sub     rsp, 32                     ;shadow space
    call    printf
    add     rsp, 32

    mov     eax, esi
    mov     esi, edi
    mov     edi, eax                    ; swaps tmp and src (esi and edi)

    dec     ebx                         ; num_disks - 1
    cmp     ebx, 1                      ; if num_disks == 1
    jne     .move_disk

    mov     r8d, r12d                   ; the 'to' peg
    mov     edx, esi                    ; the 'from' peg

    pop     r12
    pop     rdi
    pop     rsi
    pop     rbx

.skip_recursive_move:
    lea     rcx, [prompt_move_one_disk]
    sub     rsp, 32                     ;shadow space
    call    printf
    add     rsp, 32
    ret

%macro str 2
    %2: db %1, 0
%endmacro

section .rdata
    str "How many disks do you want to play with? ", prompt
    str "%u", scan_fmt
    str {"Uh-oh, I couldn't understand that...  No towers of Hanoi for you!", 10}, scan_fail
    str {"Move disk 1 from peg %d to peg %d", 10}, prompt_move_one_disk
    str {"Move disk %d from peg %d to peg %d", 10}, prompt_move_disk
added a copy-paste version of the program
Source Link
Sep Roland
Sep Roland
  • 4.6k
  • 16
  • 27

EDIT (copy-paste version):

;; bits 64
default rel

extern printf, scanf

section .text
    global main
    global hanoi
main:
    sub     rsp, 56
    lea     rcx, [prompt]
    call    printf
    lea     rdx, [rsp+32]
    lea     rcx, [scan_fmt]
    call    scanf
    cmp     eax, 1
    jz      .call_hanoi
    lea     rcx, [scan_fail]
    call    printf
    mov     eax, 1                      ; return 1
.end:
    add     rsp, 56
    ret
.call_hanoi:
    mov     ecx, dword [rsp+32]         ; ecx = num_disks
    mov     r9d, 3                      ; r9d = tmp
    mov     r8d, 2                      ; r8d = dst
    mov     edx, 1                      ; edx = src
    call    hanoi                       ; hanoi(num_disks, src, dst, tmp)
    xor     eax, eax                    ; return 0
    jmp     .end
hanoi:
    cmp     ecx, 1                      ; if num_disks == 1
    je      .skip_recursive_move

    push    rbx
    push    rsi
    push    rdi
    push    r12

    mov     ebx, ecx                    ; ECX=2+
    mov     esi, edx                    ; esi = edx = src
    mov     edi, r9d                    ; edi = r9d = tmp
    mov     r12d, r8d                   ; r12d = r8d = dst

.move_disk:
    mov     r9d, r12d                   ; dst
    mov     r8d, edi                    ; tmp
    mov     edx, esi                    ; src
    lea     ecx, [rbx - 1]              ; num_disks - 1
    call    hanoi                       ; tmp & dst are swapped for this call

    mov     r9d, r12d                   ; the 'to' peg
    mov     r8d, esi                    ; the 'from' peg
    mov     edx, ebx                    ; num_disks
    lea     rcx, [prompt_move_disk]
    call    printf

    mov     eax, esi
    mov     esi, edi
    mov     edi, eax                    ; swaps tmp and src (esi and edi)

    dec     ebx                         ; num_disks - 1
    cmp     ebx, 1                      ; if num_disks == 1
    jne     .move_disk

    mov     r8d, r12d                   ; the 'to' peg
    mov     edx, esi                    ; the 'from' peg

    pop     r12
    pop     rdi
    pop     rsi
    pop     rbx

.skip_recursive_move:
    lea     rcx, [prompt_move_one_disk]
    jmp     printf

%macro str 2
    %2: db %1, 0
%endmacro

section .rdata
    str "How many disks do you want to play with? ", prompt
    str "%u", scan_fmt
    str {"Uh-oh, I couldn't understand that...  No towers of Hanoi for you!", 10}, scan_fail
    str {"Move disk 1 from peg %d to peg %d", 10}, prompt_move_one_disk
    str {"Move disk %d from peg %d to peg %d", 10}, prompt_move_disk

EDIT (copy-paste version):

;; bits 64
default rel

extern printf, scanf

section .text
    global main
    global hanoi
main:
    sub     rsp, 56
    lea     rcx, [prompt]
    call    printf
    lea     rdx, [rsp+32]
    lea     rcx, [scan_fmt]
    call    scanf
    cmp     eax, 1
    jz      .call_hanoi
    lea     rcx, [scan_fail]
    call    printf
    mov     eax, 1                      ; return 1
.end:
    add     rsp, 56
    ret
.call_hanoi:
    mov     ecx, dword [rsp+32]         ; ecx = num_disks
    mov     r9d, 3                      ; r9d = tmp
    mov     r8d, 2                      ; r8d = dst
    mov     edx, 1                      ; edx = src
    call    hanoi                       ; hanoi(num_disks, src, dst, tmp)
    xor     eax, eax                    ; return 0
    jmp     .end
hanoi:
    cmp     ecx, 1                      ; if num_disks == 1
    je      .skip_recursive_move

    push    rbx
    push    rsi
    push    rdi
    push    r12

    mov     ebx, ecx                    ; ECX=2+
    mov     esi, edx                    ; esi = edx = src
    mov     edi, r9d                    ; edi = r9d = tmp
    mov     r12d, r8d                   ; r12d = r8d = dst

.move_disk:
    mov     r9d, r12d                   ; dst
    mov     r8d, edi                    ; tmp
    mov     edx, esi                    ; src
    lea     ecx, [rbx - 1]              ; num_disks - 1
    call    hanoi                       ; tmp & dst are swapped for this call

    mov     r9d, r12d                   ; the 'to' peg
    mov     r8d, esi                    ; the 'from' peg
    mov     edx, ebx                    ; num_disks
    lea     rcx, [prompt_move_disk]
    call    printf

    mov     eax, esi
    mov     esi, edi
    mov     edi, eax                    ; swaps tmp and src (esi and edi)

    dec     ebx                         ; num_disks - 1
    cmp     ebx, 1                      ; if num_disks == 1
    jne     .move_disk

    mov     r8d, r12d                   ; the 'to' peg
    mov     edx, esi                    ; the 'from' peg

    pop     r12
    pop     rdi
    pop     rsi
    pop     rbx

.skip_recursive_move:
    lea     rcx, [prompt_move_one_disk]
    jmp     printf

%macro str 2
    %2: db %1, 0
%endmacro

section .rdata
    str "How many disks do you want to play with? ", prompt
    str "%u", scan_fmt
    str {"Uh-oh, I couldn't understand that...  No towers of Hanoi for you!", 10}, scan_fail
    str {"Move disk 1 from peg %d to peg %d", 10}, prompt_move_one_disk
    str {"Move disk %d from peg %d to peg %d", 10}, prompt_move_disk
Source Link
Sep Roland
Sep Roland
  • 4.6k
  • 16
  • 27

Observations.

Does your main really need to reserve 56 bytes on the stack in order to receive a mere dword from scanf? And why does hanoi reserve 40 bytes on the stack that it never uses?

Move disk 1 from 1 to 3

Move disk 2 from 1 to 2

I think these messages would be more descriptive (less ambiguous) if you included the word peg:

Move disk 1 from peg 1 to peg 3
Move disk 2 from peg 1 to peg 2

mov     r9d, r12d                   ; update r9d after hanoi call

mov     r8d, esi                    ; update r8d after hanoi cal

I found it confusing to read these comments. Registers R8D and R9D are being setup for the upcoming printf and nothing else. The mention of "update after hanoi call" would suggest they have a more permanent significance which they haven't.

Optimizations.

  • The .skip_recursive_move operation for when ECX is 1 on input can be much simpler. All registers are already conveniently setup for the tailcall (jmp) to printf.

  • The program uses the EBP register in a redundant fashion and hence you can shave off a number of instructions. You also no longer need to preserve EBP.

I suggest you take a look at my version below:

hanoi:
    cmp     ecx, 1                      ; if num_disks == 1
    je      .skip_recursive_move

    push    rbx
    push    rsi
    push    rdi
    push    r12

    mov     ebx, ecx                    ; ECX=2+
    mov     esi, edx                    ; esi = edx = src
    mov     edi, r9d                    ; edi = r9d = tmp
    mov     r12d, r8d                   ; r12d = r8d = dst

.move_disk:
    mov     r9d, r12d                   ; dst
    mov     r8d, edi                    ; tmp
    mov     edx, esi                    ; src
    lea     ecx, [rbx - 1]              ; num_disks - 1
    call    hanoi                       ; tmp & dst are swapped for this call

    mov     r9d, r12d                   ; the 'to' peg
    mov     r8d, esi                    ; the 'from' peg
    mov     edx, ebx                    ; num_disks
    lea     rcx, [prompt_move_disk]
    call    printf

    dec     ebx                         ; num_disks - 1
    cmp     ebx, 1                      ; if num_disks == 1
    je      .move_one_disk

    mov     eax, esi
    mov     esi, edi
    mov     edi, eax                    ; swaps tmp and src (esi and edi)
    jmp     .move_disk

.move_one_disk:
    mov     r8d, r12d                   ; the 'to' peg
    mov     edx, edi                    ; the 'from' peg

    pop     r12
    pop     rdi
    pop     rsi
    pop     rbx

.skip_recursive_move:
    lea     rcx, [prompt_move_one_disk]
    jmp     printf

Please notice that setting up the calling registers in a consistent order (RCX, RDX, R8, R9) helps to improve readability. Leaving a blank line further groups things into logical blocks.

One additional optimization comes from exchanging ESIand EDI regardless, thus being able to re-arrange the code to avoid having 2 jump instructions:

    ...
    mov     eax, esi
    mov     esi, edi
    mov     edi, eax                    ; swaps tmp and src (esi and edi)

    dec     ebx                         ; num_disks - 1
    cmp     ebx, 1                      ; if num_disks == 1
    jne     .move_disk

    mov     r8d, r12d                   ; the 'to' peg
    mov     edx, ESI                    ; the 'from' peg
    ...

See that this time ESI gives the 'from' peg!