Sistemi di Calcolo

Corso di Laurea in Ingegneria Informatica e Automatica - A.A. 2017-2018

HomePage | Avvisi | Diario lezioni | Programma | Materiale didattico | Esami | Forum | Login

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

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;
# }

.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

es2.c
void cancspazi(char* s) {
    char* p = s;
    do if (*s!=' ') *p++ = *s;
    while (*s++!=0);
}


es2.s
# 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

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
    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

Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by WikkaWiki
Page was generated in 0.0728 seconds