[T05] Esercitazione del 29 marzo 2019

Istruzioni per l’esercitazione:

• Aprite il form di consegna in un browser e loggatevi con le vostre credenziali uniroma1.
• Scaricate e decomprimete sulla scrivania il codice dell’esercitazione. Vi sarà una sotto-directory separata per ciascun esercizio di programmazione. Non modificate in alcun modo i programmi di test *_main.c.
• Rinominare la directory chiamandola cognome.nome. Sulle postazioni del laboratorio sarà /home/biar/Desktop/cognome.nome/.
• È possibile consultare appunti/libri e il materiale didattico online.
• Rispondete alle domande online sul modulo di consegna.
• Finiti gli esercizi, e non più tardi della fine della lezione:
  • zippate la directory di lavoro in cognome.nome.zip (zip -r cognome.nome.zip cognome.nome/).
• Per consegnare:
  • inserite nel form di consegna come autovalutazione il punteggio di ciascuno dei test forniti (inserite zero se l’esercizio non è stato svolto, non compila, o dà errore di esecuzione).
  • fate upload del file cognome.nome.zip.
  • importante: fate logout dal vostro account Google!
• Prima di uscire:
  • eliminate dal desktop la directory creata (rm -rf cognome.nome).
  • firmate il foglio presenze.
  • rimettete a posto eventuali sedie prese all’ingresso dell’aula!
• Suggerimento Non traducete direttamente da C a IA32, ma scrivere prima una versione C intermedia E1/e1_eq.c equivalente a quella di partenza, ma più semplice da tradurre in assembly. Testatela con il main di prova prima di passare a scrivere la versione .s. E’ inutile tradurre la versione C equivalente se è errata!

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

• A. Le due istruzioni scrivono lo stesso valore in %eax, ma “idivl” è più efficiente di “sarl”
• B. Le due istruzioni scrivono lo stesso valore in %eax, ma “sarl” è più efficiente di “idivl”
• C. Le due istruzioni scrivono valori diversi in %eax
• D. In questo caso la “idivl” non modifica il valore del registro %edx
• E. Nessuna delle precedenti

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:

• A. Se eseguiamo “cmovnzl %edx, %ecx” viene scritto il valore 10 nel registro %ecx
• B. Se eseguiamo “cmovzl %edx, %ecx” viene scritto il valore 0 nel registro %ecx
• C. L’istruzione “cmovnzw %dx, %cx” non modifica il valore del registro %ecx
• D. L’istruzione “cmovel %edx, %ecx” è equivalente all’istruzione “cmovnzl $10, %ecx”
• E. Nessuna delle precedenti

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

• A. Se eseguiamo “cmpl %ecx, %eax” e “cmovlel %edx, %eax” viene scritto il valore 2 nel registro %eax
• B. Se eseguiamo “cmpl %ecx, %eax” e “cmovbl %edx, %eax” viene scritto il valore 2 nel registro %eax
• C. Se eseguiamo “cmpb $0, %al” e “cmovel %edx, %eax” viene scritto il valore 2 nel registro %eax
• D. Se eseguiamo “subl %ecx, %eax” e “cmovgl %edx, %eax” viene scritto il valore 2 nel registro %eax
• E. Nessuna delle precedenti

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

• A. cmovzb %al, %cl
• B. cmovzl $3, %eax
• B. cmovgew %ax, (%ecx)
• B. cmpl %ecx, $10
• B. Nessuna delle precedenti

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

es.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)

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

es.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;
}

es.s

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

es.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;
    movzbl %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 = 0; idx<32; idx++){
         bin[idx] = '0' + (x & 1);
         x = x >> 1;
    }     
}

Esercizio 5 (Domande)

1. B - Le due istruzioni scrivono lo stesso valore in %eax, ma “sarl” è più efficiente di “idivl”
2. A - Se eseguiamo “cmovnzl %edx, %ecx” viene scritto il valore 10 nel registro %ecx
3. D - Se eseguiamo “subl %ecx, %eax” e “cmovgl %edx, %eax” viene scritto il valore 2 nel registro %eax
4. E - Nessuna delle precedenti