Esercitazione 3 - 4 novembre 2016 (120 min)
Esercizio 1
Tradurre in IA32 la seguente funzione C che realizza l'algoritmo di
ricerca binaria su array ordinati. Scrivere la soluzione nel file
es1.s.
int binsearch(int* v, int n, int x) {
int m = 0; // restituisce 1 <=> x รจ nell'array ordinato v di dimensione n
while (m<n) {
int k = (m+n) >> 1; // indice dell'elemento a meta' fra m ed n
if (x == v[k]) return 1; // x e' in posizione k => trovato
if (x > v[k]) m = k+1; // x puo' essere a destra fra k+1 ed n
else n = k; // x puo' essere a sinistra fra m e k
}
return 0;
}
Usare il seguente programma di prova:
#include <stdio.h>
int binsearch
(int* v,
int n,
int x
);
int main
() {
int res, v
[] =
{ 1,
3,
4,
9,
12 }, n =
sizeof(v
)/
sizeof(int);
res = binsearch
(v, n,
0);
printf("%d (corretto: 0)\n", res
);
res = binsearch
(v, n,
3);
printf("%d (corretto: 1)\n", res
);
res = binsearch
(v, n,
5);
printf("%d (corretto: 0)\n", res
);
res = binsearch
(v, n,
12);
printf("%d (corretto: 1)\n", res
);
res = binsearch
(v, n,
13);
printf("%d (corretto: 0)\n", res
);
res = binsearch
(v,
1,
1);
printf("%d (corretto: 1)\n", res
);
res = binsearch
(v,
0,
1);
printf("%d (corretto: 0)\n", res
);
return 0;
}
Esercizio 2
Scrivere una funzione
void cancspazi(char* s) che elimina tutti gli spazi da una stringa
s e tradurla poi in IA32. Scrivere la soluzione nel file
es2.s.
Usare il seguente programma di prova:
#include <stdio.h>
void cancspazi
(char* s
);
int main
() {
char s1
[] =
"obi wan kenobi ";
char s2
[] =
"obiwankenobi";
char s3
[] =
" leila luke ";
char s4
[] =
"";
cancspazi
(s1
);
cancspazi
(s2
);
cancspazi
(s3
);
cancspazi
(s4
);
printf("\"%s\" (corretto: \"obiwankenobi\")\n", s1
);
printf("\"%s\" (corretto: \"obiwankenobi\")\n", s2
);
printf("\"%s\" (corretto: \"leilaluke\")\n", s3
);
printf("\"%s\" (corretto: \"\")\n", s4
);
return 0;
}
Compilare come al solito con
gcc -m32 -g es2.s es2-main.c -o es2. In caso di problemi debuggare con gdb.
Esercizio 3
Tradurre in IA32 le seguenti tre funzioni C che, combinate, realizzano un semplice algoritmo di ordinamento (
bubblesort). Scrivere la soluzione nel file
es3.s.
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int makepass(int* v, int n) {
int cont = 0;
while (--n>0)
if (v[n-1]>v[n]) {
swap(v+n-1, v+n);
cont = 1;
}
return cont;
}
void bubblesort(int* v, int n) {
while (makepass(v,n));
}
Scrivere tutte le funzioni assembly nello stesso file
es3.s:
.globl swap
.globl makepass
.globl bubblesort
swap: ...
ret
makepass: ...
ret
bubblesort: ...
ret
Sviluppare il programma incrementalmente, testando le funzioni una alla volta con i seguenti tre main.
Main di prova per la funzione
swap:
#include <stdio.h>
void swap
(int* x,
int* y
);
int main
() {
int a =
10, b =
20;
swap
(&a, &b
);
printf("a=%d, b=%d\n", a, b
);
// deve stampare: a=20, b=10
return 0;
}
Main di prova per la funzione
makepass:
#include <stdio.h>
int makepass
(int* v,
int n
);
void print
(int* v,
int n
) {
int i;
for (i=
0; i<n; ++i
) printf("%d ", v
[i
]);
printf("\n");
}
int main
() {
int v
[] =
{ 2,
3,
4,
5,
1 };
int n =
sizeof(v
)/
sizeof(int);
print
(v, n
);
makepass
(v, n
);
print
(v, n
);
// deve stampare 1 2 3 4 5
return 0;
}
Main di prova per la funzione
bubblesort:
#include <stdio.h>
void bubblesort
(int* v,
int n
);
void print
(int* v,
int n
) {
int i;
for (i=
0; i<n; ++i
) printf("%d ", v
[i
]);
printf("\n");
}
int main
() {
int v
[] =
{ 9,
1,
3,
2,
5 };
int n =
sizeof(v
)/
sizeof(int);
print
(v, n
);
bubblesort
(v, n
);
print
(v, n
);
// deve stampare 1 2 3 5 9
return 0;
}