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

Część 15 - Pętle i warunki - czyli o tym, jak używać bloków kontrolnych

Wszystkie języki wysokiego poziomu mają pewne bloki kontrolne i pętle, co może w oczach niektórych osób stanowić przewagę nad asemblerem. Dlatego teraz pokażę, jak przepisać te wszystkie struktury z wykorzystaniem asemblera, często uzyskując kod lepszy niż ten wytworzony przez kompilatory języków wyższego poziomu.
Zanim zaczniemy, dodam, że nie każdy język wysokiego poziomu posiada opcje kompilacji warunkowej (coś w stylu #ifdef w języku C), ale za to KAŻDY dobry kompilator języka asembler ma taką opcję wbudowaną! Po szczegóły odsyłam do instrukcji posiadanego kompilatora.


Bloki decyzyjne (warunkowe) if/else if/else.


(przeskocz bloki warunkowe)

Przetłumaczenie czegoś takiego na asembler nie jest trudne i opiera się na instrukcjach CMP oraz odpowiednich skokach warunkowych. Pokażę to na przykładzie (będę używał składni języka C, gdyż posiada wszystkie struktury, które chciałbym omówić):


(przeskocz schemat bloku if/else)
	if (a == b)		/* czy a jest równe b? */
	{
		/* część 1 */
	}
	else if (a == c)
	{
		/* część 2 */
	}
	else
	{
		/* część 3 */
	}

Powyższy kod można po prostu zastąpić czymś takim (zakładam zmienne 32-bitowe):


(przeskocz asemblerowy schemat bloku if/else)
		mov	eax, [a]
		cmp	eax, [b]
		jne	elseif1

		; część 1

		jmp	po_if1
	elseif1:
		cmp	eax, [c]	; pamiętajmy, że [a] już jest w EAX
		jne	else1

		; część 2

		jmp	po_if1
	else1:

		; część 3

	po_if1:

Na szczególną uwagę zasługuje przypadek porównywania zmiennej do zera, gdzie zamiast instrukcji  CMP EAX, 0 użyjemy instrukcji  TEST EAX, EAX.
Jeśli zaś trafi się Wam dość prosty kod w stylu:


(przeskocz przykład if/else)
	if (a == b)		/* czy a jest równe b? */
	{
		d = a;		/* wstaw wartość a do d */
	}
	else if (a == c)
	{
		d = b;
	}
	else
	{
		d = 0;
	}

lub wyrażenie warunkowe, czyli coś postaci:

		d = (a == b)? a : 0;

To możecie (a nawet powinniście) użyć instrukcji warunkowego kopiowania danych CMOV*. Instrukcje te powodują znacznie wydajniejszą pracę procesora (który już nie musi co dwie instrukcje skakać i czytać nowych instrukcji). Pierwszy fragment kodu po przetłumaczeniu mógłby wyglądać tak:


(przeskocz tłumaczenie przykładu if/else)
	xor	edx, edx	; domyślna wartość, którą wstawimy
				; do zmiennej D wynosi zero

	mov	eax, [a]
	cmp	eax, [b]
	cmove	edx, eax	; gdy a == b, to do EDX wstaw
				; wartość A, czyli EAX

	cmp	eax, [c]
	cmove	edx, [b]	; gdy a == c, to do EDX wstaw wartość B

	mov	[d], edx	; do D wstaw wynik operacji
				; (A, B lub domyślne 0)

A drugi:


(przeskocz tłumaczenie wyrażenia warunkowego)
	xor	edx, edx	; domyślna wartość to 0

	mov	eax, [a]
	cmp	eax, [b]	; porównaj A z B

	cmove	edx, eax	; gdy równe, to EDX=[a]

	mov	[d], edx	; do D wstaw wynik operacji

Tylko nowoczesne kompilatory języka C potrafią wyczyniać takie sztuczki.
Podobne instrukcje istnieją także dla liczb i rejestrów zmiennoprzecinkowych: FCMOV*.


Pętle.


(przeskocz pętle)

Z pętlami jest trochę gorzej, gdyż jest ich więcej rodzajów.
Zacznijmy od pętli o znanej z góry ilości przejść (powtórzeń, iteracji), czy pętli typu

	for (wyrażenia początkowe; warunek wykonywania; wyrażenie końcowe)

Na przykład:


(przeskocz przykład pętli for)
	for (i=1; i<10; i=i+1)
	{
		j=j+i;
	}

zostałoby przetłumaczone na:


(przeskocz tłumaczenie tego przykładu)
		mov	ecx, 1		; ECX to zmienna I. i=1
	petla_for:
		cmp	ecx, 10
		jae	koniec_petli	; wychodzimy, gdy i >= 10

		add	eax, ecx	; EAX to zmienna J. j=j+i

		add	ecx, 1		; i=i+1
		jmp	short petla_for
	koniec_petli:

Jeśli warunkiem zakończenia pętli jest to, że pewna zmienna osiągnie zero, można stosować instrukcję LOOP. Przykład:
(przeskocz drugą pętlę for)

	for (i=10; i>0; i--)
	{
		j=j+i;
	}

może zostać przetłumaczony na 2 sposoby:


(przeskocz sposoby tłumaczenia)
	; sposób 1:
		mov	ecx, 10		; ECX to zmienna I. i=10
	petla_for:
		cmp	ecx, 0		; lub: test ecx, ecx
		jbe	koniec_petli	; wychodzimy, gdy i <= 0

		add	eax, ecx	; EAX to zmienna J. j=j+i

		sub	ecx, 1		; i=i-1
		jmp	short petla_for
	koniec_petli:



	; sposób 2:
		mov	ecx, 10		; ECX to zmienna I. i=10
	petla_for:
		add	eax, ecx	; EAX to zmienna J. j=j+i
		loop	petla_for	; zmniejsz ECX o 1 i jeśli różny od
					;    zera, skocz do: petla_for

Pamiętajmy jednak, że instrukcja LOOP działa tylko na rejestrze (E)CX, więc jeśli chcemy mieć kilka zagnieżdżonych pętli, to przed każdą z nich (rozpoczynającą się zmianą rejestru ECX) musimy zachować ten rejestr (na przykład na stosie), a po zakończeniu pętli musimy przywrócić jego poprzednią wartość.

Sprawa z pętlami o nieznanej ilości powtórzeń nie jest o wiele trudniejsza. Pętla typu for jest całkowicie równoważna pętli while. Właśnie z tego skorzystamy, a kod niewiele będzie się różnić budową od poprzedniego przykładu.
Powiedzmy, że mamy taką pętlę:


(przeskocz ten przykład)
	for (i=100; i+1<=n; i=i+2)
	{
		j=j+i+4;
	}

Możemy ją zastąpić równoważną konstrukcją:


(przeskocz zamianę for na while)
	i=100;
	while (i+1 <= n)
	{
		j=j+i+4;
		i=i+2;
	}

Otrzymujemy kod:


(przeskocz tłumaczenie while)
		mov	ecx, 100	; ECX to zmienna I. i=100
	nasza_petla:
		mov	ebx, ecx
		add	ebx, 1		; EBX = i+1
		cmp	ebx, [n]	; sprawdzamy, czy i+1 <= n
		ja	koniec_while	; wychodzimy, gdy i+1 > n

		add	eax, ecx	; EAX to zmienna J. j=j+i
		add	eax, 4		; j=j+i+4

		add	ecx, 2		; i=i+2
		jmp	short nasza_petla
	koniec_while:

Ostatni rodzaj pętli to pętle typu do-while (repeat...until). Taka pętla różni się tym od poprzedniczek, że warunek jest sprawdzany po wykonaniu kodu pętli (czyli taka pętla zawsze będzie wykonana co najmniej raz). Daje to pewne możliwości optymalizacji kodu.
Popatrzmy na taki przykład:


(przeskocz przykład do-while)
	do
	{
		i=i+1;
		j=j-1;
	} while ((i < n) && (j > 1));

Warunek wyjścia to: i większe bądź równe n LUB j mniejsze bądź równe 1.
A teraz popatrzcie, co można z tym zrobić:


(przeskocz tłumaczenie do-while)
	petla_do:
		add	ecx, 1		; ECX to zmienna I. i=i+1
		sub	edx, 1		; EDX to zmienna J. j=j-1

		cmp	ecx, [n]
		jae	koniec		; i >= n jest jednym z warunków
					; wyjścia. Drugiego nie musimy
					; sprawdzać, bo wynik i tak
					; będzie prawdą
		cmp	edx, 1
		jbe	koniec		; j <= 1 to drugi warunek wyjścia

		jmp	petla_do
	koniec:

Można przepisać to w lepszy sposób:


(przeskocz lepszy sposób)
	petla_do:
		add	ecx, 1		; ECX to zmienna I. i=i+1
		sub	edx, 1		; EDX to zmienna J. j=j-1

		cmp	ecx, [n]
		jae	koniec		; i >= n jest jednym z warunków
					; wyjścia. Drugiego nie musimy
					; sprawdzać, bo wynik i tak
					; będzie prawdą

					; jeśli nadal tutaj jesteśmy,
					; to z pewnością i < n.
		cmp	edx, 1
		ja	petla_do	; j <= 1 to drugi warunek
					; wyjścia. Jeśli j > 1,
					; to kontynuuj wykonywanie pętli.
					; Jeśli j < 1, to po prostu
					; opuszczamy pętlę:
	koniec:

Jeśli warunek kontynuacji lub wyjścia z pętli jest wyrażeniem złożonym, to:

Przykłady:

	1)   a == 0 || (b > 1 && c < 2)
	2)   (b < d || a == 1) && c > 0

