contributed by <afcidk
>
先觀察 struct node,發現有 data, prev, next 成員,可以猜測資料結構是 linked list。
FunA
的作用看到 if (!*start)
區塊,這個區塊會配置新空間給 *start
,再將 value 放進去,next/prev pointer 指向自己,代表在一個 node 的時候會是雙向的 circular linked list。
再往下看,這個部份屬於 *start != NULL
。從
new_node->next = *start;
(*start)->prev = new_node;
new_node->prev = last;
可以知道新的 node 會插在 *start
前面,但是 *start
並沒有被更改,所以可以看成在 linked list 最後面插入數字。
因此 FunA
的作用是在 linked list 最後面插入 node ,如果 *start 為 NULL
,則配置空間給他。
FunB
的作用和 FunA
很像,但是是插入在 *start
前面,最後再將 *start
指派給新配的 node ,所以可以看成在 linked list 最前面插入 node。
沒有處理 *start==NULL
的情形,改善方法參考 FunA
。
FunC
的作用會先把 value1
放到 new_node 裏面,再從 linked list 裏面找到 value 為 value2
的 node,在後面插入。但是 FunC
並沒有處理到找不到 value2
的狀況,若發生會進入無窮迴圈
改善方法:
struct node *start_addr = *start; // record the first address
while (temp->data != value2) {
temp = temp->next;
if (temp == start_addr){ // break if met previous address
puts("Cannot find value, FunC failed and did not insert number.");
break;
}
}
發現 malloc 呼叫完不用轉型也可以 assign 給變數,編譯參數加上 -Wall
也不會跳出警告,但是如果加上 -Wc++compat
就會警告我們必須要轉型,因為在 C++ 中這是不允許的。為什麼在 C 裡面允許的方式 C++ 要禁止?或是說為什麼 C 可以允許這種寫法?
或許是因為 C 假設寫程式碼的人都知道自己在做什麼,所以限制比較小?這樣可以增進效能或是有什麼優點嗎?
C 和 C++ 是不同的程式語言,去比較兩者對 type 的定義差別
由上面對 Fun[ABC]
的分析,再一步一步跑 main 裡面的程式
觀察 display()
, traverse in forward direction 就是一直往後面找,當指標等於 *start
的時候就停止,也就是依序印出內容。
traverse in reverse direction 的迴圈會往前找,因為是雙向的 linked list,所以不會有指標為 NULL
的情形發生
FunX
的作用FunX
會順著 linked list 走下去。當發現是 circular 或是走到底的時候就會停下來,最後再回傳 node-head,可以用來判斷是不是 circular linked list,如果是會回傳 0 ,否則回傳非 0 數值。
在 for 迴圈裡面的 data++
沒有任何用途,猜測原本的用途應該是要在 FunX
裏面修改 data
的數值,程式碼應該要修改成 (*data)++
,並且在函數一開始讓 *data = 0
K1~K5 和 count 的數字
這段程式碼先建立基本的 linked list
struct node *head = node_new(0); // A(head)
head->next = node_new(1); // A->B
head->next->next = node_new(2); // A->B->C
head->next->next->next = node_new(3); // A->B->C->D
head->next->next->next->next = node_new(4); // A->B->C->D->E
然後檢查是不是 circular linked list,回傳非 0 ,輸出 YES
head->next->next->next->next = head;
現在結構變成 A->B->C->D->A (circular)
,輸出 NO
head->next->next->next->next->next = head->next;
結構變成 A->B->C->D->A (circular)
,輸出 NO
head->next = head->next->next->next->next->next->next->next->next
結構變成 A->A (circular)
,輸出 NO
最後要輸出 head->next->data
,這是 A->data = 0
因為剛才在 FunX
提到的缺陷,讓 count 無法更改數值,所以一直維持 0。
考慮以下程式碼,推敲其作用
uint8_t Func32(uint32_t x) {
return x ? Func32(x >> 1) - 1 : 32;
}
先檢查 x 是不是 0 ,再將 x 向右位移 1 bit繼續遞迴下去。
直接從遞迴的最尾端往上想,最後一次遞迴一定是回傳 32,然後每次往回跑的時候都會遞減 1 ,因此可以判斷這個函式是用來 count leading zero。
將 Func32
改寫為以下功能等價的程式碼:
uint8_t FuncI(uint32_t x)
{
if (!x) return 32;
int n = 1;
if (!(x >> 16)) { n += 16; x <<= 16; }
if (!(x >> M1)) { n += 8; x <<= 8; }
if (!(x >> M2)) { n += 4; x <<= 4; }
if (!(x >> M3)) { n += 2; x <<= 2; }
n = n - (x >> 31);
return n;
}
知道這個函式在算 clz 之後,再看就很容易了。
4 個 for 迴圈使用二分搜尋法來查看前 n bit 是不是 0 (有沒有 1 ),第一次找 16 bit ,第二次 8 bit… 依序這樣下去,可以推得 M1=24(16+8), M2=28(16+8+4), M3=30(16+8+4+2)。
如果沒有找到區間內存在 1 的話,就把範圍縮小(x <<= n
那部份)
最後面的 n = n - (x >> 31);
也可以按照上面四個判斷式的寫法寫成 if (!(x >> 31)) {...}
,只是少了判斷式可以讓程式快一點而已,並且一開始 n 需要初始化為 0 。
Func32
的指令,隨後在 GitHub 專案中找到 3 個應用案例並解說Func32
(或下方 Func64
) 的指令加速的案例先了解各個函式和資料結構的功能或實現的原理
union u_word
: 用來儲存把 64-bit 數字拆成兩個 32-bit 的 struct 和用 64-bit 儲存的 union,兩者記憶體空間共享(大小一樣)。union u_qword {
struct {
uint32_t low;
uint32_t high;
} dwords;
uint64_t qword;
};
struct udiv_result
: 儲存運算完的結果,分成商和餘數。struct udiv_result {
union u_qword q;
union u_qword r;
};
int Func64()
: Func32()
的擴展版本,先把數字拆成兩個 32-bit 資料,再利用原本的 Func32()
找出 leading zero。static inline int Func64(uint64_t val)
{
uint32_t lo = (uint32_t) val;
uint32_t hi = (uint32_t) (val >> 32);
return hi ? Func32(hi) : 32 + Func32(lo);
}
int do_udiv32()
: 計算 32-bit 無號除法首先,mask 會計算 divisor 和 dividend 的 leading zero 相差多少,計算 mask 的用意是知道商會有幾位數,後面我們可以利用到 mask 來判斷是否不能再繼續算下去。(mask 每次都要右移 1 bit,並決定是否要紀錄到商數,有紀錄就是 1 ,沒有就是 0)
二進位除法可以免除掉計算倍數的問題(一定是 0 或是 1 倍),只要用減的就可以完成除法。
在註解裡面的 align xxx 意思是把被除數 align 成我們計算的形式。回想長除法,除數是從 MSB 除到 LSB,所以要先把 divisor 往左"推",讓 divisor 和 dividend 的 MSB 是對齊的。
如果當前 dividend 大於 divisor,代表可以除一次,就利用 bitwise or 把 mask 的當前位數 set 上去,不能除的話商就是 0 ,只要把 mask 右移一次就好。
每次做完 divisor 都要左移一次,可以看成是往下一位繼續作除法。
dividend: 0101010, divisor: 0101
| 代表對齊的地方
[] 代表右移後補上的 0
第一次
0|101010 / 0101[000]
第一次
01|01010 / 00101[00]
第一次
010|1010 / 000101[0]
第一次
0101|010 / 0000101
static int do_udiv32(uint32_t dividend,
uint32_t divisor,
struct udiv_result *res)
{
/* Ensure dividend is always greater than or equal to the divisor. */
uint32_t mask = Func32(divisor) - Func32(dividend);
divisor <<= mask; /* align divisor */
mask = 1U << mask; /* align dividend */
do {
if (dividend >= divisor) {
dividend -= divisor;
res->q.dwords.low |= mask;
}
divisor >>= 1;
} while ((P1) && dividend);
res->r.dwords.low = dividend;
return 0;
}
int udiv64()
: 計算 64-bit 無號除法,裏面有使用到 do_udiv32()
。注意到 divisor == 0
那邊有一個數字 0xfff.....full
,那不是什麼很潮的寫法,只是在說有一個數字 0xffffffffffffffff
,型態是 unsigned long long 而已。
基本上 64-bit 的版本和 32-bit 版本差不多,但是 64-bit 多了很多判斷的條件,包括:除以 0 ,除數被除數相等,除數大於被除數,只需要使用 32-bit 版本就可以實作…等,為什麼 32-bit 沒有考慮到這些問題呢?
如果我們會在 udiv64()
以外(像是 main()
)呼叫到 do_udiv32()
,就必須也加入 除以 0 等特殊情況的判斷式,但是現在我們很確定不會發生這種事情,因為這些特殊情況在呼叫前都被前面的判斷式過濾掉了。
和 32-bit 不同的地方在於 64-bit 多了一個變數 bits ,將原本 mask 的工作用兩個變數來完成。
bits 負責計算還有多少位數還沒除,每次會減 1 。
mask 負責當作 set bit 時用的 mask,每次都會左移一位元。
這樣就可以知道 bits 等於 0 的時候要離開迴圈。
感覺這樣做才是正確的,為什麼 32-bit 的版本可以讓 mask>>=1 來替代 bits 的工作呢?
32-bit 版本的實作並不完整,其作用只是 helper function,用來實作 64-bit 版本,實際上也只有後者真的被使用
jserv
int udiv64(uint64_t dividend, uint64_t divisor, struct udiv_result *res)
{
uint64_t mask;
uint64_t bits;
res->q.qword = res->r.qword = 0;
if (divisor == 0) { /* division by 0 ? */
res->q.qword = 0xffffffffffffffffull;
return -1;
}
if (divisor == dividend) {
res->q.qword = 1;
return 0;
}
if (divisor > dividend) {
res->r.qword = dividend;
return 0;
}
/* only 32 bit operands that the preconditions are fulfilled. */
if (!(divisor >> 32) && !(dividend >> 32))
return do_udiv32((uint32_t) dividend, (uint32_t) divisor, res);
bits = Func64(divisor) - Func64(dividend);
divisor <<= bits; /* align divisor and dividend */
mask = 1ULL << bits;
/* division loop */
do {
if (dividend >= divisor) {
dividend -= divisor;
res->q.qword |= mask;
}
divisor >>= 1;
mask >>= 1;
} while ((P2) && dividend);
res->r.qword = dividend;
return 0;
}
P3 和 P5 是用來改最後輸出的結果的,因為在函式裏面我們都是用數字來表示,想要印出字元的話就要將原本的數字加上 48 (ascii: '0')。
P4 那部份是用十進位來處理數字,所以答案是 10。
可是 ASCII 0 好像是 48?
e94046165已更正,把解法寫出來就直接寫答案上去了Orz,下次不再犯QQafcidk
0xCAFEBABE
為 magic number,舉出在真實世界中程式的實際作用 (提示: 如 malloc)先理解為什麼下面程式碼輸出會是 jserv++C
#include <stdio.h>
int main() {
puts((char *) &(double []){ 3823806048287157.0, 96 });
}
把 m
轉成二進位形式表現,得到 01000011 00101011 00101011 01110110 01110010 01100101 01110011 01101010
,再將每個位元組轉成字元表示,得到 C++vresj
。
但是因為我們機器的儲存方式是 little-endian,因此顯示的會是相反過來的 jserv++C
。
再看到真正的程式碼,可以看到原本的數字 m[0] 會乘上 0[1001001 0010]1011 00101011 01110110 01110010 01100101 01110011 01101010
,再轉換成字元表示,得到 jserv++I
修改程式碼輸出 Github 帳號名稱
先把想要修改的字元寫出來,轉成二進位,用 0 把 bits 補齊,但是不能夠直接用 00000000
補,因為 0 是 termination character。
#include <stdio.h>
double m[] = {2.09703464477855301570627215629e209};
int main() { puts((char*)m); return 0; }
// output: afcidk
我先將二進位表示分成三個部份: sign bit, exponent, mantissa
(之所以不直接減他們的差是為了減少誤差導致的錯誤。)
原本 v.s. 修改後
0[1101011 0110][0100 01101001 01100011 01100110 01100001 00000001 00000001]
0[1100111 0110][1110 01110101 01001000 00000001 00000001 00000001 00000001]
1.03214314438870169274345588995E209
需要注意到的是如果先更改 exponent,mantissa 也要跟著乘上更改的數字。避免處理麻煩,我先加上 mantissa 才更動 exponent。
#include <stdio.h>
double m[] = { 2.09703464477855301570627215629E209, 64};
void gen() {
// original output: afcidk
m[0] += 1.03214314438870169274345588995E209;
while (m[1]--) {
m[0] /= 2;
}
puts((char *) m); // output:Hung
}
int main() { gen(); return 0; }
在 little-endian 中,每 8 byte 為單位,最高位元會放在 LSB。而在 big-endian 中,最高位元會放在 MSB。
要改寫到 big-endian 環境使用,需要注意以 8 byte 為單位反向放資料。
舉例來說:0x01234567 0x9abcdefa
在 little-endian 要放 67 45 23 01 fa de bc 9a
而在 big-endian 要放 01 23 45 67 9a bc de fa