# 2025q1 Homework4 (quiz3+4)
> contribute by ginsengAttack
## 第4周
### 第一題
在計算 CRC 碼的時候，會先選定一個 CRC 多項式，像最初的實做就是`0x82f63b78`。

因為 CRC 的最低8位可以決定是否互斥或，所以把迴圈拆解:

crc = (crc >> 1) ^ A;
crc = (crc >> 1) ^ B;
...
crc = (crc >> 1) ^ H;

然後我們可以把它寫成:
$crc = (((((crc >> 1)⊕A)>> 1)⊕B)>>1)⊕C...$
最終歸納為:

(crc >> 8) ^ (A >> 7) ^ (B >> 6) ^ (C >> 5) ^ (D >> 4) ^ (E >> 3) ^ (F >> 2) ^ (G >> 1) ^ H

然後將之合併:

(crc >> 8) ^ T

剛才提到，這個數字是由 CRC前面8個 bits 和多項式計算而來，因為多項式是固定的，所以最終 T 值的差別僅由 CRC前面8個 bits 決定。

有$2^8=256$種排列組合。先計算就可以透過查表來完成。

但是256種排列組合花費的空間太大，可以拆成 4-bits 和 4-bits 的方式查找，用一樣的方法預先算出結果，提供的程式碼:

/* CRC32C polynomial */
#define POLY  0xEDB88320
void generate() {
    printf("static const uint32_t crc32_table[16] = {\n");
    for (size_t i = 0; i < 16; i++) {
        uint32_t crc = i;
        for (uint32_t j = 0; j < 4; j++)
            crc = (crc >> 1) ^ (-(int)(crc & 1) & POLY);
        printf("    0x%08X%s", crc, (i % 4 == 3) ? ",\n" : ", ");
    }

    printf("};\n");
}

輸出結果:

static const uint32_t crc32_table[16] = {
    0x00000000,     0x1DB71064,     0x3B6E20C8,     0x26D930AC,
    0x76DC4190,     0x6B6B51F4,     0x4DB26158,     0x5005713C,
    0xEDB88320,     0xF00F9344,     0xD6D6A3E8,     0xCB61B38C,
    0x9B64C2B0,     0x86D3D2D4,     0xA00AE278,     0xBDBDF21C,
};

但是老師的要求是:具備與 `crc32_naive` 完全等效的行為。

uint32_t crc32_u8(uint32_t crc, uint8_t v)
{
    crc ^= v;
    static const uint32_t crc32_table[] = {
        0x00000000, 0x105ec76f, 0x20bd8ede, 0x30e349b1, 
        0x417b1dbc, 0x5125dad3, 0x61c69362, 0x7198540d, 
        0x82f63b78, 0x92a8fc17, 0xa24bb5a6, 0xb21572c9, 
        AAAA,       BBBB,       CCCC,       DDDD,
    };
    
    crc = (crc >> 4) ^ crc32_table[crc & 0x0F];
    crc = (crc >> 4) ^ crc32_table[crc & 0x0F];
    return crc;
}

這個`crc32_u8`是老師自定義的函數，邏輯上與[Fast CRC32](https://create.stephan-brumme.com/crc32/)提供的沒有區別。

本來覺得剛剛的輸出結果就應該就是答案，但是發現我遺漏了一個重要的關鍵，也就是一開始定義的 CRC 多項式。

這個值不同，計算出的 CRC 當然不同，替換掉這個數字算出新的表:

static const uint32_t crc32_table[16] = {
    0x00000000,     0x105EC76F,     0x20BD8EDE,     0x30E349B1,
    0x417B1DBC,     0x5125DAD3,     0x61C69362,     0x7198540D,
    0x82F63B78,     0x92A8FC17,     0xA24BB5A6,     0xB21572C9,
    0xC38D26C4,     0xD3D3E1AB,     0xE330A81A,     0xF36E6F75,
};

### 測驗3
select 函數的定義:

select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds,struct timeval *timeout)

第一個參數nfds:
> The number of socket descriptors to be checked. This value should be one greater than the greatest number of sockets to be checked.
You can use the select() call to pass a bit set containing the socket descriptors for the sockets you want checked. The bit set is fixed in size using one bit for every possible socket. Use the nfds parameter to force select() to check only a subset of the allocated socket bit set.

要比最高監聽數字還要高1，也就是 `server_fd + 1` 剛好程式碼已經幫我們計算 `max_fd = server_fd + 1`

而第二個參數readfds:
> Points to a bit set of descriptors to check for reading.

要讀取的集合，也就是`rfds`

## 第3周
### 測驗1

static size_t ceil_div(size_t n, size_t d)
{
    return (n+d-1)/d;
}

取上界的除法，歸納成兩種情況:
1. 有餘數 (1~d-1)
2. 沒有餘數 (0)

要把有餘數的結果加一，沒有的維持原本的結果，我們只需要在除以 d 之前先加一個 d-1 ，這樣子沒有餘數的情況下得出的餘數會變成 d-1 但是商不變，就不會影響到最終結果。如果是至少餘數為1的情況，就會讓商增加1。

#define INTMAX 0x7fffffff

void mpi_set_u64(mpi_t rop, uint64_t op)
{
    size_t capacity = ceil_div(64, 31);

    mpi_enlarge(rop, capacity);

    for (size_t n = 0; n < capacity; ++n) {
        rop->data[n] = op & INTMAX;
        op >>= 31;
    }
  
    for (size_t n = capacity; n < rop->capacity; ++n)
        rop->data[n] = 0;
}

