Principy Počítačů

17. 1. 2020 · Poznámky · 23 min čtení · 🇨🇿 · dostupné v PDF · [upravit]

• • Zjednodušené schéma počítače
  • Historie
    • Charles Babbage (1837)
    • Ada Lovelace
  • Kódování informace v počítači
    • Analogový přenos
    • Digitální přenos
      • Sériový přenos
      • MSb/LSb odbočka
  • Dohoda přenosu
    • Řešení (1): nový stav
    • Řešení (2): hodinový signál
    • Řešení (3): průběžná korekce
  • Typy přenosu
    • Značení
  • Komunikační protokol
  • Binární odbočka
    • Operace
    • Záporná čísla
  • Čísla v Pythonu
    • Implementace
    • Převody mezi soustavami
  • Převody mezi datovými typy
  • Otročina
    • Připojení
      • \(\text{I}^2 \text{C}\) (Inter Integrated Circuit)
  • Paměť
    • Jednotky
    • Typy paměti RAM
      • SRAM (static RAM)
      • DRAM (dynamic random access memory)
    • Co je to jsoucno slovo?
    • Rozbor PCF8570 SRAM paměti
  • Instrukce a architektury
    • Endianita
    • Harvard \(\times\) von Neumann
    • Historie CPU architektur
    • Assembler
    • Příznakový registr CPU
    • 6502 – akumulátorová architektura
      • Sčítání a odčítání
    • x86
      • Příklady instrukcí
      • Rychlost operací
    • Čísla v Pythonu, vol. 2
    • Násobení a dělení
    • Tomášova odbočka (příklady instrukcí)
  • Reálná čísla
    • Fixed-point
    • Floating-point
      • IEEE 754
      • Ošklivá čísla
      • Speciální hodnoty
  • Paměti ROM
    • Permanentní datové úložiště
      • HDD
        • Výhody
        • Nevýhody
      • CD / DVD / BLURAY
      • Řadiče pro úložiště
  • Adresování, soubory
    • V Pythonu
      • Soubory
      • Byty
    • Šestnáctkový výpis
    • Reprezentace obrazu
      • Pixel
      • Ukládání do paměti
        • BMP
    • Reprezentace textu
      • ASCII
      • Unicode
      • Rasterizace
  • Dokončení rozdělané magie
    • Systémová sběrnice
      • Memory/mapped I/O [wiki]
      • Co dělat po startu?

Úvodní informace

Tato stránka obsahuje moje poznámky z přednášky Pavla Ježka z akademického roku 2019/2020 (MFF UK). Pokud by byla někde chyba/nejasnost, nebo byste rádi něco přidali, tak stránku můžete upravit pull requestem (případně mi dejte vědět na mail).

Zjednodušené schéma počítače

• vymyšlena na univerzitě v Harvardu
• CPU – vykonává instrukce
• kódová paměť – uchovává instrukce; je pouze pro čtení
• datová paměť – uchovává data, se kterými pracujeme

Historie

Charles Babbage (1837)

• mechanický stroj analytical engine
  • z dnešního pohledu plnohodnotný počítač
  • byl Turingovsky úplný!
  • nebyl nikdy fyzicky postaven
  • měl usnadnit počítání tehdy komplexních matematických tabulek (pro navigaci a astronomii)

Ada Lovelace

• dcera G. G. Byrona
• finančně Babbage podporovala
• příběhy o ní jako programátorce (psaní programů, ladění bugů) jsou vesměs nesmysl, ale:
  1. napsala manuál stroje
  2. napadlo ji, že by se mohlo pracovat i s jinými informacemi než s čísly (texty, obrazy, hudba…)

Kódování informace v počítači

• pojďme si zakódovat čísla

Analogový přenos

• kódování , by nešlo, jelikož se musí čekat na bouřku
  • , zní rozumněji
• v praxi zní skvěle, ale v realitě řada problémů, jelikož napětí ovlivňuje:
  • délka vodiče
  • teplota vodiče
  • elektromagnetické pole, které je vodičem jak generováno, tak přijímáno

Digitální přenos

• problém je v intervalech, které se překrývají… co je odtáhnout od sebe?
• pouze 2 hodnoty – logická 1 a logická 0
• jednotka bit (BInary digiT, značíme )
• funguje s rozumným šumem (100procentní ale není)

Sériový přenos

• způsob přenosu více bitů informace: pošleme je za sebou

1. měření hodnoty na měřáku

   • nezapomínat na to, že napětí je relativní

     

2. měření rozdílu napětí dvou vodičů

   • výhoda – elektromagnetické rušení signál neovlivňuje, jelikož rozdíl je relativní

     

• délka bitů musí být jasně dána, aby přijímající dobře interpretoval informace
  • dnes bývá dána hardwarově
  • přenosová rychlost (= transfer rate)… baud (symbols / second)

MSb/LSb odbočka

• je potřeba se dohodnout, jak říkat různým bitům dvojkových čísel
• LSb-first – první v komunikaci přijde LSb, poslední MSb (MSb-first funguje analogicky)

Dohoda přenosu

• problém: hodiny se časem kvůli HW rozejdou – data pak stranám nedávají smysl

Řešení (1): nový stav

• vymyšlení dalšího stavu přenosu, ve kterém k přenosu nedochází

1. odpojení vodiče = floating state (plovoucí stav)

   • lze detekovat, že je linka odpojena
   • není to ideální, moc se nepoužívá

2. idle stav

   • na začátku je linka idle (tzn. přenos neprobíhá)
   • používá RS-232
   • start dohodou, většinou rising edgem (dobře se detekuje), poté držen (většinou 1) start bit
     • start (a end) bit je potřeba – když by to jen vystřelilo, tak by to druhá strana kvůli šumu vůbec nemusela detekovat
   • se startem (rising edge) se synchronizují hodiny
     • nejsou perfektní (mají tendenci se rozcházet) – omezení přenosu na bitů, kde je konstanta (v reálu )
       • pozn.: jsou 2 šestnáctkové znaky
   • velký overhead… z je jen datových…

Řešení (2): hodinový signál

• používá
• nový (tzv. referenční) vodič s digitálním (hodinovým) signálem
• diktuje, kdy lze na datovém vodiči číst
• zdá se, že je overhead, jelikož se data mohou detekovat pouze na rising edge
  • většinou ale maximální rychlost není potřeba
  • když je potřeba, tak lze obejít: detekce na rising i falling
    • značí se DDR (double data rate)
    • problém to hardwarově detekovat – používané jen tam, kde je rychlost nezbytná

Řešení (3): průběžná korekce

• bylo by fajn průběžně synchronizovat na rising edge… co když ale chodí samé nuly (nebo jedničky)?
• clock recovery (obnova hodinového signálu) – převod dat z :
  • 4krát více možností – vyberou se jen ty „hezké“ (kde se střídají a )
  • kódování/dekódování je prováděno pomocí tabulky
  • nemusí to nutně být 10, existují i jiné konfigurace

Typy přenosu

1. half-duplex: 1 datový vodič – zařízení se v přenosu střídají
   • komplikované
   • nikdy nelze posílat najednou oběma směry
2. full-duplex: 2 nezávislé simplexní linky
   • např. RS-232 – 2 datové + 1 zem

• význačné (out-of-band) stavy = dochází baterka/změna módu/…
  • někdy je potřeba sdělit uprostřed přenosu
  • digitální signály (on/off)
  • lze přes to zařízení i napájet – některá to tak dělají

Značení

• většinou je pravda a nepravda, někdy se ale hodí prohodit:

• někdy je také potřeba rozlišovat soustavu, ve které číslo je:

Komunikační protokol

• dohoda, jak přenos vypadá…

• problém: starší zařízení mají

  • řešení: řadič (controller), který přijímá data ze zařízení a zpracovává je

• config register – nastavení přenosové rychlosti, parity,…
• status register – zda se načetl celý byte

Binární odbočka

Operace

• binární:
  • OR: | – alespoň jedno
  • AND: & – oboje
  • XOR: ^ – právě jedno
  • SHL a SHR: << a >> – posouvá k MSb/LSb, ne doleva/doprava
    • ROL, ROR (bit rotation) – jako posun, ale cyklí čísla; opět k MSb
• unární:
  • NOT: ~ – opak

Záporná čísla

Řada způsobů, jak to dělat (špatně):

1. jako celá čísla, ale první bit je znaménko
   • docela k ničemu – žádné normální bitové operace na to nefungují (sčítání, odčítání, porovnání…)
2. one’s complement (jedničkový doplněk) – u záporných se prohodí 1 a 0
   • funguje porovnání (kladné x kladné a záporné x záporné) a sčítání
   • problematické: máme dvě nuly
3. two’s complement (dvojkový doplněk) – MSb je znaménkový bit, záporných je o 1 víc
   • negace čísla je flipnutí všech bitů a přičtení jedničky
   • řeší to problém se dvěma nulami (negace dá jedničky a přičtení overflowne zpět na )
   • rozsah je až (asymetrické…)

Čísla v Pythonu

Implementace

• jako pole… ukládá si právě tolik cifer, kolik je potřeba (+ padding do bytu)
• také potřebuje vědět, kolik bytů to číslo má
  • tím pádem je max. velikost bitů, což je… dost
• znamená to, že se operace chovají divně… ~255 je -256 ((0)11111111 -> (1)00000000)

Převody mezi soustavami

• literály: 0x123 (hex), 0o123 (oct), 0b101 (bin)
• převody: int(str, base), hex(num), bin(num), oct(num)

Převody mezi datovými typy

• truncation: useknutí cifer, které se do menšího datového typu nevejdou
  • z definice nemusí dobře fungovat (máme méně čísel), může se dokonce změnit znaménko
• extension:
  • zero extension – doplnění nul na prázdná místa po zvětšení datového typu
    • nedává smysl u signed intů
  • signed extension – doplnění o MSb
    • dává smysl u signed intů, ale ne u unsigned!

Otročina

• pojmy master (řídící; řídí komunikaci, dává požadavky) a slave (řízený; vykonává požadavky)
  • v komunikaci vždy 1 master a 1 slave
  • role se mohou měnit
  • směr master slave je write, obrácený read

Připojení

• point-to-point linka:
  • z bodu do bodu – 1 master a 1 slave
  • nepraktické – reálně je procesor pořád master a museli bychom do něj vést trilión linek
• multidrop/bus (sběrnice)
  • více slavů na jedné lince
  • pozor – sběrnice znamená něco jiného, ale dnes se to takhle říká

• rozlišují se adresou, která je pro každé zařízení na sběrnici unikátní
  • rozsahu těchto adres se říká adresový prostor (address space)
• linky jsou half-duplexy bez floatingového stavu
  • vždy se mezi sebou baví 2 zařízení

• když nevysílá nikdo, je tam díky pull-up rezistoru ; když někdo , tak
  • rezistor zařídí to, aby stav na lince nebyl plovoucí
• to, že se to spolu vlastně mlátí, budeme řešit až na vyšší úrovni

(Inter Integrated Circuit)

• je to opravdová sběrnice
• podporuje multimaster – více zařízení mohou být master najednou
  • musí se detekovat srážky, když chtějí 2 masterové vysílat najednou
  • rozdílné od USB (universal serial bus) – to je single master

• SDA = serial data; SCL = serial clock
• idle stav je vždy vyrušen masterem, který chce navázat komunikaci
  • rovněž generuje hodinový signál
  • začátek nastává, když nastane na SDA a na SCL (zakázaný stav!)

• bitů na byte
  • data (MSb-first)
  • acknowledgement bit (ack = ano; nak = ne)
    • pro je ACK, je NAK, jelikož stahuje… pokud tam slave není, tak tam bude
  • pořadí při přenosu vypadá následně:
    • write: M/S/M/S/M/S... (slave neustále potvrzuje, že přečetl)
    • read: M/S/S/M/S/S/M... (slave potvrzuje, že posílá a pak začne posílat)
• pro clock jsou dány standardizované rozsahy, aby to slave ustál
  • má možnost dělat clock stretching – pokud by nestíhal, tak může hodiny podržet na (hold low)

• management je obecný pro ; zbytek je device-specific
  • 1-7 je adresa, 8 je r/w
• payload – to, „za co platíme“ (samotná data)

• ADC = analog-digital converter – převod analogu do digitálu
  • přijímáme světlo (analogový signál)
• bus interface – řídí zařízení, komunikuje,…
  • pro vyrábění k jiné sběrnici stačí nahradit pouze tohle
• adresa je pevně daná… na sběrnici může být pouze jedna
• zařízení má 2 registry (read only, write only)
  • znamená to, že nemusíme rozlišovat, ze kterého registru číst a do kterého psát

Paměť

• paměťový adresový prostor – rozsah adres v paměti
  • pro bude
  • většinou i pro bude (se se nepracuje skvěle)
  • pro může být – dobře se to scaluje (při upgradu hardwaru)

Jednotky

• není (nepraktické), ale
  • používají všichni… až na výrobce pevných disků
  • dnes se hodí používat jasnější značení (ki-bi-bajt)

Typy paměti RAM

• RAM = random access (memory) – můžeme přistupovat k libovolné hodnotě a bude to trvat stejně rychle
• zpravidla bývá r/w a volatile (po vypnutí ztratí data)

SRAM (static RAM)

• = 4 až 6 tranzistorů
• kapacita je malá (řádově MB)
• všechny přístupy mají trvat stejně dlouho (staví na tom algoritmizace), ale v realitě:
  • sekvenční přístupy jsou rychlejší
  • obrácené sekvenční jsou něco mezi
  • náhodné přístupy jsou pomalejší
• přístup - ; ~

DRAM (dynamic random access memory)

• = 1 tranzistor a 1 kondenzátor
• levnější a větší (řádově GB), ale pomalejší (nabíjí/vybíjí se pomalu)
• v rámci přístupu pro ni platí (zhruba) to samé jako pro SRAM
• hodnoty si pamatuje krátce (kondenzátory…)
  • každou je potřeba refresh (přečteme a zapíšeme)
  • částečně může za pomalý access time (pořád se čte a zapisuje)
• přístup - ; ~

Co je to jsoucno slovo?

1. správná definice – jednotka přenosu
   • pro -bitové zařízení je to -bitové slovo
   • pro paměť to např. znamená, že lze vyžádat pouze
2. špatná definice – (dáno historicky)
   • double word (dword) =
   • quad word (qword) =

Rozbor PCF8570 SRAM paměti

• programovatelná adresa, 1010 vestavěná
• rychlost přenosu přes je cca.
  • overhead je
    • na každou transakci ( + ack) přeneseme 3B, z toho jen 1 jsou data
    • jde to zlepšit – burst přenos (nezačínáme další přenosy, jen sekvenčně čteme/zapisujeme):
• zápis – 1 transakce
• čtení – 2 transakce (psaní do adresového registru nějakou hodnotu + čtení slova)

Instrukce a architektury

• instrukce – posloupnost bytů
• instrukční sada (instruction set) – instrukce podporované daným CPU
• strojový kód – posloupnost instrukcí (machine code)
• instruction pointer (IP) – pozice aktuálně ukazované instrukce
  • zpravidla ukazuje na první byte (vícebytové) instrukce
  • je -bitový (logicky stejně jako code memory)

• opcode (operation code) – typ instrukce
  • podle toho se interpretují argumenty
  • bývá až
• argumenty – s čím instrukce pracuje – hodnota/adresa/…

Endianita

• pochází z Gulliverových cest podle skupin lidí, kteří jedli vejce z různých konců – little end(iáni), big end(iáni)
  • je to ve výsledku vlastně úplně jedno, jen je potřeba si něco zvolit
• většina procesorů je little endian (ten divný, obrácený způsob)
• pozor – endianita bitů a bytů může být rozdílná!

Harvard von Neumann

Historie CPU architektur

• 6502 (Apple I – Wozniak)
  • 8-bit CPU
  • von Neumann
  • 16-bit addr space (64 kB operační paměti)
  • little endian
• Intel 8088
  • 16-bit CPU
  • 20-bit addr space (1 MB operační paměti)
  • little endian
  • převládlo – 20-bit address space byl velká výhoda

Assembler

• jelikož jsou instrukce pouze posloupnost hex cifer, tak se špatně čtou – řeší to assembler
  • skok je např. JMP, load je LDA, store je STA

Příznakový registr CPU

• 1 příznak (flag) = 1 bit informace
  • zero – jestli poslední výsledek byla 0
  • sign – záporný výsledek operace
  • carry (přenos) – z nějakých operací (např. sčítání)
    • operace to definují různě (podle toho, co potřebují)
• SET a CLR instrukce umožňují explicitně upravovat hodnoty registrů

6502 – akumulátorová architektura

• A – registr, na kterém se provádějí všechny aritmetické operace
• podpora AND, OR, XOR, SHR, SHL, ROL, ROR
  • bacha… NOT nemá (jde ale přes XOR s jedničkami)
• pro vícebitové proměnné je potřeba rozdělit na části a řešit zvlášť
• aritmetika je trochu problematická – x86 ani 6502 neumějí ukládat na třetí adresu

Sčítání a odčítání

• je potřeba explicitně nastavit carry příznak na 0 (CLC instrukce)
  • řetězení: LDA CLC ADC STA | LDA ADC STA | ...
• implementace odčítání pomocí sčítání
  1. přepsání na sčítání: A - B -> A + (-B) -> A + NOT(B) + 1
  2. subtract w/ borrow (SBB) – carry je borrow
     • znamená, že si něco potřebuji půjčit z vyššího řádu
     • principiálně stejné jako normální sčítání
     • x86 to takhle dělá
     • problematické: v HW to není lehké implementovat
  3. subtract w/ carry (SBC) – carry je not borrow
     • pozor – nezapomenout na začátku pomocí SEC nastavit carry na !
     • snadněji se to HW implementuje
     • funguje na to hezký matematický trik:

1
2
3
4
5

A - X - B              // odečítání X a borrow od A
A - X - B + 256        // 256 je obecně n-bit
A - X - (1 - C) + 256  // použití carry flagu
A + (255 - X) + C
A + NOT(X) + C

x86

• více registrů = více svobody!
• slovo + address space
• obecné registry (7) – můžeme s nimi dělat, co chceme
  • v rámci zpětné podpory dovolují pracovat s prvními , , - …
  • lehčeji se řeší komplexní výrazy – a + b + e - (c + d)
    • u 6502 bychom museli pořád ukládat do akumulátoru (a dokonce ještě někam do paměti)
    • u x86 můžeme použít více registrů

Příklady instrukcí

• obecný tvar (assembleru): OP target, source
• MOV EAX, [EXP] – přesun z adresy na pozici hodnoty EXP do registru EAX
• MOV [EAX], EXP – přesun z EXP do paměti na adrese v EAX
• ADD/ADC – s/bez carry

Rychlost operací

• GHz – jednotka frekvence, ve které se měří rychlosti (moderních) procesorů
  • 1 takt…
• dnes už lze za 1 takt zvládnout základní instrukce – logické, aritmetické…
  • bavíme se čistě o operacích na registrech – přístup do paměti je významně pomalejší
• také záleží na tom, zda nesčítáme čísla na architektuře
  • když ale sčítáme na , tak je to také 1 takt

Čísla v Pythonu, vol. 2

• bloky paměti jsou vlastně (ne ), jelikož se očekává, že Python bude běžet (alespoň) na architektuře
• kolik zabírá x = 5 v Pythonu:
  • / (podle architektury), jelikož vše v Pythonu je objekt
  • samotného zápisu čísla
  • určující, kolik bitů je pro čísla využito
  • určující typ proměnné (číslo)
  • na reference counting – kolik proměnných ukazuje na hodnotu
    • je využíván garbage collectorem, aby vyhazoval z paměti to, co není používáno
  • musí se s tím provádět hrozně šaškáren, je to proto vážně pomalé (klidně až 100x pomalejší než jazyky jako C#)
• přičítání vytvoří nový objekt:
  • jelikož jsou inty immutable, tak a = 300; a += 1 vytvoří úplně nový objekt
    • lze otestovat tím, že na a voláme id(a) před a po přičtení
  • trochu záchrana – čísla od do jsou optimalizována (uložena někde v tabulce), jelikož se s nimi dost často počítá
• má to výhodu – nemusíme řešit arithmetic overflow (přetečení) nebo underflow (podtečení)
• ještě pozor: reálně je v každém bloku uloženo jen hodnot, jelikož poslední bit je chápán jako carry příznak (Python nevidí do procesoru)

Násobení a dělení

• trochu těžší instrukce – bývají pomalejší (je dobré s tím v algoritmech počítat):
  • násobení – 10 taktů
  • dělení – 10/100 taktů

• je potřeba to na architekturách, které to nemají, softwarově implementovat
  • násobení 2 je SHL; dělení 2 je SHR
    • násobení a dělení jinými čísly lze rozdělit na posuny a součty (pokročilé, nebrali jsme; je na to ale úžasná knížka Computer Systems: A Programmer’s Perspective)
  • pozor na signed čísla – SHL funguje jen pro menší čísla a SHR nefunguje vůbec (vytváří nuly)
    • je potřeba SAR (kopíruje MSb), ale pořád to není ono (-5 // 2 = -3)

Tomášova odbočka (příklady instrukcí)

• v rámci přípravy na zkoušku je naprosto super si zkusit generovat z Cčkových zdrojáků assembler:
  • na Linuxu gcc -g -c soubor.c; objdump -S soubor.o; dělá přesně tohle
  • pozn.: není to Intel syntax – pro ten je třeba k objdump přidat -d a --disassembler-options=intel

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#      int a = 5;
movl   $0x5,-0x14(%rbp)

#      int b = a + 5;
mov    -0x14(%rbp),%eax
add    $0x5,%eax
mov    %eax,-0x10(%rbp)

#      int c = ~a;
mov    -0x14(%rbp),%eax
not    %eax
mov    %eax,-0xc(%rbp)

#      int d = a * b;
mov    -0x14(%rbp),%eax
imul   -0x10(%rbp),%eax
mov    %eax,-0x8(%rbp)

#      int e = a - (b + c) - d;
mov    -0x10(%rbp),%edx
mov    -0xc(%rbp),%eax
add    %eax,%edx
mov    -0x14(%rbp),%eax
sub    %edx,%eax
sub    -0x8(%rbp),%eax
mov    %eax,-0x4(%rbp)
mov    $0x0,%eax

#      int f = a | (b & c) ^ d & e;
mov    -0x18(%rbp),%eax
and    -0x14(%rbp),%eax
mov    %eax,%edx
mov    -0x10(%rbp),%eax
and    -0xc(%rbp),%eax
xor    %edx,%eax
or     -0x1c(%rbp),%eax
mov    %eax,-0x8(%rbp)

#      int g = e << 10 + f >> 10;
mov    -0x8(%rbp),%eax
add    $0xa,%eax
mov    -0xc(%rbp),%edx
mov    %eax,%ecx
shl    %cl,%edx
mov    %edx,%eax
sar    $0xa,%eax
mov    %eax,-0x4(%rbp)
mov    $0x0,%eax

#      short g = f;
mov    -0x8(%rbp),%eax
mov    %ax,-0x1e(%rbp)

Reálná čísla

Fixed-point

• pevný počet bitů pro části před a za desetinnou čárkou
• hezky na tom funguje aritmetika – můžeme normálně sčítat, odčítat, porovnávat…
  • výrazně rychlejší než floating-point (viz dále)
• problém na operacích s hodně velkými a hodně malými čísly – přesnost…

Floating-point

• čísla v normalizovaném formátu:

• v mantise první 1 ignorujeme (je tam totiž v normalizovaném tvaru vždy)
• exponent je v bias reprezentaci: mapování
  • převody jsou přičítání/odčítání biasu
  • hodí se (později uvidíme proč)
• SW implementace by byla pomalá – bývá to podporováno v CPU
  • floating-point registry
  • stejně pomalejší než celá čísla

IEEE 754

• standard definující a floating point čísla
• pro (float) je
• pro (double) je
  • takhle je to ukládané v Pythonu

Ošklivá čísla

• nelze reprezentovat jako floating-point číslo (nekonečný dvojkový zápis)
  • programovací jazyky zaokrouhlují – nikdy floating point čísla neporovnávat, používat

Speciální hodnoty

• pro nulový exponent je číslo v denormalizovaném tvaru (pro reprezentaci fakt hodně malých čísel)
• jsou samé nuly (až na znaménko)
  • proto jsme volili reprezentaci s biasem
  • znaménko znamená, že máme 2 nuly, standard definuje oboje jako to samé
• samé v exponentu nabývá podle znaménka a mantisy speciálních hodnot ( , …):
  • ;
  • (not a number)
    • cokoliv + je
    • existuje více typů (podle vzniku)
  • bývá v normálních jazycích , Python ale kontroluje dělení nulou a hodí chybu

Paměti ROM

• jsou non-volatile – hodnoty přežijí vypnutí počítače

• EPROM – problém s mazáním (dělá se to s UV zářením… nepraktické)
• EEPROM – všechno tím nahradit nechceme, je pomalejší než RAM
  • také jim lze říkat NVRAM (non-volatile RAM)
  • omezený počet writů kvůli tomu, že fyzikálně se elektrony připojí do obalu atomů a nejdou pak moc dobře vytlačit
  • adresovatelné po individuálních bytech
  • flash – jiná výrobní technologie
    • dokáže zapsat/vracet velké bloky – /
    • rychlejší na přístup k většímu počtu dat, pomalejší na random přístup

• GPIO = General Purpose Input and Output
  • slouží jak pro vstup, tak pro výstup
  • DIR registr určuje směr pinů, IN a OUT jsou hodnoty na vstupu/výstupu

Permanentní datové úložiště

HDD

• jsou magnetické
• sektor – dnes (dříve )
• hlavičky – pohybují se všechny najednou
• disk se otáčí, hlavičky se hýbají do strany – podle toho přístup k bytům
• adresa hodnoty je trojice CHS (cylinder, head, sector)
• přístup vně je lepší – rychlost sektorů dále od středu je větší
  • zaplňují se od vnějších po vnitřní

Výhody

• levnější než alternativy
• velké množství dat

Nevýhody

• náchylné na poškození
• sekvenční přístup je fajn (disk se otáčí), obrácený je příšerný
• docela pomalé… sekvenční / obrácený sekvenční

CD / DVD / BLURAY

• jsou optické – pokud se světlo odrazí, tak ; jinak
• nejsou optimální pro archivační účely – vrací se do svého původního stavu
• oproti pevným diskům jsou data ukládána do spirály (stejně jako gramofonová deska)

• používají LBA – logical block addressing (není to už trojice – lehčí na programování)
• přenosová rychlost je menší ( ), přístupová také ( )

Řadiče pro úložiště

• registry:
  • adresový
  • příkazový
  • buffer (pro postupné ukládání dat pro čtení/zápis)
  • info (počet sektorů, velikost sektoru…)
• bylo by nepraktické používat pro každé zařízení jiný protokol – pro všechny se tedy používá LBA, jen tam jsou vždy pro příslušná zařízení převody:
  • pro HDD dochází k mapování LBA CHS
  • takhle připojený flash disk je vlastně SSD (Solid State Drive)

Adresování, soubory

• offset (v ) – posun od začátku paměti
• base address – odkud začínáme (čteme/píšeme/…)

• metadata – data o datech; ukládá:
  • čísla sektorů, kde se soubor nachází
    • princip fragmentace – rozdělení souborů do více sektorů; nechtěné (přístup je pomalejší)
  • jméno souboru
  • velikost
  • obecně: volné sektory
• OS – abstrakce nad disky
  • stejné API pro čtení, psaní, práci s metadaty…
  • používají všechny programy – open() volá (C-čkovou funkci, která volá) systémovou funkci

V Pythonu

Soubory

• otevření: with open("<path>", "<mode>", encoding="<encoding>") as f:
  • path je cesta k souboru
  • mode je podle toho, co chceme dělat (v tomhle kurzu ale většinou chceme rb):
    • r – čtení
    • w – psaní
    • b – je to binární soubor
  • když nespecifikujeme encoding, tak použije kódování typické pro daný OS
    • Windows – Windows-1250 (encoding="windows-1250")
    • Linux – (asi) UTF-8 (encoding="utf-8")
    • funguje také např. ASCII (encoding="ascii")
• f.readline() – čtení jednoho řádku
• f.read(<bytes>) – čtení daného počtu bytů; volání bez parametru přečte vše
  • může vrátit méně, když toho tam tolik není
  • pozor! u b módu vrací bytes, jinak str
• f.seek(pos) – nastavení offsetu od začátku souboru (v bytech)
  • čtení ho mění
  • f.seek(pos, mode) definuje způsob posunu
    • : posun od začátku souboru (default)
    • : posun od aktuální pozice
    • : posun od konce souboru

Byty

• <str>.encode("<encoding>") – str -> bytes
• <bytes>.decode("<encoding>") – bytes -> str
• bytes je immutable (nelze měnit) – je potřeba použít bytearray (bytearray(<size>))
  • lze převádět z bytes vcelku přímočaře: bytearray(<bytes object>)

Šestnáctkový výpis

• hex view(er) – vypsání souborů jako šestnáctkové byty
  • na Linuxu:
    • xxd <soubor>; obrácený převod xxd -r <soubor>
    • hexdump <soubor> -C
• pozor – = 2 znaky
• 3 sloupečky (tradičně po 16 znacích – dobře se počítá pozice):
  1. hex offset (pozice v souboru)
  2. hex zápis (AF 1F 3C 14 ...)
  3. pokus o interpretaci dat jako text (nezná encoding…)

Reprezentace obrazu

• bitmapy – mapy bitů
• rozdělíme na pixely – na každém bude informace o tom, „jaké je tam světlo“

• indexováno
  • pozor – jdoucí dolů stoupá, neklesá
• v paměti bývá uloženo po řádcích

Pixel

• co sem uložit? fotonů máme od do
  • je třeba (dobře) stanovit meze (analog digital) – mapování intenzit
• bit depth (bpp = bitová hloubka) – kolik dat máme na pixel:
  • – černobílá
  • – odstíny šedi
  • floating pointy – větší rozsah (HDR)
    • problémy: lidské oko to neumí dobře zpracovávat a foťáky to neumí dobře fotit
• není foton jako foton: frekvence určuje barvu
  • vnímáme malé spektrum (viditelné světlo)
  • tyčinky (rozsah) x čípky (frekvence – 3 barvy)

• barevná bit depth:
  • na pixel – dost neúsporné (jen jestli je červená/zelená/modrá) a blbě se rozděluje
  • na pixel – poslední je intenzita (1 násobí vše 2x)
  • na pixel – 5R/5G/5B/1 nic
    • někdy ten 1 bývá v zelené složce (oko je na ni citlivější)
  • na pixel (true color; 16777216 barev)
    • je to ošklivě nesoudělné; ukládá se většinou do … co se zbylými ?
      • plýtvat
      • použít na alpha kanál určující (ne)průhlednost pixelu (255 je neprůhledné, 0 transparentní)

Ukládání do paměti

• nestačí je jen uložit za sebe – potřebujeme metadata (obrázku, ne souboru), jako např.:

  1. bitová hloubka
  2. výška, šířka
  3. pořadí barev (endianita) – RGB(A) / (A)BGR (populárnější)
  4. offset, na kterém začínají data

• obecně metadata (hlavička) bývají na začátku souboru, abychom je přečetli první

BMP

• původně Windows formát
• relativně jednoduchý
• data jsou little endian (jak čísla, tak barvy)
• první jsou magic (signature) znaky
  • měly by být unikátní pro typy souborů
  • dány autorem
  • zajímavost – exe má 4d 5a, což je v ASCII MZ – iniciály Marka Zbikowskiho (autor)

Reprezentace textu

• string – posloupnost znaků
  • písmena (abcdefgh)
  • číslice (123456789)
  • symboly (@#$%^&*)
  • whitespace (mezera, tabulátor)
• grafém – nejmenší jednotka psaného jazyka
• kódování (většinou pro celý text) zavádí:
  1. 1 znak 1 kód (číslo)
  2. kód binární reprezentace
     • zda bude 1 kód = , , proměnlivý…
• ukládání do paměti tak, jak by se text četl (latinka levo-pravo, arabština pravo-levo…)
• historicky nemívá metadata – problematické (určování kódování)

ASCII

• American Standard Code for Information Interchange
• standardizování v 60. letech
• kódování ( - )
• číslice i písmena jsou v kódování blízko sebe – lze je dobře vyčíst, převádět…
• extended – rozšíření
  • každá část Evropy (W/M/E) si to rozšířila jinak
    • ISO8859-2 (Latin 2) – snaha o standardizaci, ale trochu pozdě
    • Win1250 – Windowsové kódování

Unicode

• standardizace – všechny jazyky, všechny symboly, žádné problémy
• - – odpovídají kódům z ASCII
• - – běžně znaky
• problém – neurčili binární reprezentaci, takže vznikly různé:
  • UTF-32 – každý znak je
    • 2 verze UTF-32 LE a UTF-32 BE… guláš
    • paměťově ne moc příjemné
  • UCS-2 – jednoduché (a debilní)
    • podporuje pevné … dokážeme reprezentovat pouze znaky v téhle mezi
  • UTF-16 – proměnlivá délka znaku ( / )
    • 4B… surrogates (náhradníci): pro určité hodnoty prvních musí být přečteny druhé
      • výsledek se dohromady skládá magií
    • nelze přesně říct, kolik znaků je v souboru s tímhle kódováním uloženo
    • také varianty LE a BE
  • UTF-8 – , , , znaky
    • – první bit je
    • – prvních bitů je , ten za tím (pro je to )
      • každý další byt začíná – lehce lze zjistit, že jsou součástí nějakého znaku
    • neřeší se endianita – jsou to prostě velká čísla
    • populární na internetu

Rasterizace

• string bitmapa
• potřebujeme rozeznávat, kdy skočit na další řádek… každý systém to řeší jinak:
  • původně CR (carriage return) + LF (line feed) (z psacích strojů)
    • zachovalo se pro Windows
  • Unix si zvolil LF
  • Mac OS si zvolil CR (moderní ale už používají LF)
  • Unicode – 2 nové znaky… LS (line separator) a PS (paragraph separator)
    • naprosto vůbec se to nechytlo, je v tom ještě větší guláš

Dokončení rozdělané magie

• bridge – řadič, který hostu zpřístupňuje jinou sběrnici
• memory controller – middle man mezi pamětí a CPU
  • řeší refresh u DRAM
  • maskuje to, že máme 1GB a 512MB paměť – linearizuje to pro CPU

Systémová sběrnice

• PCIe
  • sériová
  • jsou na tom všechna zařízení; na packet reagují jen ta, pro která je určený
  • 2 dedikované druhy packetů (memory write, memory read)
    • jen memory controller reaguje na tenhle packet
    • není tam adresa zařízení, ale paměti
  • příklad:
    1. CPU pošle MRd (Memory Read packet)
       • cílová adresa je adresa paměti
       • musí tam být uložena i adresa procesoru, aby mohl přijít packet zpět
    2. memory controller vykoná požadavek, pošle CplD (Completion with data)
       • cílová adresa je adresa procesoru (aby to došlo správnému procesoru)

Memory/mapped I/O [wiki]

• princip používání stejného adresového prostoru jak pro paměť, tak pro I/O
  • pro I/O jsou mapovány nějaké části paměti, které jsou volné
  • je potřeba, aby adresy byly unikátní

Co dělat po startu?

• CPU startup vector – odtud procesor začíná vykonávat instrukce
  • hardkódované v CPU (např. )
    • bývá tam v paměti skok někam, kde se instrukcí vejde více
• firmware ROM – paměť (non-volatile), kde je uložený program, který po startu dělá:
  1. test a konfigurace HW
     • mapování (nekonfliktních) adres pro zařízení
  2. hledání užitečného softwaru (bootování)
     • další ROM – option ROM
       • mívaly starší systémy
       • bootuje instantně (je to ROM…)
       • princip cartridgových her – instantní spuštění
       • bývá např. u grafických karet – počáteční nastavení
     • pevný disk – mívá boot sector, který je uzpůsobený k načtení do paměti a spuštění
       • je tu tzv. bootloader – menší prográmek, který hledá na disku zbylá data
         • dnes většinou načítá kernel – převezme základní funkce FS, načte zbytek OS…
  3. implementuje funkce pro bootování – načti sektor, znak z klávesnice, vykresli něco…