---
# System prepended metadata

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

---

# Lista 4 (25 marca 2021), grupa KBa

###### tags: `ask21` `ćwiczenia` `kba`

## 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!**

:::danger
|                      | 1   | 2   | 3   | 4   | 5   | 6     | 7     | 8     | 9     |
| --------------------:| --- | --- | --- | --- | --- | ----- | ----- | ----- | ----- |
|        Andriy Bernad | X   | X   |     | X   | X   | ==X== | X     | X     | X     | 8 
|     Wojciech	Bogucki| X   | X   |     | X   |     |       |       |       |       | 3
|         Michał Doros |  X  |  X  |  X  |  X  |  X  |   X   |    X  | X     |   X   | 9
|        Marko Golovko | X   | X   |     |     |     | X     |       |       |       | 3
|    Magdalena Jarecka | X   | X   |     | X   | X   | X     |       |       |       | 5
|        Szymon Jędras | X   | X   |     | X   | X   | X     |       |       |       | 5
|     Heorhii Karpenko | X   | X   |     | X   | X   | X     | X     | ==X== | X     | 8
|    Szymon Kosakowski | X   | X   |     | X   | X   | X     | X     |       |       | 6
|      Izabella Kozioł | X   | X   |     | X   | X   | X     |       |       |       | 5
|   Franciszek Malinka | X   | X   | X   | X   | X   | X     | ==X== | X     | X     | 9
|         Filip Pazera | X   | X   |     | X   | X   | X     | X     |       |       | 6
|    Franciszek Pindel | X   | X   | X   | X   | X   | X     | ==X== | X     | X     | 9
|     Kacper Puchalski | X   | X   |     | X   | X   | X     | X     |       |       | 6
|       Kacper Solecki | X   | X   | X   | X   | X   | X     | X     | X     | X     | 9
|      Andrzej Tkaczyk | X   | X   |     | X   | X   | X     | X     | X     | ==X== | 8
|    Łukasz Wasilewski | X   | X   |     | X   | X   | X     | X     | X     |       | 7
| Vladyslav Yablonskyi | X   | X   |     | X   |     | ==X== |       |       |       | 4
|           Adam Zyzik | X   | X   |     | X   |     | X     | X     |       |       | 5
:::

## Zadanie 1

:::success
Autor: Kacper Puchalski
:::
1. $0x100$
2. $0x13$
3. $0x108$ 
4. $(0x100)\rightarrow 0xFF$ 
5. $(0x100 + 8)\rightarrow 0xAB$ 
6. $(\%rax + \%rdx + 21 = 0x100+3+21 = 0x118) \rightarrow 0x11$

7. $(0xFC + 4 = 0x100) \rightarrow 0xFF$

8. $(\%rax + 8*\%rdx = 0x100 + 24 = 0x118) \rightarrow 0x11$
9. $(\%rcx + 2*\%rdx +265=1+2*3+265=272=0x110) \rightarrow 0x13$


## Zadanie 2

:::success
Autor: Wojciech Bogucki
:::

| Adres Wartość | Rejestr Wartość |
|:------------- |:--------------- |
| 0x100 | 0xFF |
| 0x108 | 0xAB |
| 0x110 | 0x13 |
| 0x118 | 0x11 |
| %rax  | 0x100|
| %rcx  | 1    |
| %rdx  | 3    |

| Nr | Instrukcja    | Rejestr*| Wartość  |
|:--:|:------------- | -------:| -------: |
|1|addq %rcx,(%rax)  |    0x100|0x100     |
|2|subq 16(%rax),%rdx|     %rdx|0xFFFFFFF0|
|3|shrq $4,%rax      |     %rax|0x10      |
|4|incq 16(%rax)     |    0x110|0x14      |
|5|decq %rcx         |     %rcx|0x0       |
|6|imulq 8(%rax)     |  RDX:RAX|0:AB00     |
|7|leaq 7(%rcx,%rcx,8),%rdx|%rdx|0x10     |
|8|leaq 0xA(,%rdx,4),%rdx   |%rdx|0x16    |

*W linijce 1 i 4 to nie są rejestry, tylko miejsce w pamięci.
W lini 2 powinno być o 8 'F' więcej.
Wartość drugiej linijki to 0x3-0x13.

## Zadanie 3

:::success
Autor: Michał Doros
:::

```c=
const uint16_t a = f * (1<<16); // Q0.16 w inta, f = 0.1001010101... i bierzemy pierwsze 16 bitów
const uint16_t b = -a; // 1 - a, 

s[0] = x[0];
for(int i = 1; i < n; i++){
    s[i] = ((uint32_t)a * x[i] + (uint32_t)b * s[i-1]) >> 16;
}
```

zauważmy, że trzymanie liczby x w formacie $Q_{m,n}$ w incie odpowiada trzymaniu $x \cdot 2^{n}$
więc tak naprawdę trzymamy $a\cdot 2^{16}$ oraz $x \cdot 2^{6}$ zatem mnożąc te liczby jako inty otrzymujemy $ax\cdot2^{22}$ zatem żeby wynik mnożenia był w formacie $Q_{10,6}$ musimy go podzielić przez $2^{16}$

## Zadanie 4

:::info
Autor: Izabella Kozioł
:::

<<x>> w %rdi
<<y>> w %rsi
res w %rax

```=
decode: leaq  (%rdi,%rsi), %rax / res = x + y
        xorq  %rax, %rdi / x = res ^ x
        xorq  %rax, %rsi / y = res ^ y
        movq  %rdi, %rax / res = x
        andq  %rsi, %rax / res = res & y
        shrq  $63, %rax / res = res >> 63
        ret / return res
```
Kod w C:
```C=
long decode(long x, long y){
    long res = x + y;
    return ((unsigned long)((res ^ x) & (res ^ y))) >> 63;
}
```

## Zadanie 5

:::success
Autor: Filip Pazera
:::
`%di` zawiera dwa młodsze bajty `%edi`
Ponumerujmy bajty w `%edi` jako `1 2 3 4` 
```=
rorw $8, %di     // 1 2 4 3
rorl $16, %edi   // 4 3 1 2
rorw $8, %di     // 4 3 2 1
movl %edi, %eax
ret
```

Tłumaczy się do `roll`:
```c=
(x & 0xFF000000) >> 24 | (x & 0x00FFFFFF) << 8;
```

## Zadanie 6

:::success
Autor: Władysław Jabłoński
:::
x = x1(starsze 64 bity) + x2
y = y1(starsze 64 bity) + y2
dodajemy starsze 64 bit (operacja add) jeśli wystąpiło przeniesienie bitu to jest zapalona flaga CF
```=
add %rsi, %rcx // x2 + y2
adc %rdi, %rdx // x1 + y1 + CF(Carry Flag)
mov %rcx, %rax
ret
```

## Zadanie 7
:::success
Autor: Franciszek Malinka
:::

**Dane:** $x$, $y$ w postaci $x = A\cdot 2^{64} + B, y = C\cdot 2^{64}+D$.
**Zadanie:** policz $x \cdot y \mod 2^{128}$

**Rozwiązanie:** 
\begin{align}
x\cdot y &=_{2^{128}} (A\cdot 2^{64} + B)(C\cdot 2^{64} + D) \\ &=_{2^{128}} AC\cdot 2^{128} + (AD + CB)2^{64} + BD \\
&=_{2^{128}} (AD + CB)\cdot 2^{64} + BD_{}
\end{align}

Zauważmy, że musimy wykonać dokładnie 3 mnożenia. Ponadto nie interesuje nas 64 młodszych bitów wyrażenia $AD + CB$, gdyż i tak te starsze bity giną przy przesunięciu liczby o 64 bity. Algorytm sprowadza się zatem do obliczenia 64 młodszych bitów $AD + CB$, przesunięcia ich o 64 bity w lewo, obliczenia $BD$ i dodaniu obu wartości do siebie.

```c
// %rdi - A, %rsi - B
// %rdx - C, %rcx - D
mult:
    mulq %rdx, %rsi                ; teraz w %rdx będą starsze bity
                                  ; BC, w %rax młodsze bity BC
    movq %rax, %rbx                ; przenosze młodsze bity BC do rbx
    mulq %rdi, %rcx                ; teraz w %rdx będą starsze bity AD
                                  ; w %rax młodsze bity AD
    movq %rax, %rdi                ; w %rdi są młdosze bity AD
    mulq %rsi, %rcx                ; teraz w %rdx będą starsze bity BD
                                  ; w %rax młodsze bity BD
    addq %rbx, %rdx
    addq %rdi, %rdx                ; dodaje do starszych bitów BD młodsze AD oraz BC
    ret                           ; w %rax jest to co chcemy, w %rdx też, zwracamy
```

Źle zrozumiałem jak działa mulq, myślałem że bierze dwa operandy i wynik daje do `rdx:rax`. Jednak działa tak, że trzeba przenieść jedną wartość do %rax, i wtedy `mulq <rejestr>` mnoży to co jest w `%rax` z tym co jest w `rejestr`. Poprawny kod poniżej (robi to samo, ale przed mnożeniem przenosi jedną z wartości do %rax):

```c=
// %rdi - A, %rsi - B
// %rdx - C, %rcx - D
; przez napis XY0 mam na myśli młodsze 64 bity liczby X*Y, XY1 to starsze 64 bity liczby X*Y
mult:
    movq %rsi, %rax          ; w %rax jest B    
    mulq %rdx                ; w %rdx jest C, po wykonaniu mnożenia w %rdx jest BC1, w %rax BC0
    movq %rax, %rbx          ; przenosze BC0 do %rbx
    movq %rdi, %rax          ; przenosze A do %rax
    mulq %rcx                ; mnoże D z A, po wykonaniu mnożenia w %rdx jest AD1, w %rax jest AD0
    movq %rax, %rdi          ; przenosze AD0 do %rdi
    movq %rsi, %rax          ; przenosze B do %rax
    mulq %rcx                ; mnoze przez D, po wykonaniu mnożenia w %rdx jest BD1, w %rax jest BD0
    addq %rbx, %rdx          ; dodaje BC0 do BD1
    addq %rdi, %rdx          ; dodaje AD0 do (BC0 + BD1)
    ret                      ; %rdx - BC0 + AD0 + BD1, %rax - BD0
```
Jeszcze krócej, z użyciem imulq:
```c=
mult:
    imluq    %rsi, %rdx      ; w %rdx jest teraz BC0
    movq     %rdx, %rbi      ; przenosimy BC0 do rbi
    imulq    %rcx, %rdi      ; w %rdi jest teraz AD0
    movq     %rsi, %rax      ; przenosimy B do %rax
    mulq     %rcx            ; w %rdx jest teraz BD1, w %rax jest BD0
    addq     %rdi, %rdx      ; do BD1 dodajemy AD0
    addq     %rbi, %rdx      ; do (BD1 + AD0) dodajemy BC0
    ret
```

## Zadanie 8

:::success
Autor: Grzegorz Karpenko
:::

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

```=
withJump:
        addq rdi, rsi
        jnc no_overflow  ; skok jeśli nie ma przeniesienia bitu (flaga CF)
        movq $ULONG_MAX, rsi
    no_overflow:
        movq rsi, rax
        ret
        
noJump:
        addq %rsi, %rdi
        sbbq %rax, %rax ; z tego powstanie 0 lub -1
        orq  %rdi, %rax
        ret
```

sbb rax, rax - tożsame działaniu: rax - rax - (flaga CF). Jeśli wystąpi przeniesienie to wtedy w rsi będą same zera, gdy odejmiemy od 0 1 to wtedy nam sie zapalą wszystkie bity, analogicznie mówiąc, reprezentacja bitowa będzie wskazywać na wartość -1, ale to jest unsigned wiec bedzie ulong_max

## Zadanie 9

:::info
Autor: Andrzej Tkaczyk
:::
niech x i y będą odpowiednio w %rdi i %rsi

```=
subq %rsi, %rdi    // W %rdi mamy x-y. CF=1 jeśli x<y, CF=0 wpp.
sbbq %rax, %rax    // W %rax jest -1 jeśli x<y, 0 wpp.
negq %rdi          // Gdy x=y, to x-y=0 wtedy neg ustawia CF na 0. Gdy x<y, lub x>y, to CF=1.
adcq %rax, %rax    // -1+(-1)+1 jeśli x<y, 0+0+0 jeśli x=y, 0+0+1 jeśli x>y.
ret
```