Try   HackMD

2025q1 Homework4 (quiz3+4)

contributed by < wurrrrrrrrrr >

測驗 1

程式碼運作原理

首先看到 ceil_div 是無條件進位除法：

static size_t ceil_div(size_t n, size_t d)
{
    return AAAA;
}

他的作用為計算 n 除以 d，其中 n 可以表示為 q × d + r，其中 r 是餘數，範圍為 0 到 d-1。若 r == 0，表示整除，則結果為 q；若 r > 0，則需向上取整，結果為 q + 1，為了達成這個向上取整的效果，關鍵是觀察當 n 沒有整除時，餘數 r 的範圍會落在 1 到 d - 1。因此，而如果餘數為 1 時想進位 n 就要加 d-1 ，而如果餘數為 d - 1 時想進位 n 只要加 1，為了涵蓋所有可能的餘數，我們選擇固定補上 d - 1，也就是使用公式 (n + d - 1) / d。d - 1 這個數值雖然在某些情況下可能超過進位所需要的，但它不會導致進位超過一位，而且又能保證所有餘數大於 0 的情況下都能正確進位。
AAAA = (n+d-1)/d

第二個 mpi_set_u64() 這個函式的作用是把 uint64_t 拆解成多個 31 bit 並儲存在 mpi_t 結構中。一開始計算要幾個 31 bit來表示 64 bit 的數值，而第二段是確保 rop 有足夠空間來放這些 31 bit，如果記憶體不夠，會擴展它，再來執行了一段迴圈把 64 bit 的整數 op 拆成 31 bit 的小塊儲存到 rop->data[] 中，從低位到高位依序填入，而要如何拿出 31 bit？此時就需要一個 mask 只取後 31 位，因此 INTMAX = 0x7fffffff。

若記憶體不夠，會分配或擴展。

#define INTMAX BBBB

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

BBBB = 0x7fffffff
mpi_mul_naive 函式的作用是計算兩個 op1 × op2 的乘積，並將結果儲存到 rop 中。

static void mpi_mul_naive(mpi_t rop, const mpi_t op1, const mpi_t op2)
{
    ...
    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 = CCCC; 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;
            }
        }                                     
    }
    ...   

}

其中的這段模仿我們手動筆算乘法的方式：

  1. 對每一位做乘法
  2. 加總
  3. 處理進位

而其中 op1[n] × op2[m] 的結果會放在第 n + m 位開始，就像十進位乘法的位移，因此 CCCC = n + m

mpi_fdiv_qr 的作用是執行整數的整除與餘數運算，也就是計算 q = n / d 和 r = n % d，並將結果分別儲存在 q 和 r 中:

