;name: facrec.asm
;
;build: nasm -felf64 facrec.asm -o facrec.o
; ld -melf_x86_64 facrec.o -o facrec
;
;description: calculate factorial of n, result on STDOUT with recursion.
; The program shows the execution time needed.
bits 64
%include "unistd.inc"
%include "unistd.inc"
%include "sys/time.inc"
%define MAX_VALUE 20
global _start
section .bss
buffer: resb 20
.end:
.length: equ $-buffer
section .data
usage: db "Recursive Factorial - by Agguro - 2013",10,"Usage: facrec n",10,"n must be an integer in [0..20]",10
.length: equ $-usage
sResult: db "!="
.length: equ $-sResult
sLf: db 10
.length: equ $-sLf
sExecution: db "Execution time: "
.length: equ $-sExecution
sPeriod: db "."
.length: equ $-sPeriod
sSeconds: db " secs"
.length: equ $-sSeconds
sZero: db "0"
.length: equ $-sZero
TIMESPEC starttime
TIMESPEC endtime
section .text
_start:
pop rax ;argc
cmp rax,2
jne ShowUsage
pop rax ;the command
pop rsi ;pointer to argument
call StringLength ;string length in RAX
cmp rax,2 ;maximum number of bytes allowed
jg ShowUsage
call ParseInteger ;Value of the ascii number in RAX, -1 if error
cmp rax,0 ;if RAX < 0 then error
jl ShowUsage
cmp rax,MAX_VALUE ;if RAX > 20 then to big
jg ShowUsage
push rax ;save n
push rax
call GetTime
mov qword[starttime.tv_sec], rdx
mov qword[starttime.tv_nsec], rax
pop rax
call Factorial ;RAX contains the factorial
push rax
call GetTime
mov qword[endtime.tv_sec], rdx
mov qword[endtime.tv_nsec], rax
pop rax
pop rbx ;get n
xchg rbx,rax ;swap result and n
push rbx ;result on stack
mov rsi,buffer.end-1 ;convert and write n
xor rdx,rdx
call Bits128ToDecimal
mov rdx,buffer.end+1
sub rdx,rsi
call Write
mov rsi,sResult ;second part of output to STDOUT
mov rdx,sResult.length
call Write
pop rax ;get result back from stackframe
mov rsi,buffer.end-1
xor rdx,rdx
call Bits128ToDecimal
mov rdx,buffer.end+1 ;write factorial
sub rdx,rsi
call Write
mov rsi,sLf ;write linefeed
mov rdx,1
call Write
call WriteTime
mov rsi,sLf ;write linefeed
mov rdx,1
call Write
jmp Exit
ShowUsage:
mov rsi,usage
mov rdx,usage.length
call Write
Exit:
syscall exit,0
; calculate the factorial of a number in RAX.
Factorial:
cmp rax,0
jne .next
mov rax,1
push rax
jmp .done
.next:
push rax
dec rax
call Factorial
.done:
pop rbx
imul rbx ;RDX:RAX = RAX * RBX
ret
; Following routine is a bit overkill but at the time I wrote this I got the routine already written.
; My laziness led me to use this routine instead of writing a 64 bit conversion.
;***********************************************************************************************
; Bits128ToDecimal
; ----------------
; IN : RDX:RAX is number to convert
; OUT : RSI pointer to first digit in buffer
; RDX length of decimal number
;***********************************************************************************************
Bits128ToDecimal:
push rax
push rbx
push rcx
push rdi
push r8
push rbp ;create stackframe
mov rbp,rsp
sub rsp,24 ;3 help variables to store 4 - 32 bit registers
; prepare help registers
mov r8,rax
shl r8,32
shr r8,32
mov qword[rsp],r8 ;32 lowest bits in [rsp]
shr rax,32
mov qword[rsp+8],rax ;next 32 bits in [rsp+8]
mov r8,rdx
shl r8,32
shr r8,32
mov qword [rsp+16],r8 ;next 32 bits in [rsp+16]
shr rdx,32
mov qword[rsp+24],rdx ;32 highest bits in [rsp+8]
mov rdi,buffer.end ;point to last byte in buffer
xor rcx,rcx ;digit counter
.repeat:
mov rbx,4
.checkNextDigit:
dec rbx ;point to 32 bits value on stack
mov rax,qword [rsp+rbx*8] ;load 32 bits
cmp rax,0 ;are 32 bits zero?
jnz .convert
cmp rbx,0
jne .checkNextDigit
cmp rcx,0 ;already digits converted?
jne .adjustPointer ;yes, stop
mov byte [rdi],"0"
mov rcx,1
jmp .exit
.convert:
;conversion ;not zero, convert
xor rdx,rdx ;prepare for division
push rbx ;store 32 bits pointer
mov rbx,10 ;base 10
idiv rbx ;RAX = quotient, RDX = remainder
pop rbx ;restore 32 bits pointer
mov qword[rsp+rbx*8], rax ;store quotient back
cmp rbx,0 ;last set of 32 bits?
je .isLastDigit ;yes
shl rdx,32 ;no, adjust remainder
add qword[rsp+rbx*8-8],rdx ;and add to next set
jmp .checkNextDigit ;and continue convertion
.isLastDigit:
add dl, "0" ;if last digit then make ASCII
mov byte[rdi],dl ;and store in buffer
dec rdi ;adjust buffer
inc rcx ;increment number of digits
jmp .repeat ;repeat
.adjustPointer:
inc rdi ;adjust buffer
.exit:
mov rsi,rdi ;RSI is pointer to buffer with decimal number
mov rdx,rcx ;RDX is number of digits in decimal number
mov rsp,rbp
pop rbp ;leave stackframe
pop r8 ;restore registers
pop rdi
pop rcx
pop rbx
pop rax
ret
;***********************************************************************************************
; GetTime
; -------
; This subroutine returns the time in RDX:RAX
; IN : none
; OUT : RDX = seconds
; RAX = nanoseconds
;***********************************************************************************************
GetTime:
push rsi
push rdi
push rcx
push rbp
mov rbp,rsp
sub rsp,16 ;reserve 2 QWORDS
syscall clock_gettime, CLOCK_REALTIME, rsp
mov rdx,[rsp] ;seconds
mov rax,[rsp+8] ;nanoseconds
mov rsp,rbp
pop rbp
pop rcx
pop rdi
pop rsi
ret
;***********************************************************************************************
; WriteTime
; ---------
; This subroutine writes a time in RDX:RAX in decimal seconds
;***********************************************************************************************
WriteTime:
push rsi
push rax
push rcx
push rdx
mov rsi,sExecution
mov rdx,sExecution.length
call Write
mov rax,qword [endtime.tv_nsec]
mov rdx,qword [endtime.tv_sec]
stc
sub rax,qword [starttime.tv_nsec]
sbb rdx,qword [starttime.tv_sec]
cmp rax,0
jge .done
add rax,1000000000
.done:
push rax ;nanosecs on stack
mov rax,rdx ;seconds in RAX
xor rdx,rdx
call Bits128ToDecimal
call Write
mov rsi,sPeriod
mov rdx,1
call Write
pop rax ;nanosecs from stack
xor rdx,rdx
call Bits128ToDecimal
push rdx
push rsi
mov rcx,rdx
.leadingZero:
cmp rcx, 9
je .writeNanos
mov rsi,sZero
mov rdx,sZero.length
call Write
inc rcx
jmp .leadingZero
pop rdx
call Write
.writeNanos:
pop rsi
pop rdx
call Write
mov rsi,sSeconds
mov rdx,sSeconds.length
call Write
pop rdx
pop rcx
pop rax
pop rsi
ret
;***********************************************************************************************
; Write
; -----
; Write a string pointed by RSI with length RDX to STDOUT
;***********************************************************************************************
Write:
push rax ;store used registers
push rdi
push rcx ;RCX will also be modified!!
syscall write,stdout
pop rcx ;restore used registers
pop rdi
pop rax
ret
;***********************************************************************************************
; determine the length of a zero terminated string pointed to by RSI
; the result is returned in RAX. All registers except RAX are restored.
;***********************************************************************************************
StringLength:
push rcx
push rsi
xor rcx,rcx
.repeat:
lodsb ;byte in AL
cmp al,0 ;terminating zero?
je .done ;yes, we're done
inc rcx ;increment bytecount
jmp .repeat
.done:
mov rax,rcx
pop rsi
pop rcx
ret
;***********************************************************************************************
; ParseInteger
; ------------
; Parse an integer from an zero terminated ascii string. Only numbers are
; allowed. The routine stops at the first non decimal character or when
; ending zero is reached. The result is returned in RAX. If a parse error occur -1 is returned.
; All registers except RAX are restored.
;***********************************************************************************************
ParseInteger:
push rsi
push rbx
push rcx
mov rbx,10
xor rcx,rcx
.repeat:
lodsb
cmp al,0
je .done
cmp al,"0"
jb .error
cmp al,"9"
ja .error
and al,0x0F ;ascii to decimal
xchg rcx,rax
imul rbx
xchg rcx,rax
add rcx,rax
jmp .repeat
.error:
mov rax,-1
jmp .exit
.done:
mov rax,rcx
.exit:
pop rcx
pop rbx
pop rsi
ret
