Daniele Verzotto - Ricerca MAttone di Diofanto

;
; Programma di Daniele Verzotto
; Ricerca dei Mattoni diofantei
; ASM 6502/6510
;---------------------------------
; Basic Loader
; 10 SYS2061

*=$0801

        BYTE    $0B, $08, $0A, $00, $9E, $32, $30, $36, $31, $00, $00, $00

;---------------------------------


                jmp Main


;---------------------------------Global Variables & definitions



_QU = 3000
_QUI= _QU-1
_timer = $A0     ;bytes 3
_timSQR bytes 3
_timTP bytes 3
_timBR bytes 3
_irqvec bytes 2

_CnvStr byte 0,0,0,0,0,0,0,0
ScrBase = $0400
ScrRow = $9b

_ArrTP = $2000
_ArrSq = $7600
_ArrBr = $c000

_pnt1 = $3
_pnt2 = $5
_bcd = $63
_lobyte = $c8
_mibyte = $c9
_hibyte = $ca

_regY = $2a

_cnt1 = $a3
_cnt2 = $a5
_sqcnt1 = $a7
_sqcnt2 = $aa
_lpKvalA = $57
_lpKvalB = $59
_lpKvalC = $5b
_pntBR = $5d
_pntSQ = $fb
_pntTP = $fd

_square  = $57     ; 4 bytes: $5b-$5e; input value
_sqrt    = $5F     ; 2 bytes: $5f-$60; result
_remainder = _M+2  ; 2 bytes: $5d-$5e; is in fact the high bytes of _M
_T       = $5B     ; 4 bytes: $57-$5a; could be 2 bytes: T+0 is always 0
_M       = $57     ; 4 bytes: $5b-$5e, over the input _square

dividend = $57
divisor  = $5a
remainder = $5d
pztemp    = $60

multiplier    = $61
multiplicand  = $63
product       = $57

bricks byte 0


;********************************************
;
;       CalcTP
;
;  descr: Cerca le TP con un doppio loop innestato (I,J); applicando Pitagora
;       verifica se il terzo lato è un numero intero: in quel caso è una TP
;       non calcola i quadrati, ma li recupera da quelli precalcolati
;       Il loop più interno (J) parte da I+1: non è necessario eseguire sia
;       IxJ che JxI; peraltro così ottengo una lista di TP ordinata secondo
;       il primo cateto (quello minore), e poi crescente anche per il secondo
;       cateto
;

CalcTP
        lda #0
        sta _cnt1
        sta _cnt1+1

        lda #<_ArrSq
        sta _sqcnt1
        lda #>_ArrSq
        sta _sqcnt1+1

        lda #<_ArrTP    ; <-- point to destination TP
        sta _pntTP
        lda #>_ArrTP
        sta _pntTP+1

_lpI    inc _cnt1       ; cnt1 += 1; cnt2=cnt1
        bne _incI
        inc _cnt1+1
_incI   lda _cnt1
        sta _cnt2
        lda _cnt1+1
        sta _cnt2+1
        clc
        lda #3          ; puntatore ai quadrati: si muove di 3 in 3
        adc _sqcnt1
        sta _pntSQ
        sta _sqcnt1
        lda #0
        adc _sqcnt1+1
        sta _pntSQ+1
        sta _sqcnt1+1

        ldy #0
        lda (_pntSQ),y
        sta _sqcnt2     ; load I^2
        iny
        lda (_pntSQ),y
        sta _sqcnt2+1
        iny
        lda (_pntSQ),y
        sta _sqcnt2+2
_lpJ            inc _cnt2       ; loop J: increments "J"
                bne _incJ
                inc _cnt2+1
_incJ           clc
                lda #3          ; increments pointer
                adc _pntSQ
                sta _pntSQ
                bcc _noinc
                inc _pntSQ+1
                clc
_noinc          ldy #0
                sty _square+3   ; 24bit: squareHI=0
                lda (_pntSQ),y  ; J^2 + I^2
                adc _sqcnt2
                sta _square
                iny
                lda (_pntSQ),y
                adc _sqcnt2+1
                sta _square+1
                iny
                lda (_pntSQ),y
                adc _sqcnt2+2
                sta _square+2

                jsr sqrt32

                lda _remainder    ; verifica se il resto è 0 (cioè la radice è intera)
                ora _remainder+1
                bne _nxtTP
                                ; è una TP; salviamola
                ldy #0
                lda _cnt1
                sta (_pntTP),y
                iny
                lda _cnt1+1
                sta (_pntTP),y
                iny
                lda _cnt2
                sta (_pntTP),y
                iny
                lda _cnt2+1
                sta (_pntTP),y

                clc             ; muove il puntatore in avanti per la prox TP
                lda #4
                adc _pntTP
                sta _pntTP
                bcc _nxtTP
                inc _pntTP+1
