====== 3. Základní struktura procesoru, instrukční soubor ======

  * pro vyučující: [[..:..:internal:tutorials:03:start|cvičení 3]]

===== Osnova cvičení =====

  - Význam a použití základních instrukcí
  - Seznámení se s vývojovým a simulačním prostředím (programy MipsIt a Mips) a simulace vykonávání jednoduchého programu
  - Přepis programu z jazyka C do asembleru (instrukční sada MIPS)
  - Upozornění na 1. domácí úkol ([[https://dcenet.felk.cvut.cz/apo/]])

===== Náplň cvičení =====
První část - Význam a použití základních instrukcí 

Bližší popis instrukcí:
^ Instrukce ^ Syntax ^ Operace ^ Význam ^
| add   | <nowiki>add \$d, \$s, \$t</nowiki>   | <nowiki>\$d = \$s + \$t;</nowiki>   | Add: Sečte dva registry <nowiki>\$s + \$t</nowiki> a výsledek uloží do registru <nowiki>\$d</nowiki> |
| addi   | <nowiki>addi \$t, \$s, C</nowiki>   | <nowiki>\$t = \$s + C;</nowiki>   | Add immediate: Sečte hodnotu v <nowiki>\$s</nowiki> a znaménkově rozšířenou přímou hodnotu, a výsledek uloží do <nowiki>\$t</nowiki> |
| sub   | <nowiki>sub \$d,\$s,\$t</nowiki>       | <nowiki>\$d = \$s - \$t</nowiki>   | Subtract: Odečte znaménkově obsah registru <nowiki>\$t</nowiki> od <nowiki>\$s</nowiki> a výsledek uloží do <nowiki>\$d</nowiki> |
| bne   | <nowiki>bne \$s, \$t, offset</nowiki>   | <nowiki>if \$s != \$t go to PC+4+4*offset; else go to PC+4</nowiki>   | Branch on not equal: Skáče pokud si registry <nowiki>\$s</nowiki> a <nowiki>\$t</nowiki> nejsou rovny |
| beq   | <nowiki>beq \$s, \$t, offset</nowiki>   | <nowiki>if \$s == \$t go to PC+4+4*offset; else go to PC+4</nowiki>   | Branch on equal: Skáče pokud si registry <nowiki>\$s</nowiki> a <nowiki>\$t</nowiki> jsou rovny |
| slt | <nowiki>slt \$d,\$s,\$t</nowiki> | <nowiki>\$d = (\$s < \$t)</nowiki> | Set on less than: Nastavi registr <nowiki>\$d</nowiki>, pokud plati podminka <nowiki>\$s < \$t</nowiki>  |
| sll | <nowiki>sll \$d,\$s,C</nowiki> | <nowiki>\$d = \$s << C</nowiki> | Shift Logical Left: Posune hodnotu v registru o C bitu doleva (ekvivalentni k operaci nasobeni konstantou 2<sup>C</sup> )  |
| jump  | <nowiki>j C</nowiki>                 | <nowiki>PC = (PC ∧ 0xf0000000) ∨ 4*C</nowiki> | Jump:  Skáče bezpodmíněčně na návěstí C |
| lw    | <nowiki>lw \$t,C(\$s)</nowiki>     | <nowiki>\$t = Memory[\$s + C]</nowiki> | Load word: Načte slovo z paměti a uloží jej do registru <nowiki>\$t</nowiki> |
| sw    | <nowiki>sw \$t,C(\$s)</nowiki>     | <nowiki>Memory[\$s + C] = \$t</nowiki> | Store word: Uloží obsah registru <nowiki>\$t</nowiki> do paměti |
| lui  | <nowiki>lui \$t,C</nowiki> | <nowiki>\$t = C << 16</nowiki> | Load upper immediate: Uloží předanou přímou hodnotu C do horní části registru. Registr je 32-bitový, C je 16-bitová. |
| la   | <nowiki>la \$at, LabelAddr</nowiki>     | <nowiki>lui \$at, LabelAddr[31:16]; \\ ori \$at,\$at, LabelAddr[15:0]</nowiki> | Load Address: 32-bitové návěstí uloží do registru <nowiki>\$at</nowiki>. Jedná se o pseudoinstrukci - tzn. při překladu se rozloží na dílčí instrukce. |

\\ 

----
\\ 
Druhá část - Seznámení se s vývojovým a simulačním prostředím (programy MipsIt a Mips) a simulace vykonávání jednoduchého programu 



==== Vývoj s Makefile ====
Pro psaní vlastního programu v asembleru a následné generování výstupního souboru pro simulátor Mips lze použít oblíbený textový editor (například [[http://www.geany.org/|Geany]]) a nástroj //make//.

===Makefile===
[[https://en.wikipedia.org/wiki/Make_%28software%29|Make]] je nástroj pro automatickou kompilaci zdrojových kódů, potřebná konfigurace je uložena v souboru //Makefile//.

//Makefile// šablona:
<code>
ARCH=mips-elf

CC=$(ARCH)-gcc
AS=$(ARCH)-as
LD=$(ARCH)-ld
OBJCOPY=$(ARCH)-objcopy

CFLAGS  += -ggdb -O1
AFLAGS  += -ggdb
LDFLAGS += -ggdb
LDFLAGS += -nostdlib -nodefaultlibs -nostartfiles
LDFLAGS += -Wl,-Ttext,0x80020000

all:default

.PHONY:clean

%.srec:%
        $(OBJCOPY) -O srec $< $@

%.out:%
        $(OBJCOPY) -O ecoff-bigmips $< $@

%.o:%.S
        $(CC) -D__ASSEMBLY__ $(AFLAGS) -c $< -o $@

%.s:%.c
        $(CC) $(CFLAGS) $(CPPFLAGS) -S $< -o $@

%.o:%.c
        $(CC) $(CFLAGS) $(CPPFLAGS) -c $< -o $@

# default output
default:change_me.srec

# executable file:object file.o
change_me:change_me.o
        $(CC) $(LDFLAGS) $^ -o $@

# all generated that would be cleaned
clean:
        rm -f change_me change_me.o change_me.out change_me.srec
</code>

<note important>
Odsazení řádku v Makefile musí být pomocí **tabulátoru**. Makefile nerozezná odsazení pomocí mezer.
</note>
===Zdrojový kód===
Zdrojový kód napsaný v asembleru se dle konvence ukládá do souboru s koncovkou //.S//, pro vlastní program lze použít následující šablonu:
<code>
#define t0 $8
#define t1 $9
#define t2 $10

#define s0 $16
#define s1 $17
#define s2 $18

.globl start
.set noat
.ent start

start:
// Zde je místo pro Váš vlastní kód...

nop
.end start
</code>

===Ukázka===
Pro ukázku si můžete zkusit napstat krátký program, který sečte dvě čísla uložená v registrech s0 a s1, a výsledek uloží do registru s2.
<code>
addi s0, $0, 0x15
addi s1, $0, 0x45
add  s2, s0, s1
</code>
\\ 
Klíčová slova .globl, .data, .text, .word jsou pseudoinstrukce překladače
assembleru. Podrobný popis lze nalézt v dokumentaci
([[http://sourceware.org/binutils/docs/as/index.html|GNU Assembler Manual]]).

===Kompilace===
Kompilace probíhá příkazem //make// (příkaz //make// je nutné zadávat v adresáři, ve kterém je upravený Makefile a zdrojový kód programu). //Make// vygeneruje několik souborů, z nichž pro import do simulačního prostředí Mips použijeme ten s koncovkou //.srec//.
==== Vývojové prostředí MipsIt ====
Tento program budeme používat pro psaní vlastního programu v asembleru a následné generování výstupního souboru pro simulátor Mips, MipsPipeS a MipsPipeXL (dnes budeme používat jenom simulátor Mips). 

**Letní semestr 2018**:\\
V nabídce

  Applications -> Development vybereme MipsIt

  Applications -> Development vybereme MipsIt-MIPS
  
-----

Letní semestr 2017:
  /opt/wine/bin/wine /opt/mipsit/bin/MipsIt.exe

  /opt/wine/bin/wine /opt/mipsit/bin/Mips.exe
  
-----

V prostředí učebny KNE:328 (letní semestr 2016):\\
Na instalaci **Ubuntu APO** se prostředí a ikonky na desktopu nastaví příkazem

<code>
mipsit-setup
</code>

V případě, že již je prostředí nastavené, tak lze provést jeho kompletní reset.
**POZOR** příkaz způsobí smazání veškerých dat ve složce ~/.wine. To zahrnuje i veškeré projekty v prostředí MipsIT, pokud jsou ukládané do standardní/nezměněné složky

<code>
mipsit-setup force
</code>

-----

=== 1. Vytvoření nového projektu ===
Úvodní obrazovka po spuštění programu:

{{courses:B35APO:tutorials:03:01mipsit.png?400|}}
\\ 
\\ 
Postupujeme v těchto krocích: File -> New -> karta Project,\\ 
kde vybereme Assembler, vyplníme jméno vytvářeného projektu a zvolíme umístění \\ 
Dále pak: File -> New -> karta File,\\ 
kde vybereme Assembler, vyplníme jméno souboru a zkontrolujeme zda máme zaškrtnuto "Add to project"
\\ 
=== 2. Psaní vlastního programu ===
Do nově otevřeného okna (s příponou *.s) pak píšeme vlastní program: \\ 
{{courses:B35APO:tutorials:03:02mipsit.png?400|}}
\\ 
\\ 
K tomuto účelu můžeme využít připravenou šablonu:\\ 
<code>
#define t0 $8
#define t1 $9
#define t2 $10

#define s0 $16
#define s1 $17
#define s2 $18

.globl start
.set noat
.ent start

start:
// Zde je místo pro Váš vlastní kód...

nop
.end start
</code>
\\ 
\\ 
Pro ukázku si můžete zkusit napstat krátký program, který sečte dvě čísla uložená v registrech s0 a s1, a výsledek uloží do registru s2.
<code>
addi s0, $0, 0x15
addi s1, $0, 0x45
add  s2, s0, s1
</code>
\\ 
Klíčová slova .globl, .data, .text, .word jsou pseudoinstrukce překladače
assembleru. Podrobný popis lze nalézt v dokumentaci
([[http://sourceware.org/binutils/docs/as/index.html|GNU Assembler Manual]]).

=== 3. Kompilace ===
Projekt přeložíme výběrem v menu: Build -> Build xx, kde xx je jméno Vašeho projektu. Alternativou je klávesa F7. Vygenerují se tři soubory s příponou *.o, *.out a *.sreg umístěné v podadresáři Objects aktuálního pracovního adresáře projektu. Při správném postupu by měla být obrazovka programu (výpis v okně "Output") nasledující: \\

{{courses:B35APO:tutorials:03:03mipsit.png?400|}} 
\\
\\
Důležitá poznámka: Nikde v cestě nesmí být mezera. Pokud nefunguje překlad projektu je zapotřebí zkontrolovat cestu k projektu (a/nebo také: File -> Options -> karta Directories, a zde cesty pro: Executable files, Include files a Library files.
\\ 
\\ 

==== Simulační prostředí Mips ====
Tento program budeme používat pro simulaci vykonávání napsaného programu - sledování (krokování) vykonávání programu a ověření jeho funkčnosti.

=== 1. Otevření souboru pro simulaci a příprava ===
Úvodní obrazovka po spuštění programu: 

{{courses:B35APO:tutorials:03:01_mips.png?400|}}

\\
\\ 
Soubor vygenerovaný programem MipsIt (s příponou *.srec nebo *.out) načteme cez: File -> Open. Dále pak zobrazíme pracovní registry procesoru (View -> Register) a paměť programu (View -> Memory). 

=== 2. Simulace ===
Po vykonání výše uvedeného postupu a odkrokování programu (Cpu -> Step nebo klikáním na ikonu {{courses:B35APO:tutorials:03:step.png?18|}}) dostaneme:

{{courses:B35APO:tutorials:03:03_mips.png?804|}}

\\ 
Upozornění: Před opakovaným načtením souboru *.out nebo *.sreg je zapotřebí nejdřív zresetovat procesor: Cpu -> Reset. Po každém zresetováni procesoru je zapotřebí soubor *.out nebo *.sreg načíst znovu. Okno pro vykreslování paměti (to žluté) má problémy s překreslováním - pokud se obsah paměti modifikuje instrukcemi sw nemusí být zápis vidět. Postačí jej na chvíli překrýt jiným oknem.
\\ 

=== 3. Opětovné načtení kódu do spuštěného simulátoru ===

Pokud je již některý ze simulátorů Mips.exe, MipsPipeS.exe
nebo MipsPipeXL.exe spuštěný, lze kód do simulátoru načíst
z prostředí MipsIT.exe aktivací položky 

   Build -> Upload -> To Simulator (F5)

Volba zároveň provede inicializaci CPU do počátečního stavu.

-------
\\ 
Třetí část cvičení 

==== Přepis programu z jazyka C do asembleru ====
V praktických aplikacích se častokrát setkáváme s použitím mediánového filtru. Ten nám pomáhá odstranit ze signálu (nebo obrazu) zcela zjevné výkmity (nebo poškozené pixely). Narozdíl od průměrovacího filtru, který spočítá aritmetický průměr nejakého okolí a stávající hodnotu signálu nahradí vypočteným průměrem, mediánový filtr ji nahradí prostřední hodnotou (mediánem) tohoto okolí. Pro realizaci mediánového filtru je potřebné nejdříve seřadit všechny hodnoty a pak z nich vybrat onu prostřední. Klíčovou roli zde sehrává řazení. Mějme následující problém. V datové paměti nech je uloženo N celých čísel (1 < N < 21) počínaje od nějaké adresy (například 0x00), přičemž jedno číslo v paměti zabírá velikost jednoho slova. Našim úkolem je uvedená čísla vzestupně seřadit. Nejsnažší způsob jak tento problém řešit je použít bublinkové řazení. Princip tohoto algoritmu spočívá v tom, že se postupně a opakovaně prochází seřazované pole, přičemž se porovnávají každé dva sousedící prvky, a pokud nejsou ve správném pořadí, prohodí se. Hodnotu N si zvolte sami. 
<code C>
int pole[5]={5,3,4,1,2};
int main()
{
	int N = 5,i,j,tmp;
	for(i=0; i<N; i++)
		for(j=0; j<N-1-i; j++)
			if(pole[j+1]<pole[j])
			{
				tmp = pole[j+1];
				pole[j+1] = pole[j];
				pole[j] = tmp;
			}
	return 0;
}
</code>
\\ 
Princip algoritmu: Řazení prvků se uskutečňuje ve dvou vnořených cyklech - vnějším a vnitřním. Vnější cyklus zabezpečuje opakované spouštění vnitřního cyklu. Vnitřní cyklus postupně procházení pole a vzájemně vyměňuje dvě sousedící položky pokud nejsou v správném pořadí (má být menší vlevo, větší napravo). Protože vnitřní cyklus prochází polem zleva doprava (od menších indexů k větším) důsledkem je, že na konci pole se objeví vždy největší prvek z celého pole - největší prvek "probublal" na konec pole. Proto při dalším spuštění vnitřního cyklu nemusíme již procházet celým polem, ale jenom doposud neseřazenou částí tohoto pole. Postačuje N spuštění vnitřního cyklu aby se pole seřadilo.\\ 
\\
5, 3, 4, 1, 2  --> počáteční stav \\ 
3, 4, 1, 2, **5**  --> po prvním průchodu vnějším cyklem \\ 
3, 1, 2, **4**, **5**  --> po druhém průchodu vnějším cyklem \\ 
1, 2, **3**, **4**, **5**  ... \\ 
1, **2**, **3**, **4**, **5** \\ 
**1**, **2**, **3**, **4**, **5**  --> po pátém průchodu cyklem - seřazeno \\ \\ 

Přepište výše uvedený program z jazyka C do asembleru. Vykonávání programu oveřte v simulátoru Mips. Tento program budete potřebovat na příštím cvičení - to co nestihnete na cvičeních bude nutno dodělat doma..

\\  
Můžete využít předpripravenou šablonu k tomuto úkolu:
<code>
#define t0 $8
#define t1 $9
#define t2 $10
#define t3 $11
#define t4 $12

#define s0 $16
#define s1 $17
#define s2 $18
#define s3 $19

.globl    pole
.data
.align    2

pole:
.word    5,3,4,1,2

.text
.globl start
.ent start

start:
// Zde muzete psat Vas program
nop
.end start
</code>
\\  

==== Příklady přepisu krátkých fragmentů kódu z jazyka C do asembleru ====

^ Příkaz **//if//** ^^
| <code C> 
if (i ==j)
  f = g + h;

f = f – i;
</code> | <code>
//   s0=f, s1=g, s2=h, s3=i, s4=j

  bne s3, s4, L1   // Pokud i!=j, skoč na L1 
  add s0, s1, s2   // if blok: f=g+h
L1:
  sub s0, s0, s3   // f = f-i
</code> |



^ Příkaz **//if-else//** ^^
| <code C>
if (i ==j)
  f = g + h;
else
  f = f – i;

</code> | <code>
//   s0=f, s1=g, s2=h, s3=i, s4=j

  bne s3, s4, else  // Když i!=j, skoč na else
  add s0, s1, s2    // if blok: f=g+h
  j L2              // přeskoč blok else
else:
  sub s0, s0, s3    // blok else: f = f-i
L2:
</code> |


^ Cyklus **//while//** ^^
| <code C>
int pow = 1;
int x = 0;

while(pow != 128)
{
  pow = pow*2;
  x = x + 1;
}
</code> | <code>
// s0=pow, s1=x

  addi s0, $0, 1     // pow = 1
  addi s1, $0, 0     // x = 0
  addi t0, $0, 128   // t0 = 128 pro porovnávání

while:
  beq  s0, t0, done  // Když pow==128, ukončení cyklu while
  sll  s0, s0, 1     // pow = pow*2
  addi s1, s1, 1     // x = x+1
  j    while
done:
</code> |


^ Cyklus **//for//** ^^
| <code C>
int sum = 0;

for(int i=0; i!=10; i++)
{
  sum = sum + i;
}
</code> | <code C>
//Ekvivalentní k následujícímu cyklu while:
int sum = 0;

int i = 0;
while(i!=10){
  sum = sum + i;
  i++;
}
</code> |


^ Načtení slova z datové paměti ^^
| <code C>
// Jenom pro účely ukázky...
int a, *pa=0x80020040;
int b, *pb=0x80020044;
int c, *pc=0x00001234;

a = *pa;
b = *pb;
c = *pc;
</code> | <code>
// s0=pa (bazova adresa), s1=a, s2=b, s3=c

lui  s0, 0x8002   // pa = 0x80020000;
lw   s1, 0x40(s0)     // a = *pa;
lw   s2, 0x44(s0)     // b = *pb;

addi s0, $0, 0x1234   // pc = 0x00001234;
lw   s3, 0x0(s0)      // c = *pc;
</code> |


^ Inkrementování prvků pole ^^
| <code C>
int pole[4] = { 7, 2, 3, 5 };

int main()
{
   int i,tmp;
   for(i=0; i<4; i++)
   {
      tmp = pole[i];
      tmp += 1;
      pole[i] = tmp;
   }
   return 0;
}
</code> | Kompletní program v prostředí MipsIt: <code>
#define s0 $16
#define s1 $17
#define s2 $18
#define s3 $19

.globl    pole        // nazev "pole" bude globalni (viditelny ze vsech souboru projektu)
.data                 // direktiva oznacujici zacatek datove casti
.align    2           // zarovnani dat po slovech (4 Bytech)

pole:                 // pojmenovani mista v pameti
.word    7, 2, 3, 5   // inicializace pole...

.text                 // zacatek textove casti / programu
.globl start		  
.ent start			  

start:
la   s0, pole         // ulozeni adresy pocatku pole do registru s0 (pseudoinstrukce)
addi s1, $0, 0        // inicializacni prikaz cyklu for: i=0, kde i=s1
addi s2, $0, 4        // nastaveni horni meze cyklu

for:
  beq  s1, s2, done   // kdyz s1==s2 ukonceni cyklu skokem na navesti done
  lw   s3, 0x0(s0)    // nacteni polozky pole do registru s3
  addi s3, s3, 0x1    // inkrementace registru s3
  sw   s3, 0x0(s0)    // prepsani (ulozeni) hodnoty registru s3 do pole
  addi s0, s0, 0x4    // posun na dasli polozku pole
  addi s1, s1, 0x1    // inkrementace pocitadla poctu pruchodu cyklem (i++)
  j    for            // nepodmineny skok na navesti for
done:
nop
.end start
</code> |
\\

===== Odkazy =====

  * {{courses:B35APO:tutorials:03:mipsit.zip|}} - simulátor MipsIT ke stažení
  * [[.:mips-elf-gnu:start|Křížový překladač GNU pro MIPS-ELF]] - překladač kompatibilní s GNU překladačem použitým v MipsIT, balíčky pro Debian GNU/Linux x86_64 a i586, konfigurace a kompilace ze zdrojových kódů
  * {{courses:B35APO:tutorials:03:gcc-binutils-newlib-mips-elf_4.4.4-1_mingw32.zip|}} - MIPS-ELF GCC 4.4.4 zkompilované pro MinGW32 (Windows) - pro složitější programy vyžaduje přidat přepínače -lm  -lgcc -lc , pro pokusy v MipsIT pak nejčastěji i další -nostdlib -nodefaultlibs -nostartfiles -Wl,-Ttext,0x80020000 
  * [[http://en.wikipedia.org/wiki/MIPS_architecture|Popis procesoru MIPS]] - včetně kompletní instrukční sady.
  * [[http://courses.missouristate.edu/KenVollmar/MARS/|MARS (MIPS Assembler and Runtime Simulator)]]
    * Missouri State University - Velmi povedený simulátor v jazyce Java
    * Vyžaduje assembler bez makro definic (předzpracovaný). Pro předzpracování lze použít např. GCC
        ''gcc -E assembler.S -o predzpracovany-pro-mips.s''
  * [[http://www.linux-mips.org/wiki/Emulators|Emulátory MIPS na Linux-MIPS.org]]