這個函數是要把64 bits 數字轉換成自定義的資料結構 mpi_t，因為 data 中只使用31 bits 儲存，所以`&0x7fffffff`，就可以只取31 bits 出來，然後在位移31 bits，準備取下一段。

接著 rop 沒被填滿的部分用0填充。

for (size_t n = 0; n < op1->capacity; ++n) { 
    for (size_t m = 0; m < op2->capacity; ++m) {
        uint64_t r = (uint64_t) op1->data[n] * op2->data[m];
        uint64_t c = 0;
        for (size_t k = m+n; c || r; ++k) {
            if (k >= tmp->capacity)
                    mpi_enlarge(tmp, tmp->capacity + 1);
            tmp->data[k] += (r & INTMAX) + c;
            r >>= 31;
            c = tmp->data[k] >> 31;
            tmp->data[k] &= INTMAX;
        }
    }                                     
}

做乘法運算的時候，概念和直式乘法相同，第一個數字的第 n 項乘以第二個數字的第 m 項，結果會存在第 n+m 項。

for (size_t i = start; i != (size_t) -1; --i) {
    mpi_mul_2exp(r, r, DDDD);
    if (mpi_testbit(n0, i) != 0)
        mpi_setbit(r, 0);
    if (mpi_cmp(r, d0) >= 0) {
        mpi_sub(r, r, d0);
        mpi_setbit(q, i);
    }
}

除法運算也是類似直式除法，每次算出來的餘數要往右位移，然後能減掉除數就減，不能就到下一輪。

這是因為除法是從最高位開始，所以要一直乘以2。

void mpi_gcd(mpi_t rop, const mpi_t op1, const mpi_t op2)
{
    if (mpi_cmp_u32(op2, 0) == 0) {
        mpi_set(rop, op1);
        return;
    }
        
    mpi_t q, r;
    mpi_init(q);
    mpi_init(r);

    mpi_fdiv_qr(q, r, op1, op2);

    mpi_gcd(rop,op2,r);                                     

    mpi_clear(q);
    mpi_clear(r);
}

輾轉相除法，把餘數和 op2 代入函數就可以了。

### 測驗2

/* Nonzero if X (a long int) contains a NULL byte. */
#define DETECT_NULL(X) \
    (((X) - (0x0101010101010101)) & ~(X) & (0x8080808080808080))

這個巨集會在 X 存在 null bytes 的時候回傳非0值。

#define DETECT_CHAR(X, mask) DETECT_NULL(X^mask)

利用這個巨集，在我們對兩個值做互斥或的時候，如果 X 和 mask，存在某個 bytes 相同，就會出現全部為0的 bytes，然後回傳非零值。

接著進行搜尋操作，可以一次比對整個 block ，但是要考慮到記憶體沒有對齊的問題，所以先一個 bytes 一個 bytes 比對，直到對齊在一次比較整個block。

unsigned long mask = d << 8 | d;
mask |= mask << 16;
for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
    mask |= mask<<i;

如果對齊後的字串長度大於一個 block ，先製作一個 mask，型別為 long ，其中每一 bytes 都填充成 d

while (len >= LBLOCKSIZE) {
    if (DETECT_CHAR(*asrc, mask))
        break;
    asrc++;
    len -= LBLOCKSIZE;
}

一開始是為了比對每個 bytes ，所以才把 str 轉型為 char，現在要比較一整個 block，所以轉型為 long，而且這樣子我們對 asrc++，就是跳4個 bytes。

while (len--) {
    if (*src == d)
        return (void *) src;
    src++;
}

最終我們再把不足一個 block 的部分分開處理。

detect null 的巨集，概念是只有某 bytes 為0的時候，取 not 和 -1，才有可能同時導致最左邊的 bits 為1。

### 測驗3

enum { ENV_UNUSED, ENV_RUNNABLE, ENV_WAITING };

狀態有三種。

int env;
for (env = 0; env < NENV; env++) {
    if (envs[env].status == ENV_UNUSED) /* Found a free environment */
        break;
}
if (env == NENV) /* No free environments available */
    return -1;
envs[env].status = ENV_RUNNABLE;

找到可用資源回傳，否則回傳-1。

static void coro_schedule(void)
{
    int attempts = 0;
    while (attempts < NENV) {
        int candidate = (curenv + attempts + 1) % NENV;
        if (envs[candidate].status == ENV_RUNNABLE) {
            curenv = candidate;
            /* Request delivery of TIMERSIG after 10 ms */
            timer_settime(timer, 0, &ts, NULL);
            setcontext(&envs[curenv].state);
        }
        attempts++;
    }
    exit(0);
}

找尋排程候補，但是必須+1，否則會有 starvation 問題。

void coro_yield(void)
{
    envs[curenv].state_reentered = 0;
    getcontext(&envs[curenv].state);
    if (envs[curenv].state_reentered++ == 0) {
        /* Context successfully saved; schedule the next user-level thread to
         * run.
	 */
        coro_schedule();
    }
    /* Upon re-entry, simply resume execution */
}

這個函數用來將執行權限讓給下一個執行序，所以先進行 context switch 才執行`coro_schedule`。

static void preempt(int signum UNUSED,
                    siginfo_t *si UNUSED,
                    void *context UNUSED)
{
    coro_yield();
}

而這個函數則是實作了搶佔，所以要使用`coro_yield`才能保證他有進行 context switch。