Architektura Komputerów 2 – Laboratorium nr 4 – Stos i funkcje

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:

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.

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.

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.

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.

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.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *