; horner.asm  Horners method of evaluating polynomials
;
; given a polynomial  Y = a_n X^n + a_n-1 X^n-1 + ... a_1 X + a_0
; a_n is the coefficient 'a' with subscript n. X^n is X to nth power
; compute y_1 = a_n * X + a_n-1
; compute y_2 = y_1 * X + a_n-2
; compute y_i = y_i-1 * X + a_n-i   i=3..n
; thus    y_n = Y = value of polynomial 
;
; in assembly language:
;   load some register with a_n, multiply by X
;   add a_n-1, multiply by X, add a_n-2, multiply by X, ...
;   finishing with the add  a_0
;
; for conversion of decimal to binary, X=10
; 
	extern	printf
	section	.data
decdig:	db	'5','2','8','0','.' ; decimal integer 5280
fmt:	db	"%d",10,0
	
	global	main
	section	.text
main:	push	ebp		; save ebp
        mov	ebp,esp		; ebp is callers stack
	push	ebx
	push	edi		; save registers
	

; method 1, using a "sentinel" e.g. '.'
	
	mov	eax,0		; accumulate value here
	mov	al,[decdig]	; get first ASCII digit
	sub	al,48		; convert ASCII digit to binary
	mov	edi,1		; subscript initialization
h1loop:	mov	ebx,0		; clear register (upper part)
	mov	bl,[decdig+edi]	; get next ASCII digit
	cmp	bl,'.'		; compare to decimal point
	je	h1fin		; exit loop on decimal point
	sub	bl,48		; convert ASCII digit to binary
	imul	eax,10		; * X     (ignore edx)
	add	eax,ebx		; + a_n-i
	inc	edi		; increment subscript
	jmp	h1loop
h1fin:
	push	dword eax	; print eax
	push	dword fmt	; format %d
	call	printf
	add	esp,8		; restore stack

; method 2, using a count
	
	mov	eax,0		; accumulate value here
	mov	al,[decdig]	; get first ASCII digit
	sub	al,48		; convert ASCII digit to binary
	mov	edi,1		; subscript initialization
	mov	ecx,3		; loop iteration count initialization
h2loop:	mov	ebx,0		; clear register (upper part)
	mov	bl,[decdig+edi]	; get next ASCII digit
	sub	bl,48		; convert ASCII digit to binary
	imul	eax,10		; * X     (ignore edx)
	add	eax,ebx		; + a_n-i
	inc	edi		; increment subscript
	loop	h2loop		; decrement ecx, jump on non zero

	push	dword eax	; print eax
	push	dword fmt	; format %d
	call	printf
	add	esp,8		; restore stack

; evaluate a polynomial, X=7, using a count

	section	.data
a:	dd	2,5,-7,22,-9	; coefficients of polynomial, a_n first
X:	dd	7
	section	.text
	mov	eax,[a]		; accumulate value here, get coefficient a_n
	mov	edi,1		; subscript initialization
	mov	ecx,4		; loop iteration count initialization, n
h3loop:	imul	eax,[X]		; * X     (ignore edx)
	add	eax,[a+4*edi]	; + a_n-i
	inc	edi		; increment subscript
	loop	h3loop		; decrement ecx, jump on non zero

	push	dword eax	; print eax
	push	dword fmt	; format %d
	call	printf
	add	esp,8		; restore stack

; evaluate a polynomial, X=7, using a count as index
; optimal organization of data allows a three instruction loop
	
	section	.data
aa:	dd	-9,22,-7,5,2	; coefficients of polynomial, a_0 first
	section	.text
	mov	eax,[aa+4*4]	; accumulate value here, get coefficient a_n
	mov	ecx,4		; loop iteration count initialization, n
h4loop:	imul	eax,[X]		; * X     (ignore edx)
	add	eax,[aa+4*ecx-4]; + aa_n-i
	loop	h4loop		; decrement ecx, jump on non zero

	push	dword eax	; print eax
	push	dword fmt	; format %d
	call	printf
	add	esp,8		; restore stack

; evaluate a double floating polynomial, X=7.0, using a count as index
; optimal organization of data allows a three instruction loop
	
	section	.data
af:	dq	-9.0,22.0,-7.0,5.0,2.0	; coefficients of polynomial, a_0 first
XF:	dq	7.0
Y:	dq	0.0
N:	dd	4
fmtflt:	db	"%e",10,0

	section	.text
	mov	ecx,[N]		; loop iteration count initialization, n
	fld	qword [af+8*ecx]; accumulate value here, get coefficient a_n
