Aritmetika veľkých čísel na architektúre x86 vyžaduje zvláštnu pozornosť. Je treba využívať zabudované vlastnosti aritmetických a dalších instrukcii, které niesú na prvý pohľad zrejmé a ktoré uľahčujú výpočty.
(sorry za formatovanie tohoto clanku, ten blackhole system je nejaky divny, clanok v povodnom formatovani po anglicky si mozete precitat tu)
Predpokladám, že čitateľ rozumie binárnej reprezentácii čísel, pozná základy binárnej aritmetiky a šestnástkový zápis.
Veľké čísla sú také čísla, ktoré pozostávajú z viacej bitov ako je slovo procesoru (machine word). Napríklad 1024-bitové číslo je považované za veľké číslo. Veľkosť takéhoto čísla býva zvyčajne násobkom veľkosti slova procesoru, aby sa s ním jednoduchšie pracovalo. Vtedy môžeme povedať že veľké číslo pozostáva z niekoľkých slov procesoru.
Procesor nemá inštrukcie na priamu manipuláciu s veľkými číslami, ale poskytuje inštrukcie na manipulovanie so slovami procesoru, ktoré sú súčasťou veľkého čísla.
Príklady kódu budú pre procesor x86-32, na ktorom je veľkost slova 32 bitov. Ďalej budeme toto slovo nazývať podľa zvyku dword.
Stiahnite si Intel Manual Volume 2 (2A a 2B), obsahuje popis všetkých inštrukcii, a v článku sa naň budem odvolávať.
Rozloženie veľkých čísel v pamäti
Ako už bolo povedané, veľké čísla pozostávajú z niekoľkých slov procesoru (dwordov).
Poradie slov procesoru vramci veľkého čísla je problém podobný poradiu bitov (alebo bytov) vrámci slova procesoru. Sú dve možnosti: buď je prvé najvýznamnejšie slovo (big endian), alebo je prvé najmenej významné slovo (little endian). Na architektúre x86 sa na poradie bitov/bytov používa little endian. Preto ho aj my použijeme na poradie slov vo veľkom čísle. Nieje v tom žiadna praktická výhoda, je to len nejaký štandard na ktorom sa dohodneme.
Napríklad 64bitové číslo 1 bude pozostávať z dvoch dwordov: Prvý (menej významný) s hodnotou 1, a ďalší s hodnotou 0.
dd 1 ;low order dword
dd 0 ;high order dword
96-bitové číslo (3 dwordy) s hodnotou (šestnástkovo) 0x0102030412345678ABCDEF00 bude:
dd 0xABCDEF00 ;low order dword
dd 0x12345678
dd 0x01020304 ;high order dword
Súčet
Prvá operácia ktorú si predvedieme je súčet. Vyhľadajte si v manuáli inštrukciu add.
Začneme s pripočítanim čísla 1 k 96bitovému veľkému číslu. Pre začiatok proste prirátame 1 k spodnému (prvému) dwordu:
bignum dd 15
dd 0
dd 0
...
add dword [bignum], 1
Toto ale nestačí. Ak spodný dword bude obsahovať hodnotu 0xFFFFFFFF súčet pretečie, a hodnota po súčte bude 0. V takomto musíme preniesť jednotku do vyššieho (druhého) dwordu.
Ako zistiť pretečenie? Ked inštrukcia add pretečie, nastaví CF (carry flag). Jeden spôsob ako ošetriť pretečenie je napríklad takýto:
add dword [bignum], 1
jnc done
add dword [bignum+4], 1
done:
Ten istý problém ale môže nastať aj pri druhom súčte, ak aj druhý dword obsahuje 0xFFFFFFFF. Opäť musíme v tomto prípade preniesť 1 do tretieho dwordu:
add dword [bignum], 1
jnc done
add dword [bignum+4], 1
jnc done
add dword [bignum+8], 1
done:
Ak aj posledný add pretečie, tak celá operácia pripočítania k veľkému číslu pretiekla. Podľa toho na čo veľké číslo používame môžeme toto ignorovať, alebo ohlásiť ako chybu.
add dword [bignum], 1
jnc done
add dword [bignum+4], 1
jnc done
add dword [bignum+8], 1
jc overflow
done:
Existuje aj krajší spôsob ako ten čo sme si predviedli. Procesor x86 totižto práve na tento účel obsahuje inštrukciu adc. Táto robí to isté ako add, ibaže k výsledku pripočíta ešte aj CF. Inak povedané, ak je flag CF nastavený, tak k vysledku pripočíta ešte 1. Po skončení operácie inštrukcia zase nastaví CF podľa toho či nastalo pretečenie. S použitím adc teda pripočítanie jednotky k veľkému číslu vyzerá takto:
add dword [bignum], 1
adc dword [bignum+4], 0
adc dword [bignum+8], 0
Takto isto môžeme pripočítať akúkoľvek hodnotu, nielen 1. Pri súčte nikdy nieje treba do vyššieho dwordu preniesť viac ako 1 (0xFFFFFFFF + 0xFFFFFFFF = 0x1FFFFFFFE). Nasleduje všeobecná rutina ktorá pripočíta EAX k veľkému číslu na ktoré ukazuje EDI:
add dword [edi], eax
adc dword [edi+4], 0
adc dword [edi+8], 0
S použitím adc pre vyššie dwordy tiež môžeme pripočítavať čísla väčšie ako 32bitov (resp. väčšie ako veľkosť slova procesoru). Táto ukážka pripočíta 0x12345678AABBCCDD k veľkému číslu:
add dword [edi], 0xAABBCCDD
adc dword [edi+4], 0x1234567
adc dword [edi+8], 0
Takto tiež môžeme spočítať dve veľké čísla. Nasledujúca ukážka spočíta dve 128-bitové (4 dwordy) čísla. Konkrétne, pripočíta bignum1 k bignum2:
mov eax, dword [bignum1]
add dword [bignum2], eax
mov eax, dword [bignum1+4]
adc dword [bignum2+4], eax
mov eax, dword [bignum1+8]
adc dword [bignum2+8], eax
mov eax, dword [bignum1+12]
adc dword [bignum2+12], eax
jc overflow
Rozdiel (odpočítanie)
Odpočítavanie je analogické pripočítaniu, len použijeme inštrukcie sub namiesto add a sbb namiesto adc. Pri odpočítavame nehovoríme že bit prenesieme do vyššieho dwordu, ale že sme si ho "požičali" - odtiaľ je názov sbb substract with borrow.
mov eax, dword [bignum1]
sub dword [bignum2], eax
mov eax, dword [bignum1+4]
sbb dword [bignum2+4], eax
mov eax, dword [bignum1+8]
sbb dword [bignum2+8], eax
mov eax, dword [bignum1+12]
sbb dword [bignum2+12], eax
jc underflow
Negácia
Pomerne zaujimavý problém je negácia veľkého čísla. Máme inštrukciu neg, ale tá sa nedá tak jednoducho použiť s veľkými číslami. Preto najprv začneme s metódou, ktorú už poznáme - odpočítavaním. Proste naše číslo odpočítame od nuly:
mov eax, 0
sub eax, dword [bignum]
mov dword [bignum], eax
mov eax, 0
sbb eax, dword [bignum+4]
mov dword [bignum+4], eax
mov eax, 0
sbb eax, dword [bignum+8]
mov dword [bignum+8], eax
Negácia sa dá tiež presiesť ako invertovanie všetkých bitov čísla (0->1, 1->0) a následne pripočítanie jednotky. Nebudem tu vysvetľovať prečo je to tak, musíte rozumieť tomu ako sú záporné čísla reprezentované v architektúre x86.
Na invertovanie všetkých bitov máme inštrukciu not. Pripočítavanie k veľkému číslu už bolo popísané.
not dword [bignum]
not dword [bignum+4]
not dword [bignum+8]
add dword [bignum], 1
adc dword [bignum+4], 0
adc dword [bignum+8], 0
Pokiaľ už tomuto rozumieme, môžeme si ukázať aj ako sa dá použiť inštrukcia neg na znegovanie veľkého čísla. Ako sme sa už dozvedeli, neg najprv invertuje všetky bity a potom pripočíta 1 k výsledku. Takže najprv znegujeme prvý (spodný, low order) dword. Ak hodnota pred negovaním je 0, po invertovaní bitov bude 0xFFFFFFFF, a pripočítanie 1 pretečie na 0. Toto je jediný prípad kedy musíme pripočítanú jednotku preniesť, a jediný prípad kedy NEG nastaví CF. Ak CF po negovaní nieje nastavené, v ostatných dwordoch stačí už len invertovať bity. V praxi toto riešenie nieje veľmi pekné:
neg dword [bignum]
jnc not1
neg dword [bignum+4]
jnc not2
neg dword [bignum+8]
jmp done
not1:
not dword [bignum+4]
not2:
not dword [bignum+8]
done:
Bitové posúvanie
Bitové posúvanie je niekedy pri veľkých číslach užitočné (napríklad keď sa nimi reprezuntujú tzv. čísla s plávajúcou desatinnou čiarkou, tj. exponenciálne čísla).
Začneme posúvaním o 1 bit.
Ked chceme bitovo posúvať obyčajné (nie veľké) číslo, používame inštrukcie shl a shr. Keď posúvame o jedno miesto, tak bit ktorý čísla "vysunieme" preč sa uloží do CF. Problém je však ako ho následne vložiť do ďalšieho dwordu.
V tomto prípade môžeme použiť inštrukcie rcl and rcr. Tieto "rotujú bity čísla cez CF". Keď ich použijeme na rotovanie čísla o 1 miesto, tak posunú číslo, na miesto nového bitu vsunú hodnotu CF, a bit ktorý vysunuli z čísla potom uložia do CF - presne to čo potrebujeme. Pokiaľ to nieje jasné, pozrite si manuál. Posúvanie veľkých čísel pomocou rotovania teda vyzerá takto:
Posúvanie doprava:
;shift left
shl dword [bignum], 1
rcl dword [bignum+4], 1
rcl dword [bignum+8], 1
jc overflow
Posúvanie doľava:
;shift right
shr dword [bignum+8], 1
rcr dword [bignum+4], 1
rcr dword [bignum], 1
jc overflow ;casto nieje treba
Bitové posuny sa stávajú zaujímavejšími keď chceme posúvať o viac ako 1 bit. V tomto prípade musíme medzi dwordami prenášať viac ako jeden bit. Naštastie procesor 386 priniesol nové inštrukcie špeciálne na tento úšel. Sú to shld a shrd. Tieto posunú operand rovnako ako shl a shr/sar, ale narozdiel od nich vsunuté bity vezmú z ďalšieho operandu.
Posúvanie doprava:
mov eax, [bignum+4]
shrd [bignum], eax, 5
mov eax, [bignum+8]
shrd [bignum+4], eax, 5
shr [bignum+8], 5
Posúvanie doľava:
mov eax, [bignum+4]
shld [bignum+8], eax, 5
mov eax, [bignum]
shld [bignum+4], eax, 5
shl [bignum], 5
Testovanie pretečenia je už náročnejšie. Musíme ešte pred posunom overiť či horných/spodných N bitov (N je množstvo bitov o ktoré posúvame) sú nulové. Pri posúvaní o konštantnú vzialenosť môžeme použiť klasické testovanie maskou:
Pri posúvaní doprava:
test [bignum+8], 0x0000001F ;00000000 00000000 00000000 00011111 binary
jnz overflow
Pri posúvaní doľava:
test [bignum+8], 0xF8000000 ;11111000 00000000 00000000 00000000 binary
jnz overflow
Ibaže keď počet bitov o ktorý posúvame nieje konštanta, museli by sme si najprv túto masku vytvoriť. Namiesto toho, môžeme znovu použiť shld a shrd aby sme z čísla vytiahli tie bity ktoré nás zaujímajú:
Pri posúvaní doprava:
xor eax, eax ;eax = 0
mov ebx, [bignum]
shrd eax, ebx, 5
test eax, eax ;eax ?= 0
jnz overflow
Pri posúvaní doľava:
xor eax, eax ;eax = 0
mov ebx, [bignum+8]
shld eax, ebx, 5
test eax, eax ;eax ?= 0
jnz overflow
Násobenie
Na násobenie bežných čísel máme inštrukciu mul. Budeme používať iba jej formu s jedným operandom, ostatné formy niesú použiteľné pre veľké čísla.
Inštrukcia mul vynásobí EAX iným 32bitovým číslom, a 64bitový výsledok uloží v EDX:EAX (to znamená že horných 32bitov výsledku bude v EDX a dolných 32 bitov v EAX). Vďaka tomu, časť výsledku ktorú treba po každej elementárnej operácii preniesť do vyššieho dwordu už máme pripravenú v EDX. Ukážkové násobenie desiatkou:
mov ebx, 10 ;EBX = cislo ktorym nasobime
mov eax, [bignum]
mul ebx ;EDX:EAX = EAX*EBX
mov [bignum], eax ;zapis vysledok nasobenia dwordu
mov ecx, edx ;ecx = cast ktory prenesieme do vyssieho dwordu
mov eax, [bignum+4]
mul ebx
add eax, ecx ;pripocitaj prenesenu cast z predchadzajuceho nasobenia
mov [bignum+4], eax
mov ecx, edx
mov eax, [bignum+8]
mul ebx
add eax, ecx
mov [bignum+8], eax
cmp edx, 0
jne overflow
Násobenie číslami väčšími ako 32bitov (napríklad násobenie dvoch veľkých čísel) sa už nedá riešiť takto jednoducho.
Delenie
Delenie veľkých čísel je veľmi podobné násobeniu. Budeme používať verziu inštrukcie div s jedným operandom. Táto vydelí 64-bitové číslo v EDX:EAX operandom, podiel uloží v EAX a zvyšok v EDX. Ak je výsledok väčší ako 32-bitov, procesor hodí výnimku, takže si musíme dať pozor aby sa toto nestalo.
Začneme "odvrchu" čísla (high order dword). Po každom delení zvyšok v EDX použijeme ako horných 32 bitov delenca pre ďalšie delenie. Posledný zvyšok v EDX je zvyšok po celom delení veľkého čísla.
mov ebx, 10 ;delitel
mov edx, 0
mov eax, [bignum+8] ;EDX:EAX = delenec
div ebx
mov [bignum+8], eax
mov eax, [bignum+4]
div ebx
mov [bignum+4], eax
mov eax, [bignum]
div ebx
mov [bignum], eax
;edx tu obsahuje zvyšok delenia
Opäť, delenie číslom väčším ako 32 bitov sa nedá spraviť takto jednoducho.
Pre pridávanie komentárov sa musíte prihlásiť.