# Ć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
:::
```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
:::
```=
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
:::
```=
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
:::
```
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
}
}
```
Google Drive
Gist
Clipboard
Sign in with Wallet
