Esercizi Assembly

Un programma per calcolare la media

Dato un vettore di 32 bytes unsigned memorizzato apartire dalla locazione 0x20a0, calcolarne la media ememorizzarne il valore sovrascrivendo l’ultimaposizione del vettore. Se viene rilevato un overflowin V[31] e’ posizionato il valore ff ff ff ff

0x20a0 V[0]V[1]V[2]

…

V[31]

V[31]=_i=031V[i]/32

Come gestire l’overflow?L’istruzione da controllare e’:

addb (R1)+, R2

Microcodice :

1. MAR<-R1

2. R1<-R1+1

3. Temp1<-[MDR] 8 //gli 8 lsbs di MDR estesi in segno vanno in T1

4. Temp2<-[R2] 8 //gli 8 lsbs di R2 estesi in segno vanno in T2

5. ALU_OUT=Temp1+Temp2

Se (Temp1 + Temp2) >232-1 il CARRY bit viene settato persegnalare l’overflow. Quindi , e’ sufficiente far seguireall’operazione di somma un salto condizionato del tipo:

jc error

Il codiceorg 400hARRAY EQU 20a0h ; indirizzo base arrayDIM EQU 32 ; num.elementi arrayLOG2DIM EQU 5 ; log. base 2 di DIM

codemovl #DIM,R0movl #ARRAY,R1xorl R2,R2 ;resetta R2, risultato parziale

loop: addb (R1)+,R2 ;somma i-esimo elem. i=0..DIM-1jc error ;bit c settato =>Overflowsubl #1,R0 ;decrementa contatorejnz loop ;se contatore!=0 continua il ciclalsrb #LOG2DIM, R2;dividi per il numero di elementi,

;usiamo LSRB poichè lavoriamo con unsignedmovb R2, -(R1) ;memorizza la media in ARRAY[DIM-1]jmp fine

error: movl #DIM, R1 ;gestione overflow, calcola in R1addl #ARRAY, R1 ; R1=ARRAY+DIMsubl #1,r1xorl R3,R3notl R3,R3 ; R3=111....111movb R3,(R1) ; ARRAY[DIM]=11111111

fine: haltend

Una variazione sul tema…ora, senza contatore!

Calcolare la media di 128 words memorizzate apartire dall’indirizzo 0x20ab, ma senza impiegareun registro appositamente come contatore (R0 delprogramma precedente) .

0x20 ab V[0]V[1]V[2]

…

V[127]

V[127]=_i=0127V[i]/127

0x21a9

0x20ad

0x21 ab

NOTA: non si consideral’overflow.

Il codice(funziona solo se il numero di elementi è pari a 128 words)

org 400h ; programma allocato a partire da 400hDATI EQU 20abh ;indirizzo inizio

code ;inizio istruzionimain:

xorl R2,R2 ; R2=risult.parzialemovl #DATI,R1 ; puntatore elementomovb R1,R0 ; copio lsB addr. inizio

; in R0loop: addw (R1)+, R2

cmpb R1,R0 ; lsB addr. elemento; e' = lsB addr. inizio ?

jnz looplsrw #7,R2 ; divido per 128movw R2,-(R1)halt ;serve solo per bloccare il simulatore

end ;fine della compilazione

Un altro esempio: la moda

Assumiamo di avere un vettore,V, di N bytes chememorizza nella posizione i-esima l’altezza incentimetri dell’i-esimo studente.

PROBLEMA:

Trovare l’altezza piu’ frequentetra gli studenti (moda).

altezza

id-studente

Prima soluzione:vettore di frequenze

Vogliamo calcolare la moda, costruendo innanzituttoun vettore di frequenze, F, di 255 longwords, cheassoci in posizione j, il numero di ricorrenzedell’altezza j nel vettore di partenza V.

Probabilmente: F[j]=0 se i<50 o i>220

Osservazione:

Noto il vettore delle frequenze F, ilcalcolo della moda si riconduce adeterminare per quale i, F[i]=max{F}

num.studenti

cm.

L’algoritmo per il calcolo delle frequenze

Possiamo costruire F in 2 passi.

1) Inizializziamo l’array F, di 255 longwords, con tutti 0.

for (i=0;i<256;i++) { array2[i]=0;}

2) Memorizziamo le frequenze in F scandendo una sola volta V eincrementando di volta in volta l’elemento di F in posizione V(i) di 1.

for (i=0;i<N;i++) { index=array1[i];

array2[index]++; }

Codiceorg 1400harray1 equ 800h ; V, vettore originalearray2 equ 1500h ; F, vettore frequenzedim equ 30code

;inizializzo array2 con tutti 0; for (i=0;i<256;i++) {; array2[i]=0;; };

MOVL #array2,R5 ;R2 base dell'arraymovl #0,r4

clean: movl #0, (R5)+addl #1,r4cmpl #0ffh,r4jc clean

; memorizzo frequenze in array2; for (i=0;i<N;i++) {; index=array1[i];; array2[index]++;; }

MOVL #dim,R2 ;R2 dimensione di array1XORL R3,R3 ;R3=0, contatore e offset perarray1;

count: xorl r4,r4 ; r4 è inizializzato a zero perchè la successiva mvlb ; si aspetta i 3 bytes + significativi di R4 uguali a 0

mvlb array1(R3),R4 ;R4=V[i]=array1[R3];NOTA: MVLB non estende il segno

aslw #2,R4 ;offset_array2=R4*4;Moltiplicando per 4 il contenuto;del lsb di R4 possiamo avere trabocchi,;quindi usiamo aslw per operare con 2 byte

movl array2(R4),r5 ;r5=array2[offset_array2] addl #1,r5 ; r5=array2[offset_array2]+1

addl #array2,r4 ; prima r4 era = offset_array2, ora;r4=offset_array2+base_add_array2

movl r5,(r4) ;array2[offset_array2]=array2[offset_array2]+1addl #1,R3 ; i=i+1

cmpl #R2,R3jnz count

haltend

Prima soluzione:determiniamo il max su F

Ora che abbiamo il vettore delle frequenze, ilcalcolo della moda si riconduce a determinare perquale i, F[i]=max{F}

num.studenti

cm.170=moda

Codiceorg 1400harray2 equ 1500h

codeMOVL #255,R1 ;copia il lsb byte in R1ASLL #2,R1ADDL #array2,R1 ; in R1 c’è l’indirizzo dell 256° elemento di Array2MOVL #array2,R2 ;R2 puntatore all'arrayXORL R3,R3 ;R3=0;MOVL #1,R4 ;R4=1

loop:MOVL (R2)+,R5CMPB R5,R3JNC skip ; se R3>=R5 salta a skipMOVL -(R2),R3 ; in R3 c'è il massimo temp.MOVL R2,R4 ; in R4 c'è l'indice corrisp.all'elemento massimoADDL #4,R2

skip: CMPB R2,R1

jnz loop ; condizione di uscita dal cicloSUBL #ARRAY2,R4 ; R4=[OFFSET_MAX_FREQUENZA*4]ASRL #2,R4 ; R4 / 4=OFFSET_MAX_FREQUENZAhalt

end

Ancora Moda… evitiamo il calcolo delvettore delle frequenze

Dato un vettore di DIM dati da un byte, rappresentati come unsigned trovare:

1) l’elemento con il massimo numero di ricorrenze (moda)

2) il corrispondente numero di ricorrenze

L’ALGORITMO

MAX_NUM=0; //memorizza la modaMAX_RIC=0; //memorizza il numero di ricorrenze della modaFOR INT I=0 TO DIM-1 {

IF ((I==0) || ( (I!=0) && (A[I]!=MAX_NUM) ) ) {// Conta il numero di ricorrenze dell’elemento i-esimo se e solo se I=0, oppure// I!=0 e l’elemento A[I] non è già la moda

TEMP_RIC=0;FOR INT J=I TO DIM-1

{ IF A[J]=A[I] TEMP_RIC++; }IF (TEMP_RIC>MAX_RIC) {MAX_RIC=TEMP_RIC; MAX_NUM=A[I];}

}

CodiceORG 400H

ARRAY EQU 1000HDIMEQU 10MAXNUM EQU 950HMAXRIC EQU 951H

CODE

XORL R0,R0 ; MAXNUM=0XORL R1,R1 ; MAXRIC=0XORL R2,R2 ; I=0

FOR1: MOVB ARRAY(R2),R5; R5=A[I]=ARRAY(R2)

CMPL #0,R2JZ DOIT ; IF (I==0) JMP DOITCMPB R5,R0 ; ELSE IF A[I]== MAXNUMJZ NOMAX ; JMP NOMAX (SKIP INNER CICLE)

DOIT:MOVL R2,R3 ;J=IXORL R4,R4 ;TEMPRIC=0

FOR2: CMPB ARRAY(R3), R5 ; IF A[I]!=A[J]

JNZ NOADD ; SKIP ADDADDL #1,R4 ; TEMPRIC++

NOADD:ADDL #1,R3 ; J++CMPL #DIM,R3 ; IF (J!=N) GOTO FOR2JNZ FOR2CMPL R4,R1 ; IF MAXRIC>TEMPRIC

JNC NOMAX ; SKIP UPDATING MAXMOVL R4,R1 ; MAXRIC=TEMPRICMOVB ARRAY(R2),R0; MAXNUM=A[I]

NOMAX: ADDL #1,R2 ; I++

CMPL #DIM,R2 ; IF (R2!=DIM)JNZ FOR1 ; GOTO FOR1

MOVB R0, MAXNUMMOVL R1, MAXRICHALT

END

Inversione di un array Dato un array di 10 elementi, memorizzato a partire

da 250h, rimpiazzarlo con l’array inverso (senzausare un altro vettore di appoggio).

12152

134893

11prima

984132521111

3dopo

250h254h258h25Ch260h264h268h26Ch270h274h

