HW03: Emulátor 32bitového CPU
Autor zadání Desana Daxnerová
Úprava Samuel Gorta
Odevzdávané soubory cpu.h cpu.c
Začátek odevzdávání viz diskusní fórum
Další odevzdání navíc do 2025-04-09 24:00
Konec odevzdání 2025-04-16 24:00
Vzorová implementace /home/kontr/pb071/hw03/cpu
Kostra úkolu

Představení úkolu

Představme si jednoduchý procesor, který zpracovává aritmetické operace. Náš procesor má k dispozici paměť s instrukcemi, které zpracovává, a zásobník (stack), který se nachází na konci této paměti. Navíc může ukládat mezivýsledky do malé a rychlé paměti – registrů.

Emulátor procesoru postupně čte jednotlivé instrukce z paměti a vykonává je. Naším cílem bude napsat program, který načte soubor s instrukcemi a vytvoří takovýto emulátor, který je vykoná.

Odevzdávat budete pouze soubory cpu.h a cpu.c. V kostře naleznete již naimplementovaný main.c, který otevře vstupní soubor zadaný pomocí argumentu programu a volá vámi dodané funkce. Předpokládaný vstupní soubor s instrukcemi je binární, proto máte v kostře i zdrojový kód programu compiler.c, který můžete použít k převodu textových instrukcí (assembleru) do binární podoby.

Zadání

Naimplementujte funkce z kostry úkolu, které emulují jednoduchý procesor. Přehled jednotlivých funkcí a jejich popis najdete v kapitole Požadavky.

Seznam požadovaných instrukcí a detaily ke vstupním souboru najdete v kapitole Instrukce.

Požadavky

NULL parametr

Pokud není explicitně uvedeno jinak, všechny funkce přebírající argument ukazatelem předpokládají, že tyto ukazatele nejsou NULL. Tuto skutečnost ověřujte makrem assert!

  • Číselné atributy ukládejte do proměnných typu int32_t, který najdete v hlavičkovém souboru stdint.h.

  • Nevyužité atributy všech struktur udržujte na vhodně zvolené hodnotě, tj. čísle 0 nebo ukazateli NULL.

  • Pro dvojici hlavičkového (.h) a implementačního (.c) souboru platí, že pomocí .h zveřejňujete funkce poskytované v .c. Jinými slovy, hlavičkový soubor udává veřejné rozhraní implementačního souboru. V .c samozřejmě můžete (a měli byste) mít jiné pomocné funkce, ty ale už do .h nedoplňujte a označte je klíčovým slovem static (viz příklad níže).

  • Dodržujte požadované rozhraní hlavičkového souboru. Smí obsahovat jen struktury a funkce specifikované v zadání. Některé testy se kompilují s námi dodanými hlavičkovými soubory. Pokud byste tedy upravili hlavičky funkcí nebo přidali nějaké vlastní deklarace, kód se vůbec nemusí zkompilovat!

// Somewhere in a `.c` file...
static int helper_function(void);
...
static int helper_function(void)
{
    return 42;
}

Typ struct cpu

Reprezentuje 32bitový procesor. V rámci tohoto úkolu bude implementován jako tzv. opaque struct, což znamená, že ve veřejném rozhraní (hlavičkovém souboru) se nachází pouze deklarace struktury. Její atributy jsou uvedeny až v implementačním souboru, a tak k nim nelze zvenčí přistupovat bez použití speciálních funkcí.

Náš procesor by měl obsahovat následující části:

  • celočíselné registry A, B, C, D sloužící k ukládání mezivýpočtů,

  • registr status typu enum cpu_status popisující stav procesoru (viz sekce Stavové kódy),

  • registr obsahující aktuální počet uložených hodnot v zásobníku,

  • registr obsahující index instrukce, která má být vykonaná v následujícím kroku výpočtu,

  • ukazatel na paměť emulovaného programu,

  • ukazatele do paměti emulovaného programu, které vymezují prostor, ve kterém se v paměti nachází zásobník.

Struktura paměti

Abychom odlišili kontext paměti programu a paměti emulátoru, budeme adresou nazývat hodnotu proměnné typu ukazatel v jazyce C a indexem (který je číslo, ne ukazatel) budeme nazývat adresu buněk v paměti emulovaného programu. Jedna buňka emulované paměti má velikost jako int32_t v reálné paměti.

Instrukce programu se nachází na začátku paměti. Zásobník se nachází na konci a plnit se bude směrem od konce paměti k začátku. Paměť mezi instrukcemi a zásobníkem (pokud nějaká existuje) musí být vynulovaná.

Indexem instrukce rozumíme počet buněk typu int32_t, které se nachází před ní. Například, pokud program tvoří dvě instrukce a první má jeden operand, pak rozložení indexů bude:

  • index 0: první instrukce

  • index 1: operand první instrukce

  • index 2: druhá instrukce

Vizualizace paměti

memory layout

Funkce na práci s procesorem

Úkol spočívá převážně v implementaci následujících funkcí. Jejich hlavičky se musí nacházet v cpu.h. Abyste strukturu hlavičkových souborů lépe chytili do ruky, necháváme jejich doplnění na vás.

int32_t* cpu_create_memory(FILE *program, size_t stack_capacity, int32_t **stack_bottom);

Funkce přečte binární program pro procesor ze souboru program (například pomocí funkce fgetc(3) z knihovny stdio.h (dokumentace)) a uloží ho do bloku paměti P, kterou naalokuje. Soubor se do paměti zkopíruje až po EOF.

P musí za instrukcemi obsahovat dostatek volného místa pro zásobník velikosti stack_capacity (počet int32_t buněk, ne bajtů). Na adresu, na kterou ukazuje stack_bottom (tj. do *stack_bottom) funkce uloží adresu posledního prvku (typu int32_t) v P, se kterým je ještě možné pracovat. Vrátí ukazatel na začátek P, nebo NULL při chybě. Za chybu se také považuje případ, kdy počet bajtů ve vstupním souboru není násobkem velikosti typu int32_t.

Velikost vstupu nemusí být dopředu známa, proto je třeba paměť dle potřeby zvětšovat. Aby nebyla alokace paměti zbytečně neefektivní, musí tato funkce alokovat paměť po blocích velikosti 4 KiB.

Soubor můžete přečíst jen jednou. Nepředpokládejte, že program reprezentuje regulární soubor, tj. funkce ftell(3) a fseek(3) nemusí na program dávat smysl. 
struct cpu *cpu_create(int32_t *memory, int32_t *stack_bottom, size_t stack_capacity);

Funkce inicializuje strukturu cpu. Parametr memory ukazuje na paměť emulovaného programu, který přečetla funkce cpu_create_memory().

Atribut stack_bottom je parametr, který se získá voláním cpu_create_memory(…​, &stack_bottom). Je v pořádku, pokud není mezi instrukcemi a zásobníkem volné místo.

Funkce vrací ukazatel na inicializovanou strukturu cpu, který lze předat jako parametr do následujících funkcí.

int32_t cpu_get_register(struct cpu *cpu, enum cpu_register reg);

Vrátí hodnotu registru (A až D). Validitu parametru reg ověřte pomocí makra assert.

void cpu_set_register(struct cpu *cpu, enum cpu_register reg, int32_t value);

Nastaví registr (A až D) na hodnotu value. Validitu parametru reg ověřte pomocí makra assert.

enum cpu_status cpu_get_status(struct cpu *cpu);

Vrátí stavový kód procesoru.

int32_t cpu_get_stack_size(struct cpu *cpu);

Vrátí aktuální velikost zásobníku.

void cpu_destroy(struct cpu *cpu);

Uvolní zdroje procesoru a nastaví ukazatele ve struktuře na NULL. Také vynuluje všechny registry.

void cpu_reset(struct cpu *cpu);

Vynuluje všechny registry (včetně status) a vyprázdní a vynuluje zásobník. Nedealokuje žádnou paměť.

Pro cpu_step() a cpu_run() platí, že dokud je stavový kód procesoru jiný, než CPU_OK, vrátí 0 a nedělají nic jiného. 
int cpu_step(struct cpu *cpu);

Vykoná jednu instrukci procesoru. Pokud je úspěšná, vrátí nenulový kód, jinak vrátí 0.

long long cpu_run(struct cpu *cpu, size_t steps);

Vykoná steps instrukcí. Vrátí -K, pokud se procesor dostal vykonáním K kroků do chybového stavu, jinak vrátí skutečný počet vykonaných instrukcí. Ten může být menší než steps, pokud došlo k vykonání instrukce halt.

Například pro následující program:

movr C 42 ; Make loop jump.
loop -112 ; Jump to an invalid address.

Funkce cpu_run nejdřív úspěšně vykoná movr, potom úspěšně vykoná loop, následně se při vykonávání následující (neexistující, ale to nevadí) "instrukce" stane chyba kvůli záporné hodnotě instruction_pointer – dohromady 3 kroky. Funkce tedy vrátí -3.

Instrukce

Instrukce jsou v binárním souboru, stejně jako v paměti programu, reprezentované jako 32bitové čísla. Můžou mít (32bitové) parametry typu REG (číslo registu 0 (A) až 3 (D)), INDEX (index intrukce) a NUM (celé číslo). Endianita instrukcí a operandů je little-endian.

Stavové kódy

Instrukce můžou v jistých případech nastavovat stavový kód. V kostře se nachází enum cpu_status s následujícími hodnotami (v pořadí):

  • CPU_OK,

  • CPU_HALTED,

  • CPU_ILLEGAL_INSTRUCTION,

  • CPU_ILLEGAL_OPERAND,

  • CPU_INVALID_ADDRESS,

  • CPU_INVALID_STACK_OPERATION,

  • CPU_DIV_BY_ZERO,

  • CPU_IO_ERROR.

Kromě CPU_OK a CPU_HALTED jsou všechny ostatní stavy chybové. Pro vykonání všech instrukcí platí:

  • Pokud je stavový kód emulátoru jiný než CPU_OK, instrukce se nevykoná.

  • Pokud je kód instrukce neznámý, nastaví se kód CPU_ILLEGAL_INSTRUCTION.

  • Pokud je registr instrukce neznámý, nastaví se kód CPU_ILLEGAL_OPERAND.

  • Pokud je index instrukce v registru mimo paměť emulovaného programu, nebo ukazuje do zásobníku, nastaví se kód CPU_INVALID_ADDRESS.

  • Pokud během vykonávání instrukce nastane chyba, index instrukce v registru se nemění.

Počáteční status procesoru je ve funkci cpu_create inicializován na CPU_OK.

Seznam instrukcí

Číselné hodnoty instrukcí jsou definované pořadím v tomto seznamu.

  1. nop: Nedělá nic.

  2. halt: Zastaví vykonávání programu a nastaví stav procesoru na CPU_HALTED. Funkce cpu_step() po jejím vykonání vrátí 0.

  3. add REG: Připočítá k registru A hodnotu registru REG.

  4. sub REG: Odečte z registru A hodnotu registru REG.

  5. mul REG: Vynásobí registr A hodnotou registru REG.

  6. div REG: Vydělí registr A hodnotou registru REG. Pokud je jeho hodnota 0, instrukci nevykoná a nastaví stavový kód na CPU_DIV_BY_ZERO.

  7. inc REG: Inkrementuje registr REG.

  8. dec REG: Dekrementuje registr REG.

  9. loop INDEX: Pokud je registr C nenulový, skočí na instrukci s indexem INDEX, jinak neudělá nic.

  10. movr REG NUM: Uloží do registru REG číslo NUM.

  11. load REG NUM: Uloží do registru REG číslo ze zásobníku, které se v něm nachází na indexu D + NUM od konce. Tedy pokud jsou registr D i NUM rovny nule, uloží se do registru hodnota na vrcholu zásobníku (tj. poslední vložená). Aktuální velikost zásobníku zůstává nezměněná. V případě, že je D + NUM index mimo zaplněnou část zásobníku, operace se nevykoná a nastaví se stavový kód CPU_INVALID_STACK_OPERATION.

  12. store REG NUM: Funguje podobně jako load, ale hodnotu na zásobník ukládá, tedy hodnotu z registru REG vloží na index D + NUM od konce. Aktuální velikost zásobníku zůstává nezměněná. V případě neplatného indexu se nastaví stavový kód CPU_INVALID_STACK_OPERATION stejně jako u load.

  13. in REG: Přečte ze vstupu 32bitové číslo (sekvenci číslic v desítkové soustavě) a uloží ho do registru REG. Pokud byty (znaky) na vstupu nereprezentují číslo, instrukce nic neudělá a nastaví stav procesoru na CPU_IO_ERROR. Pokud na vstupu už žádná čísla nejsou (EOF), nastaví registr C na 0 a do REG uloží hodnotu -1 (a to i v případě, že REG je C). Instrukce ignoruje bílé znaky, kterými čísla na vstupu mohou být oddělená.

  14. get REG: Přečte ze vstupu jeden znak (byte) a uloží jej do registru REG. V případě, že na vstupu už žádné byty nejsou (EOF), chová se instrukce jako in.

  15. out REG: Vypíše hodnotu registru REG jako číslo na standartní výstup. Výstup této instrukce je pouze sekvence znaků '0' – '9' (a případně '-' u záporných hodnot).

  16. put REG: Pokud je hodnota registru REG v rozsahu 0 – 255, vypíše tuto hodnotu jako právě jeden znak na standartní výstup. Jinak neudělá nic a nastaví stavový kód na CPU_ILLEGAL_OPERAND.

  17. swap REG REG: Vymění hodnoty registrů.

  18. push REG: Přidá hodnotu registru REG na zásobník, pokud není plný. Jinak neudělá nic a nastaví stavový kód CPU_INVALID_STACK_OPERATION. Instrukce upravuje aktuální velikost zásobníku.

  19. pop REG: Pokud je na zásobníku alespoň jeden prvek, odebere jej a jeho hodnotu uloží do registru REG. Jinak neudělá nic a nastaví stavový kód CPU_INVALID_STACK_OPERATION. Instrukce upravuje aktuální velikost zásobníku.

Instrukce in a get v případě EOF vynulují registr C, aby při čtení vstupu v cyklu (instrukcí loop) způsobilo EOF ukončení cyklu.

Assembler

Programy pro procesor můžete napsat v textové podobě – assembleru, a ten si následně zkompilovat pomocí kompilátoru v souboru compiler.c z kostry nebo pomocí referenční implementace.

compiler.c obsahuje POSIXovou funkci getline(3), díky které nejde zkompilovat na Windows. Na tomto operačním systému je třeba provést kompilaci ve WSL nebo na Aise.

Assembler může obsahovat kromě instrukcí i deklaraci návěstí (alfanumerický ASCII identifikátor začínající písmenem a končící dvojtečkou, např. here:). Instrukce, které berou argument typu INDEX, můžou použít místo číselné konstanty tyto návěstí.

Na každém řádku se může nacházet nejvíce jedna instrukce, která je od svých operandů oddělená právě jednou mezerou. Před a za ní může být libovolný počet mezer. Komentáře začínají znakem ;.

Do kostry jsme vám do adresáře assembler_inputs přiložili pár programů, kterými se můžete inspirovat při psaní vlastních.

Příklad

Assembler:

; simple homework assembly excercise
  dec 1     ; Decrement register B, same as `dec B`.
  loop here ; Same as loop 6.
  push 0
here:
  halt

Binární soubor (hodnota v prvním sloupci – index se v souboru nenachází, slouží jen pro názornější ukázku):

