Czasami w naszych programach zachodzi potrzeba, aby posługiwać się na przykład 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 się 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ń:
arg1i
arg2mają po 16 bajtów (128 bitów) każda. Na potrzeby nauki wystarczy w sam raz.
wynikma tyle samo bajtów, co
arg1i
arg2, z wyjątkiem mnożenia, gdzie oczywiście musi być dwa razy większa.
wynikna początku zawiera zero.
A więc do dzieła.
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
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
(Subtract with Borrow).
Działa ona tak samo, jak
zwykła instrukcja odejmowania SUB
, ale dodatkowo odejmuje 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 ; 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 odejmujemy ; pożyczki od starszych części sbb dword [arg1+8], 0 sbb dword [arg1+12], 0 neg dword [arg1] ; negujemy kolejną część i odejmujemy ; 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 poprzedni 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, na przykład 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)
Obliczenia wyglądałyby tak (pamiętamy, że wynik operacji MUL jest w EDX:EAX):
; przez rozpoczęciem procedury zmienna "wynik" musi być wyzerowana! ;[wynik] = L = D*S mov eax, dword [arg1] ; EAX = D mul dword [arg2] ; EDX:EAX = D*S mov dword [wynik], eax mov dword [wynik+4], edx ;[wynik+4] = K = C*S + D*R mov eax, dword [arg1+4] ; EAX = C mul dword [arg2] ; EDX:EAX = C*S add dword [wynik+4], eax adc dword [wynik+8], edx adc dword [wynik+12], 0 mov eax, dword [arg1] ; EAX = D mul dword [arg2+4] ; EDX:EAX = D*R add dword [wynik+4], eax adc dword [wynik+8], edx adc dword [wynik+12], 0 ;[wynik+8] = J = B*S + C*R + D*Q mov eax, dword [arg1+8] ; EAX = B mul dword [arg2] ; EDX:EAX = B*S add dword [wynik+8], eax adc dword [wynik+12], edx adc dword [wynik+16], 0 mov eax, dword [arg1+4] ; EAX = C mul dword [arg2+4] ; EDX:EAX = C*R add dword [wynik+8], eax adc dword [wynik+12], edx adc dword [wynik+16], 0 mov eax, dword [arg1] ; EAX = D mul dword [arg2+8] ; EDX:EAX = D*Q add dword [wynik+8], eax adc dword [wynik+12], edx adc dword [wynik+16], 0 ;[wynik+12] = I = A*S + B*R + C*Q + D*P mov eax, dword [arg1+12] ; EAX = A mul dword [arg2] ; EDX:EAX = A*S add dword [wynik+12], eax adc dword [wynik+16], edx adc dword [wynik+20], 0 mov eax, dword [arg1+8] ; EAX = B mul dword [arg2+4] ; EDX:EAX = B*R add dword [wynik+12], eax adc dword [wynik+16], edx adc dword [wynik+20], 0 mov eax, dword [arg1+4] ; EAX = C mul dword [arg2+8] ; EDX:EAX = C*Q add dword [wynik+12], eax adc dword [wynik+16], edx adc dword [wynik+20], 0 mov eax, dword [arg1] ; EAX = D mul dword [arg2+12] ; EDX:EAX = D*P add dword [wynik+12], eax adc dword [wynik+16], edx adc dword [wynik+20], 0 ;[wynik+16] = H = A*R + B*Q + C*P mov eax, dword [arg1+12] ; EAX = A mul dword [arg2+4] ; EDX:EAX = A*R add dword [wynik+16], eax adc dword [wynik+20], edx adc dword [wynik+24], 0 mov eax, dword [arg1+8] ; EAX = B mul dword [arg2+8] ; EDX:EAX = B*Q add dword [wynik+16], eax adc dword [wynik+20], edx adc dword [wynik+24], 0 mov eax, dword [arg1+4] ; EAX = C mul dword [arg2+12] ; EDX:EAX = C*P add dword [wynik+16], eax adc dword [wynik+20], edx adc dword [wynik+24], 0 ;[wynik+20] = G = A*Q + B*P mov eax, dword [arg1+12] ; EAX = A mul dword [arg2+8] ; EDX:EAX = A*Q add dword [wynik+20], eax adc dword [wynik+24], edx adc dword [wynik+28], 0 mov eax, dword [arg1+8] ; EAX = B mul dword [arg2+12] ; EDX:EAX = B*P add dword [wynik+20], eax adc dword [wynik+24], edx adc dword [wynik+28], 0 ;[wynik+24] = F = A*P mov eax, dword [arg1+12] ; EAX = A mul dword [arg2+12] ; EDX:EAX = A*P add dword [wynik+24], eax adc dword [wynik+28], edx adc dword [wynik+32], 0
Dzielenie dwóch liczb dowolnej długoś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. Ich
normalne
wersje możecie poznać w części 13-tej kursu, teraz zajmiemy się ich rozbudowaną wersją.
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 numer 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 ; tu 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 ; tu nie używać XOR! (zmienia flagi) rcr ebx, 1 ; teraz EBX = 00000000 lub 80000000h ; i pozostaje nam już tylko dopisać najstarszy bit w wyniku: or [arg1+12], ebx
rcr dword [arg1+12], 1 rcr dword [arg1+8], 1 rcr dword [arg1+4], 1 rcr dword [arg1], 1
Porównywanie należy oczywiście zacząć od najstarszej części i schodzić do coraz to niższych części. Pierwsza różniąca się para porównywanych elementów powie nam, jaka jest relacja między całymi liczbami. Porównywać można dowolną liczbę bitów na raz, w tym przykładzie użyję podwójnych słów (32 bity) i będę sprawdzał na równość:
mov eax, [arg1+12] cmp eax, [arg2+12] ; porównujemy najstarsze części jne nie_rowne mov eax, [arg1+8] cmp eax, [arg2+8] jne nie_rowne mov eax, [arg1+4] cmp eax, [arg2+4] jne nie_rowne mov eax, [arg1] cmp eax, [arg2] ; porównujemy najmłodsze części jne nie_rowne jmp rowne
Porównywanie liczb na inne warunki niż równość lub nierówność jest jednak trochę trudniejsze. Jest tak dlatego, gdyż nawet jeśli najstarsza część pierwszej liczby nie jest, na przykład, większa od najstarszej części drugiej liczby, to nie możemy od razu przejść do porównywania drugich części liczb.
Może się zdarzyć, że najstarsza część pierwszej liczby jest mniejsza od najstarszej części drugiej liczby, a druga część pierwszej liczby jest większa od drugiej części drugiej liczby. Nie możemy się w takim przypadku zgodzić z tym, że pierwsza liczba jest większa od drugiej (gdyż w tym przypadku to najstarsze części liczb powinny o tym decydować).
Dlatego należy wprowadzić dodatkowy skok warunkowy po porównaniu każdej pary części liczb, na przykład:
mov eax, [arg1+12] cmp eax, [arg2+12] ; porównujemy najstarsze części ja pierwsza_wieksza jb druga_wieksza ; skoro ani JA, ani JB, to wiemy, że te części tych liczb są równe mov eax, [arg1+8] cmp eax, [arg2+8] ja pierwsza_wieksza jb druga_wieksza mov eax, [arg1+4] cmp eax, [arg2+4] ja pierwsza_wieksza jb druga_wieksza mov eax, [arg1] cmp eax, [arg2] ; porównujemy najmłodsze części ja pierwsza_wieksza jb druga_wieksza jmp rowne
Teraz do porównywania drugich i dalszych części liczb przechodzimy tylko w przypadku, gdy najstarsze części są równe. W innym przypadku albo pierwsza, albo druga liczba jest większa.
To by było na tyle z rozszerzonej arytmetyki. 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 asembler (Art of asembly Language Programming, AoA) autorstwa Randalla Hyde'a. Książkę tę zawsze i wszędzie polecam jako świetny materiał do nauki nie tylko samego asemblera, ale także architektury komputerów i logiki. Książka ta dostępna jest ZA DARMO.