PB111 Nízkoúrovňové programování 1/203 13. června 2024
PB111 Nízkoúrovňové programování
Petr Ročkai
PB111 Nízkoúrovňové programování 2/203 13. června 2024
Část A: Organizace
PB111 Nízkoúrovňové programování 3/203 13. června 2024
Část A.1: Informace o kurzu
PB111 Nízkoúrovňové programování 4/203 13. června 2024
A.1.1 Prerekvizity
• princip fungování počítače (PB150, PB151)
• základy programování (IB111)
• porozumění psanému textu
PB111 Nízkoúrovňové programování 5/203 13. června 2024
A.1.2 Studijní materiály
• tyto poznámky
• sbírka úloh
• literatura
• příklady na internetu
PB111 Nízkoúrovňové programování 6/203 13. června 2024
A.1.3 Ukončení
• hodnocena pouze praktická část
• zejména práce během semestru
• programovací test ve zkouškovém
• podrobněji ve sbírce
PB111 Nízkoúrovňové programování 7/203 13. června 2024
A.1.4 Seminář
• praktické programování
• předpokládá znalosti z této přednášky
• předpokládá znalosti z IB111
PB111 Nízkoúrovňové programování 8/203 13. června 2024
A.1.5 Přehled semestru
1. model výpočtu
2. organizace paměti
3. datové struktury a algoritmy
PB111 Nízkoúrovňové programování 9/203 13. června 2024
Část B: Základní pojmy a definice
PB111 Nízkoúrovňové programování 10/203 13. června 2024
Část B.1: Výpočetní stroje
PB111 Nízkoúrovňové programování 11/203 13. června 2024
B.1.1 Počítač
• von Neumanova architektura
• výpočetní jednotka provádí instrukce
• operační paměť ukládá data
• paměť je adresovatelná
PB111 Nízkoúrovňové programování 12/203 13. června 2024
B.1.2 Registr
• ukládají čísla (slova, ne slabiky!)
• aritmetické registry
• programový čítač
PB111 Nízkoúrovňové programování 13/203 13. června 2024
B.1.3 Instrukce
• instrukce je elementární příkaz
• procesor zná jen konečný počet instrukcí
∘ lze je tedy očíslovat
• instrukce lze sdružovat podle operací
∘ add, ld, atp. jsou operace
PB111 Nízkoúrovňové programování 14/203 13. června 2024
B.1.4 Výpočet
• aritmetické a logické (ALU) instrukce
∘ sčítání, odečítání, násobení, dělení
∘ logické operace po bitech, bitové posuvy
∘ relační operátory
• přístup do paměti: ld (load), st (store)
• řízení toku: podmíněné a nepřímé skoky
• (volitelně) realizace podprogramů
PB111 Nízkoúrovňové programování 15/203 13. června 2024
B.1.5 Program
PB111 Nízkoúrovňové programování 16/203 13. června 2024
B.1.6 Překlad
PB111 Nízkoúrovňové programování 17/203 13. června 2024
Část 1: Výpočetní stroj
PB111 Nízkoúrovňové programování 18/203 13. června 2024
Část 1.1: Model výpočtu
PB111 Nízkoúrovňové programování 19/203 13. června 2024
1.1.1 Motivace
• zjednodušený model počítače
• bez virtualizace, souběžnosti
• 16bitové registry a adresy
• jednoduchá instrukční sada
PB111 Nízkoúrovňové programování 20/203 13. června 2024
1.1.2 Stav
• hodnoty uložené v
∘ registrech
∘ paměti
• konečný počet možností
PB111 Nízkoúrovňové programování 21/203 13. června 2024
pc r1 r2 paměť
0000 0000 0000 00 00 00 00 00 00 00 00 00 00 00 00
0004 0007 03ff de ad de ad de ad de ad de ad de ad
0000 1007 7fff 00 00 00 00 00 00 00 de ad 00 co de
PB111 Nízkoúrovňové programování 22/203 13. června 2024
1.1.3 Akce
• počáteční stav = program
• akce = přechod mezi stavy
• stav přesně udává akci
∘ determinismus
∘ 1 program = 1 výpočet
PB111 Nízkoúrovňové programování 23/203 13. června 2024
1.1.4 Speciální stavy
• výpočet může být konečný
• rozlišení důvodu ukončení
∘ konec programu
∘ chybná instrukce
∘ selhání tvrzení
PB111 Nízkoúrovňové programování 24/203 13. června 2024
Část 1.2: Instrukční sada
PB111 Nízkoúrovňové programování 25/203 13. června 2024
1.2.1 Registry
• 16 obecných registrů
∘ rv, l1 … l7, t1 … t6, bp, sp
∘ výpočetně zcela rovnocenné
∘ sp má navíc speciální využití
∘ jména jinak pouze pro lidi
• programový čítač pc
PB111 Nízkoúrovňové programování 26/203 13. června 2024
1.2.2 Paměť
• 64KiB (65536 jednoslabičných buněk)
• adresace 16bitovým číslem
• každá adresa je platná
• program začíná adresou 0
PB111 Nízkoúrovňové programování 27/203 13. června 2024
1.2.3 Sémantika
• popis za pomoci mikroinstrukcí
• efekt instrukce na stav
• instrukce určena stavem
∘ 4 bajty od adresy dané pc
PB111 Nízkoúrovňové programování 28/203 13. června 2024
1.2.4 Operandy
• registrové operandy
∘ 0–2 vstupní registry
∘ 0 nebo 1 výstupní registr
• přímý operand
∘ hodnota je součást instrukce
PB111 Nízkoúrovňové programování 29/203 13. června 2024
1.2.5 Kódování
• dvě slova (2⋅16 = 32b)
• horní slovo
∘ kód operace
∘ výstupní registr
∘ vstupní registr 1
• spodní slovo
∘ vstupní registr 2 nebo
∘ přímý operand
PB111 Nízkoúrovňové programování 30/203 13. června 2024
1.2.6 Kopírování hodnot
• 1× vstup + 1× výstup
• nastaví hodnotu registru
• copy reg1 → reg2
• put imm → reg1
PB111 Nízkoúrovňové programování 31/203 13. června 2024
1.2.7 Binární operace
• aritmetika, srovnání
• bitové operace (logické, posuvy)
• 2× vstup + 1× výstup
• vstup/výstup se mohou překrýt
PB111 Nízkoúrovňové programování 32/203 13. června 2024
1.2.8 Operace řízení toku
• efekt na hodnotu pc
• nepodmíněný přímý skok jmp
• podmíněný přímý skok jz, jnz
• volání podprogramu později
PB111 Nízkoúrovňové programování 33/203 13. června 2024
1.2.9 Řízení stroje
• zastavení halt
∘ bez podmínky
∘ indikuje úspěch
• tvrzení asrt
∘ podmíněno vstupním registrem
∘ nula = neúspěch → chyba
PB111 Nízkoúrovňové programování 34/203 13. června 2024
Část 1.3: Řízení toku
PB111 Nízkoúrovňové programování 35/203 13. června 2024
1.3.1 Konstrukce strojového kódu
• rekurzivní algoritmus
• postupujeme po struktuře programu
∘ blok složíme z příkazů
∘ výraz složíme z podvýrazů
• zatím pouze intuitivně
PB111 Nízkoúrovňové programování 36/203 13. června 2024
1.3.2 Podmíněný příkaz
• nejjednodušší forma: if b: stmt1
∘ realizace jedním podmíněným skokem
∘ není-li b splněno, přeskoč tělo
• rozšíření: else větev
∘ podmíněný + nepodmíněný skok
∘ na konci „then“ přeskočíme za blok else
PB111 Nízkoúrovňové programování 37/203 13. června 2024
1.3.3 Nekonečný cyklus
• jak zapsat while True?
• realizace jedním skokem
∘ nepodmíněným
∘ na nižší adresu
• časem na něj opět narazíme
PB111 Nízkoúrovňové programování 38/203 13. června 2024
1.3.4 Cyklus while
• nekonečný cyklus + podmíněný break
• break je jeden podmíněný skok
∘ pro while na začátku těla
∘ skok za konec těla
• jednodušší: do–while
PB111 Nízkoúrovňové programování 39/203 13. června 2024
Část 2: Základní prvky jazyka C
PB111 Nízkoúrovňové programování 40/203 13. června 2024
Část 2.1: Hodnoty, objekty, proměnné
PB111 Nízkoúrovňové programování 41/203 13. června 2024
2.1.1 Hodnota
• význam podobný Pythou
• celé číslo
• později složitější
• 12 ~ XII ~ (1100)2 ~ 0xc
PB111 Nízkoúrovňové programování 42/203 13. června 2024
2.1.2 Operace
• pracuje s hodnotami
• hodnoty je potřeba si pamatovat
• realizace výpočetním strojem
• příklad: součet dvou hodnot
PB111 Nízkoúrovňové programování 43/203 13. června 2024
2.1.3 Objekt
• abstrakce (zobecnění) paměťové buňky
• pamatuje si hodnotu
• má identitu
∘ různost při stejné hodnotě
∘ stejnost během výpočtu
PB111 Nízkoúrovňové programování 44/203 13. června 2024
2.1.4 Proměnná
• vazba jména na objekt
• syntaktický rozsah platnosti
• vazba je neměnná (pevná)
• platnost jména ~ živost objektu
PB111 Nízkoúrovňové programování 45/203 13. června 2024
2.1.5 Typ
• je vlastnost hodnoty
• určuje přípustné operace
• určuje chování operací
• pouze v době překladu
PB111 Nízkoúrovňové programování 46/203 13. června 2024
2.1.6 Deklarace
• proti Pythonu nový prvek
• typ jméno = výraz;
• vytvoří zároveň objekt i vazbu
• bez inicializace = zapovězená hodnota
PB111 Nízkoúrovňové programování 47/203 13. června 2024
Část 2.2: Výrazy
PB111 Nízkoúrovňové programování 48/203 13. června 2024
2.2.1 Elementární výrazy
• název proměnné: x (typ dle proměnné)
• číselný literál:
∘ typu int: 3, -1, 0x1f
∘ typu unsigned: 3u, 0x1fu
PB111 Nízkoúrovňové programování 49/203 13. června 2024
2.2.2 Aritmetické a logické operace
• popisují hodnotu, žádný vedlejší efekt
• e1 + e2, …, e1 % e2
• e1 << e2, e1 >> e2
• e1 & e2, e1 | e2, e1 ^ e2
• -e1, ~e1, !e1
PB111 Nízkoúrovňové programování 50/203 13. června 2024
2.2.3 Výpočet hodnoty výrazu
• vyhodnocení do registru R
• var ~ copy A → R
• e1 + e2, …, e1 ^ e2
∘ vyhodnoť e1 do t1
∘ vyhodnoť e2 do t2
∘ add t1, t2 → R
PB111 Nízkoúrovňové programování 51/203 13. června 2024
2.2.4 Kontrola typů
• ověří spávnost operace × hodnoty
• vkládá implicitní konverze
∘ přesná pravidla jsou složitá
• špatně utvořený program zamítne
PB111 Nízkoúrovňové programování 52/203 13. června 2024
2.2.5 Implicitní konverze
1. povýšení – vše menší než int
∘ vejde se do int → int
∘ jinak unsigned
2. stejná znaménkovost → pouze zvětšení
3. různá vede na:
a. znaménkový je-li striktně větší
b. jinak na neznaménkový
PB111 Nízkoúrovňové programování 53/203 13. června 2024
operand operand společný typ
signed char signed char int
unsigned char int
int int
unsigned unsigned !
unsigned char unsigned char int
int int
unsigned unsigned
int int int
unsigned unsigned
unsigned unsigned unsigned
PB111 Nízkoúrovňové programování 54/203 13. června 2024
2.2.6 Přiřazení
• var = e1 (pozor na levou stranu)
• proběhne typová konverze pravé strany
• výraz s vedlejším efektem
• provede zápis do objektu
• hodnota je to, co bylo zapsáno
PB111 Nízkoúrovňové programování 55/203 13. června 2024
2.2.7 Booleovské operace
• binární e1 && e2, e1 || e2
• ternární e1 ? e2 : e3
PB111 Nízkoúrovňové programování 56/203 13. června 2024
2.2.8 Vyhodnocení booleovských operací
• vyhodnocení e1 && e2 do R:
∘ vyhodnoť e1 do R
∘ je-li R true, vyhodnoť e2 do R
• vyhodnocení e1 || e2 do R:
∘ vyhodnoť e1 do R
∘ je-li R false, vyhodnoť e2 do R
PB111 Nízkoúrovňové programování 57/203 13. června 2024
Část 2.3: Příkazy
PB111 Nízkoúrovňové programování 58/203 13. června 2024
2.3.1 Výrazový příkaz
• e1; – jakýkoliv výraz
• provede vedlejší efekty
• hodnota je zapomenuta
PB111 Nízkoúrovňové programování 59/203 13. června 2024
2.3.2 Složený příkaz
• sekvence příkazů
• uzavřena do složených závorek
• připouští navíc deklarace
∘ rozsah platnosti jmen
PB111 Nízkoúrovňové programování 60/203 13. června 2024
2.3.3 Podmíněný příkaz
• if ( expr ) stmt
• if ( expr ) stmt1 else stmt2
PB111 Nízkoúrovňové programování 61/203 13. června 2024
2.3.4 Cyklus do … while
• do stmt while ( expr );
PB111 Nízkoúrovňové programování 62/203 13. června 2024
2.3.5 Řízení iterace
• break; – ukončí cyklus
• continue; – ukončí aktuální iteraci
PB111 Nízkoúrovňové programování 63/203 13. června 2024
2.3.6 Cyklus while
• while ( expr ) stmt
PB111 Nízkoúrovňové programování 64/203 13. června 2024
2.3.7 Cyklus for
• for ( decl; expr1; expr2 ) stmt
PB111 Nízkoúrovňové programování 65/203 13. června 2024
Část 3: Podprogramy
PB111 Nízkoúrovňové programování 66/203 13. června 2024
Část 3.1: Podprogramy abstraktně
PB111 Nízkoúrovňové programování 67/203 13. června 2024
3.1.1 Účel
PB111 Nízkoúrovňové programování 68/203 13. června 2024
3.1.2 Zápis
• definice
∘ návratový typ
∘ jméno
∘ formální parametry
• použití (volání)
∘ jméno
∘ skutečné parametry
PB111 Nízkoúrovňové programování 69/203 13. června 2024
3.1.3 Vstupy a výstupy
PB111 Nízkoúrovňové programování 70/203 13. června 2024
3.1.4 Sémantika
• čistá
∘ nahrazení volání výsledkem
• obecně
∘ nahrazení tělem?
∘ výsledek + efekt
PB111 Nízkoúrovňové programování 71/203 13. června 2024
3.1.5 Typy
• návratový typ
∘ patří výrazu volání
• typy parametrů
∘ výrazy skutečných parametrů
• kontrola použití bez těla
PB111 Nízkoúrovňové programování 72/203 13. června 2024
3.1.6 Parametry
• formální parametr ~ proměnná
∘ má vlastní objekt
• předání parametru
∘ jako inicializace proměnné
∘ předání hodnotou
PB111 Nízkoúrovňové programování 73/203 13. června 2024
3.1.7 Rekurze
• použití v těle (definici)
• neznámá hloubka zanoření
• koncová vs obecná
PB111 Nízkoúrovňové programování 74/203 13. června 2024
Část 3.2: Operační sémantika
PB111 Nízkoúrovňové programování 75/203 13. června 2024
3.2.1 Zásobník
• oblast v paměti
• speciální registr sp = adresa
• souvisí s datovou strukturou
∘ last in, first out
∘ operace push, pop
∘ sp ~ top
PB111 Nízkoúrovňové programování 76/203 13. června 2024
3.2.2 Sémantika push, pop
• push reg
∘ sub sp, 2 → sp
∘ st reg → sp
• pop reg
∘ ld sp → reg
∘ add sp, 2 → sp
PB111 Nízkoúrovňové programování 77/203 13. června 2024
3.2.3 Předání řízení
• vstup: call
∘ pouze návratová adresa
∘ neřeší parametry
• konec: ret
∘ pop + pouze skok
∘ neřeší parametry
PB111 Nízkoúrovňové programování 78/203 13. června 2024
3.2.4 Sémantika call, ret
• call fn (jeden krok!)
∘ push pc
∘ jmp fn
• ret ~ pop pc
∘ nebo: pop X, jmp X
∘ nepřímý skok
PB111 Nízkoúrovňové programování 79/203 13. června 2024
3.2.5 Předávání parametrů
• přednostně v registrech
∘ l1, l2, …
∘ další na zásobník
• podobně návratová hodnota (rv)
• složitější typy později
PB111 Nízkoúrovňové programování 80/203 13. června 2024
3.2.6 Volací sekvence
• f( e1, e2, …, en )
∘ vyhodnoť e1 do l1
∘ vyhodnoť e2 do l2
∘ call f
PB111 Nízkoúrovňové programování 81/203 13. června 2024
3.2.7 Lokální proměnné
• hodnota se musí zachovat
• „zálohování“ registrů
∘ na zásobník (push, pop)
∘ do rámce
PB111 Nízkoúrovňové programování 82/203 13. června 2024
Část 3.3: Rámec
PB111 Nízkoúrovňové programování 83/203 13. června 2024
3.3.1 Přelití registru
• potřebujeme volný registr
• co když jsou všechny „živé“
• přesuneme hodnotu na zásobník
∘ stejně jako při „zálohování“
PB111 Nízkoúrovňové programování 84/203 13. června 2024
3.3.2 Lokální proměnné
• lokálních proměnných může být „moc“
• uložíme je na zásobník
• načtení do „dočasných“ registrů
• příště: adresa proměnné
PB111 Nízkoúrovňové programování 85/203 13. června 2024
3.3.3 Vyhodnocení proměnné
• vyhodnocujeme do tmp
• „žije“ v registru:
∘ copy reg → tmp
• „žije“ na zásobníku:
∘ ld bp, offset → tmp
∘ offset = vlastnost proměnné
PB111 Nízkoúrovňové programování 86/203 13. června 2024
3.3.4 Rámec
• privátní paměť podprogramu
• alokuje se na zásobníku
• různé aktivace → různé rámce
• pevná velikost
PB111 Nízkoúrovňové programování 87/203 13. června 2024
3.3.5 Bookkeeping
• při vstupu do podprogram:
∘ push bp
∘ copy sp → bp
∘ sub sp, N → sp
• při výstupu:
∘ copy bp → sp
∘ pop bp
PB111 Nízkoúrovňové programování 88/203 13. června 2024
Část 4: Ukazatele
PB111 Nízkoúrovňové programování 89/203 13. června 2024
Část 4.1: Objekt, identita, adresa
PB111 Nízkoúrovňové programování 90/203 13. června 2024
4.1.1 Hodnota
PB111 Nízkoúrovňové programování 91/203 13. června 2024
4.1.2 Objekt
• buňka pro uložení hodnoty
• typicky skrze proměnnou
• má identitu
• nemá pevnou adresu
PB111 Nízkoúrovňové programování 92/203 13. června 2024
4.1.3 Identita objektu
• identita je abstraktní
• ???
PB111 Nízkoúrovňové programování 93/203 13. června 2024
4.1.4 Adresa
• číselné označení buňky
• adresu lze vypočítat
• označuje slabiky/slova
∘ nikoliv hodnoty jazyka
∘ čtení/zápis z/na adresu
PB111 Nízkoúrovňové programování 94/203 13. června 2024
4.1.5 Adresa vs identita
• jak reprezentovat identitu
• adresa prvního bajtu
• co objekt v registru?
• co přesun objektu
PB111 Nízkoúrovňové programování 95/203 13. června 2024
4.1.6 Ukazatel
• identita jako hodnota
• načti/zapiš hodnotu
∘ nikoliv slabiku/slovo
PB111 Nízkoúrovňové programování 96/203 13. června 2024
4.1.7 Typ ukazatele
• obsahuje typ objektu
• zapisujeme typ *
• existuje pro každý typ
• kolik různých typů?
PB111 Nízkoúrovňové programování 97/203 13. června 2024
4.1.8 Operátor adresy
• nový tvar výrazu – &var
• pracuje s objektem
• výsledek je ukazatel
• použití fixuje adresu objektu
PB111 Nízkoúrovňové programování 98/203 13. června 2024
4.1.9 Operátor dereference *
• nové tvary výrazů
∘ *e1 – výsledek je objekt
∘ *e1 = e2 (nepřímé přiřazení)
• objekt vs hodnota
∘ l-hodnota vs r-hodnota
∘ l-kontext vs r-kontext
PB111 Nízkoúrovňové programování 99/203 13. června 2024
4.1.10 Platnost ukazatele
• platná adresa ≠ platný ukazatel
• musí ukazova na objekt
• typ ukazatele = typ objektu
• vstupní podmínka dereference
PB111 Nízkoúrovňové programování 100/203 13. června 2024
4.1.11 Výstupní parametr
• realizace ukazatelem
• void foo( int *out )
• out → kam zapsat výsledek
• volající odpovídá za objekt
PB111 Nízkoúrovňové programování 101/203 13. června 2024
Část 4.2: Přetypování
PB111 Nízkoúrovňové programování 102/203 13. června 2024
4.2.1 Přetypování aritmetických typů
PB111 Nízkoúrovňové programování 103/203 13. června 2024
4.2.2 Přetypování ukazatelů
PB111 Nízkoúrovňové programování 104/203 13. června 2024
4.2.3 Typy a objekty
PB111 Nízkoúrovňové programování 105/203 13. června 2024
Část 5: Pole
PB111 Nízkoúrovňové programování 106/203 13. června 2024
Část 5.1: XXX
PB111 Nízkoúrovňové programování 107/203 13. června 2024
5.1.1 Složené objekty
• umožňují uložit více hodnot
• složené z podobjektů
• není totéž jako složená hodnota!
PB111 Nízkoúrovňové programování 108/203 13. června 2024
5.1.2 Pole
• typ složeného objektu
• pevný počet podobjektů
∘ podobjekt ~ prvek
• podobjekty jsou očíslovné
• index = celé číslo
PB111 Nízkoúrovňové programování 109/203 13. června 2024
5.1.3 Syntaxe
• deklarace typ jméno[počet]
∘ lokální proměnná
• počet musí být konstanta
• použití = ukazatel (decay)
∘ jméno ~ &jméno
PB111 Nízkoúrovňové programování 110/203 13. června 2024
5.1.4 Inicializace
PB111 Nízkoúrovňové programování 111/203 13. června 2024
5.1.5 Operátor indexace
• nový tvar výrazu
• zjednodušeně var[e1]
• obecně e1[e2]
∘ e1 musí být ukazatel
• výsledek → i-tý podobjekt
PB111 Nízkoúrovňové programování 112/203 13. června 2024
5.1.6 Ukazatelová aritmetika
• analogie aritmetiky adres
∘ ukazatel + číslo → ukazatel
∘ ukazatel − ukazatel → číslo
• odpovídá indexaci
• a[i] ~ *(a + i)
PB111 Nízkoúrovňové programování 113/203 13. června 2024
5.1.7 Pasti
• pole není hodnota
∘ nelze kopírovat jako celek
∘ předáváme jako ukazatel
• nemá informaci o velikosti
• ani o (ne)využitých položkách
PB111 Nízkoúrovňové programování 114/203 13. června 2024
Část 6: Struktury, zřetězený seznam
PB111 Nízkoúrovňové programování 115/203 13. června 2024
Část 6.1: Struktury
PB111 Nízkoúrovňové programování 116/203 13. června 2024
6.1.1 Složená hodnota
• hodnota složená z jiných hodnot
• podhodnoty = složky
• příklad: uspořádaná dvojice
• příklad: seznam (v Pythonu)
PB111 Nízkoúrovňové programování 117/203 13. června 2024
6.1.2 Složený typ
• typ složené hodnoty
• určuje typy složek
• vztahuje se i na objekty
PB111 Nízkoúrovňové programování 118/203 13. června 2024
6.1.3 Složené hodnoty vs objekty
• složený objekt → má podobjekty
• složená hodnota → má složky
• podobjekt obsahuje hodnotu
• složky musí „pasovat“ na podobjekty
PB111 Nízkoúrovňové programování 119/203 13. června 2024
6.1.4 Záznamový typ
• anglicky record type
• obecná, běžná konstrukce
• pevné typy a pořadí složek
• pojmenované složky
PB111 Nízkoúrovňové programování 120/203 13. června 2024
6.1.5 Struktura
• záznamový typ v C
• zavedení klíčovým slovem struct
• tělo: typy a jména složek
• jméno typu: struct jméno
• literál neexistuje
PB111 Nízkoúrovňové programování 121/203 13. června 2024
6.1.6 Inicializace
• proměnné lze inicializovat
• proběhne po složkách
• struct pair x = { 1, 2 };
• … x = { .a = 1, .b = 2 };
• inicializace ≠ přiřazení
PB111 Nízkoúrovňové programování 122/203 13. června 2024
6.1.7 Přístup ke složce
• výraz tvaru e1.jméno
• může se vyhodnotit na objekt
∘ když je e1 objekt
∘ při dočasném zhmotnění […]
• adresy musí být „pohromadě“
PB111 Nízkoúrovňové programování 123/203 13. června 2024
6.1.8 Nepřímý přístup
• výraz tvaru e1->jméno
• je vždy objektem (l-hodnotou)
• e1 musí být typu ukazatel
• vstupní podmínka: platnost e1
PB111 Nízkoúrovňové programování 124/203 13. června 2024
6.1.9 Přiřazení
• uložení hodnoty to objektu
• u struktur proběhne po složkách
• rekurzivně do podstruktur, atp.
PB111 Nízkoúrovňové programování 125/203 13. června 2024
6.1.10 Pole ve struktuře
• jméno může označovat i pole
• každému prvku odpovídá složka
• struktura je stále hodnota
• pole stále není hodnota
PB111 Nízkoúrovňové programování 126/203 13. června 2024
6.1.11 Dočasné zhmotnění
• co znamená přístup do pole
∘ e1[e2] ~ *(e1 + e2)
∘ co je f().foo[1]?
• při přístupu vytvoříme objekt
• zanikne s koncem příkazu
PB111 Nízkoúrovňové programování 127/203 13. června 2024
Část 6.2: Zřetězený seznam
PB111 Nízkoúrovňové programování 128/203 13. června 2024
6.2.1 Princip
• složený ze samostatných uzlů
• uložených na nezávislých adresách
• každý reprezentuje jeden prvek
• ukazatel na další uzel
PB111 Nízkoúrovňové programování 129/203 13. června 2024
6.2.2 Výhody
• jednoduchá implementace
• velmi flexibilní
∘ fronta
∘ zásobník
∘ seznam (iterace)
PB111 Nízkoúrovňové programování 130/203 13. června 2024
6.2.3 Nevýhody
• nahodilý přístup do paměti
• větší paměťová režie
• nelze indexovat
• nešikovná abstrakce
PB111 Nízkoúrovňové programování 131/203 13. června 2024
6.2.4 Reprezentace
• struktura pro uzel
• lze mít samostatnou hlavu
• struct node *next
• pevný typ uložené hodnoty
PB111 Nízkoúrovňové programování 132/203 13. června 2024
6.2.5 Dvojité řetězení
• jednodušší odstranění uzlu
• složitější přidání uzlu
• výrazně větší režie
• obvykle se nepoužívá
PB111 Nízkoúrovňové programování 133/203 13. června 2024
6.2.6 Základní operace
• vložení
• iterace
• odstranění
PB111 Nízkoúrovňové programování 134/203 13. června 2024
6.2.7 Iterace
• při práci s celým seznamem
• typické využití cyklu for:
∘ struct node *n = head
∘ podmínka n
∘ posun n = n->next
PB111 Nízkoúrovňové programování 135/203 13. června 2024
6.2.8 Vložení uzlu
• potřebujeme znát pozici
• ukazatel na předchozí uzel
• na začátek → triviální
• na konec → ukazatel navíc
PB111 Nízkoúrovňové programování 136/203 13. června 2024
6.2.9 Odstranění
• opět potřebujeme znát pozici
• ukazatel na předchozí uzel
• ze začátku → triviální
• z konce → dvojité řetězení
PB111 Nízkoúrovňové programování 137/203 13. června 2024
Část 7: Dynamická alokace
PB111 Nízkoúrovňové programování 138/203 13. června 2024
1 Definice problému
PB111 Nízkoúrovňové programování 139/203 13. června 2024
2
PB111 Nízkoúrovňové programování 140/203 13. června 2024
Část 8: Správa paměti
PB111 Nízkoúrovňové programování 141/203 13. června 2024
Část 8.1: Dynamická velikost
PB111 Nízkoúrovňové programování 142/203 13. června 2024
8.1.1 Automatické proměnné
• uložené v rámci
• zabírají prostor na zásobníku
• zásobník má omezenou velikost
PB111 Nízkoúrovňové programování 143/203 13. června 2024
8.1.2 Paměťová složitost
• podobně jako časová O(f(n))
• n bude velikost problému
∘ nemusí nutně být pouze vstup
• alokace na zásobníku – O(1) OK
∘ O(logn) – obvykle OK
PB111 Nízkoúrovňové programování 144/203 13. června 2024
8.1.3 Jazyk C
• proměnné mají konstantní velikost
• alokace tedy pouze O(1)
• pozor ale na počet proměnných
PB111 Nízkoúrovňové programování 145/203 13. června 2024
8.1.4 Rekurze
• podobné omezení – max. O(logn)
• např. merge sort, binární hledání
• co backtracking?
∘ exponenciální čas
∘ lineární hloubka rekurze
PB111 Nízkoúrovňové programování 146/203 13. června 2024
8.1.5 Meze rekurze
• co stromové struktury?
∘ může a nemusí být OK
∘ hloubka ne vždy O(logn)
• koncová rekurze
∘ lze v konstantní paměti
∘ v C to ale není povinné
PB111 Nízkoúrovňové programování 147/203 13. června 2024
8.1.6 Dynamická alokace
• bez striktních omezení
• adresní prostor
∘ 64b bez problémů
∘ omezený pro ≤ 32b adresy
• paměť není nekonečná
PB111 Nízkoúrovňové programování 148/203 13. června 2024
8.1.7 Standardní C
• knihovna: malloc, free
• vyžaduje interakci s OS
• malloc je (trochu) magický
PB111 Nízkoúrovňové programování 149/203 13. června 2024
Část 8.2: Dynamická živost
PB111 Nízkoúrovňové programování 150/203 13. června 2024
8.2.1 Statická živost
• lokální proměnné
• život = rozsah platnosti
• jednoduché ale omezující
PB111 Nízkoúrovňové programování 151/203 13. června 2024
8.2.2 Dynamická živost
• dynamická paměť
• rozhoduje se za běhu
∘ např. v podmínce
• významný zdroj chyb
PB111 Nízkoúrovňové programování 152/203 13. června 2024
8.2.3 Uvolnění
• konec živosti objektu
• ukazatele dále existují
∘ jsou již ale neplatné
∘ mrtvý objekt nesmí být použit
• koordinace je kritická
PB111 Nízkoúrovňové programování 153/203 13. června 2024
8.2.4 Klasifikace chyb
• použití po uvolnění
∘ lze rozlišit zápis/čtení
• dvojité uvolnění
• chybějící uvolnění (únik)
PB111 Nízkoúrovňové programování 154/203 13. června 2024
8.2.5 Použití po uvolnění
• dereference neplatného ukazatele
∘ nedefinované chování
• čtení → nesmyslná hodnota
• zápis → poškození dat
• ohrožení metadata alokátoru
PB111 Nízkoúrovňové programování 155/203 13. června 2024
8.2.6 Dvojité uvolnění
1. neplatný ukazatel
∘ poškození metadat
∘ nedefinované chování
2. omylem platný ukazatel
∘ uvolní jiný objekt
∘ další použití je pak UB
PB111 Nízkoúrovňové programování 156/203 13. června 2024
8.2.7 Únik zdrojů
• objekt nebyl uvolněn
∘ striktně – už nebude použit
∘ volně – neexistuje ukazatel
• situačně závislé
∘ použití může být zbytečné
PB111 Nízkoúrovňové programování 157/203 13. června 2024
8.2.8 Obecněji o zdrojích
• paměť není jediný zdroj
• platí stejná pravidla
∘ zdroj ~ objekt
• soubory, mutexy, atp.
PB111 Nízkoúrovňové programování 158/203 13. června 2024
8.2.9 Pseudostatická živost
• statická živost je přirozená
• nelze vždy použít i když stačí
∘ dynamicky velké pole
∘ jiné zdroje než objekty
• syntaktické párování alokace/dealokace
PB111 Nízkoúrovňové programování 159/203 13. června 2024
Část 9: Dynamické pole
PB111 Nízkoúrovňové programování 160/203 13. června 2024
Část 9.1: Abstraktní datové struktury
PB111 Nízkoúrovňové programování 161/203 13. června 2024
9.1.1 Indexovatelný seznam
• abstraktní datová struktura
• operace:
∘ append – vloží prvek na konec
∘ remove – odstraní poslední prvek
∘ get – vrátí prvek na daném indexu
∘ size – vrátí aktuální počet prvků
• srovnejte zásobník
PB111 Nízkoúrovňové programování 162/203 13. června 2024
Část 9.2: Implementace
PB111 Nízkoúrovňové programování 163/203 13. června 2024
9.2.1 Dynamické pole
• zřetězený seznam → get je O(n)
• vyhledávací strom → get je O(logn)
• standardní pole → neumí append
PB111 Nízkoúrovňové programování 164/203 13. června 2024
9.2.2 Implementace: dynamické pole
• dynamické pole → vše konstantní
∘ ale pouze amortizovaně
• vyhradíme paměť jako u běžného pole
• dojde místo → realokace
∘ alokujeme větší pole
∘ dosavadní prvky přesuneme
∘ původní paměť uvolníme
PB111 Nízkoúrovňové programování 165/203 13. června 2024
9.2.3 Organizace v paměti
• ukazatel, velikost, kapacita
• struktura se 3 položkami
• hlavička před začátkem pole
• předávání, vstupně-výstupní parametr
PB111 Nízkoúrovňové programování 166/203 13. června 2024
9.2.4 Reprezentace položek
• v poli pouze ukazatel
∘ výhodné pro velké položky
∘ nahradit zřetězeným seznamem?
• položka přímo v poli
∘ ideální pro malé položky
∘ ukazatel na položku není trvalý
PB111 Nízkoúrovňové programování 167/203 13. června 2024
9.2.5 Platnost ukazatelů
• zvětšení zneplatňuje ukazatele
∘ nelze dlouhodobě ukládat
• pozor na append během iterace
• nevíme který append je bezpečný
PB111 Nízkoúrovňové programování 168/203 13. června 2024
9.2.6 Amortizace
• uvažme posloupnost n operací
• jaká je průměrná složitost jedné?
∘ n vložení v čase O(n)
∘ na jedno vložení připadne čas O(1)
• metody analýzy → IB114
PB111 Nízkoúrovňové programování 169/203 13. června 2024
9.2.7 Taktika zvětšování
• o konstantu
∘ špatná asymptotická složitost
∘ pouze speciální situace
• na dvojnásobek
∘ zaručuje správnou složitost
∘ jednoduché a účinné
PB111 Nízkoúrovňové programování 170/203 13. června 2024
9.2.8 Exponenciální zvětšování
• na abstraktní úrovni optimální
• dopad na využití paměti?
∘ fragmentace adresního prostoru
∘ (ne)využitelnost uvolněné paměti
• možnosti řešení:
∘ alternativní schéma zvětšování
∘ speciální podpora v alokátoru
PB111 Nízkoúrovňové programování 171/203 13. června 2024
9.2.9 Další využití
• zásobník → přímočaré
• fronta → kruhová + přesuny
• fronta → dva zásobníky
• prioritní fronta
PB111 Nízkoúrovňové programování 172/203 13. června 2024
9.2.10 Zmenšování
• nezvratný růst nemusí být ideální
• naivní zmenšování nefunguje
∘ „thrashing“ okolo meze zvětšení
• hystereze, zaplnění < 0,5
PB111 Nízkoúrovňové programování 173/203 13. června 2024
9.2.11 Využití paměti
• n počet prvků, k velikost
• zarovnání na mocninu dvou
• minimum (ideální) n ⋅ k
• maximum (nejhorší) 2n ⋅ k
• průměr 1, 5n ⋅ k
PB111 Nízkoúrovňové programování 174/203 13. června 2024
9.2.12 Srovnání
• p = velikost ukazatele
• zřetězený seznam: n ⋅ (k + p)
• binární strom: n ⋅ (k + 2p)
• dynamické pole: 1, 5n ⋅ k
• velikost, kapacita: +2p
PB111 Nízkoúrovňové programování 175/203 13. června 2024
9.2.13 Režie alokátoru
• velmi variabilní
• minimální velikost alokace
• fragmentace zvětšováním pole
• výrazný dopad na obojí
PB111 Nízkoúrovňové programování 176/203 13. června 2024
9.2.14 Efektivita v praxi
• sekvenční vs náhodný přístup
• efektivita využití cache
∘ umístění mrtvé paměti
PB111 Nízkoúrovňové programování 177/203 13. června 2024
Část 9.3: Binární halda
PB111 Nízkoúrovňové programování 178/203 13. června 2024
Část 10: Slovníky a množiny
PB111 Nízkoúrovňové programování 179/203 13. června 2024
Část 10.1: Hašovací tabulky
PB111 Nízkoúrovňové programování 180/203 13. června 2024
Část 10.2: Vyhledávací stromy
PB111 Nízkoúrovňové programování 181/203 13. června 2024
Část 11: Paměť
PB111 Nízkoúrovňové programování 182/203 13. června 2024
Část 11.1: Objekty
PB111 Nízkoúrovňové programování 183/203 13. června 2024
11.1.1 Připomenutí: objekt
• objekt je zobecnění paměti
• vzniká deklarací proměnné
• ukládá hodnotu (ne bajty!)
• může mít přidělenu adresu
PB111 Nízkoúrovňové programování 184/203 13. června 2024
11.1.2 Paměť
• „pole bajtů“
• adresa ~ index
∘ (± díry v adresním prostoru)
• bajt ~ unsigned char
∘ hodnota 0–255
PB111 Nízkoúrovňové programování 185/203 13. června 2024
11.1.3 Překrývání (aliasing)
• objekty se stejnou adresou
• typicky není dovoleno
• výjimky:
∘ reprezentace
∘ kompatibilní typy
PB111 Nízkoúrovňové programování 186/203 13. června 2024
11.1.4 Reprezentace objektu
• bajty objektu = reprezentace
• reprezentace je sama objektem
• kódování definováno implementací
• nemusí být jednoznačná
PB111 Nízkoúrovňové programování 187/203 13. června 2024
11.1.5 Přetypování
• objekt a reprezentace sdílí adresu
• ukazatele mají různé typy
• přesto lze bezpečně přetypovat
∘ reprezentace → unsigned char *
• jen pozor na const
PB111 Nízkoúrovňové programování 188/203 13. června 2024
11.1.6 Vznik objektu
• paměť ~ unsigned char[N]
• zápisem reprezentace
∘ kopie po bajtech
∘ přiřazení
PB111 Nízkoúrovňové programování 189/203 13. června 2024
11.1.7 Neplatné objekty
• objekt lze konstruovat z bajtů
• ne každá reprezentace je platná
• čtení z neplatného objektu → UB
PB111 Nízkoúrovňové programování 190/203 13. června 2024
11.1.8 Ukazatel bez typu
• void * – neurčuje typ objektu
• není dovoleno dereferencovat
• povoluje implicitní přetypování
• nesmí porušit pravidla o překrývání
PB111 Nízkoúrovňové programování 191/203 13. června 2024
Část 11.2: Alokace
PB111 Nízkoúrovňové programování 192/203 13. června 2024
11.2.1 Zadání úlohy
• nalézt nepoužitou paměť
• v nějaké větší oblasti
∘ typicky od operačního systému
∘ nemusí být souvislá
• zadané minimální velikosti
PB111 Nízkoúrovňové programování 193/203 13. června 2024
11.2.2 Dynamická paměť
• nekonstantní velikost alokace
• živost určená za běhu
∘ vedlejší efekt výrazu
∘ detailněji příště
PB111 Nízkoúrovňové programování 194/203 13. června 2024
11.2.3 Další požadavky
• co nejrychleji
• co nejméně nevyužitelné paměti
∘ fragmentace adresního prostoru
∘ metadata alokátoru
PB111 Nízkoúrovňové programování 195/203 13. června 2024
11.2.4 Strategie
• rozdělit volný blok
∘ musí být dostatečně velký
∘ first-fit → první takový
∘ best-fit → nejmenší takový
• sub-alokátory
∘ kombince různých strategií
PB111 Nízkoúrovňové programování 196/203 13. června 2024
11.2.5 Předalokace
• typicky pro malé velikosti
• paměť se chystá dávkově
∘ třeba po 4KiB blocích
∘ všechny objekty stejně velké
PB111 Nízkoúrovňové programování 197/203 13. června 2024
11.2.6 Datové struktury
• zřetězený seznam volných bloků
∘ uzel uvnitř volného bloku
∘ zaužívaný název freelist
• tabulka indexovaná velikostí
• hashovací tabulky
PB111 Nízkoúrovňové programování 198/203 13. června 2024
Část 11.3: Realokace paměti
PB111 Nízkoúrovňové programování 199/203 13. června 2024
11.3.1 Situace
• implementujeme dynamické pole
• potřebujeme pole zvětšit
• triviálně:
∘ nová alokace + kopie dat
∘ dealokace původního
• lze provést i lépe?
PB111 Nízkoúrovňové programování 200/203 13. června 2024
11.3.2 Využití stávající alokace
• vyžaduje spolupráci alokátoru
• použít následující volný blok
∘ optimální – není potřeba přesun
∘
• použít předchozí blok
PB111 Nízkoúrovňové programování 201/203 13. června 2024
11.3.3 Využití předchozího bloku
• vyžaduje přesun dat
∘ překryv podle poměru velikostí
∘ dvojnásobek → bez překryvu
• celková potřebná paměť m
∘ oproti m + n pro novou alokaci
∘ dvojnásobek → 2n vs 3n
PB111 Nízkoúrovňové programování 202/203 13. června 2024
11.3.4 Přesun dat
• kopie for cyklem po bajtech
• co překrývající se oblasti
∘ někdy je potřeba iterovat odzadu
∘ mnohem méně efektivní
• alternativní metody dle platformy
PB111 Nízkoúrovňové programování 203/203 13. června 2024
11.3.5 Situace v praxi
• knihovna jazyka C má realloc
∘ umožňuje i zmenšení alokace
∘ poněkud komplikované rozhraní
• Rust, D také nabízí realloc
• C++ od podpory upustilo