---
# System prepended metadata

title: 'Lista 7 (22 kwietnia 2021), grupa KBa'
tags: [kba, ask21, ćwiczenia]

---

# Lista 7 (22 kwietnia 2021), grupa KBa

###### tags: `ask21` `ćwiczenia` `kba`

## 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(B) |
| --------------------:| --- | ----- | --- | --- | --- | --- | --- | ---- |
|        Andriy Bernad |  X  |   X   |  X  |  X  |  X  |==X==|     |      | 6
|     Wojciech	Bogucki|  X  |   X   |  X  |  X  |  X  |  X  |     |      | 6
|         Michał Doros |  X  |   X   |  X  |  X  |  X  |  X  |     |      | 6
|        Marko Golovko |     |       |     |     |     |     |     |      | 0
|    Magdalena Jarecka | X   | ==X== | X   | X   |  X  | X   |     |      | 6
|        Szymon Jędras | X   | X     | X   | X   | X   |     |     |      | 5
|     Heorhii Karpenko |  X  |   X   |  X  |  X  |     |  X  |     |      | 5
|    Szymon Kosakowski | X   |   X   |     |     |     |     |     |      | 2
|      Izabella Kozioł |     |       |     |     |     |     |     |      | 0
|   Franciszek Malinka | X   | X     | X   | X   | X   |     | X   |      | 6
|         Filip Pazera | X   | X     | X   | X   | X   |     |     |      | 5
|    Franciszek Pindel |  X  |   X   |  X  |  X  |  X  |  X  |  X  |      | 7
|     Kacper Puchalski | X   |    X  |  X  |     |     |     |     |      | 3
|       Kacper Solecki |  X  |   X   |  X  |  X  |  X  |  X  |     |      | 6
|      Andrzej Tkaczyk |  X  |   X   |  X  |  X  |  X  |     |  X  |      | 6
|    Łukasz Wasilewski |  X  |   X   |  X  |  X  |     |     |     |      | 4
| Vladyslav Yablonskyi |     |   X   |  X  |==X==|     |     |     |      | 3
|           Adam Zyzik |  X  |   X   |     |     |     |     |     |      | 2
:::

## Zadanie 1

:::danger
Autor: Łukasz Wasilewski
:::

```=
typedef struct {
  int x[A][B];
  long y;
} str1;
```

| pole | offsetof | sizeof | alignof |
|:----:|:--------:|:------:|:-------:|
|   x  |  0       | `A*B*4`|       4 |
| pad0  |  180     |     4 |       1 |
|   y  |  alignup(`A*B*4`,8) = 184 | 8 | 8 |

Poniżej rozpisuję jak "wygląda" str1. Jeżeli nie wiem ile bajtów zajmuje 
dane pole piszę wzór na liczbę tych bajtów, jeżeli zaś wiem, że dane 
pole zajmuje n bajtów zapisuję n razy |x| gdzie x to nazwa pola
`A*B*4` bajty (+4 jeżeli A i B są nieparzyste)|y|y|y|y|y|y|y|y|

```=
typedef struct {
  char array[B];
  int t;
  short s[A];
  long u;
} str2;

sufit(B/4)*4 bajty |t|t|t|t|A*2 dopełnione do pełnej 8|u|u|u|u|u|u|u|u|
```

| pole | offsetof | sizeof | alignof |
|:----:|:--------:|:------:|:-------:|
| array |  0      | B=5 |       1 |
|  pad0 |  5      | 3 | 1 |
| t     |  alignup(B,4) = 8 | 4 |       4 |
| s     | offsetof(t) + 4 | 2 * A | 2 |
| pad1 |  offsetof(t) + 2 * A | 2 | 1 |
| u     | alignup(offsetof(s) + sizeof(s), 8) = 32 | 8 | 8 |

```=
void set_val(str1 *p, str2 *q) {//%rdi -p %rsi= q
  long v1 = q->t;
  long v2 = q->u;
  p->y = v1 + v2;
}
```

```=
set_val:
  movslq 8(%rsi),%rax
  addq 32(%rsi),%rax
  movq %rax,184(%rdi)
ret
```

