Sistemi di Calcolo

Corso di Laurea in Ingegneria Informatica e Automatica

Home | Avvisi | Diario Lezioni | Esercitazioni | Esami | Materiale Didattico | Valutazioni Studenti | Lezioni di Camil Demetrescu |

[T05] Esercitazione del 27 marzo 2020

Istruzioni per l’esercitazione:

Per maggiori informazioni fate riferimento al regolamento delle esercitazioni.

Esercizio 1 (Ricerca binaria in un array ordinato)

Tradurre nel file E1/e1.s la seguente funzione C contenuta in E1/e1.c che implementa il classico algoritmo ricerca binaria (o dicotomica) restituento 1 se x appartiene all’array v di n interi int e 0 altrimenti. Usare il file E1/e1_eq.c per sviluppare la versione C equivalente.

#include "e1.h"

int binsearch(int *v, int n, int x) {
    int i=0, j=n;
    while (i<j) {
        int m = (i+j)/2;
        if (v[m]==x) return 1;
        if (v[m]>x) j=m;
        else i=m+1;
    }
    return 0;
}

Suggerimento: usare lo shift per dividere per 2.

Usare il main di prova nella directory di lavoro E1 compilando con gcc -m32 e1_main.c e1.s -o e1.

Esercizio 2 (Minimo Comune Multiplo)

Tradurre nel file E2/e2.s la seguente funzione C contenuta in E2/e2.c che, dati due interi, ne calcola il minimi comune multiplo. Usare il file E2/e2_eq.c per sviluppare la versione C equivalente.

#include "e2.h"

int lcm(int x, int y) {
    int greater = y;
    if (x > y)
        greater = x;
    while (1) {
        if ((greater % x == 0) && (greater % y == 0))
            return greater;
        greater++;
    }
}

Suggerimento: usare le istruzioni CMOVcc e SETcc.

Usare il main di prova nella directory di lavoro E2 compilando con gcc -m32 e2_main.c e2.s -o e2.

Esercizio 3 (Frequenza caratteri)

Tradurre nel file E3/e3.s la seguente funzione C contenuta in E3/e3.c che, data una stringa C, calcola la frequenza dei caratteri nel testo e restituisce il carattere ASCII più frequente. Usare il file E3/e3_eq.c per sviluppare la versione C equivalente.

#include <string.h>
#include "e3.h"

char charfreq(const char* s) {
    unsigned freq[256];
    memset(freq, 0, 256*sizeof(unsigned));

    while (*s) freq[*s++]++;

    unsigned maxi = 0;
    unsigned maxf = freq[0];
    int i;
    for (i=1; i<256; ++i){
        if (freq[i]>maxf) {
            maxi = i;        // A1
            maxf = freq[i];  // A2
        }
    }
    return maxi;
}

Suggerimento: usare l’istruzione CMOVcc per fare i due assegnamenti condizionali A1 e A2.

Usare il main di prova nella directory di lavoro E3 compilando con gcc -m32 e3_main.c e3.s -o e3.

Esercizio 4 (Palestra C)

Scrivere una funzione C uint2bin con il seguente prototipo

void uint2bin(unsigned x, char bin[32]);

che, dato un intero x senza segno a 32 bit e un buffer bin di 32 caratteri, ottiene la rappresentazione binaria del numero con il bit più significativo per primo. Gli 0 e 1 nel risultato devono essere rappresentati mediantte i caratteri ASCII ‘0’ e ‘1’.

Ad esempio, invocando la funzione con 0x0F0F0F0F, il buffer di output sarà “00001111000011110000111100001111”.

Usare il main di prova nella directory di lavoro E4 compilando con gcc e4_main.c e4.c -o e4.

Esercizio 5 (Domande)

Rispondi alle seguenti domande, tenendo conto che una risposta corretta vale 1 punti, mentre una risposta errata vale 0 punti.

Domanda 1. Un circuito combinatorio è:

Domanda 2. Data una tensione da 12V e un LED che si illumina in presenza di una corrente nel range [50, 100] mA (oltre tale valore il LED si brucia) quale tra queste resistenze può essere inserita nel circuito per far illuminare il LED?

Domanda 3. Quale tra queste affermazioni su un flip-flop SR (latch) è falsa:

Domanda 4. Cosa calcola la seguente breadboard?

Breadboard

Domanda 5. Siano %eax=20 (decimale), %edx=0 (decimale) e %ecx=8 (decimale). Con riguardo alle due istruzioni “idivl %ecx” e “sarl $3, %eax”, quale delle seguenti affermazioni risulta vera:

Domanda 6. Assumendo %eax=0xFF000000, %ecx=1 (decimale) e %edx=10 (decimale), dopo aver eseguito l’istruzione “testl %eax, %eax” quale delle seguenti affermazioni risulta vera:

Domanda 7. Assumendo %eax=10 (decimale), %ecx=7 (decimale) e %edx=2 (decimale), quale delle seguenti affermazioni risulta vera:

Domanda 8. Quale delle seguenti è un’istruzione valida:

Soluzioni

Esercizio 1 (Ricerca binaria in un array ordinato)

e3_eq.c

#include "e1.h"

int binsearch(int *v, int n, int x) {
    int i=0;
    int j=n;
    int a=1;
L:  if (i>=j) goto E0;
    int m = (i+j) >> 1;
    if (v[m]==x) goto E1;
    if (v[m]<=x) goto F;
    j=m;
    goto L;
F:  i=m+1;
    goto L;
E0: a=0;
E1: return a;
}

e1.s

.globl binsearch

binsearch:  # int binsearch(int *v, int n, int x) {

    # Register allocation: i:esi, j:edi, a=eax, m=ecx, v:edx, n:ebx, x:ebp

    pushl %esi
    pushl %edi
    pushl %ebx
    pushl %ebp

    movl 20(%esp), %edx
    movl 24(%esp), %ebx
    movl 28(%esp), %ebp

    xorl %esi, %esi             # int i=0;
    movl %ebx, %edi             # int j=n;
    movl $1, %eax               # int a=1;
L:  cmpl %edi, %esi             # if (i>=j)
    jge E0                      # goto E0;
    leal (%esi,%edi), %ecx      # m = (i+j)
    sarl %ecx                   #     >> 1;
    cmpl %ebp, (%edx, %ecx, 4)  # if (v[m]==x)
    je E1                       #   goto E1;
    cmpl %ebp, (%edx, %ecx, 4)  # if (v[m]<=x)
    jle F                       # goto F;
    movl %ecx, %edi             # j=m;
    jmp L                       # goto L;
F:  leal 1(%ecx), %esi          # i=m+1;
    jmp L                       # goto L;
E0: xorl %eax, %eax             # a=0;
E1: popl %ebp
    popl %ebx
    popl %edi
    popl %esi
    ret                         # return a;
Esercizio 2 (Minimo Comune Multiplo)

e2_eq.c

#include "e2.h"

int lcm(int x, int y) {
    int si = x;
    int di = y;
    int c = di;
    if (si <= di)
        c = si;
    int a;
L:;
    a = c; // setta d in modo opportuno!
    int d = a % si;
    char bl = d == 0;
    a = c; // setta d in modo opportuno!
    d = a % di;
    char bh = d == 0;
    bl = bl & bh;
    if (bl == 0) goto F;
    a = c;
    return a;
F:
    c++;
    goto L;
}

e2.s

.globl lcm
lcm: # int lcm(int x, int y)
    pushl %esi
    pushl %edi
    pushl %ebx

    movl 16(%esp), %esi     # int si = x;
    movl 20(%esp), %edi     # int di = y;
    movl %edi, %ecx         # int c = di;
    cmpl %edi, %esi         # if (si > di)
    cmovg %esi, %ecx        # c = si;
