A KURS14




Podstawy języka assembler, cz. 14










Jak pisać programy w języku assembler?
Część 14 - Operacje o wielokrotnej precyzji, czyli co zrobić,
gdy liczby nie mieszczą się w rejestrach.



Czasami w naszych programach zachodzi potrzeba, aby posługiwać się np. liczbami przekraczającymi
4 czy nawet 8 bajtów, a my mamy tylko rejestry 32-bitowe (lub czasem 16-bitowe).
Co wtedy zrobić?
Odpowiedzi na to właśnie pytanie postaram się udzielić w tej części kursu.



Do naszych celów posłuży coś, co sę nazywa "arytmetyką wielokrotnej precyzji" (ang.
Multiprecision Arithmetic). Generalną zasadą będzie zajmowanie się obliczeniami "po kawałku"
(bo z resztą inaczej się nie da) i zapamiętywanie, czy z poprzedniego kawałka wynieśliśmy coś
"w pamięci" (do tego celu w prosty sposób wykorzystamy flagę CF, która wskazuje właśnie, czy
nie nastąpiło przepełnienie).
Najpierw kilka ustaleń:

Będę tutaj używał rejestrów 32-bitowch, ale w razie potrzeby dokładnie
te same algorytmy działają także dla rejestrów innych rozmiarów.
Zmienne "arg1" i "arg2" mają po 16 bajtów, tj. po 128 bitów każda. Na potrzeby nauki
wystarczy w sam raz.
Zmienna "wynik" ma tyle samo bajtów, co "arg1" i "arg2", z wyjątkiem mnożenia,
gdzie oczywiście musi być dwa razy większa.
Zmienna "wynik" na początku zawiera zero.
Kod nie zawsze będzie optymalny, ale chodzi mi o to, aby był jak najbardziej jasny i przejrzysty.


A więc do dzieła.

Zacznijmy od dodawania. Dodawanie, podobnie jak uczyli nas w szkole, zaczynamy od najmłodszych
cyfr (cyfr jedności) - tyle że zamiast pojedynczych cyferek będziemy dodawać całe 32-bitowe
kawałki naraz. Flaga CF powie nam, czy z poprzedniego dodawania wynosimy coś w pamięci (nawet z
dodawania dużych liczb wyniesiemy co najwyżej 1 bit "w pamięci"). To coś
trzeba oczywiście dodać potem do wyższej części wyniku.
No to dodajemy:


mov eax, [arg1]
add eax, [arg2] ; dodajemy 2 pierwsze części liczb
mov [wynik], eax ; i ich sumę zapisujemy w pierwszej
; części wyniku. Flaga CF mówi, czy
; wynosimy coś w pamięci

mov eax, [arg1+4]
adc eax, [arg2+4] ; dodajemy drugie części + to,
; co wyszło z poprzedniego dodawania
; [arg1] i [arg2] (a to jest w fladze
; CF, stąd instrukcja ADC zamiast ADD)

mov [wynik+4], eax ; całość:[arg1+4]+[arg2+4]+"w pamięci z
; pierwszego dodawania" zapisujemy tu.
; Flaga CF zawiera (lub nie) bit
; "w pamięci", ale tym razem z ADC

; podobnie reszta działania:
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, że zaczynamy od najmłodszych cyfr i
ewentualnie "pożyczamy" od starszych. Tutaj będziemy robić dokładnie tak samo! Wymaga to
jednak poznania nowej instrukcji - SBB (Substract with Borrow). Działa ona tak samo, jak
zwykła instrukcja odejmowania SUB, ale dodatkowo odemuje wartość flagi CF, czyli 1 lub 0,
w zależności od tego, czy w poprzednim kroku musieliśmy "pożyczać" czy też nie. Ewentualną
"pożyczkę" trzeba oczywiście odjąć od wyższej części wyniku.
Piszmy więc (od "arg1" będziemy odejmować "arg2"):

mov eax, [arg1]
sub eax, [arg2] ; odejmujemy 2 pierwsze części
mov [wynik], eax ; i zapisujemy wynik
; flaga CF mówi, czy była pożyczka

mov eax, [arg1+4]
sbb eax, [arg2+4] ; odejmujemy razem z pożyczką (CF),
; jeśli w poprzednim odejmowaniu
; musieliśmy coś pożyczać

mov [wynik+4], eax ; wynik: [arg1+4]-[arg2+4]-"pożyczka
; z pierwszego odejmowania"
; Flaga CF teraz zawiera pożyczkę z SBB

; podobnie reszta działania:
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 się negacją (zmianą znaku liczby). Ta operacja jest o tyle "dziwna", że
wykonujemy ją "od góry" (od najstarszych bajtów) i po negacji niższych trzeba zadbać o
"pożyczkę" we wszystkich wyższych częściach.
Popatrzcie (będziemy negować "arg1"):

neg dword [arg1+12] ; negujemy najstarszą część

neg dword [arg1+8] ; negujemy drugą od góry
sbb dword [arg1+12], 0 ; jeśli była pożyczka od starszej
; (a prawie zawsze będzie), to tę
; pożyczkę odejmujemy od starszej

neg dword [arg1+4] ; negujemy kolejną część i odejumjemy
; pożyczki od starszych części
sbb dword [arg1+8], 0
sbb dword [arg1+12], 0

neg dword [arg1] ; negujemy kolejną część i odejumjemy
; pożyczki od starszych części
sbb dword [arg1+4], 0
sbb dword [arg1+8], 0
sbb dword [arg1+12], 0

Dla większych liczb nie wygląda to za ciekawie. Dlatego najprostszym sposobem będzie po prostu
odjęcie danej liczby od zera, do czego zastosujemy zwykły algorytm odejmowania.

 

Mnożenie jest nieco bardziej skomplikowane, ale ciągle robione tak jak w szkole, czyli od
prawej. Ustalmy dla wygody, że arg1 zawiera ABCD, a arg2 - PQRS (każda z liter oznacza 32
bajty). Ogólny schemat wygląda 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, każdy iloczyn zajmuje 2 razy po 4 bajty, np. L zajmuje [wynik] i
częściowo [wynik+4], ale tutaj podałem tylko miejsca, gdzie pójdą najmłodsze części
każdego w iloczynów)