_nxtTP
                lda _cnt2       ; verifica che il loop J non sia giunto alla fine
                cmp #<_QU
                lda _cnt2+1
                sbc #>_QU
                bcc _lpJ
        jsr PrintNum
        lda _cnt1       ; verifica che il loop I non sia giunto alla fine
        cmp #<_QUI
        lda _cnt1+1
        sbc #>_QUI
        bcs _endctp
        jmp _lpI
_endctp
        rts



align 64
;********************************************
;*    sqrt32
;*
;*   computes Sqrt of a 32bit number
;*
;*      input:  _square, the 4-byte source number
;*      output: _sqrt, 16bit value
;*              _remainder, 16bit value
;*
;* implements:
;*
;        R= 0
;        M= N
;        D= 2^(p-1)
;        for n= 1 to p
;        {
;            T= (R+R+D) ASL (p-1)
;            if (T <= M) then M=M-T: R=R+D
;            M= M ASL 1
;            D= D LSR 1
;        }
;   p: number of bits of the result
;

;_tosq16
;        jmp sqrt16

sqrt32
;        lda _square+2
;        ora _square+3
;        beq _tosq16

        lda #0
        sta _sqrt       ; R=0
        sta _sqrt+1
        sta _M+4        ; aka T+0
        ;sta _T+1       ; T+1 is zero until last iteration; T+0 is always 0

        ldy #6         ; 7 iterations (6-->0)
_loop6
;        lda _sqrt  ; (2*R+D) LSR 1; actually: R+(D LSR 1)
;;        ora stablo,y  ;   [Dlo=0 during this iterations]
;        sta _T+2       ;   [sqrt+0 =0 during this iterations]
        lda _sqrt+1    ; would be stabhi,y but changed the counter
        ora stablo,y
        sta _T+3
;;;;        bcs skip06          ;;;useless in this project

        lda _M+3
        cmp _T+3
        bcc skip16       ; T <= M    (branch if T>M)
;        bne skip06
;        lda _M+2
;        sbc _sqrt       ; T+2 = _sqrt =0 during this iterations
;        bcc skip16
skip06   ;sec
;        lda _M+2        ; M=M-T
;;        sbc _T+2
;        sbc _sqrt      ; T+2=sqrt+0  =0 during this iterations
;        sta _M+2
        lda _M+3
        sbc _T+3
        sta _M+3
;        lda _sqrt      ; R=R+D   ; stablo+1,y is zero during this iterations
;        ora stablo+1,y
;        sta _sqrt
        lda _sqrt+1
        ora stablo+1,y    ; would be stabhi,y but changed the counter
        sta _sqrt+1
skip16
        asl _M          ; M=M*2
        rol _M+1
        rol _M+2
        rol _M+3
        dey             ; implicit: D=D/2, by the move of .Y
        bpl _loop6

                        ; 8th iteration
_loop8
;        lda #$80  ; (2*R+D) LSR 1; actually: R+(D LSR 1)
;        ora _sqrt       ; _sqrt = 0
;        sta _T+2
;        lda _sqrt+1          ; stabhi,y = 0 during this iterations
;        sta _T+3
;;;;        bcs skip08          ;;;useless in this project

        lda _M+3
        cmp _sqrt+1     ; T+3=_sqrt+1
        bcc skip18      ; T <= M    (branch if T>M)
        bne skip08
        lda _M+2
        sbc #$80        ; T+2=$80
        bcc skip18
skip08   ;sec
        lda _M+2        ; M=M-T
        sbc #$80        ; T+2=$80
        sta _M+2
        lda _M+3
        sbc _sqrt+1     ; T+3=_sqrt+1
        sta _M+3
;        lda _sqrt      ; R=R+D
;        ora stablo+1,y         ; stablo+1,y =0 during this iteration
;        sta _sqrt
;        lda _sqrt+1
;        ora #1
;        sta _sqrt+1
        inc _sqrt+1
skip18
        asl _M          ; M=M*2
        rol _M+1
        rol _M+2
        rol _M+3

        ldy #6         ; 7 iterations (6-->0)
_loop9
        lda stablo,y  ; (2*R+D) LSR 1; actually: R+(D LSR 1)
        ora _sqrt
        sta _T+2
;        lda _sqrt+1     ; stabhi,y = 0 during this iterations
;        sta _T+3
;;;;        bcs skip09          ;;;useless in this project

        lda _M+3
        cmp _sqrt+1     ; T+3=_sqrt+1
        bcc skip19      ; T <= M    (branch if T>M)
        bne skip09
        lda _M+2
        sbc _T+2
        bcc skip19
