contributed by < yyyyuwen
>
在 Linux 核心原始程式碼,include/linux/bitfield.h 提及一個巨集 GENMASK
,其作用是依據給定的範圍,產生連續的 bitmask,例如:
GENMASK(6, 4)
產生 011100002GENMASK(39, 21)
產生 0x000000ffffe00000 (64 位元)已知我們使用的微處理器架構為 64 位元,且 unsigned long
為 8 位元組寬度 (符合 LP64 資料模型),以下是可能的 GENMASK
巨集的定義:
請補完,使其行為符合預期。作答規範:
LEFT
和 RIGHT
應以最簡潔的形式撰寫,且符合作業一排版規範 (近似 Linux 核心程式碼排版風格)LEFT
和 RIGHT
皆為表示式,可能包含常數LEFT
和 RIGHT
皆不該包含小括號 (即 (
和 )
)maskng bit to 1 -> OR
OR
can be set with 1.OR
can be set with 0.Example:
Masking on the higher nibble (bits 4, 5, 6, 7) while leaving the lower nibble (bits 0, 1, 2, 3) unchanged.
Masking bits to 0 -> AND
More often in practice, bits are "masked off" (or masked to 0) than "masked on" (or masked to 1)
AND
can be set with 0.AND
can be set with 1.Example
Masking off the higher nibble (bits 4, 5, 6, 7) while leaving the lower nibble (bits 0, 1, 2, 3) unchanged.
Querying the status of a bit -> AND
To use bitmask to check the state of individual bits regardless of the other bits.
-> 將要檢查的設定成1,其餘的設0。
Example
Querying the status of the 4th bit
Toggling bit values -> XOR
更多的應用是關於 XOR
XOR 又可以解釋成 "A or B, but not, A and B"
首先透過 GENMASK(6, 4)
所產生的 011100002 來討論。
(((~0UL) >> (LEFT))
:是將 ~0(all 1)
的 unsigned long 往右移,所以推測位移後高位都會是0,低位都會是1。((~0UL) >> (l) << (RIGHT))
:會先把 ~0
往右位移 l
個bits,再往左移 RIGHT
個bits,推測位移後應該是 高位與低位都是0而中間是1的型態利用 GENMASK(6, 4)
來代入得知
LEFT
= 63 - hRIGHT
= l提問:是否可將 ((~0UL) >> (4) << (RIGHT))
更改為 ((~0UL) << (l))
?
列出你的推測和實驗
jserv
延伸問題:
考慮以下程式碼:
函式 to_fd
接受指定的地址 v
,填入一個 fd
結構體,並確保第一個成員的地址得以依據〈你所不知道的 C 語言:記憶體管理、對齊及硬體特性〉描述,對 4 個位元組進行向下對齊 (即 C++ Boost 描述的 align_down)。其中 struct foo;
運用〈你所不知道的 C 語言:指標篇〉提及的 forward declaration 技巧,可在實作階段才提供具體 struct foo
的定義。
請補完,使其行為符合預期。作答規範:
EXP1
應以最簡潔的 C99 形式撰寫,符合作業一排版規範,且不該觸發編譯器警告訊息EXP1
不得使用 %
(modulo) 運算子v | 1
作答區
EXP1
= ?先去了解 data alignment ,可以知道其作用就是讓記憶體內的資料落在 4 個 bytes 或是 8 個 btyes 的倍數位置(看電腦規格,主要為)。
而 data alignment 又可分為 align down 以及 align up。
__ALIGN_KERNEL
: 指的是使 x
以 a
為邊界來對齊假設今天的 data 在 ,要將它對 align 於每4個bytes當中,即 , , , 。
此時的 Align value = 4 (byte)
若今天採取的方法為 Align up ,則 將會對齊於 的位置。
這時候 mask
為 (typeof(x))(a) - 1
意思就是 ,以 4 byte 為例, mask
此時是
((x) + (mask))
是為了讓數字不小於 x
並且不大於下一個倍數。((x) + (mask)) & ~(mask)
是為了將低位的 bit 清成零。以此題來說
而若是 alignment 不為 時,需改寫成乘除運算的形式
即
Align down 指的是向下對齊記憶體位址
與 Align up 不同的是在 __ALIGN_KERNEL
中所傳的值為 ((x) - ((a) - 1), (a))
其作用是要讓值往上移到上4 byte 後再進行 mask 的操作。
題目程式為
由於 ALIGN_DOWN(v, mask) = (v) & ~mask
(mask = size - 1
), 而題目要求是要做 4 byte 的 align ,因此 mask
= 3。
最後根據 forward declaration
的定義,我們要將回傳格式轉成 (struct foo *)
EXP = (struct foo *) (v & ~3)
延伸問題:
考慮以下程式碼,能將輸入的 8 位元無號整數逐一位元反轉,如同 LeetCode 190. Reverse Bits 的描述。
請補完,使其行為符合預期。作答規範:
EXP2 和 EXP3 應以最簡潔的 C99 形式撰寫,符合作業一排版規範,且不該觸發編譯器警告訊息
當變數和常數進行運算時,變數應該出現前於常數,例如 v | 1
作答區
EXP2 = ?
EXP3 = ?
此行代表的是 4 位元的前後反轉。 x
先分別往右以及往左 4 位元,最後再做 OR
的動作,而因為是uint,所以都是補 0
。
e.g.
再來是做兩兩位移, 代表是 。
((x & 0xCC) >> 2)
是將每 4 bits 高位元的 2 bits 做兩兩置換,這邊是先留下前面兩個 bits 將後面的捨去掉。EXP2
推測應該是要置換每 4 bits 中低位元的部分,即 ,最後再做 OR
合併。e.g.
最後是做每一個 bit 的置換, 代表的是
((x & 0xAA) >> 1)
對於每兩個 bits 中,將前一個留下而後一個拿掉,同時將式子往右移一個 bit ,是為了後許將值變成是低位的 bit。EXP3
因此對於這邊則是相反,留下後面的並拿掉前面的一個 bit ,並往左移一個 bit ,轉換每兩個 bit 的高低位元,推測應該是要用 也就是 。EXP2
= ((x & 0x33) << 2)EXP3
= ((x & 0x55) << 1)延伸問題:
延伸〈你所不知道的 C 語言:前置處理器應用篇〉,我們嘗試將 foreach 巨集 予以擴充,使得支援以下寫法:
預期輸出如下:
對應的巨集定義:
請補完,使其行為符合預期。作答規範:
EXP4
和 EXP5
應以最簡潔的 C99 形式撰寫,符合作業一排版規範,且不該觸發編譯器警告訊息(
和 )
)作答區
EXP4
= ?EXP5
= ?