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

Soluzioni fac-simile esonero (A.A. 2016-17)


[ Fac-simile esonero ]

Parte 1

es1.s
# int test(int min, int max, int* x) {
#     return (*x<min || *x>max) && max>min;
# }

.globl test

test:
    pushl %esi
    pushl %edi
    movl 12(%esp), %esi # min
    movl 16(%esp), %edi # max
    movl 20(%esp), %edx # x
    movl (%edx), %edx   # *x
    cmpl %esi, %edx
    setl %al
    cmpl %edi, %edx
    setg %cl
    orb %cl, %al
    cmpl %esi, %edi
    setg %cl
    andb %cl, %al
    movzbl %al, %eax
    popl %edi
    popl %esi
    ret


Parte 2

Soluzione 1

es2.s
# void fix(const int* u, int* v, int n) {
#     int i;
#     for (i=0; i<n-1; i++) {
#         int m = media(u[i],u[i+1]);
#         if (m > media(v[i],v[i+1])) v[i]=m;
#     }
# }

.globl fix

fix:
    pushl %ebx
    pushl %esi
    pushl %edi
    movl 16(%esp), %ebx # u
    movl 20(%esp), %esi # v
    xorl %edi, %edi     # i
L:  movl 24(%esp), %ecx # rileggo n ad ogni iterazione: media() sporca %ecx
    decl %ecx
    cmpl %ecx, %edi
    jge E
    subl $8, %esp
    movl 4(%ebx, %edi, 4), %eax # u[i+1]
    movl %eax, 4(%esp)
    movl (%ebx, %edi, 4), %eax  # u[i]
    movl %eax, (%esp)
    call media
    addl $8, %esp
    pushl %eax  # m
    subl $8, %esp
    movl 4(%esi, %edi, 4), %eax # v[i+1]
    movl %eax, 4(%esp)
    movl (%esi, %edi, 4), %eax  # v[i]
    movl %eax, (%esp)
    call media
    addl $8, %esp
    popl %edx   # m
    incl %edi   # i++
    cmpl %eax, %edx #
    jle L
    movl %edx, -4(%esi, %edi, 4) # i รจ stato incrementato quindi -4
    jmp L
E:  popl %edi
    popl %esi
    popl %ebx
    ret


Soluzione 2

es2.s
# void fix(const int* u, int* v, int n) {
#     int i;
#     i = 0;
#     n--;
# L:  if (i>=n) goto E;
#     int m = media(u[i],u[i+1]);
#     int k = media(v[i],v[i+1]);
#     if (m <= k) goto S;
#     v[i]=m;
# S:  i++;
#     goto L;
# E:  ;
# }
#
# Allocazione dei registri:
#   u   -> 28(%esp) (ed ecx localmente)
#   v   -> ebp
#   n-1 -> ebx
#   i   -> esi
#   m   -> edi
#   k   -> eax

.globl fix

fix:
    pushl %ebp
    pushl %ebx
    pushl %esi
    pushl %edi
    subl $8, %esp

    movl 32(%esp), %ebp
    movl 36(%esp), %ebx

    xorl %esi, %esi
    decl %ebx  # n-1

L:  cmpl %ebx, %esi
    jge E

    movl 28(%esp), %ecx
    movl (%ecx, %esi, 4), %eax
    movl %eax, (%esp)
    movl 4(%ecx, %esi, 4), %eax
    movl %eax, 4(%esp)
    call media
    movl %eax, %edi

    movl (%ebp, %esi, 4), %eax
    movl %eax, (%esp)
    movl 4(%ebp, %esi, 4), %eax
    movl %eax, 4(%esp)
    call media

    cmpl %eax, %edi
    jle S

    movl %edi, (%ebp,%esi,4)
S:  incl %esi
    jmp L

E:  addl $8, %esp
    popl %edi
    popl %esi
    popl %ebx
    popl %ebp
    ret


Soluzione 3
Soluzione avanzata proposta da uno studente che sfrutta l'aritmetica dei puntatori e LOOPNZ [doc1 doc2]

es2.s
# void fix(const int* u, int* v, int n) {
#     if (n==0) return;
#     u += n;
#     v += n;
#     int c = n;
#     do {
#         int b = -c;
#         int m = media(u[b],u[b+1]);
#         if (m > media(v[b],v[b+1])) v[b] = m;
#     } while (--c);
# }

.globl fix

fix:
    pushl %ebx  # b
    pushl %esi  # u
    pushl %edi  # v
    movl 16(%esp), %esi
    movl 20(%esp), %edi
    movl 24(%esp), %ecx # c=n
    testl %ecx, %ecx
    jle E
    leal (%esi, %ecx, 4), %esi  # u=u+n
    leal (%edi, %ecx, 4), %edi  # v=v+n
    subl $12, %esp
L:  movl %ecx, %ebx
    negl %ebx     # b=-c
    movl (%esi, %ebx, 4), %ecx # ecx riassegnato a fine loop
    movl %ecx, (%esp)
    movl 4(%esi, %ebx, 4), %ecx
    movl %ecx, 4(%esp)
    call media
    movl %eax, 8(%esp)
    movl (%edi, %ebx, 4), %ecx
    movl %ecx, (%esp)
    movl 4(%edi, %ebx, 4), %ecx
    movl %ecx, 4(%esp)
    call media
    movl %ebx, %ecx
    negl %ecx   # c=-b
    cmpl %eax, 8(%esp)
    jle D
    movl 8(%esp), %eax
    movl %eax, (%edi, %ebx, 4)
D:  loopnz L    # if (--c) goto L
E:  addl $12, %esp
    popl %edi
    popl %esi
    popl %ebx
    ret


Parte 3

sort-opt.c
#include "sort.h"

static int my_cmp(int* a, int* b) {
    return *a-*b;
}

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void sort(int* v, int n) {
    int k, i;
    for (k=0; k<n; k++) {
        int changed = 0;
        for (i=1; i<n; i++)
            if (my_cmp(v+i-1, v+i) > 0) {
                swap(v+i-1, v+i);
                changed = 1;
            }
        if (!changed) break;
    }
}


Parte 4

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