# 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
:::
```=
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
```
Sign in with Wallet
Connect another wallet