Tower of Hanoi in NASM Win64 Assembly

Question

This program is an implementation of the classic puzzle Tower of Hanoi! This is my first mostly recursive Assembly program. Any advice and all topical comments on code optimization and conventions is appreciated!

---

Compiled as follows using VS2017 x64 Native Tools Command Prompt:

> nasm -g -fwin64 hanoi.asm

> cl /Zi hanoi.obj msvcrt.lib legacy_stdio_definitions.lib

hanoi.asm

;; 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:
    push    r12
    mov     r12d, r8d                   ; r12d = r8d = dst
    push    rbp
    push    rdi
    push    rsi
    mov     esi, edx                    ; esi = edx = src
    push    rbx
    sub     rsp, 40
    cmp     ecx, 1                      ; if num_disks == 1
    jz      .skip_recursive_move
    mov     ebx, ecx
    mov     edi, r9d                    ; edi = r9d = tmp
.move_disk:
    lea     ebp, [rbx-1H]               ; ebp = num_disks - 1
    mov     r9d, r12d                   ; r9d = r12d = dst
    mov     r8d, edi                    ; r8d = edi = tmp
    mov     edx, esi                    ; edx = esi = src
    mov     ecx, ebp                    ; ecx = edp = num_disks - 1
    call    hanoi                       ; tmp & dst are swapped for this call
    mov     edx, ebx                    ; edx = ebx = num_disks
    mov     r9d, r12d                   ; update r9d after hanoi call
    mov     r8d, esi                    ; update r8d after hanoi call
    lea     rcx, [prompt_move_disk]
    mov     ebx, ebp                    ; ebx = ebp = num_disks - 1
    call    printf
    cmp     ebp, 1                      ; if num_disks == 1
    jz      .move_one_disk
    mov     eax, esi
    mov     esi, edi
    mov     edi, eax                    ; swaps tmp and src (esi and edi)
    jmp     .move_disk
.skip_recursive_move:
    mov     edi, edx                    ; edi = edx = src
.move_one_disk:
    add     rsp, 40
    mov     r8d, r12d
    mov     edx, edi
    pop     rbx
    lea     rcx, [prompt_move_one_disk]
    pop     rsi
    pop     rdi
    pop     rbp
    pop     r12
    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 %d to %d", 10}, prompt_move_one_disk
    str {"Move disk %d from %d to %d", 10}, prompt_move_disk

Sample output

Answer 1

Observations.

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!

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]
    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