---
# System prepended metadata

title: 2025 年春季「Linux 核心設計」第 5 週測驗題
tags: [linux2025]

---

---
tags: linux2025
---

# [2025q1](https://wiki.csie.ncku.edu.tw/linux/schedule) 第 5 週測驗題

:::info
目的: 檢驗學員對 [bitops](https://hackmd.io/@sysprog/c-bitwise)、浮點數運算，及數值系統的認知
:::

==[作答表單: 測驗 `1`, `2`](https://docs.google.com/forms/d/e/1FAIpQLSdMmRXNbBBaG0XpAGU2mLvkWG-QkDAlZy8Sb5ld87e2z261-Q/viewform?usp=dialog)==
==[作答表單: 測驗 `3`](https://docs.google.com/forms/d/e/1FAIpQLScKjIN7E_oopXjVy3HTSFGr57xh78dYYOmUK5RCgKul2dFVWQ/viewform?usp=dialog)==

### 測驗 `1`

考慮以下定點數運算:
```c
#include <stdint.h>
typedef int32_t fix16_t;
#define FIX16_ONE 0x00010000  /* 1.0 in fixed-point representation */
```

輔助函式：
```c
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 函數，用法如下：
```c
printf("%f\n", fix16_to_float(fix16_tanh(float_to_fix16(0.5))));
```

參考執行結果是 `0.462097`

以下是實作程式碼： (部分遮蔽)
```c
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](https://gist.github.com/jserv/7b311a894e6e367a9c361e21dd0670b5) (部分遮蔽)

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

參考資料:
* [類神經網路的 ReLU 及其常數時間實作](https://hackmd.io/@sysprog/constant-time-relu)
* [為何三種圓錐曲線剛好和修辭法有著一樣的英語書寫方式呢？](https://www.facebook.com/JservFans/posts/2312537835539204/)

---

### 測驗 `3`

我們嘗試改寫 [Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree)，藉此開發 [C++ std::map](https://en.cppreference.com/w/cpp/container/map) 的替代品，測試程式碼如下：
```c
/* 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](https://en.cppreference.com/w/cpp/container/map) 用紅黑樹實作，[std::unordered_map](https://en.cppreference.com/w/cpp/container/unordered_map) 用雜湊表實作。

程式碼可見 [map.c](https://gist.github.com/jserv/660b54406c9f7c6cc01ae923636d3389) (部分遮蔽)，補完程式碼以符合預期。作答規範：
* AAAA 到 DDDD 為變數名稱
* EEEE 為表示式
* FFFF 到 IIII 包含 `rotate`，注意要用一致的程式碼縮排風格，注意空白
* JJJJ 包含 `RB_`