W przypadku 1 najpierw sprawdzamy, czy a jest równe zero. Jeśli jest, to cały warunek jest prawdziwy. Jeśli nie jest, sprawdzamy najpierw ten z dwóch pozostałych, który ma największą szansę bycia fałszywym (jeśli któryś jest fałszywy, to wynik jest fałszem).
W przypadku 2 najpierw sprawdzamy, czy c jest większe od zera. Jeśli nie jest, to cały warunek jest fałszywy. Jeśli jest, to potem sprawdzamy ten z pozostałych warunków, który ma większą szansę bycia prawdziwym (jeśli któryś jest prawdziwy, to wynik jest prawdą).


Decyzje wielowariantowe (wyrażenia typu switch/case)


(przeskocz decyzje wielowariantowe)

Fragment kodu:


(przeskocz schemat switch/case)
	switch (a)
	{
		case 1: .....
		case 2: .....
		....
		default: .....
	}

w prosty sposób rozkłada się na serię wyrażeń if i else if (oraz else, o ile podano sekcję default). Te zaś już umiemy przedstawiać w asemblerze. Jest jednak jedna ciekawa sprawa: jeśli wartości poszczególnych przypadków case są zbliżone (coś w stylu 1, 2, 3 a nie 1, 20, 45), to możemy posłużyć się tablicą skoków (ang. jump table). W tej tablicy przechowywane są adresy fragmentów kodu, który ma zostać wykonany, gdy zajdzie odpowiedni warunek. Brzmi to trochę pokrętnie, dlatego szybko pokażę przykład.


(przeskocz przykład switch/case)
	switch (a)
	{
		case 1:
			j=j+1;
			break;
		case 2:
			j=j+4;
			break;
		case 4:
			j=j+23;
			break;
		default:
			j=j-1;
	}

A teraz tłumaczenie:


(przeskocz tłumaczenie przykładu switch/case)
		mov	eax, [a]
		cmp	eax, 1			; jeśli a < 1 lub a > 5,
						; to na pewno default
		jb	sekcja_default

		cmp	eax, 5
		ja	sekcja_default

		jmp	[przypadki + eax*4 - 4]

	przyp1:
		add	dword ptr [j], 1	; NASM/FASM: bez słowa PTR
		jmp	koniec

	przyp2:
		add	dword ptr [j], 4	; NASM/FASM: bez słowa PTR
		jmp	koniec

	przyp4:
		add	dword ptr [j], 23	; NASM/FASM: bez słowa PTR
		jmp	koniec

	sekcja_default:
		sub	dword ptr [j], 1

	koniec:

	....
	przypadki:	dd przyp1, przyp2, sekcja_default, przyp4

Kod najpierw sprawdza, czy a ma szansę być w którymś z przypadków (jeśli nie jest, to oczywiście wykonujemy sekcję default). Potem, jeśli a=1, to skacze pod etykietę w
zmienne [przypadki + 1*4 - 4 ] = [przypadki] = przyp1.
Podobnie, jeśli a=2, skoczymy do przyp2. Jeśli a=3, skoczymy do sekcji default, a jeśli a=4, skoczymy do sekcji przyp4.

Dla programów 64-bitowych, należy użyć mnożnika wynoszącego 8 i takiego samego rozmiaru każdego elementu w tablicy:

		jmp	[przypadki + eax*8 - 8]
	....
	przypadki:	dq przyp1, przyp2, sekcja_default, przyp4

Od razu widać wielką zaletę takiego rozwiązania: w jednej jedynej instrukcji wiemy, gdzie musimy skoczyć. Jak liczba przypadków będzie wzrastać, zauważymy też wadę tego rozwiązania: rozmiar tablicy szybko rośnie (wynosi on różnicę między wartością najwyższą możliwą a najniższą możliwą pomnożoną przez 2 bajty). Dlatego to rozwiązanie jest nieprzydatne dla możliwych wartości: {1, 20, 45} (42 wartości z 45 byłyby nieużywane, czyli wskazujące na sekcję default - zdecydowane marnotrawienie pamięci). W takim przypadku lepiej użyć tradycyjnej metody if/else if/else.


Mam nadzieję, że wiedza zawarta w tej części kursu umożliwi Wam pisanie lepszych i bardziej złożonych programów niż to było do tej pory. Teraz będziecie wiedzieć, co tak właściwie robię kompilatory, tłumacząc niektóre wyrażenia kontrolne. Ta wiedza pomoże Wam pisać lepsze programy w językach wyższego poziomu (gdyż już teraz wiecie, jak zapisywać wyrażenia logiczne tak, by dostać najbardziej wydajny kod).



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. Zaimplementować zdanie:
    Jeśli EAX jest równy EBX lub ECX nie jest równy EBP, to do EDX wstaw EAX, inaczej do ECX wstaw 0.

  2. Zaimplementować zdanie (użyć instrukcji warunkowego przesuwania):
    Jeśli EAX jest równy EBX lub ECX nie jest równy EBP, to do EDX wstaw EAX, inaczej do EDX wstaw 0.

  3. Napisać program, który liczy sumę liczb od 10 do dowolnej liczby wpisanej w kodzie/czytanej z linii poleceń.

  4. Zaimplementować zdanie:
    Dopóki ECX jest większe od 1, zmniejsz ECX o 2.

  5. Zaimplementować zdanie:
    Zwiększaj EAX o 3, dopóki EAX jest mniejsze od 100.