Array Sort

[iAN CooG]

 Su comp.sys.cbm c'e' il solito Rick Balkins (Wildstar) che sbrocca sul progetto CSDoom, dice di essere un programmatore quando non sa manco cosa servono LDA STA e i ";" nei sorgenti asm. L'hanno sfidato a scrivere un programma in asm, senza copiarlo - come ha gia' fatto dal sito di Richard Bayliss. :D
Ad ogni modo, si tratta di scrivere un prg che riordini un array di 256 bytes.
Questo e' quello che sono riuscito a fare.

Codice: [Seleziona]

; sort a 256 byte array at $c100
; challenge set up by MagerValp to Wildstar on COMP.SYS.CBM :D
; Message-ID: <p14hdo4fak2.fsf@panini.cling.gu.se>
; thread "wildstar.hollosite.com - request to be shutdown."
; iAN CooG/HokutoForce
        org $c000
array   = $c100
FIRST   = $fb
SECOND  = $fd

        ldy #1
        sty SECOND     ; $C101
        dey
        sty FIRST      ; $C100
        lda #>array
        sta FIRST+1
        sta SECOND+1
loop    
        lda (SECOND),y
        cmp (FIRST),y
        bcs noswap     ; 2nd less than 1st , swap them
        pha            ;A = (SECOND)
        lda (FIRST),y
        sta (SECOND),y
        pla
        sta (FIRST),y
noswap  
        inc SECOND
        bne loop       ; checked all 2nd elements? 1st is the lower now
        ldx FIRST      ; now set next ptrs: $C101 and $C102
        inx
        stx FIRST
        inx
        beq exit       ; if 2nd = $ff we can exit
        stx SECOND
        bne loop
exit  
        rts

Si puo' ottimizzare, o al limite ridurre?

[iAN CooG]

 

Si puo' ottimizzare, o al limite ridurre?

ridurre si puo'

Codice: [Seleziona]

       org $c000

array   = $c100

loop    
        ldy #$00
        ldx #$01
next    
        lda array,x  ; C100+x = $c101
        cmp array-1,x; C0ff+x = $c100
        bcs cont
swap    
        pha
        lda array-1,x
        sta array,x
        pla
        sta array-1,x
        iny            ; Y>0 = flag to repeat all
cont    
        inx
        bne next
        cpy #$00       ; a swap was done?
        bne loop       ; then repeat
        rts            ; else we're done
sono 16 istruzioni in 32 bytes, contro le 25 in 44b della mia prima versione.
Ma perde di efficienza perche' si ripete il ciclo senza tenere conto che il primo elemento, dopo ogni ripetizione, e' sempre il valore minore e si potrebbe fare a meno di controllare.
Ma chi se importa, parlare di efficienza con una routine che deve fare cosi' poche cose e' un po' esagerato
L'importante e' che sia ridotto.

[iAN CooG]

 Ed ecco i RISULTATI di questa competition non dichiarata

Alla fine le versioni piu' ottimizzate sono bene o male uguali.
Il risultato piu' appagante e comico e' stato che Wildstar, non sapendo che pesci pigliare, ha postato sul canale #c64friends (floodando) il sorgente che si trova QUA , sgamato dal sottoscritto 2 minuti dopo che l'aveva postato.
Grazie a questa ennesima e plateale bravata ora e' ufficialmente bollato a vita come Gran Cazzaro della comunita' C64 :D
I log della serata sono a disposizione per i curiosi e per chi si vuole fare un po' di risate (non si nota che ci sto godendo come un riccio, vero?)  

[The Overkiller]

 Dhe hi ho  :D . Ho visto che hanno partecipato anche Fungus e TMR ....

[iAN CooG]

 

Dhe hi ho  :D . Ho visto che hanno partecipato anche Fungus e TMR ....

Sia le entries di TMR che di Fungus non funzionavano. TMR l'ho gia' avvertito perche' aveva fatto una mini-cappella sul loop (loppava all'infinito), Fungus si arrangia, la sua routine manco va. Altre 2 entries sono errate, ChristianLott e MarkSeelye, perche' shiftano a dx di un byte l'array.
Anche i grandi sbagliano
Comunque, oggi mi sono dato da fare e ho finalmente ottenuto delle versioni iper ridotte.

Codice: [Seleziona]

; sort a 256 byte array at $c100
; V1.6 less efficient but 37 bytes, used illegal opcode LAX(zp),y
; 1st comparison always on the same element
; iAN CooG/HokutoForce
        org $c000
array   = $c100
FIRST   = $fb
SECOND  = $fd

        lda #>array
        sta FIRST+1
        sta SECOND+1
        lda #0
        tay
        sta FIRST      ; $C100
loop1  
        sta SECOND     ; $C100
loop2  
        lax (SECOND),y
        cmp (FIRST),y
        bcs noswap     ; 2nd less than 1st , swap them
        lda (FIRST),y
        sta (SECOND),y
        txa
        sta (FIRST),y
