Zadanie z laboratorium programowania na Informatyce UW.
Zadanie 17 (termin wysylania rozwiazan: 9 czerwca 2008, godz. 23:59)
(Procesor)
Zrealizuj symulator pewnego procesora. Ma on wczytac z wejscia jeden wiersz
zawierajacy program dla procesora, a nastepnie wykonac go, wczytujac
ewentualne dane z wejscia oraz wypisujac wyniki na wyjscie.
Procesor ma 10 rejestrow 10 bitowych przechowujacych wartosci calkowite w
kodzie U2 oraz dwa jednobitowe znaczniki mowiace o tym, czy wynik ostatniej
operacji byl ujemny oraz czy byl zerem. W chwili rozpoczecia rejestry sa
wyzerowane, znacznik "zero" ustawiony jest na true, a "minus" na false.
Program na nasz procesor jest reprezentowany przez ciag znakow (napis).
Kazda z 10 rozpoznawanych przez procesor instrukcji ma swoj jednoliterowy
kod, po ktorym podajemy od 0 do 2 jednoznakowych argumentow.
Ponizej znajduje sie lista instrukcji wraz z opisem znaczenia. W opisie tym
R oraz S oznaczaja numer rejestru ('0'..'9'), D oznacza liczbe skladajaca
sie z jednej cyfry dziesietnej a NN to dwucyfrowy zapis liczby calkowitej,
w ktorym pierwsza cyfra (dziesietna) jest bardziej znaczaca, a druga mniej.
rR (read) - wczytanie z wejscia liczby do rejestru R
wR (write) - wypisanie na wyjscie zawartosci wiersza R
aRS (add) - R=R+S
cRS (copy) - R=S
nR (negate) - R=-R
lRD (load) - R=D
jNN (jump) - goto NN
mNN (jump if minus) - if(minus) goto NN
zNN (jump if zero) - if(zero) goto NN
d (dump) - wypisuje zawartosc rejestrow
Znaczniki "minus" i "zero", wykorzystywane w instrukcjach skoku warunkowego
'm' i 'z' sa aktualizowane po kazdej instrukcji, ktora przyjmuje jako
argument przynajmniej jeden rejestr (czyli po 'r' 'w' 'a' 'c' 'n' 'l') na
podstawie wartosci, ktora znalazla sie w tym rejestrze (gdy argumentem sa
dwa rejestry, znaczniki opisuja zawartosc pierwszego z nich).
Program podczas dzialania procesora jest przechowywany w pamieci. Komorki
pamieci sa adresowane kolejnymi liczbami naturalnymi zaczynajac od 1. Kazda
instrukcja zajmuje w pamieci od 1 do 3 komorek, np. instrukcja 'd' zajmuje
jedna komorke, 'r0' dwie a 'c01' trzy.
Wykonanie programu rozpoczyna sie od instrukcji znajdujacej sie pod adresem 1,
konczy sie, gdy kolejnej instrukcji, ktora mielibysmy wykonac, w programie nie
ma.
Oto przyklady programow:
r0r1r2w2w1w0
wczytuje trzy liczby i wypisuje je w kolejnosci odwrotnej,
r0r1c20a21c31n3a30l41a40d
wczytuje dwie liczby, oblicza ich sume, roznice i dodaje 1 do pierwszej
liczby, na koniec pokazuje zawartosc rejestrow,
r0w0l11n1a01z99j03
wczytuje liczbe n>0 i wypisuje n..1,
r0r1c20c31n3a23z36m28c02j05c12n1j05w0
wczytuje dwie liczby i wypisuje ich najwiekszy wspolny dzielnik,
r0r1r2c31c40n4a34z44w2c32a34z37w0j57w1w0j99c32a34z99w0w2w1
wczytuje trzy liczby i wypisuje je tak, by rowne ze soba nie sasiadowaly.
Jesli to niemozliwe, nie wypisuje nic.
Postac danych:
Na wejsciu znajduje sie wiersz z programem (maksymalnie 100 znakow) oraz, w
kolejnych wierszach, liczby bedace danymi dla symulowanego programu (po jednej
w wierszu).
Postac wyniku:
Na wyjsciu powinien sie pojawic efekt wykonania instrukcji 'w' i 'd'.
Instrukcja 'w' wypisuje w zapisie dziesietnym (chodzi o zwykle uzycie funkcji
"printf" z pierwszym argumentem "%dn"), w pojedynczym wierszu, wartosc
argumentu. Instrukcja 'd' wypisuje zawartosc rejestrow. Dla kazdego z
dziesieciu rejestrow wypisujemy po jednym wierszu zawierajacym najpierw 10
cyfr binarnych wartosci przechowywanej w tym rejestrze (w kolejnosci od
najbardziej znaczacych), nastepnie jedna spacje oraz zapis dziesietny tej
wartosci.
A oto rozwiązanie:
#include
#include
#include
int rejestry[10][10];
char program[100];
int minus;
int zero;
//Najpierw funkcje pomocnicze dla kodu binarnego.
int rozkoduj (int rejestr)
{
//U2 na int
int i,wynik,mnoznik;
//dla ujemnego bitu:
if (rejestry[rejestr][0]==1)
{
wynik=-512;
}
else
{
wynik=0;
}
mnoznik=256;
//9 razy:
for (i=1;i<10;i++)
{
if(rejestry[rejestr][i]==1)
{
wynik=wynik+mnoznik;
}
mnoznik=mnoznik/2;
}
return wynik;
}
void zakoduj (int liczba,int rejestr)
{
//koduje int na rejestr.
int i,mnoznik;
//na poczatku dla ujemnego bitu:
if (liczba<0)
{
liczba=liczba+512;
rejestry[rejestr][0]=1;
}
else
{
rejestry[rejestr][0]=0;
}
mnoznik=256;
//9 razy:
for (i=1;i=mnoznik)
{
//ta liczba jest w rozkladzie.
rejestry[rejestr][i]=1;
liczba=liczba-mnoznik;
}
else
{
rejestry[rejestr][i]=0;
}
mnoznik=mnoznik/2;
}
}
void ustaw_flagi(int rejestr)
{
int zawartosc;
zawartosc=0;
zawartosc=rozkoduj(rejestr);
if(zawartosc==0)
{
zero=1;
minus=0;
}
else if(zawartosc>0)
{
zero=0;
minus=0;
}
else
{
zero=0;
minus=1;
}
}
//Teraz funkcje realizujace instrukcje.
int read_p(int instrukcja)
{
int rejestr,wynik;
int liczba;
//wczytuje znak do odpowiedniego rejestru
rejestr=program[instrukcja+1]-'0'; // w programie sa char'y
wynik=scanf("%d",&liczba);
if(wynik>0)
{
//przepisujemy liczbe na rejestr;
zakoduj(liczba,rejestr);
ustaw_flagi(rejestr);
return instrukcja+2;
}
else
{
return -1;
}
}
int write_p(int instrukcja)
{
int rejestr;
int liczba;
//wypisuje
rejestr=program[instrukcja+1]-'0'; // w programie sa char'y
liczba=rozkoduj(rejestr);
ustaw_flagi(rejestr);
printf("%dn",liczba);
return instrukcja+2;
}
int load(int instrukcja)
{
int rejestr;
int liczba;
//wczytuje znak do odpowiedniego rejestru
rejestr=program[instrukcja+1]-'0'; // w programie sa char'y
liczba=program[instrukcja+2]-'0';
if((liczba>=0)&&(liczba<=9))
{
//przepisujemy liczbe na rejestr;
zakoduj(liczba,rejestr);
ustaw_flagi(rejestr);
return instrukcja+3;
}
else
{
return -1;
//Blad - podano nie liczbe
}
}
int dump(int instrukcja)
{
int i,j;
//wyrzuca rejestry.
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
printf("%d",rejestry[i][j]);
}
printf(" %dn",rozkoduj(i));
}
return instrukcja+1;
}
int jump(int instrukcja)
{
int go,teraz,i;
go=(program[instrukcja+1]-'0')*10 +(program[instrukcja+2]-'0');
//szukamy go-tej instrukcji.
go+=-1;//bo w opisie numerowane od 1
teraz=0;
i=0;
while((teraz<100)&&(i<go))
{
if(program[teraz]=='d')
{
teraz+=1;
}
else if((program[teraz]=='r')||(program[teraz]=='w')||(program[teraz]=='n'))
{
teraz+=2;
}
else
{
teraz+=3;
}
i++;
}
if(i==go)
{
//znalezlismy
return teraz;
}
else
{
return -1;
//Nie ma tej instrukcji.
}
}
int jump_minus(int instrukcja)
{
if(minus)
{
return jump(instrukcja);
}
else
{
return instrukcja+3;
}
}
int jump_zero(int instrukcja)
{
if(zero)
{
return jump(instrukcja);
}
else
{
return instrukcja+3;
}
}
// no i tylko funkcje matematyki binarnej.
int copy(int instrukcja)
{
int i,rejestr1,rejestr2;
rejestr1=program[instrukcja+1]-'0';
rejestr2=program[instrukcja+2]-'0';
for(i=0;i0;i+=-1)
{
rejestry[rejestr1][i]+=rejestry[rejestr2][i];
rejestry[rejestr1][i]+=przeniesienie;
przeniesienie=0;
//przeniesienie;
if(rejestry[rejestr1][i]>1)
{
przeniesienie=1;
rejestry[rejestr1][i]+=-2;
}
}
//bit znaku:
rejestry[rejestr1][i]+=rejestry[rejestr2][i];
rejestry[rejestr1][i]+=przeniesienie;
if(rejestry[rejestr1][i]>1)
{
if(!przeniesienie)
{
//przepelnienie
return -1;
}
else
{
rejestry[rejestr1][i]+=-2;
ustaw_flagi(rejestr1);
return instrukcja+3;
}
}
else
{
ustaw_flagi(rejestr1);
return instrukcja+3;
}
}
int negate(int instrukcja)
{
int i,rejestr,przeniesienie;
rejestr=program[instrukcja+1]-'0';
//inwersja bitow
for(i=0;i1)
{
przeniesienie=1;
rejestry[rejestr][i]+=-2;
}
i=i-1;
}
ustaw_flagi(rejestr);
return instrukcja+2;
}
int main (int argc, char *argv[])
{
int i,j,k,wynik;
char znak;
zero=0;
minus=0;
for(k=0;k<10;k++)
{
for(j=0;j<10;j++)
{
rejestry[k][j]=0;
}
}
//zainicjowane.
wynik=scanf("%c",&znak);
k=0;
while((wynik!=EOF)&&(k<100)&&(znak!='n')&&(znak!='r'))
{
program[k]=znak;
wynik=scanf("%c",&znak);
k++;
}
while(k<100)
{
program[k]=' ';
k++;
}
k=0;
//Wczytujemy
if(wynik!=EOF)//jesli nie bylo programu
{
i=0;
while(i<100)
{
if(i==-1)
{
//byl blad.
break;
}
else
{
switch (program[i])
{
case 'r':
i=read_p(i);
break;
case 'w':
i=write_p(i);
break;
case 'a':
i=add(i);
break;
case 'c':
i=copy(i);
break;
case 'n':
i=negate(i);
break;
case 'l':
i=load(i);
break;
case 'd':
i=dump(i);
break;
case 'j':
i=jump(i);
break;
case 'm':
i=jump_minus(i);
break;
case 'z':
i=jump_zero(i);
break;
default:
i=-1;
break;
}
}
}
}
else
{
//Szwindel. Nie bylo znakow.
return 1;
}
return 0;
}