2025q1 第 5 週測驗題

目的: 檢驗學員對 bitops、浮點數運算，及數值系統的認知

作答表單: 測驗 1, 2
作答表單: 測驗 3

測驗 `1`

考慮以下定點數運算:

#include <stdint.h>
typedef int32_t fix16_t;
#define FIX16_ONE 0x00010000  /* 1.0 in fixed-point representation */

輔助函式：

static inline float fix16_to_float(fix16_t a)
{
    return (float) a / FIX16_ONE;
}

static inline fix16_t float_to_fix16(float a)
{
    /* Round to nearest fixed-point value */
    return (fix16_t)(a * FIX16_ONE + (a >= 0 ? 0.5f : -0.5f));
}

static inline fix16_t int_to_fix16(int a)
{
    return a * FIX16_ONE;
}

藉此打造 tanh 函數，用法如下：

printf("%f\n", fix16_to_float(fix16_tanh(float_to_fix16(0.5))));

參考執行結果是 0.462097

以下是實作程式碼： (部分遮蔽)

static inline fix16_t fix16_mul(fix16_t x, fix16_t y)
{
    int64_t res = (int64_t) x * y;
    return (fix16_t) (res >> 16);
}

static inline fix16_t fix16_div(fix16_t a, fix16_t b)
{
    if (b == 0) /* Avoid division by zero */
        return 0;
    fix16_t result = (((int64_t) a) << 16) / ((int64_t) b);
    return result;
}

fix16_t fix16_exp(fix16_t in)
{
    if (in == 0)
        return FIX16_ONE;
    if (in == FIX16_ONE)
        return AAAA /* precomputed exp(1) in fixed-point */;
    if (in >= 681391)
        return BBBB;
    if (in <= -772243)
        return 0;

    int neg = (in < 0);
    if (neg)
        in = -in;
    fix16_t result = in + FIX16_ONE;
    fix16_t term = in;
    for (uint_fast8_t i = 2; i < 30; i++) {
        term = fix16_mul(term, fix16_div(in, int_to_fix16(i)));
        result += term;
        /* Break early if the term is sufficiently small */
        if ((term < 500) && ((i > 15) || (term < 20)))
            break;
    }
    if (neg)
        result = CCCC;
    return result;
}

/* tanh(x) is defined as (exp(x) - exp(-x)) / (exp(x) + exp(-x)). */
fix16_t fix16_tanh(fix16_t in)
{
    fix16_t e_x = fix16_exp(in);
    fix16_t m_e_x = fix16_exp(-in);
    return fix16_div(e_x - m_e_x, e_x + m_e_x);
}

補完程式碼，使其運作符合預期。書寫規範：

AAAA 為十進位數值
BBBB 為十六進位數值，以 0x 開頭，英文字母大寫
CCCC 為 C 語言表示式，包含 FIX16_ONE 及 fix16_ 開頭的函式呼叫，不含空白字元
以最精簡的形式書寫

測驗 `2`

承測驗 1，以下程式碼實作倍精度的 tanh(x)，不使用任何 FPU 指令，程式碼可見 tanh.c (部分遮蔽)

書寫規範:

DDDD (Line 185): 為十六進位數值，以 0x 開頭，英文字母小寫
EEEE (Line 202): 為十六進位數值，以 0x 開頭，英文字母小寫

參考資料:

測驗 `3`

我們嘗試改寫 Linux 核心的紅黑樹，藉此開發 C++ std::map 的替代品，測試程式碼如下：

/* Custom entry structure embedding a map node. */
typedef struct {
    map_node_t node;     /* Must be the first member if using container_of on node. */
    char *key;     /* Key used for ordering. */
    int value;           /* Associated value. */
} my_entry_t;

/* Extracts the key from the given node. */
static void *my_get_key(map_node_t *node)
{
    return (void *)(((my_entry_t *)node)->key);
}

int main(void)
{
    /* Initialize the map with our key extraction function and default comparator. */
    map_t map;
    map_init(&map, my_get_key, NULL);
    
    /* Allocate and initialize several entries. */
    my_entry_t *entry1 = malloc(sizeof(my_entry_t));
    entry1->key = "apple";
    entry1->value = 10;
    
    my_entry_t *entry2 = malloc(sizeof(my_entry_t));
    entry2->key = "banana";
    entry2->value = 20;
    
    my_entry_t *entry3 = malloc(sizeof(my_entry_t));
    entry3->key = "cherry";
    entry3->value = 30;
    
    /* Insert the entries into the map. */
    if (map_push(&map, entry1->key, &entry1->node) != 0)
        printf("Duplicate key: %s\n", entry1->key);
    if (map_push(&map, entry2->key, &entry2->node) != 0)
        printf("Duplicate key: %s\n", entry2->key);
    if (map_push(&map, entry3->key, &entry3->node) != 0)
        printf("Duplicate key: %s\n", entry3->key);
    
    /* Search for an entry by key ("banana") and then erase it. */
    map_node_t *node = map_find(&map, "banana");
    if (node) {
        my_entry_t *found_entry = container_of(node, my_entry_t, node);
        printf("Found entry: Key = %s, Value = %d\n", found_entry->key, found_entry->value);
        /* Erase the found entry from the map. */
        map_erase(&map, node);
        /* After erasing, free the memory for the entry. */
        free(found_entry);
    } else {
        printf("Key 'banana' not found.\n");
    }
    
    /* Traverse and print all remaining entries in the map in sorted order. */
    printf("All entries in the map after erasing 'banana':\n");
    map_foreach(node, &map) {
        my_entry_t *entry = container_of(node, my_entry_t, node);
        printf("Key: %s, Value: %d\n", entry->key, entry->value);
    }
    
    free(entry1);
    free(entry3);
    
    return 0;
}

預期執行輸出:

Found entry: Key = banana, Value = 20
All entries in the map after erasing 'banana':
Key: apple, Value: 10
Key: cherry, Value: 30

C++ std::map 用紅黑樹實作，std::unordered_map 用雜湊表實作。

程式碼可見 map.c (部分遮蔽)，補完程式碼以符合預期。作答規範：

AAAA 到 DDDD 為變數名稱
EEEE 為表示式
FFFF 到 IIII 包含 rotate，注意要用一致的程式碼縮排風格，注意空白
JJJJ 包含 RB_

2025q1 第 5 週測驗題

測驗 1

測驗 2

測驗 3

Read more

UNIX 作業系統 fork/exec 系統呼叫的前世今生

你所不知道的 C 語言: Stream I/O, EOF 和例外處理

KVM: Linux 虛擬化基礎建設

2025 年 Linux 核心設計課程作業 —— lab0 (C)

測驗 `1`

測驗 `2`

測驗 `3`