# Ćwiczenia 7, grupa śr. 17-19, 5 kwietnia 2023
###### tags: `ASK23` `ć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!**
:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| ----------------------:| --- | --- | --- | --- | --- | --- | --- | --- |
| Mikołaj Balwicki | | | | | | | | |
| Kamila Goszcz | X |==X==| | X | | X | | |
| Mateusz Materek |==X==| | | | | | | |
| Mikołaj Łabędzki | | | | | | | | |
:::
:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::
## Zadanie 1
:::success
Autor: Mateusz Materek
:::
```=
long pointless(long n, long *p)
1 pointless:
2 pushq %r14 // %r14 na stos!
3 pushq %rbx // %rbx na stos!
4 pushq %rax // %rax na stos!
5 movq %rsi, %r14 // %r14 := *p
6 movq %rdi, %rbx // %rbx := n
7 testq %rdi, %rdi // sprawdź n, ustaw flagi
8 jle .L1 // skocz do L1 jeśli n <= 0
9 leaq (%rbx,%rbx), %rdi // %rdi := 2 * %rbx (2*n)
10 movq %rsp, %rsi // %rsi := %rsp (stack_pointer)
11 callq pointless // pointless(2*n, stack_pointer)
12 addq (%rsp), %rax // %rax += (%rsp) - dodaj wartość z końca stosu
13 jmp .L3 // skacz do L3
14 .L1: xorl %eax, %eax // %eax := 0 - %rax := 0
15 .L3: addq %rax, %rbx // %rbx += %rax
16 movq %rbx, (%r14) // (%r14) := %rbx
17 addq $8, %rsp // %rsp += 8 - obniż koniec stosu
18 popq %rbx // odtwórz ze stosu %rbx
19 popq %r14 // odtwórz ze stosu $r14
20 ret // koniec
long pointless(long n, long *p){
long result = 0;
if(n > 0){
long temp;
result = pointless(2*n, &temp);
result += temp;
}
n += result;
*p = n;
return result;
}
```
Rekord aktywacji:
1. adres powrotu
2. %r14
3. %rbx
4. %rax
Dlaczego wyrównanie do 16?
*Because some SSE instructions require such alignment and in general it costs less to maintain the alignment than to re-align everywhere you want to use those. Also even when not required, you do not want to accidentally cross cache lines.*
## Zadanie 2
:::success
Autor: Kamila Goszcz
:::
```c=
puzzle2:
movq %rdx, %r11 // %r11 = n
xorl %r10d, %r10d
xorl %eax, %eax
movabsq $LONG_MIN, %r8 // %r8 = LONG_MIN
movasbq $LONG_MAX, %r9 // %r9 = LONG_MAX
.L2: cmpq %r11, %r10
jge .L5 // if (%r10 - %r11 >= 0) goto .L5
movq (%rsi,%r10,8), %rcx // %rcx = a[i]
cmpq %rcx, %r9
cmovg %rcx, %r9 // if (%r9 - %rcx > 0) %r9 <- %rcx
cmpq %rcx, %r8
cmovl %rcx, %r8 // if (%r8 - %rcx < 0) %r8 <- %rcx
addq %rcx, %rax // %rax += rcx
incq %r10 // r10 += 1
jmp .L2
.L5: cqto
movq %r9, (%rdi) // %rdi: %r9
idivq %r11 // %rax /= %r11
movq %r8, 8(%rdi) // %rdi: %r9, r8
movq %rax, 16(%rdi) // %rdi: %r9, r8, %rax
movq %rdi, %rax // %rax = %rdi
ret
```
### Struktura T:
```c=
struct T {
long max;
long min;
long avg;
};
```
### Kod w C:
```c=
// %rdi %rsi %rdx
struct T puzzle2(long* a, long n){
struct T result;
long sum = 0;
long max = LONG_MIN;
long min = LONG_MAX;
for(int i = 0; i < n; i++) {
if(min < a[i]) min = a[i];
if(max > a[i]) max = a[i];
sum += a[i];
}
sum /= n;
result.min = min;
result.max = max;
result.average = sum;
return result;
}
```
### Przewidywana sygnatura:
```c
struct T* puzzle8(struct T* ret, long* a, long n)
```
## Zadanie 3
:::danger
Autor:
:::
```
jmpq *0x4006f8(,%rsi,8)
movq 0x4006f8(,%rsi,8), r14
push r14
ret
albo:
push 0x4006f8(,%rsi,8)
ret
call *(%rdi,%rsi,8)
push L(%rip)
push (%rdi,%rsi,8)
ret
L:
```
## Zadanie 4
:::success
Autor: Kamila Goszcz
:::
```clike=
M: pushq %rdi // zapisujemy n na stosie
testq %rdi, %rdi
je .L2 // jeśli n==0 (ZF==1) skocz do return n
leaq -1(%rdi), %rdi // przekazujemy n-1 jako argument
call M // wywołanie t1 = M(n-1)
movq %rax, %rdi // przekazujemy wynik jako parametr
call F // wywołanie t2 = F(t1) = F(M(n-1))
movq (%rsp), %rdi // wyciągamy n ze stosu
subq %rax, %rdi // n = n - t2
.L2: movq %rdi, %rax // zwracamy n
ret
```
```clike=
F: testq %rdi, %rdi
je .L3 // jeśli n == 0 return 1
movq %rdi, %r12 // zapisujemy wartość n w r12
leaq -1(%rdi), %rdi // przekazujemy n-1 jako argument
call F // wywołanie t1 = F(n-1)
movq %rax, %rdi // t2 = F(n-1) przekazujemy jako argument
call M // wywołanie M(t2)
subq %rax, %r12 // n = n - temp2
movq %r12, %rax // zwracamy n
ret
L3: movl $1, %eax // zwracamy 1
ret
```
### Konwencja wołania procedur
* przy wywołaniu procedury `%rsp` musi być podzielny przez `16`
* (**caller saved**) -- jeśli procedura wywołująca (**caller**) korzysta z rejestrów `%rax`, `%rdi`, `%rsi`, `%rdx`, `%rcx`, `%r8`, ..., `%r11`, to musi zapamiętywać stan tych rejestrów przed wywołanienm innej procedury, która z nich korzysta, ponieważ procedura wołana (**callee**) może zmodyfikować zawartość tych rejestrów bez ich zapisu.
* (**callee saved**) -- jeśli procedura wołana (**callee**) chce skorzystać z rejestru `%rbx`, `%r12`, `%r13`, `%r14`, `%rbp`, to musi zapamiętać ich wartości przed użyciem, a następnie przywrócić ich wartość przed zakończeniem swojego działania.
* Procedura przed zakończeniem musi oczywiścić stos z wartości, które na niego wstawiła.
### Pierwszy błąd
W obrębie funkcji `M` odkładamy wartość na stos, ale nigdy nie zostaje ona z niego zdjęta, zatem adres powrotu z funkcji jest błędny (wczyta pozostawioną wartość, zamiast adresu return).
**Poprawka**
```clike=
M: pushq %rdi
testq %rdi, %rdi
je .L2
leaq -1(%rdi), %rdi
call M
movq %rax, %rdi
call F
movq (%rsp), %rdi
subq %rax, %rdi
.L2: movq %rdi, %rax
popq %rdi
ret
```
#### Drugi błąd
Funkcja `F` korzysta z rejestru `%r12`, by zachować wartość `n` z poprzedniego wywołania. Jest to rejestr `callee saved`, wiec musimy uważać, by zapamiętać wartość tego rejestru dla funcji wołającej (`caller`) i przy zakończeniu funkcji wołanej (`callee`), należy ją przywrócić.
**Poprawka**
```clike=
F: testq %rdi, %rdi
je .L3
pushq %r12
movq %rdi, %r12
leaq -1(%rdi), %rdi
call F
movq %rax, %rdi
call M
subq %rax, %r12
movq %r12, %rax
popq %r12
ret
L3: movl $1, %eax
ret
```
### Kod w C:
```c=
long M (long x) {
if (x) {
long temp = x - 1;
temp = M(temp);
temp = x;
x -= F(temp);
}
return x
}
long F (long y) {
if (y == 0) return 1
else {
long temp = y - 1;
temp = F(temp);
y -= M(temp);
return y
}
}
```
## Zadanie 5
:::danger
Autor:
:::
return address <- rsp
stare rbp <- rsp
.
.
. <- rsp = rsp - 16
rax = (8*n + 15) & 0xff...ff0;
.
.
.
.
. <- rsp = rsp - rax // rsp jest podzielne przez 16
## Zadanie 6
:::success
Autor: Kamila Goszcz
:::
```c=
puzzle6:
subq $24, %rsp // zmniejszamy wskaźnik na stos o 24 bajty (alokujemy miejsce na stosie)
movq %rsp, %rdi
call readlong // wywołujemy readlong, przekazujemy mu wskaźnik na stos
leaq 8(%rsp), %rdi
call readlong // wywołujemy readlong, przekazujemy mu wskaźnik na kolejny element na stosie
movq (%rsp), %rax // przenosimy do raxa wynik pierwszego wywołania readlonga
cqto
idivq 8(%rsp) // dzielimy wynik pierwszego wywolania readlonga przez wynik drugiego (część całkowitą otrzymujemy w raxie, a resztę z dzielenia w rdx)
xorl %eax, %eax
testq %rdx, %rdx // ustawiamy ZF na 1, gdy nie otrzymaliśmy reszty, 0 wpp
sete %al // zapisujemy najmniej znaczący bit wartością flagi ZF
addq $24, %rsp // zwiększamy wskaźnik na stos o 24 bajty (zwalniamy miejsce na stosie)
ret
```
|Rekordy aktywacji funkcji |rozmiar|
|---------------------------------|-------|
|return address |8 |
|puste |8 |
|long (readlong z param. 8(%rsp)) |8 |
|long (readlong z param. %rsp) |8 |
```c=
void readlong(long *x);
long puzzle6(void){
long x, y;
readlong(&x);
readlong(&y);
return x % y == 0;
}
```
## Zadanie 7
:::danger
Autor:
:::
## Zadanie 8
:::danger
Autor:
:::
Google Drive
Gist
Clipboard
Sign in with Wallet