skip09   ;sec
        lda _M+2        ; M=M-T
        sbc _T+2
        sta _M+2
        lda _M+3
        sbc _sqrt+1     ; T+3=_sqrt+1
        sta _M+3
        lda _sqrt       ; R=R+D
        ora stablo+1,y
        sta _sqrt
;        lda _sqrt+1
;        adc #0          ; stabhi+1,y =0 during this iterations
;        sta _sqrt+1
;        lda _M          ; _M+0=0 during this iterations
;        lda _M+1
;        ora _M+2
;        ora _M+3
;        beq _sqrend     ; if M=0 then exit
skip19
;        asl _M          ; M=M*2
;        rol _M+1        ; _M+0 =0 during this iterations
        asl _M+1
        rol _M+2
        rol _M+3
        dey             ; implicit: D=D/2, by the move of .Y
        bpl _loop9

_lastiter               ; code for last iteration
        ; during last iteration D=1, so (2*R+D) LSR 1 makes D the MSB of T+1
;;;;        bcs skp0          ;;;useless in this project

        lda _M+3
        cmp _sqrt+1    ; T+3 = _sqrt+1
        bcc skp1       ; T <= M    branch if T>M
        bne skp0
        lda _M+2
        cmp _sqrt      ; T+2 = _sqrt
        bcc skp1
        bne skp0
        lda _M+1
        cmp #$80        ; T+1 = $80
        bcc skp1
skp0    ;sec
        lda _M+1
        sbc #$80        ; T+1 = $80
        sta _M+1
        lda _M+2        ; M=M-T
        sbc _sqrt
        sta _M+2
        lda _M+3
        sbc _sqrt+1
        sta _M+3
        inc _sqrt      ; R=R+D with D=1
skp1    ;asl _M          ; M=M*2
        asl _M+1
        rol _M+2
        rol _M+3
        rol _M+4
_sqrend rts

;stabhi byte 0,0,0,0,0,0,0,0
stablo BYTE $01,$02,$04,$08,$10,$20,$40,$80
;       byte 0,0,0,0,0,0,0,0



;;********************************************
;MyTimer
;        inc _timer
;        bne _go2irq
;        inc _timer+1
;        bne _go2irq
;        inc _timer+2
;_go2irq
;        jmp (_irqvec)


;********************************************
;
;       Main
;
; descr: richiama i quattro blocchi di elaborazione:
;                - Calcolo dei Quadrati
;                - Calcolo delle TP
;                - Ricerca dei mattoni
;                - Stampa della lista dei mattoni
;

Main
        lda #0
        sta _timer
        sta _timer+1
        sta _timer+2

;        sei
;        lda $314
;        sta _irqvec
;        lda $315
;        sta _irqvec+1

;        lda #<MyTimer
;        sta $314
;        lda #>MyTimer
;        sta $315
;        cli

        lda #$20
        jsr ClearScreen

        ldx #3
        ldy #3
        jsr SetCurs
        lda #<_qdr
        ldx #>_qdr
        jsr PrintAt
        lda #<_QU
        sta _lobyte
        lda #>_QU
        sta _hibyte
        jsr _ItoA
        lda #<_CnvStr
        ldx #>_CnvStr
        jsr ChainPrint
                jsr CalcQuad      ; calcola la tabella dei quadrati (24bit)
        lda _timer+2
        sta _timSQR
        lda _timer+1
        sta _timSQR+1
        lda _timer+0
        sta _timSQR+2
        ldx #10
        ldy #4
        jsr SetCurs
        jsr PrintTime


        ldx #3
        ldy #6
        jsr SetCurs
        lda #<_ctp
        ldx #>_ctp
        jsr PrintAt
                jsr CalcTP        ; calcola le terne pitagoriche (2x 16bit)
        lda _timer+1
        sta _timTP
        lda _timer+1
        sta _timTP+1
        lda _timer+0
        sta _timTP+2
        ldx #10
        stx $d3
        ldy #7
        sty $d6
        jsr SetCurs
        jsr PrintTime


        ldx #3
        ldy #9
        jsr SetCurs
        lda #<_brk
        ldx #>_brk
        jsr PrintAt
                jsr SearchBricks  ; cerca i mattoni nelle terne e produce lista (3x 16bit)
        lda _timer+2
        sta _timBR
        lda _timer+1
        sta _timBR+1
        lda _timer+0
        sta _timBR+2
        ldx #10
        ldy #10
        jsr SetCurs
        jsr PrintTime

;        sei
;        lda _irqvec
;        sta $314
;        lda _irqvec+1
;        sta $315
;        cli

                jsr PrintBricks   ; Stampa la lista dei mattoni

        rts

_qdr byte 'calcolo dei quadrati:', 0
_ctp byte 'calcolo delle terne: ', 0
_brk byte 'ricerca dei mattoni:     0', 0
_tot byte '  tempo totale:   ', 0
_sec byte ' sec',0





