8080 – násobení

Když se sejdou tři sobi, tak se radost násobí…

Už jsme si řekli, že násobení nepatří mezi základní operace, kterými procesor 8080 oplývá. A rovnou můžu prozradit, že to ani u Z80, ani u 6502 není v tomto směru o moc lepší. Po pravdě si nevzpomínám na žádný osmibitový procesor, který by měl instrukci pro násobení. Neříkám že neexistoval, jen si na něj nevzpomínám. (Paměť mi osvěžil až Roman Bórik: osmibitové jednočipy – mikrokontroléry řady 8051/8052 mají instrukce násobení i dělení.)

Pokud chceme násobit, a taková potřeba na každého někdy přijde, musíme si vystačit s tím co máme a známe. A taky trošku zavzpomínat na základní školu.

Násobení poprvé – naivní

Víme, že 3 krát 5 je vlastně 5 + 5 + 5. Třikrát se sečte pětka. Mohlo by to vypadat nějak takhle – násobíme obsah registru B obsahem registru C a výsledek ukládáme v A:

Rovnou upozorňuju, že to je jeden z nejzoufalejších kódů, co tu budou zveřejněné. Je špatný z mnoha důvodů. Zaprvé – když násobím dvě osmibitová čísla, může být výsledek až šestnáctibitový (prostý test: 255 * 255 = 65025 (FE01h)). Já tu sčítám hodnoty v registru A, který je osmibitový a přeteče už u čísla 255. Což, to by se dalo napravit snadno – místo sčítání v registru A můžu použít registry HL, přičítat k nim číslo z registrů DE a bude to… Nějak takto (opět násobíme B * C, výsledek jde do HL):

Teď už můžeme násobit v plném rozsahu, tenhle problém jsme vyřešili, ale je tu jiný problém. Totiž ten, že násobení trvá dlouho. Představte si, že B bude třeba 250 a C dvě. Budeme 250krát přičítat dvojku, stále dokola – ostatně zkuste si to v emulátoru nasimulovat, uvidíte sami. Co s tím?

Můžeme čísla na začátku prohodit (místo „250x přičti dvojku“ udělat „2x přičti 250“), ale to je řešení na půli cesty. Vlastně ne na půli cesty, ve skutečnosti na pytel! Správný postup je zahodit tenhle algoritmus a jít na to jinak.

Násobení podruhé – rafinované

Spousta lidí tváří v tvář dvojkové soustavě strne a očekává, že přestanou fungovat postupy, které znají ze soustavy desítkové. Ale ony fungují docela dobře. Třeba to násobení se dá obstojně zařídit stejně, jako jsme se to učili ve třetí třídě ZŠ, když jsme násobili na papíře dvojciferná čísla pod sebou. Pamatujete?

Postup popíšu slovy. Začneme od nejnižšího řádu druhého činitele (4). Tím vynásobíme prvního činitele (4*26) a dostaneme první mezivýsledek (104). Ten platí pro nejnižší řád (je zapsaný úplně vpravo, zarovnaný s tím řádem, který právě zpracovávám). Pokračuju k vyššímu řádu druhého činitele. Vida, je to 3. Postup opakuju: vynásobím tím číslem první činitel (3*26) a druhý mezivýsledek (78) si zapíšu na pozici desítek, tedy o řád výš než předchozí. A takhle budu pokračovat, dokud nepronásobím všechny řády druhého činitele. Nakonec mezivýsledky sečtu.

Tak. A jde to tak i ve dvojkové soustavě? Zkusíme to. Kolik je dvojkově 13 * 9?

Postup je naprosto stejný – taky násobíme a posouváme o řád, ovšem situaci máme o mnoho jednodušší: Protože pracujeme ve dvojkové soustavě, tak násobíme vždy jen buď jedničkou (tedy mezisoučet je roven prvnímu činiteli), nebo nulou (a mezisoučet je 0). Mezisoučty postupně posouváme doleva a přičítáme.

Tak, s touhle vědomostí by určitě šlo napsat násobící algoritmus, který nemá tu nectnost, že by závisel na hodnotě činitele. Jeho hlavní smyčka proběhne tolikrát, kolik má druhý činitel bitů. Ale předtím, než se do něj pustíme, si řekneme ještě pár tipů.

K posunu registru o jeden bit doleva můžeme samozřejmě použít instrukci rotace. Ovšem tady budeme rotovat rovnou dva registry najednou. Nejjednodušší způsob bude použít instrukci DAD H. Ta, jestli si vzpomínáte, přičte k registrovému páru HL hodnotu svého parametru – tedy HL. Sečíst HL a HL znamená vlastně udělat 2*HL, a z hlediska bitového je to totéž jako posunout obsah registru doleva o 1 bit a zprava doplnit nulou. Tedy přesně to, co se děje v tom algoritmu výše.

Troufnete si napsat algoritmus, který vynásobí obsah registrů D a E a výsledek uloží do HL? Zkuste to…

Řešení je následující:

Může vám připadat trošku zmatené, ale nebojte, hned si to projdeme.

Na začátku nastavím zásobník na rozumnou pozici. Připravím si do registrů D a E hodnoty, které budeme násobit (13 a 9). Samosebou bych mohl použít LXI D, 0x0D09, ale pro názornost je to takhle rozepsané. Pak volám podprogram Mul8 – jako že „Multiplication, 8 bits“.

V podprogramu si nejdřív vynuluju registry HL. Tam se budou průběžně sčítat mezivýsledky. Do B si připravím hodnotu 8 – to je počítadlo, kolikrát provedu hlavní smyčku. Budu ji provádět osmkrát, pro každý řád jednou, tak proto ta osmička. Teď bych potřeboval, aby v DE byl jen druhý činitel (tedy v D 0 a v E to, co tam je). Přesunu si tedy obsah D do registru C (mám teď činitele v registrech C a E) a registr D si vynuluju. A teď může začít vlastní kouzlo…

Podívám se, jakou hodnotu má nejnižší bit registru C, a posunu si ho o jednu pozici doprava  (v příštím průchodu tak budu kontrolovat pozici 1, pak pozici 2 atd.) To ale nemůžu udělat přímo, takže si jej musím nejprve přesunout do registru A, tam provést RRC a pak uložit zpátky do C. Instrukce RRC dělá obě věci, co potřebuju, najednou – uloží nejnižší bit (do příznaku CY) a rotuje o jednu pozici doprava.

Podle hodnoty nejnižšího bitu (mám ho teď v CY) se rozhodnu, jestli mezisoučet (DE) přičtu k celkovému výsledku (pokud je 1), nebo nepřičtu (CY=0). Použiju podmíněný skok: Pokud není CY (JNC), tak skoč dál. Pokud je CY, pokračuj a přičti DE k HL (HL=HL*DE)

Tím mám jeden krok skoro za sebou. Teď už jen musím posunout mezisoučet v DE o jednu pozici doleva. Vyřeším to tak, že ho přičtu k sobě samotnému (tedy DE = DE + DE). A protože na to instrukci nemáme, tak si pomocí XCHG na chvíli prohodíme DE a HL a provedeme HL = HL + HL.

Pak už jen snížím počet průchodů smyčkou (DCR B), a pokud ještě nejsme na nule, tak to celé provedeme znovu.

A věřte nebo ne, na tomhle principu je založena naprostá většina softwarových násobiček.

Násobení dvaapůlté – optimalizované

Můžeme u předchozího algoritmu ušetřit pár bajtů, dva registry a nějaký ten čas, a to tím, že druhý činitel umístím do registru H, zatímco mezisoučet bude neustále v HL. Zní to divně? Divné to teprve začne být!

Ve skutečnosti při tomto postupu nepůjdeme od nejmenšího bitu, ale od nejvyššího. Náš postup nebude ten, že při každém průchodu přičteme první činitel, patřičně posunutý doleva (*2), ale při každém průchodu naopak vynásobíme mezisoučet dvěmi a případně přičteme první činitel. Matematicky místo (A * 20 * b0) + (A * 21 * b1) + (A* 22 *b2) + … (A je první činitel, b0-b7 bity druhého činitele) budeme provádět (((A*b7)*2+(A*b6))*2+(A*b5))*2… Pro zájemce: Hornerovo schéma(Náš učitel programování tomu říkal tvrdošíjně „Hornerovo šéma“ – ale on říkal taky místo while cosi, co znělo jako [hwajl]…)

Využijeme toho, jak se chová instrukce DAD H. Už jsme si řekli, že udělá HL = HL + HL, tedy HL * 2. Tedy vlastně posune obsah HL o jednu pozici doleva. Zároveň nastaví příznak CY, pokud hodnota přeteče – v tomto případě přeteče, pokud je nejvyšší bit registru H = 1… takže jako by zkopíroval ten nejvyšší bit do příznaku CY.

