# D06: c-review
contributed by < `rex662624` >

## [第 4 週測驗題](https://hackmd.io/s/SyK-WApKM)

### 測驗 `1`
#### 解題
##### 1. 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;
}

這題觀察程式碼，關鍵是在第12行的部分，做了:插入的 node 下一個 node 是 start 。剩下的13~15行則是做了把插入的 node 放到合適的位置與把指標只好。因此 start 仍然為本來的 start ，但是start 前面卻多了一個 node，也就是在結尾的位置加入一個 node 。

而 2~8 行，則是在做尚未有任何一個 node 的狀況，因此在結尾插入的 node 也等於是 start。

故答案是: `(e)` 建立新節點，內容是 `value`，並安插在結尾

##### 2. 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;
}

這題本來我在想是不是與 funcA 是相同的。後來發現，差別在於第8行，它把 start 指向了新 node，因此是在開頭的地方插入新 node 。

答案是`(d)` 建立新節點，內容是 `value`，並安插在開頭

##### 3. 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;
}

首先第3行把新 node 值設為 value1 。而後從 start 一路找到值 = value2 的 node ，而後將 value1 的 node 放在 value2 node後面。

答案是 `(e)` 找到節點內容為 `value2` 的節點，並在之後插入新節點，內容為 `value1`

不過這裡好像有幾個沒有考慮的點:

1. 若是 start 是指向 NULL ，也就是尚未有任何 node 的時候，則程式應該會 core dumped ，因為有 temp->data 這個動作。
2. 若是根本沒有 value2 這個值，會進入無限迴圈，因為這是 circular linked list ，一路 next 到尾巴後又會從頭開始，永遠無法結束。因此user 必須自己保證 list 內一定有 value2 。

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

首先先看main

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

做到第 5 行結束時， list 是長這樣

[48]<->[51]<->[63]<->[72]<->[86]

觀察`Traversal in forward direction` 後做了

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

因此是從開頭一路印出 data，直到 start 的 prev 就跳出，因為最後又有印一次(第五行)，所以本來 for 沒有印出的最後一個 data 會被這行印出來。

因此答案順序為 48 51 63 72 86 。

##### 5. 在程式輸出中，訊息 `Traversal in reverse direction` 後依序印出哪幾個數字呢？
同樣的， list 是

[48]<->[51]<->[63]<->[72]<->[86]

程式碼:

    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");

這次是從 start 的前一個人開始印，一路往 prev 走直到走到 start ，這裡 start 並不會在 for 裡面印出來，而是跳出。直到第5行因為又做了一次 print ，才被印出來。

因此答案是 86 72 63 51 48

### 測驗 `2`
#### 解題
##### 1. `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 裡面，首先指向 head 的下一人，如果 node 是 NULL 或是 head 就會跳出，最後 return node - head 。在這裡如果是由於 NULL而跳出，則 node - head 不會是 0 ，而如果是因為回到 head 而跳出，則最後return 的會是 head 的 address 減掉自己，所以會是 0。而這也代表它是 circular linked list 。

因此答案是`(e)` 判斷是否為 circular linked list，若為 circular 則回傳 `0`，其他非零值

##### 2. ~ 6. `K1 >>` ~ `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;
}

首先必須要知道 node_new() 是如何運作。發現裡面只是要一塊空間並把值填入，然後把 next 指向 NULL 。

首先 9~13 行的圖形將會是以下:

9  head->[0]
10 head->[0]->[1]
11 head->[0]->[1]->[2]
12 head->[0]->[1]->[2]->[3]
13 head->[0]->[1]->[2]->[3]->[4]

因此`printf("K1 >> %s\\n", FuncX(head, &count) ? "Yes" : "No");` 會印出YES，因為這裡會回傳非0值，所以等於if ( true ) ，會印出前面的YES。**K1=YES**。

再來繼續觀察程式碼

head->next->next->next->next = head; 
printf("K2 >> %s\\n", FuncX(head, &count) ? "Yes" : "No");

本來的list是`head->[0]->[1]->[2]->[3]->[4]` 。`head->next->next->next->next `是[3]的next，因此[3]又會指向[0]成為 circular list，則 **K2=NO**。(但這裡[4]有 memory leak)

再處理K3

head->next->next->next->next->next = head->next; 
printf("K3 >> %s\\n", FuncX(head, &count) ? "Yes" : "No");

現在的list是head->[0]~[3]的單向 circular list 。而等號左邊的是[0]的next，等號右邊的也是[0]的next，因此list不變，這裡同樣**K3=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);

現在的list是head->[0]~[3]的單向 circular list 。而這裡等號左邊是[0]的next，要指向的是[0]，因此[0]自己指向自己，這裡同樣[1]~[3]會造成 memory leak 。因此最後也是一個circular linked list **K4=NO**

K5: head ([0]) 的next仍為[0]自己，因此印出的**K5=0**。

##### 7. `count >>` 後面接的輸出為何

這裡也同樣解釋了為何 1.並非 f 而是 e的原因。function 內宣告的 parameter 是 `int *data` ，而程式碼走訪每個 node 後做的是 data++; 這裡如果要輸出到底有多少 node 應該用`*data++`，而這裡 data++只不過加了 address ，而且因為對 address 是 pass by value ，所以並不會養想到 function scope 外面的任何值。

因此最後 count 仍然為原來的 0 。**K5=0**。

## [第 5 週測驗題 (上)](https://hackmd.io/s/SynmEVIqG)

### 測驗 `1`

考慮以下程式碼，推敲其作用 (選出最符合行為的描述)

uint8_t Func32(uint32_t x) {
    return x ? Func32(x >> 1) - 1 : 32;
}

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

#### 解題

**Func32 = ?**

觀察程式碼，發現做的動作是 recursive call Func32，途中 x 會不斷的右移 1 bits，直到最後 x 已經 =0，會 return 32 ，再一步一步的往上 -1 。而這個動作的意義在，右移到全部都為0了，就表示剛才 recursive call 的次數就等於尾數有幾位不為0。因此用32減掉尾數不為0有幾位，我們就可以得知開頭有幾個0。

==Ans:計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 32==

**M1、M2、M3=?**