noswap  
        inc SECOND
        bne loop2      ; checked all 2nd elements? 1st is the lower now
        inc FIRST      ; now set next ptrs: $C101 and $C102
        lda FIRST
        bne loop1
exit    
        rts

Notare l'uso dell'opcde LAX che carica il valore contemporaneamente in A e X.

E per finire, la versione piu' piccola che sono riuscito ad ottenere: 30 bytes

Codice: [Seleziona]

; sort a 256 byte array at $c100
; v2.0  less efficient but very small, 30 bytes
; used both X & Y as indexes
; 1st comparison on same element at every loop start
; iAN CooG/HokutoForce

        org $c000

array   = $c100

        ldx #0
loop1  
        txa
        tay
loop2  
        lda array,y
        cmp array,x
        bcs noswap
        pha
        lda array,x
        sta array,y
        pla
        sta array,x
noswap  
        iny
        bne loop2
        inx
        bne loop1
        rts


in pratica il tutto funziona grazie a questo pseudocodice

Codice: [Seleziona]

N=0;
while(N<256)
{
   M=N;
   while(M<256)
   {
     if(ARR[M]<ARR[N])
       swap(ARR[M],ARR[N]);
     M++;
   }
   N++;
}


[MarC=ello]

 Io ero riuscito a ridurre di un byte la tua versione precedente:

Codice: [Seleziona]

org $c000

array   = $c100

loop    
       ldy #$01
       ldx #$01
next    
       lda array,x ; C100+x = $c101
       cmp array-1,x; C0ff+x = $c100
       bcs cont
swap    
       pha
       lda array-1,x
       sta array,x
       pla
       sta array-1,x
       iny           ; Y>0 = flag to repeat all
cont    
       inx
       bne next
       dey      ; a swap was done?
       bne loop      ; then repeat
       rts           ; else we're done

Spero di non aver fatto una cappella come gli altri! Ciao!

[iAN CooG]

Spero di non aver fatto una cappella come gli altri! Ciao!

Anzi, funziona perfettamente.

[MarC=ello]

 Dimenticavo: Wildstar roolez!  :D

E per finire, la versione piu' piccola che sono riuscito ad ottenere: 30 bytes

   

[fab]

Grazie a questa ennesima e plateale bravata ora e' ufficialmente bollato a vita come Gran Cazzaro della comunita' C64 :D
 

Non ce n'era bisogno: i suoi post su comp.sys.cbm e sulla mailing list del C-One (ogni tanto Jens Schoenfeld della Individual Computers si in***za con lui. Allora lui usa degli eteronimi, come Zenomega2x, ma viene scoperto subito, mettendosi ancora più in ridicolo) erano già abbastanza. Ma questa è un'ulteriore conferma.

A volte mi chiedo: ma chi glielo fa fare a Wildstar di mettersi in ridicolo di fronte a tutta la comunità? Pensare che basterebbe che stesse zitto, e nessuno lo prenderebbe in giro!

[The Overkiller]

Grazie a questa ennesima e plateale bravata ora e' ufficialmente bollato a vita come Gran Cazzaro della comunita' C64 :D
 

Non ce n'era bisogno: i suoi post su comp.sys.cbm e sulla mailing list del C-One (ogni tanto Jens Schoenfeld della Individual Computers si in***za con lui. Allora lui usa degli eteronimi, come Zenomega2x, ma viene scoperto subito, mettendosi ancora più in ridicolo) erano già abbastanza. Ma questa è un'ulteriore conferma.

A volte mi chiedo: ma chi glielo fa fare a Wildstar di mettersi in ridicolo di fronte a tutta la comunità? Pensare che basterebbe che stesse zitto, e nessuno lo prenderebbe in giro!

Perchè è un represso.... Io non so una cippa di assembly e do il mio contributo alla comunità con quello che so fare, si vede che lui invece vuole passare per il megacool coder.  Vabbè !!!!!    

[djwiper]

 Mi impegnerò... studierò per partecipare prima o poi anche io a queste 'sfide'  

Eppure sapete una cosa? Guardando lo pseudo-codice di IAN, che dovrebbe essere in C, riesco a grandi linee a capire come tradurlo in ASM. Mi sorge una domanda: non è che è meglio, per me, imparare un pò meglio il C per poi passare all'ASM? Ovviamente il C semplice, senza implementazioni di oggetti che difficilmente vedrei nell'amato commodore.

[fab]

riesco a grandi linee a capire come tradurlo in ASM. Mi sorge una domanda: non è che è meglio, per me, imparare un pò meglio il C per poi passare all'ASM?

Io ho imparato l'Assembler del C64 prima di sapere che il C esistesse. Però conoscere meglio i linguaggi di programmazione aiuta.

Tieni presente che l'Assembler è privo di qualsiasi strutturazione (cicli ecc.) e ti devi implementare praticamente tutto da zero. In questo senso è simile al BASIC del C64