# Architektury systemów komputerowych

## Lista 10.

### Zadanie 1.

- $T_{avg seek} = 576 / 24 / 3 \cdot 1ms = 8ms$
- $T_{avg rotation} = 1/7200RPM \cdot 60s/1min / 2 = 4.17ms$
- $T_{transfer} = 1/7200RPM \cdot 60s/1min / 32000 = 0.000026ms$
- $T_{access} = 8ms + 4.17ms + 0.000026ms = 12.17ms$

## Lista 7.

### Zadanie 5.

union elem {
    struct {
        long *p;
        long y;
    } e1;
    struct {
        long x;
        union elem *next;
    } e2;
};

elem* f(elem *el){
    elem *next = el->e2.next;
    el->e2.x = *(next->e1.p) - next->e1.y;
    return next;
}

### Zadanie 6.

typedef struct A {
    ll u[2];
    ll *v;
} SA;
typedef struct B {
    ll p[2];
    ll q;
} SB;

SB eval(SA s){
    SB ret = SB();
    ret.p[0] = s.u[1] * *(s.v);
    ret.p[1] = s.u[0] - *(s.v);
    ret.q = s.u[0] - s.u[1];
    return ret;
}

ll wrap(ll x, ll y, ll z){
    SB s = eval({x,y,&z});
    return s.q * (s.p[0] + s.p[1]);
}

### Zadanie 7.

struct P{
    long sz;
    float *tab;
};

float puzzle7(P *p, float x){
    long sz = p->sz;
    float* tab = p->tab;
    float ret = 0;
    float bs = 1;
    for(int i=0;i<sz;i++){
        ret = bs * tab[i];
        bs *= x;
    }
    return ret;
}

### Zadanie 8.

Base::doit(int):
        movl    %esi, %eax
        subl    8(%rdi), %eax
        ret
Derived::doit(int):
        movl    8(%rdi), %eax
        imull   %esi, %eax
        ret
doit(Base*):
        movq    (%rdi), %rax
        movl    $1, %esi
        movq    (%rax), %rax
        jmp     *%rax
main:
        pushq   %rbx
        subq    $32, %rsp
        movq    %rsp, %rdi
        movq    $vtable for Base+16, (%rsp)
        movl    $10, 8(%rsp)
        movl    $21, 24(%rsp)
        movq    $vtable for Derived+16, 16(%rsp)
        call    doit(Base*)
        leaq    16(%rsp), %rdi
        movl    %eax, %ebx
        call    doit(Base*)
        addq    $32, %rsp
        addl    %ebx, %eax
        popq    %rbx
        ret
vtable for Base:
        .quad   0
        .quad   0
        .quad   Base::doit(int)
vtable for Derived:
        .quad   0
        .quad   0
        .quad   Derived::doit(int)

Wielomian
## Lista 6.

### Zadanie 1.

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;

extern "C" long pointless(long n, long* p);

long pointless2(long n, long* p) {
    if (n == 0)
        return 0;

    long result2 = 0;
    long result = pointless2(n+n, &result2);
    result += result2;
    n += result;
    *p = n;
    return result;
}

int main(){
    for(int i=0;i<100;i++){
        long res = 0;
        cout << pointless2(i, &res) << " ";
        res = 0;
        cout << pointless(i, &res) << "\n";
    }

    return 0;
}

### Zadanie 2.

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
using ll = long long;

struct T{
    ll a;
    ll b;
    ll c;
};

ll a[5] = {6,7,8,10,9};

extern "C" T puzzle2(ll* a, ll n);

T puzzle2hand(ll* a, ll n){
    T ret;
    ll sum = 0;
    ll maxi = LONG_MIN;
    ll mini = LONG_MAX;
    for(ll i=0;i<n;i++){
        ll rcx = a[i];
        mini = min(mini, a[i]);
        maxi = max(maxi, a[i]);
        sum += a[i];
    }
    ret.a = mini;
    ret.b = maxi;
    ret.c = sum / n;
    return ret;
}

int main(){

    T res = puzzle2(&a[0], 5);
    T res2 = puzzle2hand(&a[0], 5);
    
    cout << res.a << " " << res.b << " " << res.c << "\n";
    cout << res2.a << " " << res2.b << " " << res2.c << "\n";

    return 0;
}

