c-review

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 的定義差別

    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →
    jserv

  • Z1 ~ Z10

    由上面對 Fun[ABC] 的分析,再一步一步跑 main 裡面的程式

    • 插入 51, 現在是 51(s)
    • 插入 48, 現在是 48(s), 51
    • 插入 72, 現在是 48(s), 51, 72
    • 插入 86, 現在是 48(s), 51, 72, 86
    • 在 51 之後插入 63,現在是 48(s), 51, 63, 72, 86

    觀察 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。

第五週測驗題(上1)

考慮以下程式碼,推敲其作用

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 。

在 x86_64/Aarch32/Aarch64 ISA 中找出對應於 Func32 的指令,隨後在 GitHub 專案中找到 3 個應用案例並解說

回顧 Week1 到 Week5 的教材和作業,提出可用對應於 Func32 (或下方 Func64) 的指令加速的案例

第五週測驗題(上2)

先了解各個函式和資料結構的功能或實現的原理

  • 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

將 10 進位輸出改為 16 進位

上方程式碼的 0xCAFEBABEmagic 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] 會乘上

296,我們將 exponent 的部份加上 96 ,得到 0[1001001 0010]1011 00101011 01110110 01110010 01100101 01110011 01101010,再轉換成字元表示,得到 jserv++I

修改程式,允許輸出 Github 帳號名稱

修改程式碼輸出 Github 帳號名稱
先把想要修改的字元寫出來,轉成二進位,用 0 把 bits 補齊,但是不能夠直接用 00000000 補,因為 0 是 termination character。

#include <stdio.h>
double m[] = {2.09703464477855301570627215629e209};
int main() { puts((char*)m); return 0; }

// output: afcidk

修改 gen() 函式,將 m[] 的內容變為英文姓氏

我先將二進位表示分成三個部份: 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]

  • sign bit

    沒有更動
  • exponent

    11010110110 -> 11001110110 ,差了 64 倍。
  • mantissa

    數字可以額外寫一個程式,利用 bitwise operator 來 clear/set bit ,再直接印出兩者的差
    算出數字 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; }

在 big-endian 的環境中,要如何改寫

在 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

第五週測驗題(下)