---
# System prepended metadata

title: ASK 2020 GR. Kraski cz I
tags: [ask, github]

---


# 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 +&#x221e;,
> * 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"```
![](https://i.imgur.com/1rZggZl.png)



### 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`