# Lista 1 (4. marca 2021), grupa pwit

###### tags: `ask21` `ć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!**

Tabelka zawiera tylko osoby zapisane do grupy. Osoby oczekujące proszone są o wpisanie się do osobnej tabelki poniżej.

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| --------------------:| --- | --- | --- | --- |:---:|:---:| --- |:---:|
|Wojciech Adamiec | X |==X==| X | | X | X | X | |
|Kacper Bajkiewicz |==X==| X | X | X | X | X | X | X |
|Bartłomiej Hildebrandt|==X==| X | X | X | X | X | X | |
|Dominik Komła | X | X | X | X | X | X | X | X |
|Aleksandra Kosińska | X | X | X | X | X | X | X | X |
|Oleś Kulcewicz | | | | | | | | |
|Damian Lukas | X | X | X | | X | X | | |
|Michał Mikołajczyk | X | X | X | |==X==| X | X | |
|Mateusz Opala | X | X | X | X | X | X | X | X |
|Łukasz Orawiec | X | X | X | X | X | | X | X |
|Szymon Pielat | X | X |==X==| | X | X | X | |
|Łukasz Pluta | X | X | X | X | X | X | X | X |
|Kamil Puchacz | X | X | X | X | X | X | X | ==X== |
|Magdalena Rzepka | X | X |==X==| X | X | X | X | X |
|Cezary Stajszczyk | X | X | X | X | X | X | X | X |
|Jakub Szajner | X | X | X | X | X | X | X | X |
|Bartosz Troszka | ==X== | X | X | X | X | X | X | X |
|Miłosz Urbanik | X | X | X | X | X | X | X | X |
|Oleś Kulczewicz | X | X | X | X | X | X | X | |

Tabelka dla osób oczekujących na zapis.

| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| --------------------:| --- | --- | --- | --- |:---:|:---:| --- |:---:|
|  Łukasz Stasiak | X | | X | X | X | X | | ==X== |

:::

## Zadanie 1
:::info
Autor: Kacper Bajkiewicz
:::

uint32_t copy_bit( uint32_t x, uint32_t i, uint32_t k ){
    uint32_t i_bit = (x >> i) & 1;
    x = x & ~( 1 << k ); //zerujemy k-ty bit
    return x | ( i_bit << k );
}

Celem drugiej linijki jest dostać się do bitu znajdującego się na i-tej pozycji w liczbie x.
Później chcemy wyzerować k-ty bit w x.
1 << k to jedynka na k-tym miejscu z samymi zerami na pozostałych, więc jej negacja ma zero na k-tym miejscu i jedynki na wszystkich miejscach od zerowego do k-1szego.
Kiedy więc zrobimy x & ~(1 << k), to w zmiennej x zgasimy k-ty bit (bo and-ujemy z 0), pozostałe bity pozostaną niezmienione(ANDowanie z 1).
Wyrażenie i_bit << k to liczba składająca się z i-tego bitu w liczbie x na k-tej pozycji (na innych pozycjach będą same zera).
x | (i_bit << k) da więc liczbę x z przekopiowanym i-tym bitem na k-tą pozycję (bo na k-tym miejscu wykonamy ORa na zerze z i-tym bicie w x, co da i-ty bit w x a na pozostałych miejscach na ORze z zerem, co nie zmieni tych bitów).

copy_bit( 22, 4, 0 ) zwróci liczbę 23. 10110 -> 10111
copy_bit( 22, 0, 4 ) zwróci liczbę 6. 10110 -> 00110
copy_bit( 22, 3, 3 ) zwróci liczbę 22. 10110 -> 10110
## Zadanie 2
:::info
Autor: Wojciech Adamiec
:::

:::info
Napisz fragment kodu, który wyznaczy liczbę zapalonych bitów w zmiennej x.

UWAGA! Oczekiwana złożoność to O(logn), gdzie n to liczba bitów w słowie. Posłuż się strategią „dziel i zwyciężaj”.
:::

https://en.wikipedia.org/wiki/Hamming_weight

int aux(uint32_t x){
    uint32_t m1  = 0x55555555; // 01010101010101010101010101010101
    uint32_t m2  = 0x33333333; // 00110011001100110011001100110011
    uint32_t m4  = 0x0f0f0f0f; // 00001111000011110000111100001111
    uint32_t m8  = 0x00ff00ff; // 00000000111111110000000011111111
    uint32_t m16 = 0x0000ffff; // 00000000000000001111111111111111
    
    x = (x & m1 ) + ((x >>  1)  & m1 ); //put count of each 2 bits into those 2 bits  
    x = (x & m2 ) + ((x >>  2)  & m2 ); //put count of each 4 bits into those 4 bits 
    x = (x & m4 ) + ((x >>  4)  & m4 ); //put count of each 8 bits into those 8 bits 
    x = (x & m8 ) + ((x >>  8)  & m8 ); //put count of each 16 bits into those 16 bits 
    x = (x & m16) + ((x >> 16)  & m16); //put count of each 32 bits into those 32 bits
    return x;
}

Co się dzieje w pojedynczym kroku:


Jak wygląda całość algorytmu:


## Zadanie 3
:::info
Autor: Szymon Pielat
:::

> [name=Piotr Witkowski] Na razie przyjmujemy "niestandardową" konwencję, że mamy Unix x86-64 ale ze wskaźnikami o rozmiarze 32-bitów.

Struktura A:

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:

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:

struct B {
    uint16_t a; -- 2 bajty
                -- 6 bajty
    double b;   -- 8 bajtów
    void *c;    -- 4 bajty
                -- 4 bajty
};
Suma = 24 bajty

