contributed by < HeatCrab
>
首先定義 mpi 的資料型別 mpi_t
,接著定義以下四個記憶體操作函式:
mpi_init
:初始化 mpi_t
,將 data 設為 NULL,容量設為 0。mpi_clear
:釋放 data 的內存。mpi_enlarge
:擴展 data 數組到指定容量,並填充新分配的區域為 0。mpi_compact
:去除高位為 0 的冗餘空間,縮減容量並重新分配記憶體空間。接下來是4個基本操作的函式:
mpi_set_u64
:
首先呼叫 ceil_div
函式,作向上取整除法,原理如下:
在整數除法中, 是向下取整。例如:(實際是 )。
要向上取整,必須補償餘數部分。公式是 ,原因是
接著回傳 n = 64
與 d = 31
。 選擇 d = 31
的理由是 uint32_t
是32位元,為了防止未來在實作乘法時有溢位的情況發生,所以減少一位元,以方便計算。
再來進入第一個 for 迴圈,透過定義好的 INT_MAX
,對 op
實作 mask 的動作,位數同樣是31位。將 mask 好的資料儲存至 data 後,再把 op
右移 31 位元,重複此動作,直到沒有容量(capacity
)。
最後再使用第二個 for 迴圈將 rop
剩下 capacity 中的 data 賦值為 。
mpi_mul_naive
:
這個函式使用的是樸素乘法,也就是我們最一開始學的乘法。
首先定義 capacity 變數為被乘數(op1
)與乘數(op2
)兩個數的 capacity 總和。這樣定義由樸素乘法可以知道,舉例二位數最大 三位數最大的 :
可以得到最大值 ,共五位數。那在我們 mpi_mul_naive
函式實作中的差別在於,我們一個 capacity 中存放的有31位元,但這不影響兩者乘積的位數最多就是兩者 capacity 相加的值。
在初始化 tmp
之後,進入雙重 for 迴圈,首先使用被乘數的第1位,有就是 data[0],依序乘上乘數的每一位,並將結果存到變數 r
中。接著再使用一個 for 迴圈來將 r 切分成每31位元儲存。若是有進位的情況發生,就將進位值存放到 c
變數裡。重複此動作,直到乘法完成。過程就如同我們小學學的,以及上圖的 一樣。
最後使用 mpi_set
將 tmp 的值複製給 rop 完成乘法操作,並使用函式將記憶體釋放。
mpi_fdiv_qr
:
實作上類比長除法。首先將被除數 n
與除數 d
使用函式複製為 n0
與 d0
防止更改到原本的變數。定義商數 q
與餘數 r
。
透過 mpi_sizeinbase
函式找到被除數 n0
的最高位數,因為要如同我們學的長除法一樣,從最左邊,也就是最高位數開始做。接著進入 for 迴圈,透過定義餘數 r
的值,與判斷 r
跟除數 d
的關係來決定商數,過程上使用位元計算來模擬實作長除法時,判斷要重哪一位開始除的過程。
為了更具體的說明,以下舉例 n = 0b1101
與 d = 0b11
為例子:
嘗試過使用 graphviz 說明,但是做的圖片不是很理想,所以最後還是決定使用文字說明。
因為 start = 3
,所以迴圈從 i = 3
開始。
i = 3
:r
為 ,所以在移項(乘二)後,仍舊為零。n
的第三位不為零,所以將 r
的第0位設為1,變成 。i = 2
:r
為 ,在移項(乘二)後,變成 。n
的第二位依舊不為零,所以將 r
的第0位設為1,此時 r
是 。r
扣去除數,並將 q
的第二位設為1。r
為 , q
為 。i = 1
:r
現在又為 ,所以在移項(乘二)後,仍舊為零。n
的第三位為零,所以無動作。i = 0
:r
依舊為 ,所以移項(乘二)後,仍舊為零。n
的第零位不為零,所以將 r
的第0位設為1,此時 r
為 。r
= q
= 用十進位除法驗證一下結果:結果正確。
mpi_gcd
:
透過遞迴呼叫的方式實作輾轉相除法來找最大公因數。
在程式碼的一開始確認 op2
是否為零,若是 op2
為零,則表示輾轉相除法完成,此時的 op1
即為所求,將 op1
賦值給 rop
結束函式。
除法的部分是透過 mpi_fdiv_qr
來計算。
程式上使用了 SWAR 的手法,來實現 memchr
函式要做的事情。memchr
的原理十分簡單,就是透過 while 迴圈來找到目標 c
。那 SWAR 簡單來說,就是透過並行處理的方式,來減少運算上的成本。先使用測驗題說明中提供的程式碼來理解。
原先的 both_odd
函式就是跟將 x
與 y
兩個要比較的變數,先跟1作位元運算 and ,透過判斷最小位數是否為1,來決定是否為奇數。再使用邏輯運算 and 來判斷是否都是奇數。
使用 SWAR 方法則是透過 bit_compound
函式,使用以下的位元運算式,將 x
跟 y
這兩個32位元的變數結合在一起。
以下是 0L 的示意圖,L 表示的是 long 數據型別。圖片中將4個 bits 劃分為一位元。總共有64個0。
先加上變數 x
,接著左移32位元,得到上32位元等於 x
變數,下32位元為0的64位元數。
接著是先以同樣的動作操作 y
變數,得到如下圖:
這邊使用 -1L , 表示的是64位元全1,如圖所示:
透過右移32位元,並且與 y
變數做位元運算 and ,就可以得到一個上32位元為零,下32位元為 y
的64位元數。
最後將新的 x
與 y
變數做位元運算 or ,實現加法的動作,就得到一個上32位元為 x
,下32位元為 y
的64位元數 xy
。
在使用 both_odd_swar
函式前,先定義 SWAR_ODD_MASK
變數。首先使用 1L ,表示的是前63位元為0,最低位,也就是第0位為1。
透過左移32位元,將1的位置移到 xy
中上32位元 x
的第0位,來判斷 x
是否為奇數,接著加上1,來判斷 xy
中下32位元 y
是否為奇數。
在函式中使用位元運算 and ,如果是奇數,那經過運算後的 xy
會跟 SWAR_ODD_MASK
一致,此時回傳1,表示 true ,否則回傳0表示 false。
回到函式 memchr_opt
, 首先先轉換 str
的型別變成 unsigned char (一位元組),並將其記憶體位置定義為變數 src
。同樣將 c
轉換成 unsigned char 資料型別的 d
。
透過 while 迴圈與 UNALIGNED
函式判斷 src
變數是否有對齊 long 這個資料型別。透過位元運算 and 判斷傳入的變數 X
是否是 (sizeof(long) - 1) 的倍數,若是有對齊則位元運算結果會是0,否則回傳1,繼續 while 迴圈,直到 src
對齊。
接下來即是我們實作 SWAR 的部分。先判斷字串長度是否有足夠的必要使用 SWAR 來實作。確認字串長度夠大後,定義一個 unsigned long 的變數 asrc
來加快尋找與判斷的字串位元數。然後將 d
變數依據 LBLOCKSIZE
大小的不同擴充,舉例 d
為 ,根據程式碼步驟:
d
先左移8位,d
= d
作位元運算 or , 得到 mask
= mask
再左移32位,接著與自己做位元運算 or ,得 LBLOCKSIZE
的大小繼續左移,假設依據規格書, long 的資料型別大小是8,mask
擴充至64位,我們得到 mask
為 如果字串長度比 LBLOCKSIZE
大,那麼呼叫 DETECT_CHAR
函式。
DETECT_CHAR
函式會先將傳入的變數 X
與 mask
作 XOR,如果 X
字串包含要尋找的 d
字串的話,那 XOR 的結果就會有0位元組。接著將這個包含0位元組的結果傳入 DETECT_NULL
函式中判斷是否有零位元組。
TBD
memchr_opt
,設計實驗來觀察隨著字串長度和特定 pattern 變化的效能影響