Jak pisac programy w jezyku assembler?
Autor: Bogdan Drozdowski, bogdandr (at) op.pl

Czesc 14 - Operacje o wielokrotnej precyzji, czyli co zrobic, gdy liczby
nie mieszcza sie w rejestrach.

---------------------------------------------------------------------------

Czasami w naszych programach zachodzi potrzeba, aby poslugiwac sie np.
liczbami przekraczajacymi 4 czy nawet 8 bajtow, a my mamy tylko rejestry
32-bitowe (lub czasem 16-bitowe).

Co wtedy zrobic?
Odpowiedzi na to wlasnie pytanie postaram sie udzielic w tej czesci kursu.

Do naszych celow posluzy cos, co se nazywa "arytmetyka wielokrotnej precyzji"
(ang. Multiprecision Arithmetic). Generalna zasada bedzie zajmowanie sie
obliczeniami "po kawalku" (bo z reszta inaczej sie nie da) i
zapamietywanie, czy z poprzedniego kawalka wynieslismy cos "w pamieci"
(do tego celu w prosty sposob wykorzystamy flage CF, ktora wskazuje wlasnie,
czy nie nastapilo przepelnienie).


Najpierw kilka ustalen:

- Bede tutaj uzywal rejestrow 32-bitowch, ale w razie potrzeby dokladnie te
same algorytmy dzialaja takze dla rejestrow innych rozmiarow.
- Zmienne "arg1" i "arg2" maja po 16 bajtow, tj. po 128 bitow kazda. Na
potrzeby nauki wystarczy w sam raz.
- Zmienna "wynik" ma tyle samo bajtow, co "arg1" i "arg2", z wyjatkiem
mnozenia, gdzie oczywiscie musi byc dwa razy wieksza.
- Zmienna "wynik" na poczatku zawiera zero.
- Kod nie bedzie optymalny, ale chodzi mi o to, aby byl jak najbardziej jasny
i przejrzysty.


A wiec do dziela.

---------------------------------------------------------------------------

Zacznijmy od dodawania. Dodawanie, podobnie jak uczyli nas w szkole, zaczynamy
od najmlodszych cyfr (cyfr jednosci) - tyle ze zamiast pojedynczych cyferek
bedziemy dodawac cale 32-bitowe kawalki naraz. Flaga CF powie nam, czy z
poprzedniego dodawania wynosimy cos w pamieci. To cos trzeba oczywiscie dodac
potem do wyzszej czesci wyniku.

No to dodajemy:

mov eax, [arg1]
add eax, [arg2] ; dodajemy 2 pierwsze czesci liczb
mov [wynik], eax ; i ich sume zapisujemy w pierwszej
; czesci wyniku. Flaga CF mowi, czy
; wynosimy cos w pamieci

mov eax, [arg1+4]
adc eax, [arg2+4] ; dodajemy drugie czesci + to,
; co wyszlo z poprzedniego dodawania
; [arg1] i [arg2] (a to jest w fladze
; CF, stad instrukcja ADC zamiast ADD)

mov [wynik+4], eax ; calosc:[arg1+4]+[arg2+4]+"w pamieci z
; pierwszego dodawania" zapisujemy tu.
; Flaga CF zawiera (lub nie) bit
; "w pamieci", ale tym razem z ADC

; podobnie reszta dzialania:
mov eax, [arg1+8]
adc eax, [arg2+8]
mov [wynik+8], eax

mov eax, [arg1+12]
adc eax, [arg2+12]
mov [wynik+12], eax

jc blad_przepelnienie

---------------------------------------------------------------------------


Teraz odejmowanie. W szkole uczyli nas, ze zaczynamy od najmlodszych cyfr
i ewentualnie "pozyczamy" od starszych. Tutaj bedziemy robic dokladnie tak
samo! Wymaga to jednak poznania nowej instrukcji - SBB (Substract with
Borrow). Dziala ona tak samo, jak zwykla instrukcja odejmowania SUB, ale
dodatkowo odemuje wartosc flagi CF, czyli 1 lub 0, w zaleznosci od tego, czy
w poprzednim kroku musielismy "pozyczac" czy tez nie. Ewentualna "pozyczke"
trzeba oczywiscie odjac od wyzszej czesci wyniku.


Piszmy wiec (od "arg1" bedziemy odejmowac "arg2"):

mov eax, [arg1]
sub eax, [arg2] ; odejmujemy 2 pierwsze czesci
mov [wynik], eax ; i zapisujemy wynik
; flaga CF mowi, czy byla pozyczka

mov eax, [arg1+4]
sbb eax, [arg2+4] ; odejmujemy razem z pozyczka (CF),
; jesli w poprzednim odejmowaniu
; musielismy cos pozyczac

mov [wynik+4], eax ; wynik: [arg1+4]-[arg2+4]-"pozyczka
; z pierwszego odejmowania"
; Flaga CF teraz zawiera pozyczke z SBB

; podobnie reszta dzialania:
mov eax, [arg1+8]
sbb eax, [arg2+8]
mov [wynik+8], eax

mov eax, [arg1+12]
sbb eax, [arg2+12]
mov [wynik+12], eax

jc arg1_mniejszy_od_arg2

---------------------------------------------------------------------------

Teraz zajmiemy sie negacja (zmiana znaku liczby). Ta operacja jest o tyle
"dziwna", ze wykonujemy ja "od gory" (od najstarszych bajtow) i po negacji
nizszych trzeba zadbac o "pozyczke" we wszystkich wyzszych czesciach.


Popatrzcie (bedziemy negowac "arg1"):

neg dword [arg1+12] ; negujemy najstarsza czesc

neg dword [arg1+8] ; negujemy druga od gory
sbb dword [arg1+12], 0 ; jesli byla pozyczka od starszej
; (a prawie zawsze bedzie), to te
; pozyczke odejmujemy od starszej

neg dword [arg1+4] ; negujemy kolejna czesc i odejumjemy
; pozyczki od starszych czesci
sbb dword [arg1+8], 0
sbb dword [arg1+12], 0

neg dword [arg1] ; negujemy kolejna czesc i odejumjemy
; pozyczki od starszych czesci
sbb dword [arg1+4], 0
sbb dword [arg1+8], 0
sbb dword [arg1+12], 0

Dla wiekszych liczb nie wyglada to za ciekawie. Dlatego najprostszym sposobem
bedzie po prostu odjecie danej liczby od zera, do czego zastosujemy zwykly
algorytm odejmowania.



---------------------------------------------------------------------------

Mnozenie jest nieco bardziej skomplikowane, ale ciagle robione tak jak w
szkole, czyli od prawej. Ustalmy dla wygody, ze arg1 zawiera ABCD,
a arg2 - PQRS (kazda z liter oznacza 32 bajty).
Ogolny schemat wyglada teraz tak:


A B C D
* P Q R S
--------------
D*S
C*S
B*S
A*S
D*R
C*R
B*R
A*R
D*Q
C*Q
B*Q
A*Q
D*P
C*P
B*P
+ A*P
-----------------------------
F G H I J K L


[wynik] = L = D*S
[wynik+4] = K = C*S + D*R
[wynik+8] = J = B*S + C*R + D*Q
[wynik+12] = I = A*S + B*R + C*Q + D*P
[wynik+16] = H = A*R + B*Q + C*P
[wynik+20] = G = A*Q + B*P
[wynik+24] = F = A*P
(rzecz jasna, kazdy iloczyn zajmuje 2 razy po 4 bajty, np. L zajmuje [wynik]
i czesciowo [wynik+4], ale tutaj podalem tylko miejsca, gdzie pojda
najmlodsze czesci kazdego w iloczynow)


Policzenie L i K wygladaloby tak (pamietamy, ze wynik mnozenia jest w EDX:EAX):

mov eax, [arg1] ; EAX = D
mul dword [arg2] ; EDX:EAX = D*S
mov [wynik], eax
mov [wynik+4], edx

mov eax, [arg1+4] ; EAX = C
mul dword [arg2] ; EDX:EAX = C*S
add [wynik+4], eax
adc [wynik+8], edx

mov eax, [arg1] ; EAX = D
mul dword [arg2+4] ; EDX:EAX = D*R
add [wynik+4], eax
adc [wynik+8], edx

; adc [wynik+12], 0 ; gdy bedziemy dalej liczyc



---------------------------------------------------------------------------


