---
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_`
Sign in with Wallet
Connect another wallet