;********************************************
;
;       SearchBricks
;
; descr: ricerca i mattoni all'interno della lista delle TP
;       La lista delle TP è costituita da coppie ordinate (A,B), dove B>A e
;       l'elemento successivo della lista è tale che An+1 >= An e Bn+1 > Bn:
;       la lista è ordinata.
;       Sono tre loop innestati: nel più esterno scorro la lista
;       elemento per elemento: cerco in avanti (secondo loop) un'altra TP
;       che abbia lo stesso primo termine; ho quindi un termine B1 proveniente
;       dalla prima TP e un termine B2 proveniente dalla seconda; B1 < B2.
;       Cerco in avanti (terzo loop) una TP con B1 al primo termine e B2 al
;       secondo. Se la trovo, questo è un mattone

align 64
_toNextI
        jmp _nextI
SearchBricks
        ldx #0
        stx bricks

        lda #<_ArrBr    ; puntatore alla lista dei mattoni trovati
        sta _pntBR
        lda #>_ArrBr
        sta _pntBR+1

        lda #<_ArrTP    ; puntatore alla lista delle TP
        sta _cnt1
        sta _cnt2
        lda #>_ArrTP
        sta _cnt1+1
        sta _cnt2+1

        ; I loop
_reI    ldy #0          ; for i=0 to _pntTP-1
        lda (_cnt1),y
        sta _lpKvalA
        iny
        lda (_cnt1),y
        sta _lpKvalA+1

                ; J loop
_reJ            lda _cnt2        ; for j=i+1 to _pntTP-1
                clc
                adc #4
                sta _cnt2
                bcc _noJHiInc
                inc _cnt2+1

_noJHiInc       lda _pntTP+1     ; verifica se siamo oltre la fine
                cmp _cnt2+1
                bcc _nextI     ; J > fine
                bne _tryJ
                lda _pntTP
                cmp _cnt2
                bcc _nextI     ; J > fine

_tryJ           ldy #0          ; .Y=0
                lda _lpKvalA
                cmp (_cnt2),y   ; gli elementi successivi con primo termine uguale
                bne _nextI      ; saranno vicini: se il termine è diverso => loop esterno
                iny             ; .Y=1
                lda _lpKvalA+1
                cmp (_cnt2),y
                bne _nextI

                        ; K loop                ; for k=j+1 to _pntTP-1
                        iny             ; .Y=2
                        lda (_cnt1),y
                        sta _lpKvalB
                        lda (_cnt2),y
                        sta _lpKvalC
                        iny             ; .Y=3
                        lda (_cnt1),y
                        sta _lpKvalB+1
                        lda (_cnt2),y
                        sta _lpKvalC+1

                        lda _cnt2
                        clc
                        adc #4
                        sta _sqcnt1
                        lda _cnt2+1
                        adc #0
                        sta _sqcnt1+1

_reK                    ldy #1          ; .Y=1
                        lda _lpKvalB+1
                        cmp (_sqcnt1),y
                        bcc _reJ          ;se mHI(k1)>mHI(i2)  => prox J
                        bne _nextK        ;se mHI(k1)!=mHI(i2) => m(k1)<m(i2) => prox K
                        dey             ; .Y=0
                        lda _lpKvalB
                        cmp (_sqcnt1),y
                        bcc _reJ          ;se mLO(k1)>mLO(i2)  => prox J
                        bne _nextK        ;se mLO(k1)!=mLO(i2) => m(k1)<m(i2) => prox K

                        ; m(k1)=m(i2); vediamo se m(k2)=m(j2)
                        ldy #3          ; .Y=3
                        lda _lpKvalC+1
                        cmp (_sqcnt1),y
                        bcc _reJ          ;se mHI(k2)>mHI(j2)  => prox J
                        bne _nextK        ;se mHI(k2)!=mHI(j2) => m(k2)<m(j2) => prox K
                        dey             ; .Y=2
                        lda _lpKvalC
                        cmp (_sqcnt1),y
                        bcc _reJ          ;se mLO(k2)>mLO(j2)  => prox J
                        ;bne _nextK        ;se mLO(k2)!=mLO(j2) => m(k2)<m(j2) => prox K
                        beq _found
                        ;jmp _found

_nextK                  clc             ; punta alla prox TP
                        lda _sqcnt1
                        adc #4
                        sta _sqcnt1
                        bcc _noKHiInc
                        inc _sqcnt1+1

_noKHiInc               lda _pntTP+1    ; verifica che non siamo alla fine
                        cmp _sqcnt1+1
                        bcc _nextJ     ; K > fine
                        bne _reK
                        lda _pntTP
                        cmp _sqcnt1
                        bcc _nextJ     ; K > fine
                        bne _reK
                        ;jmp _reK

