# Lista 4 (25. marca 2021), grupa pwit

###### tags: `ask21` `ćwiczenia` `pwit`

## Deklaracje

Gotowość rozwiązania zadania należy wyrazić poprzez postawienie X w odpowiedniej kolumnie! Jeśli pożądasz zreferować dane zadanie (co najwyżej jedno!) w trakcie dyskusji oznacz je znakiem ==X== na żółtym tle.

**UWAGA: Tabelkę wolno edytować tylko wtedy, gdy jest na zielonym tle!**

Tabelka zawiera tylko osoby zapisane do grupy. Osoby oczekujące proszone są o wpisanie się do osobnej tabelki poniżej.

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ----------------------:| ----- | --- | --- | --- |:---:|:---:| --- |:---:|:-----:|
| Wojciech Adamiec | X | X | | X | X | X | X | | |
| Kacper Bajkiewicz | X | X | | X | X | X | X | X | X |
| Bartłomiej Hildebrandt | X | X | | X | X | X | X | | X |
| Dominik Komła | X | X | | X | X | X | X | X | X |
| Aleksandra Kosińska | X | X | | X | X | X | | X | X |
| Oleś Kulcewicz | X | X | | X | X | X | | | X |
| Damian Lukas | X | X | | X | | X | | | |
| Michał Mikołajczyk | X | X | | X | X | X | X | | |
| Mateusz Opala | X | X | | X | X | X | X | X | X |
| Łukasz Orawiec | X | X | | X | X | X | X | X | X |
| Szymon Pielat | X | X | | X | X | X | X | X | |
| Łukasz Pluta | X | X | | X | X | X | X | X | X |
| Kamil Puchacz | X | X | | X | X | X | X | X | X |
| Magdalena Rzepka | X | X | | X | X | X | | X | X |
| Cezary Stajszczyk | X | X | | X | X | X | | X | ==X== |
| Jakub Szajner | X | X | | X | X | X | X | X | X |
| Bartosz Troszka | ==X== | X | | X | X | X | X | X | X |
| Miłosz Urbanik | X | X | | X | X | X | | X | X |

:::

## Zadanie 1
:::info
Autor: Damian Lukas
:::

Mając wartości typu `long` mamy podać wartości operandów źródłowych.
| Adres |Wartość |Rejestr |Wartość |
|:-------:|:------:|:------:|:-------:|
| `0x100` | `0xFF` | `%rax` | `0x100` |
| `0x108` | `0xAB` | `%rcx` | `1` |
| `0x110` | `0x13` | `%rdx` | `3` |
| `0x118` | `0x11` | - | - |

W poniższych wzorach $D$ oznacza przesunięcie o stałą liczbę bajtów, $Rb$ i $Ri$ to rejestry do których się odwołujemy, a $S$ to skala (rozmiar danej):
* $\text{D(Rb, Ri, S) = Mem[Reg[Rb]+S*Reg[Ri]+D]}$
* $\text{(Rb, Ri) = Mem[Reg[Rb]+Reg[Ri]]}$
* $\text{D(Rb, Ri) = Mem[Reg[Rb]+Reg[Ri]+D]}$
* $\text{(Rb, Ri, S) = Mem[Reg[Rb]+S*Reg[Ri]]}$

Rozwiązanie:
1. `%rax` zwraca `0x100`
2. `0x110` zwraca `0x13`
3. `$0x108` zwraca `0x108` - jakaś stała
4. `(%rax)` zwraca `0xFF` - dereferencja wskaźnika, tzn. bierzemy wartość `%rax` jako adres
5. `8(%rax)` zwraca `(%rax + 8) = (0x108) = 0xAB` - jak wyżej
6. `21(%rax, %rdx)` zwraca `(%rax + %rdx + 21) = (0x100 + 3 + 21) = (0x100 + 0x18) = (0x118) = 0x11`
7. `0xFC(, %rcx, 4)` zwraca `(4 * %rcx + 0xFC) = (0x4 + 0xFC) = (0x100) = 0xFF`
8. `(%rax, %rdx, 8)` zwraca `(0x100 + 8 * %rdx) = (0x100 + 24) = (0x100 + 0x18) = (0x118) = 0x11`
9. `265(%rcx, %rdx, 2)` zwraca `(%rcx + 2 * %rdx + 265) = (0x1 + 0x6 + 0x109) = (0x110) = 0x13`

## Zadanie 2
:::info
Autor: Michał Mikołajczyk
:::
Źródło: https://www.cs.cmu.edu/~fp/courses/15213-s07/misc/asm64-handout.pdf


1. `addq %rcx, (%rax)`
- Adres docelowy: 0x100
- Wartość: 0xFF+1 = 0x100
2. `subq 16(%rax), %rdx`
Wchodzimy pod adres 0x110 (%rax + 16) i wyciągamy wartość 0x13
- Adres docelowy: %rdx
- Wartość: 0x3 - 0x13 = -0x10
3. `shrq $4, %rax`
shrq - shift logiczny w prawo
- Adres docelowy: %rax
- Wartość: 0x100 >> 4 = 0x10
4. `incq 16(%rax)`
incq - increment by 1
- Adres docelowy: 0x110
- Wartość: 0x13 + 1 = 0x14
5. `decq %rcx`
decq - decrement by 1
- Adres docelowy: %rcx
- Wartość: 0x0
6. `imulq 8(%rax)`
Mnożymy wartość pod adresem 0x108 przez wartość w %rax. 128 bitowy wynik tej operacji zapisany jest na rejestrach %rdx:%rax, gdzie rax zawiera młodszą połowę bitów. W tym przypadku mieścimy się w %rax.
- Adres docelowy: %rax
- Wartość: 0xAB * 0x100 = 0xAB00
7. `leaq 7(%rcx, %rcx, 8), %rdx`
- Adres docelowy: %rdx
- Wartość: %rcx + 8 * %rcx + 7 = 0x1 + 0x8 +0x7 = 0x10
8. `leaq 0xA(, %rdx, 4), %rdx`
- Adres docelowy: %rdx
- Wartość: 4 * %rdx + 0xA = 0x3*4 + 0xA = 0x16

## Zadanie 3
:::info
Autor:
:::

ważne: działamy na 32-bitowym procesorze, zatem mamy do dyspozycji typ int32_t i działania na nim

int32_t alp = maska_bitowa_liczby_float // wartość zmiennopozycyjna liczby alpha (nie możemy napisać tej deklaracji, bo nasz komp. nie ma floatów)

constexpr int16_t alpha = ??? //uzyskać wartość ze zmiennej float al
constexpr int16_t one_minus_alpha = 

alpha to jest w formacie Q0.16, tzn. alpha = alp * 2^16?

alp = 0.abcdef... -> alpha = abcdef.....
1-alp = -alpha

alpha= alp * 2^16

int16_t repr_x[] // zawiera reprezentację w formacie Q10.6 liczb x1,..., x_n;

repr_x[i] = x_i * 2^6;

Każą nam policzyć
$alp * x_i$, to liczymy (alpha * repr_x[i]). Ten iloczyn jest liczbą 32-bitową, ale to jest w porządku, bo dysponujemy typem int32_t.

repr_s[i] = (((int32_t) alpha * repr_x[i]) + (int32_t)(-alpha) * repr_s[i-1]) >> (22 - 6)

## Zadanie 4
:::info
Autor: Oleś Kulczewicz
:::

decode: leaq (%rdi,%rsi), %rax
        xorq %rax, %rdi
        xorq %rax, %rsi
        movq %rdi, %rax
        andq %rsi, %rax
        shrq $63, %rax
        ret

long decode_step_by_step(long x, long y) {
  long res = x + y;
  x = res ^ x;
  y = res ^ y;
  res = x & y;
  res = res >> 63;
  return res;
}

long decode(long x, long y) {
  long temp = x + y;
  return ((x ^ temp) & (y ^ temp) >> 63;
}

`x` and `y` has maximum and minimum possible values for `long` (denoting only the sign bit, so `0` is maximum and `1` is minimum possible value)
1. x: 0 && y: 0
res: 1
return: 1
2. (x: 1 && y: 0) || (x: 0 && y: 1)
res: 0
return: 0
3. x: 1 && y: 1
res: 0
return: 1

## Zadanie 5
:::info
Autor: Jakub Szajner
:::

movl %edi %eax
rol $8 %ax
rol $16 %eax
rol $8 %ax

ABCD -> ABDC -> DCAB -> DCBA

    return x << i | x >> (32 - i);

## Zadanie 6
:::info
Autor: Kamil Puchacz
:::

adc - sumuje A, B oraz flag CF; wynik przechowuje w B.
CF - flaga przeniesienia (carry flag)

Wiemy, że $x = x_1 \cdot 2^{64} + x_0$ oraz $y = y_1 \cdot 2^{64} + y_0$.
$x_1=\%rdi$
$x_0=\%rsi$
$y_1=\%rdx$
$y_0=\%rcx$

sum_big:    addq %rsi, %rcx
            adc  %rdi, %rdx
            movq %rcx, %rax
            ret

Gdy nastąpi przeniesienie bitu przy wykonaniu instrukcji addq, to wtedy zostanie zapalona flaga CF, którą następnie wykorzystamy w instrukcji adc (zostanie dodana do sumy).
https://pl.wikibooks.org/wiki/Asembler_x86/Instrukcje/Arytmetyczne#adc
https://pl.wikipedia.org/wiki/FLAGS

## Zadanie 7
:::info
Autor: Bartosz Troszka
:::


Wiemy, że $x = x_1 \cdot 2^{64} + x_0$ oraz $y = y_1 \cdot 2^{64} + y_0$. Wtedy $x*y = (x_1 \cdot 2^{64} + x_0)\cdot (y_1 * 2^{64} + y_0) = x_1\cdot y_1\cdot 2^{128} + (x_1\cdot y_0 + x_0\cdot y_1)\cdot 2^{64} + x_0\cdot y_0$.
Wartość $x_1\cdot y_1\cdot 2^{128}$ jest za duża, więc ją pomijamy.

$x_1=\%rdi$
$x_0=\%rsi$
$y_1=\%rdx$
$y_0=\%rcx$

multiply:
    movq %rdx, %rax
    mulq %rsi        
    movq %rax, %r8
    movq %rdi, %rax
    mulq %rcx         
    addq %rax, %r8
    movq %rsi, %rax
    mulq %rcx         
    addq %r8, %rdx  
    ret



## Zadanie 8
:::info
Autor: Aleksandra Kosińska
:::

Wartości $x$ i $y$ typu `uint64_t` są przekazywane przez rejestry `%rdi` i `%rsi`, a wynik zwracany w rejestrze `%rax`

$$
\begin{equation}
addu(x,y)=
\begin{cases}
ULONG\_MAX & \text{dla } x+y\geq ULONG\_MAX\\
x+y & \text{w p.p.}
\end{cases}
\end{equation}
$$

Najpierw rozwiąż zadanie używając instrukcji skoku warunkowego
`jnc` $\to$ skok, jeśli nie ma przeniesienia, flaga `CF = 0`

        addq %rsi, %rdi
        jnc jump
        movq $ULONG_MAX, %rdi
jump:   movq %rdi, %rax

Potem przepisz je używając instrukcji `sbb`

`sbb A B`
- Subtraction with Borrow
- działanie $\to$ odejmuje `B` i flagę `CF` od `A`
- wynik przechowuje w `A`
- `A` $\to$ rejestr lub adres pamięci
- `B` $\to$ konkretna wartość, rejestr lub adres pamięci (ale tylko jeśli A również nie jest adresem pamięci).

addq %rsi, %rdi  // ustawi flagę CF
sbbq %rax, %rax  // %rax = %rax − (%rax + CF)
                 // %rax = -CF
orq  %rdi, %rax  // dla %rax = -1 zwróci ULONG_MAX
                 // dla %rax = 0 zwróci %rdi

## Zadanie 9
:::info
Autor: Cezary Stajszczyk
:::

long cmp(uint64_t x, uint64_t y);

$$
\begin{equation}
cmp(x,y)=
\begin{cases}
-1 & \text{gdy } x \lt y \\
1 & \text{gdy } x \gt y \\
0 & \text{gdy } x = y
\end{cases}
\end{equation}
$$

`%rdi := x` pierwszy argument funkcji.
`%rsi := y` drugi argument funkcji.
Wartość będzie zwracana orzez `%rax`.

`adc Src, Dest` - `Dest := Dest + Src + CF`
`sbb Src, Dest` - `Dest := Dest - (Src + CF)`
`neg Dest` - `CF := !(Dest == 0)`, `Dest := -Dest`

subq %rsi, %rdi  // x = x - y
sbbq %rax, %rax
negq %rdi        // if x != y: CF := 1
adcq %rax, %rax  
ret

1. `x > y`:
- `CF := 0 and %rdi != 0`
- `%rax := 0`
- `CF := 1`
- `%rax := 1`

2. `x < y`:
- `CF := 1 and %rdi != 0`
- `%rax := -1`
- `CF := 1`
- `%rax := -1`

3. `x == y`:
- `CF := 0 and %rdi := 0`
- `%rax := 0`
- `CF := 0`
- `%rax := 0`