---
# System prepended metadata

title: 'Lista 4 (25. marca 2021), grupa pwit'
tags: [pwit, ask21, ćwiczenia]

---

# 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	
:::
![](https://i.imgur.com/9Kixlq5.png)
![](https://i.imgur.com/5NP2uRT.png)
Źródło: https://www.cs.cmu.edu/~fp/courses/15213-s07/misc/asm64-handout.pdf

![](https://i.imgur.com/9HSSB8m.png =280x)

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

```c=
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;
}
```

```c=
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

```c=
    return x << i | x >> (32 - i);
```


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

![](https://i.imgur.com/CRxMCCv.png)
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	
:::

![](https://i.imgur.com/58DLWa4.png)


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
```
![](https://i.imgur.com/ta86IfH.png)

![](https://i.imgur.com/df0bBv1.jpg)

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

```assembly=
        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).

```assembly=
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	
:::

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

```assembly=
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`

