Additions:
**Nota bene**: le soluzioni proposte sono ottimizzate per le prestazioni. Vi sono molte altre soluzioni ammissibili ugualmente valide: postatele sul [[http://solo.diag.uniroma1.it/index.php?board=304.0 forum]] e le discutiamo. Altre soluzioni sono disponibili sui diari delle lezioni dei due canali.
Deletions:
**Nota bene**: le soluzioni proposte sono ottimizzate per le prestazioni. Vi sono molte altre soluzioni ammissibili ugualmente valide: postatele sul [[http://solo.diag.uniroma1.it/index.php?board=304.0 forum]] e le discutiamo.
Variante 2 (makepass):
# int makepass(int* v, int n) { // esi <-> v, edi <-> n
# int cont = 0; ebx <-> cont
# L: n--;
# if (n<=0) goto E;
# if (v[n]>=v[n-1]) goto L;
# swap(v+n, v+n-1);
# cont = 1;
# goto L;
# E: return cont;
makepass:
subl $8, %esp # prologo
movl 24(%esp), %esi # v
movl 28(%esp), %edi # n
xorl %ebx, %ebx # int cont = 0; ebx <-> cont
L: decl %edi # L: n--
cmpl $0, %edi # tmp = n-0
jle E # if (tmp<=0) goto E
movl (%esi,%edi,4), %ecx # c = v[n]
cmpl -4(%esi,%edi,4), %ecx # tmp = c-v[n-1]
jge L # if (tmp>=0) goto L;
leal (%esi,%edi,4), %ecx # c = &v[n]
movl %ecx, (%esp) # 1mo param
leal -4(%esi,%edi,4), %ecx # c = &v[n-1]
movl %ecx, 4(%esp) # 2do param
call swap # swap(v+n, v+n-1);
movl $1, %ebx # cont = 1;
jmp L # goto L;
E: movl %ebx, %eax # E: return cont;
addl $8, %esp # epilogo
No differences.
Additions:
R: movl %esi, (%esp) # 1st param = v
call makepass
Deletions:
movl %esi, (%esp) # 1st param = v
R: call makepass
No differences.
Additions:
# int makepass(int* v, int n) { // esi <-> v, edi <-> n
# int cont = 0; ebx <-> cont
# L: n--;
# if (n<=0) goto E;
# if (v[n]>=v[n-1]) goto L;
# swap(v+n, v+n-1);
# cont = 1;
# goto L;
# E: return cont;
makepass:
subl $8, %esp # prologo
movl 24(%esp), %esi # v
movl 28(%esp), %edi # n
xorl %ebx, %ebx # int cont = 0; ebx <-> cont
L: decl %edi # L: n--
cmpl $0, %edi # tmp = n-0
jle E # if (tmp<=0) goto E
movl (%esi,%edi,4), %ecx # c = v[n]
cmpl -4(%esi,%edi,4), %ecx # tmp = c-v[n-1]
jge L # if (tmp>=0) goto L;
leal (%esi,%edi,4), %ecx # c = &v[n]
movl %ecx, (%esp) # 1mo param
leal -4(%esi,%edi,4), %ecx # c = &v[n-1]
movl %ecx, 4(%esp) # 2do param
call swap # swap(v+n, v+n-1);
movl $1, %ebx # cont = 1;
jmp L # goto L;
E: movl %ebx, %eax # E: return cont;
addl $8, %esp # epilogo
Deletions:
# int makepass(int* v, int n) { // esi <-> v, edi <-> n
# int cont = 0; ebx <-> cont
# L: n--;
# if (n<=0) goto E;
# if (v[n]>=v[n-1]) goto L;
# swap(v+n, v+n-1);
# cont = 1;
# goto L;
# E: return cont;
makepass:
subl $8, %esp # prologo
movl 24(%esp), %esi # v
movl 28(%esp), %edi # n
xorl %ebx, %ebx # int cont = 0; ebx <-> cont
L: decl %edi # L: n--
cmpl $0, %edi # tmp = n-0
jle E # if (tmp<=0) goto E
movl (%esi,%edi,4), %ecx # c = v[n]
cmpl -4(%esi,%edi,4), %ecx # tmp = c-v[n-1]
jge L # if (tmp>=0) goto L;
leal (%esi,%edi,4), %ecx # c = &v[n]
movl %ecx, (%esp) # 1mo param
leal -4(%esi,%edi,4), %ecx # c = &v[n-1]
movl %ecx, 4(%esp) # 2do param
call swap # swap(v+n, v+n-1);
movl $1, %ebx # cont = 1;
jmp L # goto L;
E: movl %ebx, %eax # E: return cont;
addl $8, %esp # epilogo
Additions:
Variante 2 (makepass):
# int makepass(int* v, int n) { // esi <-> v, edi <-> n
# int cont = 0; ebx <-> cont
# L: n--;
# if (n<=0) goto E;
# if (v[n]>=v[n-1]) goto L;
# swap(v+n, v+n-1);
# cont = 1;
# goto L;
# E: return cont;
makepass:
subl $8, %esp # prologo
movl 24(%esp), %esi # v
movl 28(%esp), %edi # n
xorl %ebx, %ebx # int cont = 0; ebx <-> cont
L: decl %edi # L: n--
cmpl $0, %edi # tmp = n-0
jle E # if (tmp<=0) goto E
movl (%esi,%edi,4), %ecx # c = v[n]
cmpl -4(%esi,%edi,4), %ecx # tmp = c-v[n-1]
jge L # if (tmp>=0) goto L;
leal (%esi,%edi,4), %ecx # c = &v[n]
movl %ecx, (%esp) # 1mo param
leal -4(%esi,%edi,4), %ecx # c = &v[n-1]
movl %ecx, 4(%esp) # 2do param
call swap # swap(v+n, v+n-1);
movl $1, %ebx # cont = 1;
jmp L # goto L;
E: movl %ebx, %eax # E: return cont;
addl $8, %esp # epilogo
Additions:
%%(c;es3.s)
.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
# 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 %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
# void bubblesort(int* v, int n) {
# while (makepass(v,n));
bubblesort: # v <-> esi, n <-> edi
subl $8, %esp
movl 20(%esp), %esi # esi = v
movl 24(%esp), %edi # edi = n
movl %esi, (%esp) # 1st param = v
movl %edi, 4(%esp) # 2nd param = n
R: call makepass
testl %eax, %eax
jne R
addl $8, %esp
popl %edi
Deletions:
[...]
Additions:
# int binsearch(int* v, int n, int x) {
# int m = 0; // restituisce 1 <=> x รจ nell'array ordinato v di dimensione n
# while (m
# 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;
cmovgl %edx, %edi # if (res > 0) n = k
Deletions:
cmovgl %edx, %edi # if (res > 0) n = k
Additions:
**Nota bene**: le soluzioni proposte sono ottimizzate per le prestazioni. Vi sono molte altre soluzioni ammissibili ugualmente valide: postatele sul [[http://solo.diag.uniroma1.it/index.php?board=304.0 forum]] e le discutiamo.
Deletions:
**Nota bene**: le soluzioni proposte sono ottimizzate per le prestazioni. Vi sono molte altre soluzioni ammissibili ugualmente valide.
Additions:
cmpl %esi, %edi # res = n-m
jg L # if (res > 0) goto L
Deletions:
jl L # if (res < 0) goto L
Additions:
jmp S # goto S
Deletions:
jmp S
Additions:
cancspazi: # s <-> eax, p <-> ecx
Deletions:
cancspazi: # s <-> eax, p <-> ecx
Additions:
cancspazi: # s <-> eax, p <-> ecx
movl 4(%esp), %eax # eax = s
movl %eax, %ecx # ecx = p = s
Deletions:
cancspazi:
movl 4(%esp), %eax # s <-> eax
movl %eax, %ecx # p <-> ecx
Additions:
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 %edi, %esi # res = m-n
jl 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
ret # return eax
Deletions:
movl 12(%esp), %ecx
movl 16(%esp), %edi
movl 20(%esp), %eax
xorl %esi, %esi
cmpl %edi, %esi
jge E0
L: leal (%esi,%edi), %edx
shrl $1, %edx
cmpl %eax, (%ecx,%edx,4)
je E1
cmovgl %edx, %edi
leal 1(%edx), %edx # edx++ (no side-effect su EFLAGS)
cmovll %edx, %esi
cmpl %edi, %esi
jl L
E0: xorl %eax, %eax
jmp C
E1: movl $1, %eax
C: popl %edi
Additions:
leal 1(%edx), %edx # edx++ (no side-effect su EFLAGS)
Deletions:
leal 1(%edx), %edx # no side-effect su EFLAGS
Additions:
leal 1(%edx), %edx # no side-effect su EFLAGS
Deletions:
leal 1(%edx), %edx # no side-effect su EFLAGS
Additions:
leal 1(%edx), %edx # no side-effect su EFLAGS
Deletions:
leal 1(%edx), %edx
Additions:
jmp C
C: popl %edi
Deletions:
popl %edi
popl %edi