contributed by < tsaiiuo
>
先研讀程式碼,回答答案。
ceil_div
: 可以透過 的概念實作,因此AAAA
:(n + d - 1) / d
INTMAX
: 這就比較直觀 BBBB
:0x7fffffff
mpi_mul_naive
: 實現天真乘法(透過兩數逐位相乘,並累加各項乘積,同時處理進位。),第 n
位和第二個 mpi_t
的第 m
位而言,他們乘起來的數字要加到第 n + m
位,因此 CCCC
:n + m
mpi_fdiv_qr
: 實現長除法,這邊須將餘數左移一位(跟實際的長除法一樣),因此 DDDD
:1
mpi_gcd
:用 mpi_fdiv_qr
做輾轉相除法用於計算計算兩個整數的最大公因數根據公式可以得知答案
例子:
gcd(46189,2310)
= gcd(2310, 46189 mod 2310)
= gcd(2310,2299) (因 46189 ÷ 2310 = 19,餘數 46189 – 19×2310 = 2299)
= gcd(2299,2310 mod 2299)
= gcd(2299,11) (2310 ÷ 2299 = 1,餘數 2310 – 1×2299 = 11)
= gcd(11,2299 mod 11)
= gcd(11,0) (2299 ÷ 11 = 209,餘數 2299 – 209×11 = 0)
= 11
因此EEEE
:mpi_gcd(rop, op2, r)
因為 op1
和 op2
皆為不可變更的,因此需要多定義 a
和 b
代替 op1
和 op2
去進行運算。
先研讀程式碼,回答問題
用 X 與 mask 做 XOR 運算,產生一個新值,這樣在各個 byte 中若有 byte 等於 d(即 mask 中對應的 byte),則 XOR 後該 byte 會變為 0,再交由 DETECT_NULL 檢查是否存在 0 byte,因此 AAAA
: (X) ^ (mask)
這段程式碼目的是建立一個 word(unsigned long)大小的 mask,其中每個 byte 都填滿了目標字元 d 的值。這個 mask 之後會用來在一次讀入多個 byte 時,用意是透過 XOR 與位元運算來檢測該 word 中是否含有目標字元(d)。
而上面程式碼如何製作 mask 我用以下一個範例去 trace code 看看:
這邊假設 d = 'w' , 即 0x77,且 LBLOCKSIZE = 8(64位元的系統)
初始計算:
d = 0x77
d<<8 = 0x7700
mask = 0x7700 | 0x77 = 0x7777
擴展到 32 位元:
mask<<16 = 0x7777 << 16 = 0x77770000
mask |= mask<<16 → 0x7777 | 0x77770000 = 0x77777777
擴展到 64 位元:
進入迴圈,初始 i = 32,
mask<<32(i) = 0x77777777 << 32 = 0x7777777700000000
mask |= mask<<32 → 0x77777777 | 0x7777777700000000 = 0x77777777_77777777
然後 i <<= 1 變成 64,迴圈結束。
因此 BBBB
: mask << i
這段程式碼就是以 word 為單位配合 DETECT_CHAR
檢查是否有符合的目標字元若有則中止,反之則檢查下一個 word(這邊的 ++ 會加上 sizeof(unsigned long) 也就是一個 word 的大小),因此 CCCC
應該為 *asrc
(上面有一段 unsigned long *asrc = (unsigned long *) src;
)
此段用意在理解 getcontext
, makecontext
,setcontext
可以取得目前程式的上下文並且存入參數的指標中
先呼叫 getcontext(&ctx_func),以取得一個現有的上下文(用意在取得合法的 ucontext_t結構體),並分配堆疊空間。設定 uc_link 為 &ctx_main,表示當 func() 執行結束(或呼叫 setcontext() 跳轉)後,會返回主 context。呼叫 getcontext(&ctx_func) 初始化 ctx_func,再用 makecontext(&ctx_func, func, 0) 指定執行函式為 func()。
完整測試函式:
結構體
程式碼本身是要實現可搶先 (preemptible) 的 user-level thread(使用者層執行緒)運作
這段程式碼是要創立一個 user-level thread ,使找到 ENV_UNUSED
狀態的執行緒時,將他的狀態設置為可執行,因此 AAAA
:ENV_RUNNABLE
。
這段程式碼是要實現簡單的 round-robin 排程,應該為搜索下一個,BBBB
:attempts + 1
。
這段程式碼是要實現讓當前執行緒主動放棄 CPU,並進入排程。在呼叫 getcontext() 取得當前 context 後,根據 state_reentered 判斷是否是第一次保存該 context,如果是則呼叫排程,因此 CCCC
: coro_shedule
。
這段程式碼當是要實現 preemption 信號傳來時,讓當前執行緒釋放。符合規範的函式名稱且以 coro_ 開頭,因此 DDDD
: yield
參見Fast CRC32 提到的 "Half-Byte Algorithm",我們可將 8-bit 表格查詢拆分為二次 4-bit 查詢,並且有提供產生器,則實際執行一次產生器即可得到所有答案。
AAAA
:0xc38d26c4
BBBB
:0xd3d3e1ab
CCCC
:0xe330a81a
DDDD
:0xf36e6f75
在 Linux 的 lib 中就有一個 crc32.c 的檔案,其中
函式針對 little-endian 進行計算,結合查表(crc32table_le)快速查得校驗值。
與 crc32_le_base 類似,但此處計算 CRC32C 校驗值,CRC32C 使用不同的多項式(通常為 0x82F63B78),查表中用 crc32ctable_le 來計算。
linux/blob/master/fs/jffs2/fs.c
在更新 inode 屬性時,JFFS2 需要保存或更新該 inode 的原始數據,這些數據包括 inode 的號碼、版本、擁有者、時間戳、檔案大小等資訊。為了防止這些資料在寫入 flash 或從 flash 中讀取時發生損壞,程式使用了 CRC32 校驗碼來計算和保存校驗值。
Flash 存儲設備(如 NAND flash)在寫入或讀取過程中容易發生資料錯誤,使用 CRC32 可以快速檢查讀取到的資料是否正確
linux/tools/pcmcia/crc32hash.c
這段程式碼是計算該字串的 CRC32 校驗值,並以十六進位數形式印出來。使用 CRC32 作為一種雜湊或校驗演算法,將任意字串映射為一個 32 位元的校驗值,根據範例推測用途為快速驗證字串。
將建立的 socket 與指定的本機位址(IP 與埠號)綁定。
啟動監聽( backlog 指定排隊等待連線的最大數)
透過監聽 socket 接受一個連線,建立一個新的 socket 對象用於與該客戶端通訊。
read()/write()
在建立連線之後,用來讀取或寫入資料。
先撰寫一個測試程式碼:
這段程式碼可以達成回聲的效果,伺服器持續可接受多個連線,並能與多個 client 反覆互動,但無法讓 client 間互相通訊。
FD_ZERO
會將一個 fd_set 結構「清空」
FD_SET
會將指定的檔案描述符加入到 fd_set 集合中。這個檔案描述符會在後續的 select() 呼叫中被檢查,看是否有特定的 I/O 事件發生(例如可讀、可寫)。
nfds
: 監控中最高檔案描述符 + 1。
readfds
: 指向要檢查「可讀」狀態的 fd_set。
writefds
: 要檢查「可寫」狀態的集合,若不需要檢查,所以傳入 NULL。
exceptfds
: 用來檢查例外或錯誤狀態,若不需要檢查,傳入 NULL。
timeout
: 指向等待時間的結構指標。
根據 select 的理解可以得到以下的解答:
IIII
: 是目前監控的所有描述符中最大的數值加 1,因此答案為 max_fd
。
JJJJ
: 則為指向要監控的可讀描述符集合的指標,因此答案為 &rfds
.
目前是使用 ANSI 控制碼去控制使用者顏色辨識不同使用者
並且在散播訊息時顯現出使用者的 file descriptor 當作使用者編號
並且有新連線時通知所有使用者
成效: