; Version	: 3.0
; Last update	: 25/5/2020
; Description	: FizzBuzz, but in assembly. Stack version.
; Note		: There are two issues;
; 0. 		: Output is limited to the size of the stack (~100000 numbers)
; 1.		: Stack writes must be aligned, so there needs to be NULL chars in the output
; Licence	: GPLv3

;; data is aligned to 8 or 16 bytes via null chars
section .data
fizz db 'Fizz',0,0,0,0xA
fizzlen equ $-fizz
buzz db 'Buzz',0,0,0,0xA
buzzlen equ $-buzz
fizzbuzz db 'FizzBuzz',0,0,0,0,0,0,0,0xA
fizzbuzzlen equ $-fizzbuzz

section .text
global _start
;_start: mov r12,100	;counter register, set to count 100 to 1 (stack writing is done in reverse, so each line should be done in reverse of what you want to come out the right way)
;_start: mov r12,100000	;counter register, set to count 100 to 1 (stack writing is done in reverse, so each line should be done in reverse of what you want to come out the right way)
_start: mov r12,1000001	;counter register, set to count 100 to 1 (stack writing is done in reverse, so each line should be done in reverse of what you want to come out the right way)
xor r9,r9		;r9 is used as a boolean to record if modulus 3 is achieved

ALIGN 16		;align the stack to 16 bytes
mov rsi,rsp		;copy the stack pointer to the source register for use at the end.
jmp skip		;skip decincrementing the first time round so 100 is kept

increment: dec r12	;deincrement the counter
skip: test r12,r12	;check if 0 has been reached
jz exit			;exit if numbers 100000 to 1 have been calculated and written to the stack

check3: imul r8d,r12d,0xaaaaaaab;calculate modulus 3 quickly by multiplying the counter by 0xaaaaaaab and truncuating the result into r8d.
cmp    r8d,0x55555555
ja check5			;if r8d is larger than 0x55555555; (r12 % 3 !=0) and so modulus 5 is directly jumped to.

;falls through if (r12 % 3 == 0)
mov r9,1 ; set the fizz boolean to true

check5: imul r8d,r12d,0xcccccccd	;calculate modulus 5 quickly by multiplying the counter by 0xcccccccd and truncuating the result into r8d.
cmp r8d,0x33333333
ja checkfizz				;if r8d is larger than 0x33333333; (r12 % 5 !=0). The state of fizz needs to be check to determine if anything needs printing.

;; fall through if (r12 % 5 == 0)
test r9,r9	;r9 is the fizz boolean
je buzzonly	;if there is no fizz, only print buzz

;; fall through if both fizz and buzz are achieved; it's fizzbuzz time
printfizzbuzz:
lea ebx,[fizzbuzz]	;load the memory address of fizzbuzz into ebx
add ebx,8		;increase ebx by 8 so it points to the '\n' in "\n       "
push qword[ebx]		;push "\n       " onto the stack (unsure if should be using r prefix, but e prefix seems to work).

sub ebx,8		;decrease ebx so it points to 'F' in "zzuBzziF"
push qword[rbx]		;push "zzuBzziF" onto the stack (unsure if should be using r prefix, but e prefix seems to work).

xor r9,r9		;zero out the fizz boolean
jmp increment		;calculate next number

checkfizz:
test r9,r9		;check if fizz is achieved
je printnum		;if not, print current number

;; fall through if fizz only is achieved
fizzonly:
push qword[fizz]	;push "\n   zziF" onto the stack

xor r9,r9		;zero out the fizz boolean
jmp increment		;next number

buzzonly:
push qword[buzz]	;push "\n    zzuB" onto the stack
jmp increment		;next number

;; Below stores a a newline and a bunch of null bytes to be overwritten
printnum:
dec rsp			;decrease stack pointer by 1 since we're write a single byte
mov ecx, 0xA		;move a newline into ecx
mov [rsp],cl		;copy the newline onto the stack (quite slow, but there's no other choice)

mov rax,r12		;rax = counter
mov r10,0xcccccccd	;used in division by 10 below

;; ecx=remainder = low digit = 0..9.  eax/=10
toascii_digit:
mov ecx,eax			;copy eax to ecx for later usage in modulus.

imul rax,r10			;sign multiply rax by 0xcccccccd to complete the first step of division by 10
shr rax,0x23			;shift rax right by 35 to finish off rax/=10

mov edx,eax			;move eax to edx so modulus can be done on it without clobbering eax
lea edx,[rdx+rdx*4]		;multiply edx by 5 as the first step of modulus
add edx,edx			;multiply edx by 2 as the second step of modulus
sub ecx,edx			;subtract edx from the original number (before /=10) to finish off modulus 10

;; the remainder(ecx) is the next calculated digit
add ecx,'0'			;add 48 to ecx to turn it into the ASCII representation of the number
dec rsp				;write the ASCII digits in MSD-first printing order, working backwards from the end of the string.
mov [rsp],cl			;copy the digit (cl == lowest byte in rcx) onto the stack (by chance the stack should be aligned to 4 bytes a few times).
;;Possible speedup(?): as soon as the digits have all been printed, the stack could be padded with null chars to align it to 4 bytes


test eax,eax
jnz toascii_digit		;if eax does not equal zero, there are more ASCII chars to generate and shove onto the stack.

jmp increment

;;print all the bytes in the stack and exit
exit:
mov eax,1			;sys_write
mov edi,1			;fp = stdout
;;rsi is a pointer to the saved "start" position in the stack and shouldn't have been changed.
lea edx,[rsi]			;truncate the pointer to the "start" of the stack.
sub edx,esp			;calculate length in bytes of all characters written to the stack by subtracting the trunctated end of the stack, to the truncated start of the stack

mov rsi,rsp			;copy the "end" of the stack to rsi
syscall				;print all the bytes in the stack

mov eax, 60			;code for sys_exit
xor edi, edi			;return value of 0
syscall				;do sys_exit