void mpi_fdiv_qr(mpi_t q, mpi_t r, const mpi_t n, const mpi_t d)
{
    ...
    size_t start = mpi_sizeinbase(n0, 2) - 1;

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

例子：當 n 為 1101 時
一開始：

  • 商 q = 0
  • 餘數 r = 0

n 是 1101 ，最高位是第 3 位

每個步驟：

  • 第 1 步：i = 3
  • r <<= 1 ➔ r = 0
  • 把 n 第 3 位(1)加進 r ➔ r = 1
  • 比較 r = 1 跟 d = 3 ➔ 1 < 3，所以不用減。
  • 商 q 第 3 位寫0。

第 2 步：i = 2

  • r <<= 1 ➔ r = 2
  • 把 n 第 2 位(1)加進 r ➔ r = 3
  • 比較 r = 3 跟 d = 3 ➔ 3 == 3，可以減
  • 減完 r = 0
  • 商 q 第 2 位寫 1。

第3步：i=1

  • r <<= 1 ➔ r = 0
  • 把 n 第 1 位(0)加進 r ➔ r還是0
  • 比較 r = 0 跟 d = 3 ➔ 0 < 3，不用減。
  • 商 q 第 1 位寫 0。

第4步：i = 0

  • r <<= 1 ➔ r = 0
  • 把 n 第 0 位(1)加進 r ➔ r = 1
  • 比較 r = 1 跟 d = 3 ➔ 1 < 3，不用減。
  • 商 q 第 0 位寫 0。

最後結果：

  • 商 q = 0100 (十進位就是4)
  • 餘數 r = 1
  • 所以 13 ÷ 3 = 4 餘 1

mpi_mul_2exp(r, r, DDDD)這行的作用是將餘數 r 左移 1 位，因此DDDD = 1。

mpi_gcd 這個函式實作的是輾轉相除法來計算兩個整數 op1 和 op2 的最大公因數。依照輾轉相除法的原理：

若 b ≠ 0，則 GCD(a, b) = GCD(b, a mod b)
所以，在遞迴的情況下，只要 op2 不為 0，就持續以 op1 % op2 的餘數作為新的下一輪的參數，直到餘數等於 0 為止。

EEEE = mpi_gcd(rop, op2, r)

這項實作依賴遞迴呼叫，請避免使用並降低記憶體開銷

下列這段程式為 mpi_gcd 的非遞迴實作版本：

void mpi_gcd(mpi_t rop, const mpi_t op1, const mpi_t op2)
{
    mpi_t a, b, q, r;
    mpi_init(a);
    mpi_init(b);
    mpi_init(q);
    mpi_init(r);

    mpi_set(a, op1);
    mpi_set(b, op2);

    while (mpi_cmp_u32(b, 0) != 0) {
        mpi_fdiv_qr(q, r, a, b);
        mpi_set(a, b);
        mpi_set(b, r);
    }

    mpi_set(rop, a);

    mpi_clear(a);
    mpi_clear(b);
    mpi_clear(q);
    mpi_clear(r);
}

延伸問題:

解釋上述程式碼運作原理
這項實作依賴遞迴呼叫，請避免使用並降低記憶體開銷
改進最大公因數的運算效率

測驗 2

解釋上述程式碼運作原理

static inline uint64_t bit_compound(uint32_t x, uint32_t y)
{
    return ((0L + x) << 32) | ((y + 0L) & (-1L >> 32));
}

在測驗 2 中可以發現，這個函式中的((y + 0L) & (-1L >> 32))是多餘的。
原因是，我傳入的 y 是uint32_t類型（無號整數），
在進行 (y + 0L) 時，C 語言會將 y 進行無號升型（promotion），
轉換成 long 型別，並且高位自動補 0，不會產生符號擴展或高位污染的問題。
為了確認這段我做了測試：

    int32_t si = -1;
    uint32_t ui = 0xFFFFFFFF;

    long sl = si + 0L;
    long ul = ui + 0L;

    printf："Signed int32_t si = %d\n", si);
    printf("After (si + 0L): 0x%016lx\n", (unsigned long)sl);

    printf("\n");

    printf("Unsigned int32_t ui = %u\n", ui);
    printf("After (ui + 0L): 0x%016lx\n", (unsigned long)ul);

而印出來的結果為

Signed int32_t si = -1
After (si + 0L): 0xffffffffffffffff

Unsigned int32_t ui = 4294967295
After (ui + 0L): 0x00000000ffffffff

後面的 & (-1L >> 32) 遮罩操作實際上並沒有任何作用，可以直接省略。

另外，如果真的需要截取後32位元，為了保證正確性與跨平台行為，
應該明確使用 unsigned long 型別進行操作，例如遮罩 0xFFFFFFFFUL，
而不是使用 (-1L >> 32) 這種有號數右移行為的寫法。

為了驗證上述這段我做了以下測試：

    unsigned long ul = (unsigned long)-1L;

    printf("Test shifting -1L (signed long)\n");
    printf("-1L >> 32 = 0x%016lx\n", (-1L >> 32));

    printf("\nTest shifting (unsigned long)-1L\n");
    printf("(unsigned long)-1L >> 32 = 0x%016lx\n", ul >> 32);

    return 0;

