# !> Three versions of factorial in assembly

.global main

.text

# Assembly Design Recipe

# 1. Signature / purpose

# long fact(long n)
# Computes the nth factorial

# 2. Pseudocode

# long fact(long n) {
#   if (n < 2) 
#     return 1;
#   else
#     temp = fact(n - 1);
#     return n * temp;
# }

# 3. Variable mappings 
# n -> %rdi -> %r12
# temp -> %rax

# 4. Skeleton

# 5. Complete the body

# Version 1: callee-save register

# long fact(long n)

fact:
  # PROLOGUE
  pushq %r12     # push 8 bytes
  enter $8, $0   # allocate 8 bytes to align the stack pointer

  # BODY
  #   if (n < 2) 
  cmpq $2, %rdi
  jge fact_else
  #     return 1;
  movq $1, %rax
  jmp fact_ret
fact_else:
  #   else {
  movq %rdi, %r12
  subq $1, %rdi
  call fact
  #     temp = fact(n - 1);
  #     return n * temp;
  imulq %r12, %rax

  # EPILOGUE
fact_ret:
  leave
  popq %r12
  ret
  #   }

# Version 2: Using local variables in the stack frame

# n -> %rdi -> -8(%rbp)
# temp -> %rax
fact2:
  # PROLOGUE
  enter $16, $0   # allocate 8 bytes + 8 bytes to align rsp

  # BODY
  #   if (n < 2) 
  cmpq $2, %rdi
  jge fact2_else
  #     return 1;
  movq $1, %rax
  jmp fact2_ret
fact2_else:
  #   else {
  movq %rdi, -8(%rbp)
  subq $1, %rdi
  call fact2
  #     temp = fact2(n - 1);
  #     return n * temp;
  imulq -8(%rbp), %rax

  # EPILOGUE
fact2_ret:
  leave
  ret
  #   }

# Version 3: Using a caller-save register

# n -> %r10
fact3:
  # PROLOGUE
  enter $0, $0

  # BODY
  #   if (n < 2) 
  cmpq $2, %rdi
  jge fact3_else
  #     return 1;
  movq $1, %rax
  jmp fact3_ret
fact3_else:
  #   else {
  movq %rdi, %r10
  subq $1, %rdi
  pushq %r10    # push twice to align the stack pointer
  pushq %r10
  call fact3
  #     temp = fact3(n - 1);
  #     return n * temp;
  popq %r10
  popq %r10
  imulq %r10, %rax

  # EPILOGUE
fact3_ret:
  leave
  ret
  #   }


# int main(int argc, char *argv[])
# tmp -> %rax
main:
  enter $0, $0

  # tmp = fact(5)
  movq $5, %rdi
  call fact3

  # printf("%ld\n", tmp)
  movq $format, %rdi
  movq %rax, %rsi
  movb $0, %al
  call printf

  # return 0;
  movq $0, %rax
  leave
  ret

.data
format:
  .asciz "%ld\n"