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