### Zadanie 3.

#include <iostream>
using namespace std;

int64_t fd(int64_t x){
    return x+5;
}

int64_t f60(int64_t x){
    return x*8;
}

int64_t f61(int64_t x){
    return x*8;
}

int64_t f62(int64_t x){
    return (x<<4) - x;
}

int64_t f64(int64_t x){
    return x >> 3;
}

int64_t f65(int64_t x){
    return x*x; 
}

int64_t (*arr[])(int64_t) = {f60, f61, f62, fd, f64, f65};

int64_t switch_prob(int64_t x, int64_t n){
    if(60 <= n && n <= 65){
        return arr[n-60](x);
    }
    return fd(x);
}

int main(){
    return 0;
}

### Zadanie 4.

#include <iostream>
using namespace std;
using ll = long long;

extern "C" ll M(ll x);
extern "C" ll F(ll x);

ll Fhand(ll x);

ll Mhand(ll x){
    return (x ? x - Fhand(Mhand(x-1)) : 0);
}

ll Fhand(ll x){
    return (x ? x - Mhand(Fhand(x-1)) : 1);
}

int main(){
    for(int i=1;i<=10;i++){
        cout << i << " " << M(i) << " " << Mhand(i) << " " <<
        F(i) << " " << Fhand(i) << "\n";
    }
    
    return 0;
}

## Lista 5.

### Zadanie 1.

.section .text
.global addu

addu:
    add %rdi, %rsi
    sbb %rax, %rax
    or %rsi, %rax
    ret

### Zadanie 2.

.section .text
.global cmp

cmp:
    sub %rsi, %rdi
    sbb %rax, %rax
    neg %rdi
    adc %rax, %rax
    ret

### Zadanie 3.

int puzzle(long x, unsigned n){
    int eax = 0;
    if(n == 0) return n;
    for(int edx=0;edx!=n;edx++){
        eax += x & 1;
        x /= 2;
    }
    return eax;
}

Popcount na pierwszych na bitach (najniższych)

### Zadanie 4.

long puzzle2(char *s, char *d){
    char* rax = d;
    do{
        char* rdx = s;
        char c;
        do{
            c = *(rdx++);
            if(c == 0){
                return rax - d;
            }
        }while(c != *rax);
        rax++;
    }while(1);
}

Liczenie najdłuższego prefiksu słowa d, które jest podsłowem słowa s.

### Zadanie 5.

#include <iostream>
using namespace std;

uint32_t puzzle3(uint32_t n, uint32_t d){
    uint64_t n2 = n;
    uint64_t d2 = d;
    d2 <<= 32;
    uint32_t edx = 32;
    uint32_t ecx = 0x80000000;
    uint32_t eax = 0;
    do{
        n2 += n2;
        int64_t r8 = n2;
        r8 -= d2;
        if(r8 >= 0){
            eax |= ecx;
            n2 = r8;
        }
        ecx >>= 1;
        edx--;
    }while(edx);
    return eax;
}


int main(){
    for(int i=1;i<=20;i++){
        for(int j=1;j<=20;j++){
            cout << puzzle3(i,j) << " ";
        }
        cout << "\n";
    }

    return 0;
}

Dzielenie całkowite liczb nieujemnych.

### Zadanie 6.

#include <iostream>
using namespace std;

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

long arr[] = {1, 5, 7, 8};

int main(){
    int i = puzzle4(&arr[0], 7, 0, 3);

    cout << i << "\n";

    return 0;
}

### Zadanie 7.

#include <iostream>
using namespace std;

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

int main(){
    return 0;
}

## Lista 4.

### Zadanie 1.

- 256
- 19
- 264
- 255
- 171
- 17
- 255
- 17
- 17

### Zadanie 2.

- 0x100 = 256
- %rdx = -10
- %rax = 16
- 0x110 = 18
- %rcx = 0
- 0x108 = 43776
- %rdx = 16
- %rdx = 22

### Zadanie 3.

#define ALPHA 0.7
#define Q16 ((uint16_t)(ALPHA * (1 << 16)))

int16_t exp_smooth(int16_t xi, int16_t s_prev, uint16_t alpha) {
    int32_t si = (int32_t)alpha * xi + ((1 << 16) - alpha) * s_prev;
    return (int16_t)(si >> 16);
}

volatile int16_t x[] = {1, 4, 3, 2};
int16_t s[] = {0, 0, 0, 0};

int main() {
    s[0] = x[0];

    for (int i = 1; i <= 10; ++i) {
        exp_smooth(x[i], s[i-1], Q16);
    }

    return 0;
}

## Zadanie 4.

long decode(long x, long y){
    long z = x + y;
    y ^= z;
    x ^= z;
    z = x & y;
    return z >> 63;
}

## Zadanie 5.

ror $24,%edi
rorq $8,%rdi
ror $24,%edi
rorq $8,%rdi
ror $24,%edi
rorq $8,%rdi
ror $24,%edi
rorq $8,%rdi
mov %edi,%eax

## Zadanie 6.

movq %rsi,%rax
addq %rcx,%rax
adcq %rdi,%rdx

## Lista 3.

### Zadanie 1.

#include <iostream>
#include <bitset>
#include <cassert>
using namespace std;

int64_t third = 0x55555556;

int64_t div3(int64_t x){
    return ((x * third) >> 32) - (-1 & x>>63);
}

int main(){
    for(int32_t i=-1e9;i<=1e9;i++){
        assert(div3(i) == (i < 0 ? -abs(i)/3 : i/3));
    }
}

### Zadanie 2.

#include <iostream>
#include <bitset>
using namespace std;

int k = 2;
int n = 4;
uint64_t a[4] = {1LL<<31, 1LL<<31, 1LL<<30, 1LL<<30};
uint64_t b[4] = {1LL<<31, 1LL<<30, 1LL<<31, 1LL<<30};;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    uint64_t tot = 0;
    uint64_t tot2 = 0;

    for(int i=0;i<n;i++){
        uint64_t res = (a[i] > b[i] ? (a[i]-b[i])*(a[i]-b[i]) : (b[i]-a[i])*(b[i]-a[i]));
        tot += res & 0x0000FFFF;
        tot2 += res >> 32;
    }
    tot2 += tot >> 32;
    
    cout << bitset<32>(tot2 >> k) << "\n";

    return 0;
}

### Zadanie 3.

$0 01100 0100000000_{16bit float} = 0.15625$

Dla normalnych floatów pewnie podobnie
subnormal min - $2^{-150}$?
positive min - $2^{-126}$
maximum num - $(2-2^{-23})*2^{127}$

### Zadanie 4.

### Zadanie 5.

1. TAK
2. NIE, MIN_INT i -1
3. TAK
4. NIE, kontrprzykład: -2147483625 -2147483415 -2147481315
5. NIE, kontrprzykład: 0 1

### Zadanie 6.

#include <iostream>
using namespace std;

uint32_t sign(uint32_t x){
    return x ^ 1<<31;
}

uint32_t log(uint32_t x){
    return (x>>23)-127 & 0x000000FF;
}

uint32_t eq(uint32_t x, uint32_t y){
    return ((x|y)==0x80000000) & (x==y);
}

int main(){
    float a = 19.5;
    int x = * ( int * ) &a;
    cout << log(x) << "\n";
}


### Zadanie 7.

uint32_t shift(uint32_t x, int32_t k){
    int32_t e = (x>>23&0x000000FF) - 127;
    uint32_t man = 0x007FFFFF;
    uint32_t exp = 0x7F800000;
    uint32_t sgn = 0x80000000;
    if(k >= 0){
        k = min(k, 255-e);
        x += k << 23;
    }
    else{
        int32_t k2 = -k;
        if(k2 > e+127){
            int32_t s = x & sgn;
            x &= ~exp | ~sgn;
            x >>= k2-e-127;
            x |= s;
        }
        else{
            x -= k2 << 23;
        }
    }
    return x;
}

### Zadanie 8.

#include <iostream>
#include <iomanip>
#include <bitset>
using namespace std;