參考[ st9007a 的 clz ](https://hackmd.io/s/rywfL4tj-)。

這裡是利用 if 來分別確認 `x` 的前 16 , 8 , 4 , 2 個 bits 是否為零，如果為零則將他們加入 `n`，並且左移 `x` 確保下個 if 能檢查到正確的位置，如果不為零則直接做下一個 if 檢查，最後 `x` 剩下 最前面的 1 bit 沒有被檢查到，在第9行做處理，如果是0就等於不做動作，如果是1就減掉1。~~第9行其實也可以在一開始做處理，多寫一個`if(x>>31==1)retrun 0 ;`，就可以把第9行刪掉。~~

因此答案是==M1=24 M2=28 M3=30==
>你這邊好像想錯了，n 一開始設為 1，所以所有"開頭有偶數個 0 "的情況第九行都是有意義的(x>>31=1)否則無法輸出偶數的 n，例如：
>開頭有 16 個 0 的話會跑if (!(x >> 16)) { n += 16; x <<= 16; }
>跑完後 n = 17, x = 10..0,到第九行 n = 17 - 1 = 16
[name=e94046165][color=green]
>>
>>感謝指正!的確 x 在中間就會被改值了。所以你說的是對的，若是偶數個 0 的狀況，因為 n 初值是1，最後跑完 if 就都會多1，要在第9行做處理。
>>[name=rex662624][color=#662624]

### 測驗 `2`

#### 解題

**Func64 的作用為？**

union u_qword {
    struct {
        uint32_t low;
        uint32_t high;
    } dwords;
    uint64_t qword;
};

struct udiv_result {
    union u_qword q;
    union u_qword r;
};

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

這裡將測驗1的 Func32 擴展為 64-bit 版本。方法是先把 64bits 分為前後 32bits，分別為 hi 和 lo 。 然後第18行判斷最高 32bits 是不是皆為0，若不是的話就呼叫 Func(32) 看看到底有0在最高位。如果前 32bits 都是0，則是用32+最低位又有幾個 leading 0 算出答案。
答案是==計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 64==

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

首先理解 do_udiv32 ，這裡用到的演算法與計算機組織用到的有點相似。
mask 是表示最後的商值有幾位數。do 裡面的演算法為，若 dividend > divisor ，dividend 就減去 divisor ，而最後的中止條件為直到(~(P1) | dividend==0) 這裡後面的 divided==0 是整除的情況跳出機制，所以可以推測 ~(P1) 是不整除的情況，也就是要用到 mask 來看商數是否已經夠長了。所以用 mask>>1 ，每次 while 迴圈算出一位數就右移一位，直到最後 mask \=\=0就跳出，因此==P1\:mask>>\=1==

同理可以推廣到下面的 64-bit 版本。這裡加上了一些除錯的機制。例如第27行是用來偵測是否除以0。

而這裡的答案==P2=bits - -==，與 32-bit 的跳出機制相同，都是偵測商數是否已經到達目標位數。

int main()
{
    char digitbuff[20];
    char *pos = digitbuff + sizeof(digitbuff);
    union u_qword v;  /* current value */
    union u_qword nv; /* next value */
    struct udiv_result d;

    int64_t value = 0xCAFEBABE; /* Java classfile magic number */
    v.qword = (unsigned long long) value;
    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);

    int len = digitbuff + sizeof(digitbuff) - pos;
    char *p = pos;
    while (len--)
        putchar(*p++);
    printf("\n");

    return 0;
}

首先P3和P5，都是做一樣的動作，把原本的數字存進 char 裡面，而這裡要把原本的數字變成 ascii 碼，所以要加上(48)~10~=(0x30)~16~。這裡參考[e94046165 同學](https://hackmd.io/6WXM0FXOR3C8T_E3f501Ww?view#%E6%B8%AC%E9%A9%97-21)找出的錯誤。

最後 P4 的部分，是因為我們要印出十進位，所以我們每次都要除10，如同我們如果要 1bit 1bit 印出二進位值，必須要用 number>>1(就是number/2)一樣。

## [第 5 週測驗題 (中)](https://hackmd.io/s/HkQjgqI5G)

### 解題

首先理解題目`jserv++C` ：

`puts((char *) &(double []){ 3823806048287157.0, 96 });`這行，把`3823806048287157.0`這個數字用 char * 型態印出來，因此透過[轉換](http://www.binaryconvert.com/convert_double.html)我們知道了在記憶體內的真實儲存資料為==01000011 00101011 00101011 01110110 01110010 01100101 01110011 01101010==
而因為一個字元就佔了 1byte ，所以我們可以知道上面的數字要用 8 bits為一個單位切割。透過[轉換](https://codebeautify.org/binary-string-converter)我們知道，答案會是 ==C++vresj== 。但這是在big-endian的狀況，而我們的環境若是little-endian，最大的 8 bit 反而會儲存在最後面。也就是其實答案是倒過來的==jserv++C==。

回過頭來看題目，實際上是把`3823806048287157.0`乘上了96次的2，因此在 IEEE-754 double-precision 等於是把次方的11個 bits 加上了96，因此影響的只有前兩個 byte ，也就是`+C`的部份。原本的 前兩個byte是 01000011 00101011 ，次方的11 bits 為1000011 0010，加上96之後會成為1001001 0010，也就是前兩個byte是 01001001 00101011 ，最後整個數字轉為 ascii 後就成為==I++vresj==，在 little-endian 印出的就是 ==jserv++I==

### 延伸題目[(github)](https://github.com/rex662624/2018D06-c-review/tree/master/W5_mid)

#### 修改程式，允許輸出你的 GitHub 帳號名稱
程式碼如下：

#include <stdio.h>
int main() {
    printf("%s",(char *) &(double []){8.2330057975734170815348646124E-67, 96 });
    puts((char *) &(double []){6.0134700169990949837211519873E-154, 96 });
}

我的 id 是 rex662624 ，因此64 bits是無法印出來的，因此需要兩行才能印出來。我的策略是：第一個數字先印出rex66262，第二個數字則印出4。

因次透過上面那兩個轉換網址，[ double-precision to deciaml ](http://www.binaryconvert.com/result_double.html?hexadecimal=2020202020202034)，[ string to binary ](https://codebeautify.org/string-binary-converter)，可以知道 rex66262 換成 decimal 是 8.2330057975734170815348646124E-67 ，而因為第二個字串只要印出4，我的 6.0134700169990949837211519873E-154 其實印出的是 =="4_______"== (去掉底線)，後面有七個空白，這樣剛好滿足 8 bytes。

如此一來，就能成功印出 rex662624 並換行。

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

jserv++C :`0` `10010010010` `1011001010110111011001110010011001010111001101101010`
rex_____: `0` `01000000010` `0000001000000010000000100000011110000110010101110010`

第一行是題目字串與它在記憶體的儲存方式，第二行則是目標產生的字串。
因此我把它分成三個部份處理，signed，exponent，mantissa。

首先第一個部份，因為 signed 一樣，所以不需要做處理。

第二個部份是 exponent，我採用了與原來相似的方式，讓它除上656次的2，就相當於把 exponent 減去656，達到我想要的數字。

第三個部份與第二個部份相關，我的方法是直接做加減法成我要的數字，而 ieee754的加減法，次方部份要做對齊才會是對的結果，因此次方的地方， m[0] 已經在第二部份被調整成目標的次方了，這裡就要用目標的次方去作加減法。

如此一來就成功輸出==rex==

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

#### 如果在 big-endian 的環境中，要達到一樣的效果，我們該如何改寫？

* 就範例程式提供的 jserv++C 來說:

1. 因為由上面的轉換，我們知道轉換出來的答案其實是 C\+\+vresj ，因此只要存入 jserv\+\+C 的數值，在big-endian 的環境就能達到正確的效果。
2. 參考[ stackoverflow ](https://stackoverflow.com/questions/2782725/converting-float-values-from-big-endian-to-little-endian)。也可以不改變數值，但是另外用一個函式ReverseFloat() 一個一個 char 轉過來。(注意網址中是只有32 bits ，因此只有 4個 char 空間，而若是適用於這題需要 0~7 ，8個空間。)

* 就題目主體gen()來說:
1. 與上一題的2.相同，gen()完再呼叫 ReverseFloat() 把它一個一個char轉過來。
2. 因為本來 C\+\+vresj ，改為 I\+\+vresj ，改變的是最前面的一個 byte 數值而已。而若是在 big-endian 的環境下則改變的是最後一個 byte 。因此不關 exponent 的事 ，而是要改 mantissa 部分，因此要用加減法去做改變 mantissa。

## [第 5 週測驗題 (下)](https://hackmd.io/s/Sk30MXDqM)

考慮某款 MIPS 實作，其 data path 如下:

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

### 解題

做這個測驗時，發現計算機組織忘記許多，備受打擊。但忘記就跟不會一樣意思，因此也不需要找藉口，只好回到白算盤尋覓過去的時光。

#### Q11:
**做了 `1: Stuck at 0 left of cut` 的修改，`sw $s1, 0($s2)` 能否運作？**


根據上面的這張圖(參考連結在最下方)，知道了這條線是控制 MemtoReg RegWr 這兩條訊號線，因此若沒有了這條線，Reg永遠不能被寫入， lw 、 add 等需要寫入 reg 的指令都會失效。
而sw不會失效，因為他不牽涉到寫回 reg 的動作。因此這題的答案是==可以運作==。

#### Q12:
**承上，下方程式能否運作？**

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

因為 lw 牽涉到寫回 reg ，而因為切掉這條訊號線導致 reg 不能被寫入，因此這個指令不能被運作。(第二個指令也不能運作，因為 add 需要加起來後把答案寫入 reg $s1)。答案是==不能運作==

#### Q21:
**做了 `2: Cut here` 的修改後，以下程式能否運作？**

add $s1, $s1, $s1
add $s1, $t0, $t1

這題的訊號線連接到的這個 mux ，是用來做選擇進入 ALU 的第一個 operand 來自 指令的部分，抑或是 Data forwarding 取上一個指令的值，這裡必須注意的是，只切了其中一條，因此 $Rs 或 $Rt 其中一個仍可以正常 Forwarding。

回頭看題目發現，這裡並不需要 Data forwarding ，因為這裡沒有 Data Hazard 發生，因此這題的答案為==可以運作==

#### 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

觀察3這條訊號，發現它是傳送 PC+4+(imm\*4) 的值，而最後會送到 program counter 前的 mux 選擇要取的值。因此若把這條線去掉了，則會使 beq bne 這種需要 PC+4+(imm\*4) 的 branch 指令失效。

回到題目發現這題沒有用到 bne beq 這類指令，而是用 jump ，因此這題答案是==可以運作==。

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

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

這裡有用到 beq ，因此答案是==無法運作==。

## 參考資料

* [計算機組織結構](https://hackmd.io/s/H1sZHv4R#)
* 白算盤書 & 計算機組織林英超老師上課講義