Dzielenie dwoch liczb dowolnej dlugosci moze byc klopotliwe i dlatego zajmiemy
sie przypadkiem dzielenia duzych liczb przez liczbe, ktora miesci sie w
32 bitach. Dzielic bedziemy od najstarszych bajtow do najmlodszych. Jedna
sprawa zasluguje na uwage: miedzy dzieleniami bedziemy zachowywac reszte
w EDX (nie bedziemy go zerowac), gdyz w taki sposob otrzymamy prawidlowe
wyniki. Oto algorytm (dzielimy "arg1" przez 32-bitowe "arg2"):


mov ebx, [arg2] ; zachowujemy dzielnik w wygodnym
; miejscu

xor edx, edx ; przed pierwszym dzieleniem zerujemy
; EDX

mov eax, [arg1+12] ; najstarsze 32 bity
div ebx
mov [wynik+12], eax ; najstarsza czesc wyniku juz jest
; policzona

; EDX bez zmian! Zawiera teraz resztke
; z [wynik+12], ktora jest mniejsza od
; EBX. Ta resztka bedzie teraz starsza
; czescia liczby, ktora dzielimy.
mov eax, [arg1+8]
div ebx
mov [wynik+8], eax

; EDX bez zmian!
mov eax, [arg1+4]
div ebx
mov [wynik+4], eax

; EDX bez zmian!
mov eax, [arg1]
div ebx
mov [wynik], eax
; EDX = reszta z dzielenia

Jesli wasz dzielnik moze miec wiecej niz 32 bity, to trzeba uzyc algorytmu
podobnego do tego, ktorego uczylismy sie w szkole. Ale po takie szczegoly
odsylam do AoA (patrz ostatni akapit w tym tekscie).


---------------------------------------------------------------------------


Przerobilismy juz operacje arytmetyczne, przyszla wiec kolej na operacje
logiczne.
Na szczescie operacje bitowe AND, OR, XOR i NOT nie zaleza od wynikow
poprzednich dzialan, wiec po prostu wykonujemy je na odpowiadajacych sobie
czesciach zmiennych i niczym innym sie nie przejmujemy.

Oto przyklad (obliczenie "arg1" AND "arg2"):

mov eax, [arg1]
and eax, [arg2]
mov [wynik], eax

mov eax, [arg1+4]
and eax, [arg2+4]
mov [wynik+4], eax

mov eax, [arg1+8]
and eax, [arg2+8]
mov [wynik+8], eax

mov eax, [arg1+12]
and eax, [arg2+12]
mov [wynik+12], eax

Pozostale trzy (OR, XOR i NOT) beda przebiegac dokladnie w ten sam sposob.


---------------------------------------------------------------------------


Sprawa z przesunieciami (SHL/SHR) i rotacjami jest nieco bardziej
skomplikowana, gdyz bity wychodzace z jednej czesci zmiennej musza jakos
znalezc sie w wyzszej czesci. Ale spokojnie, nie jest to az takie trudne,
gdy przypomnimy sobie, ze ostatni wyrzucony bit laduje we fladze CF.
A co zrobic, gdy chcemy przesuwac o wiecej niz jeden bit (wszystkie wyrzucone
bity nie znajda sie przeciez naraz w CF)?
Niestety, trzeba to robic po jednym bicie na raz. Ale ani SHL ani SHR nie
pobiera niczego z flagi CF. Dlatego uzyjemy operacji rotacji bitow przez
flage CF.

Pora na przyklad (SHL "arg1", 2):

shl dword [arg1], 1 ; wypychamy najstarszy bit do CF
rcl dword [arg1+4], 1 ; wypchniety bit wyladuje tutaj w bicie
; nr 0, a najstarszy zostaje wypchniety
; do CF

rcl dword [arg1+8], 1 ; najstarszy bit z [arg1+4] staje sie
; tutaj najmlodszym, a najstarszy z tej
; czesci laduje w CF
rcl dword [arg1+12], 1 ; najstarszy bit z [arg1+8] staje sie
; tutaj najmlodszym, a najstarszy z tej
; czesci laduje w CF

; mamy juz SHL o 1 pozycje. Teraz drugi raz
; (dokladnie tak samo):
shl dword [arg1], 1
rcl dword [arg1+4], 1
rcl dword [arg1+8], 1
rcl dword [arg1+12], 1

Podobnie bedzie przebiegac operacja SHR
(rzecz jasna, SHR wykonujemy OD GORY):

; SHR "arg1", 1