Policzenie L i K wyglądałoby tak (pamiętamy, że wynik mnożenia 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 będziemy dalej liczyć


 

Dzielenie dwóch liczb dowolnej dlugości może być kłopotliwe i dlatego zajmiemy się przypadkiem
dzielenia dużych liczb przez liczbę, która mieści się w 32 bitach. Dzielić będziemy od
najstarszych bajtów do najmłodszych. Jedna sprawa zasługuje na uwagę: między dzieleniami
będziemy zachowywać resztę w EDX (nie będziemy go zerować), gdyż w taki sposób otrzymamy
prawidłowe 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 część wyniku już jest policzona

; EDX bez zmian! Zawiera teraz resztkę
; z [wynik+12], która jest mniejsza od
; EBX. Ta resztka będzie teraz starszą
; częścią liczby, którą 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

Jeśli wasz dzielnik może mieć więcej niż 32 bity, to trzeba użyć algorytmu podobnego do tego,
którego uczyliśmy się w szkole. Ale po takie szczegóły odsyłam do AoA (patrz ostatni akapit
w tym tekście).

 

Przerobiliśmy już operacje arytmetyczne, przyszła więc kolej na operacje logiczne.
Na szczęście operacje bitowe AND, OR, XOR i NOT nie zależą od wyników poprzednich działań,
więc po prostu wykonujemy je na odpowiadających sobie częściach zmiennych i niczym innym się
nie przejmujemy. Oto przykład (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

Pozostałe trzy (OR, XOR i NOT) będą przebiegać dokładnie w ten sam sposób.

Sprawa z przesunięciami (SHL/SHR) i rotacjami jest nieco bardziej skomplikowana, gdyż
bity wychodzące z jednej części zmiennej muszą jakoś znaleźć się w wyższej części.
Ale spokojnie, nie jest to aż takie trudne, gdy przypomnimy sobie, że ostatni wyrzucony bit
ląduje we fladze CF.
A co zrobić, gdy chcemy przesuwać o więcej niż jeden bit (wszystkie wyrzucone bity nie
znajdą się przecież naraz w CF)?
Niestety, trzeba to robić po jednym bicie na raz. Ale ani SHL ani SHR nie pobiera niczego
z flagi CF. Dlatego użyjemy operacji rotacji bitów przez flagę CF.
Pora na przykład (SHL "arg1", 2):

shl dword [arg1], 1 ; wypychamy najstarszy bit do CF
rcl dword [arg1+4], 1 ; wypchnięty bit wyląduje tutaj w bicie
; nr 0, a najstarszy zostaje wypchnięty
; do CF

rcl dword [arg1+8], 1 ; najstarszy bit z [arg1+4] staje się
; tutaj najmłodszym, a najstarszy z tej
; części ląduje w CF
rcl dword [arg1+12], 1 ; najstarszy bit z [arg1+8] staje się
; tutaj najmłodszym, a najstarszy z tej
; części ląduje w CF

; mamy już SHL o 1 pozycję. Teraz drugi raz
; (dokładnie tak samo):
shl dword [arg1], 1
rcl dword [arg1+4], 1
rcl dword [arg1+8], 1
rcl dword [arg1+12], 1


Podobnie będzie przebiegać operacja SHR (rzecz jasna, SHR wykonujemy OD GÓRY):

; SHR "arg1", 1

shr dword [arg1+12], 1 ; wypychamy najmłodszy bit do CF
rcr dword [arg1+8], 1 ; wypchnięty bit wyląduje tutaj w bicie
; najstarszym, a najmłodszy zostaje
; wypchnięty do CF
rcr dword [arg1+4], 1 ; najmłodszy bit z [arg1+8] staje się
; tutaj najstarszym, a najmłodszy z tej
; części ląduje w CF
rcr dword [arg1], 1 ; najmłodszy bit z [arg1+4] staje się
; tutaj najstarszym, a najmłodszy z tej
; części ląduje w CF




Gorzej jest z obrotami (ROL, ROR, RCL, RCR), gdyż ostatni wypchnięty bit musi się
jakoś znaleźć na początku. Oto, jak możemy to zrobić (pokażę 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 najmłodszego bitu EBX.

mov ebx, 0 ; nie używać XOR! (zmienia flagi)
rcl ebx, 1 ; teraz EBX = CF (można też użyć "ADC ebx, 0")

; i pozostaje nam już tylko dopisać najmłodszy bit w wyniku:

or [arg1], ebx ; lub ADD - bez różnicy


ROL o więcej niż 1 będzie przebiegać dokładnie tak samo (ten sam kod trzeba powtórzyć
wielokrotnie). Sprawa z RCL różni się
niewiele od tego, co pokazałem wyżej. Ściśle mówiąc, SHL zamieni się na RCL i nie musimy
zajmować się bitem, który wychodzi do CF (bo zgodnie z tym, jak działa RCL ten bit musi
tam pozostać). Cała "operacja" będzie więc wyglądać 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 przebiegają podobnie:

; ROR "arg1", 1

; najpierw normalny SHR (pamiętajcie, że od góry):

shr dword [arg1+12], 1
rcr dword [arg1+8], 1
rcr dword [arg1+4], 1
rcr dword [arg1], 1 ; najmłodszy bit został wypchnięty

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

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

; i pozostaje nam już tylko dopisać najstarszy bit w wyniku:

or [arg1+12], ebx

I już tylko prosty RCR:

rcr dword [arg1+12], 1
rcr dword [arg1+8], 1
rcr dword [arg1+4], 1
rcr dword [arg1], 1


 

To by było na tyle z rozszerzonej ayrtmetyki. Mam nadzieję, że algorytmy te wytłumaczyłem
wystarczająco dobrze, abyście mogli je zrozumieć. Jeśli nawet coś nie jest od razu jasne, to
należy przejrzeć rozdział o instrukcjach procesora i wrócić tutaj - to powinno rozjaśnić
wiele ewentualnych wątpliwości.



Niektóre algorytmy zawarte tutaj wziąłem ze wspaniałej książki Art of Assembler (Art of
Assembly Language Programming, AoA) autorstwa Randalla Hyde'a. Książkę tę zawsze i
wszędzie polecam
jako świetny materiał do nauki nie tylko samego assemblera, ale także architektury komputerów
i logiki. Książka ta dostępna jest ZA DARMO ze strony
http://webster.cs.ucr.edu


Ćwiczenia:

Napisz program, który zrobi, co następuje:

Przemnoży EAX przez EBX (wartości dowolne, ale nie za małe) i zachowa wynik (najlepiej
w rejestrach).
Przemnoży ECX przez EBP.
Jeśli dowolny wynik wyszedł zero (sprawdzić każdy co najwyżej 1 instrukcją), to niech
przesunie te drugi w prawo o 4 miejsca. Jeśli nie, to niech doda je do siebie.






Wyszukiwarka

Podobne podstrony:
A KURS14
A KURS14
a kurs14
DOS A KURS14
A KURS14

więcej podobnych podstron