# 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.)
Sign in with Wallet
Connect another wallet