h5loop:	fmul	qword [XF]	; * XF
	fadd	qword [af+8*ecx-8] ; + aa_n-i
	loop	h5loop		; decrement ecx, jump on non zero

	fstp	qword [Y]	; store Y in order to print Y
	push	dword [Y+4]	; print Y (must be two parts of quadword)
	push	dword [Y]	; print Y
	push	dword fmtflt	; format %e
	call	printf
	add	esp,12		; restore stack


; Convert the fractional polynomial, Y = a_-1 X^-1 + a_-2 X^-2 + ...
; This must be performed using divide in reverse order.
; compute y_1 = a_-n / X + a_-n+1
; compute y_2 = y_1 / X + a_-n+2
; compute y_i = y_i-1 / X + a_-n+i   i=3..n
; thus    y_n = Y_n-1 / X  = Y = value of polynomial 
; Using the coefficients above a_-1 = -9.0 (first)
; a_-2 = 22.0, a_-3 = -7.0, a_-4 = 5.0, a_-5 = 2.0
; N=4 (not 5) because the the first term is outside the loop

	mov	ecx,[N]		; loop iteration count initialization, n
	fld	qword [af+8*ecx]; accumulate value here, get  a_-n-1 = 2.0
h6loop:	fdiv	qword [XF]	; * XF
	fadd	qword [af+8*ecx-8] ; + aa_n-i
	loop	h6loop		; decrement ecx, jump on non zero
	fdiv	qword [XF]	; extra divide for fractional terms
	
	fstp	qword [Y]	; store Y in order to print Y
	push	dword [Y+4]	; print Y (must be two parts of quadword)
	push	dword [Y]	; print Y
	push	dword fmtflt	; format %e
	call	printf
	add	esp,12		; restore stack


; Convert the fractional part, a_-1 X^-1 + a_-2 X^-2 + ...
; This must be performed using "fixed point" arithmetic.
; The implied binary point is 16-bits from LSB.
	
	section	.data
fracdig:db	'.','1','2','3','4' ; decimal fraction .1234
fmth:	db	"%X",10,0
ten:	dd	10
eaxsave:dd	0
	
	global h7loop		; for debugging loop  "break h7loop"
	section	.text
	mov	eax,0		; accumulate value here
	mov	al,[fracdig+4]	; get last ASCII digit
	sub	al,48		; convert ASCII digit to binary
	shl	eax,16		; move binary point
	mov	ecx,3		; loop iteration count initialization
h7loop:	mov	edx,0		; must clear upper dividend
	idiv	dword [ten]	; quotient in eax
	mov	ebx,0		; clear register (upper part)
	mov	bl,[fracdig+ecx]; get next previous ASCII digit
	sub	bl,48		; convert ASCII digit to binary
	shl	ebx,16		; move binary point 16-bits
	add	eax,ebx		; + a_n-i
	loop	h7loop		; decrement ecx, jump on non zero
	mov	edx,0		; must clear upper dividend
	idiv	dword [ten]	; final divide
	
	mov	[eaxsave],eax	; save eax, printf destroys it
	push	dword eax	; print eax
	push	dword fmth	; format %X (look at low 16-bits)
	call	printf
	add	esp,8		; restore stack

; print the bits in eaxsave:
	section	.bss
abits:	resb	17		; 16 characters plus zero terminator
	section	.data
fmts:	db	"%s",10,0
	section	.text
	mov	eax,[eaxsave]	; restore eax
	ror	eax,1		; get bottom bit in top of eax
	mov	ecx,16		; for printing 16 bits
h8loop:	mov	edx,0		; clear edx ready for a bit
	shld	edx,eax,1	; top bit of eax into edx
	add	edx,48		; make it ASCII
	mov	[abits+ecx-1],dl ; store character
	ror	eax,1		; next bit into top of eax
	loop	h8loop		; decrement ecx, jump non zero
	
	mov	byte [abits+16],0 ; end of "C" string
	push	dword abits	; string to print
	push	dword fmts	; "%s"
	call	printf
	add	esp,8
	

	pop	edi
	pop	ebx
	mov	esp,ebp		; restore callers stack frame
	pop	ebp
	ret			; return

; output from execution:
; 5280
; 5280
; 6319
; 6319
; 6.319000e+03
; -8.549414e-01
; 1F97
; 0001111110010111