2018q1 Homework3 (c-review)

contributed by <raygoah>

第 4 週測驗

題目

題目之 HackMD 連結

測驗一

FuncA 的作用：
- 首先觀察 FuncA，如下所示：
```
void FuncA(struct node **start, int value) {
    if (!*start) {
        struct node *new_node = malloc(sizeof(struct node));
        new_node->data = value;
        new_node->next = new_node->prev = new_node;
        *start = new_node;
        return;
    }
    struct node *last = (*start)->prev;
    struct node *new_node = malloc(sizeof(struct node));
    new_node->data = value;
    new_node->next = *start;
    (*start)->prev = new_node;
    new_node->prev = last;
    last->next = new_node;
}
```
- 可以看到一開始的 if 中，若此 linked list 還沒有創立，這時建立一個 node 作為 linked list 的開頭，被指標 start 所指向，而這邊特別注意到，new_node->next = new_node->prev = new_node; 這一行，在這裡指向下一個 node 的指標 next 以及指向前一個 node 的指標 prev，都是指向自己的
- 從題目中可以知道，此 linked list 為環狀，同時為雙向，接著從第 12 到第 14 行中可以看出，新增 node 時，新 node 的 prev 會指向原本 linked list 中的最後一個 node，同時新 node 的 next 會指向 start node，因此可以知道 FuncA 中新增 node 時，是將 node 插入在 linked list 的最尾端
- 因此由上可得，FuncA 中所做的事為 (e) 建立新節點，內容是 value，並安插在結尾

FuncB 的作用：

觀察 FuncB 如下：









void FuncB(struct node **start, int value) {
    struct node *last = (*start)->prev;
    struct node *new_node = malloc(sizeof(struct node));
    new_node->data = value;
    new_node->next = *start;
    new_node->prev = last;
    last->next = (*start)->prev = new_node;
    *start = new_node;
}

從第 8 行可以直接看出，FuncB 將新插入的 node 設為 linked list 的 start node，因此和 FuncA 不同，FuncB 是從前方插入新 node，因此此題要選： (d) 建立新節點，內容是 value，並安插在開頭

FuncC 的作用：

觀察 FuncC 的程式碼：












void FuncC(struct node **start, int value1, int value2) {
    struct node *new_node = malloc(sizeof(struct node));
    new_node->data = value1;
    struct node *temp = *start;
    while (temp->data != value2)
        temp = temp->next;
    struct node *next = temp->next;
    temp->next = new_node;
    new_node->prev = temp;
    new_node->next = next;
    next->prev = new_node;
}

在 FunC 中可以看到，其中有一個 while 迴圈，在迴圈中尋找值和 value2 相同的 node，接著在第 7 到第 11 行中可以看到，程式將新建立值為 value 1 的 node，插入在剛剛找到的值為 value2 的 node 後面
由上面可以知道，在 FuncC 中所做的，是將值為 value1 的 node，插入在值為 value2 的 node 後面，因此答案要選：(e) 找到節點內容為 value2 的節點，並在之後插入新節點，內容為 value1

在程式輸出中，訊息 Traversal in forward direction 後依序印出哪幾個數字呢？






















void display(struct node *start) {
    struct node *temp = start;
    printf("Traversal in forward direction \n");
    for (; temp->next != start; temp = temp->next)
        printf("%d ", temp->data);
    printf("%d ", temp->data);
    printf("\nTraversal in reverse direction \n");
    struct node *last = start->prev;
    for (temp = last; temp->prev != last; temp = temp->prev)
    printf("%d ", temp->data);
    printf("%d ", temp->data);
    printf("\n");
}

int main() {
    struct node *start = NULL;
    FuncA(&start, 51); FuncB(&start, 48);
    FuncA(&start, 72); FuncA(&start, 86);
    FuncC(&start, 63, 51);
    display(start);
    return 0;
}

從前面可以知道，各個 Function 的功用：
- FuncA: 建立新節點，內容是 value，並安插在結尾
- FuncB: 建立新節點，內容是 value，並安插在開頭
- FuncC: 找到節點內容為 value2 的節點，並在之後插入新節點，內容為 value1
- 因此可得到一個 linked list 為：48 -> 51 -> 63 -> 72 -> 86

在程式輸出中，訊息 Traversal in reverse direction 後依序印出哪幾個數字呢？
- 由第 4 點中得到的 linked list reverse 即可得到答案

測驗二