L:
    movl %ecx, %eax         # a = c; // setta d in modo opportuno!
    movl %eax, %edx
    sarl $31, %edx
    idivl %esi              # int d = a % si;
    testl %edx, %edx        # char bl = d == 0;
    setzb %bl
    movl %ecx, %eax         # a = c; // setta d in modo opportuno!
    movl %eax, %edx
    sarl $31, %edx
    idiv %edi               # d = a % di;
    testl %edx, %edx        # char bh = d == 0;
    setzb %bh
    andb %bh, %bl
    jz F
    movl %ecx, %eax         # a = c;
    popl %ebx
    popl %edi
    popl %esi
    ret                 # return a;
F:
    incl %ecx           # c++;
    jmp L               # goto L;
Esercizio 3 (Frequenza caratteri)

e3_eq.c

#include <string.h>
#include "e3.h"

char charfreq(const char* s) {
    unsigned freq[256];
    memset(freq, 0, 256*sizeof(unsigned));

L1:;char c = *s;
    if (c == 0) goto F;
    freq[c]++;
    s++;
    goto L1;

F:; unsigned maxi = 0;
    unsigned maxf = freq[0];
    int i=1;
L2: if (i>=256) goto E;
    if (freq[i]>maxf) maxi = i;
    if (freq[i]>maxf) maxf = freq[i];
    ++i;
    goto L2;
E:  return maxi;
}

e3.s

.globl charfreq

charfreq: # char charfreq(const char* s) {

    # Register allocation: s: esi, freq:ebx, maxi:eax, maxf:edx, c:cl, i:edi

    pushl %edi                                  # Prologo
    pushl %esi
    pushl %ebx
    subl $1036, %esp                            # unsigned freq[256];

    leal 12(%esp), %ebx
    movl %ebx, (%esp)                           #
    movl $0, 4(%esp)                            #
    movl $1024, 8(%esp)                         #
    call memset                                 # memset(freq, 0, 256*sizeof(unsigned));

    movl 1052(%esp), %esi                       # 
L1: movb (%esi), %cl                            # char c = *s;
    movsbl %cl, %ecx
    testl %ecx, %ecx                            # if (c == 0)
    jz F                                        # goto F;
    incl (%ebx, %ecx, 4)                        # freq[c]++;
    incl %esi                                   # s++;
    jmp L1                                      # goto L1;

F:  xorl %eax, %eax                             # unsigned maxi = 0;
    movl (%ebx), %edx                           # unsigned maxf = freq[0];
    movl $1, %edi                               # int i=1;
L2: cmpl $256, %edi                             # if (i>=256)
    jge E                                       # goto E;
    cmpl %edx,(%ebx,%edi,4)
    cmovgl %edi, %eax                           # if (freq[i]>maxf) maxi = i;
    cmovgl (%ebx, %edi, 4), %edx                # if (freq[i]>maxf) maxf = freq[i];
    incl %edi                                   # ++i;
    jmp L2                                      # goto L2;
E:
    addl $1036, %esp
    popl %ebx
    popl %esi
    popl %edi
    ret                     # return maxi;
Esercizio 4 (Palestra C)
#include <string.h>
#include "e4.h"

void uint2bin(unsigned x, char bin[32]) {
    int idx;
    for (idx = 31; idx>=0; idx--){
         bin[idx] = '0' + (x & 1);
         x = x >> 1;
    }
}
Esercizio 5 (Domande)
  1. A - costruito mediante porte logiche e calcola funzioni booleane
  2. C - 220
  3. B - la configurazione S=0 e R=1 non garatisce Q = NOT Q’
  4. C - OR
  5. B - Le due istruzioni scrivono lo stesso valore in %eax, ma “sarl” è più efficiente di “idivl”
  6. A - Se eseguiamo “cmovnzl %edx, %ecx” viene scritto il valore 10 nel registro %ecx
  7. D - Se eseguiamo “subl %ecx, %eax” e “cmovgl %edx, %eax” viene scritto il valore 2 nel registro %eax
  8. E - Nessuna delle precedenti