NS Diagrams to ARM

La traduzione di un diagramma in un linguaggio di programmazione dipende dal linguaggio di arrivo. Infatti tradurre in linguaggio ad alto livello è molto semplice che tradurlo in un linguaggio a basso livello (assembly ARM).

Utilizzeremo quindi delle semplificazioni come la direttiva DCD (Define Constant Double-words) che alloca word da 32-bit per ogni valore nell’elenco, associando l’elenco (array) ad un label:

v DCD 3,2,5,6   -- v = [3,2,5,6] 

Per la gestione degli indici viene utilizzato un registro che contiene l’indirizzo di memoria reale dell’elemento dell’array. Per esempio se vogliamo accedere a 3 , R1 (registro base) conterrà l’indirizzo di v , mentre per accedere a 2 , R1 = indirizzo_di_v + 4.

Traduzione blocchi di sequenze

La traduzioni dei blocchi posti in sequenza avviene rispettando il loro ordine ed ogni operazione astratta verrà tradotta in termini di istruzioni elementari ARM.

Vediamo un esempio , dove vogliamo calcolare il quinto termine della successione di Fibonacci definendo i primi valori della successione con X=1 e Y=1 :

ora traduciamo in ARM :

MOV R0, #0x1  -- R0=X=1
MOV R1, #0x1  -- R1=Y=1
ADD R0, R0, R1 -- R0=R0+R1
ADD R1, R0, R1 -- R1=R0+R1
ADD R0, R0 ,R1 -- R0=R0+R1

Traduzione blocchi di selezione

Selezione singola

Possiamo rappresentare direttamente con :

La difficoltà comune è quando abbiamo delle condizioni complesse da tradurre e quindi si scompongono le condizioni in modo da essere più semplici e facilmente traducibili. In questo caso il blocco di selezione verrà suddiviso in tanti blocchi innestati.

Per esempio :

ora traduciamolo in istruzioni ARM :

Selezione binaria

La traduzione della selezione binaria è analoga a quella della selezione singola , con l’unica eccezione che entrambi i blocchi non sono vuoti.

Vediamo un esempio :

Selezione multipla

La traduzione del costrutto switch segue uno schema lineare e modulare

Ricordiamo che le istruzioni cosi scritte , verranno così eseguite , quindi per esempio nell'ultimo pezzo codice , se BEQ blocco2 non è soddisfatta passa ad eseguire direttamente default perché effettivamente sta dopo.

Traduzione dei blocchi di iterazione

For

While

Do While

Ovviamente c’è anche un altro modo di strutturarlo (più sporco) :

do:
	...
	-- blocco del ciclo 
	...
 
while:
	CMP R0, R1
	BGE end  -- R0 >= R1 
	B do
	
end: 
	NOP  

ESEMPI

1. Vogliamo scrivere un programma che dati due numeri $\text{X}$ e $\text{Y}$ calcoli la divisione (assoluta) $\left|\frac{\text{X}}{\text{Y}}\right|$

Definiamo :

• contratto : word divisione(word X,word Y)
• pre-condizione : $\text{X}\ge 0$ e $\text{Y}>0$
• post-condizione : $\left|\frac{\text{X}}{\text{Y}}\right|$

Il diagramma NS sarà il seguente :

quindi ora traduciamo in ARM :

MOV R0, X
MOV R1, Y
MOV R2, #0
 
while: 
	CMP R0, R1
	BLT end 
	SUB R0, R0, R1
	ADD R2, R2, #1
	B while 
 
end: 
	NOP
 

possiamo usare anche con le precondizioni (<PreCond>)

MOV R0, X
MOV R1, Y
MOV R2, #0
 
while: 
	CMP R0, R1
	SUBGE R0, R0, R1
	ADDGE R2, R2, #1
	BGE while 
 
end: 
	NOP
 

---

2. Vogliamo ora implementare la moltiplicazione tra due numeri $\text{X}$ e $\text{Y}$. Beh siccome :

$$\text{X}\times \text{Y}=\sum _{n=1}^{\text{Y}}\text{X}$$

ma allora diventa semplice fare il diagramma NS :

ora traduciamo in ARM :

MOV R0, X
MOV R1, Y
MOV R2, 0
MOV R3, #1 
for: 
	CMP R3,R1
	ADDLE R3, R3, #1 
	ADDLE R2, R2, R0
	BLE for 
	
end: 
	NOP 
 

---

3. Vogliamo ora implementare la potenza di due numeri $\text{X}$ e $\text{Y}$ quindi vogliamo fare ${\text{X}}^{\text{Y}}$. Definiamo :

• contratto : word pow(word X, word Y)
• pre-condizione : $\text{X},\text{Y}\ge 0$
• post-condizione : restituire $-1$ se $\text{X}=\text{Y}=0$ , altrimenti ${\text{X}}^{\text{Y}}$

ora tocca tradurre in ARM :

MOV R0, X
MOV R1, Y
MOV R2, #1 
CMP R0, #0 
BEQ and 
MOV R3, #1
for: 
	 CMP R3, R1 
	 MULLE R2, R2, R0 
	 ADDLE R3, #1
	 BLE for
	 B end 
 
and: 
	CMP R1, #0 
	MOVEQ R2, #-1
	BEQ end 
	MOV R3, #1 
	B for  
 
end: 
	NOP 

---

4. Supponiamo di disporre di due array V1 e V2 della stessa dimensione (n=V1[0]=V2[0]) e vogliamo calcolare la seguente espressione logica (AND e OR) :

$$\text{V1[1]V2[1]}+\text{V1[2]V2[2]}+\cdots +\text{V1[n]V2[n]}$$

