# ASK 2020 GR. Kraski cz I
## Lista 3 (26.03.2020)
### Zadanie 1
:::info
Zastąp instrukcję dzielenia całkowitoliczbowego zmiennej $n$ typu ```int32_t``` przez stałą 3 przy pomocy operacji mnożenia liczb typu ```int64_t```. Skorzystaj z faktu, że $\frac{x}{k} \equiv x \cdot \frac{1}{k}$. Przedstaw dowód poprawności swojego rozwiązania. Instrukcja dzielenia działa zgodnie z wzorem podanym na wykładzie, tj.:
$$
\texttt{div3}(n) =
\begin{cases}
\lfloor \frac{n}{3} \rfloor & \text{dla } n \geq 0 \\
\lceil \frac{n}{3} \rceil & \text{dla } n < 0
\end{cases}
$$
:::
```c=
x = 0x55555556
y = ((x * n) >> 32)
y = y + ((n>>31) & 1);
```
Dowód:
Zauważmy, że $x = \frac{2^{32}+2}{3}$
1. Dla $n \geq 0$
y = x * n >> 32 czyli $\frac{x \cdot n}{2^{32}}$
Rozipisując,
$$
y = \Big\lfloor \frac{2^{32} \cdot n + 2 \cdot n}{3 \cdot 2^{32}} \Big\rfloor =
\Big\lfloor \frac{n}{3} + \frac{2 \cdot n}{3 \cdot 2^{32}} \Big\rfloor
$$
2. dla $n < 0$
y = x * n >> 32 + 1, czyli $\frac{x\cdot n}{2^{32}} + 1$
Rozipisując
$$
y = \Big\lfloor \frac{2^{32} \cdot n + 2 \cdot n + 3 \cdot 2^{32}}{3 \cdot 2^{32}} \Big\rfloor =
\Big\lceil \frac{2^{32} \cdot n + 2 \cdot n + 1}{3 \cdot 2^{32}} \Big\rceil =
\Big\lceil \frac{n}{3} + \frac{2 \cdot n + 1}{3 \cdot 2^{32}} \Big\rceil
$$
Przejście z podłogi do sufitu:
$$
\Big\lfloor \frac{n + d - 1}{d} \Big\rfloor = \Big\lceil \frac{n}{d} \Big\rceil
$$
W obu przypadkach "reszta", która nam została jest bardzo mała i nie zmienia wyniku w przypadku, gdyby jej nie było.
### Zadanie 2
:::info
Standard IEEE 754-2008 definiuje liczby zmiennopozycyjne o szerokości 16-bitów. Zapisz ciąg bitów reprezentujący liczbę $1.5625 \cdot 10^{-1}$. Porównaj zakres liczbowy i dokładność w stosunku do liczb zmiennopozycyjnych pojedynczej precyzji (```float```).
:::
Odpowiedz:
0.15625 = 0b0 01100 0100000000
halfy sa postaci: 1 bit znaku, 5 bitow cechy, 10 bitow mantysy
najpierw zapisujemy 0.15625 jako fixed precision:
0.00101 przesuwamy . o 3 miejsca w prawo (mnozymy przez 2^-3)
otrzymujemy 1.01
bias dla half'ów to 15 wiec chcemy zakodowac 15 - 3 = 12
s = 0
exp = 01100 = 12
frac = 0100000000
czyli 0.15625 = 0b0 01100 0100000000
zakres liczbowy single precision (float):
[-3.4 * 10^38, 3.4 * 10^38]
dokladnosc single precision (float):
24/log2(10) co daje 7 znaczacych cyfr po przecinku
zakres liczbowy half precision:
[-65504,65504]
* największa liczba - 2^15 * (2-1/2^10^)
* najmniejsza dodatnia wartość znormalizowana - 2^-14^ * 1
* najmniejsza wartość dodatnia - 2^-14^ *1/2^10^ = 2^-24^
dokladnosc half precision:
11/log2(10) co daje 3 znaczace cyfry po przecinku
### Zadanie 3
:::info
Oblicz ręcznie $3.984375 \cdot 10^{-1} + 3.4375 \cdot 10^{-1} + 1.771 \cdot 10^{3}$ używając liczb w formacie z poprzedniego zadania. Zapisz wynik binarnie i dziesiętnie. Czy wynik się zmieni jeśli najpierw wykonamy drugie dodawanie?
:::
Najpierw dostosujmy liczby do naszej reprezentacji:
$3.984375 \cdot 10^{-1} = 0.0110011_{2} = 1.10011_{2} \cdot 2^{-2}$
$3.4375 \cdot 10^{-1} = 0.01011_{2} = 1.011_{2} \cdot 2^{-2}$
$1.771 \cdot 10^{3} = 11011101011 = 1.1011101011 \cdot 2^{10}$
Przystępujemy do obliczania pamiętając o wyrównaniu, by uzyskać takie same wykładniki(dodając) oraz o zasadach zaokrąglania (round to even):
$1.10011_{2} \cdot 2^{-2} + 1.011 \cdot 2^{-2} + 1.1011101011_{2} \cdot 2^{10}=$
$10.0011_{2} \cdot 2^{-2} + 1.1011101011_{2} \cdot 2^{10}=$
$1.011111_{2} \cdot 2^{-1} + 1.1011101011_{2} \cdot 2^{10}=$
$(0.00000000001011111_{2} + 1.1011101011_{2}) \cdot 2^{10}=$
$1.101110101110_{2} \cdot 2^{10} = 1.10111011_{2} \cdot 2^{10} = 1772_{10}$
Zamieniając kolejność:
$1.011 \cdot 2^{-2} + 1.1011101011_{2} \cdot 2^{10} + 1.10011_{2} \cdot 2^{-2}=$
$(0.000000000001011_{2} + 1.1011101011_{2}) \cdot 2^{10} + 1.10011_{2} \cdot 2^{-2}=$
$1.1011101011_{2} \cdot 2^{10} + 1.10011_{2} \cdot 2^{-2} =$
$1.1011101011_{2} \cdot 2^{10} = 1771_{10}$
Wyniki różnią się w zależności od tego, w jakiej kolejności wykonywaliśmy dodawanie. Powodem jest to, że po każdym dodawaniu musimy zaokrąglić liczbę tak, aby zmieściła się w naszym typie, stąd dodając bardzo małą liczbę do dużej możemy ją 'zgubić', jeśli nie jest wystarczająco znacząca (tak stało się przy zamienieniu kolejności działania).
### Zadanie 4
:::info
Mamy zmienne $x$, $y$ i $z$ typu ```int32_t``` ustawione na wybrane przez nas wartości. Konwertujemy je do liczb typu ```double``` zapisanych w zmiennych $dx$, $dy$ i $dz$. Rozważmy poniższe wyrażenia z języka ```C```. Wskaż, które z nich mogą obliczyć się do fałszu. Podaj kontrprzykład – konkretne wartości naszych zmiennych całkowitoliczbowych.
* ```(float)x == (float)dx```
* ```dx - dy == (double)(x - y)```
* ```(dx + dy) + dz == dx + (dy + dz)```
* ```(dx * dy) * dz == dx * (dy * dz)```
* ```dx / dx == dz / dz```
:::
* ```(float)x == (float)dx``` - Zawsze true
Zmiana z int na double jest bezstratna i po zmianie na float w równianiu
otrzymujemy to samo.
* ```dx - dy == (double)(x - y)```
Kontrprzykład: x = INT_MIN i y = 1
Po lewej stronie wykona się normalnie odejmowanie,
a natomiast po prawej będziemy mieli underflow i dopiero
po tym zmiane na double.
* ```(dx + dy) + dz == dx + (dy + dz)``` - Zawsze true
Dodawanie nigdy nie wyjdzie poza zakres nawet jak każda
z liczb będzie równa INT_MAX, bo 3*INT_MAX < DBL_MAX
Tak samo jeśli chodzi o underflow.
Z racji, że operujemy na liczbach rzędu 2^33^, spokojnie mieścimy się w zakresie double.
* ```(dx * dy) * dz == dx * (dy * dz)```
Wybierając duże, przypadkowe x,y,z może zdarzyć sie, że
nastąpi zaokrąglenie które sprawi, że otrzymamy fałsz.
Z racji, że operujemy na liczbach rzędu 2^96^, czasami potrzebne jest zaokrąglanie, które może sprawić, że dostaniemy różne wyniki.
* ```dx / dx == dz / dz```
Kontrprzykład: x = 1 y = 0
Po lewej stronie otrzymamy 1 natomiast po prawej będziemy
mieli dzielenie 0/0 i dostaniemy jakąś przpadkową liczbę.
### Zadanie 5
:::info
Reprezentacje binarne liczb zmiennoprzecinkowych $f$ i $g$ typu ```float``` zostały załadowane odpowiednio do zmiennych ```x``` i ```y``` typu ```uint32_t```. Podaj wyrażenie, które:
* zmieni znak liczby ```x```,
* obliczy wartość $\lfloor log_2 |\texttt{f}| \rfloor$ typu ```int``` dla $f$ w postaci znormalizowanej,
* zwróci wartość logiczną operacji ```x == y```,
* zwróci wartość logiczną operacji ```x < y```.
Pamiętaj, że dla liczb zmiennopozycyjnych w standardzie IEEE 754 zachodzi $-0 \equiv +0$. Można pominąć rozważanie wartości ```NaN```.
:::
1. Należy zmienić bit znaku na przeciwny: ```x ^= (1 << 31);```
2. Korzystamy z informacji zapisanych w EXP: ```((x >> 23) & 255) - 127;```
3. Specjalny przypadek $0 = -0$: ```(x == y) | (x | y == (1 << 31))```
4. Porównujemy, znowu $0 = -0$ jest problemem:
```(x>=0 && x<y) || (x<0 && x>y)```
```(((~(x | y) & (x - y)) | (x & y & (y - x)) | (x & ~y)) & (1ll << 31)) != 0 & ((x | y) != (1ll << 31))```
> Zauważmy, że jeśli liczby są tego samego znaku, to najpierw powinniśmy porównać ich wykładniki, a jeśli są równe, to porównać mantysy. Bity liczby są akurat tak ustawione, że tak naprawdę wystarczy porównać ich wartości bitowe. Do tego wystarczy orównać znak ich różnicy. Zatem aby wykonać zadanie musimy:
> * jeśli obie są dodatnie, to sprawdzić znak x-y,
> * jeśli obie są ujemne, to sprawdzić znak y-x,
> * jeśli x jest ujemne a y dodatnie to zwracamy prawdę,
> * na końcu sprawdzić czy nie są zerami.
>
$$
-Nan < -\infty < -Norm < -Denorm \leq +Denorm < Norm < +\infty < +Nan
$$
### Zadanie 6
:::info
Reprezentacja binarna liczby zmiennoprzecinkowej $f$ typu ```float``` została załadowana do zmiennej ```x``` typu ```uint32_t```. Podaj algorytm obliczający $f \cdot 2^i$ wykonujący obliczenia na zmiennej ```x``` używając wyłącznie operacji na liczbach całkowitych. Osobno rozważ $i \ge 0$ i $i < 0$. Zakładamy, że liczba $f$~jest znormalizowana, ale wynik operacji może dać wartość $\pm \infty$, $\pm 0$ lub liczbę zdenormalizowaną. Możesz założyć, że wynik zaokrąglamy w kierunku zera.
:::
#### Rozwiązanie:
```c=
int e = ((x & 0x7f800000) >> 23) - 127;
e = e + i;
if (e>127)
x=0x7FF0000000000000 + x^(1<<31);
else if (-150 <= e && e <= -127)
x = (x & 0x80000000) + ((x&0x007fffff) >> -(e + 127));
else if (e < -150)
x = 0;
else
x = (x&807fffff) + (127 + e)<<23;
```
do wyliczenia korzystamy ze wzoru:
$(-1)^S \cdot M \cdot 2^{i + E}$
gdzie M to Mantysa, E to cecha, S to bit znaku
###### obliczamy i + exponent
```c=
int e = ((x & 0x7f800000) >> 23) - 127;
e = e + i;
```
###### Jeżeli jest za duże to ustawiamy x = INF
```c=
if (e>127)
x=0x7FF0000000000000 + x^(1<<31);
```
###### na tym przedziale wynik jest zdenormalizowany
```c=
else if (-150 <= e && e <= -127)
x = (x & 0x80000000) + ((x&0x007fffff) >> -(e + 127));
```
###### Jeżeli za mała liczba - ustwiamy x = 0 (pomijamy znak 0)
```c=
else if (e < -150)
x = 0;
```
###### w każdym innym wypadku wynik jest znormalizowany
```c=
else
x = (x&807fffff) + (127 + e)<<23;
```
### Zadanie 7
:::info
Masz liczbę ```double``` jako ```uint64_t```. Wyprodukuj ```float``` z zaokręgleniem do najbliższej parzystej. Podaj definicje bitów guard, round, sticky.
:::
>Zanim przystąpimy do rozwiązania należy zwrócić uwagę na format double i float:
>
>$double$
>|sign |exponent| fraction|
>|------|--------|---------|
>|1 bit |11 bits | 52 bits |
>$float$
>|sign |exponent| fraction|
>|------|--------|---------|
>|1 bit | 8 bits | 23 bits |
>
> Double zapewnia nam większą dokładność, dlatego musimy zaokrąglić mantysę zgodnie z założeniami round to even.
>
>
> Ponieważ na zakodowanie wykładnika float mamy 8 bitów to:
> $E_{minn} = -126$ - dla liczb w postaci znormalizowanej
> $E_{minz} = -149$ - dla liczb w postaci zdenormalizowanej
> $E_{max} = 127$
>
> Konwertując musimy zatem rozważyć następujące przypadki brzegowe:
> * Jeśli wyliczone $E_{double} > 127$ zwracamy +∞,
> * Gdy $E_{double} < -149$ zwracamy 0,
> * W przypadku $-149 ≤ E_{double} ≤ -126$ zwracamy liczbę zdenormalizowaną.
```cpp
uint32_t double_to_float(uint64_t x)
{
// obliczamy każdą część naszej liczby double
int32_t sign = (x >> 63) & 1;
/*dekodujemy wykładnik i kodujemy go na wykładnik float:
(x >> 52) & ((1 << 11) - 1) <- wyodrębnienie EXPd
1023 <- Bias double
127 <- Bias float */
int32_t e = (x >> 52) & ((1 << 11) - 1) - 1023 + 127;
int64_t frac = x & ((1 << 52) - 1);
//zaczynamy obliczać części do floata
/* wyodrębniamy pierwsze 23 bity pierwotnej mantysy*/
int32_t new_frac = (frac >> 29);
//wartości do zaokrąglania
/*
guard - najmniej znaczący bit wyniku
round - najbardziej znaczący usuwany bit
sticky - OR pozostałych usuwanych bitów
*/
int32_t guard = (frac >> 29) & 1;
int32_t round = (frac >> 28) & 1;
int32_t sticky = (frac & 0xFFFFFFF) != 0;
//0xFFFFFFF wyodrębnia 28 dolnych bitów
// zaokrąglenie
/*
1.gdy round = sticky = 1 mamy przypadek, w którym jesteśmy w
'ponad połowie'
do następnej liczby i zaokrąglamy
2.gdy round = guard = 1 mamy przypadki
* jeśli sticky = 0 to jesteśmy w połowie i zaokrąglamy
do najbliższej parzystej (w górę)
* jeśli sticky = 1 to przypadek 1.
*/
if (round == 1 && (sticky == 1 || guard == 1))
new_frac++;
//sprawdzamy czy zaokrąglając mantysę nie przekroczymy 2
if (new_frac >= (1 << 23))
{
e++;
new_frac ^= (1 << 23);
}
// jeśli mamy zbyt duży wykładnik, zwracamy inf
if (e > 253)
return (sign << 31) | 0x7F800000;
// jeśli mamy zbyt mały wykładnik, zwracamy 0
if (e < -23)
return 0;
// jeśli wykładnik wpada w przedział zdenormalizowanych
if (e >= -23 && e <= 0)
{
//przesuwamy mantysę
new_frac = new_frac >> -e;
e = 0;
}
return (sign << 31) | (e << 23) | new_frac;
}
```
### Zadanie 8
:::info
Uzupełnij ciało funkcji zadeklarowanej następująco:
```cpp
/* Skonwertuj reprezentację liczby float do wartości int32_t. */
int32_t float2int(int32_t f);
```
Zaokrąglij liczbę w kierunku zera. Jeśli konwersja spowoduje nadmiar lub $f$ ma wartość ```NaN```, zwróć ```0x80000000```. Dla czytelności napisz najpierw rozwiązanie z instrukcjami warunkowymi. Potem przepisz je, by zachować zgodność z wytycznymi z nagłówka listy.
Uwaga: prowadzący zezwala na użycie instrukcji ```if``` i porównań.
:::
```c=
int float2int(int f){
//0x7FFFFF = 0b00000000011111111111111111111111
//0x7F800000 = 0b01111111100000000000000000000000
//1.
/*
Wyciągamy wszystkie części float'a
i dosuwamy je do prawej strony.
Każdy bit sign jest równy bitowi znaku.
*/
int sign = f>>31;//znak
int mant = 0x7FFFFF&f;//mantysa
int exp = (0x7F800000&f)>>23;//cecha
//2.
/*
(mant | 1<<23) - dopisujemy do mantysy
ukrytą jedynkę sprzed przecinka.
(exp-127) - pozbywamy się uprzedzenia cechy
Przemnażamy mantysę przez 2^cecha - uzyskujemy
wartość bezwzględną wyniku.
+-23 - bierzemy pod uwagę, że mantysa, to tak naprawdę liczby po przecinku
*/
/*
sign jest całe wypełnione tym samym bitem,
dlatego and'owanie z sign działa.
Jeśli f jest ujemna, to odwracamy res,
inaczej zostawiamy bez zmian.
*/
int res;
if(sign){
res = (mant | 1<<23)>>(exp-127+23);
res = -res;
}
else{
(mant | 1<<23)<<(exp-127-23);
}
//bitowo:
/*
int res = sign & (mant | 1<<23)>>(exp-127+23) + ~sign & (mant | 1<<23)<<(exp-127-23);
res = sign & -res + ~sign & res;
*/
//3.
/*
Sprawdzamy NaN i infinity(oba mają mantysę równą 0b11111111).
(b<<31)>>31 propaguje nam wartość b[0] na każdy
bit (czego potrzebujemy, by nasz bitowy "if" działał).
*/
if(exp==0b11111111){
res = 0x80000000;
}
//bitowo:
int mask = ((exp==0b11111111)<<31)>>31
res = mask & 0x80000000 + ~mask & res;
//4.
/*
Sprawdzamy nadmiar.
Nasz wynik zajmuje 24 najmłodsze bity res.
Zatem największe exp nie powodujące nadmiaru to 7
(bo potem wejdziemy z ukrytym bitem sprzed przecinka
(dopisanym w 2.) na bit znaku).
*/
//można to zapisać bitowo, ale dla czytelności zostawmy tak
if(exp>7){
res = 0x80000000;
}
return res;
}
```
# Lista 4 (02.04.2020)
### Zadanie 1
:::info
Poniżej podano wartości typu ```long``` leżące pod wskazanymi adresami i w rejestrach:
|Adres | Wartość| | Rejestr| Wartość|
|-------|--------|-|--------|--------|
| 0x100 | 0xFF | | %rax | 0x100
| 0x108 | 0xAB | | %rcx | 1
| 0x110 | 0x13 | | %rdx | 3
| 0x118 | 0x11 | |
Oblicz wartość poniższych operandów:
1. %rax
2. 0x110
3. $0x108
4. (%rax)
5. 8(%rax)
6. 21(%rax,%rdx)
7. 0xFC(,%rcx,4)
8. (%rax,%rdx,8)
9. 265(%rcx,%rdx,2)
:::
1) `%rax` zwróci nam $0\text{x}100$
2) `0x110` zwróci nam to, co przechowuje, mianowicie $0\text{x}13$
3) `$0x108` to stała, więc wynik wynosi $0\text{x}108$
4) `(%rax)` zwraca to, co jest pod adresem równym wartości `%rax`, czyli $0\text{x}FF$
5) `8(%rax)` obliczy $0\text{x}100+8=0\text{x}108$, pod której adresem znajduje się $0$x$AB$
6) `21(%rax, %rdx)` oblicza się do $(21+0\text{x}100+0\text{x}3)=(0\text{x}15+0\text{x}100+0\text{x}3)=0\text{x}118$ pod którym kryje się $0\text{x}11$
7) `0xFC(,%rcx,4)` obliczy się do $4*0\text{x}1+0\text{xFC} = 0\text{x}100$ pod którym kryje się $0\text{xFF}$
8) `(%rax, %rdx,8)` obliczy się do $0\text{x}100 + 8*0\text{x}3 = 0\text{x}100 + 0\text{x}18 = 0\text{x}118$ pod którym kryje się $0\text{x}11$
9) `265(%rcx, %rdx,2)` obliczy się do $0\text{x}1 + 2*0\text{x}3 + 0\text{x}109 = 0\text{x}7 + 0\text{x}109 = 0\text{x}110$ pod którym kryje się $0\text{x}13$
### Zadanie 2
:::info
Każdą z poniższych instrukcji wykonujemy w stanie maszyny opisanym tabelką z poprzedniego zadania. Wskaż miejsce, w którym zostanie umieszczony wynik działania instrukcji, oraz obliczoną wartość.
```assembly=
addq %rcx,(%rax)
subq 16(%rax),%rdx
shrq $4,%rax
incq 16(%rax)
decq %rcx
imulq 8(%rax)
leaq 7(%rcx,%rcx,8),%rdx
leaq 0xA(,%rdx,4),%rdx
```
:::
1.addq %rcx, (%rax)
(%rax) = (%rax) + %rcx
0x100 = 0xFF + 0x1
0x100 = 0x100
2.subq 16(%rax), %rdx
%rdx = %rdx - 0x10(%rax)
%rdx = 0x3 - (0x100 + 0x10)
%rdx = 0x3 - (0x110)
%rdx = 0x3 - 0x13
%rdx = 0xFFFFFFF0
3.shrq $4, %rax // shrq src,dest -> dest = dest >> src
%rax = %rax >> 0x4
%rax = 0x100 >> 0x4
%rax = 0x10
4.incq 16(%rax)
0x10(%rax) = 0x10(%rax) + 0x1
0x110 = (0x110) + 0x1
0x110 = 0x13 + 0x1
0x110 = 0x14
5.decq %rcx
%rcx = 0x1 - 0x1
%rcx = 0x0
6.imulq 8(%rax)
%rdx: %rax = 8(%rax) * %rax
%rdx: %rax = (0x100 + 0x8) * 0x100
%rdx: %rax = (0x108) * 0x100
%rdx: %rax = 0xAB * 0x100
%rdx: %rax = 0xAB00
7.leaq 7(%rcx, %rcx, 8), %rdx
%rdx = %rcx + 8*%rcx + 0x7
%rdx = 0x1 + 0x8 + 0x7
%rdx = 0x10
8.leaq 0xA(,%rdx,4),%rdx
%rdx = 0x4 * 0x3 + 0xA
%rdx = 0xC + 0xA
%rdx = 0x16
### Zadanie 3
:::info
W rejestrach %rdi i %rsi przechowujemy wartość zmiennych ```x``` i ```y```. Porównujemy je instrukcją ```cmp %rsi,%rdi```. Jakiej instrukcji należy użyć, jeśli chcemy skoczyć do etykiety ```label``` gdy:
1. ```x``` był wyższy lub równy ```y```,
2. ```y``` nie był mniejszy lub równy ```x```,
3. ```x``` nie był niższy lub równy ```y```,
:::
```
cmp %rsi, %rdi # (%rsi trzyma y, %rdi trzyma x)
```
cmp ustawia flagi dla operacji x-y ( można na to patrzeć jak na x + (-y) )
Flagi modyfikowane przez cmp:
| flaga | | |
| ----- | --------------- |:--------------------------------------------------------------------:|
| CF | "Carry Flag" | Wystąpił Overflow dla liczb Unsigned (dodawanie z "pożyczką") |
| OF | "Overflow Flag" | Wystąpił Overflow dla liczb Signed |
| SF | "Sign Flag" | Mówi czy w wyniku operacji zapalił się bit znaku |
| ZF | "Zero Flag" | Mówi czy operacja dała wynik 0 |
| PF | "Parity Flag" | Mówi czy w wyniku operacji dostaliśmy liczbę z parzystą liczbą bitów |
#### 1. x wyższy lub równy y
(wyższy - większy w znaczeniu Unsigned)
jae - Jump if above or equal (też jnb)
wykonuje skok jeżeli CF = 0
```
jae <<label>> #~CF
```
#### 2. y nie był mniejszy lub równy x
!(y<=x) czyli x<y
a więc: x-y < 0
jl - jump if less (signed) (też jnge)
wykonuje skok gdy tylko i wyłącznie jedna z flag SF lub OF = 1
```
jl <<label>> #SF^0F
```
cmp zapali flagę SF bo liczba x-y < 0
#### 3. x nie był niższy lub równy y
(niższy - mniejszy w znaczeniu unsigned)
!(x <= y) <=> (x > y)
ja - Jump if above (unsigned) (też jnbe)
wykonuje skok gdy CF = 0 i SF = 0
```
ja <<label>> #~CF&~SF
```
### Zadanie 4
:::info
Zaimplementuj w asemblerze x86-64 procedurę konwertującą liczbę typu ```uint32_t``` między formatem little-endian i big-endian. Argument funkcji jest przekazany w rejestrze %edi, a wynik zwracany w rejestrze %eax. Należy użyć instrukcji cyklicznego przesunięcia bitowego ```ror``` lub ```rol```.
Podaj wyrażenie w języku C, które kompilator optymalizujący przetłumaczy do instrukcji ```ror``` lub ```rol```.
:::
```=
%edi = 0x4A 3B 2C 1D
ROLW %di, 8 -> %edi = 0x4A 3B 1D 2C
ROLL %edi, 16 -> %edi = 0x1D 2C 4A 3B
ROLW %di, 8 -> %edi = 0x1D 2C 3B 4A
MOVL %edi,%eax -> %eax = 0x1D 2C 3D 4A
```
Wyrażenie w C:
```c=
x=(x<<count)|(x>>(32-count))
```
### Zadanie 5
:::info
Zaimplementuj w asemblerze x86-64 funkcję liczącą wyrażenie ```x + y```. Argumenty i wynik funkcji są 128-bitowymi liczbami całkowitymi ze znakiem i nie mieszczą się w rejestrach maszynowych. Zatem ```x``` jest przekazywany przez rejestry %rdi (starsze 64 bity) i %rsi (młodsze 64 bity), analogicznie argument ```y``` jest przekazywany przez %rdx i %rcx, a wynik jest zwracany w rejestrach %rdx i %rax.
Wskazówka! Użyj instrukcji ```adc```. Rozwiązanie wzorcowe składa się z 4 instrukcji bez ```ret```.
:::
| | Starsze bity | Mlodsze bity |
| --- | ------------ | ------------ |
| x | %rdi | %rsi |
| y | %rdx | %rcx |
| ret | %rdx | %rax |
ADD:
"It evaluates the result for both signed and unsigned integer operands and sets the CF and OF flags to indicate a carry (overflow) in the signed or unsigned result, respectively. "
```
add128:
#dodajemy mlodsze bity
addq %rsi, %rcx #flaga CF trzyma overflow z dodawania
#dodajemy starsze bity + flage CF dzieki adc (DEST <- DEST + SRC + CF)
adcq %rdi, %rdx #rdx trzyma sume starszych bitow tak jak w poleceniu
movq %rcx, %rax #przenosimy sume mlodszych bitow do rax
ret
```
### Zadanie 6
:::info
Zaimplementuj w asemblerze x86-64 funkcję liczącą wyrażenie ```x * y```. Argumenty i wynik funkcji są 128-bitowymi liczbami całkowitymi bez znaku. Argumenty i wynik są przypisane do tych samych rejestrów co w poprzednim zadaniu. Instrukcja ```mul``` wykonuje co najwyżej mnożenie dwóch 64-bitowych liczb i zwraca 128-bitowy wynik. Wiedząc, że n = n~127...64~ · 2^64^ + n~63...0~, zaprezentuj metodę obliczenia iloczynu, a dopiero potem przetłumacz algorytm na asembler.
UWAGA! Zapoznaj się z dokumentacją instrukcji ```mul``` ze względu na niejawne użycie rejestrów %rax i %rdx
:::
x - na rejestrach %rdi:%rsi
y - na rejestrach %rdx:%rcx
Wynik - na rejestrach %rdx:%rax
Wiemy, że każdą liczbę n 128-bitową można zapisać jako: $$n_{127...64} \cdot 2^{64} + n_{63...0}$$
Wobec tego $x*y = (x_{127...64}*y_{127...64}*2^{128}) + (x_{63...0}*y_{127...64}*2^{64}) + \\(y_{63...0}*x_{127...64}*2^{64}) +(x_{63...0}*y_{63...0})$
Wynik ma być na rejestrach %rdx:%rax (czyli 128 bitach), więc pierwszą część powyższej sumy, możemy pominąć (nie zmieści się).
Rozważamy więc jedynie 3 ostanie składniki powyższej sumy, ponieważ one mieszczą się na 128 bitach:
```
multiply:
movq %rdx,%r8
movq $0,%rdx
movq %rdi,%r9
imulq %rcx,%r9
imulq %rsi,%r8
movq %rsi,%rax
mul %rcx # w przypadku OF wynik będzie w %rdx:%rax,
addq %r9,%rdx
addq %r8,%rdx
```
### Zadanie 7
:::info
Zaimplementuj poniższą funkcję w asemblerze x86-64, przy czym wartości «x» i «y» typu ```uint64_t``` są przekazywane przez rejestry %rdi i %rsi, a wynik zwracany w rejestrze %rax. Po napisaniu rozwiązania uprość je z użyciem instrukcji ```set``` albo ```cmov``` albo ```sbb```.
$$
addu(x,y) =
\begin{cases}
\texttt{ULONG_MAX} & \text{dla } x + y \geq \texttt{ULONG_MAX} \\
x + y & \text{w p.p.}
\end{cases}
$$
:::
Główna idea jest taka, że chcemy sprawdzić czy dodawanie x i y nie wywołało nam overflow.
Używamy warunku below (mniejszy bez znaku) odpowiednio w skoku i cmov. Jeżeli składnik okaże się większy od wyniku to mamy overflow.
Wtedy przypisujemy %rax wartość ULONG_MAX.
wersja ze skokiem warunkowym:
```
addu:
leaq (%rdi, %rsi), %rax
cmp %rdi, %rax
jb label
ret
label:
movq $0xFFFFFFFF, %rax // ULONG_MAX = 0xFFFFFFFF
ret
```
wersja z użyciem set, cmov lub sbb:
```
addu:
leaq (%rdi,%rsi), %rax
cmp %rdi,%rax
cmovb $0xFFFFFFFF, %rax
ret
```
### Zadanie 8
:::info
W wyniku deasemblacji procedury ```long decode(long x, long y)``` otrzymano kod:
```
decode: leaq (%rdi,%rsi), %rax
xorq %rax, %rdi
xorq %rax, %rsi
movq %rdi, %rax
andq %rsi, %rax
shrq $63, %rax
ret
```
Zgodnie z System V ABI dla architektury x86-64, argumenty ```x``` i ```y``` są przekazywane odpowiednio przez rejestry %rdi i %rsi, a wynik zwracany w rejestrze %rax. Napisz funkcję w języku C, która będzie liczyła dokładnie to samo co powyższy kod w asemblerze. Postaraj się, aby była ona jak najbardziej zwięzła.
:::
- long x jest w rejestrze %rdi
- long y jest w rejestrze %rsi
- long z jest w rejestrze %rax
Tutaj funkcja niezwięzła
```c=
long decode(long x, long y)
{
long z = x + y;
x ^= z;
y ^= z;
z = x;
z &= y;
z = ((unsigned long)z) >> 63;
return z;
}
```
Wersja skrócona
```c=
long decode(long x, long y)
{
long z = x + y;
return (((unsigned long)((x^z) & (y^z))) >> 63);
}
```
Funkcja sprawdza czy podczas dodawania liczb ze znakiem doszło do przepełnienia.
### Zadanie 9
:::info
Zapisz w języku C funkcję o sygnaturze ```int puzzle(long x, unsigned n)``` której kod w asemblerze podano niżej. Zakładamy, że parametr ```n``` jest niewiększy niż 64. Przedstaw jednym zdaniem
co robi ta procedura.
```
puzzle: testl %esi, %esi
je .L4
xorl %edx, %edx
xorl %eax, %eax
.L3: movl %edi, %ecx
andl $1, %ecx
addl %ecx, %eax
sarq %rdi
incl %edx
cmpl %edx, %esi
jne .L3
ret
.L4: movl %esi, %eax
ret
```
:::
- %rdi - x
- %edi - n
- %eax - nasz wynik (cnt)
- %edx - zmienna pomocnicza do petli (y)
```c=
int puzzle(long x , unsigned int n)
{
int cnt=0;
for(int y=0;y!=n;y++)
{
cnt+=(x&1);
x>>=1;
}
return cnt;
}
```
Dana procedura liczy ile jest zapalonych bitów wśród n najmniej znaczących bitów liczby x.
# Lista 5 (09.04.2020)
### Zadanie 1
:::info
Zaimplementuj funkcję zdefiniowaną poniżej w asemblerze ```x86-64```. Taka procedura w języku ```C``` miałaby sygnaturę ```long cmp(uint64_t x, uint64_t y)```.
$$
cmp(x,y) =
\begin{cases}
-1 & \text{gdy } x < y \\
\phantom{+}1 & \text{gdy } x > y \\
\phantom{+}0 & \text{gdy } x = y \\
\end{cases}
$$
Wskazówka: Rozwiązanie wzorcowe ma cztery wiersze (bez ```ret```). Użyj instrukcji ```adc```, ```sbb``` i ```neg```.
:::
```
neg D - arithmetic negation (D = -D) (modyfikuje CF)
sbb S, D - substract with borrow (D = D - (S +CF)) (modyfikuje CF)
adc S, D - add with carry (D = D + S + CF) (modyfikuje CF)
```
```
Parametry funkcji:
x -> %rdi
y -> %rsi
Wynik zwracamy w %rax
```
```scala=
cmp:
subq %rsi, %rdi // x - y; CF = 1 dla x < y
sbbq %rax, %rax // rax = -1 dla x < y
// wpp. rax = 0
negq %rdi // x = 0 - (x-y);
// CF = 1 dla x > y lub x < y
adcq %rax, %rax // x < y : rax = -1
// x == y : rax = 0
// x > y : rax = 1
ret
```
### Zadanie 2
:::info
Poniżej zamieszczono kod procedury o sygnaturze «long puzzle2(char *s, char *d)». Wyznacz bloki podstawowe oraz narysuj graf przepływu sterowania. Przetłumacz tę procedurę na język C, a następnie jednym zdaniem powiedz co ona robi.
```=
puzzle2:
movq %rdi, %rax
.L3:
movb (%rax), %r9b
leaq 1(%rax), %r8
movq %rsi, %rdx
.L2:
movb (%rdx), %cl
incq %rdx
testb %cl, %cl
je .L4
cmpb %cl, %r9b
jne .L2
movq %r8, %rax
jmp .L3
.L4:
subq %rdi, %rax
ret
```
:::
Zauważmy, że s i d to są tablice typu char. Nasza procedura iteruje się po tablicy s, sprawdzając po kolei, czy jej elementy należą również do d. Jeśli napotka element z s , który nie należy do d, procedura kończy działanie i zwraca liczbę pierwszych elementów z s należących do d.
Tabelka zmiennych dla poniższego kodu:
|Zmienna |Rejestr |
|-----------|-----------|
|s |%rdi |
|d |%rsi |
|temp_s |%rax |
|temp_d |%rdx |
|s_znak |%r9b |
|d_znak |%cl |
|s_next |%r8 |
Wersja z goto:
```C=
long puzzle2_goto(char* s,char* d)
{
char* temp_s = s; char s_znak,d_znak; char* s_next; char* temp_d; // 1
L3:
s_znak = *temp_s;// 2
s_next = temp_s+1;
temp_d = d;
L2:
d_znak = *temp_d; // 3
temp_d = temp_d+1;
if (d_znak == 0) return temp_s-s; // end - sprawdzamy czy koniec tablicy d
if (d_znak != s_znak) goto L2; //4
else{ // 5
temp_s = s_next;
goto L3;
}
}
```
Dla przypomnienia:
- blok podstawowy - grupa instrukcji zakończona instrukcją skoku
- graf przepływu sterowania - graf skierowany, w którym wierzchołkami są bloki podstawowe - reprezentuje możliwe ścieżki działanie programu
Graf przepływu sterowania (bloki podstawowe oznaczone w komentarzach powyżej):
```graphviz
digraph graf{
6 [label="end"]
1->2
2->3
3->4
3->6
4->5
4->3
5->2
}
```
Kod w C bez goto:
```C=
long puzzle2_normal(char *s,char *d)
{
char* temp_s=s;
char* temp_d;
while (1)
{
temp_d = d;
while (*temp_d != *temp_s)
{
if (*temp_d == 0) return temp_s-s;
temp_d++;
}
temp_s++;
}
}
```
### Zadanie 3
:::info
Poniżej widnieje kod funkcji o sygnaturze «uint32_t puzzle3(uint32_t n, uint32_t d)». Wyznacz bloki podstawowe oraz narysuj graf przepływu sterowania, po czym przetłumacz tę funkcję na język C. Na podstawie ustępu „Mixing C and Assembly Language” strony GNU Assembler Examples3 napisz program, który pomoże Ci powiedzieć co ta funkcja robi.
```=
puzzle3:
movl %edi, %edi
salq $32, %rsi
movl $32, %edx
movl $0x80000000, %ecx
xorl %eax, %eax
.L3:
addq %rdi, %rdi
movq %rdi, %r8
subq %rsi, %r8
js .L2
orl %ecx, %eax
movq %r8, %rdi
.L2:
shrl %ecx
decl %edx
jne .L3
ret
```
:::
```=
.global _start
.global puzzle3
.text
puzzle3:
movl %edi, %edi //A
salq $32, %rsi
movl $32, %edx
movl $0x80000000, %ecx
xorl %eax, %eax
.L3: addq %rdi, %rdi //B
movq %rdi, %r8
subq %rsi, %r8
js .L2
orl %ecx, %eax //C
movq %r8, %rdi
.L2: shrl %ecx //D
decl %edx
jne .L3
ret
_start:
call puzzle3
syscall
```
```graphviz
digraph finite_state_machine {
node [shape=box]
START -> A
A -> B
B -> C
C -> D
D -> STOP
edge [style=dashed]
B -> D
D -> B
}
```
```
Parametry funkcji:
n -> %edi
d -> %esi
Zmienne:
x -> %rsi
m -> %rdi
a -> %edx
b -> %ecx
result -> %eax
```
```C=
uint32_t puzzle3(uint32_t n, uint32_t d)
{
int64_t x = d << 32;
int32_t a = 32;
int64_t b = 0x80000000;
int32_t result = 0;
int64_t m = n;
while(a>=0)
{
m*=2;
if (m - x >= 0)
{
result = b | result;
m -= x;
}
b /= 2;
a -= 1;
}
return result;
}
```
Ten algorytm to restoring division (n przez d).
### Zadanie 4
:::info
Poniżej zamieszczono kod rekurencyjnej procedury o sygnaturze «int puzzle4(long *a, long v, uint64_t s, uint64_t e)». Wyznacz bloki podstawowe oraz narysuj graf przepływu sterowania. Przetłumacz tę procedurę na język C, a następnie jednym zdaniem powiedz co ona robi.
```=
puzzle4:
movq %rcx, %rax
subq %rdx, %rax
shrq %rax
addq %rdx, %rax
cmpq %rdx, %rcx
jb .L5
movq (%rdi,%rax,8), %r8
cmpq %rsi, %r8
je .L10
cmpq %rsi, %r8
jg .L11
leaq 1(%rax), %rdx
call puzzle4
.L10:
ret
.L11:
leaq -1(%rax), %rcx
call puzzle4
ret
.L5:
movl $-1, %eax
ret
```
Wskazówka: Z reguły procedurę «puzzle4» woła się następująco: «i = puzzle4(a, v, 0, n - 1)»
:::
```
puzzle4:
movq %rcx, %rax //1
subq %rdx, %rax
shrq %rax
addq %rdx, %rax
cmpq %rdx, %rcx
jb .L5
movq (%rdi,%rax,8), %r8 // 2
cmpq %rsi, %r8
je .L10
cmpq %rsi, %r8 // 3
jg .L11
leaq 1(%rax), %rdx // 4
call puzzle4
.L10: ret // 5
.L11: leaq -1(%rax), %rcx // 6
call puzzle4
ret
.L5: movl $-1, %eax // 7
ret
```
```graphviz
digraph finite_state_machine {
START -> 1
1 -> 2
2 -> 3
3 -> 4
4 -> 5
5 -> STOP
6 -> STOP
7 -> STOP
1 -> 7
2 -> 5
3 -> 6
}
```
puzzle4: BinarySearch
s (początek tablicy)- rdx
e (koniec tablicy)- rcx
a (tablica)- rdi
v (szukana wartość)- rsi
```c=
int puzzle4(long *a,long v, uint64_t s, uint64_t e)
{
if (e >= s) {
int mid = s + (e - s) / 2;
if (a[mid] == v)
return mid;
if (a[mid] > v)
return puzzle4(a, v, s, mid - 1);
return puzzle4(a, v, mid + 1, e);
}
return -1;
}
```
### Zadanie 5
:::info
Poniższy kod w asemblerze otrzymano w wyniku deasemblacji funkcji zadeklarowanej jako «long switch_prob(long x, long n)». Zapisz w języku C kod odpowiadający tej funkcji.
```
400590 <switch_prob>:
400590: 48 83 subq $0x3c,%rsi
400594: 48 83 fe 05 cmpq $0x5,%rsi
400598: 77 29 ja *0x4005c3
40059a: ff 24 f5 f8 06 40 00 jmpq *0x4006f8(,%rsi,8)
4005a1: 48 8d 04 fd 00 00 00 00 lea 0x0(,%rdi,8),%rax
4005a9: c3 retq
4005aa: 48 89 f8 movq %rdi,%rax
4005ad: 48 c1 f8 03 sarq $0x3,%rax
4005b1: c3 retq
4005b2: 48 89 f8 movq %rdi,%rax
4005b5: 48 c1 e0 04 shlq $0x4,%rax
4005b9: 48 29 f8 subq %rdi,%rax
4005bc: 48 89 c7 movq %rax,%rdi
4005bf: 48 0f af ff imulq %rdi,%rdi
4005c3: 48 8d 47 4b leaq 0x4b(%rdi),%rax
4005c7: c3 retq
```
Zrzut pamięci przechowującej tablicę skoków:
```
(gdb) x/6gx 0x4006f8
0x4006f8: 0x4005a1
0x400700: 0x4005a1
0x400708: 0x4005b2
0x400710: 0x4005c3
0x400718: 0x4005aa
0x400720: 0x4005bf
```
:::
```c=
long switch_prob(long x, long n){
n-=0x3c;
switch(n){
case 0:
case 1:
return 8*x;
case 4:
return x<<3;
case 2:
x*=15;
case 5:
x*=x;
case 3:
default:
return x+0x4b;
}
}
```
### Zadanie 6
:::info
Poniżej zamieszczono kod procedury o sygnaturze «struct T puzzle8(long *a, long n)». Na jego podstawie podaj definicję typu «struct T». Przetłumacz tę procedurę na język C, po czym jednym zdaniem powiedz co ona robi. Gdyby sygnatura procedury nie była wcześniej znana to jaką należałoby wywnioskować z poniższego kodu?
```=
puzzle8:
movq %rdx, %r11
xorl %r10d, %r10d
xorl %eax, %eax
movq $LONG_MIN, %r8
movq $LONG_MAX, %r9
.L2:
cmpq %r11, %r10
jge .L5
movq (%rsi,%r10,8), %rcx
cmpq %rcx, %r9
cmovg %rcx, %r9
cmpq %rcx, %r8
cmovl %rcx, %r8
addq %rcx, %rax
incq %r10
jmp .L2
.L5:
cqto
movq %r9, (%rdi)
idivq %r11
movq %r8, 8(%rdi)
movq %rax, 16(%rdi)
movq %rdi, %rax
ret
```
Wskazówka: Zauważ, że wynik procedury nie mieści się w rejestrach %rax i %rdx, zatem zostanie umieszczony w pamięci.
:::
```
Argumenty funkcji:
struct *T -> %rdi (wskaźnik na miejsce na strukturę)
long *a -> %rsi (wskaźnik na tablicę)
long n -> %rdx (długość tablicy)
Zmienne:
int i -> %r10d
long sum -> %rax
long max -> %r8
long min -> %r9
long value -> &rcx
long average -> %r11
struct *T result -> %rax (zwracany wskaźnik na miejsce w pamięci, w którym
zapisaliśmy wynik)
```
Warto zauważyć, że sum zostaje zapisana do %rax.
Dzieje się tak, gdyż kilka linii później wywołujemy instrukcję idiv, która
aby wykonać dzielenie korzysta właśnie z tego rejestru.
```
cqto - instrukcja rozszerza %rax do %rdx:%rax (tak, że wartość
z %rax zachowuje znak)
idivq S - dzielenie ze znakiem %rdx : %rax przez S, gdzie
%rdx - wynik dzielenia całkowitego
%rax - reszta z dzielenia
```
Widzimy również, że wyniki z naszej funkcji (max, min, sum) zapisujemy
pod adresem przechowanym w %rdi przesuniętym o odpowiednią ilość bajtów,
tak, by adres odpowiadał konkretnemu polu w strukturze. Nie przekazaliśmy
tego adresu jawnie jako parametr w funkcji, ale dostaliśmy go wraz z jej wywołaniem.
(Chcąc wywołać tą funkcję w assemblerze musielibyśmy najpierw zadbać o to,
by dostała wskaźnik na miejsce w pamięci w której ma zapisać utworzoną strukturę.)
```c=
struct T
{
long min;
long max;
long average;
}
struct T puzzle8(long *a, long n)
{
long sum = 0; //4
long max = LONG_MIN; //5 (r8)
long min = LONG_MAX; //6 (r9)
for(int i = 0; i < n; i++) //3, 7, 8, 16
{
long value = a[i]; //10
if(min > value) //11 (r9 > val)
min = value; //12
if(max < value) //13 (r8 < val)
max = value; //14
sum += value; //15
} //17
//19 cqto - przygotowuje rdx pod dzielenie
long average = sum/n; //2, 21
struct T result;
result.min = min; //20
result.max = max; //22
result.average = average; //23
return result; //25
}
```
Wnioskowanie dotyczące sygnatury: linie 20-22 wskazują, że zapisujemy do miejsc wskazanych przez %rdi i offset, a zwracamy rdi. Argumentami funkcji jest wartosc n (linie 2 i 19) i adres wskazany przez a (linia 9).
Możliwe by było wywnioskowanie sygnatury:
```
void* puzzle8(struct* T result, long *a, long n )
```
gdzie wynikiem jest result.
Zatem chociaż w kodzie "zwracamy strukturę" to w rzeczywistości, ponieważ nie mieści się na rejestrze %rdx:%rax, zapisujemy ją w pamięci i zwracamy wskaźnik na nią.
Jeśli chodzi o działanie funkcji to przyjmuje ona tablicę ```a``` typu ```long``` oraz jej długość ```n```, zaś zwraca strukturę przechowującą informacje o liczbie najmniejszej, największej i średniej wszystkich elementów.
|Dla poniższych zadań należy podać kompletny algorytm, zatem dozwolona jest cała składnia języka C bez ograniczeń z nagłówka listy zadań. Jednakże należy używać wyłącznie operacji na typie «int32_t» lub «uint32_t».|
|-|
### Zadanie 7 z listy 3
:::info
Uzupełnij ciało poniższej procedury konwertującej wartość całkowitoliczbową do binarnej reprezentacji liczby typu «float». Wynik należy zaokrąglić do najbliższej liczby parzystej – w tym celuwyznacz wartość bitów guard, round i sticky. Do wyznaczenia pozycji wiodącej jedynki można użyć funkcji «__builtin_clz», tj. instrukcji wbudowanej1 w kompilator gcc.
```cpp
int32_t int2float(int32_t i) {
/* TODO */
}
```
:::
```c=
int32_t int2float(int32_t i) {
/*
przykład: int32_t = 00000000000000000000000101011101 =
= 2^8 + 2^6 + 2^4 + 2^3 + 2^2 + 2^0 = 2^8 (1 + 2^-2 + 2^-4 + 2^-5 + 2^-6 + 2^-8) =
= 2^8 * 1.01011101
czyli:
e = 8 + 127 (trzeba uwzględnić bias)
m = 1.01011101
s = 0
kolejny przykład -127 = -1 * (2^6 + 2^5 + 2^4 + 2^3 + 2^2 + 2^1 + 2^0) =
= -1 * 1.111111 * 2^6 (czyli przesunięcie bitowe o 6 w lewo)
*/
/* znak - sign:
-1 jeśli znak był ujemny */
int32_t s = i >> 31;
/* jesli i jest ujemna to otrzymaliśmy już znak,
a chcemy znaleźć wiodącą jedynkę, która nie oznacza znaku */
if (s == -1) {
i = -i; // usuwamy jedynkę z początkowego bitu
s = 1;
}
/* pozycja:
__builtin_clz zwraca liczbę zer wiodących
więc mozemy policzyć pozycje wiodącej jedynki (od prawej)
odejmując od 32 wynik __builtin_clz(i) */
int32_t p = 32 - __builtin_clz(i);
/* wykładnik - exponent:
po odjęciu 1 (bo chcemy numerować bity od 0, by i-ty bit oznaczał 2^i w sumie)
i dodaniu bias (obliczając wykładnik trzeba go odejmować)
mamy nasz wykładnik */
int32_t bias = 127;
int32_t e = p - 1 + bias;
/* tworzymy maskę, aby wyeliminować wiodącą jedynkę, aby mieć tylko mantysę
więc przesuwamy 1 na pozycję p i wtedy odejmujemy 1, aby na prawo od p były same 1*/
int32_t mask = (1<<(p-1))-1;
/* eliminujemy wiodącą jedynkę */
i &= mask;
/* guard, round i sticky
potrzebne nam będą do zaokrąglenia round-to-even */
int32_t
guard = 0,
round = 0,
sticky = 0;
/* zaokrąglamy, gdy pozycja p jest większa niż 23,
ponieważ na prawo od niej znajduje się wtedy za dużo bitów na mantysę */
if (p > 24) {
/* ostatni bit mantysy jest na pozycji 23 na prawo od p ( p - 23 )
więc jeśli chcemy dostać się do tego bitu to przesuniemy o (p - 23) - 1
bo aby dostać się do bitu k-tego na prawo, przesuwamy o k-1 w prawo */
guard = ( i >> (p - 23 - 1) ) & 1;
/* bit round jest o 1 w prawo od bitu guard */
round = ( i >> (p - 23 - 2) ) & 1;
/* sticky bit to OR bitów na prawo od round
więc 1 przesuwamy na pozycję round i odejmujemy 1
więc aby wziąć OR, wystarczy sprawdzić czy liczba jest większa od 0*/
sticky = ( i & ( ( 1 << (p - 23 - 2) ) - 1 ) ) > 0;
}
/* mantysa - fraction:
chcemy, aby miejsce wiodącej jedynki znajdowało się na 24 pozycji od prawej,
aby na najmniej znaczących 23 bitach znajdowała się mantysa
musimy dosunąć
w lewo o tyle ile brakuje nam do 24 pozycji (jeśli p < 24)
w prawo o tyle ile jesteśmy za daleko do 24 pozycji (jeśli p >= 24) */
int32_t f =
( p < 24 ? (i << (24 - p)) : (i >> (p - 24)) ) +
((guard & round) | (round & sticky)) ;
return (s << 31) + (e << 23) + f ;
}
```
### Zadanie 8 z listy 3
:::info
Uzupełnij ciało poniższej procedury konwertującej binarną reprezentację liczby typu «float» umieszczoną w zmiennej «f» do wartości typu «int32_t». Wynik należy zaokrąglić w kierunku zera. Jeśli konwersja spowoduje nadmiar lub f ma wartość NaN, zwróć wartość 0x80000000 (tj. MIN_INT). Kod procedury zaczyna się wyodrębnieniem poszczególnych elementów liczby zmiennopozycyjnej:
```cpp
int32_t float2int(int32_t f) {
int32_t s = f >> 31; /* -1 jeśli znak był ujemny */
int32_t e = (f >> 23 & 255) - 127; /* wykładnik po odjęciu bias */
uint32_t m = f << 8 | 0x80000000; /* mantysa 1.xxx... dosunięta do lewej */
/* TODO */
}
```
Wskazówka: Wzorcówka ma dodatkowe cztery linie kodu i używa jednej instrukcji warunkowej!
:::
```cpp
int32_t float2int(int32_t f)
{
int32_t s = (f >> 31)|1; // -1 jeśli znak był ujemny
int32_t e = (f >> 23 & 255) - 127; // wykładnik po odjęciu bias
uint32_t m = f << 8 | 0x80000000; // mantysa 1.xxx... dosunięta do lewej
if(e > 30)
return 0x80000000; //dla Nan, dużych liczb lub MIN_INT
if(e < 0)
return 0; // dla małych liczb
// s*=(e>=0);
return s * (m >> (31-e));
}
```
# Lista 6 (16.04.2020)
### Zadanie 1
:::info
Poniższy wydruk otrzymano w wyniku deasemblacji rekurencyjnej procedury zadeklarowanej następująco: «long puzzle(long n, long *p)». Zapisz w języku C kod odpowiadający tej procedurze. Następnie opisz zawartość jej rekordu aktywacji (ang. stack frame). Wskaż rejestry zapisane przez funkcję wołaną (ang. callee-saved registers), zmienne lokalne i adres powrotu.
```=
puzzle:
push %rbp
xorl %eax, %eax
mov %rsi, %rbp
push %rbx
mov %rdi, %rbx
sub $24, %rsp
test %rdi, %rdi
jle .L1
lea 8(%rsp), %rsi
lea (%rdi,%rdi), %rdi
call puzzle
add 8(%rsp), %rax
add %rax, %rbx
.L1:
mov %rbx, (%rbp)
add $24, %rsp
pop %rbx
pop %rbp
ret
```
Uwaga! Wskaźnik wierzchołka stosu w momencie wołania procedury musi być wyrównany do adresu podzielnego przez 16.
:::
```c=
long puzzle(long n,long* p)
{
long res=0;//%rax
if(n>0)
{
res=puzzle(n*2,p);
res+=*p;
n+=res;
}
*p=n;
return res;
}
```
| rekord aktywacji |
| -------------------------------------------------- |
| %rbp |
| %rbx |
| - |
| na to miejsce wskazuje %rsi gdy wywolujemy funkcje |
| - |
| call puzzle |
rejestry zapisane przez funkcje wołaną: %rbp, %rbx
zmienne lokalne = res -> %rax
adres powrotu jest w %rbp przy wywołaniu funkcji odkładamy go na stos,
przy powrocie jest zdejmowany (instrukcje push i pop)
### Zadanie 2
:::info
Skompiluj poniższy kod źródłowy kompilatorem gcc z opcjami «-Og -fomit-frame-pointer» i wykonaj deasemblację jednostki translacji przy użyciu programu «objdump». Wytłumacz co robi procedura alloca(3), a następnie wskaż w kodzie maszynowym instrukcje realizujące przydział i zwalnianie pamięci.
```cpp=
#include <alloca.h>
long aframe(long n, long idx, long *q) {
long i;
long **p = alloca(n * sizeof(long *));
p[n-1] = &i;
for (i = 0; i < n; i++)
p[i] = q;
return *p[idx];
}
```
Wskazówka: Przeczytaj również co robi instrukcja «leave».
:::
```c=
000000000000066a <aframe>:
66a: 55 push %rbp
66b: 48 89 e5 mov %rsp,%rbp
//przydział pamięci na stosie - początek
66e: 48 83 ec 10 sub $0x10,%rsp
672: 64 48 8b 04 25 28 00 mov %fs:0x28,%rax
679: 00 00
67b: 48 89 45 f8 mov %rax,-0x8(%rbp)
//w rax obliczamy ile pamięci potrzebujemy na n*long
67f: 31 c0 xor %eax,%eax
681: 4c 8d 0c fd 00 00 00 lea 0x0(,%rdi,8),%r9
688: 00
689: 49 8d 41 1e lea 0x1e(%r9),%rax
68d: 48 83 e0 f0 and $0xfffffffffffffff0,%rax
691: 48 29 c4 sub %rax,%rsp
//przydział pamięci na stosie - koniec
694: 4c 8d 44 24 0f lea 0xf(%rsp),%r8
699: 49 83 e0 f0 and $0xfffffffffffffff0,%r8
69d: 4c 89 c1 mov %r8,%rcx
6a0: 48 8d 45 f0 lea -0x10(%rbp),%rax
6a4: 4b 89 44 08 f8 mov %rax,-0x8(%r8,%r9,1)
6a9: 48 c7 45 f0 00 00 00 movq $0x0,-0x10(%rbp)
6b0: 00
6b1: eb 09 jmp 6bc <aframe+0x52>
6b3: 48 89 14 c1 mov %rdx,(%rcx,%rax,8)
6b7: 48 83 45 f0 01 addq $0x1,-0x10(%rbp)
6bc: 48 8b 45 f0 mov -0x10(%rbp),%rax
6c0: 48 39 f8 cmp %rdi,%rax
6c3: 7c ee jl 6b3 <aframe+0x49>
6c5: 49 8b 04 f0 mov (%r8,%rsi,8),%rax
6c9: 48 8b 00 mov (%rax),%rax
6cc: 48 8b 75 f8 mov -0x8(%rbp),%rsi
6d0: 64 48 33 34 25 28 00 xor %fs:0x28,%rsi
6d7: 00 00
6d9: 75 02 jne 6dd <aframe+0x73>
//zwolnienie pamięci na stosie
6db: c9 leaveq
6dc: c3 retq
6dd: e8 5e fe ff ff callq 540 <__stack_chk_fail@plt>
```
alloca - funkcja alokująca pamięć, która jest automatycznie zwalniana, kiedy funkcja, która wywołała alloca wraca do swojego callera(wywoływacza?).
leave zamyka ramkę. Jest równoważne skopiowaniu %rbp do %rsp, a następnie przywróceniu starej wartości %rbp ze stosu.
### Zadanie 3
:::info
Poniżej widnieje kod procedury o sygnaturze «long puzzle5(void)». Podaj rozmiar i składowe rekordu aktywacji procedury «puzzle5». Procedura «readlong», która wczytuje ze standardowego wejścia liczbę całkowitą, została zdefiniowana w innej jednostce translacji. Jaka jest jej sygnatura? Przetłumacz procedurę «puzzle5» na język C i wytłumacz jednym zdaniem co ona robi.
```=
puzzle5:
subq $24, %rsp
movq %rsp, %rdi
call readlong
leaq 8(%rsp), %rdi
call readlong
movq (%rsp), %rax
cqto
idivq 8(%rsp)
xorl %eax, %eax
testq %rdx, %rdx
sete %al
addq $24, %rsp
ret
```
:::
```c=
void readlong(long* a){
scanf("%l", &a);
}
int puzzle5() {
long a;
readlong(&a);
long b;
readlong(&b);
if(a%b == 0)
return 0;
return 1;
}
```
procedura puzzle5 mówi nam czy występuje reszta z dzielenia dwóch long'ów wczytanych w trakcie wykonania procedury (~ (b|a) )
rozmiar rekordu aktywacji - 32 bajty
trzymamy w nim zmienne a i b
### Zadanie 4
:::info
Procedurę ze zmienną liczbą parametrów używającą pliku nagłówkowego ```stdarg.h``` skompilowano z opcjami «-Og -mno-sse». Po jej deasemblacji otrzymano następujący wydruk. Co robi ta procedura i jaka jest jej sygnatura? Jakie dane są przechowywane w rekordzie aktywacji tej procedury? Prezentację zacznij od przedstawienia definicji struktury «va_list».
```=
puzzle7:
movq %rsi, -40(%rsp)
movq %rdx, -32(%rsp)
movq %rcx, -24(%rsp)
movq %r8, -16(%rsp)
movq %r9, -8(%rsp)
movl $8, -72(%rsp)
leaq 8(%rsp), %rax
movq %rax, -64(%rsp)
leaq -48(%rsp), %rax
movq %rax, -56(%rsp)
movl $0, %eax
jmp .L2
.L3:
movq -64(%rsp), %rdx
leaq 8(%rdx), %rcx
movq %rcx, -64(%rsp)
.L4:
addq (%rdx), %rax
.L2:
subq $1, %rdi
js .L6
cmpl $47, -72(%rsp)
ja .L3
movl -72(%rsp), %edx
addq -56(%rsp), %rdx
addl $8, -72(%rsp)
jmp .L4
.L6:
ret
```
Wskazówka: Przeczytaj rozdział §3.5.7 dokumentu opisującego ABI dostępnego na stronie przedmiotu.
:::
Definicja struktury va_list:
```C=
typedef struct{
unsigned int gp_offset; /* "odległość" od reg_save_area
do kolejnego argumentu przekazanego przez zwykły rejestr*/
unsigned int fp_offset; /* "odległość" od reg_save_area
do kolejnego rejestru typu %xmm0...15
(rejestry dla liczb zmiennoprzecinkowych )*/
void *overflow_arg_area;/* używany do pobierania argumentów
przekazanych przez stos*/
void *reg_save_area; /* początek miejsca, gdzie mamy argumenty
przekazane przez rejestry */
}
```
W naszej procedurze:
- gp_offset: -72(%rsp)
- overflow_arg_area: 8(%rsp)
- reg_save_area: -48(%rsp)
- fp_offset: kompilowaliśmy z flagą -mno-sse, dzięki czemu
wszystkie argumenty przekazane zostały przez rejestry ogólnego przeznaczenia albo stos. W tej procedurze fp_offset nie jest wyodrębniony.
--------------------------
```=
puzzle7:
movq %rsi, -40(%rsp)
movq %rdx, -32(%rsp)
movq %rcx, -24(%rsp)
movq %r8, -16(%rsp)
movq %r9, -8(%rsp)
movl $8, -72(%rsp)
leaq 8(%rsp), %rax
movq %rax, -64(%rsp)
leaq -48(%rsp), %rax
movq %rax, -56(%rsp) # Koniec przygotowania stosu
movl $0, %eax
jmp .L2
.L3:
movq -64(%rsp), %rdx # Czytamy kolejny argument przekazany
leaq 8(%rdx), %rcx # przez stos
movq %rcx, -64(%rsp)
.L4:
addq (%rdx), %rax # w %rdx mamy obliczony adres kolejnego
.L2: # argumentu funkcji. Dodajemy go do %rax
subq $1, %rdi
js .L6
cmpl $47, -72(%rsp) # Sprawdzamy, czy jeszcze możemy
ja .L3 # korzystać z argumentów z rejestrów
movl -72(%rsp), %edx # Czytamy kolejny argument przekazany przez rejestr
addq -56(%rsp), %rdx
addl $8, -72(%rsp)
jmp .L4
.L6:
ret
```
Stan stosu po wykonaniu początkowych instrukcji (lin. 11):
| ADRES | ZAWARTOŚĆ |
| --------- | -------------------------------------- |
| 32(%rsp) | ... |
| 24(%rsp) | arg3 |
| 16(%rsp) | arg2 |
| 8(%rsp) | arg1 |
| %rsp | |
| -8(%rsp) | r9 |
| -16(%rsp) | r8 |
| -24(%rsp) | rcx |
| -32(%rsp) | rdx |
| -40(%rsp) | rsi |
| -48(%rsp) | |
| -56(%rsp) | reg_save_area, początkowo: -48(%rsp) |
| -64(%rsp) | overflow_arg_area, pocz: 8(%rsp) |
| -72(%rsp) | gp_offset, pocz: 8 |
| -80(%rsp) | ... |
- rsi,rdx...r9 - argumenty funkcji przekazane przez rejestry
- arg1,arg2... - argumenty funkcji przekazane przez stos
----------------------
W naszej procedurze czytamy kolejne argumenty funkcji (przekazane przez rejestr albo stos) i dodajemy do %rax, przy czym pierwszy argument funkcji (%rdi) to liczba składników (kolejnych argumentów funkcji). Nasza funkcja ma więc sygnaturę:
```C=
long add_args(long n, ...)
```
# Lista 7 (23.04.2020)
### Zadanie 1
:::info
Przeczytaj poniższy kod w języku C i odpowiadający mu kod w asemblerze, a następnie wywnioskuj jakie są wartości stałych «A» i «B».
```cpp=
typedef struct {
int x[A][B];
long y;
} str1;
typedef struct {
char array[B];
int t;
short s[A];
long u;
} str2;
void set_val(str1 *p, str2 *q) {
long v1 = q->t;
long v2 = q->u;
p->y = v1 + v2;
}
```
```=
set_val:
movslq 8(%rsi),%rax
addq 32(%rsi),%rax
movq %rax,184(%rdi)
ret
```
:::
1. long v1=q->t == *q+8
2. long v2=q->u == *q+32
3. p->y == rdi+184
:::info
```cpp=
typedef struct {
char array[B]; // 8 //
int t; // 32
short s[A]; //
long u;
} str2;
```
Więc aby przejść do int t musimy się przesunąc o 8 bajtów,czyli char array[B] wynosi maksymalnie 8 bajtów.
Minimalny rozmiar char array[B] to 5,gdyż inaczej int mogłby ustawić się na wcześniejszej pozycji równej 4.
Char jest 1 bajtowy, więc 5<=B<=8.
Aby przejść do long u to przesuwamy się o 32 bajty.
32- 8(char array)- 4 (int t)=20
Więc short s[A] ma maksymalnie 20 bajtów, zaś minimalnie 13, gdyż 32-8 (tyle ile long mogłby się przesunąć) +1 (aby przesuniecie nie było możliwe)- 8 -4=13
Short ma 2 bity, więc 7<=A<=10
Maksymalna wielkość int x[A][B] wynosi 184 bajtów.
Minimalna to 184-8(wielkość longa)+1=177.
Ilość komórek to 177/4=45(zaokrąglone w góre) < x <184/4=46
A * B=45 lub A * B=46
5<=B<=8 7<=A<=10
Z obliczeń wynika,że A=5 a B=9.
:::
### Zadanie 2
:::info
Przeczytaj poniższy kod w języku C i odpowiadający mu kod w asemblerze, a następnie wywnioskuj jakie są wartości stałych «R», «S» i «T».
```cpp=
long A[R][S][T];
long store_elem(long i, long j, long k, long *dest)
{
*dest = A[i][j][k];
return sizeof(A);
}
```
```=
store_elem:
leaq (%rsi,%rsi,2),%rax //rax = 3j
leaq (%rsi,%rax,4),%rax //rax = 13j
movq %rdi,%rsi //rsi = i
salq $6,%rsi //rsi = i<< 6 = 64i
addq %rsi,%rdi //rdi = i+ 64i = 65i
addq %rax,%rdi //rdi = 13j + 65i
addq %rdi,%rdx //rdx = 13j + 65i + k
movq A(,%rdx,8),%rax //rax = A + 8(65i + 13j + k)
movq %rax,(%rcx) //*dest = A[i][j][k]
movq $3640,%rax //sizeof(A) = 8 * R * S * T = 3640
ret
```
:::
Szukamy wartości liczb R, S T. Widzimy, że sizeof(A) = 3640 oraz jest to tablica typu long, zatem mozemy wyliczyć, że
R * S * T = 3640/8 = 455.
Z wykładu wiemy, że chcać uzyskać element tablicy A[R][S][T] oznaczony A[i][j][k] musimy przesunąć wskaźnik A na miejsce
A + 8 * i * S * T + 8 * j * T + 8 * k = A + 8(i * S * T + j * T + k).
W kodzie chcemy odnieść się do pozycji A + 8(65i+ 13j + k), zatem widzimy, że T = 13,
a S = 65/13 = 5. Z naszego iloczynu R * S * T możemy wyliczyć, że R = 455/65 = 7.
Zatem:
T = 13
S = 5
R = 7
### Zadanie 3
:::info
Przeczytaj poniższy kod w języku C i odpowiadający mu kod w asemblerze, a następnie wywnioskuj jaka jest wartość stałej «CNT» i jak wygląda definicja struktury «a_struct».
```cpp=
typedef struct {
int first;
a_struct a[CNT];
int last;
} b_struct;
void test (long i, b_struct *bp) {
int n = bp->first + bp->last;
a_struct *ap = &bp->a[i];
ap->x[ap->idx] = n;
}
```
```=
test:
movl 0x120(%rsi),%ecx //0x120 = 288B, przesunięcie o tyle wskaźnika
addl (%rsi),%ecx
leaq (%rdi,%rdi,4),%rax
leaq (%rsi,%rax,8),%rax //obliczamy rozmiar struktury - 8*5 = 40B
movq 0x8(%rax),%rdx
movslq %ecx,%rcx
movq %rcx,0x10(%rax,%rdx,8)
retq
```
:::
```cpp=
typedef struct A
{
long idx;
long x[4];
}A;
```
CNT = 7
Przesuwamy wskaźnik o 288B, 8B rezerwujemy na int, więc zosteje nam 280B na struktury. Następnie chcąc dostać się do struktury musimy pomnożyć liczbę przez 40(obliczona przy pomocy poleceń leaq), stąd A posiada 40B, posiada też liczbę i tablicę - co wnioskujemy z funkcji void test w C, z których liczba jest na początku. Tablica jest tablicą longów, bo nasze n rozszerzamy na 64 bit. Long ma 64 bit(operujemy na rejestrach 64 bit), wieć jeśli chcemy mieć ich tablice będzie miała rozmiar 5 (40/8), jednak potrzbujemy miejsce na idx, więc ma rozmiar 4.
### Zadanie 4
:::info
Przeczytaj definicję unii «elem» i wyznacz jej rozmiar w bajtach. Następnie przepisz procedurę «proc» na kod w języku C.
```cpp=
union elem {
struct {
long *p;
long y;
} e1;
struct {
long x;
union elem *next;
} e2;
};
```
```=
proc:
movq 8(%rdi),%rax
movq (%rax),%rdx
movq (%rdx),%rdx
subq 8(%rax),%rdx
movq %rdx,(%rdi)
ret
```
:::
Unia w C ma zajmuje tyle pamięci co jej największy element.
Tutaj elementami są 2 structy. Każdy z tych structów zajmuje 16 bajtów zatem cała unia
również tyle zajmuje.
najpierw zapiszę wszystkie operacje bez interpretowania których structów dotyczą.
```cpp=
elem* proc(elem* now)
{
*now = *(*(*(now+8))) - *(*(now+8)+8);
return now->next;
}
```
teraz kod już po zinterpretowaniu
```cpp=
elem* proc(elem* now)
{
now->e2.x = *(now->e2.next->e1.p) - now->e2.next->e1.y;
return now->next;
}
```
wyjaśnienie:
zacznijmy od interpretacji tej części ```*(*(*(now+8)))```
```
(*(now+8))
```
to może być ```now->e2.next``` lub ```now->e1.y``` jednak w następnym kroku
chcę wykonać na tym elemencie dereferencje więc musi to być wskaźnik, zatem jest to ```now->e2.next```
```
(*(*(now+8))
```
jest to dereferencja wskaźnika na elem a wskaźnik na union elem jest jednocześnie wskaźnikiem na 1 element
tego uniona zatem może być to ```now->e2.next->e1.p``` lub ```now->e2.next->e2.x```. Znowu kolejnym
krokiem będzie dereferencja zatem znowu musi być to wskaźnik zatem mamy pewność że jest to
```now->e2.next->e1.p```
```
(*(*(*(now+8)))
```
dokonujemy dereferencji na wskaźniku na long zatem jest to ```*(now->e2.next->e1.p)```.
dane wyrażenie ma typ long. Można w takim razie wywnioskować już na tym etapie że to co chcemy
odjąć powinno mieć również typ long a także to do czego chcemy przypisać wartość różnicy również
powinno mieć typ long. Z tego widzimy od razy że ```*now``` ma być typu long zatem będzie to ```now->e2.x```
w takim razie intepretacja tej części ```*(*(now+8)+8)```
tak jak we wcześniejszym przykładzie na ```*(now+8)``` będę chciał dokonać w następnym kroku dereferencje
zatem musi być to wskaźnik więc będzie to ```now->e2.next```
wiemy z poprzedniej części rozwiązania że ```*(*(now+8)+8)``` powinno być longiem zatem będzie to
```now->e2.next->e1.y```
### Zadanie 5
:::info
Przeczytaj definicje struktur «SA» i «SB», po czym przeanalizuj kod procedur o sygnaturach «SB eval(SA s)» i «long wrap(long x, long y, long z)». Nastepnie zapisz w języku C kod odpowiadający procedurom «eval» i «wrap». Narysuj diagram przedstawiający zawartość rekordu aktywacji procedury «wrap» w momencie wywołania funkcji «eval».
```cpp=
typedef struct A {
long u[2];
long *v;
} SA;
typedef struct B {
long p[2];
long q;
} SB;
```
```=
eval:
movq %rdi, %rax
movq 16(%rsp), %rcx // bierzemy y ze stosu
movq 24(%rsp), %rdx // bierzemy &z ze stosu
movq (%rdx), %rsi // dokonujemy dereferencji
movq %rcx, %rdx
imulq %rsi, %rdx // y * z
movq %rdx, (%rdi) // kładziemy wynik na stosie
movq 8(%rsp), %rdx // bierzemy x ze stosu
movq %rdx, %rdi
subq %rsi, %rdi // x - z
movq %rdi, 8(%rax) // kładziemy wynik na stosie
subq %rcx, %rdx // x - y
movq %rdx, 16(%rax) // wynik kładziemy na stosie
ret
wrap:
subq $72, %rsp // szykujemy miejsce na stosie
movq %rdx, (%rsp) // kładziemy 'z' na stos
movq %rsp, %rdx
leaq 8(%rsp), %rax
pushq %rdx // kładziemy '&z' na stos
pushq %rsi // kładziemy 'y' na stos
pushq %rdi // kładziemy 'x' na stos
movq %rax, %rdi // jako argument dajemy adres "pod" zmiennymi na stosie
call eval
movq 40(%rsp), %rax // bierzemy (x - z)
addq 32(%rsp), %rax // dodajemy do niego (y * z)
imulq 48(%rsp), %rax // wynik mnożymy przez (x - y)
addq $96, %rsp // zwalniamy miejsce w stosie
ret
```
:::
W momencie wywołania eval
|------------------------|
| 96 | |
| 88 | |
| 80 | |
| 72 | |
| 64 | |
| 56 | |
| 48 | |
| 40 | |%rax, %rdi
| 32 | z |
| 24 | &z |v
| 16 | y |u[1]
| 8 | x |u[0]
| 0 |returnAdress |%rsp
Po zakończeniu eval
|------------------------|
| 96 | |
| 88 | |
| 80 | |
| 72 | |
| 64 | |
| 56 | x - y |q
| 48 | x - z |p[1]
| 40 | y * z |p[0]
| 32 | z |
| 24 | &z |
| 16 | y |
| 8 | x |%rsp
```c=
SB eval(SA sa)
{
SB sb;
sb.p[0] = sa.u[1] * (*sa.v);
sb.p[1] = sa.u[0] - (*sa.v);
sb.q = sa.u[0] - sa.u[1];
return sb;
}
long wrap(long x,long y,long z)
{
SA sa;
sa.v = &z;
sa.u[0] = x;
sa.u[1] = y;
SB sb = eval(sa);
return (sb.p[1] + sb.p[0]) * sb.q;
}
```
### Zadanie 6
:::info
Poniżej widniej kod procedury o sygnaturze «float puzzle6(struct P *, float)». Wyznacz definicję typu «struct P». Przetłumacz tę procedurę na język C i wyjaśnij jednym zdaniem co robi.
```=
puzzle6:
movq (%rdi), %rdx
leaq 8(%rdi), %rcx
xorl %eax, %eax
vxorps %xmm1, %xmm1, %xmm1
vmovss .LC1(%rip), %xmm2
.L2:
cmpq %rdx, %rax
jge .L5
vfmadd231ss (%rcx,%rax,4), %xmm2, %xmm1
incq %rax
vmulss %xmm0, %xmm2, %xmm2
jmp .L2
.L5:
vmovaps %xmm1, %xmm0
ret
.LC1: .long 0x3f800000
```
:::
```c=
struct P{
long n;
float a[];
}
float puzzle6(struct P * p , float q)
{
int n = p->n;//2
float *a = p.a;//3
float sum = 0;//5
float pow = 1.0;//6 (0x3f800000)
for(long i = 0; i<=n; i++)//4, 7-8, 10, 12
{
sum += a[i] * pow;//9
pow*= q;//11
}
return sum;
}
```
```c=
vfmadd231ss a, b, c
powieksz c przez pomnożone a przez b
c+=a*b;
vmulss a, b, c
c=a*b;
```
Wynikiem jest:
$$
\sum_{i=0}^{n} a_i*q^i
$$
# Lista 8 (30.04.2020)
### Zadanie 1
:::info
Poniżej podano zawartość pliku «swap.c»:
```cpp=
extern int buf[];
int *bufp0 = &buf[0];
static int *bufp1;
static void incr() {
static int count = 0;
count++;
}
void swap() {
int temp;
incr();
bufp1 = &buf[1];
temp = *bufp0;
*bufp0 = *bufp1;
*bufp1 = temp;
}
```
Wygeneruj plik relokowalny «swap.o», po czym na podstawie wydruku polecenia «readelf -t -s» dla każdego elementu tablicy symboli podaj:
• adres symbolu względem początku sekcji,
• typ symbolu – tj. «local», «global», «extern»,
• rozmiar danych, na które wskazuje symbol,
• numer i nazwę sekcji – tj. «.text», «.data», «.bss» – do której odnosi się symbol.
Co przechowują sekcje «.strtab» i «.shstrtab»?
:::
```
Num: Value Size Type Bind Vis Ndx Name
0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND
1: 0000000000000000 0 FILE LOCAL DEFAULT ABS swap.c
2: 0000000000000000 0 SECTION LOCAL DEFAULT 1
3: 0000000000000000 0 SECTION LOCAL DEFAULT 3
4: 0000000000000000 0 SECTION LOCAL DEFAULT 4
5: 0000000000000000 0 SECTION LOCAL DEFAULT 5
6: 0000000000000000 8 OBJECT LOCAL DEFAULT 4 _ZL5bufp1
7: 0000000000000008 4 OBJECT LOCAL DEFAULT 4 _ZZL4incrvE5count
8: 0000000000000000 22 FUNC LOCAL DEFAULT 1 _ZL4incrv
9: 0000000000000000 0 SECTION LOCAL DEFAULT 8
10: 0000000000000000 0 SECTION LOCAL DEFAULT 9
11: 0000000000000000 0 SECTION LOCAL DEFAULT 7
12: 0000000000000000 8 OBJECT GLOBAL DEFAULT 5 bufp0
13: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND buf
14: 0000000000000016 72 FUNC GLOBAL DEFAULT 1 _Z4swapv
```
```Value``` - adres
```Type``` - typ
```Size``` - rozmiar
```Ndx``` - number sekcji
| numer | nazwa |
| ----- | ------------------------- |
| UND | undefined |
| ABS | nie podlega żadnej sekcji |
| 1 | ```.text``` |
| 3 | ```.data``` |
| 4 | ```.bss``` |
| 5 | ```.data.rel``` |
| 7 | ```.comment``` |
| 8 | ```.note.GNU-stack``` |
| 9 | ```.eh_frame``` |
```.strtab``` - String Table
String Table jest trzyma stringi z nazwami symboli.
```.shstrtab``` - Section Header String Table
Section Header String Table trzyma stringi z nazwami sekcji.
### Zadanie 2
:::info
Rozważmy program składający się z dwóch plików źródłowych:
```cpp=
/* mismatch-a.c */
void p2(void);
int main(void) {
p2();
return 0;
}
```
```cpp=
/* mismatch-b.c */
#include <stdio.h>
char main;
void p2(void) {
printf("0x%x\n", main);
}
```
Po uruchomieniu program drukuje pewien ciąg znaków i kończy działanie bez zgłoszenia błędu. Czemu tak się dzieje? Skąd pochodzi wydrukowana wartość? Zauważ, że zmienna «main» w pliku «mismatch-a.c» jest niezainicjowana. Co by się stało, gdybyśmy w funkcji «p2» przypisali wartość pod zmienną «main»? Co by się zmieniło gdybyśmy w pliku «mismatch-b.c» zainicjowali zmienną «main» w miejscu jej definicji?
:::
Dzieje się tak ponieważ ```char main``` jest symbolem słabym (ponieważ jest niezainicjowany), natomiast
```int main()``` jest symbolem silnym. Konsolidator preferuje symbole silne zatem output będzie pochodził z
```int main()```. Po wykonaniu ```objdump -d mismatch-a.o``` dostajemy output
```
0000000000000000 <main>:
0: f3 0f 1e fa endbr64
4: 50 push %rax
5: e8 00 00 00 00 callq a <main+0xa>
a: 31 c0 xor %eax,%eax
c: 5a pop %rdx
d: c3 retq
```
natomiast output samego programu to ```0xfffffff3```. Można zauważyć że jest to pierwszy bajt zapisu funkcji ```int main()``` rozszerzony do 4 bajtów.
jeśli spróbujemy zainicjalizować ```char main``` to stanie się to symbol silny zatem będziemy mieli konflikt silnych symboli i spowoduje to linker error.
natomiast jeśli spróbujemy zmienić wartość ```char main``` to dostaniemy błąd podczas wykonania programu ponieważ spróbujemy zmienić zawartość kodu funkcji ```int main()``` co nie jest dozwolone.
### Zadanie 3
:::info
Zapoznaj się z narzędziami do analizy plików relokowalnych w formacie ELF i bibliotek statycznych, tj. «objdump», «readelf» i «ar»; a następnie odpowiedz na następujące pytania:
1. Ile plików zawierają biblioteki «libc.a» i «libm.a» (katalog «/usr/lib/x86_64-linux-gnu»)?
2. Czy wywołanie kompilatora z opcją «-Og» generuje inny kod wykonywalny niż «-Og -g»?
3. Z jakich bibliotek współdzielonych korzysta interpreter języka «Python» (plik «/usr/bin/python»)?
Zaprezentuj w jaki sposób można dojść do odpowiedzi korzystając z podanych poleceń.
:::
Podpunkt 1.:
1. Wejdź do katalogu «/usr/lib/x86_64-linux-gnu».
2. Wpisz ```ar t libc.a | wc -l```. Wynik: ```1690```
3. Wpisz ```cat libm.a```, aby wyświetlić ścieżki (u mnie ~/libm-2.27.a, ~/libmvec.a).
Następnie ```ar t libm-2.27.a | wc -l```; wynik: ```794```.
Potem ```ar t libmvec.a | wc -l```; wynik: ```129```.
Razem: 794 + 129 = 923.
Podpunkt 2.:
Flaga -Og wyłącza pewne optymalizacje.
Flaga -g oznacza włączenie standardowych informacji dla debuggera (można to sprawdzić szukając sekcji .debug_info).
Podpunkt 3.:
Wejdź do /usr/bin. Następnie:
```readelf -d python2.7```
```readelf -d python2.7 | grep "NEEDED"```
### Zadanie 4
:::info
Rozważmy program składający się z dwóch plików źródłowych:
```cpp=
/* str-a.c */
#include <stdio.h>
char *somestr(void);
int main(void) {
char *s = somestr();
s[5] = ’\0’;
puts(s);
return 0;
}
```
```cpp=
/* str-b.c */
char *somestr(void) {
return "Hello, world!";
}
```
Po uruchomieniu program kończy się z błędem dostępu do pamięci. Dlaczego? Gdzie została umieszczona stała znakowa "Hello, world!"? Popraw ten program tak, by się poprawnie zakończył. Gdzie został umieszczony ciąg znaków po poprawce? Nie wolno modyfikować sygnatury procedury «somestr» i pliku «str-a.c», ani korzystać z dodatkowych procedur.
:::
Po uruchomieniu program kończy się z błędem dostępu do pamięci. Dlaczego?
Dzieje się tak ponieważ próbujemy wprowadzić zmiany do read-only
W standardzie C jest napisane,że ciągi znaków które nie są wrzucone na stos lub sterte trafiają zawsze do read-only data.
Co możemy zrobić, żeby temu zapobiec?
1. Możemy wrzucić "Hello, world!" na stos.
```c=
char str[] = "Hello, world!";
```
tylko wtedy pojawi się problem, ponieważ str będzie lokalną wartością
więc po zakończeniu funkcji zostanie zdjęta ze stosu i nie będzie istnieć poza funkcją. - czyli to zmieni jeden problem na inny
2. Możemy użyć malloc żeby wrzucić "Hello, world!" na sterte
```c=
char *str = (char*)malloc(sizeof(char)*14);
```
i po kolei wrzucać literkę po literce, albo skopiować używajac strcpy.
Problem z tym rozwiązaniem jest taki, że wymaga użycia
stdlib.h
3. Możemy zadeklarować "Hello, world!" jako static
```c=
static char str[] = "Hello, world!";
```
to rozwiązanie spowoduje, że ciąg znaków "Hello, world!" zostanie umieszczony w sekcji .data dzięki czemu zwrócony wskaźnik będzie wskazywał na ciąg znaków istniejący cały czas w trakcie działania naszego programu
(tak samo jak domyślnie przy return "Hello, world!")
i będzie można zmieniać ten ciąg znaków bo nie będzie już read-only.
Jedyne co może być kłopotliwe w tym rozwiązaniu, to fakt, że przy każdym wywołaniu funkcji dostaniemy wskaźnik do tego samego ciągu znaków w .data
a więc jeśli go zmienimy gdzieś poza funkcją somestr(void) to przy kolejnym wywołaniu tej funkcji dostaniemy wskaźnik na ten sam ciąg, który został zmieniony.
```
int main(void) {
char *s = somestr();
s[5] = ’\0’;
puts(s);
s = somestr();
puts(s);
return 0;
}
```
a więc ten kod wyprodukuje w konsoli:
Hello
Hello
### Zadanie 5
:::info
Posiłkując się narzędziem «objdump» podaj rozmiary sekcji «.data» i «.bss» plików «bar.o» i «foo.o». Wskaż rozmiar i pozycje symboli względem początków odpowiednich sekcji. Wyjaśnij znaczenie opcji «-fno-common» przekazywanej do kompilatora.
```cpp=
/* bar.c */
int bar = 42;
short dead[15];
```
```cpp=
/* foo.c */
long foo = 19;
char code[17];
```
Na czym polega częściowa konsolidacja z użyciem opcji «-r» do polecenia «ld»? Czym różni się sposób wygenerowania plików «merge-1.o» i «merge-2.o»? Na podstawie mapy konsolidacji porównaj pozycje symboli i rozmiary sekcji w plikach wynikowych. Z czego wynikają różnice skoro konsolidator nie dysponuje informacjami o typach języka C?
:::
bar.o
```
[Nr] Name
Type Address Offset Link
Size EntSize Info Align
Flags
[ 2] .data
PROGBITS 0000000000000000 0000000000000040 0
0000000000000004 0000000000000000 0 4
[0000000000000003]: WRITE, ALLOC
```
O rozmiarze sekcji informuje nas parametr Size.
|Plik |Rozmiar «.data»(B)|Rozmiar «.bss»(B)|
|:---:|:----------------:|:---------------:|
|bar.o| 0x4 | 0x1e |
|foo.o| 0x8 | 0x11 |
symtab dla bar.o
```
Symbol table '.symtab' contains 7 entries:
Num: Value Size Type Bind Vis Ndx Name
0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND
1: 0000000000000000 0 SECTION LOCAL DEFAULT 1
2: 0000000000000000 0 SECTION LOCAL DEFAULT 2
3: 0000000000000000 0 SECTION LOCAL DEFAULT 3
4: 0000000000000000 0 SECTION LOCAL DEFAULT 4
5: 0000000000000000 30 OBJECT GLOBAL DEFAULT 3 dead
6: 0000000000000000 4 OBJECT GLOBAL DEFAULT 2 bar
```
|Symbol| Offset| Sekcja |
|:----:|:-----:|:------:|
| dead | 0x0 | «.bss» |
| bar | 0x0 |«.data» |
symtab dla foo.o
```
Symbol table '.symtab' contains 7 entries:
Num: Value Size Type Bind Vis Ndx Name
0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND
1: 0000000000000000 0 SECTION LOCAL DEFAULT 1
2: 0000000000000000 0 SECTION LOCAL DEFAULT 2
3: 0000000000000000 0 SECTION LOCAL DEFAULT 3
4: 0000000000000000 0 SECTION LOCAL DEFAULT 4
5: 0000000000000000 17 OBJECT GLOBAL DEFAULT 3 code
6: 0000000000000000 8 OBJECT GLOBAL DEFAULT 2 foo
```
|Symbol| Offset| Sekcja |
|:----:|:-----:|:------:|
| dead | 0x0 | «.bss» |
| bar | 0x0 |«.data» |
Opcja [-fno-common](https://gcc.gnu.org/onlinedocs/gcc/Code-Gen-Options.html#Code-Gen-Options) (domyślna) umieszcza niezainicjalizowane zmienne globalne w sekcji «.bss».
Opcja [-r](https://linux.die.net/man/1/ld) dla ld oznacza, że konsolidator ma wygenerować plik relokowalny.
:::info
Czym różni się sposób wygenerowania plików «merge-1.o» i «merge-2.o»?
:::
merge-1.o generujemy konsolidując częściowo foo.o z bar.o, a merge-2.o bar.o z foo.o.
| Plik |Rozmiar «.data»(B)|Rozmiar «.bss»(B)|
|:-------:|:----------------:|:---------------:|
|merge-1.o| 0xc | 0x3e |
|merge-2.o| 0x10 | 0x31 |
Na podstawie map:
merge-1.map:
```
.data 0x0000000000000000 0xc
*(.data)
.data 0x0000000000000000 0x8 foo.o
0x0000000000000000 foo
.data 0x0000000000000008 0x4 bar.o
0x0000000000000008 bar
.data1
*(.data1)
.bss 0x0000000000000000 0x3e
*(.bss)
.bss 0x0000000000000000 0x11 foo.o
0x0000000000000000 code
*fill* 0x0000000000000011 0xf
.bss 0x0000000000000020 0x1e bar.o
0x0000000000000020 dead
```
merge-2.map
```
.data 0x0000000000000000 0x10
*(.data)
.data 0x0000000000000000 0x4 bar.o
0x0000000000000000 bar
*fill* 0x0000000000000004 0x4
.data 0x0000000000000008 0x8 foo.o
0x0000000000000008 foo
.data1
*(.data1)
.bss 0x0000000000000000 0x31
*(.bss)
.bss 0x0000000000000000 0x1e bar.o
0x0000000000000000 dead
*fill* 0x000000000000001e 0x2
.bss 0x0000000000000020 0x11 foo.o
0x0000000000000020 code
```
Wynika to z tego, że sekcja może wymagać wyrównania.
Z użyciem ```readelf -t merge-1.o``` lub ```readelf -t merge-2.o``` możemy dla każej sekcji wyczytać jej wartość dla parametru Align (dostosowany jest do przechowywanych zmiennych).
W tym przypadku dla ```«.data»``` jest to 8, a dla ```«.bss»``` to 16. O dodanym paddingu informuje nas ```*fill*```.
### Zadanie 6
:::info
Plik wykonywalny powstały w wyniku kompilacji poniższych plików źródłowych powinien być nie dłuższy niż 1KiB. Na podstawie nagłówka pliku ELF wskaż w zdeasemblowanym pierwszą instrukcję, którą wykona procesor po wejściu do programu. Na podstawie nagłówków programu wskaż pod jaki adres wirtualny zostanie załadowany segment z sekcją «.text».
```cpp=
/* start.c */
int is_even(long);
void _start(void) {
asm volatile(
"syscall"
: /* no output */
: "a" (0x3c /* exit */),
"D" (is_even(42)));
}
```
```cpp=
/* even.c */
int is_odd(long n);
int is_even(long n)
if (n == 0)
return 1;
else
return is_odd(n - 1);
}
```
```cpp=
/* odd.c */
int is_even(long n);
int is_odd(long n) {
if (n == 0)
return 0;
else
return is_even(n - 1);
}
```
Wskaż w kodzie źródłowym miejsca występowania relokacji. Zidentyfikuj je w wydruku polecenia «objdump -r -d», po czym pokaż jak zostały wypełnione w pliku wykonywalnym. Na podstawie rozdziału §7.7 podręcznika „Computer Systems: A Programmer’s Perspective” zreferuj algorytm relokacji. Wydrukuj tabele relokacji plików relokowalnych, fragment mapy konsolidacji opisujący złączoną sekcję «.text», po czym oblicz ręcznie wartości, które należy wpisać w miejsce relokacji.
:::
**Plik wykonywalny** - zawiera kod i dane w formie pozwalającej na bezpośrednie skopiowanie do pamięci i uruchomienie
**Nagłowek pliku ELF** - zawiera podstawowe informacje dot. pliku takie jak: sposób zapisu danych (np. U2, little endian), typ pliku (np. relokowalny), entry point address itd.
(polecenie: readelf -h nazwa_pliku)
Przykładowo w nagłówku pliku *main* mamy entry point address = 0x40009B, czyli pierwszą wykonaną instrukcją będzie sub $0x8,%rsp
**Segment** - część pliku zawierająca kod wykonywalny.
**Nagłówek programu** - część pliku ELF, która dla danego segmentu przechowuje informacje takie jak np. offset od początku pliku, adres wirtualny, rozmiar itd.
Przykładowo dla pliku *main* mamy adres wirtualny = 0x400000 dla segmentu z sekcją .text
(polecenie: readelf -l nazwa_pliku)
**Relokacja** - scalanie kilku plików relokowalnych w jeden; następuje przy tym scalanie ze sobą odpowiednich sekcji oraz odpowiednie dopasowywanie adresów pamięci (np. przy instrukcjach call)
W naszym kodzie źródłowym obliczanie odpowiednich adresów nastąpi gdy wywołujemy:
1. w funkcji _start - funkcję is_even
2. w funkcji is_even - funkcję is_odd
3. w funkcji is_odd - funkcję is_even
W zdeasemblowanym pliku *main* (objdump -d -r main) wygląda to tak:
```=
main: file format elf64-x86-64
Disassembly of section .text:
0000000000400078 <is_even>:
400078: 48 85 ff test %rdi,%rdi
40007b: 74 08 je 400085 <is_even+0xd>
40007d: 48 ff cf dec %rdi
400080: e9 06 00 00 00 jmpq 40008b <is_odd> # relokacja
400085: b8 01 00 00 00 mov $0x1,%eax
40008a: c3 retq
000000000040008b <is_odd>:
40008b: 48 85 ff test %rdi,%rdi
40008e: 74 08 je 400098 <is_odd+0xd>
400090: 48 ff cf dec %rdi
400093: e9 e0 ff ff ff jmpq 400078 <is_even> # relokacja
400098: 31 c0 xor %eax,%eax
40009a: c3 retq
000000000040009b <_start>:
40009b: 48 83 ec 08 sub $0x8,%rsp
40009f: bf 2a 00 00 00 mov $0x2a,%edi
4000a4: e8 cf ff ff ff callq 400078 <is_even> # relokacja
4000a9: 89 c7 mov %eax,%edi
4000ab: b8 3c 00 00 00 mov $0x3c,%eax
4000b0: 0f 05 syscall
4000b2: 58 pop %rax
4000b3: c3 retq
```
W plikach *odd.o*, *even.o*, *start.o* mieliśmy odwołania do funkcji, których adresu jeszcze nie znaliśmy. W takiej sytuacji zostały utworzone relocation entries, na przykład:
```=
even.o: file format elf64-x86-64
Disassembly of section .text:
0000000000000000 <is_even>:
0: 48 85 ff test %rdi,%rdi
3: 74 08 je d <is_even+0xd>
5: 48 ff cf dec %rdi
8: e9 00 00 00 00 jmpq d <is_even+0xd>
9: R_X86_64_PC32 is_odd-0x4
d: b8 01 00 00 00 mov $0x1,%eax
12: c3 retq
```
W 8 bajcie funkcji is_even mamy instrukcję e9 00 00 00 00 00, przy czym te 8 zer to adres który w przyszłości (w pliku main) zostanie odpowiednio zmieniony. Relocation entry jest tu postaci 9: R_X86_64_PC32 is_odd-0x4, gdzie:
* 9 - offset od początku funkcji is_even
* R_X86_64_PC32 - typ relokacji
* is_odd-0x4 - symbol do którego relocation entry się odnosi
Gdy w pliku *main* obliczamy odpowiednie adresy, postępujemy wg algorytmu (zależy on od typu relokacji, tutaj dla każdego relocation entry mamy R_X86_64_PC32, więc poniżej znajduje się algorytm dla tego przypadku):
----------
w każdej sekcji s dla każdego relocation entry r:
1. refptr = s + r.offset (wskaźnik na adres który powinniśmy zmienić)
2. refadr = ADRES(s) + r.offset
3. *refptr = (unsigned) (ADRES(r.symbol) + *refptr - refadr)
(gdy jednak typ relocation entry to R_X86_32):
1. refptr = s + r.offset
2. *refptr = (unsigned) (ADRES(r.symbol) - *refptr)
----------
W naszym przypadku do dyspozycji mamy następujące dane:
* relocation entries (polecenie readelf -r file_name.o):
```=
is_even.o
Relocation section '.rela.text' at offset 0xf8 contains 1 entry:
Offset Info Type Sym. Value Sym. Name + Addend
000000000009 000500000002 R_X86_64_PC32 0000000000000000 is_odd - 4
------------------------------------
is_odd.o:
Relocation section '.rela.text' at offset 0xf0 contains 1 entry:
Offset Info Type Sym. Value Sym. Name + Addend
000000000009 000500000002 R_X86_64_PC32 0000000000000000 is_even - 4
------------------------------------
start.o:
Relocation section '.rela.text' at offset 0x100 contains 1 entry:
Offset Info Type Sym. Value Sym. Name + Addend
00000000000a 000500000002 R_X86_64_PC32 0000000000000000 is_even - 4
```
* fragment z pliku main.map (mamy tutaj adresy poszczególnych sekcji):
```=
.text 0x0000000000400078 0x3c
*(.text.unlikely .text.*_unlikely .text.unlikely.*)
*(.text.exit .text.exit.*)
*(.text.startup .text.startup.*)
*(.text.hot .text.hot.*)
*(.text .stub .text.* .gnu.linkonce.t.*)
.text 0x0000000000400078 0x13 even.o
0x0000000000400078 is_even
.text 0x000000000040008b 0x10 odd.o
0x000000000040008b is_odd
.text 0x000000000040009b 0x19 start.o
0x000000000040009b _start
```
Mamy więc do obliczenia 3 adresy, jakie powiny zostać zmienione po relokacji:
1. w funkcji is_even, wywołanie is_odd:
r.offset = 0x9
r.symbol = is_odd - 0x4
ADRES(s) = 0x400078
ADRES(r.symbol) = 0x40008B
i teraz zgodnie z algorytmem:
refptr = 0x400078 + 0x9
refadr = 0x400078 + 0x9
*refptr = 0x40008B - 0x4 + 0 - (0x400078 + 0x9) = **0x6**
2. w funkcji is_odd, wywołanie is_even:
r.offset = 0x9
r.symbol = is_even - 0x4
ADRES(s) = 0x40008B
ADRES(r.symbol) = 0x400078
refptr = 0x40008B + 0x9
refadr = 0x40008B + 0x9
*refptr = 0x400078 - 0x4 + 0 - (0x40008B + 0x9) = **0xFFFFFFE0**
3. w funkcji _start, wywołanie is_even:
r.offset = 0xA
r.symbol = is_even - 0x4
ADRES(s) = 0x40009B
ADRES(r.symbol) = 0x400078
refptr = 0x40009B + 0xA
refadr = 0x40008B + 0xA
*refptr = 0x400078 - 0x4 + 0 - (0x40009B + 0xA) = **0xFFFFFFCF**
Możemy sprawdzić obliczenia patrząc na zdeasemblowany plik *main* (pamiętając, że tutaj adresy są zapisane w Little Endian):
```=
main: file format elf64-x86-64
Disassembly of section .text:
0000000000400078 <is_even>:
400078: 48 85 ff test %rdi,%rdi
40007b: 74 08 je 400085 <is_even+0xd>
40007d: 48 ff cf dec %rdi
400080: e9 06 00 00 00 jmpq 40008b <is_odd>
400085: b8 01 00 00 00 mov $0x1,%eax
40008a: c3 retq
000000000040008b <is_odd>:
40008b: 48 85 ff test %rdi,%rdi
40008e: 74 08 je 400098 <is_odd+0xd>
400090: 48 ff cf dec %rdi
400093: e9 e0 ff ff ff jmpq 400078 <is_even>
400098: 31 c0 xor %eax,%eax
40009a: c3 retq
000000000040009b <_start>:
40009b: 48 83 ec 08 sub $0x8,%rsp
40009f: bf 2a 00 00 00 mov $0x2a,%edi
4000a4: e8 cf ff ff ff callq 400078 <is_even>
4000a9: 89 c7 mov %eax,%edi
4000ab: b8 3c 00 00 00 mov $0x3c,%eax
4000b0: 0f 05 syscall
4000b2: 58 pop %rax
4000b3: c3 retq
```
### Zadanie 7
:::info
W trakcie tłumaczenia poniższego kodu na asembler kompilator umieścił tablicę skoków dla instrukcji przełączania w sekcji «.rodata».
```cpp=
int relo3(int val) {
switch (val) {
case 100:
return val;
case 101:
return val + 1;
case 103:
case 104:
return val + 3;
case 105:
return val + 5;
default:
return val + 6;
}
}
```
```
0000000000000000 <relo3>:
0: 8d 47 9c lea -0x64(%rdi),%eax
3: 83 f8 05 cmp $0x5,%eax
6: 77 15 ja 1d <relo3+0x1d>
8: 89 c0 mov %eax,%eax
a: ff 24 c5 00 00 00 00 jmpq *0x0(,%rax,8)
11: 8d 47 01 lea 0x1(%rdi),%eax
14: c3 retq
15: 8d 47 03 lea 0x3(%rdi),%eax
18: c3 retq
19: 8d 47 05 lea 0x5(%rdi),%eax
1c: c3 retq
1d: 8d 47 06 lea 0x6(%rdi),%eax
20: c3 retq
21: 89 f8 mov %edi,%eax
23: c3 retq
```
Dla sekcji «.text» i «.rodata» określ pod jakimi miejscami znajdują się relokacje, a następnie podaj zawartość tablicy relokacji «.rela.text» i «.rela.rodata», tj. listę rekordów składających się z:
• przesunięcia relokacji względem początku sekcji,
• typu relokacji,
• nazwy symbolu i przesunięcia względem początku symbolu.
W wyniku konsolidacji pliku wykonywalnego zawierającego procedurę «relo3», została ona umieszczona pod adresem 0x1000, a tablica skoków pod 0x2000. Oblicz wartości, które należy wstawić w miejsca relokacji.
:::
### Zadanie 8
:::info
Na podstawie rozdziału §7.12 podręcznika „Computer Systems: A Programmer’s Perspective” opisz proces leniwego wiązania (ang. lazy binding) symboli i odpowiedz na następujące pytania:
• Czym charakteryzuje się kod relokowalny (ang. Position Independent Code)?
• Do czego służą sekcje «.plt» i «.got» – jakie dane są tam przechowywane?
• Czemu sekcja «.got» jest modyfikowalna, a sekcje kodu i «.plt» są tylko do odczytu?
• Co znajduje się w sekcji «.dynamic»?
Zaprezentuj leniwe wiązanie na podstawie programu «lazy». Uruchom go pod kontrolą debuggera GDB, ustaw punkty wstrzymań (ang. breakpoint) na linię 4 i 5. Po czym wykonując krokowo program (stepi) pokaż, że gdy procesor skacze do adresu procedury «puts» zapisanego w «.got» – za pierwszym wywołaniem jest tam przechowywany inny adres niż za drugim.
Wskazówka: Wykorzystaj rysunek 7.19. Dobrze jest zainstalować sobie GDB dashboard.
:::
###### tags: `github` `ask`
Sign in with Wallet
Connect another wallet