index  1  2  3  4    význam
0      07 00 00 00   ( 7) dec
1      01 00 00 00             (operand registr B)
2      08 00 00 00   ( 8) loop
3      06 00 00 00   ( 6)      (operand index 6)
4      11 00 00 00   (17) push
5      00 00 00 00   ( 0)      (operand registr A)
6      01 00 00 00   ( 1) halt

Rozhraní v příkazovém řádku

Tato část je implementovaná v kostře.

Program akceptuje dva až tři argumenty: první je run nebo trace, druhý, nepovinný, je stack_capacity, poslední je cesta k souboru s instrukcemi. run vykoná všechny instrukce a vypíše stav CPU, trace vypíše stav po každé instrukci a počká na Enter před vykonáním další.

Bonusové rozšíření

Instrukce skoků [5 bodů]

Kód související s touto rozšířenou instrukční sadou obalte příkazy preprocesoru (každý na samostatném řádku). Pro účely testování přidejte k přepínačům překladače (pro CMake obsah proměnné CMAKE_C_FLAGS) přepínač -DBONUS_JMP.

#ifdef BONUS_JMP
    // Bonus code.
#endif // BONUS_JMP

Rozšiřte struct cpu o registr result, který bude obsahovat výsledek poslední aritmetické operace (add, sub, mul, div, inc, dec) nebo operace cmp.

Rozšiřte všechny relevantní funkce o registr result. Tento registr bude jako operand dostupný pod indexem 4.

Instrukční sadu rozšiřte o následující instrukce:

  1. cmp REG_X REG_Y: Do registru result zapíše REG_X - REG_Y. Hodnoty registrů REG_X ani REG_Y se nezmění.

  2. jmp INDEX: Skočí na INDEX.

  3. jz INDEX: Skočí na INDEX, pokud se result rovná nule.

  4. jnz INDEX: Skočí na INDEX, pokud result není nula.

  5. jgt INDEX: Skočí na INDEX, pokud je result striktně větší než nula.

Do registru result zároveň uloží svůj výsledek všechny aritmetické operace (např. add do result zkopíruje konečnou hodnotu A, inc do result zkopíruje hodnotu operandu po jeho inkrementaci apod.). Ostatní instrukce (např. load, swap, in) můžou tento registr pouze číst. Při pokusu o zápis procesor nastaví stavový kód CPU_ILLEGAL_OPERAND.

Procedury [5 bodů]

Tento bonus povolte makrem BONUS_CALL:

#ifdef BONUS_CALL
    // Bonus code.
#endif // BONUS_CALL

  1. call INDEX: Pokud je na zásobníku dost místa, uloží na něm index následující instrukce a skočí na INDEX. Jinak nastaví stavový kód na CPU_INVALID_STACK_OPERATION.

  2. ret: Vybere z vrcholu zásobníku index instrukce (kterou, pokud byl program korektně napsaný, tam vložila instrukce call) a skočí na ni. Pokud je zásobník prázdný, nastaví stavový kód CPU_INVALID_STACK_OPERATION.

Pokud se rozhodnete implementovat jen druhý bonus, ujistěte se, že má instrukce call ve vašem řešení stejný kód, jaký by měla, pokud by existovaly i instrukce cmp a jgt!

Poznámky

  • Program kompilujte příkazem

    gcc -o hw03 main.c cpu.c -std=c99 -Wall -Wextra -Werror -pedantic

  • Vzorové řešení můžete spustit na aise:

    /home/kontr/pb071/hw03/compiler
/home/kontr/pb071/hw03/cpu
/home/kontr/pb071/hw03/cpu-bonus

  • POZOR! Vzorové řešení vyžaduje argument!

  • Nezapomínejte na vhodnou dekompozici. Vyrobte si pomocné funkce, kde třeba.

Během psaní řešení vás to možná bude svádět k vytvoření obrovského switch. Ten nepotěší vaše opravující a práce s ním bude zbytečně pracná. Zkuste využít znalosti z přednášek a než začnete psát, zamyslete se nad správným návrhem vašeho řešení.