Jak pisać programy w języku asembler?

Część 13 - Operacje na bitach, czyli to, w czym asembler błyszczy najbardziej

W tej części poznamy ważną grupę instrukcji - operacje na bitach. Te właśnie instrukcje odróżniają asemblera od innych języków, gdzie rzadko pojawia się możliwość działania na tych najmniejszych jednostkach informacji (odpowiednie operatory istnieją w językach C i Pascal, ale inne języki, jak na przykład Fortran 77, są tego pozbawione).
Mimo iż o wszystkich instrukcjach opisanych w tej części już wspomniałem przy okazji omawiania podstawowych rozkazów procesora, to instrukcje bitowe są ważne i zasługują na oddzielny rozdział, poświęcony w całości tylko dla nich.

Zdawać by się mogło, że z takim jednym, maleńkim bitem niewiele da się zrobić: można go wyczyścić (wyzerować), ustawić (wstawić do niego 1) lub odwrócić jego bieżącą wartość. Ale te operacje mają duże zastosowania i dlatego ich poznanie jest niezbędne. Jeśli sobie przypomnicie, to używaliśmy już wielokrotnie takich instrukcji jak AND czy XOR. Teraz przyszedł czas, aby poznać je bliżej.


Instrukcja NOT


(przeskocz NOT)

Instrukcja NOT (logiczna negacja - to NIE jest to samo, co zmiana znaku liczby!) jest najprostszą z czterech podstawowych operacji logicznych i dlatego to od niej rozpocznę wstęp do instrukcji bitowych.

NOT jest instrukcją jednoargumentową, a jej działanie wygląda tak:

	NOT 0 = 1
	NOT 1 = 0

Używamy tej instrukcji wtedy, gdy chcemy naraz odwrócić wszystkie bity w zmiennej lub rejestrze. Na przykład, jeśli AX zawiera 0101 0011 0000 1111 (530Fh), to po wykonaniu NOT AX w rejestrze tym znajdzie się wartość 1010 1100 1111 0000 (ACF0h). Dodanie obu wartości powinno dać FFFFh.

NOT może mieć zastosowanie tam, gdzie wartość logiczna fałsz ma przyporządkowaną wartość zero, a prawda - wartość FFFFh, gdyż NOT w tym przypadku dokładnie przekłada prawdę na fałsz.



Instrukcja AND


(przeskocz AND)

Instrukcji AND (logicznej koniunkcji) najprościej używać do wyzerowania bitów. Tabelka działania AND wygląda tak:

	0 AND 0 = 0
	0 AND 1 = 0
	1 AND 0 = 0
	1 AND 1 = 1

No ale jakie to może mieć zastosowanie?
Powiedzmy teraz, że chcemy sprawdzić, czy bit numer 4 (numerację będę podawał od zera) rejestru AX jest równy 1, czy 0. Tutaj nie wystarczy proste porównanie CMP, gdyż reszta rejestru może zawierać nie wiadomo co. Z pomocą przychodzi nam właśnie instrukcja AND. Poniżej pseudo-przykład:

	and	ax, 0000 0000 0001 0000b	; (and ax, 16)

Teraz, jeśli bit numer 4 (odpowiadający wartości 2^4=16) był równy 1, to cały AX przyjmie wartość 16, jeśli zaś był równy zero, to cały AX będzie zerem. Na nasze szczęście, instrukcja AND ustawia odpowiednio flagi procesora, więc rozwiązaniem naszego problemiku będzie kod:

	and	ax, 16
	jz	bit_4_byl_zerem
	;jnz	bit_4_nie_byl_zerem

A jakieś zastosowanie praktyczne?
Już podaję: zamiana małych liter na wielkie. W kodzie ASCII litery małe od wielkich różnią się tylko tym, że mają ustawiony bit numer 5. Tak więc po wykonaniu:

	mov	al, "a"
	and	al, 5fh		; 5fh = 0101 1111 - czyścimy bit 5
				; (i 7 przy okazji)

w rejestrze AL będzie kod wielkiej litery A.
Inne zastosowanie znajdziecie w moim kursie programowania głośniczka:

	in	al, 61h
	and	al, not 3		; zerujemy bity 0 i 1
					; NASM: and al,~3
	out	61h, al

W tym kodzie instrukcja AND posłużyła nam do wyczyszczenia bitów 0 i 1 (NOT 3 = NOT 0000 0011 = 1111 1100).

Jak zauważyliście, instrukcja AND niszczy zawartość rejestru, oprócz interesujących nas bitów. Jeśli zależy Wam na zachowaniu rejestru, użyjcie instrukcji TEST. Działa ona identycznie jak AND, ale nie zapisuje wyniku działania. Po co nam więc taka instrukcja? Otóż, wynik nie jest zapisywany, ale TEST ustawia dla nas flagi identycznie jak AND. Pierwszy kod przepisany z instrukcją TEST będzie wyglądał tak:

	test	ax, 16
	jz	bit_4_byl_zerem
	;jnz	bit_4_nie_byl_zerem

Teraz nasz program będzie ciągle działać prawidłowo, ale tym razem zawartość rejestru AX została zachowana.
Jest jeszcze jedno ciekawe zastosowanie instrukcji TEST:

	test	ax, ax

I co to ma niby robić? Wykonuje  AND AX, AX , nigdzie nie zapisuje wyniku i tylko ustawia flagi.
No właśnie! Ustawia flagi, w tym flagę zera ZF. To, co widzicie powyżej to najwydajniejszy sposób na to, aby sprawdzić czy wartość rejestru nie jest zerem.




Instrukcja OR


(przeskocz OR)

Instrukcja OR (logiczna alternatywa) w prosty sposób służy do ustawiania bitów (wpisywania do nich 1).
Tabelka działania wygląda następująco:

	0 OR 0 = 0
	0 OR 1 = 1
	1 OR 0 = 1
	1 OR 1 = 1

Jeśli na przykład chcemy, aby 2 najmłodsze bity rejestru BX były się równe 1, a nie chcemy naruszać innych bitów (czyli MOV jest wykluczone), możemy to zrobić tak:

	or	bx, 0000 0000 0000 0011		; (or bx, 3)

Zastosowanie tego jest proste. Podam 2 przykłady. Pierwszy z nich jest wyjęty z mojej procedury wytwarzającej dźwięk w głośniczku (i kursu poświęconego temu zagadnieniu):

	in	al, 61h
	or	al, 3				; ustawiamy bity 0 i 1
	out	61h, al

Przykład drugi jest odwróceniem operacji AND na znakach ASCII:

	mov	al, "A"
	or	al, 20h			; 20h = 0010 0000 - ustawiamy bit 5

teraz w AL powinien być kod małej literki a.
Instrukcja OR nie ma swojego odpowiednika, jakim jest TEST dla AND. Ale za to ma inne ciekawe zastosowanie - można nią sprawdzić, czy 2 rejestry naraz nie są zerami (to jest najlepszy sposób - bez żadnych CMP, JNZ/JZ itp.):

	or	ax, bx

Podobnie, jak w instrukcji AND, flaga zera będzie ustawiona, gdy wynik operacji jest zerem - a to może się zdarzyć tylko wtedy, gdy AX i BX są jednocześnie zerami.
Zauważcie, że nie można do tego celu użyć instrukcji AND. Dlaczego? Podam przykład: niech AX=1 i BX = 8. AX i BX nie są oczywiście równe zero, ale:

		0000 0000 0000 0001	(=AX)
	AND	0000 0000 0000 1000	(=BX)
		=
		0000 0000 0000 0000

Dlatego zawsze należy przemyśleć efekt działania instrukcji.




Instrukcja XOR


(przeskocz XOR)

Instrukcji XOR (eXclusive OR, logiczna alternatywa wykluczająca) używa się do zmiany stanu określonego bitu z 0 na 1 i odwrotnie.
Działanie XOR jest określone tak:

	0 XOR 0 = 0
	0 XOR 1 = 1
	1 XOR 0 = 1
	1 XOR 1 = 0

Zauważmy także, że dla dowolnych a i b mamy:
(a XOR b) XOR b = a
a XOR 0 = a
a XOR -1 = NOT a (-1 = FF w bajcie, FFFF w słowie i FFFFFFFF w dwordzie)
a XOR a = 0
Z tej ostatniej równości wynika natychmiast, że wyXORorwanie rejestru z samym sobą zawsze go wyzeruje. W ten sposób otrzymujemy jeden z dwóch najwydajniejszych sposobów na wyzerowanie rejestru:

	xor	rej, rej

Drugi sposób to SUB rej,rej.

Teraz przykład: chcemy, aby wartość rejestru AX stała się równa 1 gdy rejestr był wyzerowany, a zerem, gdy była w tym rejestrze jedynka. Oto, jak możemy to zrobić:

		cmp	ax, 1
		je	wyzeruj
		mov	ax, 1
		jmp	koniec
	wyzeruj:
		mov	ax, 0
	koniec:

Ale wersja optymalna wygląda tak:

	xor	ax, 1

gdyż mamy:

	wartość AX:	0000 0000 0000 0001		0000 0000 0000 0000
		XOR	0000 0000 0000 0001		0000 0000 0000 0001
		=
	nowy AX:	0000 0000 0000 0000		0000 0000 0000 0001

Jak widać, jest to o wiele prostsze i wydajniejsze rozwiązanie. Dlatego właśnie dobrze jest, gdy pozna się instrukcje logiczne.




Instrukcje przesuwania bitów


(przeskocz instrukcje przesuwania)

Instrukcje przesuwania bitów (shift) przemieszczają bity, nie zmieniając ich wzajemnego położenia (przesuwają grupowo). To wyjaśnienie może się wydawać bardzo pokrętne, ale spokojnie - zaraz wszystko się wyjaśni.
Na początek powiem, że jest kilka takich instrukcji (które też były podane w rozdziale o podstawowych instrukcjach procesora):

Działanie każdej z tych instrukcji pokażę na przykładzie.
Niech na początku AX = 1010 0101 1010 0101 (A5A5h).

SHL i równoważna SAL działa tak (zakładając, że przesuwamy o jeden): najstarszy bit jest we fladze CF, każdy inny bit wchodzi na miejsce bitu starszego o 1, a do bitu zerowego wkładane jest zero.
Po wykonaniu SHL AX,3 wartość AX będzie więc wynosić 0010 1101 0010 1000 (2D28h), gdyż wszystkie bity przesunęliśmy o 3 miejsca w lewo, oraz CF=1 (bo jako ostatnia z rejestru wyleciała jedynka).

Instrukcja SHR działa w drugą stronę niż SHL: bit zerowy jest umieszczany we fladze CF, każdy inny bit wchodzi na miejsce bitu młodszego o 1, a do najstarszego bitu wkładane jest zero.
Dlatego teraz po wykonaniu SHR AX,1 w rejestrze AX będzie 0001 0110 1001 0100 (1694h), bo poprzednie bity AX przesunęliśmy o 1 miejsce w prawo, oraz CF=0.

SAR różni się od SHR nie tylko nazwą, ale też działaniem. Słowo arytmetyczne w nazwie NIE jest tu bez znaczenia. Gdy SAR działa na liczbach ze znakiem, to zachowuje ich znak (bit7), czyli wykonuje to samo, co SHR, ale zamiast wkładać zero do najstarszego bitu, wstawia tam jego bieżącą wartość.
Z poprzedniego przykładu mamy, że AL = 94h = 1001 0100. Gdy teraz wykonamy SAR AL,2 to jako wynik otrzymamy 1110 0101 (E5h), bo wszystkie bity poszły o 2 miejsca w prawo o bit 7 został zachowany, i CF=0.

SHLD i SHRD wykonują to samo, co SHL i SHR ale na dwóch rejestrach naraz (no, prawie). Na przykład wykonanie  SHLD EAX,EBX,3 spowoduje że 3 najstarsze bity EAX zostaną wyrzucone (i CF=ostatni z wyrzuconych) oraz 3 najstarsze bity EBX przejdą na nowo powstałe miejsca w 3 najmłodszych bitach EAX. Ale uwaga: EBX pozostaje niezmieniony ! I to jest właśnie przyczyna użycia słów no prawie.

Ale nie sposób powiedzieć o SHL i SHR bez podania najbardziej popularnego zastosowania: szybkie mnożenie i dzielenie.
Jak można mnożyć i dzielić tylko przesuwając bity, pytacie?
Otóż, sprawa jest bardzo prosta. Wpiszcie do AX jedynkę i wykonajcie kilka razy SHL AX,1 za każdym razem sprawdzając zawartość AX. Jak zauważycie, w AX będą kolejno 1,2,4,8,16,... Czyli za każdym razem zawartość AX się podwaja.
Ogólnie,  SHL rej,n mnoży zawartość rejestru przez 2^n. Na przykład  SHL AX,4 przemnoży AX przez 2^4 = 16.
Ale co zrobić, gdy chcemy mnożyć przez coś innego niż 2^n?
Odpowiedź jest równie prosta, na przykład AX * 10 = (AX*8) + (AX*2) - z tym się chyba zgodzicie. A od tego już tylko 1 krok do

	mov	bx, ax
	shl	ax, 3		; AX = AX*8
	shl	bx, 1		; BX = BX*2 = AX*2
	add	ax, bx		; AX = AX*10

Ale niekoniecznie musimy dodawać wyniki. Zauważcie, że AX * 15 = (AX*8) + (AX*4) + (AX*2) + AX. Trzeba byłoby wykonać 3 SHL i 3 ADD. Ale my skorzystamy z innego rozwiązania: AX * 15 = (AX*16) - AX. Już tylko 1 SHL i 1 SUB. Stąd mamy:

	mov	bx, ax
	shl	ax, 4		; AX = AX*16
	sub	ax, bx

Dokładnie w ten sam sposób działa dzielenie (tylko oczywiście przy dzieleniu używamy SHR/SAR i niestety szybko możemy dzielić tylko przez potęgi dwójki). Pilnujcie tylko, aby używać tej właściwej instrukcji! Jak wiemy, 65534 = 0FFFEh = -2 . Teraz, oczywiście FFFE SHR 1 = 7FFFh = 32767 (=65534/2) a FFFE SAR 1 = FFFF = -1 (= -2/2). Widać różnicę, prawda? Pamiętajcie, że SAR patrzy na znak i go zachowuje.

Używanie SHL dla mnożenia i (zwłaszcza) SHR dla dzielenia może znacznie przyśpieszyć nasze programy, gdyż instrukcje MUL i DIV są dość wolne.




Instrukcje rotacji bitów


(przeskocz instrukcje rotacji)

Teraz przedstawię kolejną grupę instrukcji bitowych - instrukcje rotacji bitów. W tej grupie są tylko 4 instrukcje:

Schematyczne działanie tych instrukcji na bajtach widać na tych rysunkach:


(przeskocz rysunki)
	ROL:
			+-->------------->-------------->--+
			|				   |
		CF <-	7 <- 6 <- 5 <- 4 <- 3 <- 2 <- 1 <- 0

	RCL:
			+-->-----------> CF >----------->--+
			|				   |
			7 <- 6 <- 5 <- 4 <- 3 <- 2 <- 1 <- 0

	ROR:
			+--<-------------<--------------<--+
			|				   |
			7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0   -> CF

	RCR:
			+--<-----------< CF <-----------<--+
			|				   |
			7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0

W przypadku ROL i ROR, to ostatni wyjęty z jednej strony a włożony z drugiej strony bit zostaje też zapisany do flagi CF.
RCR i RCL działają tak, że bit, który ma zostać wstawiony, jest pobierany z CF, a wypchnięty bit ląduje w CF, a nie od razu na nowym miejscu.

No to kilka przykładów:

	0011 1100  ROL  2  =  1111 0000  (tak samo jak SHL)
	0011 1100  ROL  3  =  1110 0001

	1111 0000  ROR  1  =  0111 1000  (tak samo jak SHR)
	1010 0011  ROR  5  =  0001 1101

