[T02] Esercitazione del 8 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!

Per maggiori informazioni fate riferimento al regolamento delle esercitazioni.

Esercizio 1 (comparatore per interi)

Tradurre nel file E1/e1.s la seguente funzione C contenuta in E1/e1.c che realizza un comparatore per tipi int:

int comp(void* xv, void* yv) {
    int* x = (int*)xv; 
    int* y = (int*)yv; 
    return *x - *y;
}

Nota: in IA32 i puntatori non hanno tipo e sono semplicemente dei contenitori che denotano indirizzi, cioè interi senza segno. Pertanto il cast (int*) è come se non ci fosse nella traduzione IA32. Usare il main di prova nella directory di lavoro E1 compilando con gcc -m32 e1_main.c e1.s -o e1.

Esercizio 2 (ricerca in un array)

Tradurre nel file E2/e2.s la seguente funzione C contenuta in E2/e2.c che cerca un intero in un array:

int find(int* v, int n, int x) {
    int i;
    for (i=0; i<n; ++i)
        if (v[i] == x) return 1;
    return 0;
}

Suggerimento: provare a riformulare il codice C in una forma equivalente in modo che usi solo tre variabili.

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

Esercizio 3 (strcmp alla vaccinara)

Tradurre nel file E3/e3.s la seguente funzione C contenuta in E3/e3.c che realizza la funzione di confronto di stringhe C strcmp come specificato dallo standard POSIX:

char my_strcmp(const char* s1, const char* s2) {
    while (*s1 && *s1 == *s2) {
        s1++;
        s2++;
    }
    return *s1 - *s2;
}

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 nel file E4/e4.c una funzione dal seguente prototipo che, data una stringa s e una stringa sub, calcola il numero di posizioni distinte in s in cui sub appare come sottostringa:

int count_substrings(const char* s, const char* sub);

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

Esercizio 5 (Domande)

Rispondere ai quiz riportati nel form di consegna di consegna.

Soluzioni

Esercizio 1 (comparatore per interi)

.global comp

comp:
    movl 4(%esp), %eax
    movl 8(%esp), %ecx
    movl (%eax), %eax
    subl (%ecx), %eax
    ret

Esercizio 2 (ricerca in un array)

C equivalente:

int find(int* v, int n, int x) {
    int* c = v;
    int  d = n;
    int  a = x;
    d--;
L:  if (d < 0)     goto R0;
    if (c[d] == a) goto R1;
    d--;
    goto L;
R0: a = 0;
    return a;
R1: a = 1;
    return a;
}

IA32:

.global find

find: # int find(int* v, int n, int x) {
    movl 4(%esp), %ecx         # int* c = v;
    movl 8(%esp), %edx         # int  d = n;
    movl 12(%esp), %eax        # int  a = x;
    decl %edx                  # d--;
L:  testl %edx, %edx           # if (d < 0)
    jl R0                      # goto R0;
    cmpl %eax, (%ecx,%edx,4)   # if (c[d] == a)
    je R1                      # goto R1;
    decl %edx                  # d--;
    jmp L                      # goto L;
R0: xorl %eax, %eax            # a = 0;
    ret                        # return a;
R1: movl $1, %eax              # a = 1;
    ret                        # return a;

Esercizio 3 (strcmp alla vaccinara)

C equivalente:

char my_strcmp(const char* s1, const char* s2) {
    const char* c = s1;
    const char* d = s2;
L:; char a = *c;
    if (a == 0)  goto E;
    if (a != *d) goto E;
    c++;
    d++;
    goto L;
E:  a = a - *d;
    return a;
}

IA32:

.global my_strcmp

my_strcmp: # char my_strcmp(const char* s1, const char* s2) {
    movl 4(%esp), %ecx           # const char* c = s1;
    movl 8(%esp), %edx           # const char* d = s2;
L:  movb (%ecx), %al             # ; char a = *c;
    testb %al, %al               # if (a == 0)
    je E                         # goto E;
    cmpb (%edx), %al             # if (a != *d)
    jne E                        # goto E;
    incl %ecx                    # c++;
    incl %edx                    # d++;
    jmp L                        # goto L;
E:  subb (%edx), %al             # a = a - *d;
    ret                          # return a;

Esercizio 4 (Palestra C)

static int is_prefix(const char* sub, const char* s) {
    while (*sub == *s && *sub!=0 && *s!=0) {
        sub++;
        s++;
    }
    return *sub == 0;
}

int count_substrings(const char* s, const char* sub) {
    int cnt = 0;
    do cnt += is_prefix(sub,s); while(*s++);
    return cnt;
}

Esercizio 5 (Domande)

Domanda 1) L’operando (%eax, %ecx, 5) è valido?

• No [la scala può essere solo {1, 2, 4}]

Domanda 2) Si consideri la variabile int* p e si assuma che venga tenuta nel registro %eax. A quale istruzione assembly corrisponde l’istruzione C p++?

• addl $4,%eax [p è un puntatore ad int: l’indirizzo in %eax va incrementato di 4 byte]

Domanda 3) Quali delle seguenti operazioni IA32 permette di azzerare il registro %eax?

• qualunque delle precedenti

Domanda 4) Quali dei seguenti predicati C permette di verificare se la variabile int x contiene un valore pari?

• x & 1 == 0 [se il bit meno significativo è zero allora il numero è pari]

Domanda 5) Come tradurresti in IA32 l’assegnamento v[5] = 7, assumendo che v sia int* e sia tenuto nel registro %eax?

• movl $7, 20(%eax) [l’elemento v[5] si trova a 20 byte da v in quanto è preceduto da 4 elementi di taglia 4 byte]

Domanda 6) Quale operazione useresti per scambiare i 16 bit meno significativi di int x con i 16 più significativi?

• x = (x << 16) + ((unsigned)x >> 16);

Domanda 7) Si consideri la riga di comando gcc main.c prova.s -o prova su una piattaforma a 64 bit. Dove prova.s è un codice IA32. Che esito probabile ti aspetteresti?

• Segmentation Fault [codice IA32 userà %esp (32bit) invece che %rsp (64bit) andando ad operare con indirizzi non validi]