# Lista 7 (22.04.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 |==X==| X | X | X | | X | | |
|Kacper Bajkiewicz | X | X | X | X | | X | | |
|Bartłomiej Hildebrandt| X | X | X |==X==| | X | | |
|Dominik Komła | X | X | X | X | | X | | |
|Aleksandra Kosińska | X | X | X | X | | | | |
|Oleś Kulcewicz | X | X | | X | | | | |
|Damian Lukas | X | X | | X | | | | |
|Michał Mikołajczyk | X | X | X | X | | | | |
|Mateusz Opala | X | X | X | X | | X | | |
|Łukasz Orawiec | X | X | X | X | | X | | |
|Szymon Pielat | X |==X==| X | X | | X | | |
|Łukasz Pluta | X | X | X | X | | X | | |
|Kamil Puchacz | X | X | X | X | X | X | | |
|Magdalena Rzepka | X | X | X | X | | | | |
|Cezary Stajszczyk | X | X | X | X | | | | |
|Jakub Szajner | X | X | X | X | | X | | |
|Bartosz Troszka | X | X | X | X | | | | |
|Miłosz Urbanik | X | X | X | X | X | | | |

Deklaracje zadań 7 i 8 z listy 6:

| | 7 | 8 |
| --------------------:| --- |:---:|
| ... | | |
:::

## Zadanie 1
:::info
Autor: Wojciech Adamiec
:::
:::info
:::

Zauważmy, że chcąc dostać się do $t$ w strukturze $str2$ wykonujemy `move` na adresie `(%rsi + 8)`. Oznacza to, że `char array[B]` ma co najwyżej 8 bajtów. Jednocześnie wiemy, że gdyby ten array miał 4 lub mniej bajtów to $t$ nie musiałoby znajdować się na 8 bajcie, tylko na 4 (wyrównanie dla inta to 4 bajty).

Z tego wnioskujemy, że $B \in \{5, 6, 7, 8\}$.

Teraz zobaczmy na `movq %rax, 184(%rdi)`, który odpowiada dostaniu się do `long y` w strukturze $str1$. Wiemy, że wyrównanie jest mniejsze od 8 bajtów (long) i jednocześnie wiemy, że rozmiar `int x[A][B]` jest równy $4\cdot A \cdot B$.

Oznacza to, że rozmiar tej tablicy jest z przedziału $178 \leq 4 \cdot A \cdot B \leq 184$. Co po przekształceniu daje $45 \leq A \cdot B \leq 46$. Wiedząc, że $A, B$ są naturalne wnioskujemy, że $AB \in \{45, 46\}$.

Mamy teraz dwa więzy:

1. $B \in \{5, 6, 7, 8\}$
2. $AB \in \{45, 46\}$

Zachłannie szukamy rozwiązania i okazuje się, że jedyne rozwiązanie mamy dla:

1. $A = 9$
2. $B = 5$

Co rozwiązuje nasze zadanie.

## Zadanie 2
:::info
Autor: Szymon Pielat
:::

long A[R][S][T];
// i - %rdi, j - %rsi, k - %rdx, *dest - %rcx
long store_elem(long i, long j,long k, long *dest)
{
    *dest = A[i][j][k];
    return sizeof(A);
}

store_elem:
    leaq (%rsi,%rsi,2),%rax   // %rax = 3*j
    leaq (%rsi,%rax,4),%rax   // %rax = (4*3+1)*j = 13j
    movq %rdi,%rsi            // %rsi = i
    salq $6,%rsi              // %rsi = 64*i
    addq %rsi,%rdi            // %rdi = 65*i
    addq %rax,%rdi            // %rdi = 65i + 13j
    addq %rdi,%rdx            // %rdx = 65i + 13j + k
    movq A(,%rdx,8),%rax      // %rax = A + 8(65i + 13j + k)
    movq %rax,(%rcx)
    movq $3640,%rax
    ret

Z kodu możemy od razu znamy wielkość `long A[R][S][T]`, bo funkcja `store_elem` zwraca ją nam zwraca: $3640$. Jeśli `A` ma $3640$ bajtów, to zawiera $\frac{3640}{8} = 455$ elementów typu `long`.

$A + 8(65i + 13j + k)$ określa nam przesunięcie względem A aby dostać się do szukanej komórki. Z wykładu wiemy, że $(i\cdot S \cdot T + j\cdot T + k)$ jest wzorem na te przesunięcie. Czyli:

$(i\cdot S \cdot T + j\cdot T + k) = (65i + 13j + k)$.

Zatem:
- $T = 13$,
- $S \cdot T = 65 \implies S = 65 \div 13 = 5$,
- $R = \frac{455}{13 \cdot 5} = 7$.

## Zadanie 3
:::info
Autor: Cezary Stajszczyk
:::

#define CNT 7

typedef struct {
	int first;
	a_struct a[CNT];
	int last;
} b_struct;

void test (long i, b_struct *bp) {
	int n = bp->first + bp->last;  // 2, 3
	a_struct *ap = &bp->a[i];  // 4, 5, 6
	ap->x[ap->idx] = n;
}

`%rdi := i, %rsi := *bp`

test:
	movl	0x120(%rsi),%ecx    // %ecx := bp->last
	addl	(%rsi),%ecx         // %ecx += bp->first
	leaq	(%rdi,%rdi,4),%rax  // %rax := 5 * i
	leaq	(%rsi,%rax,8),%rax  // %rax := bp + 40 * i
	movq	0x8(%rax),%rdx      // %rdx := bp + 40 * i + 8
	movslq	%ecx,%rcx
	movq	%rcx,0x10(%rax,%rdx,8) // *
	retq
//* 0x10(%rax,%rdx,8) = %rax + 8 * %rdx + 16 = bp + 40*i + 8*%rdx + 16
//  bp + 8 + 40*i + 8*idx + 8

typedef struct {
	long idx;
	long x[4];
} a_struct;

## Zadanie 4
:::info
Autor: Magdalena Rzepka
:::

union elem // razem 16 bajtów 
{
 struct //razem 16 bajtów
 {
 long *p; //8 bajtów
 long y;  // 8 bajtów
 } e1;
 struct // razem 16 bajtów
 {
 long x; // 8 bajtów
 union elem *next; //8 bajtów
 } e2;
 };

Jedna instancja union korzysta tylko z jednej składowej a rozmiar to rozmiar większej składowej.

proc:
 movq 8(%rdi),%rax  // %rax = *zm = ele->e2.next //+8 czyli skipujemy x
 movq (%rax),%rdx   // %rdx = zm->e1.p //przechodzimy wgłąb
 movq (%rdx),%rdx   // %rdx = *(zm->e1.p) 
 subq 8(%rax),%rdx  // %rdx = *(zm->e1.p) - zm->e1.y //+8 czyli skipujemy *p w drugim argumencie
 movq %rdx,(%rdi)   // ele->x = *(zm->e1.p) - zm->e1.y
 ret

union elem *proc(union elem *ele)
{
union elem *zm = ele->e2.next;
ele->e2.x = *(zm->e1.p) - zm->e1.y;
return zm;
}

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

Definicje struktur:

typedef struct A{
    long u[2];
    long *v;
}SA;

typedef struct B{
    long p[2];
    long q;
}SB;

Kod z zadania:

#SB eval(SA s)
eval:
    movq %rdi, %rax     //kopia adresu do rax - adres zwracanej struktury res
    movq 16(%rsp), %rcx // long %rcx = s.u[1]
    movq 24(%rsp), %rdx // long* %rdx = s.v
    movq (%rdx),   %rsi // long %rsi = *(s.v)
    movq %rcx, %rdx     // %rdx = s.u[1]
    imulq %rsi, %rdx    // %rdx = s.u[1] * *(s.v)
    movq %rdx, (%rdi)   // res.p[0] = s.u[1] * *(s.v)
    movq 8(%rsp), %rdx  // long %rdx = s.u[0]
    movq %rdx, %rdi     // long %rdi = s.u[0]
    subq %rsi, %rdi     // %rdi = s.u[0] - *(s.v)
    movq %rdi, 8(%rax)  // res.p[1] = s.u[0] - *s.v
    subq %rcx, %rdx     // %rdx = s.u[0] - s.u[1]
    movq %rdx, 16(%rax) // res.q = s.u[0] - s.u[1]
    ret

# long wrap(long x, long y, long z)
wrap:
    subq $72, %rsp //rezerwacja 72 bajtów
    movq %rdx, (%rsp) //na wierzch stosu zapisz z
    movq %rsp, %rdx // kopia wskaźnika wierzchu stosu do %rdx
    leaq 8(%rsp), %rax // %rax = %rsp + 8 - adres wynikowego structa
    pushq %rdx  //wepchij na stos wskaźnik na wierzchołek stosu - &z
    pushq %rsi  //wepchij y 
    pushq %rdi  //wepchij x
    movq %rax, %rdi // %rdi =  adres wynikowego structa
    call eval   
    movq 40(%rsp), %rax //po powrocia %rsp wskazuje na ostatnio wepchnięte x, czyli rax = res.p[1]
                        //ze structa zwróconego przez eval
    addq 32(%rsp), %rax //%rax = res.p[0] + res.p[1]
    imulq 48(%rsp), %rax //%rax = (res.p[0] + res.p[1])*res.q
    addq $96, %rsp //zwolnienie trzech wepchniętych wartości i rezerwacji 72 bajtów
    ret

Procedury przetłumaczone do C:

SB eval(SA s){
    SB result;
    result.p[0] = s.u[1] * *s.v;
    result.p[1] = s.u[0] - *s.v;
    result.q = s.u[0] - s.u[1];
    return result;
}

long wrap(long x, long y, long z){
    SA tempStruct;
    long tempZ = z;
    tempStruct.u[0] = x;
    tempStruct.u[1] = y;
    tempStruct.v = &tempZ;
    SB res = eval(tempStruct);
    return (res.p[0] + res.p[1]) * res.q
}

Zawartość ramki stosu procedury `wrap` przed wywołaniem `eval`

|adres|zawartość |
|-----|--------- |
|72 | adres powrotu |
|8 | rezultat eval (zarezerwowany adres, nic jeszcze nie zapisane) |
|0 | z |
|-8 |&z |
|-16 |y |
|-24 |x |

`rsp` wskazuje na -24

## Zadanie 6
:::info
Autor: Kamil Puchacz
:::

:::info
Zadanie 6. Poniżej widniej kod procedury o sygnaturze «float puzzle6(struct P *, float)». Wyznacz definicję typu «struct P». Przetłumacz tę procedurę na język C i wyjaśnij jednym zdaniem co robi.
:::

puzzle6:
    movq    (%rdi), %rdx
    leaq    8(%rdi), %rcx
    xorl    %eax, %eax                       //rax = 0
    vxorps  %xmm1, %xmm1, %xmm1              //zerujemy rejestr xmm1
    vmovss  .LC1(%rip), %xmm2                // xmm2 = 1 (z 20 linijki)
.L2: 
    cmpq    %rdx, %rax
    jge    .L5                               // jesli x>=0 -> skaczemy do .L5
    vfmadd231ss (%rcx,%rax,4), %xmm2, %xmm1 // robimy działanie xmm1 = (%rcx,%rax,4) * xmm2 + xmm1
    incq    %rax                            // rax++
    vmulss  %xmm0, %xmm2, %xmm2             // xmm2= xmm0 * xmm2, inaczej xmm2 = p * xmm2
    jmp     .L2
.L5:  
    vmovaps %xmm1, %xmm0                   // xmm0 = xmm1
    
    ret
.LC1: 
    .long   0x3f800000                    // 1 (stała, float)
                                            //konwerter hex na float: https://gregstoll.com/~gregstoll/floattohex/

typedef struct P{
    long n;
    float a[];
}

float puzzle6(struct P *s, float p){
    long n = s->n;
    float *a = s->a;
    float acc = 0;             // xmm1
    float x = 1;               // xmm2
    
    for(long i = 0; i < n; i++){
        acc += a[i] * x;   // z 11 linii asm
        x *= p;               // z 13 linii asm
    }
    return acc;
}

// puzzle6 - oblicza wartosc wielomianu dla argumentu p, stopień(n) oraz wspołczynniki (*p) są przechowywane w struct P * s.

## Zadanie 7
:::info
Autor:
:::

## Zadanie 8
:::info
Autor:
:::