# Lista 1 (4 marca 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 |
| --------------------:| ---:| ------ | --- | ----- | --- | ----- | ----- | --- |
| Andriy Bernad | X | X | X | X | X | ==X== | X | X | 8 +
| Wojciech Bogucki | | X | X | | | | | | 2
| Michał Doros | X | X | X | X | X | X | | X | 7
| Marko Golovko | X | X | X | X | X | X | X | X | 8
| Magdalena Jarecka | X | | X | | X | X | | | 4
| Heorhii Karpenko | X | X | X | ==X== | X | X | X | X | 8
| Szymon Kosakowski | X | X | X | X | X | X | X | | 7
| Izabella Kozioł | X | X | X | X | X | | X | | 6
| Franciszek Malinka | X | ==X== | X | X | X | X | X | X | 8
| Filip Pazera | X | | X | | X | X | X | | 5
| Kacper Puchalski | X | X | X | X | X | X | X | | 7
| Michał Siwiec | | | | | | | | | 0
| Kacper Solecki | X | X | X | X | X | X | X | X | 8
| Andrzej Tkaczyk | X | X | X | X | X | X | X | X | 8
| Łukasz Wasilewski | x | x | x | x | x | x | x | | 7
| Vladyslav Yablonskyi | | | | X | X | X | X | | 4
| Jakub Zając | x | x | x | x | x | x | ==x== | x | 8
| Adam Zyzik | X | X | X | | X | X | | | 5
| Antoni Kamiński | X | X | X | | X | X | | | 5
:::
## Zadanie 1
:::info
Autor: Szymon Kosakowski
:::
```c++=1
int32_t copy_ith_to_kth(int32_t X, int k, int i)
{
int32 Y = X & ~(1<<k); //gaszę k-ty bit
uint32_t pom = (X & (1<<i))>>i; //biorę i-ty bit do zmiennej pomocniczej
return Y | (pom<<k); //przesuwam i-ty bit na k-tą pozycję
}
```
:::spoiler
1000 (int4) >> 3 = 1111
1000 (uint4) >> 3 = 0001
:::
## Zadanie 2
:::info
Autor: Franciszek Malinka
:::
:::spoiler
```c=
char* utb(uint32_t x) {
static char rep[36];
int cnt = 34;
for (int i = 0; i < 32; i += 1) {
if (i > 0 && i % 8 == 0) {
rep[cnt] = ' ';
cnt -= 1;
}
rep[cnt] = (x & 1) + '0';
cnt -= 1;
x >>= 1;
}
rep[35] = '\0';
return rep;
}
void pb(uint32_t x) {
printf("%s : %d\n", utb(x), x);
}
```
:::
```c=
const int S[] = {1, 2, 4, 8, 16};
const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};
// wersja prosta
c = v - ((v >> 1) & B[0]);
c = ((c >> S[1]) & B[1]) + (c & B[1]);
c = ((c >> S[2]) + c) & B[2];
c = ((c >> S[3]) + c) & B[3];
c = ((c >> S[4]) + c) & B[4];
// wersja dla koksow, nie moja
v = v - ((v >> 1) & 0x55555555);
v = ((v >> 2) & 0x33333333) + (v & 0x33333333);
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
```
Wyjaśnienie: pomysł opiera się na zliczaniu liczby zapalonych bitów w "kubełkach". Najpierw chcemy policzyć liczbę zapalonych bitów w kubełkach 2-elementowych (czyli dzielimy naszą liczbę na 16 kubełków), później w kubełkach 4-elementowych itd. aż do jednego kubełka 32-elemenotwego.
Wiersz `c = v - ((v >> 1) & B[0]);` powoduje, że w zmiennej `c` każde kolejne dwa bity przechowują liczbę zapalonych bitów w tych 2-elementowych kubełkach liczby v.
```
v = 1011 0001
v >> 1 = 0101 1000
v >> 1 & 0x55 = 0101 0000 // 0x55 = 0101 0101
^ W tej liczbie zgaszone są nieparzyste bity. To nam gwarantuje, że w tych dwuelementowych kubełkach liczba reprezentowana przez te bity to 1 lub 0.
v - (v >> 1 & 0x55) = 0110 0001
^ wszystko się zgadza. Pierwsze dwa bity v mają zapalony jeden bit,
drugie dwa zapalone mają dwa bity, itd.
```
Możliwe kombinacje tych dwuelementowych kubełków to: `00`, `01`, `10`, `11`.
Chcemy teraz jakoś umieć zmienić je na liczby, które reprezentują liczbę zapalonych w nich bitów, czyli `00 -> 00, 01 -> 01, 10 -> 01, 11 -> 10`
Zauważmy, że `00` oraz `01` same reprezentują swoją liczbę zapalonych bitów. Tylko dwa następne muszą zmienić się w coś innego. Jeżeli zastanowimy się co stanie się z tymi liczbami po przesunięciu w prawo, a potem po odjęciu od nich samych, to od razu przekonanmy się że ten sposób działa poprawnie.
Wiersz `c = ((c >> S[1]) & B[1]) + (c & B[1]);` wykonuje dokładnie tą samą technikę, tym razem jednak mamy kubełki dwuelementowe i chcemy je zmergować w kubełki czteroelementowe.
Dalej już leci analogicznie.
## Zadanie 3
:::danger
Autor: Łukasz Wasilewski
:::
```c
struct A {
int8_t a;
void *b;
int8_t c;
int16_t d;
};
```
Komputer przechowuje dane w 64-bitowych(lub 32 bitowych) blokach. Jeżeli dane są za
duże, żeby zmieścić się w jednym bloku następne dane są dopisywane do następnego
bloku. Ilustruję to w poniższej tabelce. wiersze symbolizują bloki, zaś komórki
bajty.
```
+0 |a| | | | | | | |
+8 |b|b|b|b|b|b|b|b|
+16 |c| |d|d| | | | |
każda komórka ma jeden bajt
```
1. offset pola wyrównujemy do `sizeof(pola)`
2. `sizeof(struktury)` wyrównujemy do `sizeof(największego użytego słowa maszynowego)`
```c
struct A1 {
int8_t a;
int8_t c;
int16_t d;
void *b;
};
```
```
+0 |a|c|d|d| | | | |
+8 |b|b|b|b|b|b|b|b|
```
```c
struct B {
uint16_t a;
double b;
void *c;
};
```
```
|a|a| | | | | | |
|b|b|b|b|b|b|b|b|
|c|c|c|c|c|c|c|c|
nie da się nic poprawic
```
## Zadanie 4
:::info
Autor: Heorhii Karpenko
:::
### Volatile
- ***Działanie***:
Modyfikator volatile dodany do zmiennej jest informacją dla kompilatora, że jej zawartość może się zmienić w nieznanych momentach nawet jeśli kod danej funkcji jej nie zmienia. Konsekwencją jest niestosowanie optymalizacji dla zmiennej volatile. Oznacza to, że kompilator przy każdym użyciu odczytuje jej wartość z pamięci zamiast przechowywać ją w rejestrze jeśli wykonuje na niej kilka operacji. Poza tym kompilator nie zmienia kolejności działań wykonywanych przy użyciu tej zmiennej.
- ***Użycie***:
- Pozwala na korzystanie ze zmiennej pomiędzy wywołaniem setjmp i longjmp. (Po wywołaniu longjmp() nie należy uzyskiwać dostępu obiektów lokalnych nie zaznaczonych jako volatile, jeśli ich wartości mogły ulec zmianie od czasu wywołania setjmp(). Ich wartość w tym przypadku jest uważana za nieokreśloną, a dostęp do nich jest niezdefiniowanym zachowaniem)
- Wszystkie rejestry procesora są zadeklarowane jako wskaźniki do zmiennych typu volatile. Ta technika nosi nazwę memory mapping i dzięki niej w kodzie programu jesteśmy w stanie zareagować np. na zmianę wartości pinu, czy ustawienie flagi.
- Innym przykładem zastosowania volatile przy interakcji ze sprzętem jest wykorzystanie DMA. Jeśli przekażemy jakiś adres pamięci do DMA, jego zawartość może się zmienić i nie mamy wpływu na to, kiedy to nastąpi. Nie możemy nawet obronić się przed zapisem do tej pamięci za pomocą wyłączenia przerwań. Dlatego bufory przekazywane do DMA powinny być deklarowane jako volatile. Chyba, że zaimplementujemy mechanizm zapewniający, że pamięć nie jest jednocześnie używana przez DMA i program.
- Wielowątkowość: volatile jest używany do deklaracji zmiennych współdzielonych przez różne wątki. W każdym momencie wykonywania danego wątku może nastąpić zmiana kontekstu i wywołanie drugiego wątku korzystającego z tej zmiennej. Mechanizm działania jest tu podobny jak w przypadku przerwań. Warto w tym miejscu podkreślić, że użycie volatile do komunikacji między wątkami nie jest najlepszym rozwiązaniem.
:::spoiler
- Direct Memory Access, DMA (z ang. bezpośredni dostęp do pamięci) – technika, w której sprzęt komputerowy podłączony do płyty głównej, np. karta graficzna, karta dźwiękowa, karta sieciowa czy kontroler dysku twardego, mogą korzystać z pamięci operacyjnej RAM lub portów we-wy, pomijając przy tym CPU.
- W najprostszym użyciu proces wywołuje gdzieś ***setjmp***, a później wywołuje ***longjmp***. Z grubsza, wywołanie longjmp przywraca proces w takim stanie, w jakim istniał, kiedy wywołało setjmp.
:::
### Static
- Zmienna globalna lub procedura
- ***Działanie***: W tym przupadku static mówi kompilatorowi, aby nie udostępniał zmiennej dla innych plików źródłowych. Jeśli inny plik spróbuje użyć zmiennej, być może używając słowa kluczowego extern, wygeneruje błąd (unresolved external symbol). Ta sama koncepcja dotyczy funkcji, których dostęp chcesz ograniczyć do bieżącego pliku.
- ***Użycie***: Jest to bardzo przydatne do tworzenia file-private zmiennych i funkcji. W ten sposób też możemy nadać im dowolne nazwy bez ryzyka kolizji nazw w globalnej przestrzeni nazw.
- Zmienna lokalna
- ***Działanie***: Zmienna w kontekście funkcji jest tworzona przy pierwszym jej wywołaniu i później pamięta swoją wartość pomiędzy wywołaniami funkcji.
- ***Użycie***: To świetny sposób na śledzenie, ile razy funkcja została wywołana, więc dobrze sprawdza się przy generowaniu unikalnych numerów identyfikacyjnych. Przydatne jest również śledzenie, czy funkcja jest wywoływana po raz pierwszy.
### Restrict
- ***Działanie***: Restrict to słowo kluczowe. Dodając ten kwalifikator typu, programista wskazuje kompilatorowi, że dostęp do wartości na który wskazuje wskaźnik, będzie odbywał się wyłącznie z użyciem tegoż wskaźnika lub wartości bezpośrednio z niego pochodząca. Restrict ogranicza skutki aliasingu (odwołanie do obiektu zapomocą wielu wskaźników) wskaźnika, wspomagając optymalizacje. Jeśli deklaracja intencji nie jest przestrzegana, a dostęp do obiektu uzyskuje się za pomocą innego wskaźnika, spowoduje to niezdefiniowane zachowanie.
## Zadanie 5
:::info
Autor: Kacper Solecki
:::
```c=
s += (b[j+1] + b[--j])
```
```=
j1 := j + 1
j1 := j1 * 4
t := b + j1
res := *t
j := j - 1
j2 := j * 4
t := b + j2
x := *t
res := res + x
s := s + res
```
```c=
a[i++] -= *b * (c[j*2] + 1)
```
```=
i := i + 1
x := *b
j2 := j * 8
t := c + j2
y := *t
y := y + 1
x := x * y
i2 := i - 1
i2 := i2 * 4
t := a + i2
z := *t
z := z - x
*t := z
```
## Zadanie 6
:::info
Autor: Andriy Bernad
:::
struktura A:
```c=
struct A{
int8_t a; 1bajt
... 3bajty wyrównania
void *b; 4bajty
int8_t c; 1bajt
... 1bajt wyrównania
int16_t d; 2bajty
}
// rozmiar struktury A=12 bajtów
```
Liczymy: vs->d = us[1].a + us[j].c
```=c
i := 1
t1 := i * 12 // ponieważ us jest tablicą elementów 'struct A'
t1 := us + t1
t1 := t1 + 0 // offset a
res1 := *t1 // us[1].a
t2 := j * 12
t2 := us + t2
t2 := t2 + 8 // offset c
res2 := *t2 // us[j].c
t3 := vs + 10 // vs->d
t4 := res1 + res2
*t3 := t4 // vs->d = us[1].a + us[j].c
```
## Zadanie 7
:::info
Autor: Jakub Zając
:::
```c=
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--;
}
}
}
```
bloki podstawowe - blok sekwancyjnych instrukcji które nie zawierają skoków, taki blok może mieć tylko jeden punkt wejścia i wyjścia.
graf przepływu sterowania - graf skierowany który prezentuje wszystkie możliwe przejścia w trakcie wykonania programu między blokami podstawowymi które są jego wierzchołkami
```=
i := 0 <<B0>>
L0: if i => length goto EL0 <<B1>>
j := i <<B2>>
L1: if j <= 0 goto EL1 <<B3>>
tj := j * 4 <<B4>>
t2 := arr[tj]
t3 := tj - 4
t4 := arr[t3]
if t2 >= t4 goto EL1
arr[j] := t4 <<B5>>
arr[t3] := t2
j := j - 1
goto L1
EL1: i := i + 1 <<B6>>
goto L0
EL0: return <<B7>>
```
```graphviz
digraph {
B0[label="B0\ni := 0 "]
B3[label="B1\nif i => length"]
B1[label="B2\nj := i"]
B2[label="B3\nif j <= 0"]
B4[label="B4\ntj := j * 4\nt2 := arr[tj]\nt3 := tj - 4\nt4 := arr[t3]\nif t2 >= t4"]
B5[label="B5\n arr[j] := t4\narr[t3] := t2\nj := j - 1"]
B6[label="B6\ni := i + 1 "]
start -> B0 -> B1
B1 -> B2 [color=green]
B3 -> B4 [color=green]
B4 -> B5
B2 -> B3 [color=green]
B6 -> B1
B1 -> end [color=red]
B2 -> B6 [color=red]
B3 -> B6 [color=red]
B5 -> B1
}
```
## Zadanie 8
:::info
~~Autor: Łukasz Stasiak~~
Autor: Andrzej Tkaczyk
:::
funkcja secret kopiuje bajt po bajcie z from do to
```c=
void secret1(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: do { *to++ = *from++;
l7: *to++ = *from++;
l6: *to++ = *from++;
l5: *to++ = *from++;
l4: *to++ = *from++;
l3: *to++ = *from++;
l2: *to++ = *from++;
l1: *to++ = *from++;
} while (--n > 0);
}
```
:::spoiler
```c=
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;
}
```
:::
> [name=Franciszek Malinka] Da się to zrobić nie korzystając z pętli do.. while.
Sign in with Wallet
Connect another wallet