Zastosowanie tych instrukcji znalazłem jedno: generowanie chaosu w rejestrach...
Po co to mi? Na przykład generatory liczb pseudo-losowych z mojej biblioteki korzystają z tych właśnie instrukcji (a także z kilku poprzednich, na przykład XOR).




Instrukcje testowania i szukania bitów


(przeskocz instrukcje BT*)

Ostatnia już grupa rozkazów procesora to instrukcje testowania i szukania bitów. W tej grupie znajdują się:

Teraz po kolei omówię działanie każdej z nich.

Instrukcje BT* przyjmują 2 argumenty: miejsce, gdzie mają znaleźć dany bit i numer tego bitu, a zwracają wartość tego bitu we fladze CF. Ponadto, BTS ustawia znaleziony bit na 1, BTR czyści znaleziony bit a BTC odwraca znaleziony bit.
Kilka przykładów:

	bt	eax, 21		; umieść 21. bit EAX w CF
	jc	bit_jest_1
	...
	bts	cl, 2		; umieść 2. bit CL w CF i ustaw go
	jnc	bit_2_byl_zerem
	...
	btc	dh, 5		; umieść 5. bit DH w CF i odwróć go
	jc	bit_5_byl_jeden	

Instrukcje Bit Scan przyjmują 2 argumenty: pierwszy z nich to rejestr, w którym będzie umieszczona pozycja (numer od zera począwszy) pierwszego bitu, którego wartość jest równa 1 znalezionego w drugim argumencie instrukcji. Dodatkowo, BSF szuka tego pierwszego bitu zaczynając od bitu numer 0, a BSR od najstarszego (numer 7, 15 lub 31 w zależności od rozmiaru drugiego argumentu).

Teraz szybki przykładzik:

	mov	ax, 1010000b
	bsf	bx, ax
	bsr	cx, ax

Po wykonaniu powyższych instrukcji w BX powinno być 4, a w CX - 6 (bity liczymy od zera).



Jak pewnie zauważyliście, w kilku miejscach w tym tekście wyraźnie podkreśliłem słowa najwydajniejszy i im podobne. Chciałem w ten sposób uzmysłowić Wam, że operacje logiczne / binarne są bardzo ważną grupą instrukcji. Używanie ich, najlepiej wraz z instrukcją LEA służącą do szybkich rachunków, może kilkakrotnie (lub nawet kilkunastokrotnie) przyśpieszyć najważniejsze części Waszych programów (na przykład intensywne obliczeniowo pętle o milionach powtórzeń - patrz na przykład program L_mag.asm z 8. części tego kursu).

Dlatego zachęcam Was do dobrego opanowania instrukcji binarnych - po prostu umożliwia to pisanie programów o takiej wydajności, o której inni mogą tylko pomarzyć...

Po szczegółowy opis wszystkich instrukcji odsyłam, jak zwykle do : Intela i AMD

Ciekawe operacje na bitach (w języku C)



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. W jednej komendzie policz:
    1. iloraz z dzielenia EDI przez 4
    2. resztę z dzielenia EDI przez 4
    3. największą liczbę mniejszą lub równą EDI dzielącą sie przez 4
    Wskazówka: 4 = 2^2 oraz możliwe reszty z dzielenia przez 4 to 0, 1, 2 i 3 i zajmują one co najwyżej 2 bity.

  2. W jednej komendzie:
    1. ustaw bity 0, 11, 4 i 7 rejestru CX, nie ruszając pozostałych
    2. wyczyść bity 9, 2, 7 i 25 rejestru ESI, nie ruszając pozostałych
    3. przełącz (zmień wartość na odwrotną) bity 16, 4, 21, 1 i 10 rejestru EAX, nie ruszając pozostałych
    4. spraw, by wartość rejestru AL=18h zmieniła się na 80h, bez instrukcji MOV
    5. spraw, by wartość rejestru AL=18h zmieniła się na 81h, bez instrukcji MOV
    6. przełącz bit 23 rejestru EDX nie ruszając pozostałych, a jego starą wartość umieść we fladze CF