---
# System prepended metadata

title: 'Lista 6 (15. kwietnia 2021), grupa pwit'
tags: [pwit, ask21, ćwiczenia]

---

# Lista 6 (15. kwietnia 2021), grupa pwit

###### tags: `ask21` `ć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!**

Tabelka zawiera tylko osoby zapisane do grupy. Osoby oczekujące proszone są o wpisanie się do osobnej tabelki poniżej.


:::danger
|                      | 1   | 2   | 3   | 4   |  5  |  6  | 7   |  8  |
| --------------------:| --- | --- | --- | --- |:---:|:---:| --- |:---:|
|Wojciech Adamiec      |     |     |     |     |     |     |     |     |
|Kacper Bajkiewicz     |  X  |  X  |     |  X  |  X  |  X  |     |     |
|Bartłomiej Hildebrandt|  X  |     |     |     |  X  |  X  |     |     |
|Dominik Komła         |  X  |  X  |  X  |  X  |  X  |  X  |     |     |
|Aleksandra Kosińska   |  X  |  X  |     |  X  |     |  X  |     |     |
|Oleś Kulczewicz       |  X  |  X  |     |  X  |     |  X  |     |     |
|Damian Lukas          |  X  |  X  |     |     |     |  X  |     |     |
|Michał Mikołajczyk    |  X  |  X  |  X  |  X  |     |  X  |     |     |
|Mateusz Opala         |  X   |  X   |  X   |  X   |  X   |  X   |     |     |
|Łukasz Orawiec        |  X  |     |  X  |  X  |     |  X  |     |     |
|Szymon Pielat         |     |     |     |     |     |     |     |     |
|Łukasz Pluta          |  X  | X   |  X  |  X  |  X  |  X  |     |     |
|Kamil Puchacz         |  X  |  X  |  X  |  X  |     |  X  |     |     |
|Magdalena Rzepka      |  X  |  X  |     |==X==|     |  X  |     |     |
|Cezary Stajszczyk     |  X  |     |     |  X  |     |  X  |     |     |
|Jakub Szajner         |  X  |  X  |     |  X  |  X  |  X  |     |     |
|Bartosz Troszka       |   X  |  X   |  X   |  X   |     |   X  |     |     |
|Miłosz Urbanik        |  X  |  X  |     |  X  |  X  |  X  |     |     |



:::



## Zadanie 1
:::info
Autor: Cezary Stajszczyk
:::

**Rekord aktywacji** (ramka stosu, stack frame), to wszystkie dane odłożone na stos w wyniku wywołania procedury. Należy do nich na przykład adres powrotu (wepchnięty na stos przez `call`), rejestry **callee-saved** (o ile chcemy modyfikować ich zawartość), a także zmienne lokalne.
W przypadku poniższego kodu na stosie zapisywana jest zawartość rejestrów `%rbp` oraz `%rbx`. Ich wartość jest przywracana na końcu procedury.

```c=
puzzle:
	push  %rbp	  // zapisuje na stosie %rbp
	xorl  %eax, %eax  // zeruje %rax
	mov   %rsi, %rbp  // przenosi drugi argument do %rbp
	push  %rbx	  // zapisuje na stosie %rbx
	mov   %rdi, %rbx  // przenosi pierwszy argument do %rbx
	sub   $24,  %rsp  // zwiększa stos o 24
	test  %rdi, %rdi  // sprawdza pierwszy argument i ustawia flagi
	jle   .L1	  // skacze jeżeli pierwszy argument ≤ 0
	lea   8(%rsp), %rsi  // zapisuje adres stosu + 8 do %rsi
	lea   (%rdi,%rdi), %rdi // %rdi := 2 * %rdi
	call  puzzle	 // rekurencja
	add   8(%rsp), %rax  // dodaje coś ze stosu do %rax
	add   %rax, %rbx // dodaje %rax do %rbx
.L1:    mov   %rbx, (%rbp) // przenosi %rbx pod adres (%rbp)
	add    $24, %rsp  // zmniejsza stos
	pop    %rbx  // przywraca %rbx
	pop    %rbp  // przywraca %rbp
ret	
```
Ramka stosu:
 1. Adres powrotu
 2. %rbp
 3. %rbx
 4. -
 5. tmp
 6. -

