;************************************************
;* mulu8x8 (unsigned)
;*
;* Input : a, x
;* Output: prod_lo (x) / prod_hi (a)
;*
;* Trash: a,x,y
;*
;* Zeropage defines 
;* 
;* mul_a  
;* mul_b  
;* prod_lo
;* prod_hi
;*
;************************************************

mulu8x8
	sta	mul_a
	stx	mul_b

        ; sum = a+b
        lda	mul_a
        clc	
        adc	mul_b
        tay
        jsr	load_qs_word_by_carry

        ; diff = |a-b|
        lda	mul_a
        sec	
        sbc	mul_b
        bcs	@+
        eor	#$ff
        clc	
        adc	#1
@	tay
        clc
        jsr	sub_qs_word_by_carry
        
        ldx	prod_lo
        lda	prod_hi
        rts
    
;************************************************
;* muls8x8 (signed)
;*
;* Input : a, x
;* Output: prod_lo (x) / prod_hi (a)
;*
;* Trash: a,x,y
;*
;* Zeropage defines 
;* 
;* mul_a  
;* mul_b  
;* prod_lo
;* prod_hi
;*
;************************************************

muls8x8
	sta	mul_a
	stx	mul_b
	
        lda	mul_a
        eor	mul_b
        php                 ; n-flag (sr) to stack

        ; X = abs(a)
        lda	mul_a
        bpl	@+
        eor	#$FF
        clc	
        adc	#1
@	tax

        ; mul_b = abs(b)
        lda	mul_b
        bpl	@+
        eor	#$FF
        clc	
        adc	#1
@	sta	mul_b

        ; QS[sum]
        txa	
        clc	
        adc	mul_b
        tay
        jsr	load_qs_word_by_carry

        ; QS[diff]
        txa
        sec
        sbc	mul_b
        bcs	@+
        eor	#$ff
        clc	
        adc	#1
@	tay
        clc
        jsr	sub_qs_word_by_carry

        ; apply sign
        plp
        bpl	@+            		; N=0 => positivee

        ; prod = -prod (16-bit)
        sec
        lda	#0
        sbc	prod_lo
        sta	prod_lo
        lda	#0
        sbc	prod_hi
        sta	prod_hi

@    	ldx	prod_lo
        lda	prod_hi

	rts	

;------------------------------------------------
; QS helpers

load_qs_word_by_carry
        bcc	@+
	lda	QS_P1_LO,y
        sta	prod_lo
        lda	QS_P1_HI,y
        sta	prod_hi
        rts

@	lda	QS_P0_LO,y
        sta	prod_lo
        lda	QS_P0_HI,y
        sta	prod_hi
        rts

sub_qs_word_by_carry
        bcc	@+
	sec
        lda	prod_lo
        sbc	QS_P1_LO,y
        sta	prod_lo
        lda	prod_hi
        sbc	QS_P1_HI,y
        sta	prod_hi
        rts

@	sec
        lda	prod_lo
        sbc	QS_P0_LO,y
        sta	prod_lo
        lda	prod_hi
        sbc	QS_P0_HI,y
        sta	prod_hi
        rts

; QS[n] = floor(n*n/4) -> n=0..511, stored as page-selectable byte tables