Takže jednou instrukcí tu máme:

  • posun hodnoty v registru H o jeden bit doleva (tedy můžeme jít bit po bitu od b7 po b0)
  • při každém posunu udělá vlastně jeden bit prostoru pro mezisoučet v HL (to, že H v průběhu výpočtu ve vyšších bitech obsahuje nějaký zmatek, to nevadí, protože „zmatek“ se postupem času odsune pryč)
  • vynásobí mezisoučet dvěma.

Tolik dobra za jednu cenu, že?


Vyšší dívčí? Nebojte se, vpravíte se do toho. V očích vám teď vidím otázku: Zešílels? Tohle přeci není normální!

Takže: Ano, zešílel, ale to s tím nijak nesouvisí, a ne, v assembleru je tohle naprosto normální. Když chcete, hrajete o každý bit v registru, takt procesoru, bajt v paměti… A někdy ani nechcete, ale musíte!

Násobení potřetí

V assembleru má optimalizace vždycky dvě fáze. V té první vyhazujete instrukce, které jste napsali zbytečně – program bude kratší i rychlejší. V té druhé si musíte vybrat: Chcete kratší kód? Musíte dělat triky, co vás budou stát nějaký ten čas. Chcete kód rychlý? Musíte obětovat prostor. I u algoritmu násobení stojíte před stejným rozhodováním: rychleji? Bude to něco stát…

Úplně nejrychlejší algoritmus by byl takový, který by měl v paměti výsledky všech možných kombinací pro násobení (v případě osmibitových činitelů by jich bylo 65536) a prostě by si jen sáhnul tam, kam potřebuje. Taková tabulka by ale zabrala spoustu paměti a pro vlastní program by v adresním prostoru běžného osmibitového procesoru zůstalo… ehm… přesně 0 bajtů. Naštěstí existují kompromisní řešení, kdy si do tabulky uložíme jen pár konstant (třeba 1024) a zbytek dopočítáme. Je to opět kompromis mezi rychlostí a velikostí. A jak tedy bude násobení vzor 3 vypadat? To si nechme na jindy…

Líbil se vám článek? Podpořte autora na Patreonu
Příspěvek byl publikován v rubrice 8080. Můžete si uložit jeho odkaz mezi své oblíbené záložky.

8 komentáře u 8080 – násobení

  1. Roman Bórik napsal:

    >> Po pravdě si nevzpomínám na žádný osmibitový procesor, který by měl instrukci pro násobení. Neříkám že neexistoval, jen si na něj nevzpomínám. <<

    Ak sa oprostíme od pojmu (mikro)procesor, tak mikrokontrolér 8051 inštrukcie MUL a DIV v inštrukčnej sade má.

  2. Milan Palička napsal:

    Pár zajímavostí na doplnění – tyhlety klasické osmibity přímo násobit zpravidla neuměly, ale firma AMD uvedla na trh už někdy v sedmdesátých letech osmibitový matematický koprocesor AM9511, který to uměl (mimo jiné) a dokonce i Tesla vyráběla jednoúčelovou hardwarovou násobičku MH102 – vhodná jako periferní obvod k mikroprocesoru 8080, jak je psáno v tehdejším katalogu 🙂

    • Martin Malý napsal:

      Jojo, díky za doplnění. Je pravda, že na to existoval hardware, ale marně přemýšlím, v jakém známějším mikroprocesorovém systému z té doby byla třeba ta násobička použitá. 🙂

      • Milan Palička napsal:

        Tak to taky netuším… Snad v něčem ze Zbrojovky, ale to jen odhaduji. Ty MH102 co mám v šuplíku mají na sobě znak „pro armádu“, takže se možná používaly v nějakém naváděcím systému. Třeba se někdy dokopu ho zkusit připojit např. k PMI-80…

      • Roman Bórik napsal:

        Násobička MH102 bola použitá v PP-01. Teda, aby som bol presný, tak v schéme je zakreslená a preškrtnutá. V príručke technického popisu je uvedený aj popis, avšak s dodatkom, že „Tento obvod sa však štandardne neosadzuje.“

      • Martin napsal:

        Ja mam kartu s AM9511 pro Apple II. Za zminku stoji i AM9512. Oba obvody mam uz nejakou dobu v supliku a tesim se, ze si s nimi pohraju.

Napsat komentář

Vaše emailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *