# Lista 5 (01.04.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!**

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

:::

## Zadanie 1
:::info
Autor: Szymon Pielat
:::

%rdi = x %esi = n %eax = res

puzzle: testl %esi, %esi   // ZF = 1 if a&b ==0
        je .L4             // jeśli ZF == 1 
        xorl %edx, %edx    // i = 0
        xorl %eax, %eax    // res = 0
.L3:    movl %edi, %ecx    // %ecx = x (mlodsze 32 bity)
        andl $1, %ecx      // %ecx = x & 1
        addl %ecx, %eax    // res += x & 1
        sarq %rdi          // x = x >> 1
        incl %edx          // i += 1
        cmpl %edx, %esi    // cmp(n, i)
        jne .L3            // n != i -> loop .L3
        ret                // return %eax (res)
.L4:    movl %esi, %eax    // res = n
        ret                // return %eax (res)

%rdi = x %esi = n %eax = res

// zwraca liczbę zapalonych bitów w n najmłodszych bitach x
int puzzle(long x, unsigned n) { 
    if (n == 0) 
        return 0;
    else {
      int res = 0;
      for(unsigned i = 0; i != n; ++i)
          res += 1 & x;
          x = x >> 1;
      }
      return res;
    }
}

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

:::info
Poniżej zamieszczono kod procedury o sygnaturze «long puzzle2(char *s, char *d)». Wyznacz bloki podstawowe oraz narysuj graf przepływu sterowania. Przetłumacz tę procedurę na język C, a następnie jednym zdaniem powiedz co ona robi.
:::

char *res   = %rax (%al)
char *s     = %rdi (%dil)
char *d     = %rsi (%sil)
char  s_chr = %r9b
char *s_ptr = %r8  (%r8b)
char *d_ptr = %rdx (%dl)
char  d_chr = %cl

puzzle2:
        movq  %rdi, %rax   // B1, res = s
.L3:    movb  (%rax), %r9b // B2, s_chr = *res
        leaq  1(%rax), %r8 //     s_ptr = res+1
        movq  %rsi, %rdx   //     d_ptr = d
.L2:    movb  (%rdx), %cl  // B3, d_chr = *d_ptr
        incq  %rdx         //     d_ptr++
        testb %cl, %cl     //     ZF = 1 if a & b == 0
        je    .L4          //     d_chr == 0 (null char) => goto .L4
        cmpb  %cl, %r9b    // B4, cmp(s_chr, d_chr)
        jne   .L2          //     s_chr != d_chr => goto .L2
        movq  %r8, %rax    // B5, res = s_ptr
        jmp   .L3          //     goto .L3
.L4:    subq  %rdi, %rax   // B6, res = s
        ret                //     return (long)res

long puzzle2(char *s, char *d) {
    char *res = s;
    while (true) {
        char s_chr = *res;
        char *s_ptr = res+1;
        char d_chr;
        char *d_ptr = d;         
        do {
            d_chr = *d_ptr;
            d_ptr++;
            if (d_chr == 0) { // d_chr = 0 => koniec d
                res -= s;
                return (long)res;
            }
        } while (s_chr != d_chr);
        res = s_ptr;
    }
}

Funkcja puzzle2 zwraca długośc najdłuższego prefiksu s, który zawiera litery występujące w d.

digraph przepływ {
            START -> B1;
            B1 -> B2;
            B2 -> B3;
            B3 -> B6;
            B3 -> B4;
            B4 -> B3;
            B4 -> B5;
            B5 -> B2;
            B6 -> END;
}

## Zadanie 3
:::info
Autor: Dominik Komła
:::

digraph g{
    B1->B2;
    B2->B3;
    B2->B4;
    B3->B4;
    B4->B2;
    B4->B5;
    }

puzzle3:
        movl %edi, %edi	                #B1
	salq $32, %rsi
	movl $32, %edx
	movl $0x80000000, %ecx
	xorl %eax, %eax
.L3:	addq %rdi, %rdi                #B2
	movq %rdi, %r8              pom = n
	subq %rsi, %r8              pom -= d;
	js .L2
        orl %ecx, %eax			        #B3
	movq %r8, %rdi            n = pom     n -= d
.L2:	shrl %ecx			            #B4
	decl %edx
	jne .L3
        ret				               #B5

n - rdi
d - rsi

uint32_t puzzle3(uint32_t n, uint32_t d)
{
    uint32_t res = 0;
    uint64_t d2 = d;
    d2<<=32;
    uint64_t n2 = n;
    uint32_t m=0x80000000;
    for(int i=32;i>0;i--)
    {
        n2<<=1;
        if(n2 >= d2)
        {
            res |= m;
            n2 -= d2;
        }
        m>>=1;
    }
    return res;
}