250h254h258h25Ch260h264h268h26Ch270h274h

Il primo passo di esecuzione

12152134893

11 R1

R2

12152134893

11121521348911

3R1

R2

R3=10/2=5 R3=R3-1=4scambia (R1) con (R2)

Rappresentazione dell’informazione

12152134893

11250h254h258h25Ch260h264h268h26Ch270h274h

336 (dec)340344348352356360364368372

00010101000000000000000000000000

258h259h25ah25bh

344345346347

Base_Addr(Array) +(DIM-1)*size_of(elem) =Addr(Array[DIM-1])

336 +9 * 4 =372

9*4=36 (OFFSET)

ORG 400HDIM EQU 10ARRAY EQU 250H

CODEMOVL #ARRAY,R2MOVL #DIM,R4SUBL #1,R4ASLL #2,R4 ; offset da sommare alla base dell'array per ottenere l'ultimo elementoADDL R4,R2 ; in R2 c'è l'indirizzo dell'ultimo elemento dell'arrayMOVL #ARRAY,R1 ; R1 <-indirizzo arrayMOVL #DIM,R3 ; R3<-10 (000... 00001010)ASRL #1,R3 ; R3=R3/2=5 (000... 000000101)

REPEAT:MOVL (R1),R0; R0 registro d'appoggio per lo scambioMOVL (R2),(R1); Copia memoria memoria dell'"ultimo" elemento sul "primo"MOVL R0,(R2); recupera il valore del primo elemento da R0 e copialo in codaADDL #4,R1; avanza di 4 byte il valore dell'offset sul vettore originaleSUBL #4,R2; decrementa di 4 byte il valore dell'offset sul vettore invertitoSUBL #1,R3; decrementa il contatoreJNZ REPEAT; fino a 0

HALTEND

Il codice

Un algoritmo per la moltiplicazione

Il set di istruzioni del PD32 non prevede istruzioni pereffettuare la moltiplicazione tra due operandi.

La moltiplicazione puo’ essere realizzata banalmentesommando al moltiplicando se stesso, un numero di voltepari al valore del moltiplicatore. 5*3=5+5+5=15.

Tale algoritmo ha complessità computazionale pari a O(N),dove N è il valore del moltiplicatore.

Vogliamo proporre un algoritmo per la moltiplicazione la cuicomplessità sia pari a O(log2N).

Moltiplicazione: primo approccio

00110 x

00101 = 00110 00000 00110 00000

00000000011110

sommeparziali

00000 + 00110 00110 + 00000 000110 + 00110 0011110 + 00000 00011110 +00000000011110

somma parziale

“prodotto parziale”

Risultatofinale

In altre parole...

Traslo a destra il moltiplicatore di una posizione perverificare se il suo lsb vale 1. Il suo lsb finisce in C.

Sommo il moltiplicandoalla somma parziale.

C=1C=0

Traslo a destra la somma parziale, copiando il bitfuoriuscito (lsb della somma parziale) nel msb delmoltiplicatore (che diventa passo dopo passo laparte meno significativa del risultato)

L’algoritmo (precondizioni)

0 00 1 1 0

0 0 0 0 0

A C

0 0 1 0 1 DB

moltiplicando, A=6 moltiplicatore,D=5

• Ripeti i seguenti passi tante volte quanti sono i bit di D.1. Azzero C2. Trasla a destra D3. Se C=1 somma A e B4. Trasla a destra B5. Se C=1 inverto il bit più significativo di D

L’algoritmo (postcondizione)

0 00 1 1 0

0 0 0 0 0

A C

1 1 1 1 0 DB

moltiplicando, A=6

Il risultato della moltiplicazione necessita di un numero dibits doppio per poter essere rappresentato. Per semplicitàmoltiplicando e moltiplicatore hanno 5 bits nel nostroesempio=> risultato scritto in 10 bits. I 5 MSB sono scritti inB, i 5 LSB sovrascrivono il moltiplicatore.

Risultato=30

Il codice

ORG 400Hrls EQU 2000h ;addr.parte meno sig.del risult.rms EQU 2004h ;addr.parte + sig.del risult.A DL 6 ; variabile contenente il moltiplicandoD DL 5 ; variabile contente il moltiplicatore

CODEMOVL A,R0 ; carico il moltiplicando in R0MOVL D,R3 ; carico il moltiplicatore in R3XORL R2,R2 ; azzero R2 (B)MOVL #32,R1; R1 è il contatore: inizializzo a

; 32, #bits moltiplicatoremult: CLRC

LSRL #1, R3JNC dopo

ADDL R0,R2dopo: LSRL #1,R2

JNC poiXORL #80000000h, R3 ;inverto il bit + significativodi R3 (d)

poi: SUBL #1, R1JNZ multMOVL R3, rls ; la parte meno significativa

; contenuta in R3 viene caricata; nella longword di memoria; di indirzzo rls

MOVL R2,rms ; la parte più significativa in rmsEND