Jak pisać programy w języku asembler pod Linuksem?

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

  1. 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.
  2. Zmienne arg1 i arg2 mają po 16 bajtów (128 bitów) każda. Na potrzeby nauki wystarczy w sam raz.
  3. 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.
  4. Zmienna wynik na początku zawiera zero.
  5. 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. 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):


(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

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.


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

  1. Napisz program, który zrobi, co następuje:
    1. Przemnoży EAX przez EBX (wartości dowolne, ale nie za małe) i zachowa wynik (najlepiej w rejestrach).
    2. Przemnoży ECX przez EBP.
    3. 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.