QS_P0_LO	
	.byte	$00,$00,$01,$02,$04,$06,$09,$0C,$10,$14,$19,$1E,$24,$2A,$31,$38
        .byte   $40,$48,$51,$5A,$64,$6E,$79,$84,$90,$9C,$A9,$B6,$C4,$D2,$E1,$F0
        .byte   $00,$10,$21,$32,$44,$56,$69,$7C,$90,$A4,$B9,$CE,$E4,$FA,$11,$28
        .byte   $40,$58,$71,$8A,$A4,$BE,$D9,$F4,$10,$2C,$49,$66,$84,$A2,$C1,$E0
        .byte   $00,$20,$41,$62,$84,$A6,$C9,$EC,$10,$34,$59,$7E,$A4,$CA,$F1,$18
        .byte   $40,$68,$91,$BA,$E4,$0E,$39,$64,$90,$BC,$E9,$16,$44,$72,$A1,$D0
        .byte   $00,$30,$61,$92,$C4,$F6,$29,$5C,$90,$C4,$F9,$2E,$64,$9A,$D1,$08
        .byte   $40,$78,$B1,$EA,$24,$5E,$99,$D4,$10,$4C,$89,$C6,$04,$42,$81,$C0
        .byte   $00,$40,$81,$C2,$04,$46,$89,$CC,$10,$54,$99,$DE,$24,$6A,$B1,$F8
        .byte   $40,$88,$D1,$1A,$64,$AE,$F9,$44,$90,$DC,$29,$76,$C4,$12,$61,$B0
        .byte   $00,$50,$A1,$F2,$44,$96,$E9,$3C,$90,$E4,$39,$8E,$E4,$3A,$91,$E8
        .byte   $40,$98,$F1,$4A,$A4,$FE,$59,$B4,$10,$6C,$C9,$26,$84,$E2,$41,$A0
        .byte   $00,$60,$C1,$22,$84,$E6,$49,$AC,$10,$74,$D9,$3E,$A4,$0A,$71,$D8
        .byte   $40,$A8,$11,$7A,$E4,$4E,$B9,$24,$90,$FC,$69,$D6,$44,$B2,$21,$90
        .byte   $00,$70,$E1,$52,$C4,$36,$A9,$1C,$90,$04,$79,$EE,$64,$DA,$51,$C8
        .byte   $40,$B8,$31,$AA,$24,$9E,$19,$94,$10,$8C,$09,$86,$04,$82,$01,$80

QS_P0_HI	
	.byte	$00,$00,$00,$00,$00,$00,$00,$00,$00,$00,$00,$00,$00,$00,$00,$00
        .byte   $00,$00,$00,$00,$00,$00,$00,$00,$00,$00,$00,$00,$00,$00,$00,$00
        .byte   $01,$01,$01,$01,$01,$01,$01,$01,$01,$01,$01,$01,$01,$01,$02,$02
        .byte   $02,$02,$02,$02,$02,$02,$02,$02,$03,$03,$03,$03,$03,$03,$03,$03
        .byte   $04,$04,$04,$04,$04,$04,$04,$04,$05,$05,$05,$05,$05,$05,$05,$06
        .byte   $06,$06,$06,$06,$06,$07,$07,$07,$07,$07,$07,$08,$08,$08,$08,$08
        .byte   $09,$09,$09,$09,$09,$09,$0A,$0A,$0A,$0A,$0A,$0B,$0B,$0B,$0B,$0C
        .byte   $0C,$0C,$0C,$0C,$0D,$0D,$0D,$0D,$0E,$0E,$0E,$0E,$0F,$0F,$0F,$0F
        .byte   $10,$10,$10,$10,$11,$11,$11,$11,$12,$12,$12,$12,$13,$13,$13,$13
        .byte   $14,$14,$14,$15,$15,$15,$15,$16,$16,$16,$17,$17,$17,$18,$18,$18
        .byte   $19,$19,$19,$19,$1A,$1A,$1A,$1B,$1B,$1B,$1C,$1C,$1C,$1D,$1D,$1D
        .byte   $1E,$1E,$1E,$1F,$1F,$1F,$20,$20,$21,$21,$21,$22,$22,$22,$23,$23
        .byte   $24,$24,$24,$25,$25,$25,$26,$26,$27,$27,$27,$28,$28,$29,$29,$29
        .byte   $2A,$2A,$2B,$2B,$2B,$2C,$2C,$2D,$2D,$2D,$2E,$2E,$2F,$2F,$30,$30
        .byte   $31,$31,$31,$32,$32,$33,$33,$34,$34,$35,$35,$35,$36,$36,$37,$37
        .byte   $38,$38,$39,$39,$3A,$3A,$3B,$3B,$3C,$3C,$3D,$3D,$3E,$3E,$3F,$3F

QS_P1_LO	
	.byte	$00,$80,$01,$82,$04,$86,$09,$8C,$10,$94,$19,$9E,$24,$AA,$31,$B8
        .byte   $40,$C8,$51,$DA,$64,$EE,$79,$04,$90,$1C,$A9,$36,$C4,$52,$E1,$70
        .byte   $00,$90,$21,$B2,$44,$D6,$69,$FC,$90,$24,$B9,$4E,$E4,$7A,$11,$A8
        .byte   $40,$D8,$71,$0A,$A4,$3E,$D9,$74,$10,$AC,$49,$E6,$84,$22,$C1,$60
        .byte   $00,$A0,$41,$E2,$84,$26,$C9,$6C,$10,$B4,$59,$FE,$A4,$4A,$F1,$98
        .byte   $40,$E8,$91,$3A,$E4,$8E,$39,$E4,$90,$3C,$E9,$96,$44,$F2,$A1,$50
        .byte   $00,$B0,$61,$12,$C4,$76,$29,$DC,$90,$44,$F9,$AE,$64,$1A,$D1,$88
        .byte   $40,$F8,$B1,$6A,$24,$DE,$99,$54,$10,$CC,$89,$46,$04,$C2,$81,$40
        .byte   $00,$C0,$81,$42,$04,$C6,$89,$4C,$10,$D4,$99,$5E,$24,$EA,$B1,$78
        .byte   $40,$08,$D1,$9A,$64,$2E,$F9,$C4,$90,$5C,$29,$F6,$C4,$92,$61,$30
        .byte   $00,$D0,$A1,$72,$44,$16,$E9,$BC,$90,$64,$39,$0E,$E4,$BA,$91,$68
        .byte   $40,$18,$F1,$CA,$A4,$7E,$59,$34,$10,$EC,$C9,$A6,$84,$62,$41,$20
        .byte   $00,$E0,$C1,$A2,$84,$66,$49,$2C,$10,$F4,$D9,$BE,$A4,$8A,$71,$58
        .byte   $40,$28,$11,$FA,$E4,$CE,$B9,$A4,$90,$7C,$69,$56,$44,$32,$21,$10
        .byte   $00,$F0,$E1,$D2,$C4,$B6,$A9,$9C,$90,$84,$79,$6E,$64,$5A,$51,$48
        .byte   $40,$38,$31,$2A,$24,$1E,$19,$14,$10,$0C,$09,$06,$04,$02,$01,$00

QS_P1_HI	
	.byte	$40,$40,$41,$41,$42,$42,$43,$43,$44,$44,$45,$45,$46,$46,$47,$47
        .byte   $48,$48,$49,$49,$4A,$4A,$4B,$4C,$4C,$4D,$4D,$4E,$4E,$4F,$4F,$50
        .byte   $51,$51,$52,$52,$53,$53,$54,$54,$55,$56,$56,$57,$57,$58,$59,$59
        .byte   $5A,$5A,$5B,$5C,$5C,$5D,$5D,$5E,$5F,$5F,$60,$60,$61,$62,$62,$63
        .byte   $64,$64,$65,$65,$66,$67,$67,$68,$69,$69,$6A,$6A,$6B,$6C,$6C,$6D
        .byte   $6E,$6E,$6F,$70,$70,$71,$72,$72,$73,$74,$74,$75,$76,$76,$77,$78
        .byte   $79,$79,$7A,$7B,$7B,$7C,$7D,$7D,$7E,$7F,$7F,$80,$81,$82,$82,$83
        .byte   $84,$84,$85,$86,$87,$87,$88,$89,$8A,$8A,$8B,$8C,$8D,$8D,$8E,$8F
        .byte   $90,$90,$91,$92,$93,$93,$94,$95,$96,$96,$97,$98,$99,$99,$9A,$9B
        .byte   $9C,$9D,$9D,$9E,$9F,$A0,$A0,$A1,$A2,$A3,$A4,$A4,$A5,$A6,$A7,$A8
        .byte   $A9,$A9,$AA,$AB,$AC,$AD,$AD,$AE,$AF,$B0,$B1,$B2,$B2,$B3,$B4,$B5
        .byte   $B6,$B7,$B7,$B8,$B9,$BA,$BB,$BC,$BD,$BD,$BE,$BF,$C0,$C1,$C2,$C3
        .byte   $C4,$C4,$C5,$C6,$C7,$C8,$C9,$CA,$CB,$CB,$CC,$CD,$CE,$CF,$D0,$D1
        .byte   $D2,$D3,$D4,$D4,$D5,$D6,$D7,$D8,$D9,$DA,$DB,$DC,$DD,$DE,$DF,$E0
        .byte   $E1,$E1,$E2,$E3,$E4,$E5,$E6,$E7,$E8,$E9,$EA,$EB,$EC,$ED,$EE,$EF
        .byte   $F0,$F1,$F2,$F3,$F4,$F5,$F6,$F7,$F8,$F9,$FA,$FB,$FC,$FD,$FE,$FF