První série třicátého ročníku KSP

Termín odeslání Vašich řešení této série jest určen na 30. října 2017 (seriál 13. listopadu 2017). Řešení můžete odevzdávat jak elektronicky, tak klasickou poštou na známou adresu.

Dotazy ohledně zadání můžete posílat na adresu ksp@mff.cuni.cz, nebo se ptát přímo na diskusním fóru KSP.

Odměna série: Sladkou odměnu pošleme každému, kdo vyřeší tři libovolné úlohy na plný počet bodů.

Zadání úloh

To snad není pravda! Já jsem věděl, že není dobrý nápad začínat další ročník KSP takhle těžkou úlohou. Zadání jsem si přečetl před čtyřmi dny, neustále jsem nad ním přemýšlel, ale řešení ne a ne přijít. Já snad upíšu svoji duši ďáblu, aby mi aspoň trochu poradil.

Kupodivu se zdá, že se mi skutečně taková příležitost naskytne. Ráno jsem v e-mailu mezi zásobami spamu objevil podivnou zprávu:

Nápovědy od pana Nápovědy! Vyřešíme i váš algoritmický problém. Ulice Na Větru, jsme tu 24 hodin denně.

Chtěl jsem zjistit, kdo to ten pan Nápověda vlastně je. Zkusil jsem ho hledat podle e-mailu v nějaké veřejné online databázi osob. Nic jsem ale nenašel, akorát jsem odhalil, že celá databáze je pořádně rozbitá.


Teoretická úloha30-1-1 Oprava databáze (7 bodů)


Máme databázi osob, kde každý záznam obsahuje jen dva údaje: jméno osoby a její e-mail. V databázi jsou ale chyby a existuje mnoho záznamů buď se stejným e-mailem, nebo se stejným jménem.

Správci databáze se konečně rozhodli nepořádek vyřešit a pro každou osobu, která je v databázi, chtějí zjistit, kolik záznamů tam vlastně má. Platí, že kdykoli se dva záznamy shodují ve jméně nebo v e-mailu, patří stejné osobě.

Příklad: Záznamy Pepa <pepa@example.com>, Josef <pepa@example.com>Josef <josef@example.com> všechny patří jedné a té samé osobě.

Řešení

Nakonec jsem to nevydržel a do ulice Na Větru jsem se opravdu vypravil. Dorazil jsem tam až pozdě večer a na první pohled se nezdálo, že by liduprázdné místo nabízelo cokoliv zajímavého. Udělali si ze mě legraci, pomyslel jsem si zklamaně. Chtěl jsem odejít, ale pak jsem si všiml zvláštní telefonní budky na konci ulice.

Na první pohled vypadala docela obyčejně, ale uvnitř měla zvláštní panel: místo číselníku obsahoval padesát očíslovaných tlačítek a nad nimi byl displej, na kterém teď svítil nápis: „Pro Napovedu vlozte minci“. Tak vida! Vytáhl jsem z peněženky korunu a vhodil ji do automatu. „Nejdriv 3, potom 15“, objevilo se na displeji. Schválně zkusím další korunu. „Nejdriv 22, potom 38“, změní se text. Asi chtějí, abych ta tlačítka stisknul v nějakém pořadí, ale kolik mincí budu muset spotřebovat, abych to pořadí zjistil?


Teoretická úloha30-1-2 Telefonní hlavolam (10 bodů)


Aby se náš hrdina dostal k panu Nápovědovi, musí ve správném pořadí stisknout N tlačítek, očíslovaných od jedničky do N, přičemž každé tlačítko se stiskne právě jednou a existuje jen jedno správné pořadí. Naštěstí nám protistrana posílá řadu dvojic čísel, kde dvojice (I,J) znamená, že číslo I ve správném pořadí přijde před číslem J (nemusí však být těsně vedle sebe).

Dohromady dostaneme až M dvojic a je zaručeno, že dohromady nám dvojice jednoznačně určují pořadí (protistrana není nikterak zlomyslná). Za každou další napovězenou dvojici si ale musíme zaplatit, takže bychom chtěli najít správné seřazení na co nejmenší počet dvojic (dvojice dostáváme v nějakém náhodném pořadí).

Příklad: Pro N = 4 se protistrana rozhodla, že nám postupně napoví dvojice (2, 1), (3, 4), (3, 2), (4, 1), (2, 4)(3, 1). Správné pořadí je 3, 2, 4, 1 a je jednoznačně určené po pěti nápovědách – o poslední nápovědu tedy už nemusíme žádat.

Řešení