int32_t int2float(int32_t x){
    if(x == 0) return 0;
    uint32_t sgn = x < 0;
    x = abs(x);
    uint32_t lb = __builtin_clz(x);
    uint32_t exp = 31 - lb;
    uint32_t man = ((uint32_t)(x & ((1<<(exp+1))-1)) << (32 - exp)) >> 9;
    uint32_t guard = (exp >= 23 ? (x >> exp-23 & 1) : 0);
    uint32_t round = (exp >= 24 ? (x >> exp-24 & 1) : 0);
    uint32_t stick = (exp >= 25 ? (x & (1<<(exp-24))-1) > 0 : 0);
    if(round && (guard || stick)) man++;
    if(man >> 23){
        man &= (1<<23)-1;
        man >>= 1;
        exp++;
    }
    return (sgn << 31) | ((exp+127) << 23) | man;
}

int main(){

    int32_t x = int2float((1<<30)-1);
    cout << (1<<30)-1 << "\n";
    cout << *(float*)(&x) << "\n";

    return 0;
}

### Zadanie 9.

#include <iostream>
using namespace std;

int32_t float2int(int32_t f) {
    int32_t s = f >> 31; /* -1 jeśli znak był ujemny */
    int32_t e = (f >> 23 & 255) - 127; /* wykładnik po odjęciu bias */
    uint32_t m = f << 8 | 0x80000000; /* mantysa 1.xxx... dosunięta do lewej */
    m = (e > 31 ? 0x80000000 : (m>>max(0,(31-e))));
    return m * (2*s+1);
}

int main(){
    float x = 0x80000000;

    cout << float2int(*(int32_t*)&x) << "\n";

    return 0;
}

### Zadanie 10.

## Lista 2.

### Zadanie 1.

- NIE, bo $INT\_MIN < 0$ i $INT\_MIN - 1 > 0$
- TAK, jeśli pierwszy warunek jest spełniony to reprezentacją tej liczby po przesunięciu będzie $111000000\dots_2$
- NIE, $(2^{15} + 2^{14})^2 < 0$
- TAK, $0$ spełnia, wszystkie oprócz $INT\_MIN$a też i sam $INT\_MIN$ tak samo
- TAK, bo tak powiedziałem
- NIE, bo $0$
- TAK, typy signed i unsigned dodają się tak samo, przy porównaniu następuje konwersja typu (bez zmiany reprezentacji)
- TAK, sumarycznie $y$ i $\neg y$ upraszczają się do mnożenia przez $-1$

### Zadanie 2.

x ^= y ^= x ^= y;

### Zadanie 3.

int32_t overflowcheck(int32_t x, int32_t y){
    return (~(x^y)&(s^x))>>31&1;
}

### Zadanie 4.

uint32_t simdadd(uint32_t x, uint32_t y){
    return (x & 0x7F7F7F7F) + (y & 0x7F7F7F7F) ^ (x ^ y) & 0x80808080;
}

uint32_t simdsub(uint32_t x, uint32_t y){
    return ~((x ^ y | 0x7F7F7F7F) ^ (x | 0x80808080) - (y & 0x7F7F7F7F));
}

### Zadanie 5.

int32_t threefourths(int32_t x){
    return ((x>>2)<<1) + (x>>2) + ((((x&3)<<1)+(x&3))>>2);
}

### Zadanie 6.

uint32_t lesssigned(int32_t x, int32_t y){
    return (~y&x|(~y|x)&(x^1<<31)-(y^1<<31))>>31&1;
}

uint32_t lessunsigned(uint32_t x, uint32_t y){
    return (~x&y|(~x|y)&x-y)>>31&1;
}

### Zadanie 7.

int32_t abs(int32_t x){
    return ~x>>31 & x | x>>31 & -x;
}

### Zadanie 8.

int32_t sgn(int32_t x){
    return ~x>>31 & 1 & ~(~x>>31 & x-1>>31) | x>>31 & -1; 
}

### Zadanie 9.

int32_t oddpop(uint32_t x){
    x = (x & 0x55555555) + ((x>>1) & 0x55555555);
    x = (x & 0x33333333) + ((x>>2) & 0x33333333);
    x = (x & 0x0F0F0F0F) + ((x>>4) & 0x0F0F0F0F);
    x = (x & 0x00FF00FF) + ((x>>8) & 0x00FF00FF);
    x = (x & 0x0000FFFF) + ((x>>16) & 0x0000FFFF);
    return (x & 1);
}