Magazín FLOP

Posloupnosti podmínek

Radek Štěrba, RASTER

Spousta podmínek za sebou se ve strojovém kódu objevuje dost často, zvláště v těch částech, kde např. reagujeme na stisk nějaké klávesy nebo podle jiného parametru rozhodujeme o provedení určité akce.

Nejčastější formou je postupné kladení podmínek:

    LDA PARAM  ;tj.nějaký parametr, který porovnáváme
    CMP #0
    BNE NA1
    ;pro PARAM=0
    ...
NA1 CMP #1
    BNE NA3
    ;pro PARAM=1
    ...
NA2 CMP #2
    BNE NA3
    ;pro PARAM=2
    ...
    ...

Tento způsob je přehledný a vzhledem k rychlosti provádění strojového kódu i hojně používaný. Pokud bude podmínek hodně (třeba i několik desítek), je možné použít metodu s rozeskakovací tabulkou.

Tento příklad provede skok na dané návěští podle hodnoty nalezené na adrese PARAM. (Je to vlastně obdoba BASICovského příkazu ON GOTO.) Hodnotě 0 odpovídá skok na NA0, 1 skok na NA1, 2 skok na NA2, atd... (Pozn.: Názvy návěští mohou být libovolné, pouze je nutné bezpodmínečně dodržet jejich pořadí na řádku s definicí VECTAB.)

    LDA PARAM
    ASL A
    TAX
    LDA VECTAB,X
    STA ADR
    LDA VECTAB+1,X
    STA ADR+1
    JMP (ADR)
ADR .WORD $0000 
VECTAB .WORD NA0,NA1,NA2,...
NA0
    ...
NA1 
    ...
NA2
    ...

Vysvětlivky:
ASL A
..násobení dvěma, protože adresa se skládá ze dvou bytů
TAX
..přesun do X
LDA VECTAB,X
..získání nižšího bytu cílové adresy
STA ADR
..uložení nižšího bytu na adresu ADR
LDA VECTAB+1,X
..vyšší byte cílové adresy
STA ADR+1
..uložení vyššího bytu na ADR+1
JMP (ADR)
..nepřímý skok. Program skočí na adresu, jejíž hodnotu najde na adrese uvedené v závorkách (ADR). Přesněji řečeno: skutečnou adresu pro skok dostaneme tak, že vezmeme obsah adresy ADR a přičteme 256-ti násobek obsahu adresy ADR+1.
ADR .WORD $0000
..vyhrazení místa pro uložení dolního a horního bytu skutečné cílové adresy, na kterou má být proveden skok.
VECTAB .WORD NA0,NA1,NA2,...
..tabulka návěští pro skoky (od adresy VECTAB budou v paměti za sebou dvojice hodnot - vždy dolní a horní byte hodnoty daného návěští).

Další část tohoto textu bude určena spíše pokročilým a těm, kterým jde ve svých strojových programech o ušetření každého taktu procesoru (tj. cca 1/1720000sec.). Zabývat se takovými úsporami má význam pouze u rutin, které jsou volány mnohokrát za vteřinu (řádově v 10000-cích). Teprve pak má vynaložené úsilí patřičný efekt..

Pokud hodnota parametru není 0,1,2,3,.. ale je to nějaké číslo (např. kód stisknuté klávesy), řeší se to většinou posloupností podmínek, neboť rozeskakovací tabulku nelze použít (pokud nechceme obětovat 256bytů paměti a tak vlastně udělat tabulku pro parametr od 0 až do 127).

I tady však lze udělat jisté vylepšení:

Př. Podle hodnot PARAM = 63,21,18,58,42,56,61,57 (tj. Kódy kláves A,B,C,..,H) chceme provádět různé činnosti.

Když tento problém budeme řešit posloupností 8-mi podmínek, bude to jistě fungovat, ale např. pro písmeno H bude nejprve porovnáváno všech 7 předchozích čísel. Existuje však i efektivnější způsob:

seřadíme si hodnoty podle velikosti:
18,21,42,56,57,58,61,63
vybereme prostřední hodnotu
tj. 56
rozdělíme posloupnost na 2 části (dělícím prvkem je č.56)
v každé části vybereme prostřední hodnotu a posloupnosti zase rozdělíme na dvě části (atd.)
( (18) 21 (42) ) 56 ( (57 ) 58 ( 61 ( 63) ) ) <\ol>
Program pak bude vypadat takto:
```
    LDA PARAM
    CMP #56 
    BEQ J56 ;=56
    BCS N56 ;>=56
    CMP #21
    BEQ J21 ;=21
    BCS N21 ;>=21
    CMP #18
    BEQ J18 ;=18
    JMP NIC
N21 CMP#42
    BEQ J42 ;=42
    JMP NIC
N56 CMP#58
    BEQ J58 ;=58
    BCS N58 ;>=58
    CMP #57
    BEQ J57 ;=57
    JMP NIC
N58 CMP #61
    BEQ J61 ;=61
    CMP #63
    BEQ J63 ;=63
    JMP NIC
NIC ;nebyl to žádný
;Návěští pro jednotlivé hodnoty:
J18 ;pro PARAM=18
J21 ;=21
J42 ;=42
J56 ;=56
J57 ;=57
J58 ;=58
J61 ;=61
J63 ;=63
```
Že je to šíleně složité a nechápete to? Vysvětlím...
Pokud porovnáme parametr vždy s prostřední hodnotou, zjistíme, že
1. je roven této hodnotě, takže skočíme na návěští pro provedení operací příslušejících k této hodnotě (tj. návěští Jxx).
2. je větší (instrukce BCS provede skok). Teď už budeme uvažovat pouze pravou polovinu posloupnosti (levá část nás tedy již vůbec nezajímá). Pokračujeme porovnáním s prostřední hodnotou v pravé části atd...
3. je menší (BCS neskočí). Teď nás bude zajímat už jen levá část posloupnosti (pravou si odmyslíme). Pokračujeme porovnáním s prostřední hodnotou v levé části atd...
Zdá se vám to stále složité? Doufám alespoň, že princip je jasný?!
A jaký je efekt toho celého?
Klasickým způsobem se provádí v nejhorším případě 8-krát instrukce CMP a 8-krát BNE, tedy celkem 16 instrukcí.
Po "inovaci" průzkumem zjistíme, že v nejhorším případě (pokud PARAM=63) program projde přes 4 instrukce CMP, 4 instrukce BEQ a 2 BCS - to je dohromady 10 instrukcí.
Jestli se vám zdá, že je to zbytečné usilí kvůli 6 instrukcím, máte pravdu. Tento příklad je přece pouze demonstrační. Vězte však, že s rostoucím počtem možných hodnot je tato metoda mnohem efektivnější. To ale oceníte až při programování superrychlých rutin.
Tento princip můžete s výhodou využít i u programů v jiných programovacích jazycích, neboť jeho síla je ve snížení celkového počtu provedených operací porovnání.