Uf, mince mi vystačily jen tak tak. Naťukám správné pořadí, displej vítězoslavně zabliká a telefon začne zvonit. Zvědavě zvednu sluchátko.

„Je tam pan Nápověda?“ ptám se. „Výborně, jste docela schopný,“ dostanu odpověď. „Bude jistě lepší, když se uvidíme osobně. Zítra dopoledne, pražská ZOO, pavilon hrochů. Těšte se, poradím vám,“ řekne úsečně a zavěsí. Jsem nadšený, člověk, který si dělal práci s hádankou v telefonní budce, mi určitě dokáže poradit! Ale asi byl bych o něco méně nadšený, kdybych si na konci hovoru všiml jemného zachechtání.

* * *

Do ZOO jsem dorazil brzy ráno, ale v pavilonu hrochů se dlouho nic nedělo. Sledoval jsem přicházející návštěvníky, a hádal, kdo z nich bude muž, se kterým jsem včera mluvil. Pak mně najednou někdo vezme za rameno. „Kdo jste?“ leknu se a podívám se na něj. Je to nějaký vysoký člověk, tváří se udýchaně a nervózně. „Já jsem řešitel KSP“, zakoktám. „Vy jste pan Nápověda?“ „Ještě aby tohle,“ ušklíbne se dlouhán, „Hned pojď se mnou!“ řekne mi. Překvapivě nejdeme k východu, ale k nějakým špinavým dveřím, které určitě nejsou určené pro návštěvníky.

„Rychle ti vysvětlím situaci. Já jsem Jirka, organizátor KSPčka. Můžeš být rád, že ses panu Nápovědovi nedostal do spárů,“ vysvětluje, zatímco probíháme místnostmi obloženými krmením pro hrochy. „Chtěl jsem od něj řešení jedné úlohy,“ přiznám se. „Stejně jako spousta řešitelů před tebou! Nalákal je na pomoc při řešení nějaké úlohy, a teď pro něj píšou programy v jeho bunkru.“ Vyběhneme ven na malý dvorek, uprostřed kterého stojí zaparkovaný červený Volkswagen.

Jirka stiskne ovladač centrálního zamykání. Auto se nejenom odemkne, ale taky se mu bleskurychle automaticky otevřou dveře. „Nejnovější vychytávka,“ ušklíbne se. „Rychle, sedni si dopředu! Snad ještě Nápověda nezjistil, kde jsme.“ Nastoupíme, nastartujeme, dveře se samy zabouchnou a auto vyrazí dopředu, až se mu protočí kola.

„Otevřete nám, okamžitě“ volá Jirka do vysílačky. Odloží si ji na přední panel, pokrytý mnoha dalšími zařízeními, o jejichž funkci nemám tušení. Neskutečně rychle se proplétáme mezi ohradami s exotickou zvěří a najednou se před námi vynoří kovová vrata. Naštěstí je právě otevírá jakýsi zaměstnanec ZOO – jenže není dost rychlý. Proletíme branou a ozve se křupnutí, protože jsme právě přišli o boční zrcátka.

„Měli jsme mu zaplatit víc,“ zamumlá Jirka. „Víš, ve skutečnosti jsi nám dost pomohl. Nápověda totiž udělal chybu a při domlouvání tvého únosu použil mobilní síť. Takže teď víme, kde se jeho bunkr nachází.“ „Vy odposloucháváte mobilní síť?“

„Ne že by to byl takový problém,“ ozve se za mnou. Teprve teď si všimnu kluka v oranžovém tričku, který je usazený na zadním sedadle, na klíně má položený notebook a v uších sluchátka. „Já jsem Filip, taky org. Vypadáš trochu vyděšeně. Teď se musíš sebrat. Nechceš něco ostřejšího?“ ptá se. „Jako myslíš alkohol?“ Zatřese hlavou, podá mi kalíšek a nalije do něj z termosky tmavě hnědou tekutinu. „Dlouho louhovaný Puerh. To má povzbuzující účinky i na mrtvolu.“


Teoretická úloha30-1-3 Placení v čajovně (12 bodů)


Filip si před zátahem na Nápovědu kupuje Puerh ve svém oblíbeném čajovém obchodě. Protože má v peněžence mnoho drobných, chtěl by se jich zbavit, zvláště těch nejtěžších mincí.

Celková cena čaje je H korun. Existuje N různých mincí o hodnotách H1, … , HN a hmotnostech M1,… ,MN. Zároveň víme, kolik mincí každého druhu má Filip v peněžence.

