2025q1 Homework3 (kxo)

contributed by < BennyWang1007 >

注意書寫規範！

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [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 字元

開發環境

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0

$ lscpu
架構：                    x86_64
  CPU 作業模式：          32-bit, 64-bit
  Address sizes:          39 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   20
  On-line CPU(s) list:    0-19
供應商識別號：            GenuineIntel
  Model name:             12th Gen Intel(R) Core(TM) i7-12700H
    CPU 家族：            6
    型號：                154
    每核心執行緒數：      2
    每通訊端核心數：      14
    Socket(s):            1
    製程：                3
    CPU(s) scaling MHz:   23%
    CPU max MHz:          4700.0000
    CPU min MHz:          400.0000
    BogoMIPS:             5376.00
Virtualization features:  
  虛擬：                  VT-x
Caches (sum of all):      
  L1d:                    544 KiB (14 instances)
  L1i:                    704 KiB (14 instances)
  L2:                     11.5 MiB (8 instances)
  L3:                     24 MiB (1 instance)
NUMA:                     
  NUMA 節點：             1
  NUMA node0 CPU(s)：     0-19

提昇版面傳輸速率

commit a285e0b
commit a969618

我將原先傳輸 DRAWBUFFER_SIZE bytes 的資料改為 BOARD_DATA_SIZE bytes，定義如下。

- #define DRAWBUFFER_SIZE                                                 \
-     ((BOARD_SIZE * (BOARD_SIZE + 1) << 1) + (BOARD_SIZE * BOARD_SIZE) + \
-     ((BOARD_SIZE << 1) + 1) + 1)
- static char draw_buffer[DRAWBUFFER_SIZE];

+ #define BOARD_HISTORY_ELE_BITS 2
+ #define BOARD_HISTORY_SIZE \
+     (BOARD_SIZE * BOARD_SIZE * BOARD_HISTORY_ELE_BITS / 8)
+ static char board_data[BOARD_DATA_SIZE] = {0};

注意書寫規範，中英文間用一個半形空白字元區隔

每一個位置皆只使用兩bit來傳輸，比起原先的 char 加空格，省去了許多不必要的資訊。
當版面夠大時（

$BOARD\mathrm{\_}SIZE\to \mathrm{\infty }$），節省了

$\underset{n\to \mathrm{\infty }}{lim}(1-{\displaystyle \frac{n^2/4}{3n^2+4n+2}})\approx 91.7％$ 的資料大小。

提供更多數學分析

顯示歷史紀錄

commit 797c875

首先我定義了 type board_history_t 作為一盤棋的紀錄。

#define BOARD_HISTORY_SIZE \
    ((BOARD_SIZE * BOARD_SIZE * BOARD_SIZE_SQUARE_LOG2 + 7) / 8)

typedef struct board_history {
     char moves[BOARD_HISTORY_SIZE];
     size_t length;
 } board_history_t;

（記 BOARD_SIZE = n）
其中我定義座標

$A1=0,A2=1,...,B1=n,...$。一盤棋最多會有

$n^2$ 步，因此需要

$\lceil {\displaystyle \frac{n^2\cdot \lceil lo{g}_2(n^2)\rceil }{8}}\rceil$ bytes 的大小來存取資料，並預留一個 byte 存 \0。

接著我讓程式在進行移動時用 history_append_move()將資料存入歷史紀錄，並用 history_next_board() 在該盤棋結束時將地址一向下一個紀錄。

最後我定義了 kxo 的 ioctl interface 讓使用者能夠向 kernel 獲取儲存的歷史盤面，如以下用法。

ioctl(device_fd, KXO_GET_BOARD_HISTORY, &histories);

程式輸出如下。

Stopping the kernel space tic-tac-toe game...
Game history:
Moves: B2 -> D2 -> B1 -> C2 -> D2 -> B1 -> C2 -> B1
Moves: A2 -> D2 -> B2 -> D2 -> A2
Moves: C2 -> D1 -> C2 -> D2 -> D2 -> D2 -> B1
Moves: A2 -> D2 -> B2 -> D2 -> A2
Moves: C2 -> D2 -> D2 -> B1 -> C2 -> B2 -> D2

顯示時間

commit 1777226

在每次繪製盤面後，使用 gettimeofday() 以及 localtime() 來將時間轉換為當地時間，最後用 strftime() 將時間轉為字串並顯示出來，範例如下。

O . . . 
. X . . 
. . . O 
. . . . 
Current time: 2025-04-19 02:58:22

修正執行多次 xo-user 會卡死

commit ef3fa9b

在結束 kxo 時會將 attr_obj.end 設為 1，但在下次呼叫 kxo 時並未重置而造成卡死。因此我將初始化從 kxo_init() 移至 kxo_open() 以保證每次執行都有全新的初始值。