2025q1 Homework4 (quiz3+4)

contributed by < Brianpan >

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
避免使用不必要的 emoji 字元

Quiz 3

Q1

完整程式碼

目標

理解高精度無號整數運算
以區塊為單位的四則運算和位元操作

結構體定義










#include <inttypes.h>
#include <stdint.h>

/* mpi: Multi-Precision Integers */
typedef struct {
    uint32_t *data;                           
    size_t capacity;
} mpi_t[1];
        
typedef size_t mp_bitcnt_t;

mpi_t[1]的理由: 根據03/04課堂筆記將mpi_t定義為一個元素的陣列,在編譯時便可確保 mpi_t 始終會佔據一個 struct 的空間。而使用陣列的形式而非指標，即可不需要再額外分配記憶體

上取整數的商, 此計算方法是利用餘數定義

0 \leq r < d

同時加上d-1

d - 1 \leq r^{'} < (2 d - 1)

(2d -1)/d的商數仍是1故這個方法成立
詳細步驟參見





/* ceiling division without needing floating-point operations. */
static size_t ceil_div(size_t n, size_t d)
{
    return (n + d - 1)/d;
}

此程式每個區塊我們最大利用的空間為31位元
因此我們的INTMAX會是0x7ffffff

mpi_set_u64的邏輯是

確立容量多少的mpi_t, uint64_t需要三
每個block最多存31位元資料,透過INTMAX & 操作去取得數值
下一輪即是右移31位元並繼續比較
















#define INTMAX 0x7ffffff

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;
}

mul_naive

略過初始化和清理區域變數
乘法的主要邏輯是這個雙層迴圈
乘數和被乘數以區塊為單位相乘得到的結果再放置到相應的位置

舉個例子 n = 0, m = 1
先將對應區塊的乘積算出, 也就是變數r,使用uint64_t是因為兩個31位元大小乘法必須使用64位元存放
c變數為進位的數值

再來是填格子,把乘積放到對應的位置
k從m+n開始算起,因為至少會從m+n位開始填
可以想成指數乘法
繼續條件是考慮是否有進位或是仍有數值沒處理














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;
        }
    }                                     
}

除法與餘數運算

利用的函式：
mpi_sizeinbase: 計算需要多少個位元, 8 ->

2^{3}

結果為三
mpi_mul_2exp:取得

r * 2^{x}

->這裡的x是1
mpi_testbit:比較某個索引的值是否是1
mpi_setbit:設置特定位元至某個索引
mpi_sub: mpi減法運算

主要程式邏輯可以想成直式除法

m p i_{m} u l_{2} e x p (r, r, 1);

的用意是上一輪結束後要和新一輪位數合併
至於使用1的理由是我們是以二進位表示法的除法

接著判斷被除數的新加進來的最右位是否存在
存在就設置位元
第二個if是直式除法的核心邏輯
如果現在被除數的值比除數大,減掉被除數, 並設置商在該i位元為一
比起十進位簡化很多,因為二進位除法一個位數的商只有0或1兩種可能











size_t start = mpi_sizeinbase(n0, 2) - 1;

for (size_t i = start; i != (size_t) -1; --i) {
    mpi_mul_2exp(r, r, 1);
    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);
    }
}

計算最大公因數

用的是輾轉相除法的定義解


















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);
}

Q2

完整程式

目標

理解 SIMD within a register (SWAR) 技巧
實作以區塊為單位的快速字元搜尋

SWAR

透過利用硬體的word大小, 一次進行以word大小的區塊做操作
本題是一次比較sizeof(long)長度的字串是否包含要找尋的目標字元

memchr_opt

函數定義： void *memchr_opt(const void *str, int c, size_t len)
找到出現字元c的指標位置,如果沒有回傳NULL

改進的方法是利用SWAR技巧一次比較一個word大小
本題是比較sizeof(long)

主要程式邏輯

迴圈判斷是否對齊並檢查沒對齊的字元是否符合條件







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

以一個sizeof(long)的大小去比較該字元是否存在這個區塊中, 這裡也是程式的精髓,
透過位元運算把一個字元大的字元變成sizeof(long)





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

透過特殊設計的DETECT_CHAR巨集判斷字元是否在內






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

最後是去搜尋sizeof(long)長度的區塊是哪一個包含目標字元,當然如果len等於0代表沒有找到,回傳NULL

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

   return NULL;
}

解構DETECT_CHAR










#if LONG_MAX == 2147483647L
#define DETECT_NULL(X) (((X) - (0x01010101)) & ~(X) & (0x80808080))
#else
#if LONG_MAX == 9223372036854775807L
/* 當 X（型態為 long）包含 NULL byte 時會是非 0 */
#define DETECT_NULL(X) \
    (((X) - (0x0101010101010101)) & ~(X) & (0x8080808080808080))

