# Ćwiczenia 8, grupa śr. 17-19, 12 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 | 9 |
| ----------------------:| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Mikołaj Balwicki | | | | | | | | | |
| Kamila Goszcz | | X | X | X | | | X | | |
| Mateusz Materek | X |==X==| X | | 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
:::

struct node {				// offset 	align 	size
    char id[2];				// 0		1	2B
					//			6B padding
    int (*hashfn)(char *);		// 8 		8	8B
    short flags;			// 16		2	2B
					// 			6B padding (alignof union...)
    union {				//  			max {8, 16} = 16B
        struct {			// 			SUM: 16B
            short n_key;		// 24		2	2B
					// 			2B padding
            int n_data[2];		// 28		4	8B
            unsigned char n_type;	// 36		1	1B
					// 			3B padding
        } s;
        unsigned l_value[2];		// 24		4	8B
    } u;
};
					// CAŁOŚĆ: 40B

Optymalizacja (32B):

struct node {
    union {
        struct {
            int n_data[2];
            short n_key;
            unsigned char n_type;
        } s;
        unsigned l_value[2];
    } u;
    int (*hashfn)(char *);
    short flags;
    char id[2];
};

## Zadanie 2
:::success
Autor: Mateusz Materek
:::

## Zadanie 3
:::success
Autor: Mateusz Materek
:::

long A[R][S][T];
//		%rdi 	%rsi,  %rdx    %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)		// *dest = %rax
    movq $3640,%rax		// %rax = 3640 <- rozmiar struktury
    ret

Skoro 3640 to `sizeof(A)`, to `A` zawiera 455 longów.

Wzorek z wykładu: $(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, S = 5$,
$R \cdot S \cdot T = 455, R = 7$.

## Zadanie 4
:::success
Autor: Kamila Goszcz
:::

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

//          %rdi       %rsi
void test (long i, b_struct *bp) {
	int n = bp->first + bp->last;  
	a_struct *ap = &bp->a[i];
	ap->x[ap->idx] = n;
}

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

`movl 0x120(%rsi),%ecx` informuje nas o tym, że `sizeof(int) + CNT * sizeof(a_struct)` to `288`, zatem `CNT * sizeof(a_struct) = 280`

z instrukcji `leaq` wiemy, że rozmiar `a_struct` wynosi 40, z funkcji test wiemy, że `a_struct` ma pola `idx` oraz `x`, przy czym `x` jest tablicą. Dodatkowo wiemy, że rozmiar `idx` = 8 i jest on położony na samym początku struktury. Zatem wystarczy wyliczyć rozmiar tablicy `x`: `(40 - 8) / 8 = 4`. Skoro tak, to `CNF = 280 / 40 = 7`

### Struktura a_struct:

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

## Zadanie 5
:::success
Autor: Mateusz Materek
:::

union elem {				// max {e1, e2} = 16B
	struct {			// suma: 16B
		long *p;		// 8B
		long y;			// 8B
	} e1;
	struct {			// suma: 16B
		long x;			// 8B
		union elem *next;	// 8B
	} e2;
};

proc:
	//    \/ dereferencja drugiego pola, czyli musimy mieć wskaźnik; zatem e2
	movq 8(%rdi),%rax  // %rax = *result = arg->e2.next
	movq (%rax),%rdx   // %rdx = result->e1.p
	movq (%rdx),%rdx   // %rdx = *(result->e1.p) 
	subq 8(%rax),%rdx  // %rdx = *(result->e1.p) - result->e1.y
	movq %rdx,(%rdi)   // arg->x = *(result->e1.p) - result->e1.y
	ret

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

## Zadanie 6
:::danger
Autor:
:::

stos w momencie wywołania evala z zewnątrz (nie przez wrap):

v
u[1]
u[0]
adres powrotu z eval <- %rsp przed wykonaniem pierwszej instrukcji z eval

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;
}

| %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 | cofnąć o 8 |
| +16 | %rdx |
| +8 | %rsi |
| +0 | %rdi |

## Zadanie 7
:::success
Autor: Kamila Goszcz
:::

:::info
- `vfmadd231ss xmm1, xmm2, xmm3` - Multiply scalar single-precision floating-point value from xmm2 and xmm3/m32, add to xmm1 and put result in xmm1.
:::

puzzle7:
		movq (%rdi), %rdx		// %rdx = s->a
		leaq 8(%rdi), %rcx		// %rcx = s->b
		xorl %eax, %eax		// i = 0
		vxorps %xmm1, %xmm1, %xmm1	// %xmm1 = 0
		vmovss .LC1(%rip), %xmm2	// %xmm2 = 1
.L2: 	
		cmpq %rdx, %rax								
		jge .L5				// if (i >= s.a) goto L5
		vfmadd231ss (%rcx,%rax,4), %xmm2, %xmm1	
						// %xmm1 = (%rcx,%rax,4) * %xmm2 + %xmm1
		incq %rax			// i += 1
		vmulss %xmm0, %xmm2, %xmm2	// %xmm2 = %xmm2 * %xmm0 
		jmp .L2
.L5: 	
		vmovaps %xmm1, %xmm0		// %xmm0 = %xmm1
		ret

.LC1: 	.long 0x3f800000			

// 0x3f800000 = 
// 0 01111111 00000000000000000000000 = 
// 2 ^ (127 - 127) * 1 = 1

struct P {
    long n;
    float *a;
}

float puzzle6(struct P *s, float f){
    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;   			// vfmadd231ss
        x *= f;               			// vmulss
    }
    return acc;
}

Funkcja wylicza wartość wielomianu przechowywanego w strukturze `P` stopnia `n` o współczynnikach przechowywanych w `a` dla zmiennej `f`

## Zadanie 8
:::danger
Autor:
:::

Rekord aktywacji funkcji main w momencie wykonania funkcji `doit(&b)`:

Rekord aktywacji:

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

## Zadanie 9
:::danger
Autor:
:::