Jak pisać programy w języku asembler?

Część 8 - Zaawansowane programy, czyli zobaczmy, co ten język naprawdę potrafi

No cóż, nie jesteśmy już amatorami i przyszła pora, aby przyjrzeć się temu, w czym asembler wprost błyszczy: algorytmy intensywne obliczeniowo. Specjalnie na potrzeby tego kursu napisałem następujący programik. Zaprezentuję w nim kilka sztuczek i pokażę, do jakich rozmiarów (tutaj: 2 instrukcje) można ścisnąć główną pętlę programu.
Oto ten programik:


(przeskocz program obliczający sumę liczb)
; Program liczący sumę liczb od 1 do liczby wpisanej z klawiatury
;
; Autor: Bogdan D.
;
; kompilacja NASM:
;   nasm -O999 -o ciag_ar.obj -f obj ciag_ar.asm
;   alink ciag_ar.obj  bibl\lib\bibldos.lib -c- -oEXE -m-
; kompilacja FASM (stary format biblioteki - OMF):
;   fasm ciag_ar.asm ciag_ar.obj
;   alink ciag_ar.obj  bibl\lib\bibldos.lib -c- -entry _start -oEXE -m-
; kompilacja FASM (nowy format biblioteki - COFF):
;   fasm ciag_ar.asm ciag_ar.obj
;   ld -s -o ciag_ar.exe ciag_ar.obj bibl\lib\bibldos.a



%include "bibl\incl\dosbios\nasm\std_bibl.inc"
%include "bibl\incl\dosbios\nasm\do_nasma.inc"

.stack 400h

section .text

; FASM (stary format biblioteki - OMF):
; format coff
; include "bibl\incl\dosbios\fasm\std_bibl.inc"
; use16
; public start
; public _start

; FASM (nowy format biblioteki - COFF):
; format coff
; include "bibl\incl\dosbios\fasm32\std_bibl.inc"
; public start
; public _start

start:
_start:
..start:
	pisz
	db	"Program liczy sume liczb od 1 do podanej liczby.",cr,lf
	db	"Podaj liczbe calkowita: ",0

	we32e		; pobieramy z klawiatury liczbę do rejestru EAX
	jnc	liczba_ok	; flaga CF=1 oznacza błąd


blad:
	pisz
	db	cr, lf, "Zla liczba!",0

	wyjscie 1			; mov ax, 4c01h / int 21h

liczba_ok:
	test	eax, eax		; jeśli EAX=0, to też błąd
	jz	blad

	mov	ebx, eax		; zachowaj liczbę. EBX=n
	xor	edx, edx		; EDX = nasza suma
	mov	ecx, 1

petla:
	add	edx, eax		; dodaj liczbę do sumy
	sub	eax, ecx		; odejmij 1 od liczby
	jnz	petla			; liczba różna od zera?
					; to jeszcze raz dodajemy

	pisz
	db	cr, lf, "Wynik z sumowania 1+2+3+...+n= ",0

	mov	eax, edx		; EAX = wynik
	pisz32e				; wypisz EAX

	mov	eax, ebx		; przywrócenie liczby
	add	eax, 1			; EAX = n+1
	mul	ebx			; EDX:EAX = EAX*EBX = n*(n+1)

	shr	edx, 1
	rcr	eax, 1			; EDX:EAX = EDX:EAX/2

	pisz
	db	cr, lf, "Wynik ze wzoru: n(n+1)/2= ",0

	pisz64		; wypisuje na ekranie 64-bitową liczbę całkowitą
			; z EDX:EAX


	wyjscie 0			; mov ax, 4c00h / int 21h

Jak widać, nie jest on ogromny, a jednak spełnia swoje zadanie. Teraz przeanalizujemy ten krótki programik:


Poniższy programik też napisałem dla tego kursu. Ma on pokazać złożone sposoby adresowania oraz instrukcje warunkowego przesunięcia (CMOV..):


(przeskocz program z macierzą)
; Program wczytuje od użytkownika macierz 3x3, po czym znajduje
; element największy i najmniejszy
;
; Autor: Bogdan D.
;
; kompilacja:
;   nasm -O999 -o macierze.obj -f obj macierze.asm
;   alink macierze.obj  bibl\lib\bibldos.lib -c- -oEXE -m-
; kompilacja FASM (stary format biblioteki - OMF):
;   fasm macierze.asm macierze.obj
;   alink macierze.obj  bibl\lib\bibldos.lib -c- -entry _start -oEXE -m-
; kompilacja FASM (nowy format biblioteki - COFF):
;   fasm macierze.asm macierze.obj
;   ld -s -o macierze.exe macierze.obj bibl\lib\bibldos.a

%include "bibl\incl\dosbios\nasm\std_bibl.inc"
%include "bibl\incl\dosbios\nasm\do_nasma.inc"

%define rozmiar 3

.stack 400h

section .text

; FASM (stary format biblioteki - OMF):
; format coff
; include "bibl\incl\dosbios\fasm\std_bibl.inc"
; use16
; rozmiar = 3
; public start
; public _start

; FASM (nowy format biblioteki - COFF):
; format coff
; include "bibl\incl\dosbios\fasm32\std_bibl.inc"
; rozmiar = 3
; public start
; public _start

start:
_start:
..start:
	; wyłączyć dwie poniższe linie w przypadku FASMa z nowym formatem
	; biblioteki (32-bitowy COFF nie pozwala na manipulację segmentami)
	mov	ax, cs
	mov	ds, ax	; DS musi być = CS, bo inaczej zapisywalibyśmy
			; nie tam, gdzie trzeba, a macierz jest w
			; segmencie kodu.

	pisz
	db	"Prosze podac 9 elementow macierzy,"
	db	cr,lf," a ja znajde najwiekszy i najmniejszy.",0

	xor	edx, edx			; ECX = 0
	mov	ebx, macierz

petla_wczyt:
	pisz
	db	cr, lf, "Prosze podac element nr ", 0
	mov	eax, edx
	add	eax, 1
	pisz32e				; wypisz numer elementu

	mov	ax, (0eh << 8) | ":"		; wypisz dwukropek
; FASM:
;	mov	ax, (0eh shl 8) or ":"

	int	10h
	mov	al, spc			; wypisz spację
	int	10h

	we32e				; wczytaj element
	jc	blad
	mov	[ebx+4*edx], eax	; umieść w macierzy

	add	edx, 1			; zwiększ licznik elementów
					; i równocześnie pozycję w macierzy

	cmp	edx, rozmiar*rozmiar
	jb	petla_wczyt

	jmp	wczyt_gotowe

blad:
	pisz
	db	cr, lf, "Zla liczba!",0

	wyjscie 1


wczyt_gotowe:
					; EBP = max, EDI = min

	mov	ebp, [ebx]
	mov	edi, [ebx]		; pierwszy element
	mov	edx, 1
	mov	eax, 1
	mov	esi, rozmiar*rozmiar

znajdz_max_min:
	mov	ecx, [ ebx + 4*edx ]
	cmp	ebp, ecx	; EBP < macierz[edx] ?
	cmovb	ebp, ecx	; jeśli tak, to EBP = macierz[edx]

	cmp	edi, ecx	; EDI > macierz[edx] ?
	cmova	edi, ecx	; jeśli tak, to EDI = macierz[edx]

	add	edx, eax
	cmp	edx, esi
	jb	znajdz_max_min

	pisz
	db	cr, lf, "Najwiekszy element: ",0
	mov	eax, ebp
	pisz32e

	pisz
	db	cr, lf, "Najmniejszy element: ",0
	mov	eax, edi
	pisz32e


	wyjscie 0



macierz:	times	rozmiar*rozmiar		dd 0

Przypatrzmy się teraz miejscom, gdzie można zwątpić w swoje umiejętności:

Powyższy program trudno nazwać intensywnym obliczeniowo, bo ograniczyłem rozmiar macierzy do 3x3. Ale to był tylko przykład. Prawdziwe programy mogą operować na macierzach zawierających miliony elementów. Podobny program napisany w HLLu jak C czy Pascal po prostu zaliczyłby się na śmierć.


Teraz pokażę program, który ewoluował od nieoptymalnej formy (zawierającej na przykład więcej skoków warunkowych w głównej pętli oraz inne nieoptymalne instrukcje) do czegoś takiego:


(przeskocz program znajdujący liczby magiczne)
; L_mag.asm
;
; Program wyszukuje liczby, które są sumą swoich dzielników
;
; Autor: Bogdan D.
; kontakt: bogdandr (at) op (dot) pl
;
; nasm -O999 -o l_mag.com -f bin l_mag.asm
; fasm l_mag.asm l_mag.com


org 100h

start:
	mov	ax,cs
	mov	ebx,1			; liczba początkowa

	mov	ebp,1
	mov	ds,ax

align 16
start2:
	mov	esi,ebx			; ESI = liczba

	mov	ecx,ebp			; EBP = 1
	shr	esi,1			; zachowanie połowy liczby

	xor	edi,edi			; suma dzielników=0

align 16
petla:
	xor	edx,edx			; dla dzielenia
	nop
	cmp	ecx,esi			; czy ECX (dzielnik)>liczba/2?
	mov	eax,ebx			; przywrócenie liczby do dzielenia
	nop
	ja	dalej2			; Jeśli ECX > ESI, to koniec
					; dzielenia tej liczby

	nop
	div	ecx			; EAX = EDX:EAX / ECX, EDX=reszta

	nop
	nop
	add	ecx,ebp			; zwiększamy dzielnik o 1
	nop

	test	edx,edx			; czy ECX jest dzielnikiem?
					; (czy EDX=reszta=0?)
	nop
	nop
	jnz	petla			; nie? Dzielimy przez następną liczbę

					; tak?
	lea	edi,[edi+ecx-1]		; dodajemy dzielnik do sumy, nie
					; sprawdzamy na przepełnienie.
					; ECX-1 bo dodaliśmy EBP=1 do
					; ECX po DIV.

	jmp	short petla		; dzielimy przez kolejną liczbę
	ud2


align 16
dalej2:
	cmp	ebx,edi			; czy to ta liczba?
					; (czy liczba=suma dzielników)
	mov	ah,9
	mov	edx,jest
	jne	nie			; nie

	int	21h			; tak - napis  "znaleziono "

	mov	eax,ebx
	call	pl			; wypisujemy liczbę

align 16
nie:
	mov	ah,1
	int	16h
	nop
	jnz	klaw

	cmp	ebx,0ffffffffh		; czy już koniec zakresu?
	nop
	je	koniec			; tak

	add	ebx,ebp			; nie, zwiększamy liczbę badaną o
					; jeden i od początku
	nop
	jmp	short start2
	ud2


align 16
klaw:
	xor	ah,ah
	int	16h
koniec:
	mov	ah,9
	mov	edx,meta
	nop
	int	21h			; napis  "koniec "

	mov	eax,ebx
	call	pl		; wypisujemy ostatnią sprawdzoną liczbę
spr:					; czekamy na klawisz
	mov	ah,1
	nop
	int	16h
	jz	spr

	xor	ah,ah
	int	16h

	mov	ax,4c00h
	int	21h
	ud2

align 16
pc:					; wypisuje cyfrę w AL
	mov	ah,0eh
	push	ebp
	or	al,30h
	int	10h
	pop	ebp
	ret
	ud2

align 16
pl:				; wypisuje liczbę dziesięciocyfrową w EAX
	mov	ecx,1000000000
	xor	edx,edx
	div	ecx
	call	pc

	mov	eax,edx
	mov	ecx,100000000
	xor	edx,edx
	div	ecx
	call	pc

	mov	eax,edx
	mov	ecx,10000000
	xor	edx,edx
	div	ecx
	call	pc

	mov	eax,edx
	mov	ecx,1000000
	xor	edx,edx
	div	ecx
	call	pc

	mov	eax,edx
	mov	ecx,100000
	xor	edx,edx
	div	ecx
	call	pc

	mov	eax,edx
	mov	ecx,10000
	xor	edx,edx
	div	ecx
	call	pc

	mov	eax,edx
	xor	edx,edx
	mov	ecx,1000
	div	ecx
	call	pc

	mov	eax,edx
	mov	cl,100
	div	cl
	mov	ch,ah
	call	pc

	mov	al,ch
	xor	ah,ah
	mov	cl,10
	div	cl
	mov	ch,ah
	call	pc

	mov	al,ch
	call	pc
	ret
	ud2

align 4
jest	db	10,13,"Znaleziono: $"
meta	db	10,13,"Koniec. ostatnia liczba: $"

A oto analiza:


O tych wszystkich sztuczkach, które tu zastosowałem, można przeczytać w podręcznikach dotyczących optymalizacji programów, wydanych zarówno przez Intel, jak i AMD (u AMD są też wymienione sztuczki, których można użyć do optymalizacji programów napisanych w języku C).
Podaję adresy (te same co zwykle): AMD, Intel.

Życzę ciekawej lektury i miłej zabawy.


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 obliczający Największy Wspólny Dzielnik i Najmniejszą Wspólną Wielokrotność dwóch liczb wiedząc, że:
    NWD(a,b) = NWD(b, reszta z dzielenia a przez b) i NWD(n,0)=n (algorytm Euklidesa)
    NWW(a,b) = a*b / NWD(a,b)

  2. Napisz program rozkładający daną liczbę na czynniki pierwsze (liczba może być umieszczona w kodzie programu).