_nextJ          jmp _reJ

_nextI  clc
        lda _cnt1       ; si sposta alla prox TP
        adc #4
        sta _cnt1
        sta _cnt2
        lda _cnt1+1
        adc #0
        sta _cnt1+1
        sta _cnt2+1

        lda _pntTP+1    ; verifica che non siamo alla fine
        cmp _cnt1+1
        bcc _endloop
        bne _toreI
        lda _pntTP
        cmp _cnt1
        bcc _endloop
        beq _endloop
_toreI  jmp _reI
_endloop
        ldx bricks
        stx _lobyte
        ldx #0
        stx _hibyte
        jsr _ItoA
        ldx #24
        ldy #9
        jsr SetCurs
        lda #<_CnvStr
        ldx #>_CnvStr
        jmp PrintAt

_found                  ; trovato! m(k1)=m(i2) e m(k2)=m(j2)
                        inc bricks      ; aumenta il contatore
                        ldx bricks
                        stx _lobyte     ; stampa il numero di mattoni trovati
                        ldx #0
                        stx _hibyte
                        ldx #24
                        ldy #9
                        jsr SetCurs
                        jsr _ItoA
                        lda #<_CnvStr
                        ldx #>_CnvStr
                        jsr PrintAt

                        ldy #0          ; salva i 3 valori e la loro somma
                        lda _lpKvalA
                        sta (_pntBR),y
                        iny             ; .Y=1
                        lda _lpKvalA+1
                        sta (_pntBR),y
                        iny             ; .Y=2
                        lda _lpKvalB
                        sta (_pntBR),y
                        iny             ; .Y=3
                        lda _lpKvalB+1
                        sta (_pntBR),y
                        iny             ; .Y=4
                        clc
                        lda _lpKvalC
                        sta (_pntBR),y
                        adc _lpKvalA               ; Alo + Clo
                        sta _lpKvalC
                        iny             ; .Y=5
                        lda _lpKvalC+1
                        sta (_pntBR),y
                        adc _lpKvalA+1             ; Ahi + Chi
                        sta _lpKvalC+1
                        iny             ; .Y=6
                        clc
                        lda _lpKvalC
                        adc _lpKvalB               ; Alo + Blo + Clo
                        sta (_pntBR),y
                        iny             ; .Y=7
                        lda _lpKvalC+1
                        adc _lpKvalB+1             ; Ahi + Bhi + Chi
                        sta (_pntBR),y
                        clc
                        lda #8
                        adc _pntBR
                        sta _pntBR
                        bcc _tonextJ
                        inc _pntBR+1
_tonextJ                jmp _reJ
                        ;jmp _aftfound


;********************************************
;
;       CalcQuad
;
; descr: calcola i quadrati dei numeri 0-3000, e li mette in una lista
;       vengono salvati solo 3 bytes (24 bit) perché sufficienti
;

CalcQuad
        lda #>_ArrSq
        sta _pntSQ+1
        lda #<_ArrSq+3
        sta _pntSQ

        ldx #0
        stx _cnt1
        stx _cnt1+1

_lp     inc _cnt1       ; cnt1 += 1
        bne _next
        inc _cnt1+1

_next   lda _cnt1       ; prepara la moltiplicazione del numero per sé stesso
        sta multiplier
        sta multiplicand
        lda _cnt1+1
        sta multiplier+1
        sta multiplicand+1

        jsr mult16      ; richiama la moltiplicazione

        ldy #0          ; salva il prodotto nella lista (solo 3 byte)
        lda product
        sta (_pntSQ),y
        iny
        lda product+1
        sta (_pntSQ),y
        iny
        lda product+2
        sta (_pntSQ),y

        clc
        lda #3          ; sposta il puntatore
        adc _pntSQ
        sta _pntSQ
        bcc _prx
        inc _pntSQ+1

_prx    lda _cnt1       ; verifica che non sia alla fine
        cmp #<_QU
        lda _cnt1+1
        sbc #>_QU
        bcc _lp
        rts


;********************************************
PrintNum
        ldy #6
        ldx #24
        jsr SetCurs

        lda _cnt1
        sta _lobyte
        lda _cnt1+1
        sta _hibyte
        jsr _ItoA
        lda #<_CnvStr
        ldx #>_CnvStr
        jmp PrintAt



;********************************************
WaitForSpace            ;thanx to Phaze101
        lda     #$7f    ;%01111111 - only row 7 KB matrix
        sta     $dc00
        lda     $dc01
        and     #$10    ;mask %00010000
        bne     WaitForSpace
        rts

_waitkey byte 'premere spazio per la lista',0



;********************************************
;
;       PrintBricks
;
; descr: stampa la lista dei mattoni trovati. Stampa solo i mattoni primitivi.
;       E' hackerata un po' brutalmente in maniera da saltare i mattoni
;       non primitivi, come richiesto dal challenge
;

PrintBricks
        ldy #20
        ldx #8
        jsr SetCurs
        lda #<_waitkey
        ldx #>_waitkey
        jsr PrintAt

        jsr WaitForSpace
        lda #$20
        jsr ClearScreen

        lda #<_ArrBr
        sta _cnt1
        lda #>_ArrBr
        sta _cnt1+1

        lda bricks
        lsr
        sta _cnt2+1
        lda #0
        sta _cnt2


        sta _regY

        lda #10
        sta _cnt2+1

_loop1clmn
                jsr CheckIfP
                lda _PoD
                bne _1np

                ldy _cnt2
                iny
                iny
                ldx #2
                jsr SetCurs
                ldy #0
                lda (_cnt1),y
                sta _lobyte
                iny
                lda (_cnt1),y
                sta _hibyte
                iny
                sty _regY
                jsr _ItoA       ; conversion
                ldx #>_CnvStr
                lda #<_CnvStr
                jsr PrintAt     ; print

                ldy _regY
                lda (_cnt1),y
                sta _lobyte
                iny
                lda (_cnt1),y
                sta _hibyte
                iny
                sty _regY
                jsr _ItoA       ; conversion
                ldx #>_CnvStr
                lda #<_CnvStr
                jsr ChainPrint     ; print

                ldy _regY
                lda (_cnt1),y
                sta _lobyte
                iny
                lda (_cnt1),y
                sta _hibyte
                iny
                sty _regY
                jsr _ItoA       ; conversion
                ldx #>_CnvStr
                lda #<_CnvStr
                jsr ChainPrint     ; print

                ldx #>_BrPR
                lda #<_BrPR
                jsr ChainPrint

_1np            clc
                lda #8
                adc _cnt1
                sta _cnt1
                lda _cnt1+1
                adc #0
                sta _cnt1+1
                lda _PoD
                bne _loop1clmn

                ldx _cnt2
                inx
                stx _cnt2
                cpx _cnt2+1
                bne _loop1clmn

                jmp _ep

                sec
                lda bricks
                sbc _cnt2+1
                sta _cnt2+1
                lda #0
                sta _cnt2

_loop2clmn
                jsr CheckIfP
                ldy _cnt2
                iny
                iny
                ldx #22
                jsr SetCurs
                ldy #0
                lda (_cnt1),y
                sta _lobyte
                iny
                lda (_cnt1),y
                sta _hibyte
                iny
                sty _regY
                jsr _ItoA       ; conversion
                ldx #>_CnvStr
                lda #<_CnvStr
                jsr PrintAt     ; print

                ldy _regY
                lda (_cnt1),y
                sta _lobyte
                iny
                lda (_cnt1),y
                sta _hibyte
                iny
                sty _regY
                jsr _ItoA       ; conversion
                ldx #>_CnvStr
                lda #<_CnvStr
                jsr ChainPrint     ; print

                ldy _regY
                lda (_cnt1),y
                sta _lobyte
                iny
                lda (_cnt1),y
                sta _hibyte
                iny
                sty _regY
                jsr _ItoA       ; conversion
                ldx #>_CnvStr
                lda #<_CnvStr
                jsr ChainPrint     ; print

                lda _PoD
                bne _2np
                ldx #>_BrPR
                lda #<_BrPR
                jsr ChainPrint

_2np            clc
                lda #8
                adc _cnt1
                sta _cnt1
                lda _cnt1+1
                adc #0
                sta _cnt1+1

                ldx _cnt2
                inx
                stx _cnt2
                cpx _cnt2+1
                bne _loop2clmn

_ep     ldx #3
        ldy #23
        jsr SetCurs
        lda #<_elab
        ldx #>_elab
        jsr PrintAt
        ldx #26
        ldy #23
        jsr SetCurs


        lda _timBR
        sta _timer+2
        lda _timBR+1
        sta _timer+1
        lda _timBR+2
        sta _timer
        jsr PrintTime

        jsr WaitForSpace

        rts
_BrPR byte ' p',0
_BrDR byte ' d',0
_elab byte 'Tempo di elaborazione: ',0



;********************************************
;
;       CheckIFP
;
; descr: controlla se il mattone corrente è primitivo: cerca all'indietro
;       nella lista dei mattoni, dividendo la somma dei termini per la somma
;       dei termini dei mattoni precedenti: se il resto della divisione è 0
;       allora il mattone non è primitivo
;
_PoD   byte 0
CheckIfP
        lda #0
        sta _PoD
        lda _cnt1
        sta _sqcnt1
        lda _cnt1+1
        sta _sqcnt1+1

_lpSrchDer
        sec
        lda _sqcnt1
        sbc #8
        sta _sqcnt1
        lda _sqcnt1+1
        sbc #0
        sta _sqcnt1+1
        cmp #>_ArrBr
        bcc _endsearch
        bne _dotest
        lda _sqcnt1
        cmp #<_ArrBr
        bcc _endsearch
_dotest ldy #6
        lda (_cnt1),y
        sta dividend
        lda (_sqcnt1),y
        sta divisor
        iny
        lda (_cnt1),y
        sta dividend+1
        lda (_sqcnt1),y
        sta divisor+1
        lda #0
        sta dividend+2
        jsr div24
        lda remainder
        ora remainder+1
        bne _lpSrchDer

        dec _PoD
_endsearch
        rts



;--------------------------------------
; Call with
; .X = value of horizontal pos
; .Y = value of vertical pos
;
; thanx to Phaze101
;--------------------------------------

SetCurs
        lda #0
        sta _pnt1
        sta _pnt1+1
        cpy #0                 ;first line: no need to add rows
        beq AddColumn-1

        clc
CalcRow
        tya             ;2                max(Y)=25
        asl             ;2   A= Y x 2
        asl             ;2   A= Y x 4
        sty _pnt1-1     ;3
        adc _pnt1-1     ;3   A= Y x 5
        asl             ;2   A= Y x 10 (still contained in one byte)
        asl             ;2   A= Y x 20 (now needs two bytes)
        rol _pnt1+1     ;5    flows on high byte
        asl             ;2   A= Y x 40
        rol _pnt1+1     ;5    flows on high byte
        sta _pnt1       ;3   stores on low byte

AddColumn
        clc
        txa
        adc     _pnt1
        sta     _pnt1
        bcc AddScrBase
        inc     _pnt1+1

        clc                     ;Add position to base address
AddScrBase
        ;lda     _pnt1
        adc     #<ScrBase
        sta     _pnt2
        lda     #>ScrBase
        adc     _pnt1+1
        sta     _pnt2+1

        rts

;-------------------------------
; Converts a 16bit number in BCD
;-------------------------------
_ItoA
;        lda #0
;        sta _CnvStr
;        sta _CnvStr+1
;        sta _CnvStr+2
;        sta _CnvStr+3
;        sta _CnvStr+4
;        sta _CnvStr+5


BINBCD16        SED             ; Switch to decimal mode
                LDA #0          ; Ensure the result is clear
                STA _bcd+0
                STA _bcd+1
                STA _bcd+2
                LDX #16         ; The number of source bits
CNVBIT          ASL _lobyte     ; Shift out one bit
                ROL _hibyte
                LDA _bcd+0      ; And add into result
                ADC _bcd+0
                STA _bcd+0
                LDA _bcd+1      ; propagating any carry
                ADC _bcd+1
                STA _bcd+1
                LDA _bcd+2      ; ... thru whole result
                ADC _bcd+2
                STA _bcd+2
                DEX             ; And repeat for next bit
                BNE CNVBIT
                CLD             ; Back to binary

                ;rts             ; All Done.


;-------------------------------
; Converts a 16bit unsigned number into string
;-------------------------------
;_ItoA
        ;jsr BinBcd16
        ;lda _bcd+2
        and #$0f
        ora #$30
        sta _CnvStr+0

        lda _bcd+1
        and #$0f
        ora #$30
        sta _CnvStr+2
        lda _bcd+1
        lsr
        lsr
        lsr
        lsr
        ora #$30
        sta _CnvStr+1

        lda _bcd+0
        and #$0f
        ora #$30
        sta _CnvStr+4
        lda _bcd+0
        lsr
        lsr
        lsr
        lsr
        ora #$30
        sta _CnvStr+3
        lda #0
        sta _CnvStr+5
;        rts                    ; uncomment to avoid stripping leading 0s

        ldx #0                  ;remove 0s at beginning
        stx _CnvStr+6
_rem0   lda _CnvStr,x
        cmp #$30
        bne _rts
        lda #$20                ;put a space instead
        sta _CnvStr,x
        inx
        cpx #$5
        bne _rem0

_rts    rts



;--------------------------------------
; PrintAt, ChainPrint
; Call with
; .A = low  byte of the string
; .X = high byte of the string
;
; thanx to Phaze101
;--------------------------------------
PrintAt
        ldy #$0
        sta _pnt1
        stx _pnt1+1
        jmp _ln
_PrtLoop
        sta (_pnt2),y
        iny
_ln     lda (_pnt1),y
        bne _PrtLoop

        sty _PAdisp
        rts

_PAdisp   byte 0