Prodavači musíme dát mince celkové hodnoty alespoň H. Pokud nemáme přesnou částku, tak nám vrátí, ale vždy nejtěžší možnou sadou mincí. Zároveň platí, že můžeme zaplatit K mincemi a prodavač vrátí maximálně L mincí.

Na základě znalosti všech parametrů vyberte mince, kterými má Filip zaplatit, aby měl na konci transakce co nejlehčí peněženku.

Řešení

„Nabereme Janku a jedeme do bunkru,“ vysvětlí mi Filip, zatímco Jirka kličkuje po pěší zóně a snaží se nesrazit ani chodce, ani tramvaj. „Nápověda je dost schopný, ale teď zůstal v ZOO. Musíme se do bunkru dostat dřív než on a osvobodit všechny uvězněné řešitele.“

Pořád mám trochu vyražený dech. „Tak co vlastně jste? Orgové KSPčka, nebo tajní agenti?“

„Obojí,“ řekne a znuděně zazívá. „Potom, co nám začal pan Nápověda dělat problémy, jsme zjistili, že si s ním policie neumí poradit. A řekli jsme si, že být tajným agentem není v zásadě o tolik hektičtější, než třeba organizovat soustředění.“

Odněkud vytáhne další notebook a podá mi ho. „Najdeš tam soubor s mapou bunkru. Napiš mi program, který v něm dokáže najít cestu, ať nám jsi k něčemu užitečný.“


Praktická opendata úloha30-1-4 Cesta v bunkru (15 bodů)


Pan Nápověda se rozhodl vystavět svůj bunkr jako nejdokonalejší bludiště na světě. Jeho zdi mají tvar Hilbertovy křivky, což je jistá křivka procházející všemi body roviny. Aby bludiště dokázal v konečném čase postavit, musel místo opravdové Hilbertovy křivky použít její aproximaci určitého konečného řádu r≥ 1.

Mapu bunkru si můžeme nakreslit jako čtvercovou síť velikosti (2r+1+1)×(2r+1+1) políček, přičemž políčka ležící na Hilbertově křivce tvoří zdi a ostatními políčky je možné procházet. Bludiště řádů 1, 2 a 3 vypadají následovně:

Hilbertova bludiště řádů 1, 2, 3

Z obrázku je také vidět, jak se křivka obecně konstruuje: Křivka řádu r+1 vznikne ze 4 kopií křivky řádu r, které vhodně natočíme a pospojujeme šedými políčky.

Vaším úkolem bude nalézt v Hilbertově bludišti nejkratší cestu mezi zadanými dvěma políčky. Například mezi políčky (6,6)(6,10) obsahuje nejkratší cesta 41 políček a vypadá následovně:

Nejkratší cesta v Hilbertově bludišti

Toto je praktická open-data úloha. V odevzdávacím systému si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu: Vstup má jediný řádek. Na něm se nachází pět mezerou oddělených čísel: řád Hilbertovy křivky (1≤ r≤ 30), dvojice souřadnic počátečního políčka a dvojice souřadnic cílového políčka. Souřadnice se skládají z čísla řádku (číslováno shora od 0) a čísla sloupce (číslováno zleva od 0).

Formát výstupu: Výstupem je jediné přirozené číslo: počet políček na nejkratší cestě mezi zadanou dvojicí políček.

Příklad: Předchozímu obrázku odpovídá vstup 3 6 6 6 10 a výstup 41.

Řešení

Naštěstí se mi napsat program podařilo docela rychle, právě ve chvíli, kdy jsme se blížili ke dvěma vzrostlým věžákům. Zajeli jsme do průjezdu, kde na nás čekal další organizátor. Tedy, vlastně organizátorka.

„Vyrušili ste ma pri opravovaní úloh, zasa nestihneme termín,“ řekla nespokojeně, ale stejně se usmála. „Podarilo sa mi pripojiť sa na sieť bunkru.“ „Takhle rychle?“ řekl Jirka nadšeně. „Nie je to komplikovanejšie ako web KSPčka,“ odpověděla, sedla si dozadu k Filipovi a požádala ho o kalíšek Puerhu. „Teraz tam len vypustiť môj obľúbený vírus.“


Teoretická úloha30-1-5 Zavirování sítě (10 bodů)


Janky oblíbený virus infiltruje počítačovou síť. Předpokládáme, že síť je stromem, kde vrcholy jsou počítače a hrany jsou propojením mezi počítači. Na začátku si vybereme několik počítačů, které nakazíme virem. Následně se virus může šířit a platí, že počítač se nakazí, pokud alespoň polovina počítačů, se kterými je propojený, je nakažena.

Najděte, kolik nejméně počítačů musíte nakazit (popřípadě které), aby se v dalších krocích postupně nakazily všechny počítače.

Příklad: Následující graf se dá vyřešit nakažením jednoho (jakéhokoliv) vrcholu, z něj se nákaza rozšíří na všechny stroje.

Graf: cesta o délce 5

Řešení

Jirka už zase vyrazil na cestu. Opouštěli jsme centrum Prahy a před naší přední kapotou se vynořovaly obrysy nějakého sídliště. „Sem matfyzáci obvykle jezdí na tělocvik, a ne zachraňovat středoškoláky,“ řekl Jirka, když jsme se skřípěním brzd zastavili u budovy s nápisem Sportovní centrum. „Nejradši bych prorazil tu skleněnou stěnu a vjel přímo k bazénu.“ „Nie, teraz musíme byť nenápadní,“ poprosila ho Janka. Vypadala, že ji ta myšlenka vylekala. „Musím zostať tu, ten vírus zatiaľ akosi nefunguje.“

Filip, Jirka a já jsme vešli do budovy a zamířili si to ke vchodu do bazénu. „Té paní u recepce se bojím víc než Nápovědy,“ zašeptal Filip. Ale zdálo se, že Jirka je na celou situaci připravený. Přišel k recepční a aniž by cokoliv řekl, nakreslil na pult nějaký tajemný symbol. Znuděně vypadající žena najednou ožila. Ze skříně vytáhla balíček karet, zamíchala ho a rozložila deset karet na pult. Na každé z nich bylo celé číslo.

„To je jeho další hádanka,“ řekl Filip. Přišel blíže k pultu a začal si karty pozorně prohlížet. „Vy jste se asi necvičili v xorování, že ano?“


Teoretická úloha30-1-6 Karetní hlavolam (9 bodů)


Nápověda si rád ověřuje bystrost svých studentů podle toho, jak rychle dokáží provádět binární operace s celými čísly. Jednou z těchto operací je xor, známý též jako „exkluzivní nebo“ a značený .

Pokud chceme spočítat xor dvou (kladných celých) čísel A a B, nejprve obě převedeme do dvojkové soustavy. Jednotlivým cifrám dvojkového zápisu říkáme bity a číslujeme je od nuly zprava: poslední cifra je nultý bit, předposlední je první bit atd.

Výsledek dostaneme opět ve dvojkové soustavě, a to následovně: i-tý bit výsledku je 1 právě tehdy, když jsou i-té bity čísel A a B různé.

Příklad: spočítáme 26 ⊕6 (uprostřed jsou čísla přepsaná do binární soustavy):

26       = 11010
6        = 00110
26 xor 6 = 11100 = 28
Takže 26 ⊕6 = 28

Recepční na stůl vyloží N karet, na každé kartě je kladné celé číslo. Úkolem je najít dvojici karet s takovými čísly A a B, že hodnota A⊕B je největší možná.

Řešení

Zřejmě se Filipovi podařilo hádanku vyřešit správně, protože žena se usmála a položila na stůl klíč s visačkou s číslem. „Běžte do šatny,“ řekla. Tam odemkneme příslušnou skříňku a já vydechnu překvapením. Netušil jsem, že do obyčejné šatní skříňky se dá schovat výtah pro přepravu osob! Tedy, ve skutečnosti jen jedné osoby, víc se tam nevejde. Nápovědův bunkr je schovaný někde pod zemí a tohle je vchod.

* * *

„Ani se nehýbejte,“ ozvalo se ostře za námi. To snad není pravda. Mohli jsme být v bunkru snad pět minut a jsme chyceni! Pan Nápověda, prošedivělý stařec, byl za našimi zády. Ohlédli jsme se a strnuli, protože držel v ruce revolver a mířil na nás.

„Nic se nestane, nebudu vás zabíjet,“ ušklíbne se, „potřebuji další mozky pro svůj tým programátorů.“ „Jak jste se sem dostal tak rychle?“ ptá se Jirka a zdá se být skoro naštvaný z toho, že se sem ze ZOO dokázal dopravit rychleji někdo jiný než on. „Jednoduše! Zachytil jsem vaše auto, už když jste tam přijížděli.“ Jsme v háji, už tu zůstanem navždycky, proběhne mi hlavou.

Než stihneme cokoliv udělat, vyjede mezi námi a Nápovědou skleněná stěna. Nápověda se ale kupodivu zatváří překvapeně. „To jsem nebyl já,“ zamumlá. A najednou se ozve dunivý výbuch a chodbu za Nápovědou začne rychle zaplavovat voda. „Rýchlo zmiznite!“ ozve se z interkomu, nebo něčeho podobného. „Dvere vľavo, vpravo a hore po schodoch,“ upřesní hlas. Na nic nečekáme: chodba za skleněnou stěnou je téměř po strop zaplavená a samotná stěna to asi také dlouho nevydrží. Běžíme pryč podle instrukcí a najednou jsme zpátky na denním světle. Vyšli jsme u bazénu – nebo přesněji u toho, co z bazénu zbylo. Byl prázdný, všechna voda odtekla do bunkru přes díru v jeho prostředku.

„Chalani, vy si to tak komplikujete,“ přijde k nám Janka. Za ní jsou osvobození řešitelé, kteří teď překvapeně mžourají do denního světla. „Ak by ste boli opatrnejší, nemusela som robiť takú katastrofu.“ „Ale pan Nápověda je poražený…“ řekne Filip. Najednou mu ale pípne mobil a na displeji se objeví zpráva:

Porazili jste me imperium, ale ja se nevzdam. Uvidime se v Tokiu!

A takhle to v týmu organizátorů chodí. Občas musíte opravit úlohu, občas nestíháte a občas musíte jet zneškodnit schopného padoucha až do Japonska. Ale pokud jsi jenom účastník a nevyužiješ nějaké pochybné známosti, aby vyřešila úlohu za tebe, nemáš se čeho bát. Ačkoliv, i řešit KSP je taky někdy pořádná jízda!

Kuba Maroušek


Seriálová úloha30-1-7 Assembler (15 bodů)


V letošním seriálu se ponoříme hlouběji do nitra nejen našich počítačů a notebooků, ale i chytrých mobilních telefonů, a nahlédneme pod křemíkovou pokličku procesorů. Naučíme vás, jak vlastně vypadají příkazy, které procesor umí provádět, zkusíme si něco pomocí nich naprogramovat a povíme si i něco o paralelním počítání. Teď ovšem nepředbíhejme a začněme hezky od začátku…

0xE3A00001 nebo mov r0, 1

Procesor si můžeme představit jako takovou malou krabičku, která krok za krokem čte instrukce a každou z nich vykoná. Všechny tyto instrukce musí být nějakým způsobem „zadrátované“ v procesoru, a tak nás asi nepřekvapí, že tam nenajdeme složité instrukce typu spočítej faktoriál nebo nakresli hrocha, ale mnohem jednodušší instrukce. O to rychleji je však procesor dokáže vykonávat: typický dnešní procesor jich zvládne přes 2 miliardy za sekundu!

Instrukce musíme procesoru předávat v nějakém formátu, kterému rozumí. Protože počítače si již od počátku lépe rozumí s čísly než se slovy, i instrukce jsou pro procesor zakódované pomocí čísel. To, jaké číslo znamená kterou instrukci, se může u jednotlivých procesorů značně lišit. Proto existují instrukční sady, což jsou pevně dané předpisy, jaké číslo odpovídá jaké instrukci. Pokud jste někdy slyšeli pojmy jako x86, ARM, PowerPC nebo MIPS, to všechno jsou instrukční sady. Díky tomu dva x86 procesory chápou instrukci číslo 123 identicky nehledě na to, jestli jsou od Intelu či AMD.

I když počítače lépe rozumí číslům, u lidí tomu tak zdaleka není. Schválně, dokážete z následujících čísel v šestnáctkové soustavě aspoň trochu vytušit, co by ARMový procesor provedl?

  0c 00 a0 e3
  2a 10 a0 e3
  91 00 03 e0

Pokud nemáte tušení, nebojte. Protože to nešlo většině lidí, velmi záhy stvořili assemblery. No posuďte sami, nečte se tohle lépe?

  MOV  r0, #12
  MOV  r1, #42
  MUL  r3, r1, r0

Pokud si spojíte MUL se slovem multiply, možná i odhadnete, že tento program vynásobí 12 a 42, i když jste nikdy žádný assembler neviděli. Assemblery nám tedy ve své nejjednodušší podobě umožňují zapsat instrukce pro člověka čitelnějším způsobem. Assembler se však stále před použitím musí tzv. assemblovat, neboli přeložit do číselné podoby instrukcí, kterou jsme viděli dříve.

