   #Start Prev Next Contents

   Jak pisac programy w jezyku asembler pod Linuksem?

Czesc 8 - Zaawansowane programy, czyli zobaczmy, co ten jezyk naprawde
potrafi

   No coz, nie jestesmy juz amatorami i przyszla pora, aby przyjrzec sie
   temu, w czym asembler wprost blyszczy: algorytmy intensywne
   obliczeniowo. Specjalnie na potrzeby tego kursu napisalem nastepujacy
   programik. Zaprezentuje w nim kilka sztuczek i pokaze, do jakich
   rozmiarow (tutaj: 2 instrukcje) mozna scisnac glowna petle programu.
   Oto ten programik:
   (przeskocz program obliczajacy sume liczb)
; Program liczacy sume 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 liczbe do rejestru EAX
        jnc     liczba_ok       ; flaga CF=1 oznacza blad


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

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

liczba_ok:
        test    eax, eax        ; jesli EAX=0, to tez blad
        jz      blad

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

petla:
        add     edx, eax        ; dodaj liczbe do sumy
        sub     eax, ecx        ; odejmij 1 od liczby
        jnz     petla           ; liczba rozna 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        ; przywrocenie 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-bitowa liczbe calkowita
                        ; z EDX:EAX


        nwln
        wyjscie 0

   Jak widac, nie jest on ogromny, a jednak spelnia swoje zadanie. Teraz
   przeanalizujemy ten krotki programik:
     * Komentarz naglowkowy.
       Mowi, co program robi oraz kto jest jego autorem. Moze zawierac
       informacje o wersji programu, o niestandardowym sposobie
       kompilacji/uruchomienia i wiele innych szczegolow.
     * pisz, we32e, pisz32e oraz pisz64.
       To sa makra uruchamiajace procedury z mojej biblioteki. Uzywam
       ich, bo sa sprawdzone i nie musze ciagle umieszczac kodu tych
       procedur w programie.
     * Makro "wyjscie" zawiera w sobie kod wyjscia z programu, napisany
       obok.
     * test rej, rej / jz ... / jnz ...
       Instrukcja TEST jest szybsza niz cmp rej, 0 i nie zmienia
       zawartosci rejestru, w przeciwienstwie do OR. Jest to najszybszy
       sposob na sprawdzenie, wartosc rejestru wynosi 0.
     * Petla glowna.
       Jak widac, najpierw do sumy dodajemy n, potem n-1, potem n-2, i na
       koncu 1. Umozliwilo to znaczne skrocenie kodu petli, a wiec
       zwiekszenie jej szybkosci. Napisanie sub eax, ecx zamiast sub eax,
       1 skraca rozmiar instrukcji i powoduje jej przyspieszenie, gdyz
       dzieki temu w samej petli procesor operuje juz tylko na
       rejestrach.
     * shr edx, 1 / rcr eax, 1
       Wynik musimy podzielic przez 2, zgodnie ze wzorem. Niestety, nie
       ma instrukcji shr dla 64 bitow. Wiec trzeba ten brak jakos obejsc.
       Najpierw, shr edx, 1 dzieli EDX przez 2, a bit 0 laduje we fladze
       CF. Teraz, rcr eax, 1 (rotate THROUGH CARRY) wartosc CF (czyli
       stary bit 0 EDX) umiesci w bicie 31 EAX. I o to chodzilo!
     _________________________________________________________________

   Ponizszy programik tez napisalem dla tego kursu. Ma on pokazac zlozone
   sposoby adresowania oraz instrukcje warunkowego przesuniecia (CMOV..):
   (przeskocz program z macierza)
; Program wczytuje od uzytkownika macierz 3x3, po czym znajduje
; element najwiekszy 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 spacje

        pop     edx
        pop     ebx

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

        add     edx, 1                  ; zwieksz licznik elementow
                                        ; i rownoczesnie pozycje 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                ; jesli tak, to EBP = macierz[edx]

        cmp     edi, ecx                ; EDI > macierz[edx] ?
        cmova   edi, ecx                ; jesli 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 sie teraz miejscom, gdzie mozna zwatpic w swoje
   umiejetnosci:
     * mov [ebx+4*edx], eax
       EBX = adres macierzy. EDX = 0, 1, 2, ..., rozmiar*rozmiar=9.
       Elementy macierzy maja rozmiar po 4 bajty kazdy, stad EDX mnozymy
       przez 4. Innymi slowy, pierwszy EAX idzie do [ebx+4*0]=[ebx],
       drugi do [ebx+4] (na 2 miejsce macierzy), trzeci do [ebx+8] itd.
     * Fragment kodu:
        mov     ecx, [ ebx + 4*edx ]
        cmp     ebp, ecx        ; EBP < macierz[edx] ?
        cmovb   ebp, ecx        ; jesli tak, to EBP = macierz[edx]

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

        add     edx, eax
        cmp     edx, esi
        jb      znajdz_max_min
       Najpierw, do ECX idzie aktualny element. Potem porownujemy EBX z
       tym elementem i, gdy EBP < ECX, kopiujemy ECX do EBP. Do tego
       wlasnie sluzy instrukcja CMOVB (Conditional MOVe if Below).
       Instrukcje z rodziny (F)CMOV umozliwiaja pozbywanie sie skokow
       warunkowych, ktore obnizaja wydajnosc kodu.
       Podobnie, porownujemy EDI=min z ECX.
       Potem, zwiekszamy EDX o 1 i sprawdzamy, czy nie przeszlismy przez
       kazdy element macierzy.

   Powyzszy program trudno nazwac "intensywnym obliczeniowo", bo
   ograniczylem rozmiar macierzy do 3x3. Ale to byl tylko przyklad.
   Prawdziwe programy moga operowac na macierzach/tablicach zawierajacych
   miliony elementow. Podobny program napisany w HLLu jak C czy Pascal po
   prostu zaliczylby sie na smierc.
     _________________________________________________________________

   Teraz pokaze program, ktory ewoluowal od nieoptymalnej formy
   (zawierajacej na przyklad wiecej skokow warunkowych w glownej petli
   oraz inne nieoptymalne instrukcje) do czegos takiego:
   (przeskocz program znajdujacy liczby magiczne)
; L_mag.asm
;
; Program wyszukuje liczby, ktore sa suma swoich dzielnikow
;
; 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 przejscia do nowej linii (Line Feed)
section .text
global _start


_start:
        mov     ebx,1           ; liczba poczatkowa

        mov     ebp,1

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

        mov     ecx,ebp         ; EBP = 1
        shr     esi,1           ; zachowanie polowy liczby

        xor     edi,edi         ; suma dzielnikow=0

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

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

        nop
        nop
        add     ecx,ebp         ; zwiekszamy dzielnik o 1
        nop

        test    edx,edx         ; czy ECX jest dzielnikiem?
                                ; (czy EDX=reszta=0?)
        nop
        nop
        jnz     petla           ; nie? - dzielimy przez nastepna liczbe

                                ; tak? -
        lea     edi,[edi+ecx-1] ; dodajemy dzielnik do sumy,
                                ; nie sprawdzamy na przepelnienie.
                                ; ECX-1 bo dodalismy EBP=1 do ECX po DIV.

        jmp     short petla     ; dzielimy przez kolejna liczbe
        ud2

align 16
dalej2:
        cmp     ebx,edi         ; czy to ta liczba?
                                ; (czy liczba=suma dzielnikow?)
        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 liczbe

align 16
nie:

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

        add     ebx,ebp         ; nie, zwiekszamy liczbe badana o 1
        nop
        jmp     start2          ; i idziemy od poczatku
        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 ostatnia sprawdzona liczbe

        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 cyfre 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:                     ; wyswietla liczbe dziesieciocyfrowa 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:
     * Petla glowna:
       Dziel EBX przez kolejne przypuszczalne dzielniki. Jesli trafisz na
       prawdziwy dzielnik (reszta=EDX=0), to dodaj go do sumy=EDI.
       Unikalem ustawiania obok siebie takich instrukcji, ktore zaleza od
       siebie, jak na przyklad CMP / JA czy DIV / ADD
     * Nie za duzo tych NOPow?
       Nie. Zamiast czekac na wynik poprzednich instrukcji, procesor
       zajmuje sie... robieniem niczego. Ale jednak sie zajmuje.
       Wspolczesne procesory potrafia wykonywac wiele niezaleznych
       instrukcji praktycznie rownolegle. Wiec w czasie, jak procesor
       czeka na wykonanie poprzednich instrukcji, moze rownolegle
       wykonywac NOPy. Zwieksza to przepustowosc, utrzymuje uklady
       dekodujace w ciaglej pracy, kolejka instrukcji oczekujacych na
       wykonanie nie jest pusta.
     * Co robi instrukcja lea edi,[edi+ecx-1] ?
       LEA - Load Effective Address. Do rejestru EDI zaladuj ADRES
       (elementu, ktorego) ADRES wynosi EDI+ECX-1. Czyli, w paskalowej
       skladni: EDI := EDI+ECX-1. Do EDI dodajemy znaleziony dzielnik.
       Musimy odjac 1, bo wczesniej (po dzieleniu) zwiekszylismy ECX o 1.
     * Co robi instrukcja UD2 i czemu jest umieszczona po instrukcjach
       JMP ?
       Ta instrukcja (UnDefined opcode 2) wywoluje wyjatek wykonania
       nieprawidlowej instrukcji przez procesor. Umiescilem ja w takich
       miejscach, zeby nigdy nie byla wykonana.
       Po co ona w ogole jest w tym programie w takich miejscach?
       Ma ona interesujaca wlasciwosc: powstrzymuje jednostki dekodujace
       instrukcje od dalszej pracy. Po co dekodowac instrukcje, ktore i
       tak nie beda wykonane (bo byly po skoku bezwarunkowym)? Strata
       czasu.
     * Po co ciagle align 16 ?
       Te dyrektywy sa tylko przed etykietami, ktore sa celem skoku.
       Ustawianie kodu od adresu, ktory dzieli sie przez 16 moze ulatwic
       procesorowi umieszczenie go w calej jednej linii pamieci
       podrecznej (cache). Mniej instrukcji musi byc pobieranych z
       pamieci (bo te, ktore sa najczesciej wykonywane juz sa w cache),
       wiec szybkosc dekodowania wzrasta. Ukladania kodu i danych
       zwieksza ogolna wydajnosc programu

   O tych wszystkich sztuczkach, ktore tu zastosowalem, mozna przeczytac
   w podrecznikach dotyczacych optymalizacji programow, wydanych zarowno
   przez Intel, jak i AMD (u AMD sa tez wymienione sztuczki, ktorych
   mozna uzyc do optymalizacji programow napisanych w jezyku C).
   Podaje adresy (te same co zwykle): AMD, Intel.

   Zycze ciekawej lektury i milej zabawy.

   Poprzednia czesc kursu (klawisz dostepu 3)
   Kolejna czesc kursu (klawisz dostepu 4)
   Spis tresci off-line (klawisz dostepu 1)
   Spis tresci on-line (klawisz dostepu 2)
   Ulatwienia dla niepelnosprawnych (klawisz dostepu 0)
     _________________________________________________________________

Cwiczenia

    1. Napisz program obliczajacy Najwiekszy Wspolny Dzielnik i
       Najmniejsza Wspolna Wielokrotnosc dwoch liczb wiedzac, ze:
       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 rozkladajacy dana liczbe na czynniki pierwsze
       (liczba moze byc umieszczona w kodzie programu).