FuncX 的作用：
- 觀察程式碼
```
int FuncX(struct node *head, int *data) {
    struct node *node;
    for (node = head->next; node && node != head; node = node->next)
        data++;
    return node - head;
}
```
- 在 for 迴圈中可以看到，node 會從 head 的下一個開始，依序造訪整個 linked list ，直到當前的 node 為 null 或是指回 head 時停止，而最後回傳的值為 node - head，若目前 node 正好為 head 的時候，便回傳 0，不是則回傳非 0 的數字
- 因此此題要選 (e) 判斷是否為 circular linked list，若為 circular 則回傳 0，其他非零值

K1 K2 K3 K4 K5 >> 後面接的輸出為何
























struct node *node_new(int data) {
    struct node *temp = malloc(sizeof(struct node));
    temp->data = data; temp->next = NULL;
    return temp;
}

int main() {
    int count = 0;
    struct node *head = node_new(0);
    head->next = node_new(1);
    head->next->next = node_new(2);
    head->next->next->next = node_new(3);
    head->next->next->next->next = node_new(4);
    printf("K1 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
    head->next->next->next->next = head;
    printf("K2 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
    head->next->next->next->next->next = head->next;
    printf("K3 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
    head->next = head->next->next->next->next->next->next->next->next;
    printf("K4 >> %s\n", FuncX(head, &count) ? "Yes" : "No");
    printf("K5 >> %d\n", head->next->data);
    printf("count >> %d\n", count);
    return 0;
}

依照順序建立 linked list，[ ] 內為 node 的值
- 第 10 行： head[0] -> [1]
- 第 11 行： head[0] -> [1] -> [2]
- 第 12 行： head[0] -> [1] -> [2] -> [3]
- 第 13 行： head[0] -> [1] -> [2] -> [3] -> [4]
因此第 14 行中，linked list 不為 circular 因此回傳非 0 值，故 k1 為 Yes
第 15 行中，head->next->next->next->next = head;，會將 [3] 的 next 接回 head，形成 circular，因此 k2 為 No，
- linked list 為 head[0] -> [1] -> [2] -> [3] -> head[0]
第 17 行中，head->next->next->next->next->next = head->next; ，所形成的 linked list 和第 15 行中的 linked list 相同，並未改變，因此 k3 和 k2 一樣為 No
- linked list 為 head[0] -> [1] -> [2] -> [3] -> head[0]
第 19 行中，head->next = head->next->next->next->next->next->next->next->next; ，等號右邊為 [0]，會形成 head[0] -> head[0]，因此為 circular ，k4 為 No
第 21 行中，因為 linked list 為 head[0] -> head[0] 因此 k5 的值為 0

count >> 後面接的輸出為何
- 這邊要注意到，因為 FuncX(head, &count) 傳入 count 的記憶體位址，但是在 FuncX 中，做的是 data++ 而不是 * data++ ，因此並不會實際計算走訪的 node，所以最後離開 FuncX 後 count 值仍為 0

第 5 週測驗（上）

題目

題目之 HackMD 連結

解題

測驗 1

Func 32 = ?
- 觀察程式碼
```
uint8_t Func32(uint32_t x) {
    return x ? Func32(x >> 1) - 1 : 32;
}
```
- 從式碼中可以看到，裡面有個遞迴呼叫，每次都把 x 右移 1 位，直到 x 的值為 0 時，會回傳 32，這時表示經過多次右移後得到的 x 其所有 bits 全部都為 0，但因為每次遞迴呼叫回傳後，後面還會將回傳值減掉 1，減一的意思代表著，這次右移去除掉的那個 bit，其存在不屬於從左到右連續全為 0 的一份子，因此把這些不屬於的部分一一減掉，便會得到一個
  $<= 32$ 的數字
- 而這個數字換句話說，便等於最一開始的 x 從左到右，從高位元到低位元共有幾個連續的 0
- 因此此題要選: © 計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 32
M1, M2, M3 = ?
- 觀察 FuncI，因為和 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;
}
```
- 在第五行中可以看到，將 x 向右移 16 位後，如果移位前原本的 16 ~ 32 bit 都是 0，就把 n + 16 ，之後再向右移 16 位，確保下次能從正確的位元開始計算
- 而在第六行中看到，通過 if 的條件後，做的是把 n 加上 8，因此可以知道是要確認 x 從高位元到低位元的 8 個 bits 是不是 0，以此類推第七行和第八行做的，便是確認 x 的前 4 個 bits 跟前 2 個 bits 是不是為 0
- 因此由上面可以知道，要能順利做到確認每個 if 所對應的 bits，要選擇 M1 = 24、M2 = 28、M3 = 30

測驗 2

Func64 的作用為?
- 觀察 Func64 相關的程式碼
```
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);
}
```
- 可以看到基本上和上一題中的 Func32 的做法相同，但是改為 64 位元的版本，把 64 個 bits 切為 low bits 32 個和 high bits 32 個，先找完 hi 中的 32 個 bits 後，再繼續判斷 lo 的 32 個 bits，最後得到結果。
- 因此此題要選的答案為: © 計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 64
P1 應該為?
- 先觀察包含 P1 的 function
```
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;
}
```
- 此函式是用來進行 32 位元的除法，在第六行中，先計算出 divisor 和 dividend 開頭皆為 0 的數字長度差距，差距為 mask
- 在第八行中，把除數向左移位 mask 位，為的就是讓除數對齊被除數，這樣才能達成我們平常在長除法時，從最高有效位開始做除法的目的，而在二進位中，因為只有 1 跟 0，所以除法是用減的，不需要計算相差幾倍的問題
- 參考 What does (1U << X) do?，才知道原來第九行中的 1U 是這個意思，代表把第 0 個 bit 設為 1，接著同樣移位 mask 位，讓 1 能夠對齊被除數的最高有效位
- 接著便是實際除法的部份，do while 中，被除數大於除數時，就讓被除數減掉除數後更新成新的被除數，接著第 13 行所做的便是除法中差幾倍的概念，只是因為數字都是 0 和 1，所以針對 mask 中 bit 為 1 的那一位數用 OR 的方式 set 在商數中，這樣有進行被除數和除數的相減時，對應的 bit 就會被設為 1，反之就會被設為 0
- 而藉由上面除法的過程，可以知道 mask 每次都必須要更新，需要向右移位一次，才能在每次要 set 商數時，能夠 set 到正確的 bit，所以得到 P1 必須填入 mask >> 1

P2 應該為?

包含 P2 的函式為 udiv64






































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;
}

udiv64 做的事情和 udiv32 相同，本質上也就是除法，但不同的地方在於這邊是針對 64 位元的數字做除法，且相比之下多了許多處理不同條件的程式碼
而注意到在實際除法的地方，多了一個變數 bits，在 32 位元的除法中，這裡 P2 的答案是 bit–，也就是判斷除到底了沒，是否該停止了，而這邊和 32 位元的地方不同，在 32 位元中，mask 同時用來 set bit 以及判斷除玩了沒有

這邊的話其實我不太清楚分開成兩個變數跟只用一個變數解決的差異在哪裡，思考後覺得有可能是讓一個變數 "專心" 做好一件事，會比較不容易出錯，或是比較好維護程式碼

參考 afcidk 的提問及 jserv 老師的回答，如下:

afcidk: 感覺這樣做才是正確的，為什麼 32-bit 的版本可以讓 mask>>=1 來替代 bits 的工作呢？
jserv: 32-bit 版本的實作並不完整，其作用只是 helper function，用來實作 64-bit 版本，實際上也只有後者真的被使用

P3 P4 P5 應該為?











while (v.dwords.high != 0) { /* process 64 bit value as long as needed */
        /* determine digits from right to left */
        udiv64(v.qword, 10, &d);
        *--pos = d.r.dwords.low + P3;
        v.qword = d.q.qword;
    }

    do { /* process 32 bit (or reduced 64 bit) value */
        nv.dwords.low = v.dwords.low / P4;
        *--pos = (v.dwords.low - (10 * nv.dwords.low)) + P5;
    } while ((v.dwords.low = nv.dwords.low) != 0);

註解中有說明 process 64 bit value as long as needed 以及 process 32 bit (or reduced 64 bit) value，然後看到程式碼的部分，要印出字元，需要將數字正確輸出的話要加 49，也就是 0x31，因此 P3 以及 P5 皆為 0x31
P4 是為了把數字轉成 10 進位，因此除以 10，故 P4 選 10

第 5 週測驗（中）

題目

題目之 HackMD 連結

解題

下方程式碼的輸出結果為 jserv++C




#include <stdio.h>
int main() {
    puts((char *) &(double []){ 3823806048287157.0, 96 });
}

首先先將 3823806048287157.0 以二進位表示：01000011 00101011 00101011 01110110 01110010 01100101 01110011 01101010
接著要將這一長串 0 和 1 轉換成 char ，因此將每 8 個 bits 一組形成一個字元，最後呈現的結果便是 C++vresj，但是因為使用的機器其儲存方式為 little-endian，所以顯示的結果會相反：jserv++C
再來看到題目的部份:










#include <stdio.h>
double m[] = { 3823806048287157.0, 96 };
void gen() {
    if (m[1]--) {
        m[0] *= 2;
        gen();
    } else
        puts((char *) m);
}
int main() { gen(); return 0; }

可以看到在 gen() 中，會將 m[0] 的值乘上 2，而因為遞迴的關係，最後 m[0] 會乘上
$2^{96}$
對於乘上
$2^{96}$ 在 IEEE 754 的規定中，即是要將第 52 到第 62 共 11 個 bits 的 exponent 加上 96，因此會得到 01001001 00101011 00101011 01110110 01110010 01100101 01110011 01101010，轉換成字元後及為：jserv++I

延伸題目

修改程式，允許輸出你的 GitHub 帳號名稱







#include <stdio.h>

int main() {
    puts((char *) &(double []){ 1.08497298767257192667014240249E-306, 96 });

}

輸出結果為：raygoah

修改 gen() 函式，透過特定的轉換，讓 m[] 的內容變為你的英文姓氏 (last name)

將 raygoah 改成 LEI
- raygoah:
  0 00000000110 1000011000010110111101100111011110010110000101110010
- LEI_____:
  0 10111110101 1111010111110101111101011111010010010100010101001100
由上面比較可知，sign bit 不變，而 exponent 需要加上 1519，因此乘上
$2^{1519}$
乘完後，次方相同的情況，再加上兩者的差距，即可順利轉換成要的結果













#include <stdio.h>
double m[] = { 1.08497298767257192667014240249E-306, 1519 };
void gen() {&nbsp;&nbsp;&nbsp;&nbsp;
    if (m[1]--) {
        m[0] *= 2;
        gen();
    } else {
        m[0] = m[0] + (0.57218400314947140020383950500E151);
        puts((char *) m);
    }
}
int main() { gen(); return 0; }

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

使用 codebeautify 可以發現到，要讓最後程式輸出得到 raygoah，一開始轉換時要輸入 haogyar，因此在 big_endian 環境中要得到正確結果的話，一開始轉換時就要注意

第 5 週測驗（下）

題目

題目之 HackMD 連結
考慮某款 MIPS 實作，其 data path 如下:

上圖紅色的 1, 2, 3 對 MIPS 做了對應的修改，請考慮以下狀況，分別解釋對應的程式碼是否能運作。

解題

測驗 `1`

Q11: 做了 1: Stuck at 0 left of cut 的修改，sw $s1, 0($s2) 能否運作？
Q12: 承上，下方程式能否運作？

lw $s1, 0($s2)
add $s1,$2,$3

在 1 切斷的電路中，關係到寫入 reg 的指令能不能運作
由上圖可以看到，第一列是 R-type 指令，第二列是 lw ，第三列是 sw ，第四列是 beq，所以切斷 1 後，會影響到 R-type 以及 lw ，而 sw 則不會受到影響，因為 sw 不用將值寫入reg，而是相反的將值從 reg 中寫入 memory
因此 Q11 是能運作的，但在 Q12 中，因為有使用到 lw，且 add 為 R-type 指令，所以不能正常運作

測驗 `2`

Q21: 做了 2: Cut here 的修改後，以下程式能否運作？
```
add $s1, $s1, $s1
add $s1, $t0, $t1
```

在 2 中切掉的電路，會影響到 RS 的 forwarding
但因為在第一行做完後，第二行中的 RS 及 RT 都沒有用到 $s1，只有在 RD 的地方使用到 $s1，因此此題不會有 Data Hazard 的情況發生，可以正常運作

測驗 `3`

Q31: 做了 3: Cut here 的修改後，以下程式能否運作？ (exit 為某個副程式)

cmp:
    xor $t1, $s2, $s1
    slt $t2, $zero, $t1
    sll $t2, 2
    add $ra, $ra, $t2
    jr  $ra

entry:
    addi $s2, $zero, 2
    addi $s1, $zero, 2
    jal  cmp
    j    exit

Q32: 承上，以下程式能否運作？

    addi $s2, $zero, 2
    addi $s1, $zero, 2
    beq $s2, $s1, exit

在 3 中切斷的電路，會影響到 PC + 4 + (imm*4) 的部份，也就是 I 型指令 beq，而對於 R 型指令：jr ，或是 J 型指令： j，都是沒有影響的
因此在 Q31 中，沒有使用到 beq，使用了 jr 以及 j，所以可以正常執行
而在 Q32 中，因為使用到了 beq 所以沒有辦法順利執行

2018q1 Homework3 (c-review)

第 4 週測驗

題目

測驗一

測驗二

第 5 週測驗（上）

題目

解題

測驗 1

測驗 2

第 5 週測驗（中）

題目

解題

延伸題目

第 5 週測驗（下）

題目

解題

測驗 1

測驗 2

測驗 3

參考

測驗 `1`

測驗 `2`

測驗 `3`