/* @return nonzero if (long)X contains the byte used to fill MASK. */
#define DETECT_CHAR(X, mask) DETECT_NULL(X^mask)

DETECT_CHAR呼叫DETECLT_NULL(X^mask)判斷X和mask是否有位元組相符
用XOR比較的理由是如果位元組相同回傳0x00

接著解構DETECT_NULL巨集

(X) - (0 x 0101010101010101)

: 如果某個位元組是0x00相減過後為0xFF

(X)

: 取一補數後0x00會變為0xFF

(0 x 8080808080808080)

:如果該字元是0x00前面兩個操作結束後的最高位是1

Q3

目標

了解linux當中的signal
了解搶佔式coroutine

詳見整理筆記

建立coroutine後要更改狀態是可排程ENV_RUNNABLE





















int coro_create(coro_entry entry, void *args)
{
    /* Search for an available environment slot */
    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;

    /* Initialize the context for the new user-level thread */
    getcontext(&envs[env].state);
    make_stack(&envs[env].state);
    envs[env].state.uc_link = &exiter;
    makecontext(&envs[env].state, (void (*)(void)) entry, 1, args);

    /* Return the identifier of the newly created user-level thread */
    return env;
}

排程coroutine使用attempts + 1 避免重複在試同一個coroutine















static void coro_schedule(void)
{
    int attempts = 0;
    while (attempts < NENV) {
        int candidate = (curenv + BBBB) % 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);
}

coro_yield: 讓出資源給其他coroutine












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 */
}

搶佔coroutine就是讓出現在的資源給其他coroutine






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

Quiz 4

Q1

目標

CRC (循環冗餘校驗，Cyclic Redundancy Check) 的運作方法

CRC 計算時，不是使用標準的數字除法，而是透過 XOR 運算來模擬二進位多項式的除法

在計算 CRC 時，使用資料的多項式去除以預先指定的 CRC 多項式，取餘數作為校驗碼。例如，給定資料 11010101（8-bit），若用 0x1EDC6F41 來除，就會得到一個 32-bit 餘數，這就是 CRC32 的值。

在編譯器最佳化的運作下(cmov)使用三元運算子會有更好的效率


for (int bit = 0; bit < 8; bit++)
    crc = (crc & 1) ? ((crc >> 1) ^ UINT32_C(0x82f63b78)) ? (crc >> 1);

題目是要計算32位元組長度的CRC校驗碼產生
利用godbolt程式碼來改寫
最外層迴圈i是執行16組的預設資料
內迴圈j是每4個位元為一組























#include <stdint.h>
#include <stdio.h>

/* CRC32C polynomial */
#define POLY  0x82f63b78

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");
}

int main()
{
    generate();
}

XOR技巧


crc = (crc >> 1) ^ (-(int)(crc & 1) & POLY);

(crc & 1):檢查LSB是否為一
-(int)(crc & 1): 如果為一,取負數的32位元組表示是0xffffffff相當於所有的位元為一

& POLY: 和預設的多項式值取AND運算
(crc >> 1) ^ (上述結果)：(crc >> 1)就是等同於如果LSB是一就和POLY做XOR運算

產生後的表格






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

AAA: 0xc38d26c4
BBB: 0xd3d3e1ab
CCC: 0xe330a81a
DDD: 0xf36e6f75

Q2

沒有修過信號與系統先跳過 @@

Q3

學習目標

精簡的聊天伺服器實作
tcp socket建立流程
select 系統呼叫

聊天伺服器

主要程式碼邏輯透過下圖的描述建立一個TCP伺服器

socket() -> bind() -> listen() 在 event loop之前完成
accept()則是在event loop去取得新連接

中間有一段ioctl使得連結不是blocking
原因如註解所說斷開的連結仍可以讀取, 所以之後的read呼叫可能會卡住






int onoff = 1;
if (ioctl(new_fd, FIONBIO, &onoff) < 0) {
    printf("fcntl(%d): %s\n", new_fd, strerror(errno));
    close(new_fd);
    continue;
}

更改增加使用者

commit

主要的改動是多一個結構體userinfo的陣列存取使用者名稱




struct userinfo {
    int fd;
    char name[32];
};

在每一次accept()之後給使用者發送訊息輸入使用者名稱
並且透過set_userinfo去判斷儲存使用者名稱

並在廣播訊息的時候把發訊息的使用者名稱透過snprintf再寫給建立連接的其他檔案描述子


int sz = snprintf(userbuf, sizeof(userbuf), "[%.*s]:", (int) sizeof(users[fd].name), users[fd].name);

測驗答案

IIII: max_fd
JJJJ: &rfds