sufit(B/4)*4 = 8
sufit(B/4) =2
5≤B≤8

184 = A * B * 4 (+4 jeżeli A i B są nieparzyste)
gdyby A i B były nieparzyste to A*B*4 = 180
A* B = 45
więc B=5, zaś A = 9
wtedy str2 ma postać
```
array|array|array|array|array|array|array|array|t|t|t|t|s|s|s|s|s|s|s|s|s|s|s|s|s|s|s|s|s|s| | |u|u|u|u|u|u|u|u|
```
i wtedy ustawienie wskaźnika na u jest równoważne ze zwięœkszeniem wskaźnika na strukturę o 32, czyli "wszystko się zgadza"

jeżeli A lub B są parzyste to 184 = A*B
czyli B=8, zaś A=23 czyli, żeby przejść do pola u trzeba dodać do wskaźnika coś większego niż 32, czyli A=9, B=5

## Zadanie 2

:::info
Autor: Magdalena Jarecka
:::

```c=
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
```
Funkcja store_elem zwraca nam wielkość *A*. Odpowiada za to fragment `movq $3640,%rax`. Tak więc rozmiar *A* wynosi 3640 a skoro jest typu long to będzie przetrzymywać 455 elementów. Teraz (tak jak w komentarzach powyżej) możemy podstawić do równania.
$A + (i\cdot S \cdot T \cdot 8 + j\cdot T \cdot 8 + k\cdot 8) = A + 8\cdot (i\cdot S \cdot T + j\cdot T + k)$
$(i\cdot S \cdot T + j\cdot T + k)$ = $(65 \cdot i + 13\cdot j + k)$
$T = 13$
$(i\cdot S \cdot 13 + j\cdot 13 + k)$ = $(65 \cdot i + 13\cdot j + k)$
$S = \frac{65}{13} = 5$
$(i\cdot 65 + j\cdot 13 + k)$ = $(65 \cdot i + 13\cdot j + k)]$
$R = \frac{455}{5 \cdot 13} = 7$ 



## Zadanie 3

:::info
Autor: Michał Doros
:::

```c=
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;
  a_struct *ap = &bp->a[i];
  ap->x[ap->idx] = n;
}
```

```asm=
test:
movl 0x120(%rsi),%ecx       #last do ecx
addl (%rsi),%ecx            #last + first do ecx
leaq (%rdi,%rdi,4),%rax     #
leaq (%rsi,%rax,8),%rax     #bp + 40i sizeof(a) = 40
movq 0x8(%rax),%rdx         #bp + 40i + 8 wskazuje na ap czyli też jego pierwszy element: na idx
movslq %ecx,%rcx            #rozszerzenie do 64 bitow
movq %rcx,0x10(%rax,%rdx,8) 
#rax + 16 to początek tablicy x
#rdx trzyma idx więc rax + 16 + 8 * idx to dokładnie ap->x[ap->idx]
retq
```

`b_struct`

| pole | offsetof | sizeof | alignof |
|:----:|:--------:|:------:|:-------:|
| first | 0 | 4 | 4 |
| pad0 | 4 | 4 | 1 |
| a | 8 | 40 | 8 |
| last | 288 | 4 | 4 |

Rozmiar a wynosi 40 i wiemy z kodu, że jest tam liczba idx oraz tablica x.
x jest typu long ponieważ przed wrzuceniem n rozszerzamy je do 64 bitów
zatem rozmiar tablicy x wynosi (40-8)/8 = 4.
```c=
struct a_struct {
    long idx;
    long x[4];
};
```
w b_struct offset a to 8, offset last to 288, sizeof a to 40 więc CNT to 280/40 = 7.
struct b: first 4| padding 4|a[0] 40|...|a[6] 40|last 4 | padding 4|

## Zadanie 4

:::success
Autor: Władysław Jabłoński
:::
```c=
union elem {
    struct {
        long *p;            
        long y;             
    } e1;                   
    struct {
        long x;             
        union elem *next;  
    } e2;                   
};                        
```

| pole | offsetof | sizeof | alignof |
|:----:|:--------:|:------:|:-------:|
| p | 0 | 8 | 8 |
| y | 8 | 8 | 8 |
| x | 0 | 8 | 8 |
| next | 8 | 8 | 8 |

```=
proc:                     # union elem* proc2(union elem* arg)
    movq 8(%rdi), %rax    #     union elem* result = arg->e2.next;
    movq (%rax),  %rdx    #     long *tempPtr = result->e1.p;
    movq (%rdx),  %rdx    #     long temp = *(tempPtr);
    subq 8(%rax), %rdx    #     temp -= result->e1.y;
    movq %rdx,    (%rdi)  #     arg->e2.x = temp;
    ret                   #     return result;
```

Prześledźmy po kolei instrukcje i stwórzmy kod w C odpowiadający funkcji `proc`:
*    `movq 8(%rdi), %rax` - stąd uzyskujemy informacje na temat typu funkcji oraz argumentu, jako że do `%rax` wysyłamy adres, to funkcja będzie typu `union elem*`, podobnie jak jej argument, a sama instrukcja odpowiada `union elem* result = arg->e2.next`
*    `movq (%rax), %rdx` - odpowiada to instrukcji `long *tempPtr = result->e1.p`
*    `movq (%rdx), %rdx` - `long temp = *(tempPtr);`, w assemblerowym kodzie linijki 3/4 odpowiadają instrukcji z linijki 13 w C.

Po assemblerowym kodzie możemy wywnioskować z którą strukturą pracujemy tylko przez to, czy odwołujemy się do wartości, czy adresów: zauważmy, że pierwszym elementem `struct e1` jest wskaźnik, a drugim wartość, a w `struct e2` jest odwrotnie.

```c=11
union elem* proc(union elem* arg){
    union elem* result = arg->e2.next;
    arg->e2.x = *result->e1.p - result->e1.y;
    return result;
}
```

```c=11
union elem* proc(union elem* arg){
    union elem* result = arg->e2.next;
    long temp = *(result->e1.p);
    temp -= result->e1.y;
    arg->e2.x = temp;
    return result;
}
```

rozmiar unii to rozmiar jej największego elementu. Rozmiar unii elem 16 bajtów

## Zadanie 5

:::success
Autor: Filip Pazera
:::
![](https://i.imgur.com/akVSedL.png)
```c=
  typedef struct A {
      long u[2];
      long *v;
  } SA;
 
  typedef struct B {
      long p[2];
      long q;
  } SB;
```
```=+
eval:
    movq %rdi, %rax
    movq 16(%rsp), %rcx
    movq 24(%rsp), %rdx
    movq (%rdx), %rsi
    movq %rcx, %rdx
    imulq %rsi, %rdx
    movq %rdx, (%rdi)
    movq 8(%rsp), %rdx
    movq %rdx, %rdi
    subq %rsi, %rdi
    movq %rdi, 8(%rax)
    subq %rcx, %rdx
    movq %rdx, 16(%rax)
    ret
wrap:
    subq $72, %rsp
    movq %rdx, (%rsp)
    movq %rsp, %rdx
    leaq 8(%rsp), %rax
    pushq %rdx 
    pushq %rsi 
    pushq %rdi
    movq %rax, %rdi
    call eval
    movq 40(%rsp), %rax
    addq 32(%rsp), %rax
    imulq 48(%rsp), %rax
    addq $96, %rsp
    ret
```
```c=+
SB eval(SA s) {
    SB b;
    
    long v = *s.v;
    
    b.p[0] = s.u[1] * v;
    b.p[1] = s.u[0] - v;
    b.q = u[0] - u[1];
    
    return b;
}

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

Rekord aktywacji procedury `wrap` w momencie wywołania funkcji `eval`:


| %rsp | Zawartość                                   |
| ---- |:------------------------------------------- |
| +96  | adres powrotu                               |
| +88  |                                             |
| +80  |                                             |
| +72  |                                             |
| +64  |                                             |
| +56  |                                             |
| +48  | <span style="color:lightgrey">b.q</span>    |
| +40  | <span style="color:lightgrey">b.p[1]</span> |
| +32  | <span style="color:lightgrey">b.p[0]</span> |
| +24  | z                                           |
| +16  | %rdx                                        |
| +8   | %rsi                                        |
| +0   | %rdi                                        |

## Zadanie 6

:::success
Autor: Andrzej Bernad
:::
:::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 ( 20 linia)
.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/
```

```c=
struct P s{
    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,
// stopnia(n) oraz wspołczynnikami(*a) są przechowywane w struct P *s.
```

## Zadanie 7

:::success
Autor: Franciszek Pindel
:::

W języku C++ klasy mogą  posiadać wirtualne metody. Zauważ, że  w wierszu  15 nie  wiemy jakiego typu jest obiekt, na który wskazuje «bp», tj. może to być zarówno «Base» jak i «Derived». Skompiluj  poniższy  kod  przy  pomocy  polecenia  «gcc -Os -fno-rtti -S -o - example.cpp | c++filt». W wygenerowanym wydruku znajdź miejsce definicji i użycia tabeli metod wirtualnych. Opisz zawartość rekordu aktywacji procedury przed wykonaniem wiersza 21. Skąd implementacja metody «doit» wie, gdzie w pamięci znajduje się zmienna «data»?

Dla każdej klasy jest tworzona tabela zawierająca adresy poszczególnych metod. Każdy obiekt otrzymuje niejawnie wskaźnik na odpowiednią tablicę. Korzystając z tej tablicy można wywołać odpowiednią funkcję

```c=
struct Base {
    Base(int n) : data(n) {}
    int data;
    virtual int doit(int n) { 
        return n - data; 
    }
};

struct Derived : Base {
    Derived(int n) : Base(n + 1) {}
    int doit(int n) { return n * data; }
};

int doit(Base *bp) {
    return bp->doit(1);
}

int main(int argc, char *argv[]) {
    Base b = Base(10);
    Derived d = Derived(20);
    return doit(&b) + doit(&d);
}
```

```=
Base::doit(int):
        movl    %esi, %eax
        subl    8(%rdi), %eax
        ret
Derived::doit(int):
        movl    8(%rdi), %eax
        imull   %esi, %eax
        ret
doit(Base*): # skok do odpowiedniej funkcji za pomocą tabeli
        movq    (%rdi), %rax
        movl    $1, %esi
        movq    (%rax), %rax
        jmp     *%rax
main:
        pushq   %rbx
        subq    $32, %rsp
        movq    %rsp, %rdi
        movq    $vtable for Base+16, (%rsp)
        movl    $10, 8(%rsp)
        movl    $21, 24(%rsp)
        movq    $vtable for Derived+16, 16(%rsp)
        call    doit(Base*)
        leaq    16(%rsp), %rdi
        movl    %eax, %ebx
        call    doit(Base*)
        addq    $32, %rsp
        addl    %ebx, %eax
        popq    %rbx
        ret
vtable for Base:    # tabela metod wirtualnych dla Base
        .quad   0
        .quad   0
        .quad   Base::doit(int)
vtable for Derived: # tabela metod wirtualnych dla Derived
        .quad   0
        .quad   0
        .quad   Derived::doit(int)
```

Rekord aktywacji:


| offset | zawartość             |
| ------ | --------------------- |
| 40     | return address        |
| 32     | rbx                   |
| 24     | 21                    |
| 16     | vtable for Derived+16 |
| 8      | 10                    |
| 0      | vtable for Base+16    |

>[name=Franciszek Malinka] Można sobie ładnie wypisać to jak w pamięci układają się te structy komendą `clang -cc1 -std=c++11 -fdump-record-layouts -emit-llvm example.cpp`
:::spoiler
```
*** Dumping AST Record Layout
         0 | struct Base
         0 |   (Base vtable pointer)
         8 |   int data
           | [sizeof=16, dsize=12, align=8,
           |  nvsize=12, nvalign=8]

*** Dumping AST Record Layout
         0 | struct Derived
         0 |   struct Base (primary base)
         0 |     (Base vtable pointer)
         8 |     int data
           | [sizeof=16, dsize=12, align=8,
           |  nvsize=12, nvalign=8]
```
:::

## Zadanie 8

:::danger
Autor: Maksymilian Debeściak
:::