# Ćwiczenia 2, grupa śr. 17-19, 1 marca 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 | 10 |
| ----------------------:| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Mikołaj Balwicki | | | | | | | | | | |
| Kamila Goszcz | X | X | X | X | X | X | X | | | |
| Monika Jędrzejkowska | | | | | | | | | | |
| Mateusz Materek | | X | X | X | X | X | X | X | | |
| Kacper Ponikowski | | | | | | | | | | |
| Maciej Styś | | | | | | | | | | |
| Mikołaj Łabędzki | | | | | | | | | | |
:::

**Tutaj można dodeklarować zad. 7 i zad. 10 z listy 0:**
|Imię i Nazwisko | zad. 7 | zad. 10 |
| -------------- | ---- | ---- |
| Kamila Goszcz | X | |
| ... | | |

:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::

## Zadanie 1
:::success
Autor: Kamila Goszcz
:::

if (i < k) {
    uint32_t mask = (x & (1 << i)) << (i - k);
    x = mask | (x & ~(1 << k));
} else if (i > k) {
    uint32_t mask = (x & (1 << i)) >> (i - k);
    x = mask | (x & ~(1 << k)); 
}

uint32_t mask = (x & (1 << i)) >> i;
x = (mask << k) | (x & ~(1 << k));

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

const uint32_t m1  = 0x5555555555555555; // 0101...
const uint32_t m2  = 0x3333333333333333; // 00110011...
const uint32_t m4  = 0x0f0f0f0f0f0f0f0f; // 00001111...
const uint32_t m8  = 0x00ff00ff00ff00ff; // 8 x 0, 8 x 1...
const uint32_t m16 = 0x0000ffff0000ffff; // 16 x 0, 16 x 1.


int pc(uint32_t x)
{
    x = (x & m1 ) + ((x >>  1) & m1 );
    x = (x & m2 ) + ((x >>  2) & m2 );
    x = (x & m4 ) + ((x >>  4) & m4 );
    x = (x & m8 ) + ((x >>  8) & m8 );
    x = (x & m16) + ((x >> 16) & m16);
    return x;
}

## Zadanie 3
:::success
Autor: Kamila Goszcz
:::

struct A {
    int8_t a;   // 1 bajt
    void *b;    // 8 bajty
    int8_t c;   // 1 bajt
    int16_t d;  // 2 bajty
}

schemat struktury A:

a| | | | | | |
b|b|b|b|b|b|b|b
c| |d|d| | | |

Uzasadnienie: np. efektywny transfer pomiędzy pamięcią główną a pamięcią podręczną. Pamięć główna jest podzielona na rozłączne bloki. Niech blok ma 16 bajtów.
Bez wyrównania:
| | | | | | | | | | | | | | | |d | d| | | | | | | | | | | | | | |
Może się zdarzyć, że każdy bajt zmiennej d będzie w innym bloku.
Jeśli zmienna d jest wyrównana to mamy pewność, że obydwa jej bajty będą w jednym bloku.

Ponieważ pamięć 'rozciąga' się do największego elementu to całość wraz z paddingiem zajmuje 12 bajtów. Wystarczy jednak aby zamienić kolejnością elementy `a` i `*b` aby jej wielkość zmniejszyła się do 8 bajtów


b|b|b|b|b|b|b|b
d|d|a|c| | | |

struct B {
    uint16_t a;    // 2 bajty
    double b;      // 8 bajtów
    void *c;       // 4 bajty
}

Schemat struktury B:

a|a| | | | | |
b|b|b|b|b|b|b|b
c|c|c|c|c|c|c|c

Analogicznie do struktury A, z tym wyjątkiem, że jej rozmiar wynosi 24 bajtów. Możemy zoptymalizować rozmiar w poniższy sposób:


Generalnie dobrą strategią optymalizacji jest sortowanie pól względem rozmiaru - od największego do najmniejszego. Pozwala to na maksymalne rozszerzenie na samym początku a co za tym idzie 'zbicie' mniejszych elementów.

## Zadanie 4
:::success
Autor: Mateusz Materek
:::

`volatile` -> służy do oznaczenia zmiennej, która może ulec zmianie poza kodem - np. kieruje na dane pochodzące ze sprzętu, może wpłynąć na nią inny wątek. W praktyce chodzi o to, aby każdy dostęp do zmiennej wymagał spojrzenia do pamięci, a nie np. skorzystania z wartości w cache'u.
Przykład z Wikipedii:

static int foo;

void var(void) {
    foo = 0;
    
    while (foo != 255){
        /* ... */
    }
}

(dez)optymalizacja:

static int foo;

void var(void) {
    foo = 0;
    
    while (true){
        /* ... */
    }
}

`static`:
1. A static variable inside a function keeps its value between invocations (zastosowanie: przechowywanie stanu między wywołaniami, ale nie chcemy zmiennych globalnych).
2. A static global variable or a function is "seen" only in the file it's declared in (zastosowanie: kontrola dostępu, pokazujemy na zewnątrz tak mało, jak tylko trzeba).

`restrict` -> przekazuje do kompilatora informację, że przez cały czas życia obiektu, tylko ten jeden jedyny wskaźnik będzie na niego wskazywać (zastosowanie: np. pewne optymalizacje w zakresie przesuwania obiektu w pamięci).

## Zadanie 5
:::success
Autor: Kamila Goszcz
:::

- `s += b[j+1] + b[--j]`

t1 := j + 1
t2 := t1 * 4
t3 := b[t2]
j  := j - 1
t4 := j * 4
t5 := b[t4]
t5 := t3 + t5
s  := s + t5

- `a[i++] -= *b * (c[j*2] + 1)`

t1 := j * 2
t2 := t1 * 4
t3 := c[t2]
t4 := t3 + 1
t5 := *b
t6 := t5 * t4
i  := i + 1
t7 := i * 4
t8 := a[t7]
t9 := t8 - t6
a[t7] := t9

## Zadanie 6
:::success
Autor: Mateusz Materek
:::

struct A {
    int8_t a;    // 1
                 // 7 offset
    void *b;     // 8
    int8_t c;    // 1
                 // 1 offset
    int16_t d;   // 2
                 // 4 offset
};

suma: 24 bajty

// us[1].a
t1 := us + 24

// us[j].c
t2 := j * 24
t2 := us + t2
t3 := t2 + 16

// vs->d
t4 := vs + 18

// przypisywanie wartości
t5 := *t1
t6 := *t3
*t4 := t5 + t6

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

void insertion_sort(int arr[], int length) {
    int j, temp;
    for (int i = 0; i < length; i++) {
        j = i;
        while (j > 0 && arr[j] < arr[j-1]) {
            temp = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = temp;
            j--;
        }
    }
}

        i := 0                          <<B1>>
FOR:    if i >= length goto END         <<B2>>
        j := i                          <<B3>>
WHILE:  if j <= 0 goto ADD              <<B4>>
        t1 := j * 4                     <<B5>>
        t2 := arr[t1]
        t3 := j - 1
        t3 := t3 * 4
        t4 := arr[t3]
        if t2 >= t4 goto ADD                   
        arr[t1] := t4                   <<B6>>
        arr[t3] := t2
        j := j - 1
        goto WHILE
ADD:    i := i + 1                      <<B7>>
        goto FOR
END:                                    <<B8>>

Graf przepływu sterowania:

## Zadanie 8
:::success
Autor: Mateusz Materek
:::

#define N (sizeof(int32_t) * 8)

int32_t isqrt(int32_t n) {
	if (n < 0)
		return INT32_MIN;

	int32_t x = n;
	int32_t c = 0;
	int32_t d = 1 << (N - 2);

	while (d > n)
		d >>= 2;
	while (d) {
		if (x >= c + d) {
			x -= c + d;
			c = (c >> 1) + d;
		} else {
			c >>= 1;
		}
		d >>= 2;
	}

	return c;
}

        N := 4 * 8            // x86_64 ?    // B0
        if n >= 0 goto start                 
        return INT32_MIN                     // B1
        
start:  x := n                               // B2
        c := 0
        t := N - 2
        d := 1 << t
while1: if d <= n goto while2                // B3
        d := d >> 2                          // B4
        goto while1
while2: if d <= 0 goto end                   // B5
        t := c + d                           // B6
        if x >= t goto true
        c := c >> 1                          // B7
        goto while2
true:   x := x - t                           // B8
        t := c >> 1
        c := t + d
        goto while2
end:    return c                             // B9


## Zadanie 9
:::danger
Autor: dodeklarować
:::

## Zadanie 10
:::danger
Autor:
:::

https://en.wikipedia.org/wiki/Duff%27s_device

void secret(uint8_t *to, uint8_t *from, size_t count) {
size_t n = (count + 7) / 8;
switch (count % 8) {
case 0: do { *to++ = *from++;
case 7:
*to++ = *from++;
case 6:
*to++ = *from++;
case 5:
*to++ = *from++;
case 4:
*to++ = *from++;
case 3:
*to++ = *from++;
case 2:
*to++ = *from++;
case 1:
*to++ = *from++;
} while (--n > 0);
}
}

void secret2(uint8_t *to, uint8_t *from, size_t count) {
size_t n = (count + 7) / 8;
static void *array[] = {&&l0, &&l1, &&l2, &&l3, &&l4, &&l5, &&l6, &&l7};
goto *array[count % 8];
l0: *to++ = *from++;
l7: *to++ = *from++;
l6: *to++ = *from++;
l5: *to++ = *from++;
l4: *to++ = *from++;
l3: *to++ = *from++;
l2: *to++ = *from++;
l1: *to++ = *from++;
if(--n > 0) goto l0;
}