V celém našem seriálu se budeme věnovat procesorům z rodiny ARM. Rodina ARM zahrnuje několik architektur, neboť si ARM postupně prošel několika verzemi, jejich koncepty jsou však na úrovni assembleru naštěstí velmi podobné, takže by nás neměla jiná verze ARMu zaskočit. Tyto procesory najdete ve většině chytrých telefonů a tabletů a například i v Raspberry Pi.

Protože většina z vás asi nemá v šuplíku ARMový procesor, na kterém byste mohli testovat svá řešení úložek, připravili jsme si pro vás jednoduchý simulátor. Ten najdete na adrese http://ksp.mff.cuni.cz/viz/asm.

Čísla, čísla, čísla…

Zatímco počítače umí pracovat s nejrůznějšími typy dat (textem, obrázky, zvukem, …), jejich procesory zvládnou zpracovávat jenom čísla. A navíc ta čísla nesmí být moc velká. Typický procesor pracuje najednou buďto s 32-bitovými nebo 64-bitovými celými čísly. My si budeme povídat o jedné ze starších verzí architektury ARM, která je 32-bitová. Práci s čísly si nicméně pro větší názornost předvedeme na 8-bitových číslech.

Nejprve se podíváme, jak se ukládají přirozená (celá nezáporná) čísla; říká se jim také čísla bez znaménka. Procesor je ukládá ve dvojkové soustavě, v každém bitu je uložena jedna číslice dvojkového zápisu. Například číslo 42 bychom zapsali jako 0010 1010 (protože 42 = 25 + 23 + 21). Řády bývá zvykem oddělovat po čtveřicích, nebo ještě lépe číslo místo ve dvojkové soustavě zapisovat v šestnáctkové (hexadecimální; s číslicemi 0 až 9 a a až f). Čtyři dvojkové číslice totiž odpovídají právě jedné šestnáctkové. Šestnáctkové zápisy se obvykle uvozují znaky 0x, takže číslo 42 bychom zapsali jako 0x2a.

Bity čísla číslujeme od 0 do 7, nejnižší řád má číslo 0, nejvyšší 7; i-tý bit má tedy váhu 2i. Nejmenší 8-bitové číslo je tudíž 0000 0000 = 0, nejvyšší 1111 1111 = 20 + 21 + … + 27 = 28 - 1 = 255.

Pokud při sčítání čísel dojde k přetečení, čili výsledek se nevejde do 8 bitů, pak přebytečnou část výsledku prostě odřízneme. To je totéž, jako kdybychom řekli, že počitáme modulo 28. Například:

175 + 85 = 1010 1111 + 0101 0101 = (1) 0000 0100 = 4.

Odčítání také probíhá modulo 28, takže kdyby mělo vyjít záporné číslo, přičteme k prvními číslu 28, aby výsledek vyšel kladný. Třeba takto:

2 - 4 = (1) 0000 0010 - 0000 0100 = 1111 1110 = 254.

V posloupnosti sčítání a odčítání se tedy nemusíme o přetékání starat: dokud víme, že výsledek se vejde do 8-bitového čísla, vyjde správně.

Také si všimněme, že číslo 254 se chová stejně jako -2. To ostatně dává smysl, neboť tato dvě čísla se liší o násobek 28, takže jsou modulo 28 stejná. Toho můžeme využít k reprezentaci záporných čísel. Jen by se nám občas hodilo, abychom uměli poznat záporné číslo od kladného.

Proto zavedeme reprezentaci čísel se znaménkem pomocí dvojkového doplňku. Nejvyšší bit nám poslouží jako znaménkový bit: bude-li nulový, ukládáme nezáporné číslo obvyklým způsobem (bude tedy v rozsahu 0 až 127). Čísla s jedničkou ve znaménkovém bitu budeme považovat za záporná: 1111 1111 bude znamenat -1, 1111 1110 = -2, … až 1000 0000 = -128. Ukládáme tedy o 256 více, než je hodnota záporného čísla. Dohromady proto dovedeme ukládat všechna čísla od -128 do 127.

Dodejme ještě, že sčítání a odčítání funguje úplně stejně pro čísla se znaménkem jako bez znaménka: obojí pracuje modulo 28, jen si pokaždé výsledek vykládáme různě. Násobení a dělení už ale musí znaménka brát v úvahu.

Škatulata, hejbejte se

Procesor si čísla, se kterými zrovna pracuje, potřebuje někde pamatovat. K tomu slouží registry. Registry našeho ARMu jsou 32-bitové a je jich celkem 16. Prvních 13 z nich se jmenuje r0, r1, …, r12 a jsou general purpose (tedy k obecnému použití), což znamená, že si do nich můžeme ukládat naprosto cokoliv. Poslední tři registry mají speciální význam, o kterém si však něco povíme až v příštím dílu seriálu.

První instrukcí, kterou si společně představíme, je MOV. Ta slouží k přesunu dat (z anglického MOVe). Pozor na to, že argumenty dostává v pořadí kam, co. První argument je vždy název registru, druhý argument může být buď název jiného registru nebo číselná konstanta. Pokud chceme v ARMovém assembleru zapsat číselnou konstantu, je třeba před samotné číslo napsat znak #. Pro pořádek ještě zmíníme, že zavináčem začíná komentář do konce řádku. Příklad použití:

 MOV  r7,  #42   @ Do r7 se uloží číslo 42
 MOV  r10, r7    @ Do r10 se uloží číslo 42 z r7
 MOV  r2,  #0xFF @ Do r2 se uloží číslo 255

Když už jsme si pořídili počítač, bylo by hezké, kdyby i něco počítal. K tomu si musíme ukázat ještě jeden registr, který se chová jinak než všechny ostatní. Nazývá se CPSR a je to takzvaný registr příznaků (anglicky flag register). Aritmetické operace mohou do tohoto registru nastavit jednotlivé příznaky podle toho, jak výpočet dopadl. Na ARMu máme čtyři aritmetické příznaky, a to N (Negative), pokud je výsledek záporný, Z (Zero), pokud je výsledek nula, a V (oVerflow) upozorňující, že došlo k přetečení. Čtvrtým příznakem je C (Carry), do kterého se uloží ten bit výsledku, který se do registru při ukládání již nevejde (tedy na našem 32-bitovém ARMu 32. bit, číslujeme-li od nuly). K čemu je to dobré, uvidíme záhy.

Sčítání a odčítání zajišťuje šestice instrukcí ADD (ADD), ADC (ADd with Carry), SUB (SUBtract), RSB (Reverse SuBtract), SBC (SuBtract with Carry), RSC (Reverse Subtract with Carry). Pozor na to, že odčítání nastavuje carry opačně, než odpovídá definici!

  • ADD a, b: a = a + b
  • ADC a, b: a = a + b + carry
  • SUB a, b: a = a - b
  • RSB a, b: a = b - a
  • SBC a, b: a = a - b - (1 - carry)
  • RSC a, b: a = b - a - (1 - carry)

Instrukce, které pracují s carry, nám umožňují sčítat velmi velká čísla – to, co se nám přeneslo z předchozího bloku, prostě přičteme k bloku dalšímu. Jelikož je u odčítání carry definováno obráceně, SBC a RSC odčítají jeho negaci. Také pozor, že na ARMu příznaky mění pouze varianty instrukcí zakončené písmenem S, např. ADDS nebo RSCS!

ARM nám zároveň umožňuje uložit výsledek do libovolného registru, k čemuž slouží instrukce se třemi parametry, např. ADD c, a, b uloží a + b do c. Stejně jako u MOV je a registr a b může být registr nebo číslo.

Nejlépe si to ukážeme na příkladu:

  MOV   r1, #42
  MOV   r2, #30
  ADD   r3, r1, r2   @ r3 = 72
  SUB   r4, r1, r2   @ r4 = 12
  RSCS  r1, r2       @ r1 = -12, příznak N

Pro násobení existuje na ARMu mnoho instrukcí, my si pro jednoduchost ukážeme pouze jednu z nich, která nám pro násobení malých čísel bude stačit. Je to MUL (MULtiply) pro násobení znaménkových čísel a používá stejný formát argumentů jako aritmetické instrukce. U ní existuje i varianta MULS, která nastaví příslušné příznaky. S dělením je situace přehlednější, existují pouze instrukce SDIV (Signed DIVide) pro znaménkové dělení a UDIV (Unsigned DIVide) pro bezznaménkové, ovšem tyto instrukce nemají variantu nastavující příznaky. Násobení i dělení používají opět 2 až 3 argumenty se stejným významem jako ostatní aritmetické operace.

Úkol 1 [4b]

Napište v assembleru posloupnost instrukcí, která do registru r0 spočítá povrch kvádru, jehož rozměry jsou zadané v registrech r1, r2 a r3.

Podobnou kategorii operací představují bitové operace AND (bitové and), ORR (bitové or), EOR (bitové xor) a BIC (bitové and not). Tyto instrukce vždy berou tři argumenty, tedy cílový registr, zdrojový registr a třetím parametrem může být další zdrojový registr nebo číslo.