Definiamo :

• contratto : boolean AND_OR(word[] V1, word[] V2)
• pre-condizione : nessuna
• post-condizione :
  • restituisce 0 se :
    • $\text{V1[0]}\le 0$
    • $\text{V2[0]}\le 0$
    • $\text{V1[0]}\ne \text{V2[0]}$
  • altrimenti l’espressione logica indicata sopra

il diagramma NS sarà :

ora traduciamo in ARM :

V1 DCD 2,0xFFFF, 0x00FF
V2 DCD 2,0xF12F, 0xFF00
 
MOV R0, #0 
MOV R5, #4  -- questo può andare anche dopo il controllo R3 > 0 (+) 
LDR R1, =V1  -- R1 = indirizzo(V1)
LDR R2, =V2  -- R2 = indirizzo(V2)
LDR R3, [R1] -- R3 = mem[R1]
LDR R4, [R2] -- R4 = mem[R2]
CMP R3, R4
BNE end 
CMP R3, #0 
BLE end 
MOV R6, R3, LSL #2  -- OPPURE con pseudo-istruzione LSL R6, R3, #2 
 
do: 
	LDR R3, [R1, R5]
	LDR R4, [R2, R5]
	AND R7, R3, R4
	ORR R0, R0, R7
	ADD R5, R5, #4 
	CMP R5, R6
	BLE do 
 
end: 
	NOP -- in R0 ci aspettiamo = 0xF12F

---

4. Vogliamo ora implementare la funzione merge dato due array v e w , ordinati in ordine crescente.

.global _start
_start:
	
	V: .word 3, -1, 4, 5  
	W: .word 2, 3, 4 
	Z: .word 0
 
	MOV R0, #4  
	MOV R1, #4 
	LDR R4, =V       -- R4 = indirizzo(V)
	LDR R5, =W       -- R5 = indirizzo(W)
	LDR R2, [R4]     -- R2 = mem[R4]
	LSL R2, R2, #2   
	LDR R3, [R5]     -- R3 = mem[R5]
	LSL R3, R3, #2 
 
	LDR R8, =Z       -- R8 = indirizzo(Z)
	ADD R6, R2, R3
	
	
	MOV R7, #4
for: 
    CMP R7, R6
    BGT end 
    LDR R9, [R4,R0]
    LDR R10, [R5, R1]
    CMP R1, R3
    BGT copia_v_z
    CMP R0, R2
    BGT copia_w_z
    CMP R9, R10
    BGE copia_w_z
    B copia_v_z
 
copia_v_z: 
    STR R9, [R8, R7]
    ADD R0, R0, #4
    ADD R7, R7, #4
    B for 
 
copia_w_z:
    STR R10, [R8, R7]
    ADD R1, R1, #4
    ADD R7, R7, #4
    B for
 
end: 
 

PS : ho scritto direttamente il codice in ARM compatibile con CPULator per testarlo.

---

ESERCIZI

9. Realizzare una funzione reverse che riceve in ingresso un array e restituisce in uscita un array di medesima dimensione e contenuto, ma con gli elementi in ordine inverso.

Soluzione in loco :

.global _start
_start:
	
	v: .word 9, 1, 2, 3, 4, 5, 6,7, 8,9
 
	LDR R0, =v
	LDR R1, [R0]
	MOV R2, #4
	LSL R3, R1, #2  
	LSR R4, R1, #1
	LSL R4, R4, #2
 
while: 
      CMP R2, R4
      BGT end 
      LDR R5, [R0, R2]
      LDR R6, [R0, R3]
      STR R6, [R0, R2]
      STR R5, [R0, R3]
      ADD R2, R2, #4
      SUB R3, R3, #4
	  B while
 
end: 

---

8. Realizzare un metodo che riceve in ingresso un valore intero X e un array , e restituisce in uscita il numero di volte in cui X è contenuto nel array.

Il diagramma NS risulta :

ora ci tocca tradurre in ARM:

array: .word 6, 1, 2, 1, 3, 1, 1
 
MOV R0, #1 
LDR R1, =array 
LDR R3, [R1]
LSL R3, R3, #2 
MOV R2, #0 
 
MOV R4, #4
for: 
	CMP R4, R3
	BGT end 
	LDR R5, [R1, R4]
	CMP R0, R5
	ADDEQ R2, R2, #1
	ADD R4, R4, #4
	B for 
 
end: 

---

7. Realizzare una funzione che permetta di unire sequenzialmente gli elementi di due array forniti in ingresso.

.global _start
_start:
	
	V: .word 4,1, 2, 3, 4
	W: .word 3,5, 6, 7
	Z: .word 0
	
	LDR R0, =V
	LDR R1, =W
	LDR R4, =Z
	LDR R2, [R0]
	LSL R2, R2, #2
	LDR R3, [R1]
	LSL R3, R3, #2
	MOV R5, #4
	MOV R6, #4
	ADD R7, R2, R3
	-- ora memorizzo nella prima posizone dell'array finale la sua dimensione finale (n+m) (in questo caso 7)
	LSR R7, R7, #2
	STR R7, [R4]
	
	MOV R8, #4
for: 
	CMP R8, R7
	BGT end
	CMP R8, R2
	BLE copy_v
	B copy_w 
	
copy_v: 
	LDR R9, [R0, R5]
	STR R9, [R4, R8]
	ADD R5, R5, #4
	ADD R8, R8, #4
	B for 
	
copy_w: 
	LDR R9, [R1, R6]
	STR R9, [R4, R8]
	ADD R6, R6, #4
	ADD R8, R8, #4
	B for
	
	
end: