# Lista ćwiczeniowa nr 3 (środa)
###### tags: `SysKomp20`

:::info
grupa PWit, środa 8-10
:::

:::success
[Link do audio/wideo-konferencji](https://meet.google.com/muu-ahkr-aak?authuser=1)
:::

## Deklaracje

:::info
Studenci wypełniają poniższą tabelkę przed rozpoczęciem zajęć. Student ma obowiązek zapoznać się wcześniej ze składnią języka Markdown!
:::
Gotowość rozwiązania zadania należy wyrazić poprzez postawienie X w odpowiedniej kolumnie! Jeśli kogoś nie ma na liście to proszę dopisać się pod spodem.

| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| -------------- | --- | --- | --- | --- | --- | --- | --- | --- |---|
| Maksymilian DeBeściak |X|X|X|X|X|X|X|X|X|
| Paweł Bajgrowicz |X|X|X|X|X|X|X| | |
| Przemysław Czerwiński |X|X|X|X|X|X|X| | |
| Antoni Dąbrowski |X|X|X|X|X|X| | |X|
| Alicja Danilczuk |X|X|X|X|X|X|X| | |
| Agnieszka Jonak |X|X|X|X|X|X| | | |
| Agata Kasprzak |X|X|X|X|X|X|X| | |
| Karol Kęciński |X|X|X|X|X|X|X|X|X|
| Błażej Korasiak | | | | | | | | | |
| Józef Kowalewicz |X|X|X| |X|X|X| | |
| Jakub Mendyk |X|X|X|X|X|X|X|X|X|
| Barbara Piasecka |X|X|X|X|X|X|X| | |
| Damian Ratajski | | | | | | | | | |
| Aleksandra Stępniewska |X |X |X |X |X |X |X |X | |
| Karol Stuła |X|X|X|X|X|X|X| |X|
| Daniel Wiczołek | | | | | | | | | |
| Patryk Wilusz |X|X|X|X|X|X|X| | |
| Mateusz Zając |X|X|X|X|X| |X| | |

## Rozwiązania (30 minut)

:::info
Na początku zajęć prowadzący przypisuje studentów do zadań. W ciągu 30 minut student ma obowiązek uzupełnić rozwiązanie zadania. Jeśli zadanie wymaga posłużenia się diagramem, to można wkleić jego zdjęcie. Prowadzący może zlecić przygotowanie rozwiązania danego zadania więcej niż jednej osobie.

:::

:::warning
Zamieszczanie zdjęć gotowych rozwiązań jest niedozwolone chyba, że prowadzący na to pozwoli.
:::

:::danger
Udostępnianie gotowych rozwiązań studentom z innych grup ćwiczeniowych jest niedozwolone!
:::

### Zadanie 1
> [name=Piotr Witkowski] Rozwiązuje p. Agnieszka Jonak.

1. %rax - **0x100** - nie może dotyczyć adresu w pamięci
2. $0x110 - **0x110** - nie może dotyczyć adresu w pamięci
3. 0x108 - **0xAB**
4. (%rax) - **0xFF**
5. 8(%rax) - **0xAB** bo 8(%rax) = 0x100 + 8 = 0x108 czyli odczytujemy wartość pod adresem 0x108
6. 23(%rax,%rcx) - **0x11** bo 0x100 + 1 + 23 = 0x118
7. 0x104(,%rdx,4) - **0x13** bo 3*4 + 0x104 = 0x110
8. (%rax,%rdx,8) - **0x11** bo 0x100 + 3*8 = 0x118
9. 265(%rcx,%rdx,2) - **0x13** bo 1 + 3*2 + 265 = 272 = 0x110

### Zadanie 2
> [name=Piotr Witkowski] Zadanie rozwiązuje p. Agata Kasprzak.
>

NR PODPUNKTU | ADRES | WARTOŚĆ |
| -------- | -------- | -------- |
|1 addq %rcx,(%rax)| 0x100 | 1+0xFF=0x100 |
|2 subq 16(%rax),%rdx| %rdx | 3-(0x100+0x10)=3-0x13=-0x10 |
|3 shrq $4,%rax| %rax | 0x100>>4=0x10 |
|4 incq 16(%rax)| 0x110 | (0x100+0x10)+1=0x13+1=14|
|5 decq %rcx| %rcx | 1-1=0|
|6 imulq 8(%rax)| 0x108 | (0x100+8)* (%rdx:)%rax=0xAB*0x100=0xAB00|
|7 leaq 7(%rcx,%rcx,8),%rdx| %rdx| 9*1+7=0x10|
|8 leaq 0xA(,%rdx,4),%rdx| %rdx | 4*3+10=0x16|

### Zadanie 3
> [name=Piotr Witkowski] Zadanie rozwiązuje p. Józef Kowalewicz.
>
Dla każdej z poniższych instrukcji wyznacz odpowiedni sufiks (tj. b, w, l lub q) na podstawie rozmiarów operandów:
(b - 1 bajt; w - 2 bajty; l - 4 bajty; q - 8 bajtów)
1. mov %eax,(%rsp)
>movl %eax,(%rsp)
2. mov (%rax),%dx
>movw (%rax),%dx
3. mov $0xFF, %bl
> movb $0xFF, %bl
4. mov (%rsp,%rdx,4),%dl
>movb (%rsp,%rdx,4),%dl
5. mov (%rdx),%rax
>movq (%rdx),%rax
6. mov %dx,(%rax)
>movw %dx,(%rax)

### Zadanie 4

> [name=Piotr Witkowski] Zadanie rozwiązuje p. Mateusz Zając.
>

Które z poniższych linii generuje komunikat błędu asemblera i dlaczego?

1. movb $0xF,(%ebx) - W architekturze x86-64 powinniśmy używać 64 bitowych wskaźników. Błąd zniknie jeśli zamiast %ebx użyjemy %rbx.

2. movl %rax,(%rsp) - Błędny suffix. Operandy mają długość 64 bitów, a suffix jest dla operandów 32 bitowych.

3. movw (%rax),4(%rsp) - Nie można przenosić danych bezpośrednio z jednego miejsca w pamięci w drugie przy użyciu jednej instrukcji.

4. movb %al,%sl - Nie istnieje taki rejestr jak %SL.

5. movq %rax,$0x123 - Drugi operand (miejsce do zapisu) nie może być wartością. Nie możemy zapisać czegoś do stałej.

6. movl %eax,%rdx - Suffix L jest dla operandów 32-bitowych. %RDX to operand 64-bitowy.

7. movb %si,8(%rbp) - Suffix B jest dla operandów 8-bitowych, %SI to operand 16-bitowy.

### Zadanie 5

> [name=Piotr Witkowski] Zadanie rozwiązuje p. Antoni Dąbrowski.
>

Rejestry %rax i %rcx przechowują odpowiednio wartości x i y. Podaj wyrażenie, które będzie opisywać zawartość rejestru %rdx po wykonaniu każdej z poniższych instrukcji:

1. leaq 6(%rax), %rdx

x+6

2. leaq (%rax, %rcx), %rdx

x+y

3. leaq (%rax, %rcx, 4), %rdx

x+y*4

4. leaq 7(%rax, %rax, 8), %rdx

7+(x+x*8) = 9*x+7

5. leaq 0xA(, %rcx, 4), %rdx

10+(0+y*4) = 4*y+10

6. leaq 9(%rax, %rcx, 2), %rdx

9+(x+y*2) = x+2*y+9

### Zadanie 6
> [name=Piotr Witkowski] Zadanie rozwiązuje p. Przemysław Czerwiński.
>

Zastąp instrukcję subq %rsi, %rdi równoważnym ciągiem instrukcji bez jawnego użycia operacji odejmowania. Można używać dowolnych innych instrukcji i rejestrów.

**Rozwiązanie**

Dla dowolnego x:
`-1 == ~x + x` | +1, -x
`-x == ~x + 1`

Dlatego zamiast `y - x` możemy użyć `y + ~x + 1`.

notq %rsi
addq %rsi,%rdi # %rdi += ~%rsi
incq %rdi      # %rdi += 1 

> [name=Piotr Witkowski] Dlaczego powyższy kod jest lepszy od:

notq %rsi
incq %rsi
addq %rsi,%rdi # %rdi += ~%rsi

> Podpowiedź: przypadki brzegowe? Co się dzieje gdy %rsi jest równe INT32_MIN? A %rdi jest np. nieujemne?

### Zadanie 7

> [name=Piotr Witkowski] Zadanie rozwiązuje p. Karol Kęciński.
>

Kompilator przetłumaczył funkcję o sygnaturze «uint64_t compute(int64_t x, int64_ty)» na następujący kod asemblerowy.

compute:
$\quad$ leaq (%rdi,%rsi), %rax
$\quad$ movq %rax, %rdx
$\quad$ sarq $31, %rdx
$\quad$ xorq %rdx, %rax
$\quad$ subq %rdx, %rax
$\quad$ ret

Argumenty x i y zostały przekazane funkcji compute odpowiednio przez rejestry
%rdi i %rsi, a wynik został zwrócony przez instrukcję ret w rejestrze %rax. Jaką
wartość oblicza ta funkcja?

Możemy zapisać tę funkcję w ten sposób:

%rax = x + y
%rdx = %rax
%rdx = %rdx>>31
%rax = %rax ^ %rdx
%rax = %rax - %rdx

Niech z = x + y
Wtedy ta fukcja oblicza wartość wyrażenia

((z >> 31) ^ z) - (z >> 31)

Czyli

|x + y|

x i y muszą mieścić się w zakresie od -2^32 do 2^32
(ponieważ wykonujemy przesunięcie o 31 bitów, a x i y są typu int64_t)

> [name=Przemysław Czerwiński] Wydaje mi się, że nie działa to dla wszystkich x, y w podanym zakresie. Na przykład:
x = 2^31^, y = 1
(2^31^ + 1) >> 31 == 1
1 ^ (2^31^ + 1) == 2^31^
2^31^ - 1 –> to jest ostateczny wynik, a powinno wyjść 2^31^ + 1
> [name=Agata Kasprzak] te liczby powinny być chyba z zakresu int32_t a 2^31^ się tam nie mieści
> [name=Przemysław Czerwiński] Tak, dla x, y z zakresu [-2^31^, 2^31^ - 1] to powinno działać (chociaż nie jest to oczywiste i wydaje mi się, że przydałby się w tym miejscu jakiś dowód).

### Zadanie 8

> [name=Piotr Witkowski] Zadanie rozwiązuje p. Jakub Mendyk.
>

Rozwiąż poprzednie zadanie dla funkcji «int16_t compute2(int8_t m, int8_t s)».
Jak poprzednio, pierwszy argument został przekazany w rejestrze %rdi, drugi w
%rsi a wartość zwracana jest w %rax. Funkcja operuje na 8-, 16-, 32 i 64-
bitowych rejestrach, a zwraca wynik w rejestrze 64-bitowym. Wyjaśnij, jak
poszczególne wiersze kodu zmieniają starsze bajty rejestrów, których młodszymi
bajtami są ich operandy.

#### Rozwiązanie

| Instrukcja | Komentarz |
| --------------------- | ---- |
| compute2: | %dil -> m (i8), %sil -> s (i8), wynik w %rax |
| movsbw %dil, %di | rozszerzenie liczby ze znakiem 8-bitowej do 16-bitowej |
| movl %edi, %edx | %edx <- %edi |
| sall $4, %edx | %edx <- %edx $* 2 ^ 4$ |
| subl %edi, %edx | %edx <- %edx - %edi |
| leal 0(,%rdx,4), %eax | %eax <- $4*$ %rdx |
| movsbw %sil, %si | rozszerzenie liczby ze znakiem 8-bitowej do 16-bitowej |
| addl %esi, %eax | %eax <- %eax + %esi |
| ret | %rax |

Cofamy się od ostatniej do pierwszej instrukcji, otrzymując wyrażenie, którego wartość została zwrócona:

%rax
%eax
%eax + %esi [%si]
(4 * %rdx) + %esi [%si]
(4 * %edx) + %esi [%si]
(4 * (%edx - %edi)) + %esi [%si]
(4 * ((%edx << 4) - %edi)) + %esi [%si]
(4 * ((%edx << 4) - %edi)) + %esi [%si]
(4 * ((%edi << 4) - %edi)) + %esi [%si]
(4 * ((m << 4) - m)) + s
wynik: 60*m + s
// m -- 1-bajt, rozszerzony do dwóch
// m << 4 -- przesunięte o 1/4 szerokości
// 4(m << 4 - m) -- pomniejszone o m i przesunięte o 1/8 szerokości

Stany rejestrów:

<table>
<thead>
<tr><th>Rejestr</th><th>4-bajt</th><th>3-bajt</th><th>2-bajt</th>
<th>1-bajt</th></tr></thead>
<tbody>
<tr><td>eax</td><td colspan="4" align="center">4((%edi << 4) - %edi)</td></td></tr>
<tr><td>edx</td><td colspan="4" align="center">(%edi << 4) - %edi</td></td></tr>
<tr><td>edi</td><td colspan="2" align="center">0</td><td>yyyyyyyy</td><td>yijklmno</td></tr>
<tr><td>esi</td><td colspan="2" align="center">0</td><td>xxxxxxxx</td><td>xabcdefgh</td></tr>
</tbody>
</table>

### Zadanie 9

> [name=Piotr Witkowski] Zadanie rozwiązuje p. Karol Stuła.
>
> EDIT: p. Karol robi punkt 1. Punkty 2. i 3. rozwiązują odpowiednio pp. Antoni Dąbrowski i Karol Kęciński.
>

Zinterpretuj poniższe stałe szesnastkowe jako liczby pojedyńczej precyzji (32-
bitowe) w formacie IEEE 754, następnie wykonaj dodawania i zapisz wynik w takim
samym formacie.

1. 0xC0D20004 + 0x72407020
2. 0xC0D20004 + 0x40DC0004
3. (0x5FBE4000 + 0x3FF80000) + 0xDFDE4000

Punkt A
0xC0D20004 + 0x72407020
| C | 0 | D | 2 | 0 | 0 | 0 | 4 |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 1100 | 0000 | 1101 | 0010 | 0000 | 0000 | 0000 | 0100 |

znak = 1
wykladnik = 10000001 = 129
mantysa = 10100100000000000000100 = 0.640625238
(-1)^s * 2^(wykladnik-bias) * 1.mantysa = -6.562501

| 7 | 2 | 4 | 0 | 7 | 0 | 2 | 0 |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 0111 | 0010 | 0100 | 0000 | 0111 | 0000 | 0010 | 0000 |

znak = 0
wykladnik = 11100100 = 228
mantysa = 10000000111000000100000 = 0.503421783447265625
(-1)^s * 2^(wykladnik-bias) * 1.mantysa = 3.811627e^30

Sprowadajac do takiego samego wykladnika otrzymujemy

1 | 10000001 | 10100100000000000000010 - przed przesunieciem pierwsza liczba
1 | 11100100 | 00000000000000000000000 - po przesunieciu(mamy same zera w mantysie, poniewaz przesunelismy w prawo o 99 miejsc)

Dodajmy liczby:

A = 1 | 11100100 | 00000000000000000000000
B = 0 | 11100100 | 10000000111000000100000

Wynik = A + B = 0 | 11100100 | 10000000111000000100000

>[name=Antoni Dąbrowski] podpunkt B

0xC0D20004 = 0b1100 0000 1101 0010 0000 0000 0000 0100

| znak | wykładnik | mantysa |
|:----:|:---------:|:-----------------------:|
| 1 | 10000001 | 10100100000000000000100 |

0x40DC0004 = 0b0100 0000 1101 1100 0000 0000 0000 0100

> [name=Piotr Witkowski] Błąd konwersji powyższej liczby
wykładnik = 30 - 127 = -97 = 0b10011110

| znak | wykładnik | mantysa |
|:----:|:---------:|:-----------------------:|
| 0 | 10000001 | 10111000000000000000100 |

1 | 10000001 | 10100100000000000000100 | +
0 | 10000001 | 10111000000000000000100 | =
0 | 01111101 | 01000000000000000000000 |

| znak | wykładnik | mantysa |
|:----:|:---------:|:-----------------------:|
| 0 | 01111101 | 01000000000000000000000 |

Punkt C

(0x5FBE4000 + 0x3FF80000) + 0xDFDE4000

5FBE4000_16 = 1,011111101111100100000000000000 * 2^30
3FF80000_16 = 1,11111111110000000000000000000 * 2^29

(0x5FBE4000 + 0x3FF80000) =
= 1,0011111101101100100000000000000 * 2^31

| znak | wykładnik | mantysa |
|------|-----------|-----------------------|
| 0 | 10100000 |00111111011011001000000|

DFDE4000_16 = 1,1011111110111100100000000000000 * 2^31

(0x5FBE4000 + 0x3FF80000) + 0xDFDE4000 =
= 1,01111111100101001000000000000000 * 2^32
= 234.577777752_d
= 0x50BFCA40

| znak | wykładnik | mantysa |
|------|-----------|-----------------------|
| 0 | 10100001 |01111111100101001000000|

> [name=Piotr Witkowski] Punkty 2) i 3) zawierają błędy. Poprawność swoich wyników można zweryfikować programem w C. Oto przykład:
>

#include<assert.h>
#include<stdio.h>
#include<stdint.h>


typedef union {
  int32_t i;
  float f;
} if_u; 


int main(void) {

printf("Rozmiar unii w bajtach: %d\n", sizeof(if_u));

 if_u a, b, c;
 a.i = 0xC0D20004;
 b.i = 0x40DC0004;

 printf("a = %f\n", a.f); 
 printf("b = %f\n", b.f); 

 c.f = a.f + b.f;
 printf("c = %f\n", c.f); 
 /*Ale uwaga, powyższy printf może nie wypisać wszystkich cyfr 
 znaczących. Dlatego lepiej wypisać wartość całkowitą c.i 
i porównać z wzorcem bitowym wyliczonym ręcznie!*/

 return 0;
}

## Konsultacje (60 minut)

:::info
W trakcie konsultacji prowadzący udostępnia kartę przeglądarki z bieżącym dokumentem w wideokonferencji. Moderuje dyskusję według własnego uznania, na przykład:
* kieruje dodatkowe pytania do osób, które dostarczyły rozwiązania,
* wymaga uzupełnienia rozwiązania przez autora lub wybraną osobę,
* umożliwia studentom zadawanie pytań,
* odpowiada na pytania w komentarzach.
:::