Tyto operace fungují nezávisle pro jednotlivé bity čísla: i-tý bit výsledku zi spočítáme z i-tých bitů vstupních čísel xiyi. Pro AND je přitom zi=1 právě tedy, když je xi = yi = 1. Pro OR je zi=1, kdykoliv xi=1 nebo yi=1. A pro EOR potřebujeme, aby právě jeden z bitů xiyi byl jednička. NOT prostě přepne jedničku na nulu nebo nulu na jedničku. Zde je příklad:

  MOV   r1, #0xF0FF
  MOV   r2, #0x0FF0
  AND   r3, r1, r2   @ r3 = 0x00F0
  ORR   r4, r1, r2   @ r4 = 0xFFFF
  EOR   r5, r1, r2   @ r5 = 0xFF0F

Hop sem, hop tam

Občas se nám může hodit skočit na jiné místo programu. K tomu na ARMu slouží instrukce B (Branch) (v jiných instrukčních sadách se často jmenuje JMP (JuMP)). Abychom mohli assembleru říct, kam má daný skok vést, tak si příslušné místo v programu pojmenuje návěštím (anglicky label). Návěští v sobě může mít číslice, písmena anglické abecedy a podtržítka. Hezký nekonečný cyklus by mohl vypadat třeba takto:

  MOV   r1, #42
cyklus:
  SUB   r1, #1
  B     cyklus

Pokud bychom nyní chtěli v assembleru začít psát nějaké užitečnější programy, asi by nám velmi rychle začaly chybět podmínky. To většina procesorů řeší implementací podmíněných skoků – v případě, že se podmínka vyhodnotí jako pravdivá, procesor skočí na cílové návěští, v opačném případě pokračuje následující instrukcí. Jaké podmínky procesor umí? Zde se konečně dostáváme k využití registru příznaků, neboť podmínky využívají právě uložených příznaků.

Pro snazší pochopení názvů podmínek si ještě představme instrukci CMP (CoMPare). Ta se chová naprosto identicky jako SUBS, akorát výsledek se nikam neukládá, pouze se podle něho nastaví příslušné příznaky. V pravém sloupci následující tabulky naleznete význam podmínky po provedení CMP a,b. Sloupce příznaků obsahují 1 pro nastavený příznak a 0 pro nenastavený.

podmínkaZCNVvýznam
EQ (EQual)1a = b
NE (Not Equal)0a ≠ b
CS (Carry Set)1a ≥ b (neznaménk.)
HS (Higher Same)
CC (Carry Clear)0a < b (neznaménk.)
LO (LOwer)
VS (oVerflow Set)1Došlo k přetečení
VC (oVerflow Clear)0Nedošlo k přetečení
HI (HIgher)Z=0 ∧ C=1a > b (neznaménk.)
LS (Lower Same)Z=1 ∨ C=0a ≤ b (neznaménk.)
GT (Greater Than)Z=0 ∧ N=Va > b (znaménkově)
LE (Lower Equal)Z=1 ∨ N≠Va ≤ b (znaménkově)
GE (Greater Equal)N = Va ≥ b (znaménkově)
LT (Lower Than)N ≠ Va < b (znaménkově)
MI (MInus)1a-b < 0
PL (PLus)0a-b ≥ 0

Příznaky MI a PL moc nemá smysl používat po CMP. Lepší je použít LT/LO nebo GE/HS. Pro výsledky aritmetických operací se však hodí.

Například si ukažme jednoduchý cyklus, který (pokud je r1 ≥ 1) spočítá součin r1 ·(r1-1) ·… ·1 do r0:

  MOV   r0, #1
cyklus:
  MUL   r0, r1
  SUBS  r1, #1
  BNE   cyklus  @ skoč, pokud r1 není 0.

ARM je mezi instrukčními sadami výjimečný tím, že dovoluje podmínku k mnoha dalším instrukcím než jen ke skokům. Nicméně zatím se bez toho obejdeme.

Úkol 2 [5b]

Vymyslete, jak pomocí podmíněných skoků zapsat následující pseudokód:

  if r1 == 0:
    r0 = r0+1
  else:
    r0 = r0-1
  r2 = r0*2

Úkol 3 [6b]

Napište v assembleru posloupnost instrukcí, která do registru r0 spočítá největšího společného dělitele čísel zadaných v registrech r1 a r2.

To je pro tento rychlý úvod do assemblerů vše, příště se vrhneme na paměti a další pěkné věci.

Jan „Goci“ Gocník & Martin „Medvěd“ Mareš

Řešení