   #Start Prev Next Contents

   Jak pisac programy w jezyku asembler?

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:
;   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 liczbe do rejestru EAX
        jnc     liczba_ok       ; flaga CF=1 oznacza blad


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

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

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

        pisz64          ; wypisuje na ekranie 64-bitowa liczbe calkowita
                        ; z EDX:EAX


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

   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, czy 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 -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:
        ; wylaczyc dwie ponizsze linie w przypadku FASMa z nowym formatem
        ; biblioteki (32-bitowy COFF nie pozwala na manipulacje segmentami)
        mov     ax, cs
        mov     ds, ax  ; DS musi byc = CS, bo inaczej zapisywalibysmy
                        ; 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 spacje
        int     10h

        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      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        ; 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      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 sie teraz miejscom, gdzie mozna zwatpic w swoje
   umiejetnosci:
     * mov ax, (0eh << 8) | ":"
       Znaki "<<" odpowiadaja instrukcji SHL, a znak "|" odpowiada
       instrukcji OR. Mamy wiec: 0eh shl 8, czyli 0e00h. Robimy OR z
       dwukropkiem (3ah) i mamy AX=0e3ah. Uruchamiajac przerwanie 10h, na
       ekranie otrzymujemy dwukropek.
     * 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 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 -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 poczatkowa

        mov     ebp,1
        mov     ds,ax

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)
        mov     ah,9
        mov     edx,jest
        jne     nie                     ; nie

        int     21h                     ; tak - napis  "znaleziono "

        mov     eax,ebx
        call    pl                      ; wypisujemy liczbe

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

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

        add     ebx,ebp                 ; nie, zwiekszamy liczbe badana o
                                        ; jeden i od poczatku
        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 ostatnia sprawdzona liczbe
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 cyfre w AL
        mov     ah,0eh
        push    ebp
        or      al,30h
        int     10h
        pop     ebp
        ret
        ud2

align 16
pl:                             ; wypisuje 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

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

   A oto analiza:
     * Petla glowna:
       Dziel EBX przez kolejne przypuszczalne dzielniki. Jesli trafisz na
       prawdziwy dzielnik (reszta=EDX=0), to dodaj go do sumy, ktora jest
       w 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).
