---
# System prepended metadata

title: 'Lista 5 (1 kwietnia 2021), grupa KBa'
tags: [kba, ask21, ćwiczenia]

---

# Lista 5 (1 kwietnia 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(2) | 4(2)  | 5(2)  |
| --------------------:| --- | --- | ---- | ----- | ----- |
|        Andriy Bernad | X   | X   |      | X     | X     | 6
|     Wojciech Bogucki | X   | X   | X    | X     | ==X== | 8
|         Michał Doros | X   | X   | X    | X     | X     | 8
|        Marko Golovko | X   | X   |      |       |       | 2
|    Magdalena Jarecka | X   | X   | X    | ==X== | X     | 8
|        Szymon Jędras |     |     |      |       |       | 0
|     Heorhii Karpenko |     |     |      |       |       | 0
|    Szymon Kosakowski | X   | X   | X    | X     |       | 6
|      Izabella Kozioł | X   | X   |      |       |       | 2
|   Franciszek Malinka | X   | X   | X    | X     | X     | 8
|         Filip Pazera | X   | X   | X    | X     | X     | 8
|    Franciszek Pindel | X   | X   | X    | X     | X     | 8
|     Kacper Puchalski |  X  |  X  | X    |  X    |       | 6
|       Kacper Solecki | X   | X   | X    | X     | X     | 8
|      Andrzej Tkaczyk | X   | X   | X    | X     | X     | 8
|    Łukasz Wasilewski | x   | x   |      |       |       | 2
| Vladyslav Yablonskyi | X   | X   |      | X     | X     | 6
|           Adam Zyzik | X   | X   | X    | X     | X     | 8
:::

## Zadanie 1

:::info
Autor: Izabella Kozioł
:::

Assembler:
```=
puzzle: testl %esi, %esi     # n&n (flags: ZF, SF, PF, OF = 0, CF = 0, AF = undef)  
        je    .L4            # ZF (equal/zero)
        xorl  %edx, %edx     # i = 0 (flags : ZF, SF, PF; OF, CF = cleared, AF = undef) 
        xorl  %eax, %eax     # res = 0 (flags : ZF, SF, PF; OF, CF = cleared, AF = undef) 
.L3:    movl  %edi, %ecx     # tmp = x              
        andl  $1, %ecx       # tmp = 1 & tmp (flags ZF, SF, PF; OF, CF = cleared, AF = undef)
        addl  %ecx, %eax     # res += tmp 
        sarq  %rdi           # x >> 1 (arythmetic) (flags : CF)
        incl  %edx           # i += 1 (preserving the state of CF)
        cmpl  %edx, %esi     # n : i (flags)
        jne   .L3            # ~ZF not equal/not zero
        ret                  #
.L4:    movl  %esi, %eax     # res = n
        ret                  #
```

C:
```C=
int puzzle(long x, unsigned n){
   // if (n == 0) return n; 
    
    int res = 0;
    
    for(unsigned i = 0; i < n; i++){
        int tmp = x & 1;
        res += tmp;
        x = x >> 1;
    }
    
    return res;
}
```
Działanie : Zliczanie zapalonych bitów w pierwszych n najmłodszych bitach liczby x.

## Zadanie 2

:::info
Autor: Adam Zyzik
:::

Funkcja `puzzle2(char* s, char* d)` zwraca długość najdłuższego prefiksu `s`, w którym każda litera występuje również w `d`.

```c99=
long puzzle2(char *s, char *d) {
    char *pos_s = s;
    while(true) {
        char *pos_d = d;
        bool found = false;
        while(*pos_d) {
            if (*pos_d == *pos_s) {
                found = true;
                break;
            }
            pos_d++;
        }
        if (!found) {
            return pos_s - s;
        }
        pos_s++;
    }
}
```
> [name=Andrzej Tkaczyk]
>:::spoiler
>```c=
> long puzzle2(char *s, char *d){
>  for(char *a=s; ; a++){
>    for(char *b=d; ; b++){
>      if(*a == *b){
>        break;
>      }
>      if(*b == 0){
>        return a - s;
>      }
>    }
>  }
>}
>```
>:::

```assembly=
puzzle2:
        movq  %rdi, %rax        <<A>>
.L3:    movb  (%rax), %r9b      <<B>>
        leaq  1(%rax), %r8
        movq  %rsi, %rdx
.L2:    movb  (%rdx), %cl       <<C>>
        incq  %rdx
        testb %cl, %cl
        je    .L4              
        cmpb  %cl, %r9b         <<D>>
        jne   .L2
        movq  %r8, %rax         <<E>>
        jmp   .L3
.L4:    subq  %rdi, %rax        <<F>>
        ret
```

```graphviz
digraph graphname {
        START -> A
		A -> B; 
		B -> C;
		C -> D;
        C -> F
        D -> E
        D -> C
        E -> B
		F -> KONIEC;
	}
```

> [name=Franciszek Malinka] pierwszego while'a możesz na fora zamienić, drugiego zresztą też
:::spoiler
```c
long puzzle2_decoded(char *s /* rdi */, char *d /* rsi */) {
    for (char *result = s ; ; result++) {
        char first = *result;
        for (char *crawl = d; *crawl != first; crawl++) {
            if (*crawl == 0) {
                return result - s;
            }
        }
    }
}
```
:::

> [name=Franciszek Pindel] można jeszcze krócej (i nie robić `return` ani `break` w środku pętli)
:::spoiler
```c
/* s - %rdi
 * d - %rsi */
long puzzle2(char *s, char *d) {
    char *actD = d;
    char *actS;
    
    for (actS = s; *actD != '\0'; actS++)
        for (actD = d; *actD != '\0' && *actD != *actS; actD++) ;
        
    return actS - s - 1;
}
```
> [name=Franciszek Malinka] to Ci się skompiluje? `char *actS` jest lokalną zmienną w pętli, nie możesz tego użyć potem w returnie poza tą pętlą.
:::

> [name=Franciszek Pindel] teraz powinno być ok.


## Zadanie 3

:::danger
Autor: Szymon Kosakowski
:::
```assembly=
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
	subq %rsi, %r8
	js .L2
	orl %ecx, %eax			    #B3
	movq %r8, %rdi
.L2:	shrl %ecx			    #B4
	decl %edx
	jne .L3
	ret				    #B5
```

Graf przepływu sterowania
```graphviz
digraph g{
START->B1;
B1->B2;
B2->B3;
B2->B4;
B3->B4;
B4->B2;
B4->B5;
B5->END;
}
```


```c=
uint32_t puzzle3(uint32_t n, uint32_t d)
{
    long new_d = ((long)d)<<32;
    long new_n = n;
    int count = 32;
    uint32_t result_bit = 0x80000000;
    uint32_t result = 0;
    do{
        new_n += new_n;
        long tmp = new_n - new_d;
        if(tmp >= 0){
            result |= result_bit;
            new_n = tmp;
        }
        result_bit >>= 1;
        count--;
    } while (count != 0)
    return result;
}
```

Funkcja liczy $\lfloor\frac{n}{d}\rfloor$


przykład dla 4-bitowych n = 7, d = 2
#### 1
rsi:
| | | | | | | | |
|-|-|-|-|-|-|-|-|
|0|0|1|0|0|0|0|0|

rdi:
(od razu przesunięte w lewo)
| | | | | | | | |
|-|-|-|-|-|-|-|-|
|0|0|0|0|1|1|1|0|

eax:
| | | | |
|-|-|-|-|
|0|0|0|0|
|^| | | |

#### 2
rsi:
| | | | | | | | |
|-|-|-|-|-|-|-|-|
|0|0|1|0|0|0|0|0|

rdi:
| | | | | | | | |
|-|-|-|-|-|-|-|-|
|0|0|0|1|1|1|0|0|

eax:
| | | | |
|-|-|-|-|
|0|0|0|0|
| |^| | |

#### 3
rsi:
| | | | | | | | |
|-|-|-|-|-|-|-|-|
|0|0|1|0|0|0|0|0|

rdi:
| | | | | | | | |
|-|-|-|-|-|-|-|-|
|0|0|1|1|1|0|0|0|

(rsi - rdi > 0)

r8:
| | | | | | | | |
|-|-|-|-|-|-|-|-|
|0|0|0|1|1|0|0|0|

eax:
| | | | |
|-|-|-|-|
|0|0|1|0|
| | |^| |

#### 4
rsi:
| | | | | | | | |
|-|-|-|-|-|-|-|-|
|0|0|1|0|0|0|0|0|

rdi:
| | | | | | | | |
|-|-|-|-|-|-|-|-|
|0|0|1|1|0|0|0|0|

(rsi - rdi > 0)

r8:
| | | | | | | | |
|-|-|-|-|-|-|-|-|
|0|0|0|1|0|0|0|0|

eax:
| | | | |
|-|-|-|-|
|0|0|1|1|
| | | |^|

## Zadanie 4

:::danger
Autor: Magdalena Jarecka
:::

:::info
Poniżej zamieszczono kod rekurencyjnej procedury o sygnaturze «int puzzle4(long *a,long v, uint64_t s, uint64_t e)». 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

```c=
*a = rdi, v = rsi, s = rdx, e = rcx
r8 = mid

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             // B10
.L11:   leaq -1(%rax), %rcx // B11
        call puzzle4
        ret
.L5:    movl $-1, %eax // B5
        ret
```
:::


```graphviz
digraph g{
		L1 [label="B1"]
		L2 [label="B2"]
		L3 [label="B3"]
		L4 [label="B4"]
		L10 [label="B10"]
		L11 [label="B11"]
		L5 [label="B5"]
        START
        END

		L1 -> L2
		L2 -> L3
		L3 -> L4

		L1 -> L5
		L2 -> L10
		L3 -> L11
		L4 -> L10
        
		START -> L1
		L5 -> END
		L10 -> END
        L11 -> END
}
```

#### Przeszukiwanie binarne

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

## Zadanie 5

:::    success
Autor: Wojciech Bogucki
:::
```scala=
400590 <switch_prob>:            switch_prob:
400590: 48 83                                subq $0x3c,%rsi
400594: 48 83 fe 05                          cmpq $0x5,%rsi
400598: 77 29                                ja *0x4005c3
40059a: ff 24 f5 f8 06 40 00                 jmpq *0x4006f8(,%rsi,8)
4005a1: 48 8d 04 fd 00 00 00 00  .L0/1       lea 0x0(,%rdi,8),%rax
4005a9: c3                                   retq
4005aa: 48 89 f8                 .L4         movq %rdi,%rax
4005ad: 48 c1 f8 03                          sarq $0x3,%rax
4005b1: c3                                   retq
4005b2: 48 89 f8                 .L2         movq %rdi,%rax
4005b5: 48 c1 e0 04                          shlq $0x4,%rax
4005b9: 48 29 f8                             subq %rdi,%rax
4005bc: 48 89 c7                             movq %rax,%rdi
4005bf: 48 0f af ff              .L5         imulq %rdi,%rdi
4005c3: 48 8d 47 4b              .L3         leaq 0x4b(%rdi),%rax
4005c7: c3                                   retq

Zrzut pamięci przechowującej
tablicę skoków:
(gdb) x/6gx 0x4006f8
0x4006f8: 0x4005a1 :L0
0x400700: 0x4005a1 :L1
0x400708: 0x4005b2 :L2
0x400710: 0x4005c3 :L3
0x400718: 0x4005aa :L4
0x400720: 0x4005bf :L5
```

```c=
long switch_prob(long x, long n){
    n-=0x3c;// stała 60, potrzebna gdy w switchu dajemy <0,5>
    switch(n){
        case 0:
        case 1:
            return x*8;
        case 4:
            return x/8;
        case 2:
            x = (x << 4) - x;
            //x*=15;
        case 5:
            x*=x;
        default:
            return x + 0x4b;
    }
}
```

> [name=Franciszek Malinka] w 10 linii w switch_prob nie powinieneś jeszcze odejmować x? Spójrz na wiersz 13 w assemblerze
> [name=Wojtek Bogucki] Faktycznie, poprawię.
> [name=Franciszek Malinka] powinno być raczej `x = (x << 4) - x`, powinna być jeszcze stara wartość `x`. 
> [name=Wojtek Bogucki] Faktycznie, dzięki, poprawię.(Orginalnie było `x = x << 4;`, zostawaim dla potomnych.)