###### 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.
```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.
### 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>>
```
## 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);
}
}
```
```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;
}
```
Sign in with Wallet
Connect another wallet