12 / 4 na 5 bitach
n = 12
d = 4
new_d = 0b0100 << 5 == 0b010000000 = 128
edx = 5
ecx = 0b10000 = 2^4 = 16
eax = 0

do:
    new_n = 24
    r8 = 24
    r8 - new_d = bardzo duża lczba na minusie
    nie wchdzi do ifa
    przesuwamy ecx w prawo o 1: ecx = 0b01000 = 8
    edx = 4
do:
    new_n = 48
    r8 = 48
    r8= r8 - new_d - bardzo duża lczba na minusie
    nie wchdzi do ifa
    przesuwamy ecx w prawo o 1: ecx = 0b00100 = 4
    edx = 3
do:
    new_n = 96
    r8 = 96
    r8=r8 - new_d - bardzo duża lczba na minusie
    nie wchdzi do ifa
    przesuwamy ecx w prawo o 1: ecx = 0b000010 = 2
    edx = 2
do:
    new_n = 192
    r8 = 192
    r8 = r8 - new_d = 64 > 0 czyl wchodzi do ifa
    eax było 0 a teraz robimy eax |= ecx czyli eax = 2
    new_n = 64
    ecx = 1
    edx = 1
do:
    new_n = 128
    r8 = 128
    r8 = r8 - new_d = 0 >= 0 czyl wchodzi do ifa
    eax było 2 a teraz robimy eax |= ecx czyli eax = 3
    new_n = 0
    ecx = 0
    edx = 0
    
wychodzimy z pętli
zwracamy eax, które jest równe 3

Funkcja liczy $\lfloor\frac{n}{d}\rfloor$ używając dzielenia pisemnego.

"Restoring division"

## Zadanie 4
:::info
Autor: Kacper Bajkiewicz
:::
a -> %rdi
v -> %rsi
s -> %rdx
e -> %rcx

Przenosimy wartość e do do raxa, odejmujemy od niej s, dzielimy wszystko przez 2 i dodajemy wartość rax do rdx.
Czyli w rax znajduje sie (e-s)/2 + s. Porównujemy rdx < rcx, jeśli tak to wtychdozimy z programu ze zwrotem -1.
Jeśli nie to do %r8 przenosimy wartość z %rdi + %rax * 8, czyli tak naprawdę wartość ze środka tablicy danej wskaźnikiem a.
Jeśli v == tej wartości, to wychodzimy z indeksem w raxie.

Wpp jeśli v < tej wartości, to do rdx (start) przenosimy %rax + 1, czyli środek podtablicy + 1 i wywołujemy procedurę z takimi argumentami:
a -> a
v -> v
s -> (e-s)/2 + s + 1
e -> e
Wpp za e wstawiamy środek - 1, czyli ( e-s )/2 + s - 1 i wywołujemy.

Bloki podstawowe:

puzzle4:  movq %rcx, %rax                            ;B1
          subq %rdx, %rax
          shrq %rax
          addq %rdx, %rax
          cmpq %rdx, %rcx
          jb .L5                                      
          movq (%rdi,%rax,8), %r8                    ;B2
          cmpq %rsi, %r8
          je .L10                                    
          cmpq %rsi, %r8                             ;B3
          jg .L11                                    
          leaq 1(%rax), %rdx                         ;B4
          call puzzle4        
.L10:     ret                                        ;B5
.L11:     leaq -1(%rax), %rcx                        ;B6
          call puzzle4       
          ret          
.L5:      movl $-1, %eax                             ;B7
          ret

Kod w C:

int puzzle4 (long* a, long v, uint64_t s, uint64_t e)
{
    if ( e < s ){
        return -1;
    } 
    uint64_t mid = ( e-s ) / 2 + s;
    long midEl = a[mid];
    
    if ( midEl == v ){
        return mid;
    } 
    if ( v < mid ){
        return puzzle4( a, v, s, mid - 1 );
    } 
    return puzzle4( a, v, mid + 1, e );
}

digraph{
B1 -> B2
B2 -> B3
B1 -> B7
B3 -> B4
B2 -> B5
B3 -> B6
B7 -> EXIT
B6 -> EXIT
B5 -> EXIT
B4 -> B5
}

## Zadanie 5
:::info
Autor: Mateusz Opala
:::

x - rdi
n - rsi

long switch_prob(long x, long n)
{
    switch(n)
    {
        case 60:
            return x * 8;
        case 61:
            return x * 8;
        case 64:
            return x >> 3;
        case 62:
            x *= 15;
        case 65:
            x *= x;
        default:
            return x + 75;
    }
}