# 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
:::
```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
:::
Sign in with Wallet
Connect another wallet