# 2025q1 Homework3 (kxo)
contributed by < [BennyWang1007](https://github.com/BennyWang1007) >

:::danger
注意書寫規範！
:::

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

## 開發環境

$ 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](https://github.com/BennyWang1007/kxo/commit/a285e0b6c4357f61fb89feb32edd014db73a525c)
> commit [a969618](https://github.com/BennyWang1007/kxo/commit/a969618ac5660c8be92a2078c4fce7d889357629)

我將原先傳輸 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};

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

每一個位置皆只使用兩bit來傳輸，比起原先的 `char` 加空格，省去了許多不必要的資訊。
當版面夠大時（$BOARD\_SIZE\to\infty$），節省了 $\lim\limits_{n\to\infty} (1-\dfrac{n^2/4}{3n^2+4n+2}) \approx 91.7％$ 的資料大小。

:::danger
提供更多數學分析
:::

## 顯示歷史紀錄
> commit [797c875](https://github.com/BennyWang1007/kxo/commit/797c875c3b115d76051bafb72cce31a03ef77d4b)

首先我定義了 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 \dfrac {n^2 \cdot \lceil log_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](https://github.com/BennyWang1007/kxo/commit/1777226249e8e8614b07b385a7de88b15322d022)

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

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

## 修正執行多次 xo-user 會卡死
> commit [ef3fa9b](https://github.com/BennyWang1007/kxo/commit/ef3fa9ba63684e7f2d3b60dd656ec8e090326b20)

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