---
# System prepended metadata

title: 'Ćwiczenia 6, grupa śr. 17-19, 29 marca 2023'
tags: [pwit, ćwiczenia, ASK23]

---

# Ćwiczenia 6, grupa śr. 17-19, 29 marca 2023

###### tags: `ASK23` `ć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   | 6   | 7   |
| ----------------------:| --- | --- | --- | --- | --- | --- | --- |
| Mikołaj Balwicki       |     |     |     |     |     |     |     |
| Kamila Goszcz          |  X  |  X  |  X  |     |     |  X  |==X==|
| Mateusz Materek        |  X  |  X  |  X  |     |  X  |==X==|  X  |
| Mikołaj Łabędzki       |     |     |     |     |     |     |     |
:::


Tutaj można zadeklarować zadania 7, 8 i 9 z poprzedniej listy. Proszę wpisać imię, nazwisko i numery zadań:
- 
- 



:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::




## Zadanie 1
:::success
Autor:	Kamila Goszcz
:::

![](https://i.imgur.com/JHDjTU3.png)

```assembly=
withJump:
        addq %rdi, %rsi
        jnc .OK 
        movq $ULONG_MAX, %rsi
.OK:    movq %rsi, %rax
        ret
```
sbb: des = des - (src + CF)
```assembly=
noJump:
        addq %rsi, %rdi
        sbbq %rax, %rax
        orq  %rdi, %rax
        ret
```

## Zadanie 2
:::success
Autor:	Mateusz Materek	
:::
![](https://i.imgur.com/M2Uv9ct.png)

```=
cmp:
    subq %rsi, %rdi  // x = x - y
    sbbq %rax, %rax  // -CF (0 jeśli x > y, -1 jeśli x < y)
    negq %rdi        // if x != y: CF := 1
    adcq %rax, %rax  
    ret
```

Dla `x = y`: %rdi = 0, %rax = 0, %rdi = 0 (CF = 0), %rax = 0. OK
Dla `x > y`: %rdi > 0 (CF = 0), %rax = 0, %rdi < 0 (CF = 1), %rax = 1. OK
Dla `x < y`: %rdi < 0 (CF = 1), %rax = -1, %rdi > 0 (CF = 1), %rax = -2+1 = -1. OK

## Zadanie 3
:::success
Autor:	Kamila Goszcz
:::

```assembly=
puzzle: 
        testl %esi, %esi
        je .L4
        xorl %edx, %edx
        xorl %eax, %eax
.L3:    movl %edi, %ecx
        andl $1, %ecx
        addl %ecx, %eax
        sarq %rdi
        incl %edx
        cmpl %edx, %esi
        jne .L3
        ret
.L4:    movl %esi, %eax
        ret
```

```c=
//          %rdi      %rsi
int puzzle(long x, unsigned n){   
    int res = 0;
    
    for(unsigned i = 0; i < n; i++){
        int tmp = x & 1;
        res += tmp;
        x = x >> 1;
    }
    
    return res;
}
```

Funkcja zlicza liczbę zapalonych bitów w n najmłodszych bitach liczby x

## Zadanie 4
:::danger
Autor:	
:::


```clike
puzzle2:
2 movq %rdi, %rax // rax = s
3 .L3: movb (%rax), %r9b // r9b = s[0]
4 leaq 1(%rax), %r8 // r8 = s + 1; // hipoteza: r8 służy do iteracji po s?
5 movq %rsi, %rdx // rdx = d
6 .L2: movb (%rdx), %cl // cl = d[1]
7 incq %rdx // rdx = rdx + 1 = d + 2 // hipoteza: rdx służy do iteracji po d
8 testb %cl, %cl // hipoteza: iterujemy po d aż dojedziemy do końca tego łańcucha znaków
9 je .L4 // znaleźliśmy konieć d to kończymy program
10 cmpb %cl, %r9b // d[0] == s[0] ?
11 jne .L2  // if d[0] != s[0] then goto L2
12 movq %r8, %rax 
13 jmp .L3
14 .L4: subq %rdi, %rax
15 ret
```

```clike=
long puzzle2(char *s, char *d) {
   
    for (char *p = s;; p = p +1) {
        if (*q == 0) goto L4;

        for(char* q = d; *q != *p; q = q +1) {     
        if (*q == 0) goto L4;
     
    }
        
      }
  
    
        
    }
    

    .L4: return  p - s; 
      
}
```



## Zadanie 5
:::success
Autor:	Mateusz Materek	
:::
![](https://i.imgur.com/IGnzA00.png)

```=
puzzle3:
	movl %edi, %edi	  	 // B1
        salq $32, %rsi
        movl $32, %edx
        movl $0x80000000, %ecx
        xorl %eax, %eax
.L3:	addq %rdi, %rdi          // L3
        movq %rdi, %r8
        subq %rsi, %r8
        js .L2
        orl %ecx, %eax		 // B2
        movq %r8, %rdi
.L2:	shrl %ecx		 // L2
        decl %edx
        jne .L3
        ret			 // B3
```

Graf przepływu sterowania
```graphviz
digraph g{
START->B1
B1->L3
L3->B2
L3->L2
B2->L2
L2->L3
L2->B3
B3->END
}
```

```c=
uint32_t puzzle3(uint32_t n, uint32_t d){
        uint64_t nd = ((long)d) << 32;
        uint64_t nn = n;
        uint32_t counter = 32;
        uint32_t ecx = 0x80000000;
        uint32_t result = 0;

        do{
                nn += nn;
                if(nn >= nd){
                        result = result | ecx;
                        nn -= nd;
                }
                ecx >>= 1;
                counter--;
        } while(counter != 0);

        return result;
}
```

## Zadanie 6
:::success
Autor:	Mateusz Materek	
:::
![](https://i.imgur.com/GtXB1qB.png)


```
puzzle4:                            // START
        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
        jg .L11			    // B3
        leaq 1(%rax), %rdx          // B4
        call puzzle4
.L10:   ret                          // L10
.L11:   leaq -1(%rax), %rcx	     // L11
        call puzzle4
        ret
.L5:    movq $-1, %eax		     // L5
        ret
        			     // END
```

Z cheatsheeta:
```
%rdi -> a
%rsi -> v
%rdx -> s
%rcx -> e
```

```graphviz
digraph g{
		B1
		B2
		B3
		B4
		L10
		L11
		L5
        START
        END

		B1 -> B2
		B2 -> B3
		B3 -> B4

		B1 -> L5
		B2 -> L10
		B3 -> L11
		B4 -> L10
        
		START -> B1
		L5 -> END
		L10 -> END
        L11 -> END
}
```

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

To jest po prostu binsearch.

## Zadanie 7
:::success
Autor:	Kamila Goszcz	
:::

```assembly=
400590                            <switch_prob>:
400590: 48 83 ef 3c                       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ący tablicę skoków:
```assembly=
(gdb) x/6gx 0x4006f8
0x4006f8: 0x4005a1 :L0
0x400700: 0x4005a1 :l1
0x400708: 0x4005b2 :L2
0x400710: 0x4005c3 :L3
0x400718: 0x4005aa :L4
0x400720: 0x4005bf :L5
```

```c=
//                %rdi    %rsi
long switch_prob(long x, long n){
    n -= 60                        // 0x3c
    switch(n) {
        case 0:
        case 1:
            return x * 3
        case 4:
            return x >> 3
        case 2:
            x *= 15                // x = (x << 4) - x = 16x - x
        case 5:
            x *= x
        default:
            return x + 75         // 0x4b
    }
}
```
