Soluzione esercitazione 3
Nota bene: le soluzioni proposte sono ottimizzate per le prestazioni. Vi sono molte altre soluzioni ammissibili ugualmente valide: postatele sul
forum e le discutiamo. Altre soluzioni sono disponibili sui diari delle lezioni dei due canali.
Esercizio 1
# 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;
# }
.globl binsearch
binsearch: # v <-> ecx, n <-> edi, x <-> eax, m <-> esi, k <-> edx
pushl %esi
pushl %edi
movl 12(%esp), %ecx # ecx = v
movl 16(%esp), %edi # edi = n
movl 20(%esp), %eax # eax = x
xorl %esi, %esi # m = 0
cmpl %edi, %esi # res = m-n
jge E0 # if (res >= 0) goto E0
L: leal (%esi,%edi), %edx # k = n+m
shrl $1, %edx # k = k/2
cmpl %eax, (%ecx,%edx,4) # res = v[k] - x
je E1 # if (res == 0) goto E1
cmovgl %edx, %edi # if (res > 0) n = k
leal 1(%edx), %edx # edx++ (no side-effect su EFLAGS)
cmovll %edx, %esi # if (res < 0) m = k+1
cmpl %esi, %edi # res = n-m
jg L # if (res > 0) goto L
E0: xorl %eax, %eax # eax = 0
jmp C # goto C
E1: movl $1, %eax # eax = 1
C: popl %edi
popl %esi
ret # return eax
Esercizio 2
void cancspazi(char* s) {
char* p = s;
do if (*s!=' ') *p++ = *s;
while (*s++!=0);
}
# void cancspazi(char* s) {
# char* p = s;
# do if (*s!=' ') *p++ = *s;
# while (*s++!=0);
# }
.globl cancspazi
cancspazi: # s <-> eax, p <-> ecx
movl 4(%esp), %eax # eax = s
movl %eax, %ecx # ecx = p = s
jmp S # goto S
L: incl %eax # s++
S: movb (%eax), %dl # dl = *s
cmpb $32, %dl # if (dl == ' ')
je L # goto L
movb %dl, (%ecx) # *p = dl
incl %ecx # p++
testb %dl, %dl # if (dl!=0)
jne L # goto L
ret
Esercizio 3
.globl swap
.globl makepass
.globl bubblesort
# void swap(int* a, int* b) {
# int temp = *a;
# *a = *b;
# *b = temp;
# }
swap:
pushl %ebx
movl 8(%esp), %eax # eax = a
movl 12(%esp), %ebx # ebx = b
movl (%eax), %ecx # ecx = *a
movl (%ebx), %edx # edx = *b
movl %ecx, (%ebx) # *b = ecx
movl %edx, (%eax) # *a = edx
popl %ebx
ret
# 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;
# }
makepass: # edi <-> v, esi <-> n, ebx <-> cont
pushl %esi
pushl %edi
pushl %ebx
subl $8, %esp
movl 24(%esp), %esi # esi = v
movl 28(%esp), %edi # edi = n
xorl %ebx, %ebx # cont = 0
decl %edi # --n
testl %edi, %edi # res = n
jle E # if (res <= 0) goto E
L: leal -4(%esi,%edi,4), %eax # eax = v+n-1
movl (%eax), %ecx # ecx = v[n-1]
cmpl (%esi,%edi,4), %ecx # res = v[n-1] - v[n]
jle C # if (res <= 0) goto C
movl %eax, (%esp) # 1st param = eax = v+n-1
addl $4, %eax # eax += 4
movl %eax, 4(%esp) # 2nd param = eax = v+n
call swap # swap()
movl $1,%ebx # cont = 1
C: decl %edi # --n
testl %edi, %edi # res = n
jg L # if (res > 0) goto L
E: movl %ebx, %eax
addl $8, %esp
popl %ebx
popl %edi
popl %esi
ret
# void bubblesort(int* v, int n) {
# while (makepass(v,n));
# }
bubblesort: # v <-> esi, n <-> edi
pushl %esi
pushl %edi
subl $8, %esp
movl 20(%esp), %esi # esi = v
movl 24(%esp), %edi # edi = n
R: movl %esi, (%esp) # 1st param = v
movl %edi, 4(%esp) # 2nd param = n
call makepass
testl %eax, %eax
jne R
addl $8, %esp
popl %edi
popl %esi
ret