Asembler: DOS, część 14 - Wielokrotna precyzja













Jak pisać programy w języku asembler?
Część 14 - Wielokrotna precyzja, czyli co robić,
gdy dane nie mieszczą się w rejestrach



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ń:

Będę tutaj używał rejestrów 32-bitowych, 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 (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.







Dodawanie

(przeskocz dodawanie)

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:
(przeskocz program do dodawania)


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








Odejmowanie

(przeskocz 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 (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):
(przeskocz program do odejmowania)


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






Zmiana znaku liczby

(przeskocz NEG)

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):
(przeskocz program do negacji)


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

(przeskocz mnożenie)

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:

(przeskocz schemat mnożenia)


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):
(przeskocz program mnożenia)

; 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

(przeskocz dzielenie)

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):
(przeskocz program dzielenia)


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).







Operacje logiczne i bitowe

(przeskocz operacje bitowe)

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):
(przeskocz AND)

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):

(przeskocz SHL)

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):
(przeskocz SHR)

; 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):
(przeskocz ROL)

; 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:
(przeskocz RCL)

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:
(przeskocz ROR)

; 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

I już tylko prosty RCR:
(przeskocz RCR)

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










Porównywanie liczb

(przeskocz porównywanie)

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ść:

(przeskocz program do porównywania)

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



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.




Poprzednia część kursu (Alt+3)
Kolejna część kursu (Alt+4)
Spis treści off-line (Alt+1)
Spis treści on-line (Alt+2)
Ułatwienia dla niepełnosprawnych (Alt+0)





Ć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.