Architettura dei calcolatori / Fondamenti di Informatica II (prof. Montessoro) 22 gennaio 2018
Prova scritta per studenti di Ing. Elettronica e Ing. Gestionale immatricolati negli anni accademici 2016-17 e precedenti – DURATA DELLA PROVA: 2 ORE
Matricola __________________
Nome _____________________
Cognome __________________
ISTRUZIONI (da leggere attentamente)
1) 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.
2) Non è consentito l’uso di libri, appunti, calcolatrici, telefoni cellulari.
3) Rispondere sinteticamente negli spazi di fianco o seguenti le domande, oppure sul retro del foglio.
1. (3 punti) Eseguire le seguenti conversioni (scrivendo il risultato sia in binario che in esadecimale), indicando eventualmente se non sono possibili.
-128 in complemento a 2 su 8 bit ______________________________________ 1000 0000, 80 -255 in complemento a 2 su 8 bit ______________________________________ non possibile -128 in binario puro su 8 bit ______________________________________ non possibile -255 in binario puro su 8 bit ______________________________________ non possibile -1 in complemento a 2 su 64 bit ______________________________________ 111...111,
FFFFFFFFFFFFFFFF
2. (2 punti) Indicare le associazioni ritenute corrette
codici polinomiali [ ] compressione [ ] controllo errori [ ] correzione errori singolo bit di parità [ ] compressione [ ] controllo errori [ ] correzione errori RLE [ ] compressione [ ] controllo errori [ ] correzione errori LZW [ ] compressione [ ] controllo errori [ ] correzione errori
codici polinomiali [ ] compressione [X] controllo errori [ ] correzione errori singolo bit di parità [ ] compressione [X] controllo errori [ ] correzione errori RLE [X] compressione [ ] controllo errori [ ] correzione errori LZW [X] compressione [ ] controllo errori [ ] correzione errori
Si consideri la libreria in linguaggio C per manipolare file bitmap vista a lezione, così definita:
typedef unsigned char byte;
typedef unsigned short int word;
typedef unsigned long int dword;
#define BMPFILETYPE 0x4D42 typedef struct tagCOLORTRIPLE {
byte blue;
byte green;
byte red;
} COLORTRIPLE;
typedef struct tagFILEHEADER {
word ImageFileType;
dword FileSize;
word Reserved1;
word Reserved2;
dword ImageDataOffset;
} FILEHEADER;
typedef struct tagBMPHEADER {
dword HeaderSize;
dword ImageWidth;
dword ImageHeight;
word NumberOfImagePlanes;
word BitsPerPixel;
dword CompressionMethod;
dword SizeOfBitmap;
dword HorizonalResolution;
dword VerticalResolution;
dword NumberOfColorsUsed;
dword
NumberOfSignificantColors;
} BMPHEADER;
typedef struct tagBITMAP {
dword width;
dword height;
COLORTRIPLE *pixel;
FILEHEADER fileheader;
BMPHEADER bmpheader;
} BITMAP;
#define PIXEL(image, row, column) \ image.pixel [(row( * image.width +
(column)]
BITMAP ReadBitmap (FILE *fp);
void WriteBitmap (BITMAP bitmap, FILE *fp);
BITMAP CreateEmptyBitmap
(dword height, dword width);
void ReleaseBitmapData (BITMAP *bitmap);
3. (12 punti) Nei montaggi video, l’effetto di transizione tra due immagini detto “tendina orizzontale” (“wipe”, in inglese) consiste in una linea verticale che si sposta dall'estremità sinistra a quella destra dello schermo rivelando la nuova immagine.
Si scriva un programma che generi i fotogrammi intermedi di una tale transizione. Il programma deve ricevere sulla riga di comando, nell’ordine, i seguenti parametri:
• nome del file contenente la prima immagine
• nome del file contenente la seconda immagine (di dimensioni identiche alla prima)
• numero N di fotogrammi da generare
Il programma deve generare N+1 file bitmap di uscita, di nome wipe_0.bmp, wipe_1.bmp, wipe_2.bmp, ... wipe_N.bmp (dove N sarà il numero inserito sulla riga di comando), contenenti ciascuno una delle immagini intermedie. Poiché la transizione risulta divisa in N intervalli, ad ogni passo la porzione visibile della prima immagine diminuirà di 1/N e quella visibile della seconda aumenterà di 1/N. Il primo file generato (crossfade_0.bmp) conterrà la transizione con pesi 100%:0%, e sarà quindi uguale alla prima immagine, mentre l’ultimo file generato conterrà la transizione con pesi 0%:100%, e sarà quindi uguale alla seconda immagine.
La figura riporta un esempio di transizione con N = 3.
wipe_0.bmp wipe_1.bmp wipe_2.bmp wipe_3.bmp Suggerimenti:
• si usi la funzione sprintf per generare i nomi dei file di uscita;
• si scriva una generica funzione che componga due immagini in parti proporzionali ad un valore passato come argomento.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "bmp.h"
#define OUT_FILE_BASE_NAME "wipe_"
#define OUT_FILE_EXT ".bmp"
void wipe_mix (BITMAP img1, BITMAP img2, BITMAP imgout, double p);
int main (int argc, char *argv[]) {
FILE *fp1, *fp2, *fpout;
char filename[64];
int n, i;
BITMAP img1, img2, imgout;
if (argc != 4)
{ printf ("ARGOMENTI: <file in1> <file in2> <N>\n");
exit (EXIT_FAILURE);
}
if ((fp1 = fopen (argv[1], "rb")) == NULL) {
printf ("Error opening input file 1\n");
exit (EXIT_FAILURE);
}
if ((fp2 = fopen (argv[2], "rb")) == NULL) {
printf ("Error opening input file 2\n");
exit (EXIT_FAILURE);
}
n = atoi (argv[3]);
img1 = ReadBitmap (fp1);
fclose (fp1);
img2 = ReadBitmap (fp2);
fclose (fp2);
if (img1.height != img2.height || img1.width != img2.width) {
printf ("Images have different sizes\n");
exit (EXIT_FAILURE);
}
imgout = CreateEmptyBitmap (img1.height, img1.width);
for (i = 0; i <= n; i++) {
sprintf (filename, "%s%d%s", OUT_FILE_BASE_NAME, i, OUT_FILE_EXT);
if ((fpout = fopen (filename, "wb")) == NULL) {
printf ("Error opening output file %s\n", filename);
exit (EXIT_FAILURE);
}
wipe_mix (img1, img2, imgout, i / (double) n);
WriteBitmap (imgout, fpout);
fclose (fpout);
}
ReleaseBitmapData (&img1);
ReleaseBitmapData (&img2);
ReleaseBitmapData (&imgout);
return EXIT_SUCCESS;
}
void wipe_mix (BITMAP img1, BITMAP img2, BITMAP imgout, double p) {
int r, c, threshold;
threshold = p * imgout.width;
for (r = 0; r < imgout.height; r++) {
for (c = 0; c < imgout.width; c++) {
if (c < threshold)
PIXEL (imgout, r, c) = PIXEL (img1, r, c);
else
PIXEL (imgout, r, c) = PIXEL (img2, r, c);
} }
return;
}
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:
4. (4 punti) Facendo uso delle indicazioni presenti nei commenti, si completi il seguente programma in linguaggio assembly, che scambia il contenuto delle variabili X e Y
X: word 0AAAA Y: word 0BBBB
START: _________ ; R1 <- valore della variabile X _________ ; R2 <- valore della variabile Y _________ ; variabile X <- valore di R2 _________ ; variabile Y <- valore di R1 HLT
X: word 0AAAA Y: word 0BBBB
START: LDWA R1 X ; R1 <- valore della variabile X LDWA R2 Y ; R2 <- valore della variabile Y STWA R2 X ; variabile X <- valore di R2 STWA R1 Y ; variabile Y <- valore di R1 HLT
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)
a partire dall’indirizzo 0.
0004
AA | X: word 0AAAA AA |
BB | Y: word 0BBBB BB |
10 | START: LDWA R1 X ; R1 <- valore della variabile X 20 |
00 | 00 |
20 | LDWA R2 Y ; R2 <- valore della variabile Y 20 |
02 | 00 |
20 | STWA R2 X ; variabile X <- valore di R2 22 |
00 | 00 |
10 | STWA R1 Y ; variabile Y <- valore di R1 22 |
02 | 00 |
00 | HLT CF |
6. (2 punti) Quali di queste informazioni sono contentue nella page table?
[ ] pagina accessibile solo in lettura
[ ] pagina presente/non presente in memoria centrale/nel page file [ ] indirizzo della pagina in memoria centrale o nel page file [ ] indirizzo della segment table
[ ] indirizzo del primo segmento della pagina [ ] indirizzo della linea in memoria centrale [ ] indirizzo della linea in memoria cache [ X] pagina accessibile solo in lettura
[ X] pagina presente/non presente in memoria centrale/nel page file [ X] indirizzo della pagina in memoria centrale o nel page file [ ] indirizzo della segment table
[ ] indirizzo del primo segmento della pagina [ ] indirizzo della linea in memoria centrale [ ] indirizzo della linea in memoria cache
7. (3 punti) Si descriva brevemente il funzionamento di un sistema operativo time-sharing
(per la soluzione si vedano il libro di testo, gli appunti e i lucidi delle lezioni)