Soluzioni esercitazione 3 presentate a lezione (Canale 2)
Esercizio 1
#int binsearch(int* v, int n, int x) {
# int m = 0;
# while (m<n) {
# int k = (m+n) >> 1;
# if (x == v[k]) return 1;
# if (x > v[k]) m = k+1;
# else n = k;
# }
# return 0;
#}
.globl binsearch
binsearch:
# v->eax, n->ecx, x->edx, m->ebx, k->edi
pushl %ebx
pushl %edi
movl 12(%esp), %eax # v
movl 16(%esp), %ecx # n
movl 20(%esp), %edx # x
xorl %ebx, %ebx # m = 0
L: cmpl %ecx, %ebx
jge R0
movl %ebx, %edi # k = m
addl %ecx, %edi # k = m+n
sarl $1, %edi # k = (m+n) >> 1
cmpl (%eax, %edi, 4), %edx # x vs v[k]
je R1
jl MI
movl %edi, %ebx
incl %ebx
jmp L
MI: movl %edi, %ecx # n = k
jmp L
R1: movl $1, %eax
jmp E
R0: xorl %eax, %eax
E: popl %edi
popl %ebx
ret
Variante ottimizzata che ricorre a
CMOV in luogo di
jl MI per gestire la
if ... else nel ciclo:
.globl binsearch
binsearch:
# v->eax, n->ecx, x->edx, m->ebx, k->edi
pushl %ebx
pushl %edi
movl 12(%esp), %eax # v
movl 16(%esp), %ecx # n
movl 20(%esp), %edx # x
xorl %ebx, %ebx # m = 0
L: cmpl %ecx, %ebx
jge R0
movl %ebx, %edi # k = m
addl %ecx, %edi # k = m+n
sarl $1, %edi # k = (m+n) >> 1
cmpl (%eax, %edi, 4), %edx # x vs v[k]
je R1
cmovll %edi, %ecx # n = k if (x < v[k])
leal 1(%edi), %edi
cmovgl %edi, %ebx # m = ++k if (x > v[k])
jmp L
R1: movl $1, %eax
jmp E
R0: xorl %eax, %eax
E: popl %edi
popl %ebx
ret
Esercizio 2
#void cancspazi(char* s) {
# char *p = s;
# while (*s != 0) {
# if (*s != 32) *p++ = *s; // ' ' = 32
# s++;
# }
# *p = 0;
#}
.globl cancspazi
cancspazi:
movl 4(%esp), %eax # s
movl %eax, %ecx # p
L: movb (%eax), %dl
cmpb $0, %dl
je E
cmpb $32, %dl
je I
movb %dl, (%ecx)
incl %ecx
I: incl %eax
jmp L
E: movb $0, (%ecx)
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
movl 12(%esp), %ecx
movl (%eax), %ebx
movl (%ecx), %edx
movl %ebx, (%ecx)
movl %edx, (%eax)
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:
pushl %ebx
pushl %edi
pushl %esi
movl 16(%esp), %ebx # v
movl 20(%esp), %edi # n
xorl %esi, %esi # cont = 0
W: decl %edi
testl %edi, %edi
jle E
leal (%ebx, %edi, 4), %eax # &v[n]
subl $4, %eax # &v[n-1]
movl (%eax), %ecx # v[n-1]
cmpl (%ebx, %edi, 4), %ecx
jle W
subl $8, %esp
movl %eax, (%esp) # &v[n-1]
addl $4, %eax # &v[n]
movl %eax, 4(%esp)
call swap
addl $8, %esp
movl $1, %esi
jmp W
E: movl %esi, %eax
popl %esi
popl %edi
popl %ebx
ret
# void bubblesort(int* v, int n) {
# while (makepass(v,n));
# }
bubblesort:
pushl %ebx
pushl %edi
movl 12(%esp), %ebx
movl 16(%esp), %edi
L: subl $8, %esp
movl %ebx, (%esp)
movl %edi, 4(%esp)
call makepass
addl $8, %esp
testl %eax, %eax
jne L
popl %edi
popl %ebx
ret
Variante di
bubblesort che utilizza i registri
caller-save per il passaggio dei parametri, preservandone il contenuto:
# void bubblesort(int* v, int n) {
# while (makepass(v,n));
# }
.globl bubblesort
bubblesort:
movl 4(%esp), %ecx
movl 8(%esp), %edx
L: pushl %ecx
pushl %edx
subl $8, %esp
movl %ecx, (%esp)
movl %edx, 4(%esp)
call makepass
addl $8, %esp
popl %edx
popl %ecx
testl %eax, %eax
jne L
ret
Variante di
bubblesort che ad ogni chiamata
makepass rilegge dallo stack frame del chiamante i parametri da passare:
# void bubblesort(int* v, int n) {
# while (makepass(v,n));
# }
.globl bubblesort
bubblesort:
subl $8, %esp
movl 12(%esp), %eax
movl %eax, (%esp)
movl 16(%esp), %eax
movl %eax, 4(%esp)
call makepass
addl $8, %esp
testl %eax, %eax
jne bubblesort
ret