Powerpc Assembly - part 2 (Bubble Sort)

Continuando a parlare di Assembly, stavolta voglio mostrare come è possibile implementare un bubble sort con poche istruzioni assembly.
Per chi dispone di un’architettura x86 o non PPC,ricordo che sono diffusi diversi emulatori powerpc open,tra cui PearPc.

Dedico questo codice ad una “certa” categoria di professori…
(Chi vuol capir capisca)

.data
vec:	.long 9          #il nostro vettore di interi disordinati
 .long 2          #ogni intero è 4 byte,cioè una word in un'architettura ppc 32bit
 .long 122
 .long 12
 .long 23
 .long 213
 .long 14539
 .long 121
 .long 42
 .long 12314
end_vec:                        #inserisco un'etichetta qui per calcolare la dimensione del vettore
 .align 2              #allineo il campo dati con la word (anche se non ce n'è bisogno,avendo a che fare solo con una word per ogni intero)

.text                             #segmento codice
 .globl main

main:
 stwu 1,-32(1)          #allocazione dello stackpointer e del LR nello stack
 mflr 0
 stw  0,28(1)
 #siamo ancora nel main #(bubble non ha un suo stackframe)

bubble:
 li 3,4         #  sizeof(long)->r3

	lis  6,vec@ha        #vec -> r6
     addi 6,6,vec@l

	lis 7,end_vec@ha       #end_vec ->r7
     addi 7,7,end_vec@l

	sub 7,7,6          # vec - end_vec ->r7
        divwu 7,7,3       #r7= r7 / sizeof long
                         #cioè la dim. del vettore
       mr 31,7          #dim(vec) -> r31
       mr 7,6            #copia di r6 in r7,utilizzo tale vettore per ripristinare r6 ad ogni ciclo

	subi 31,31,1     #dim(vec)-1 -> r31
                          #nel primo ciclo effettueremo dim-1 confronti
                          #r31 è il counter esterno 'i'

             li 30,0            #0  ->r30
                                 # r30 è il counter interno 'j'

bubble_inner_loop:
 	   addi  30,30,1   #j++
 	   lwz 4,0(6)      # vec[0]->r4
 	   lwz 5,4(6)      # vec[1]->r5

           cmpw 7,4,5        #if(vec[0] < vec[1])
 	   blt 7,next      #salta a next (non effettua lo swap)

swap:			       #altrimenti effettua lo swap
            stw 5,0(6)        #riposiziono in memoria i due interi
            stw 4,4(6)        #invertendo la posizione

next:                 #preparo i registri per il prossimo confronto

	   addi  6,6,4   #vec++ incremento il puntatore
 	   cmpw  6,30,31            #if(j != i)
 	   bne 6,bubble_inner_loop    #continuo col ciclo interno

bubble_extern_loop:       #else…

	   li   30,0                  #j=0
 	   subi 31,31,1            #i–
 	   mr 6,7                    #ripristino vec
           cmpwi  5,31,0          #if (i !=0)
 	   bne 5,bubble_inner_loop #rieffettuo il ciclo interno

end:
 	 lwz 0,28(1)              #riprendo il contenuto di LR dallo stack
 	 stw 1,32(1)              #cancello lo stackframe del main
         mtlr 0                           #riposiziono LR col suo valore originale
 	 blr                           #salto all'indirizzo di ritorno del main

PowerPC assembly

Essendo uno degli ultimi possessori di un processore della famiglia PowerPC non potevo resistere alla tentazione di scoprire le caratteristiche interne di questa meravigliosa macchina.
Il processore appartiene alla famiglia RISC,cioè ha un set di istruzioni limitato nelle funzionalità,(load and store), presenta un banco di 31 registri in virgola fissa a 32 bit e un banco di 32 registri in virgola mobile a 64 bit e alcuni registri di uso speciale.

In giro si trova parecchio materiale a riguardo,ho trovato un paio di references : semplificata
ed estesa
ma scarseggiavano un pò gli esempi e il codice.
Con il compilatore gcc però si può effettuare la compilazione senza assemblare il programma in codice eseguibile, adoperando

 gcc -S -o programma nomesorgente.c

e grazie a questo, è possibile studiare semplici programmi scritti ad alto livello e tradotti in assembly.

Unzip Ricorsivo

Ho scritto uno scriptino per bash per effettuare la decompressione di files Zip ricorsivamente.
A partire dalla directory corrente viene effettuata la ricerca di files zippati da decomprimere nelle sottodirectories,viene gestita anche la possibilità di spazi nel nome dei files.
Spero possa esservi utile.

#!/bin/sh

work(){
        for i  in `ls | sed -e s/' '/"__spazio__"/g`
                do
                        a=`echo $i | sed -e s/"__spazio__"/' '/g`
                        zip=$(file -b "$a" | awk '$1 ~ /^Zip/ { print $1 }' 
                        directory=$(ls -ld "$a" | awk '$1 ~ /^d/ {print "directory"}' 
                        if [ ! -z $zip ]
                                then
                                        unzip "$a"
                                elif [ ! -z $directory ]
                                then
                                        cd "$a"
                                work
                        fi
                done

                cd ..
}

work

Ahi serva Italia, di dolore ostello… Non donna di province, ma bordello

Alberi Avl

Visto che si avvicina il natale è una buona idea iniziare a preparare gli alberelli.
L’albero che ho addobbato è un albero Avl cioè una particolare struttura dati basata su un albero binario semplice ma con una caratteristica in più: la possibilità di ribilanciarsi dopo l’inserimento e la cancellazione di nodi.
Un albero bilanciato è un albero che ha un fattore di bilanciamento in valore assoluto minore o uguale a 1 per ogni nodo,vale a dire che la differenza tra l’altezza del sottoalbero sinistro e quella del sottoalbero destro rispetto al nodo si differenziano di al più una unità.

Questa caratteristica è utilissima perchè un tale albero presenta un’altezza al più logaritmica rispetto al numero dei nodi.
Con una tale struttura le operazioni di ricerca e quindi di inserimento e cancellazione presentano un costo

O(log(n))

rispetto al numero dei nodi.
L’albero Avl non è l’unico ad avere questa proprietà, vi sono anche gli alberi 2-3,i Btrees,i Red Black e tanti altri.

L’albero Avl si serve di rotazioni per ribilanciarsi.
Sostanzialmente viene effettuata una ricerca

I.Q. a Roma il 23/11/07

Gli I.Q. sono una rock band Inglese,il loro genere è il neo progressive, e nascono negli anni ‘80 dalle ceneri di quello che è stato il prog rock di gruppi come Genesis e Yes.
E’ da ritenersi un gruppo fondamentale nella scena prog ‘80 assieme a band del calibro di Marillion e Porcupine Tree.

Numeroni e programmazione : la libgmp

Spesso nasce la necessità di effettuare tramite l’elaboratore, calcoli che producono risultati non gestibili dai registri del nostro processore.Un registro di 32 bit ad esempio,non può rappresentare interi con segno che si estendano oltre 2 ³¹ -1 in quanto ci si imbatterebbe in un overflow.
Similmente,anche avendo a disposizione registri a virgola mobile,notiamo che in un moderno calcolatore non possiamo visualizzare in output un numero maggiore di 6 cifre dopo la virgola.Per questo è necessario sfruttare librerie dedicate alla gestione
dei “grandi numeri” e tra queste ho pensato di presentarvi la libgmp,