---
# System prepended metadata

title: Lista 1
tags: [ASK]

---

###### tags: `ASK`

# Lista 1

## Zadanie 1

```cpp=
void bit_copy(uint32_t* x, uint32_t i, uint32_t k) {
  uint32_t mask = (*x >> i) & 1;
  mask <<= k;
  
  *x &= ~(1<<k); // zeruje bit na k-tej pozycji
  *x |= mask;   // ustawia bit na taki sam jak i-ty
}
```

## Zadanie 2

Rozwiązanie metodą *dziel i zwyciężaj*. Działa w czasie $O(\log_2 n)$

W każdym kroku dzielimy x na coraz większe bloki, następnie w tym każdym kroku zamieniamy kolejne bloki na ilość zapisanych bitów w tych blokach.

![](https://i.imgur.com/ZomGlnA.png)

```cpp=
uint32_t popcount(uint32_t x) {
  x = (x & 0x55555555) + ((x >> 1) & 0x55555555); // 01010101010101010101010101010101
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333); // 00110011001100110011001100110011
  x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F); // 00001111000011110000111100001111
  x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF); // 00000000111111110000000011111111
  x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF); // 00000000000000001111111111111111

  return x;
}
```

## Zadanie 3

Struktury są organizowane w pamięci według następujących reguł:
 - Elementy struktury są przechowywane w takiej samej kolejności w jakiej zostały zadeklarowane.
 - Offset zmiennej o typie `T` musi zostać wyrównany do `sizeof(T)` bajtów.
 - Rozmiar całej struktury zaokrąglany jest w górę do wielokrotności rozmiaru jej największego elementu.

Rozmiar struktury można redukować, zamieniając kolejność deklarowanych zmiennych (jak pokazano w Optymalizacji poniższych struktur).

Padding - stosowany po to aby zmiejszyć liczbę cykli procesora podczas wykonywania instrukcji na strukturze.

Kompilator sam nie optymalizuje wielkości struktury aby wczytując strukturę z pliku binarnego wczytać ją w odpowiedniej kolejności oraz aby programista wiedział dokładnie jaka jest kolejność (bo może na niej operować)

Struktura A:
```c=
struct A {
    int8_t a;  -- 1 bajt
               -- 3 bajty
    void *b;   -- 4 bajty
    int8_t c;  -- 1 bajt
               -- 1 bajt
    int16_t d; -- 2 bajty
};

Suma = 12 bajty
```
Optymalizacja:
```c=
struct A {
    void *b;   -- 4 bajty
    int16_t d; -- 2 bajty
    int8_t a;  -- 1 bajt
    int8_t c;  -- 1 bajt
};
Suma = 8 bajtów
```
Struktura B:
```c=
struct B {
    uint16_t a; -- 2 bajty
                -- 6 bajty
    double b;   -- 8 bajtów
    void *c;    -- 4 bajty
                -- 4 bajty
};
Suma = 24 bajty
```
Optymalizacja:
```c=
struct B {
    double b;   -- 8 bajtów
    void *c;    -- 4 bajty
    uint16_t a; -- 2 bajty
                -- 2 bajty
};
Suma = 16 bajtów
```

Sprawdzenie w programie dla Unix x86 (32-bitowy):
```bash
gcc -m32 offset_size.c
```

```c=
#include <stdio.h>
#include <inttypes.h>
#include <stddef.h>

struct A {
  int8_t a;
  void *b;
  int8_t c;
  int16_t d;
};

struct B {
  uint16_t a;
  double b;
  void *c;
};

int main(){
    printf("struktura A:\n");
    printf("a: %d, %d\n", offsetof(struct A, a), sizeof(int8_t));
    printf("b: %d, %d\n", offsetof(struct A, b), sizeof(void));
    printf("c: %d, %d\n", offsetof(struct A, c), sizeof(int8_t));
    printf("d: %d, %d\n", offsetof(struct A, d), sizeof(int16_t));
    printf("A: %d\n", sizeof(struct A));

    printf("struktura B:\n");
    printf("a: %d, %d\n", offsetof(struct B, a), sizeof(uint16_t));
    printf("b: %d, %d\n", offsetof(struct B, b), sizeof(double));
    printf("c: %d, %d\n", offsetof(struct B, c), sizeof(void));
    printf("B: %d\n", sizeof(struct B));
    return 0;
}
```
```
struktura A:
a: 0, 1
b: 4, 1
c: 8, 1
d: 10, 2
A: 12
struktura B:
a: 0, 2
b: 4, 8
c: 12, 1
B: 16
```

## Zadanie 4

### volatile
Oznacza zmienną, która może zmienić wartość niezależnie od kodu, w którym się znajduje. Zmusza kompilator do tego, żeby nie cache’ował zmiennej i żeby przy każdym odwołaniu do niej wczytywał ją z pamięci.

Należy używać tego słowa kluczowego np. gdy mamy wskaźnik na adres pod którym jest zmapowana pamięć jakiegoś urządzenia z którym się komunikujemy.

![](https://i.imgur.com/BMazJMq.png)

![](https://i.imgur.com/gR4IM4z.png)


### static

Statyczne zmienne globalne i procedury są widoczne tylko w pliku, w którym zostały zadeklarowane

Statyczna zmienna lokalna jest inicjalizowana tylko raz i zachowuje swoją wartość między wywołaniami funkcji

Statyczna zmienna procedur mówi, że funkcje są widoczne tylko dla innych funkcji w tym samym pliku.

```c=
void test(){
    static int x = 0;
    x++;
    printf("%d ", x);
}
int main(){
    for(int i = 0; i < 5; i++) test(); // wypisuje 1 2 3 4 5
    return 0;
}
```

### restrict
*w stosunku do typów zmiennych wskaźnikowych*

Mówi kompilatorowi, że oznaczony tym słowem kluczowym wskaźnik jest jedynym wskaźnikiem wskazującym na obiekt, na który wskazuje
Jest to gwarancja od programisty dla kompilatora. Używane ze wskaźnikiem p mówi kompilatorowi, że ptr jest jedynym sposobem na dostęp do obiektu wskazanego przez this.

```c=
#include <stdio.h>
void my_function(int* x, int* y, int* restrict z) {
   *x += *z;
   *y += *z;
}
main(void) {
   int x = 10, y = 20, z = 30;
   my_function(&x, &y, &z);
   printf("%d %d %d", x, y, z);
}

Output = 40 50 30
```
```c=
int* restrict p1 = &a;
int* restrict p2 = &b;
p1 = p2; // undefined behavior
```

## Zadanie 5

**Kod trójkowy** - to postać pośrednia stosowana przez kompilatory przy translacji z języka wysokiego poziomu do asemblera. W większości przypadków można ją bezpośrednio przetłumaczyć na kod maszynowy procesora.

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

```pseudocode=
t1 := j + 1 
t2 := t1 * 4 
t3 := b + t2  // adres b[j+1]
t4 := *t3     // wartość b[j+1]
j := j - 1
t5 := 4 * j
t6 := b + t5  // adres b[--j]
t7 := *t6     // wartość b[--j]
t8 := t7 + t4 // suma po prawej
s := s + t8   // zwiększamy s
```

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

```c=
t1 := *b
t2 := j * 2
t3 := 4 * t2
t4 := c + t3 // adres c[j * 2]
t5 := *t4 // wartość c[j * 2]
t6 := 1 + t5 // c[j * 2] + 1
t7 := t1 * t6 // *b * (c[j*2] + 1)
t8 := 4 * i
t9 := a + t8 // adres a[i++]
t10 := *t9 // wartość a[i++]
*t9 := t10 - t7 // przypisanie do a[i] prawej strony
i := i + 1
```

## Zadanie 6

```cpp=
struct A {
  int8_t a;
  void *b;
  int8_t c;
  int16_t d;
};

vs->d = us[1].a + us[j].c;
```

a) Unix x86-64
```c=
t1 := us + 24
t2 := *t1
t3 := j * 24
t4 := us + t3
t5 := t4 + 16
t6 := *t5
t7 := vs + 18
*t7 := t2 + t6
```
b) Unix x86
```c=
t1  := us + 12
t2  := *t1
t3  := j * 12
t4  := us + t3
t5  := t4 + 8
t6  := *t5
t7  := vs + 10
*t7 := t2 + t6
```

## Zadanie 7

**blok podstawowy** - sekwencja instrukcji (nie wliczamy skoków), kończąca się instrukcją: skoku bezwarunkowego, skoku warunkowego lub powrotem z procedury. Ma jeden punkt wejścia i jeden punkt wyjścia.

**graf przepływu sterowania** - graf skierowany reprezentujący wszystkie ścieżki programu, które można przejść w trakcie jego wykonania. Jego wierzchołkami są *bloki podstawowe*.


```c=
        i := 0
                                <<B1>>
FOR:	if i >= length goto END
                                <<B2>>
        j := i
                                <<B3>>
WHILE:	if j <= 0 goto INC
                                <<B4>>
        t1 := j * 4
        t2 := arr + t1 // adres arr[j]
        t3 := *t2      // wartość arr[j]
        t4 := t2 - 4   // adres arr[j-1]
        t5 := *t4      // wartość arr[j-1]
        if t3 >= t5 goto INC  // arr[j] >= arr[j-1]
                                <<B5>>
        temp := t3  // temp = arr[j]
        *t2 := t5   // arr[j] = arr[j-1]
        *t4 := temp // arr[j-1] = temp
        j := j - 1
        goto WHILE
                                <<B6>>
INC:	i := i + 1
        goto FOR
                                <<B7>>
END:
                                <<B8>>
```
![](https://i.imgur.com/sCYjyUi.png)

## Zadanie 8

Procedura `secret()` kopiuje `count` wartości bajt po bajcie z miejsca w pamięci wskazanego przez `from` do `to`. Jest to procedura podobna do `memcpy`
$n = \lceil \frac{count}{8} \rceil$ - bo nie każdy count jest wielokrotnością 8

```cpp=
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);
  }
}
```
![](https://i.imgur.com/epUkTY5.png)

```c=
void secret(uint8_t *to, uint8_t *from, size_t count) {
  size_t n = (count + 7) / 8;
  
  static const void *E[] = {&&END, &&E0, &&E7, &&E6, &&E5, &&E4, &&E3, &&E2, &&E1};
  goto *E[count % 8 + 1];
  
  E0:  *to++ = *from++;
  E7:  *to++ = *from++;
  E6:  *to++ = *from++;
  E5:  *to++ = *from++;
  E4:  *to++ = *from++;
  E3:  *to++ = *from++;
  E2:  *to++ = *from++;
  E1:  *to++ = *from++;
  
  goto *E[--n > 0];
  
  END: return;
}
```