```c=
long puzzle(long n, long *p){
    long result = 0;                   //3
    if(n > 0){                         //8, 9
        long tmp;                      //10
        result = puzzle(2*n, &tmp);    //11, 12
        result += tmp;                 //13
        n += result;                   //14
    }
    *p = n;                            //15
    return result;                     //19
}
```



## Zadanie 2
:::info
Autor: Jakub Szajner
:::
```
r11 = n
r10 = 0
rax = 0
r8 = long_min
r9 = long_max
while r10 < r11 
rcx = rsi[r10]
if rcx < r9
    r9 = rcx
if rcx < r8
    r8 = rcx
rax += rcx
r10++
rax/r11
rdi[0]=r9
rdi[1]=r8
rdi[2]=rax
return
```
```c=
struct T puzzle8(long *a, long n)
{
    long sum = 0;
    long min = LONG_MAX;
    long max = LONG_MIN;
    for( int i = 0; i < n; i++ )
    {
        if( a[i] < min )
            min = a[i];
        if( a[i] > max )
            max = a[i];
        sum += a[i];
    }
    T ans;
    ans.min=min;
    ans.max=max;
    ans.average=sum/n;
    return ans;
}

struct T{
    long min;
    long max;
    long average;
}
```


```
void puzzle8(struct T* arg1, long *a, long n)
```

## Zadanie 3
:::info
Autor: Bartosz Troszka
:::

skok pośredni - podajemy adres za pośrednictwem rejestru

samomodyfikujący się kod to kod, który zmienia swoje instrukcje.

call  = pushq %rip -> jmp 
skok pośredni - podajemy adres za pośrednictwem rejestru
samomodyfikujący się kod to kod, który zmienia swoje instrukcje.

Jak zastąpić jmp?

call 0x4006f8(,%rsi,8)
w miejscu 0x4006f8+8*%rsi musimy użyć pop r9
ponieważ call wywołuje przed jmp pushq %rip 

jak zastąpić jump bez call:

pushq 0x4006f8(,%rsi,8)
-----popq %rip - źle
ret

## Zadanie 4
:::info
Autor: Miłosz Urbanik
:::

- **Konwencja wołania prodedur** - ustandaryzowany zbiór zasad regulujących w jaki sposób należy przekazywać parametry do funkcji, zwracać wyniki funkcji, jak wywoływać funkcję, jak funkcja zapewnia utrzymywanie stosu i swojej ramki stosu.

ABI V wymaga aby przed użyciem instrukcji `call`. Adres wierzchu stosu (rejestr rsp) był wyrównany do 16. Jeśli używamy typów `__m256`/`__m512` to adres wierzchu stosu ma być wyrównany do 32/64.

Rejestry zachowywane przez funkcję wywoływaną: rbx, rsp, rbp, r12, r13, r14, r15

Argumenty funkcji: rdi, rsi, rdx, rcx, r8, r9
Jeśli wywoływana funkcja przyjmuje więcej argumentów, to funkcja wywołująca musi przygotować miejsce na dodatkowe argumenty w swojej ramce stosu.


Kod z zadania zawierający błędy.

```=
M:  pushq %rdi
    test1 %rdi, %rdi
    je .L2
    leaq -1(%rdi), %rdi
    call M 
    movq %rax, %rdi
    call F
    movq (%rsp), %rdi # przed wyjściem z funkcji nie zwinięty stos
    subq %rax, %rdi
.L2 movq %rdi, %rax
    ret

F:  testq %rdi, %rdi
    je .L3
    movq %rdi, %r12 # callee saved register r12, naruszony
    leaq -1(%rdi), %rdi
    call F          # stack pointer niewyrównany przed callem
    movq %rax, %rdi
    call M
    subq %rax, %r12
    movq %r12, %rax
    ret
.L3:movl $1, %eax
    ret
```

Próba poprawienia błędów konwencji wołania funkcji:

```=
M:  pushq %rdi
    test1 %rdi, %rdi
    je .L2
    leaq -1(%rdi), %rdi
    call M 
    movq %rax, %rdi
    call F
    movq (%rsp), %rdi # do rdi zapisna zawartość wierzchu stosu
    subq %rax, %rdi
.L2 movq %rdi, %rax
    addq $8, %rsp # cofnięty adres wierzchu stosu
    ret

F:  testq %rdi, %rdi
    je .L3
    push %r12 # zapisany r12, wskaźnik rsp przesunięty o 8
    movq %rdi, %r12
    leaq -1(%rdi), %rdi
    call F  
    movq %rax, %rdi
    call M
    subq %rax, %r12
    movq %r12, %rax
    pop %r12
    ret
.L3:movl $1, %eax
    ret
```

## Zadanie 5
:::info
Autor: Łukasz Pluta
:::

```=
00000000000005fa <aframe>:
 5fa:	55                   	push   %rbp
 5fb:	48 89 e5             	mov    %rsp,%rbp
 5fe:	48 83 ec 10          	sub    $0x10,%rsp
 602:	4c 8d 0c fd 00 00 00 	lea    0x0(,%rdi,8),%r9
 609:	00 
 60a:	49 8d 41 1e          	lea    0x1e(%r9),%rax
 60e:	48 83 e0 f0          	and    $0xfffffffffffffff0,%rax
 612:	48 29 c4             	sub    %rax,%rsp
 615:	4c 8d 44 24 0f       	lea    0xf(%rsp),%r8
 61a:	49 83 e0 f0          	and    $0xfffffffffffffff0,%r8
 61e:	4c 89 c1             	mov    %r8,%rcx
 621:	48 8d 45 f8          	lea    -0x8(%rbp),%rax
 625:	4b 89 44 08 f8       	mov    %rax,-0x8(%r8,%r9,1)
 62a:	48 c7 45 f8 00 00 00 	movq   $0x0,-0x8(%rbp)
 631:	00 
 632:	eb 09                	jmp    63d <aframe+0x43>
 634:	48 89 14 c1          	mov    %rdx,(%rcx,%rax,8)
 638:	48 83 45 f8 01       	addq   $0x1,-0x8(%rbp)
 63d:	48 8b 45 f8          	mov    -0x8(%rbp),%rax
 641:	48 39 f8             	cmp    %rdi,%rax
 644:	7c ee                	jl     634 <aframe+0x3a>
 646:	49 8b 04 f0          	mov    (%r8,%rsi,8),%rax
 64a:	48 8b 00             	mov    (%rax),%rax
 64d:	c9                   	leaveq 
 64e:	c3                   	retq   

```
Jednostką translacji nazywany jest plik źródłowy (w C lub C++) razem z plikami włączonymi w wyniku działania dyrektywy #include

Funkcja alloca() alokuje przestrzeń w ramce stosu funkcji wołajacej. Miejsce to jest autmatycznie zwalniane przy wyjsciu z funkcji wywolujacej alloca().

Alokacja odbywa się w liniach 60a - 612, a dealokacja w 64d.

Leave przesuwa rejestr %rsp do %rbp oraz przywraca wartość %rbp z funkcji wołającej zdejmując tę wartość ze stosu.