此為輸出結果：

Test shifting -1L (signed long)
-1L >> 32 = 0xffffffffffffffff

Test shifting (unsigned long)-1L
(unsigned long)-1L >> 32 = 0x00000000ffffffff

而 memchr_opt 分為三個階段，其中要填入的為第二段
第一段：逐字元搜尋 c 直到記憶體位置對齊
第二段：快速以 long 單位搜尋是否包含目標字元 c
第三段：逐字元搜尋剩餘字元是否包含目標字元 c

首先看到這段：

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

從題目的敘述可以知道 DETECT_NULL(X) 會檢查 X 中是否有 byte 是 0x00。
我們想判斷某個 long 變數是否包含特定字元 c，做法是：
將該 long 變數 X 與一個由目標字元重複填滿的 mask 做 XOR，若 X 中有任何 byte 等於目標字元，則 XOR 結果對應 byte 就會是 0，等同 DETECT_NULL 可檢測到，因此 AAAA = X^mask

由上述可得知，mask 是由目標字元 d 重複填滿，而下列這段是想產生一個 unsigned long mask，裡面所有的 byte 都填滿字元 d。
初始時先用 16 bits 來填滿（d << 8 | d），接著利用位移與 OR 操作將其擴展到 32 bits。
如果 unsigned long 是 64 位元，會執行下面的迴圈，持續將目前的 mask 左移並 OR 到自己，直到整個 64-bit mask 都被填滿：

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

因此可以得知 BBBB = mask<<i 而 CCCC 則是指向資料區塊的 unsigned long 變數，因此 CCCC = *asrc，用來進行目標字元的檢測

延伸問題:

解釋上述程式碼運作原理
比較 Linux 核心原本 (與平台無關) 的實作和 memchr_opt，設計實驗來觀察隨著字串長度和特定 pattern 變化的效能影響
研讀 2022 年學生報告，在 Linux 核心原始程式碼找出 x86_64 或 arm64 對應的最佳化實作，跟上述程式碼比較，並嘗試舉出其中的策略和分析
下一步：貢獻程式碼到 Linux 核心
Phoronix 報導

測驗 3

AAAA = ENV_RUNNABLE
BBBB = attempts+1
CCCC = coro_schedule
DDDD = coro_yield

測驗 1

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

給一個 0到 15 的初始值
↓
做 4 次 CRC 模擬（每次根據最低 bit 決定要不要 XOR）
↓
得到最終 CRC 表格值
↓
填到你的查表陣列

用 0xC 當例子
初始： crc = 0x0000000C //(binary 1100)
0x0000000C 這樣的初始值，其高位元可以假設為 0，原因是後續的運算中，每次都會進行 crc >> 4 的位移操作，把高位資料不斷移除掉，因此原本高位的內容不會影響最終的結果。

第一次位移 (bit 0)

  • crc & 1 == 0（最低位是0）
    只右移 >>
    crc = 0x00000006

第二次位移 (bit 1)

  • crc & 1 == 0
    再右移 >>
  • crc = 0x00000003

第三次位移 (bit 2)

  • crc & 1 == 1
    先右移，再 XOR 0x82F63B78
    crc = 0x82F63B79

第四次位移 (bit 3)
crc & 1 == 1
再次先右移再 XOR 0x82F63B78：
crc = 0xC38D26C4

以此類推
AAAA：0xc38d26c4
BBBB：0xd3d3e1ab
CCCC：0xe330a81a
DDDD：0xf36e6f75

延伸問題:

在 Linux 核心原始程式碼中找到 CRC32 的應用案例至少 3 處，並探討其原始程式碼
設計實驗來分析 Fast CRC32 提出的手法 (要涵蓋 branchless 和查表的變形)，並與硬體的 CRC32 指令效能進行比較。
以 x86-64 或 Arm64 為探討標的，說明 Linux 核心如何使用硬體加速的 CRC32 指令

測驗 2

AAAA：0x7FFF
BBBB：0x80000000
CCCC：0x7FFFFFFF
DDDD：0x80000000
EEEE：0x7FFFFFFF
FFFF：input & 0xFF
GGGG：Q15_MAX
HHHH：Q15_MIN

延伸問題:

解釋上述程式碼運作原理，搭配「信號與系統」教材
探討定點數的使用和其精確度
改進 MIDI 一閃一閃亮晶晶的音效輸出

測驗 3

IIII： max_fd
JJJJ： &rfds

這支 server 程式是一個多人聊天室伺服器，支援同時多個 client 連線進來聊天，每當有一個 client 發訊息給 server，server 會自動把這個訊息轉發給其他所有連線中的 client，而且如果有 client 離開，server 也會自動偵測並清除連線。

執行這支程式，server 在本機的你輸入的 port 上開始監聽，等待 client 連進來。

client 可以用像是 telnet 或 netcat 來連線到 server ，例如:

telnet 127.0.0.1 5000

每成功一個連線，server 端會：

  1. 執行 accept() 接受這個新連線
  2. 打印出來一行訊息，顯示 new_fd 和 client 的 IP/port
  3. 把這個新 client 的 fd 記錄到 conns[] 陣列中（活躍的 client 列表）
  4. 把這個 fd 加到 select() 監控的集合裡（下一輪重建 fd_set 時加進去）
  5. 把這個 socket 設成 non-blocking 模式（避免 read() 卡住）
listening on port 5000
[4] connect from 127.0.0.1:59490

client 發送可以訊息給 server

client 任意打字，例如： Hello everyone!
server 端在下一輪 select() 中偵測到這個 client fd 有資料可以讀。

listening on port 5000
[4] connect from 127.0.0.1:59490
[4] activity
[4] read: Hello everyone!

server 處理收到的訊息
當 server 偵測到某個 client 有資料：
呼叫 read(fd, buf, sizeof(buf)) 讀取資料。
如果 read() 回傳 > 0，代表真的有資料收到。
接著 server 會：

  1. 把剛收到的這段文字存在 buf 中。
  2. 迴圈遍歷所有活著的 client_fd。
  3. 把這份資料（buf）寫給除了自己以外的所有 client (dest_fd != fd)。
  4. 用 write(dest_fd, buf, nread) 把訊息廣播出去。

client 斷線時的處理

如果某個 client：
自己正常關閉連線或是網路問題中斷 server 端在 read(fd, buf, sizeof(buf)) 時會遇到： read() 回傳 0
這時 server：

  1. 印出 [fd] closed
  2. close(fd) 把這個 client 的連線關掉
  3. conns[fd] = 0 從活躍連線列表清掉
[4] activity
[4] closed

延伸問題:

解釋上述程式碼運作原理
學習 jserv/ttt 程式碼，在不使用 (n)curses 一類現成的函式庫前提下，改進網路聊天室的文字呈現介面
在既有的程式碼之上，實作帳號登入 (login) 及基本管理功能，並該有線上與否的提示，留意 ping value 的處理機制

Last changed by 
 
巫冠君
0
56

Read more

Linux Suspend/Resume 實驗（二）

追蹤程式碼

Jun 24, 2025
Linux Suspend/Resume 實驗（一）

Linux Suspend/Resume

Jun 22, 2025
suspend resume 教材整理

這個演講主要探討了優化 suspend/resume 的研究，並強調了它對手錶和手機等設備的重要影響。在一開始，Saravana Kannan 簡單介紹了 suspend/resume 的過程，並將其劃分為以下幾個階段：

Jun 22, 2025
Linux Suspend/Resume 實驗（四）

）

Jun 13, 2025
Read more from 巫冠君
Published on HackMD