ChainPrint
        sta _pnt1
        stx _pnt1+1
        lda _PAdisp
        ldy #0
        clc
        adc _pnt2
        sta _pnt2
        bcc _ln
        inc _pnt2+1
        bcs _ln



;--------------------------------------
; Call with
; .A = value of the character to use to fill the screen
;
; thanx to Phaze101
;--------------------------------------
ClearScreen    ldx #+124 ; init index
ClrLoop        sta ScrBase,x
               sta ScrBase+125,x
               sta ScrBase+250,x
               sta ScrBase+375,x
               sta ScrBase+500,x
               sta ScrBase+625,x
               sta ScrBase+750,x
               sta ScrBase+875,x
               dex
               bpl ClrLoop
               rts




;********************************************
mult16
        lda     #$00
        sta     product+2       ; clear upper bits of product
        sta     product+3
        ldx     #$10            ; set binary count to 16
sh_r    lsr     multiplier+1    ; divide multiplier by 2
        ror     multiplier
        bcc     rot_r
        clc
        lda     product+2       ; get upper half of product and add multiplicand
        adc     multiplicand
        sta     product+2
        lda     product+3
        adc     multiplicand+1
rot_r   ror                     ; rotate partial product
        sta     product+3
        ror     product+2
        ror     product+1
        ror     product
        dex
        bne     sh_r
        rts



;********************************************
PrintTime
        lda _timer+2
        sta dividend
        lda _timer+1
        sta dividend+1
        lda _timer+0
        sta dividend+2
        lda #60
        sta divisor
        lda #0
        sta divisor+1
        sta divisor+2
        jsr div24
        lda dividend
        sta _lobyte
        lda dividend+1
        sta _hibyte
;        lda dividend+2
;        sta _hibyte
        jsr _ItoA
        lda #<_CnvStr
        ldx #>_CnvStr
        jsr PrintAt
        lda #<_sec
        ldx #>_sec
        jmp ChainPrint


align 63
;********************************************
div24   lda #0          ;preset remainder to 0
        sta remainder
        sta remainder+1
        sta remainder+2
        ldx #24         ;repeat for each bit: ...

divloop asl dividend    ;dividend lb & hb*2, msb -> Carry
        rol dividend+1
        rol dividend+2
        rol remainder   ;remainder lb & hb * 2 + msb from carry
        rol remainder+1
        rol remainder+2
        lda remainder
        sec
        sbc divisor     ;substract divisor to see if it fits in
        tay             ;lb result -> Y, for we may need it later
        lda remainder+1
        sbc divisor+1
        sta pztemp
        lda remainder+2
        sbc divisor+2
        bcc skip        ;if carry=0 then divisor didn't fit in yet

        sta remainder+2 ;else save substraction result as new remainder,
        lda pztemp
        sta remainder+1
        sty remainder
        inc dividend    ;and INCrement result cause divisor fit in 1 times

skip    dex
        bne divloop
        rts





;********************************************
;*    sqrt16
;*
;*   computes Sqrt of a 16bit number
;*
;*      input:  square, the 2-byte source number
;*      output: sqrt, 8bit value
;*              remnd, 8bit value
;*

sqrt16
        lda #0
        ;sta _sqrt      ; R=0
        sta _sqrt+1
        sta _M+2
        ;sta T          ; (T+0) is zero until last iteration
        tax

        ldy #6          ; 7 iterations (6-->0) + last iteration
loopsq16
        txa             ; _sqrt
        ora stablo,y    ; (2*R+D) LSR 1; actually: R+(D LSR 1)
        sta _T+1

        lda _M+1

        bcs skip016

        cmp _T+1
        bcc skip116
skip016   ;sec
        sbc _T+1         ; M=M-T
        sta _M+1
        txa              ; R=R+D
        ora stablo+1,y
        tax
skip116
        asl _M           ; M=M*2
        rol _M+1
        dey              ; implicit: D=D/2, by the decrement of .Y
        bpl loopsq16
lastiter16               ; code for last iteration
        ; during last iteration D=1, so [(2*R+D) LSR 1] makes D the MSB of T+1
        stx _sqrt
        bcs skp016
        lda _M+1
        cmp _sqrt        ; (T+1) = sqrtLO
        bcc skp116
        bne skp016
        lda _M
        cmp #$80         ; value of (T+0) during last iteration
        bcc skp116
skp016    ;sec
        lda _M
        sbc #$80         ; (T+0) during last iteration
        sta _M
        lda _M+1         ; M=M-T
        sbc _sqrt        ; (T+1)
        sta _M+1
        inc _sqrt        ; R=R+D with D=1
skp116
        asl _M           ; M=M*2
        rol _M+1
        lda _M+2         ; remainder to M+2/M+3
        rol
        sta _M+3
        lda _M+1
        sta _M+2
        rts