Stos procesora
Stos jest strukturą danych, w której dane dokładane są na wierzch stosu i z wierzchołka stosu są pobierane. W procesorach z rodziny x86 stos znajduje się w górnej części pamięci operacyjnej, a dane umieszczane są na nim w kierunku odwrotnym – tj. od większego adresu do mniejszego.
Aby odłożyć zawartość rejestru na stos, korzystamy z rozkazu push REJESTR
. Aby ściągnąć zawartość ostatniego elementu ze stosu do rejestru, używamy rozkazu pop REJESTR
.
Rejestr przechowujący wskaźnik na ostatni element stosu to RSP. Zwiększenie zawartości tego rejestru o 8 powoduje “usunięcie” ze stosu ostatniej wartości. Dokładniej mówiąc wartość ta nie jest usuwana, ale podczas następnego odłożenia wartości na stos zostanie ona nadpisana.
Możliwy jest też dostęp do dowolnego elementu stosu. Korzystamy wtedy ze wskaźnika RSP:
mov (%rsp), %rax
– pobierze zawartość pamięci spod adresu określonego w RSP (ostatni element ze stosu) do rejestru RAX,
mov 16(%rsp), %rbx
– pobierze zawartość drugiego elementu (2*8) stosu (licząc od końca) do rejestru RBX.
Na stos odłożyć możemy także rejestr flagowy. Jest to przydatne jeśli korzystamy z wielu rozkazów modyfikujących tą samą flagę pod rząd. Przykładowo dodawanie z przeniesieniem modyfikuje flagę carry. Jeśli realizujemy je w pętli i korzystamy z rozkazu cmp
do ustalenia czy należy powrócić na początek pętli czy też z niej wyjść, to rozkaz ten również zmodyfikuje zawartość rejestru flagowego.
Do odłożenia na stos rejestru flagowego wykorzystujemy rozkaz pushf
, a do ściągnięcia zawartości tego rejestru ze stosu – popf
.
Funkcje w języku Asembler i C
Funkcje w języku Asembler w najprostszej postaci wykonuje się wykorzystując rozkazy call
oraz ret
. Rozkaz call
odkłada na stos obecny adres (tj. ten z którego nastąpiło wywołanie funkcji), a następnie wykonuje skok do nowego adresu/etykiety. Rozkaz ret
powraca pod ten adres (do następnej instrukcji po wywołaniu funkcji) i ściąga go ze stosu.
Rozkaz call
nie odkłada automatycznie na stos zawartości rejestrów. Możemy wykorzystać je do przekazania parametrów i zwrócenia wyniku.
Funkcje w języku C przyjmują swoje parametry poprzez stos. Jest to również popularny sposób przekazywania parametrów w programach pisanych w Asemblerze.
Poniższy kod prezentuje sposób przekazywania parametrów przez stos:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
# # Wywołanie funkcji "dodaj" # push %r8 # Umieszczenie drugiego parametru na stosie push %r9 # Umieszczenie pierwszego parametru na stosie call dodaj # Wywołanie funkcji add $16, %rsp # Usunięcie parametrów ze stosu # Wynik trafia do RAX # # Kod funkcji # dodaj: # # Pobranie parametrów # push %rbp # Umieszczenie na stosie poprzedniej wartości # rejestru bazowego mov %rsp, %rbp # Pobranie zawartości rejestru RSP (zawierającego # wskaźnik na ostatni element umieszczony # na stosie) do rejestru bazowego sub $8, %rsp # "Zwiększenie" wskaźnika stosu o jedną komórkę mov 16(%rbp), %rax # Pobranie pierwszego argumentu do rejestru RAX mov 24(%rbp), %rbx # Pobranie drugiego argumentu do rejestru RBX # # Właściwy kod funkcji # add %rbx, %rax # # Zwrot wartości i powrót do miejsca wywołania # # Wynik działania funkcji już znajduje się w rejestrze RAX ret # Powrót do miejsca wywołania funkcji |
Sito Eratostenesa
Pierwszym programem z zadania domowego była implementacja algorytmu Sita Eratostenesa. Jest to algorytm wyznaczania liczb pierwszych z zadanego zakresu. Opiera się on na tablicy wartości prawda/fałsz (sito) określających czy przyporządkowana im liczba jest liczbą pierwszą czy też nie. W kolejnych iteracjach głównej pętli, dla każdej liczby której wartość w sicie nie jest równa fałszowi, w zagnieżdżonej pętli, kolejne jej wielokrotności oznaczane są jako fałsz (liczby nie pierwsze). Po zakończeniu działania algorytmu, na podstawie wygenerowanej tablicy sita uzupełniany jest bufor liczb pierwszych. Następnie bufor ten jest wyświetlany.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 |
.data STDOUT = 1 SYSWRITE = 1 SYSEXIT = 60 EXIT_SUCCESS = 0 ILOSC_LICZB = 9999 # Ilość liczb jakie sprawdzić ma algorytm. PODSTAWA_WYJSCIA = 10 # Stałe wykorzystywane przy wyświetlaniu liczb. POCZATEK_LICZB = 0x30 # -||- NOWA_LINIA = 0xA # -||- .bss .comm sito_bufor, 9999 # Bufor wartości 0/1 decydujących czy dana # liczba (indeks+2) jest liczbą pierwszą # czy nie. Jego rozmiar to ilość liczb # do wygenerowanie-2. .comm liczby, 79992 # Bufor przechowujący liczby pierwsze # wygenerowane przez algorytm. Każda liczba # zapisywana jest na 64 bitach, czyli 8 bajtach, # więc jego rozmiar to 8*rozmiar poprzedniego # bufora. .comm textinv, 512 # Bufory wykorzystywane do zamiany liczb .comm textout, 512 # na postać ciągów kodów ASCII kolejnych cyfr. .text .globl _start _start: # # Wywołanie funkcji realizującej algorytm sita Eratostenesa. # Jej kod został umieszczony na końcu programu. # call sito_eratostenesa # # WYŚWIETLENIE WYNIKU DZIAŁANIA ALGORYTMU # # Zamiana wartości liczb wygenerowanych i umieszczonych przez # algorytm w buforze "liczby" do postaci ciągów kodów ASCII # i ich wyświetlanie. # mov $0, %r8 # Licznik do pętli - zostanie ona wykonana dla każdej # komórki bufora "liczby". Liczby o wartości zero nie # zostaną wyświetlone. petla1: mov liczby(, %r8, 8), %rax # Skopiowanie liczby do rejestru RAX cmp $0, %rax je pomin # Jeśli liczba jest równa 0, pominięcie konwersji # i wyświetlania # # DEKODOWANIE WARTOŚCI LICZBY W PĘTLI # mov $PODSTAWA_WYJSCIA, %rbx mov $0, %rcx petla2: mov $0, %rdx div %rbx # Dzielenie bez znaku liczby z rejestru RAX przez RBX # i zapis wyniku do RAX oraz reszty z dzielenie do RDX. # Reszta z dzielenia to przy każdej iteracji pętli kolejna # pozycja wyniku. Po dodaniu kodu znaku pierwszej liczby, # są to kody znaków ASCII liczb na kolejnych pozycjach. add $POCZATEK_LICZB, %rdx # Zapis znaków do bufora w odwrotnej kolejności mov %dl, textinv(, %rcx, 1) # Zwiększenie licznika i w kolejnych iteracjach powrót # na początek pętli, aż do uzyskania zerowego wyniku dzielenia inc %rcx cmp $0, %rax jne petla2 jmp przed_petla3 # # ODWRÓCENIE KOLEJNOŚCI CYFR # # Po wykonaniu ostatniego kroku, cyfry zapisane są w buforze # w odwrotnej kolejności, w tej pętli są przepisywane z końca # na początek do nowego bufora textout. przed_petla3: mov $0, %rdi mov %rcx, %rsi dec %rsi petla3: mov textinv(, %rsi, 1), %rax mov %rax, textout(, %rdi, 1) inc %rdi dec %rsi cmp %rcx, %rdi jle petla3 # # WYŚWIETLENIE LICZBY # # Dopisanie na końcu bufora wyjściowego znaku nowej linii movb $NOWA_LINIA, textout(, %rcx, 1) inc %rcx # Wyświetlenie tekstu z bufora textout mov $SYSWRITE, %rax mov $STDOUT, %rdi mov $textout, %rsi mov %rcx, %rdx syscall pomin: # Powrót na początek pętli aż do wykonania instrukcji dla # wszystkich liczb. inc %r8 cmp $ILOSC_LICZB, %r8 jl petla1 # # ZAKOŃCZENIE PROGRAMU # mov $SYSEXIT, %rax mov $EXIT_SUCCESS, %rdi syscall # # FUNKCJA REALIZUJĄCA ALGORYTM SITA ERATOSTENESA # sito_eratostenesa: # Czyszczenie bufora liczb i sita w pętli mov $ILOSC_LICZB, %rdi sito_petla1: dec %rdi movb $1, sito_bufor(, %rdi, 1) movq $0, liczby(, %rdi, 8) cmp $0, %rdi jg sito_petla1 # Pętla wykonująca się dla każdej liczby z sita # [ for(i=2; i<$ILOSC_LICZB+2; i++) ] mov $0, %r10 mov $0, %rdi # Licznik indeksów w buforze sita # - od 0 do $ILOSC_LICZB. mov $2, %rsi # Licznik wartości elementów odpowiadających # indeksom w buforze sita. Dla pierwszego elementu # z bufora tj. o indeksie 0, wartością będzie 2, # ponieważ w obliczeniach pomijamy liczby 0 i 1. sito_petla2: # Jeśli aktualna liczba nie jest liczbą pierwszą przechodzimy # do kolejnego wykonania pętli. # [ if(sito[i-2] == 0) continue; ] mov sito_bufor(, %rdi, 1), %al cmp $0, %al je sito_pomin2 # Jeśli liczba jest liczbą pierwszą tj. w buforze sita ma # przypisaną wartość true, dopisujemy ją do bufora "liczby". mov %rsi, liczby(, %r10, 8) inc %r10 # Oznaczenie każdej wielokrotności wybranej liczby w buforze # sita jako liczbę nie pierwszą - tj. przypisanie jej wartości 0. # [ for(j=i; j<$ILOSC_LICZB+2; j+=i) ] mov %rdi, %r8 # Licznik indeksów w buforze sita # - od (i-2) do $ILOSC_LICZB. mov %rsi, %r9 # Licznik wartości - od i do $ILOSC_LICZB+2. sito_petla3: mov $0, %al mov %al, sito_bufor(, %r8, 1) add %rsi, %r8 add %rsi, %r9 cmp $ILOSC_LICZB, %r8 jl sito_petla3 sito_pomin2: # Zwiększenie liczników i ew. powrót na początek pętli głównej. inc %rdi inc %rsi cmp $ILOSC_LICZB, %rdi jl sito_petla2 ret # Powrót do miejsca wywołania funkcji |
Największy wspólny dzielnik (parametry przekazywane przez stos)
Jest to drugi kod z zadania domowego. Prezentuje on działanie funkcji rekurencyjnej oraz przekazywania parametrów przez stos. Wykorzystywany został tutaj algorytm Euklidesa. W kolejnych rekurencjach mniejsza, z pary liczb, jest odejmowana od większej, aż do momentu kiedy uzyskane liczby będą sobie równe. Wtedy następuje zwrot wartości i jej wyświetlenie.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 |
.data STDOUT = 1 SYSWRITE = 1 SYSEXIT = 60 EXIT_SUCCESS = 0 PIERWSZA_LICZBA = 5500 # Pierwsza z liczb dla których szukać # będziemy największego wspólnego dzielnika. DRUGA_LICZBA = 1250 # Druga -||- PODSTAWA_WYJSCIA = 10 POCZATEK_LICZB = 0x30 NOWA_LINIA = 0xA .bss .comm textinv, 512 # Bufory potrzebne do konwersji liczby .comm textout, 512 # na ciąg znaków ASCII. .text .globl _start _start: # # WYWOŁANIE FUNKCJI REALIZUJĄCEJ ALGORYTM EUKLIDESA # # Zapis pierwszej i drugiej liczby do rejestrów mov $PIERWSZA_LICZBA, %r8 mov $DRUGA_LICZBA, %r9 # Umieszczenie wartości obu rejestrów na stosie push %r8 push %r9 call nwd # Wywołanie funkcji add $16, %rsp # Usunięcie parametrów ze stosu # Wynik działania znajdzie się w rejestrze RAX. # # ZAMIANA LICZBY Z REJESTRU NA KOD ASCII W BUFORZE # przed_petla2: mov $PODSTAWA_WYJSCIA, %rbx mov $0, %rcx jmp petla2 petla2: mov $0, %rdx div %rbx # dzielenie bez znaku liczby z rejestru RAX przez RBX # i zapis wyniku do RAX oraz reszty z dzielenie do RDX. # reszta z dzielenia to przy każdej iteracji pętli kolejna # pozycja wyniku. po dodaniu kodu znaku pierwszej liczby, # są to kody znaków ASCII liczb na kolejnych pozycjach. add $POCZATEK_LICZB, %rdx # zapis znaków do bufora w odwrotnej kolejności mov %dl, textinv(, %rcx, 1) # zwiększenie licznika i w kolejnych iteracjach powrót # na początek pętli, aż do uzyskania zerowego wyniku dzielenia inc %rcx cmp $0, %rax jne petla2 jmp przed_petla3 # # ODWRÓCENIE KOLEJNOŚCI # # po wykonaniu ostatniego kroku, liczby zapisane są w buforze # w odwrotnej kolejności, w tej pętli są przepisywane z końca # na początek do nowego bufora textout. przed_petla3: mov $0, %rdi mov %rcx, %rsi dec %rsi jmp petla3 petla3: mov textinv(, %rsi, 1), %rax mov %rax, textout(, %rdi, 1) inc %rdi dec %rsi cmp %rcx, %rdi jle petla3 jmp wyswietl # # WYŚWIETLENIE WYNIKU # wyswietl: # dopisanie na końcu bufora wyjściowego znaku nowej linii movb $NOWA_LINIA, textout(, %rcx, 1) inc %rcx # wyświetlenie tekstu z bufora textout mov $SYSWRITE, %rax mov $STDOUT, %rdi mov $textout, %rsi mov %rcx, %rdx syscall # zwrot zera na wyjściu programu mov $SYSEXIT, %rax mov $EXIT_SUCCESS, %rdi syscall # # FUNKCJA REALIZUJĄCA ALGORYTM EUKLIDESA # nwd: push %rbp # Umieszczenie na stosie poprzedniej wartości # rejestru bazowego mov %rsp, %rbp # Pobranie zawartości rejestru RSP (zawierającego # wskaźnik na ostatni element umieszczony # na stosie) do rejestru bazowego. sub $8, %rsp # "Zwiększenie" wskaźnika stosu o jedną komórkę. mov 16(%rbp), %rax # Pobranie pierwszego argumentu do rejestru RAX. mov 24(%rbp), %rbx # Pobranie drugiego argumentu do rejestru RBX. # Porównanie obu liczb cmp %rax, %rbx jl mniejsza jg wieksza # Jeśli obie liczby są równe - koniec algorytmu jmp koniec # Jeśli liczba z rejestru RBX jest mniejsza niz druga - w RAX: mniejsza: sub %rbx, %rax # Odjęcie drugiej od pierwszej jmp rekurencja # Jeśli liczba z rejestru RBX jest większa niz druga - w RAX: wieksza: sub %rax, %rbx # Odjęcie pierwszej od drugiej jmp rekurencja # Rekurencyjne wywołanie funkcji dla nowych wartości rekurencja: push %rax push %rbx call nwd add $16, %rsp # Zakończenie wykonywania funkcji i zwrot wartości koniec: mov %rbp, %rsp pop %rbp ret |
Największy wspólny dzielnik (parametry przekazywane przez rejestry)
Trzecim programem z zadanie domowego była lekka modyfikacja kodu opisana w poprzednim punkcie. Parametry przekazywane są tutaj w sposób prostszy – przez umieszczenie ich w rejestrach, a nie jak poprzednio – przez stos.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 |
.data STDOUT = 1 SYSWRITE = 1 SYSEXIT = 60 EXIT_SUCCESS = 0 PIERWSZA_LICZBA = 5500 # Pierwsza z liczb dla których szukać # będziemy największego wspólnego dzielnika. DRUGA_LICZBA = 1250 # Druga -||- PODSTAWA_WYJSCIA = 10 POCZATEK_LICZB = 0x30 NOWA_LINIA = 0xA .bss .comm textinv, 512 # Bufory potrzebne do konwersji liczby .comm textout, 512 # na ciąg znaków ASCII. .text .globl _start _start: # # WYWOŁANIE FUNKCJI REALIZUJĄCEJ ALGORYTM EUKLIDESA # # Zapis pierwszej i drugiej liczby do rejestrów mov $PIERWSZA_LICZBA, %r8 mov $DRUGA_LICZBA, %r9 # Wywołanie funkcji call nwd # # ZAMIANA LICZBY Z REJESTRU NA KOD ASCII W BUFORZE # przed_petla2: mov %r8, %rax # skopiowanie liczby do rejestru RAX mov $PODSTAWA_WYJSCIA, %rbx mov $0, %rcx jmp petla2 petla2: mov $0, %rdx div %rbx # dzielenie bez znaku liczby z rejestru RAX przez RBX # i zapis wyniku do RAX oraz reszty z dzielenie do RDX. # reszta z dzielenia to przy każdej iteracji pętli kolejna # pozycja wyniku. po dodaniu kodu znaku pierwszej liczby, # są to kody znaków ASCII liczb na kolejnych pozycjach. add $POCZATEK_LICZB, %rdx # zapis znaków do bufora w odwrotnej kolejności mov %dl, textinv(, %rcx, 1) # zwiększenie licznika i w kolejnych iteracjach powrót # na początek pętli, aż do uzyskania zerowego wyniku dzielenia inc %rcx cmp $0, %rax jne petla2 jmp przed_petla3 # # ODWRÓCENIE KOLEJNOŚCI # # po wykonaniu ostatniego kroku, liczby zapisane są w buforze # w odwrotnej kolejności, w tej pętli są przepisywane z końca # na początek do nowego bufora textout. przed_petla3: mov $0, %rdi mov %rcx, %rsi dec %rsi jmp petla3 petla3: mov textinv(, %rsi, 1), %rax mov %rax, textout(, %rdi, 1) inc %rdi dec %rsi cmp %rcx, %rdi jle petla3 jmp wyswietl # # WYŚWIETLENIE WYNIKU # wyswietl: # dopisanie na końcu bufora wyjściowego znaku nowej linii movb $NOWA_LINIA, textout(, %rcx, 1) inc %rcx # wyświetlenie tekstu z bufora textout mov $SYSWRITE, %rax mov $STDOUT, %rdi mov $textout, %rsi mov %rcx, %rdx syscall # zwrot zera na wyjściu programu mov $SYSEXIT, %rax mov $EXIT_SUCCESS, %rdi syscall # # FUNKCJA REALIZUJĄCA ALGORYTM EUKLIDESA # nwd: # Porównanie obu liczb cmp %r8, %r9 jl mniejsza jg wieksza # Jeśli obie liczby są równe - koniec algorytmu ret # Jeśli liczba z rejestru R9 jest mniejsza niz druga - w R8: mniejsza: sub %r9, %r8 # Odjęcie drugiej od pierwszej call nwd # Rekurencyjne wykonanie funkcji ret # Powrót do miejsca jej wywołania # Jeśli liczba z rejestru R9 jest większa niz druga - w R8: wieksza: sub %r8, %r9 # Odjęcie pierwszej od drugiej call nwd # Rekruencyjne wykonanie funkcji ret # Powrót do miejsca jej wywołania |
Funkcja obliczająca n-ty wyraz ciągu
Jest to pierwszy program napisany na laboratorium. Wykorzystywana jest tutaj funkcja rekurencyjna która ma za zadanie obliczyć wartość podanego elementu ciągu. Pierwsze dwa wyrazy ciągu zostały podane i zapisane w stałych. Kolejne dwa bazują na poprzednich zgodnie ze wzorem: 3*f(n-1)+2*f(n-2)
, gdzie f(n)
to wartość funkcji dla danego parametru n – numeru wyrazu ciągu.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 |
.data STDOUT = 1 SYSWRITE = 1 SYSEXIT = 60 EXIT_SUCCESS = 0 ILOSC_WYRAZOW = 5 # Wyraz ciągu do obliczenia PIERWSZY_WYRAZ = 3 # Wartość pierwszego (0) wyrazu ciągu DRUGI_WYRAZ = -1 # Wartość drugiego (1) wyrazu ciągu PODSTAWA_WYJSCIA = 10 POCZATEK_LICZB = 0x30 NOWA_LINIA = 0xA PLUS = '+' MINUS = '-' .bss .comm textinv, 512 # Bufory potrzebne do konwersji liczby .comm textout, 512 # na ciąg znaków ASCII. .comm znak, 1 .text .globl _start _start: # # Wywołanie funkcji obliczającej n-ty wyraz ciągu # mov $ILOSC_WYRAZOW, %r8 push %r8 # Umieszczenie parametru na stosie call n # Wywołanie funkcji add $8, %rsp # Usunięcie parametru ze stosu # Wynik znajdzie się w rejestrze RBX. # # Odwrócenie liczby jeśli ujemna i ustawienie flagi znaku # mov $0, %r15 # Flaga znaku (domyślnie 0 = +) cmp $0, %rbx jge przed_petla2 # Pomiń jeśli liczba jest dodatnia not %rbx # Odwrócenie bitów liczby i dodanie 1, inc %rbx # aby uzyskać jej wartość bezwzględną. mov $1, %r15 # Ustawienie flagi znaku na 1 = -. # # ZAMIANA LICZBY Z REJESTRU NA KOD ASCII W BUFORZE # przed_petla2: mov %rbx, %rax # skopiowanie liczby do rejestru RAX mov $PODSTAWA_WYJSCIA, %rbx mov $0, %rcx jmp petla2 petla2: mov $0, %rdx div %rbx # dzielenie bez znaku liczby z rejestru RAX przez RBX # i zapis wyniku do RAX oraz reszty z dzielenie do RDX. # reszta z dzielenia to przy każdej iteracji pętli kolejna # pozycja wyniku. po dodaniu kodu znaku pierwszej liczby, # są to kody znaków ASCII liczb na kolejnych pozycjach. add $POCZATEK_LICZB, %rdx # zapis znaków do bufora w odwrotnej kolejności mov %dl, textinv(, %rcx, 1) # zwiększenie licznika i w kolejnych iteracjach powrót # na początek pętli, aż do uzyskania zerowego wyniku dzielenia inc %rcx cmp $0, %rax jne petla2 jmp przed_petla3 # # ODWRÓCENIE KOLEJNOŚCI # # po wykonaniu ostatniego kroku, liczby zapisane są w buforze # w odwrotnej kolejności, w tej pętli są przepisywane z końca # na początek do nowego bufora textout. przed_petla3: mov $0, %rdi mov %rcx, %rsi dec %rsi jmp petla3 petla3: mov textinv(, %rsi, 1), %rax mov %rax, textout(, %rdi, 1) inc %rdi dec %rsi cmp %rcx, %rdi jle petla3 # # WYŚWIETLENIE ZNAKU LICZBY # push %rcx # Odłożenie zawartości rejestru RCX na stosie. # Będzie on potrzebny do wywołania funkcji systemowej. # Umieszczenie znaku "+" w buforze znaku mov $0, %r12 movb $PLUS, znak(, %r12, 1) # Jeśli liczba jest dodatnia, przeskok do etykiety pomin cmp $0, %r15 je pomin # Jeśli liczba jest ujemna: # Zamiana znaku "+" na "-" movb $MINUS, znak(, %r12, 1) # Wyświetlenie zawartości bufora pomin: mov $SYSWRITE, %rax mov $STDOUT, %rdi mov $znak, %rsi mov $1, %rdx syscall pop %rcx # Ściągnięcie rejestru RCX ze stosu. # # WYŚWIETLENIE LICZBY # wyswietl: # dopisanie na końcu bufora wyjściowego znaku nowej linii movb $NOWA_LINIA, textout(, %rcx, 1) inc %rcx # wyświetlenie tekstu z bufora textout mov $SYSWRITE, %rax mov $STDOUT, %rdi mov $textout, %rsi mov %rcx, %rdx syscall # zwrot zera na wyjściu programu mov $SYSEXIT, %rax mov $EXIT_SUCCESS, %rdi syscall # # Funkcja obliczająca n-ty wyraz ciągu # n: # if(i==0) return 3; # if(i==1) return -1; # return 3*n(i-1)+2*n(i-2); # Pobranie przesłanego parametru - numeru wyrazu, do rejestru RAX. push %rbp mov %rsp, %rbp sub $8, %rsp mov 16(%rbp), %rax # Porównanie parametru "n" i skok do odpowiedniej etykiety cmp $1, %rax jl pierwszy_wyraz # Jeśli n=0 to f()=3 je drugi_wyraz # Jeśli n=1 to f()=-1 # Jeśli n >= 2: mov $0, %rcx # Czyszczenie rejestru RCX. # Będzie on przechowywał dotychczasowy wynik. # Trzykrotne wykonanie funkcji dla parametru n=n-1 # Za każdym razem wynik dodawany będzie do rejestru RCX. dec %rax push %rcx push %rax call n pop %rax pop %rcx add %rbx, %rcx push %rcx push %rax call n pop %rax pop %rcx add %rbx, %rcx push %rcx push %rax call n pop %rax pop %rcx add %rbx, %rcx # Dwukrotne wykonanie funkcji dla parametru n=n-2 # Za każdym razem wynik dodawany będzie do rejestru RCX. dec %rax push %rcx push %rax call n pop %rax pop %rcx add %rbx, %rcx push %rcx push %rax call n pop %rax pop %rcx add %rbx, %rcx # Zwrot wyliczonej wartości z rejestru RCX mov %rcx, %rbx # Wynik zwracany jest do rejestru RBX mov %rbp, %rsp pop %rbp ret # Zwrot wartości 3 jeśli przesłany parametr n=0 pierwszy_wyraz: mov $PIERWSZY_WYRAZ, %rbx mov %rbp, %rsp pop %rbp ret # Zwrot wartości -1 jeśli przesłany parametr n=1 drugi_wyraz: mov $DRUGI_WYRAZ, %rbx mov %rbp, %rsp pop %rbp ret |
Liczby pierwsze nie będące wspólnymi podzielnikami podanych dwóch liczb
Drugim zadaniem laboratoryjnym była modyfikacja kodu z punktu trzeciego – Sita Eratostenesa. Tym razem wyświetlone miały zostać liczby pierwsze nie będące wspólnymi podzielnikami podanej pary liczb. Zadanie zostało zrealizowane w postaci drugiej funkcji usuwającej z bufora liczb pierwszych te spełniające podane kryterium.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 |
.data STDOUT = 1 SYSWRITE = 1 SYSEXIT = 60 EXIT_SUCCESS = 0 ILOSC_LICZB = 9999 # Ilość liczb jakie sprawdzić ma algorytm PODSTAWA_WYJSCIA = 10 # Stałe wykorzystywane przy wyświetlaniu liczb POCZATEK_LICZB = 0x30 # -||- NOWA_LINIA = 0xA # -||- LICZBA_A = 30 # Liczby dla których wygenerowane liczby pierwsze LICZBA_B = 35 # nie mogą być wspólnymi podzielnikami .bss .comm sito_bufor, 9999 # Bufor wartości 0/1 decydujących czy dana # liczba (indeks+2) jest liczbą pierwszą # czy nie. Jego rozmiar to ilość liczb # do wygenerowanie - 2. .comm liczby, 79992 # Bufor przechowujący liczby pierwsze # wygenerowane przez algorytm. Każda liczba # zapisywana jest na 64 bitach, czyli 8 bajtach, # więc jego rozmiar to 8 * rozmiar poprzedniego # bufora. .comm textinv, 512 # Bufory wykorzystywane do zamiany liczba .comm textout, 512 # na postać ciągów kodów ASCII kolejnych cyfr. .text .globl _start _start: # # Wywołanie funkcji realizującej algorytm sita Eratostenesa. # Jej kod został umieszczony na końcu programu. # call sito_eratostenesa # # Wywołanie funkcji usuwającej z bufora liczby będące wspólnymi # podzielnikami liczb $LICZBA_A i $LICZBA_B. # Jej kod został umieszczony na końcu programu. # call sito_eratostenesa # # WYŚWIETLENIE WYNIKU DZIAŁANIA ALGORYTMU # # Zamiana wartości liczb wygenerowanych i umieszczonych przez # algorytm w buforze "liczby" do postaci ciągów kodów ASCII # i ich wyświetlenie. # mov $0, %r8 # Licznik do pętli - zostanie ona wykonana dla każdej # komórki bufora "liczby". Liczby o wartości zero nie # zostaną wyświetlone. petla1: mov liczby(, %r8, 8), %rax # Skopiowanie liczby do rejestru RAX cmp $0, %rax je pomin # # DEKODOWANIE WARTOŚCI LICZBY W PĘTLI # mov $PODSTAWA_WYJSCIA, %rbx mov $0, %rcx petla2: mov $0, %rdx div %rbx # Dzielenie bez znaku liczby z rejestru RAX przez RBX # i zapis wyniku do RAX oraz reszty z dzielenie do RDX. # Reszta z dzielenia to przy każdej iteracji pętli kolejna # pozycja wyniku. Po dodaniu kodu znaku pierwszej liczby, # są to kody znaków ASCII liczb na kolejnych pozycjach. add $POCZATEK_LICZB, %rdx # Zapis znaków do bufora w odwrotnej kolejności mov %dl, textinv(, %rcx, 1) # Zwiększenie licznika i w kolejnych iteracjach powrót # na początek pętli, aż do uzyskania zerowego wyniku dzielenia inc %rcx cmp $0, %rax jne petla2 jmp przed_petla3 # # ODWRÓCENIE KOLEJNOŚCI CYFR # # Po wykonaniu ostatniego kroku, cyfry zapisane są w buforze # w odwrotnej kolejności, w tej pętli są przepisywane z końca # na początek do nowego bufora textout. przed_petla3: mov $0, %rdi mov %rcx, %rsi dec %rsi petla3: mov textinv(, %rsi, 1), %rax mov %rax, textout(, %rdi, 1) inc %rdi dec %rsi cmp %rcx, %rdi jle petla3 # # WYŚWIETLENIE LICZBY # # Dopisanie na końcu bufora wyjściowego znaku nowej linii movb $NOWA_LINIA, textout(, %rcx, 1) inc %rcx # Wyświetlenie tekstu z bufora textout mov $SYSWRITE, %rax mov $STDOUT, %rdi mov $textout, %rsi mov %rcx, %rdx syscall pomin: # Powrót na początek pętli aż do wykonania instrukcji dla # wszystkich liczb. inc %r8 cmp $ILOSC_LICZB, %r8 jl petla1 # # ZAKOŃCZENIE PROGRAMU # mov $SYSEXIT, %rax mov $EXIT_SUCCESS, %rdi syscall # # FUNKCJA REALIZUJĄCA ALGORYTM SITA ERATOSTENESA # sito_eratostenesa: # Czyszczenie bufora liczb i sita w pętli mov $ILOSC_LICZB, %rdi sito_petla1: dec %rdi movb $1, sito_bufor(, %rdi, 1) movq $0, liczby(, %rdi, 8) cmp $0, %rdi jg sito_petla1 # Pętla wykonująca się dla każdej liczby z sita # [ for(i=2; i<$ILOSC_LICZB+2; i++) ] mov $0, %r10 mov $0, %rdi # Licznik indeksów w buforze sita # - od 0 do $ILOSC_LICZB. mov $2, %rsi # Licznik wartości elementów odpowiadających # indeksom w buforze sita. Dla pierwszego elementu # z bufora tj. o indeksie 0, wartością będzie 2, # ponieważ w obliczeniach pomijamy liczby 0 i 1. sito_petla2: # Jeśli aktualna liczba nie jest liczbą pierwszą przechodzimy # do kolejnego wykonania pętli. # [ if(sito[i-2] == 0) continue; ] mov sito_bufor(, %rdi, 1), %al cmp $0, %al je sito_pomin2 # Jeśli liczba jest liczbą pierwszą tj. w buforze sita ma # przypisaną wartość true, dopisujemy ją do bufora "liczby". mov %rsi, liczby(, %r10, 8) inc %r10 # Oznaczenie każdej wielokrotności wybranej liczby w buforze # sita jako liczbę nie pierwszą - tj. przypisanie jej wartości 0. # [ for(j=i; j<$ILOSC_LICZB+2; j+=i) ] mov %rdi, %r8 # Licznik indeksów w buforze sita # - od (i-2) do $ILOSC_LICZB. mov %rsi, %r9 # Licznik wartości - od i do $ILOSC_LICZB+2. sito_petla3: mov $0, %al mov %al, sito_bufor(, %r8, 1) add %rsi, %r8 add %rsi, %r9 cmp $ILOSC_LICZB, %r8 jl sito_petla3 sito_pomin2: # Zwiększenie liczników i ew. powrót na początek pętli głównej. inc %rdi inc %rsi cmp $ILOSC_LICZB, %rdi jl sito_petla2 ret # Powrót do miejsca wywołania funkcji. # # Funkcja usuwająca liczby będące wspólnymi # podzielnikami liczb $LICZBA_A i $LICZBA_B # usun_podzielniki: # Pętla wykonująca się dla każdej liczby z bufora "liczby" mov $0, %rdi # Licznik do pętli (od 0 do długości bufora-1) usun_petla: mov liczby(, %rdi, 8), %rbx # Pobranie liczby z bufora # do rejestru RBX. # Jeśli liczba jest równa zero, przeskok # do kolejnej iteracji cmp $0, %rbx je zostaw # Jeśli liczba jest większa niż $LICZBA_A, wyzerowanie jej cmp $LICZBA_A, %rbx jge zeruj # Jeśli liczba jest większa niż $LICZBA_B, wyzerowanie jej cmp $LICZBA_B, %rbx jge zeruj # Jeśli reszta z dzielenia $LICZBA_A przez liczbę # z bufora jest różna od zera, pozostawienie liczby # w buforze i przeskok do kolejnej iteracji. mov $0, %rdx mov $LICZBA_A, %rax div %rbx cmp $0, %rdx jne zostaw # Jeśli reszta z dzielenia $LICZBA_B przez liczbę # z bufora jest różna od zera, pozostawienie liczby # w buforze i przeskok do kolejnej iteracji. mov $0, %rdx mov $LICZBA_B, %rax div %rbx cmp $0, %rdx jne zostaw # W przeciwnym przypadku - liczba jest wspólnym # podzielnikiem $LICZBA_A i $LICZBA_B - wyzerowanie # jej wartości i przeskok do kolejnej iteracji pętli. zeruj: movq $0, liczby(, %rdi, 8) zostaw: inc %rdi cmp $ILOSC_LICZB, %rdi jl usun_petla ret # Powrót do miejsca wywołania funkcji |