shr dword [arg1+12], 1 ; wypychamy najmlodszy bit do CF
rcr dword [arg1+8], 1 ; wypchniety bit wyladuje tutaj w bicie
; najstarszym, a najmlodszy zostaje
; wypchniety do CF
rcr dword [arg1+4], 1 ; najmlodszy bit z [arg1+8] staje sie
; tutaj najstarszym, a najmlodszy z tej
; czesci laduje w CF
rcr dword [arg1], 1 ; najmlodszy bit z [arg1+4] staje sie
; tutaj najstarszym, a najmlodszy z tej
; czesci laduje w CF


Gorzej jest z obrotami (ROL, ROR, RCL, RCR), gdyz ostatni wypchniety bit
musi sie jakos znalezc na poczatku. Oto, jak mozemy to zrobic
(pokaze ROL "arg1", 1):

; najpierw normalny SHL:

shl dword [arg1], 1
rcl dword [arg+4], 1
rcl dword [arg+8], 1
rcl dword [arg1+12], 1

; teraz ostatni bit jest w CF. Przeniesiemy go do najmlodszego bitu EBX.

mov ebx, 0 ; nie uzywac XOR! (zmienia flagi)
rcl ebx, 1 ; teraz EBX = CF (mozna tez uzyc
; "ADC ebx, 0")

; i pozostaje nam juz tylko dopisac najmlodszy bit w wyniku:

or [arg1], ebx ; lub ADD - bez roznicy

ROL o wiecej niz 1 bedzie przebiegac dokladnie tak samo (ten sam kod trzeba
powtorzyc wielokrotnie). Sprawa z RCL rozni sie niewiele od tego, co
pokazalem wyzej. Scisle mowiac, SHL zamieni sie na RCL i nie musimy zajmowac
sie bitem, ktory wychodzi do CF (bo zgodnie z tym, jak dziala RCL ten bit
musi tam pozostac). Cala "operacja" bedzie wiec wygladac po prostu tak:

rcl dword [arg1], 1
rcl dword [arg+4], 1
rcl dword [arg+8], 1
rcl dword [arg1+12], 1

Operacje ROR i RCR przebiegaja podobnie:
; ROR "arg1", 1

; najpierw normalny SHR (pamietajcie, ze od gory):

shr dword [arg1+12], 1
rcr dword [arg1+8], 1
rcr dword [arg1+4], 1
rcr dword [arg1], 1 ; najmlodszy bit zostal wypchniety

; teraz ostatni bit jest w CF. Przeniesiemy go do najstarszego bitu EBX.

mov ebx, 0 ; nie uzywac XOR! (zmienia flagi)
rcr ebx, 1 ; teraz EBX = 00 00 00 00 lub
; 80 00 00 00h

; i pozostaje nam juz tylko dopisac najstarszy bit w wyniku:

or [arg1+12], ebx
I juz tylko prosty RCR:
rcr dword [arg1+12], 1
rcr dword [arg1+8], 1
rcr dword [arg1+4], 1
rcr dword [arg1], 1



To by bylo na tyle z rozszerzonej ayrtmetyki. Mam nadzieje, ze algorytmy
te wytlumaczylem wystarczajaco dobrze, abyscie mogli je zrozumiec. Jesli
nawet cos nie jest od razu jasne, to nalezy przejrzec rozdzial o
instrukcjach procesora i wrocic tutaj - to powinno rozjasnic wiele
ewentualnych watpliwosci.


-----------------------------------------------------------------------------

Niektore algorytmy zawarte tutaj wzialem ze wspanialej ksiazki
Art of Assembler (Art of Assembly Language Programming, AoA)
autorstwa Randalla Hyde'a. Ksiazke te zawsze i wszedzie polecam jako swietny
material do nauki nie tylko samego assemblera, ale takze architektury
komputerow i logiki. Ksiazka ta dostepna jest ZA DARMO ze strony

http://webster.cs.ucr.edu




----------------------------------------------------------------------------
Cwiczenia:

1. Napisz program, ktory zrobi, co nastepuje:
a) Przemnozy EAX przez EBX (wartosci dowolne, ale nie za male) i zachowa
wynik (najlepiej w rejestrach).
b) Przemnozy ECX przez EBP.
c) Jesli dowolny wynik wyszedl zero (sprawdzic kazdy co najwyzej 1
instrukcja), to niech przesunie te drugi w prawo o 4 miejsca. Jesli
nie, to niech doda je do siebie.