---
# System prepended metadata

title: 'Ćwiczenia 7, grupa śr. 17-19, 5 kwietnia 2023'
tags: [pwit, ćwiczenia, ASK23]

---

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

```=
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.*

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

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

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

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