Università degli Studi di Udine
Fondamenti di Programmazione + Architettura dei calcolatori / Fondamenti di Informatica II (prof. Montessoro)
2 febbraio 2018
Prova scritta per studenti di Ing. Elettronica e Ing. Gestionale immatricolati negli anni accademici 2016-17 e precedenti – DURATA DELLA PROVA: 3 ORE
Matricola __________________
Nome _____________________
Cognome __________________
A pena di annullamento immediato della prova:
1) Non è possibile consultare libri o appunti (in qualunque forma) né utilizzare calcolatrici, telefoni cellulari, ecc.
2) Non è consentito comunicare (con qualunque mezzo) 3) Non è consentito uscire dall’aula
Lo studente è tenuto a scrivere, correggere, compilare ed eseguire su computer (a casa o in laboratorio) gli esercizi di programmazione prima della prova orale. Alla prova orale lo studente deve portare una memory pen USB contenente i sorgenti dei programmi corretti e le stampe dei relativi file.
1. (2 punti) X16+X15+X2+1 rappresenta:
[ ] uno schema di memorizzazione dei bit ridondanti nella codifica di Hamming [ ] una funzione di compressione senza perdita
[ ] una funzione di compressione con perdita [ ] un polinomio generatore per il CRC
Si consideri una libreria in linguaggio C per manipolare file audio così definita:
typedef unsigned char byte;
typedef unsigned short int word;
typedef unsigned long int dword;
#define SAMPLE(wave, channel, offset) \ wave.wavedata.sample \ [2 * (offset) + (channel)]
#define FMTPCM 1
#define SAMPLINGRATE 44100
#define CHANNELS 2
#define BITSPERSAMPLE 16
#define LEFT 0
#define RIGHT 1
#define RIFF_ID "RIFF"
#define WAV_ID "WAVE"
#define FMT_ID "fmt "
#define DATA_ID "data"
typedef struct tagRIFFHEADER {
char riffid[4];
dword FileSize;
char waveid[4];
} RIFFHEADER;
typedef struct tagFMTHEADER {
char fmtid[4];
dword fmtsize;
word format;
word channels;
dword SampleRate;
dword BytesPerSecond;
word BlockAlign;
word BitsPerSample;
} FMTHEADER;
typedef struct tagWAVEDATA {
char dataid[4];
dword DataSize;
signed short int *sample;
} WAVEDATA;
typedef struct tagWAVE {
RIFFHEADER riffheader;
FMTHEADER fmtheader;
unsigned long int numofstereosamples;
WAVEDATA wavedata;
} WAVE;
void WriteWave (WAVE wave, FILE *fp);
WAVE ReadWave (FILE *fp);
WAVE CreateEmptyCDaudioWave (unsigned long int numofstereosamples);
void ReleaseWaveData (WAVE *wave);
2. (4 punti) Per amplificare un suono senza incorrere nell’overflow è necessario conoscere in anticipo il massimo valore assunto dai campioni nella WAVE da amplificare.
Si scriva in linguaggio C la funzione short int max_campione (WAVE w) che riceve come argomento una WAVE (già letta da file e caricata in memoria) e restituisca il massimo valore presente tra i campioni di entrambi i canali.
(svolgere sul retro)
Un elaboratore (il modello didattico SimCPU visto a lezione) dispone di CPU (a 16 bit) con 16 registri di uso generale (R0, R1, ..., R15) più il Program Counter, l’Instruction Register, lo Stack Pointer e 4 flag Z (zero), N (negative), C (carry) e V (overflow).
Si ricorda che il linguaggio assembler di tale elaboratore dispone delle seguenti istruzioni:
assembly inst. name machine code action LDWI d X load word 00010000dddd0000 DATA(16) d <- X LDWA d A load word 00100000dddd0000 ADDR(16) d <- mem[A]
LDWR d a load word 00110000ddddaaaa d <- mem[a]
LDBI d X load byte 00010001dddd0000 DATA(8) d <- X LDBA d A load byte 00100001dddd0000 ADDR(16) d <- mem[A]
LDBR d a load byte 00110001ddddaaaa d <- mem[a]
STWA s A store word 00100010ssss0000 ADDR(16) mem[A] <- s STWR s a store word 00110010ssssaaaa mem[a] <- s STBA s A store byte 00100011ssss0000 ADDR(16) mem[A] <- s STBR s a store byte 00110011ssssaaaa mem[a] <- s MV s d move 00000100ssssdddd d <- s PUSH s push 00001000ssss0000 push (s) POP d pop 00001001dddd0000 d <- pop () SPRD d read SP 00001101ssss0000 d <- SP SPWR s write SP 00001110ssss0000 SP <- s ADD s d add 01000000ssssdddd d <- d + s SUB s d subtract 01000001ssssdddd d <- d - s NOT r bitwise NOT 01000010rrrr0000 r <- ~r AND s d bitwise AND 01000011ssssdddd d <- d & s OR s d bitwise OR 01000100ssssdddd d <- d | s XOR s d bitwise XOR 01000101ssssdddd d <- d ^ s INC r increment 01001000rrrr0000 r <- r + 1 DEC r decrement 01001001rrrr0000 r <- r + 1 LSH r left shift 01001010rrrr0000 r <- r << 1 RSH r right shift 01001011rrrr0000 r <- r >> 1
assembly inst. name machine code action INW d A input word 10000000dddd0000 IN_ADDR(16) d <- read[A]
INB d A input byte 10000001dddd0000 IN_ADDR(16) d <- read[A]
OUTW s A out word 10000010ssss0000 OUT_ADDR(16) out[A] <- s OUTB s A out byte 10000011ssss0000 OUT_ADDR(16) out[A] <- s
TSTI A test input 1000010000000000 IN_ADDR(16) if completed then Z <- 1 else Z <- 0
TSTO A test output 1000010100000000 OUT_ADDR(16) if completed then Z <- 1 else Z <- 0
BR A branch 1100000000000000 ADDR(16) PC <- A JMP F jump 11000001FFFFFFFF PC <- PC + F
JMPZ F jump if zero 11000010FFFFFFFF if (z == 1) PC <- PC + F JMPNZ F jump if not zero 11000011FFFFFFFF if (z == 0) PC <- PC + F JMPN F jump if negative 11000100FFFFFFFF if (N == 1) PC <- PC + F JMPNN F jump if not neg. 11000101FFFFFFFF if (N == 0) PC <- PC + F JMPC F jump if carry 11000110FFFFFFFF if (C == 1) PC <- PC + F JMPV F jump if overflow 11000111FFFFFFFF if (V == 1) PC <- PC + F CALL A subroutine call 1100100000000000 ADDR(16) push (PC); PC <- A RET return from sub. 1100100100000000 PC <- pop() HLT halt 1100111100000000 halt LEGENDA:
- lettere minuscole = registri; lettere maiuscole = dati numerici - ‘r’ = registro letto e modificato
- ‘s’ = registro soltanto letto - ‘d’ = registro modificato
- ‘a’ = registro il cui contenuto è usato come indirizzo - FFFFFFFF = offset (in complemento a 2)
3. (5 punti) Assumendo che i nomi delle variabili corrispondano ai nomi dei registri della CPU, si traduca in linguaggio assembly il seguente frammento di codice C:
R0 = 0;
while ((R10 = *R1) != 0) {
R1++;
R0++;
}
4. (6 punti) Si disegni lo schema di una memoria cache a mappatura diretta e se ne spieghi il funzionamento con un esempio numerico ipotizzando, per semplicità, indirizzi di memoria scritti su otto bit, blocchi da 16 byte e linee da quattro byte.
5. (13 punti) Un’azienda deve dipingere degli oggetti di forme geometriche regolari (sfere e cubi) con diversi colori. I colori sono generati mescolando in proporzioni diverse le vernici di cinque colori primari: blu, rosso, giallo, bianco e nero. La tabella che indica come devono
essere combinati i colori primari per ottenere un dato colore è riportata in un file il cui formato può essere dedotto dall’esempio a fianco. Come si può facilmente intuire, la prima è una riga di intestazione e le altre riportano le percentuali da utilizzare per ciascun colore primario.
Valgono le seguenti assunzioni:
• i codici dei colori sono sempre composti da una sola parola;
• le percentuali sono sempre dei numeri interi;
• i colori primari sono sempre gli stessi e sono sempre scritti nel medesimo ordine (blu, rosso, giallo, bianco e nero);
• il massimo numero di colori nella tabella è pari a 100;
• indipendentemente dal colore utilizzato, per dipingere una superficie di 1 metro quadrato sono necessari 0.15 litri di vernice.
Un secondo file contiene un elenco di superfici (espresse in metri quadrati) con associato il colore da utilizzare per ciascuna. Si veda l’esempio a fianco. Si assuma che tutti i colori riportati in tale file siano sicuramente presenti nella tabella di cui sopra.
Si scriva un programma in linguaggio C che riceva sulla riga di comando il nome di un file contenente la tabella dei colori e il nome di un file contenente l’elenco delle superfici come sopra descritto.
Il programma deve stampare la quantità totale, in litri, dei colori primari necessari a verniciare tutti gli oggetti presenti nel secondo file.
Relativamente agli esempi sopra riportati, il programma dovrà stampare:
0.700923 litri di blu 0.340797 litri di rosso 2.54435 litri di giallo 0.237285 litri di bianco 0.1026 litri di nero
3.6 BLU_S 15.3 YEL7 2 YEL7 5.273 C0Q2 colore % blu % rosso % giallo % bianco % nero C0Q2 34 26 10 30 0 BLU_S 80 1 0 0 19 YEL7 0 5 95 0 0
