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

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 -O999 -f elf ciag_ar.asm
; ld -s -o ciag_ar ciag_ar.o bibl/lib/libasmio.a
;
; fasm ciag_ar.asm ciag_ar.o
; ld -s -o ciag_ar ciag_ar.o bibl/lib/libasmio.a

; FASM:
; format ELF
; include "bibl/incl/linuxbsd/fasm/std_bibl.inc"
; section ".text" executable
; public _start

; NASM
%include "bibl/incl/linuxbsd/nasm/std_bibl.inc"
section .text
global _start



_start:
	pisz
	db	"Program liczy sume liczb od 1 do podanej liczby.",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	lf, "Zla liczba!",lf,0

	wyjscie 1		; mov ebx, 1 / mov eax, 1 / int 80h

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	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	lf, "Wynik ze wzoru: n(n+1)/2= ",0

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


	nwln
	wyjscie 0

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 -f elf macierze.asm
; ld -s -o macierze macierze.o -Lbibl/lib -lasmio
;
; fasm macierze.asm macierze.o
; ld -s -o macierze macierze.o -Lbibl/lib -lasmio

; FASM:
; format ELF
; include "bibl/incl/linuxbsd/fasm/std_bibl.inc"
; section ".text" executable
; public _start
; rozmiar = 3

; NASM
%include "bibl/incl/linuxbsd/nasm/std_bibl.inc"
%define rozmiar 3
section .text
global _start


_start:

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

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

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

	push	ebx
	push	edx

	mov	eax, 4
	mov	ebx, 1
	mov	ecx, dwukspc
	mov	edx, 2
	int	80h			; wypisz dwukropek i spację

	pop	edx
	pop	ebx

	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	lf, "Zla liczba!",lf,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	lf, "Najwiekszy element: ",0
	mov	eax, ebp
	pisz32e

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

	nwln
	wyjscie 0

; FASM: section ".data" writeable
section .data

macierz		times	rozmiar*rozmiar		dd 0
dwukspc		db ": "

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/tablicach 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 -f elf l_mag.asm
; ld -s -o l_mag l_mag.o
;
; fasm l_mag.asm l_mag

; FASM:
; format ELF executable
; entry _start
; segment readable executable
; lf = 10

; NASM
%define lf 10		; znak przejścia do nowej linii (Line Feed)
section .text
global _start


_start:
	mov	ebx,1		; liczba początkowa

	mov	ebp,1

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?)
	jne	nie		; nie

	push	ebx

	mov	eax, 4
	mov	ebx, 1
	mov	ecx, jest
	mov	edx, jest_dlugosc
	int	80h		; tak - napis "znaleziono"

	pop	ebx

	mov	eax,ebx
	call	pl		; wypisujemy liczbę

align 16
nie:

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

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

align 16
koniec:

	push	ebx

	mov	eax, 4
	mov	ebx, 1
	mov	ecx, meta
	mov	edx, meta_dlugosc
	int	80h

	pop	eax
	call	pl		; wypisujemy ostatnią sprawdzoną liczbę

        mov     eax, 4
        mov     ebx, 1
        mov     ecx, nwln
        mov     edx, 1
        int     80h		; wypisz znak nowej linii

	mov	eax, 1
	xor	ebx, ebx
	int	80h

	ud2

align 16
pc:				; wypisuje cyfrę w AL
	push	eax
	or	al, "0"
	mov	[cyfra], al

	push	ebx
	push	ecx
	push	edx

	mov	eax, 4
	mov	ebx, 1
	mov	ecx, cyfra
	mov	edx, 1
	int	80h

	pop	edx
	pop	ecx
	pop	ebx
	pop	eax

	ret
	ud2

align 16
pl:			; wyświetla 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


; FASM:  segment readable writeable
section .data align=4

jest	db	lf,"Znaleziono: "
jest_dlugosc	equ	$-jest	; FASM: "=" zamiast "equ"

meta	db	lf,"Koniec. ostatnia liczba: "
meta_dlugosc	equ	$-meta	; FASM: "=" zamiast "equ"

cyfra	db	0
nwln	db	lf
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).