Optymalizacja:

struct B {
    double b;   -- 8 bajtów
    void *c;    -- 4 bajty
    uint16_t a; -- 2 bajty
                -- 2 bajty
};
Suma = 16 bajtów

> []Standardowe konwencje:
>
a) Unix x86

> W domu proszę skompilować przykładowy program z tymi strulturami tak:
> gcc -m32 nazwa.c -o program_wynikowy
> (być może trzeba doinstalować pakiet multilib)
> zobacz: x86 struct alignment w google.

b) Unix x86-64:

struct B {
    uint16_t a; -- 2 bajty
                -- 6 bajty
    double b;   -- 8 bajtów
    void *c;    -- 8 bajtów
}
Optymalizacja:

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

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

Suma = 24 bajty

Optymalizacja:

struct A {
    void *b;   -- 8 bajty
	int16_t d; -- 2 bajty
    int8_t a;  -- 1 bajt
    int8_t c;  -- 1 bajt
		 -- 4 bajty
};
Suma = 16 bajtów

## Zadanie 4
:::info
Autor: Łukasz Orawiec
:::

* ```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

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``` mówi kompilatorowi, że oznaczony tym słowem kluczowym wskaźnik jest jedynym wskaźnikiem wskazującym na obiekt, na który wskazuje

## Zadanie 5
:::info
Autor: Michał Mikołajczyk
:::

// C
s += b[j+1] + b[--j];

// TAC
t1 := j + 1
t2 := t1 * 4
t3 := b + t2
t4 := *t3       // b[j+1]

j  := j - 1
t5 := j * 4
t6 := b + t5
t7 := *t6       // b[--j]

s := s + t4     // s += b[j+1]
s := s + t7     // s += b[--j]

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

// TAC
t1 := i * 4
i  := i + 1     // i++
t2 := a + t1    // Adres a[i++] (a[i])
t3 := *t2       // a[i]

t4 := *b        // *b

t5 := j * 2
t6 := t5 * 4
t7 := c + t6
t8 := *t7       // c[j*2]

t9 := t8 + 1    // c[j*2] + 1

t10 := t4 * t9  // *b * (c[j*2] + 1)

t11 := t3 - t10 // a[i] - (*b * (c[j*2] + 1))
*t2 := t11      // a[i] -= *b * (c[j*2] + 1)

## Zadanie 6
:::info
Autor: Jakub Szajner
:::

konwencja dokładnie taka, o jaką prosili w zadaniu 3 (unix x86 (32 bity)):

struct A {
int8_t a;   // 1 bajt
            // 3 bajty wypełnienia
void *b;    // 4 bajty
int8_t c;   // 1 bajt
            // 1 bajt
int16_t d;  // 2 bajty
};
// sizeof(struct A) == 12





t1 := vs + 10
t2 := us + 12
t3 := j * 12
t4 := us + t3
t5 := t4 + 8
t6 := *t2
t7 := *t5
t8 := t6 + t7
*t1 :=t8

## Zadanie 7
:::info
Autor: Miłosz Urbanik
:::

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

Insert sort w kodzie trójkowym

            i := 0                            //B1     
FBegin:     if (i >= length) goto End         //B2
            j := i                            //B3
            zero := 0
WBegin:     if (j <= zero) goto WEnd         //B4
            t0 := j * 4                      //B5
            t1 := t0 - 4
            adr0 := arr + t0
            adr1 := arr + t1
            elem0 := *adr0   //arr[j]
            elem1 := *adr1   //arr[j-1]
            if (elem0 >= elem1) goto WEnd
            *adr0 := elem1                  //B6
            *adr1 := elem0
            j := j - 1
            goto WBegin
WEnd:       i := i + 1                     //B7
            goto FBegin
End:        return                         //B8

digraph{
    START -> B1;
    B1->B2;
    B2->B3, B8;
    B3->B4;
    B4->B5, B7;
    B5->B6, B7;
    B6->B4;
    B7->B2
    B8->END
}

* blok podstawowy - fragment kodu, do którego mamy jedno wejście na jego początku oraz wyjście na jego końcu. Bez możliwości rozpoczęcia wykonywania instrukcji od żadnego innego miejsca bloku.

* graf przepływu sterowania - graf skierowany ilustrujący wejścia i wyjścia pomiędzy blokami podstawowymi. Wierzchołki to bloki podstawowe, a krawędzie to skoki pomiędzy nimi.

## Zadanie 8
:::info
Autor: Kamil Puchacz
:::

:::info
Być może jest to zaskakujące, ale poniższy kod jest poprawny i w dodatku czasami korzysta się z tej niskopoziomowej techniki optymalizacji. Co robi procedura «secret»?
:::

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

Ta procedura kopiuje n bajtów (lub liczb typu uint8_t) z położenia w pamięci from do pamięci położonej pod adresem 'to'.
Procedura Secret to taki odpowiednik procedury memcpy.
przypadki case zastępują nam w tym przypadku etykiety oraz skoki goto. W rzeczywistości jest to sekwencyjny kod zaczynający się od case 0 (po prostu jest oetykietowany).

Trzeba jeszcze napisać wersje z goto:

void secret2(uint8_t *to, uint8_t *from, size_t count) {
    size_t n = (count + 7) / 8;

    static void* label[]={ &&case_0, &&case_1, &&case_2, &&case_3, &&case_4, &&case_5, &&case_6, &&case_7};
    goto *label[count%8];

    case_0: *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++;
    --n;
    if(n>0) goto *label[0];
}