```
pwit@wielebny:~/Praca/zajecia/ASK21/Lista 6$ objdump -d alloca-ex.o

alloca-ex.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <aframe>:
   0: 55                    push   %rbp
   1: 48 89 e5              mov    %rsp,%rbp
   4: 48 83 ec 10          sub    $0x10,%rsp
   8: 4c 8d 0c fd 00 00 00 lea    0x0(,%rdi,8),%r9
   f: 00
  10: 49 8d 41 17          lea    0x17(%r9),%rax
  14: 48 83 e0 f0          and    $0xfffffffffffffff0,%rax
  18: 48 29 c4              sub    %rax,%rsp
  1b: 4c 8d 44 24 0f        lea    0xf(%rsp),%r8
  20: 49 83 e0 f0          and    $0xfffffffffffffff0,%r8
  24: 4c 89 c1              mov    %r8,%rcx
  27: 48 8d 45 f8          lea    -0x8(%rbp),%rax
  2b: 4b 89 44 08 f8        mov    %rax,-0x8(%r8,%r9,1)
  30: 48 c7 45 f8 00 00 00 movq   $0x0,-0x8(%rbp)
  37: 00
  38: 48 8b 45 f8          mov    -0x8(%rbp),%rax
  3c: 48 39 f8              cmp    %rdi,%rax
  3f: 7d 0b                jge    4c <aframe+0x4c>
  41: 48 89 14 c1          mov    %rdx,(%rcx,%rax,8)
  45: 48 83 45 f8 01        addq   $0x1,-0x8(%rbp)
  4a: eb ec                jmp    38 <aframe+0x38>
  4c: 49 8b 04 f0          mov    (%r8,%rsi,8),%rax
  50: 48 8b 00              mov    (%rax),%rax
  53: c9                    leaveq
  54: c3                    retq 
 ``` 


To zadanie wyedytuje PWit:

-----
|adres powrotu |
|-----|
|rbp |
| .   |
| .  |  

wiersz 7-9:

rax = (8n + 16 + 7) & -16

(-16) = 0b11111111110000

Dwa przypadki:

n = 2k albo n = 2k +1


n = 2k:   rax = (16k + 16 + 7) & -16 = 16k + 16 = 8n + 16
n = 2k+1: rax = 16k + 16 + 15) & -16 = 16k + 16 = 8n + 8

-----
|adres powrotu |
|rbp |
| i   | <- to jest adres komórki liczony w wierszu 12
|  |      <- adres tej komórki jest podzielny przez 16, to jest pierwsza komórka za końcem tablicy       
| p[n-1] koniec  |       -
| .  |
| .  |              8n + 16 lub 8n + 8
| .  | 
| .  |
| .  |
| początek| <- RSP     -

11: rdx = (rsp + 15) & -16

n = 2k   : (16k+16 + 15) & -16 = 16k + 16 = 8n + 16
n = 2k+1 : (16k + 8 + 15) & -16 = (16k + 16 + 7) & -16 = 16k + 16 = 8n + 8;




























## Zadanie 6
:::info
Autor: Dominik Komła
:::

```=
puzzle5:
    subq    $24, %rsp      //przesuwamy koniec stosu o 24 bajty
    movq    %rsp, %rdi     //zapisujemy do rdi adres gory stosu
    call    readlong       //wywolujemy readlong z argumentem %rdi
    leaq    8(%rsp), %rdi  //zapisujemy do rdi adres 2 z gory argumentu ze stosu
    call    readlong       //wywolujemy readlong z argumentem %rdi
    movq    (%rsp), %rax   //przenosimy wartosc tego co zwrocilo nam pierwsze wywolanie readlonga do raxa
    cqto
    idivq   8(%rsp)        //dzielimy to co zwrocilo nam pierwsze wywolanie readlonga przez to co zwrocilo drugie
    xorl    %eax, %eax     //zerujemy raxa
    testq   %rdx, %rdx     //sprawdzamy czy x % y == 0
    sete    %al            //i zapisujemy wynik do raxa
    addq    $24, %rsp      //zwalniamy zaalokowane miejsce
    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 puzzle5(void){
    long x, y;
    readlong(&x);
    readlong(&y);
    return x%y == 0;
}
```



## Zadanie 7
:::info
Autor: Piotr Witkowski
:::


## Zadanie 8
:::info
Autor: Piotr Witkowski
:::



