2018q1 Homework3 (c-review) === contributed by < `TingL7` > ## 第 4 週測驗題 測驗 `1` ![](https://i.imgur.com/iqFZJkY.png) 分析以下程式碼，推敲 `FuncA`, `FuncB`, `FuncC` 的作用，並且推測程式執行結果。 假設條件： * `malloc` 總是成功而且返回的記憶體空間可讀寫 ```Clike= #include <stdlib.h> #include <stdio.h> struct node { int data; struct node *next, *prev; }; 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; } 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; } 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; } 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; } ``` --- ### 解題想法 & 思考 * `FuncA` 的作用是 * 由開頭的 if 與第 14 行的可以發現，這個函式主要的功能是在建立新節點 * 新節點的 `next` 是 `*start` ， `prev` 是 `last` ，且 `*start` 沒有變動，因此新節點是安插在結尾。 * `FuncA` ：建立新節點，內容是 `value`，並安插在結尾 * `FuncB` 的作用是 * 基本架構與 `FuncA` 差不多 * 關鍵在於第 29 行 `*start = new_node;` 改變了開頭為新節點，也就是說，新節點是安插在開頭 * `FuncB` :建立新節點，內容是 `value`，並安插在開頭 * `FuncC` 的作用是 * 第 33~34 行在建立內容為 `value1` 的新節點 * 第 35~38 行在尋找內容為 `value2` 的節點 * 第 39~42 行在找到的節點後面插入新節點 * 因此， `FuncC` :找到節點內容為 `value2` 的節點，並在之後插入新節點，內容為 `value1` * 在程式輸出中，訊息 `Traversal in forward direction` 後依序印出哪幾個數字呢？ * `main` 中，依序建立： * **51** * **48** 51 * 48 51 **72** * 48 51 72 **86** * 48 51 **63** 72 86 * 由 `start` 不斷印出 `next` 的結果： `48 51 63 72 86` * 在程式輸出中，訊息 `Traversal in reverse direction` 後依序印出哪幾個數字呢？ * 由 `last` 不斷印出 `prev` 的結果： `86 72 63 51 48` ## 第 4 週測驗題 測驗 `2` ![](https://i.imgur.com/KKSlhnO.png) 考慮以下程式碼，推敲程式作用並分析輸出。 假設條件： * `malloc` 總是成功而且返回的記憶體空間可讀寫 * `malloc()` 得到的地址成嚴格單調遞增函數 ```Clike #include <stdio.h> #include <stdlib.h> /* Link list node */ struct node { int data; struct node *next; }; int FuncX(struct node *head, int *data) { struct node *node; for (node = head->next; node && node != head; node = node->next) data++; return node - head; } 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; } ``` --- ### 解題想法 & 思考 * `FuncX` 的作用是 (涵蓋程式執行行為的正確描述最多者) - [x] 走 circular linked list 所有節點 * for loop 中有走訪過所有節點，但是沒有對節點做任何事 - [x] 判斷是否為 circular linked list * 最後得到的 node 是 NULL 或 head ，回傳要兩個相減，明顯可以看出兩者的差異在於是否為 circular linked list - [ ] 計算節點數量並更新 * 改變的是 data 所紀錄的位址，也就是更新的是 count 的位址，並沒有計算節點數量 * 如果要計算節點數量，程式需要修改 ``` int FuncX(struct node *head, int *data) { struct node *node; for (node = head->next; node && node != head; node = node->next) (* data)++; return node - head; } ``` - [ ] 回傳最後一個節點和開頭的地址距離 (offset) * 若為 circular 回傳的便不是最後一個節點與開頭的距離 - [ ] 若為 circular 則回傳非零值，其他回傳 0 - [x] 若為 circular 則回傳 0，其他非零值 * 若為 circular 則 node 為 head ，因此回傳 head - head 0 * 若非 circular 則回傳最後一個節點和開頭的地址距離 (offset) - [ ] 過程中計算走訪的節點總數 * 改變的是 data 所紀錄的位址，也就是更新的是 count 的位址，並沒有計算走訪的節點數量 * 判斷是否為 circular linked list，若為 circular 則回傳 `0`，其他非零值 * `K1 >>` 後面接的輸出為何 * link list ```graphviz digraph graphname{ rankdir=LR; 0 -> 1; 1 -> 2; 2 -> 3; 3 -> 4; } ``` * 非 circular linked list ，`FuncX` 回傳 0 * `K1 >> Yes` * `K2 >>` 後面接的輸出為何 * `head->next->next->next->next = head;` head 0------>1------>2----->3 **------>** head * link list ```graphviz digraph graphname{ rankdir=LR; head[color=Blue, fontcolor=Red, fontsize=18, shape=box]; head -> 0; 0 -> 1; 1 -> 2; 2 -> 3; 3 -> 0; 4; } ``` * circular linked list ，`FuncX` 回傳 1 * `K2 >> No` * `K3 >>` 後面接的輸出為何 * `head->next->next->next->next->next = head->next;` head 0-------->1------>2------>3------>0 **----->** (head->next 1) * link list ```graphviz digraph graphname{ rankdir=LR; head[color=Blue, fontcolor=Red, fontsize=18, shape=box]; head -> 0; 0 -> 1; 1 -> 2; 2 -> 3; 3 -> 0; 4; } ``` * circular linked list ，`FuncX` 回傳 1 * `K3 >> No` * `K4 >>` 後面接的輸出為何 * `head->next = head->next->next->next->next->next->next->next->next;` head 0 **--------->** head 0------->1------>2------>3------>0------>1------>2------>3------>0 * link list ```graphviz digraph graphname{ rankdir=LR; head[color=Blue, fontcolor=Red, fontsize=18, shape=box]; head -> 0; 0 -> 0; 1 -> 2; 2 -> 3; 3 -> 0; 4; } ``` * circular linked list ，`FuncX` 回傳 1 * `K4 >> No` * `K5 >>` 後面接的輸出為何 * head->next->data head 指向自己，因此裡面的值是 0 * `K5 >> 0` * `count >>` 後面接的輸出為何 * `count` 初始值為 0 * 每次使用 `FuncX` 時，會傳入 `count` 的位址作為參數 `data` ，並在 `FuncX` 中改變 `data` ，但改變後的 `data` 不會回傳，因此實際上 `count` 沒有任何改變 * `count >> 0` ## 第 5 週測驗題 (上) 測驗 `1` 考慮以下程式碼，推敲其作用 (選出最符合行為的描述) ```clike uint8_t Func32(uint32_t x) { return x ? Func32(x >> 1) - 1 : 32; } ``` 將 `Func32` 改寫為以下功能等價的程式碼: ```clike 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 = ? * 從上方的程式碼可以發現 * 如果 `x` 不為 0 的話，每次就會向右移一位，且會傳值會減一，也就是 32 減去遞迴層數。 * 遞迴層數為從高位算來第一個 1 的位置，因此 32 減去遞迴層數即為從高位到低位開頭 0 的數量 * 從下方的程式碼可以發現， Func32 再做的事主要有兩件 * 如果 `x` 為 0 就回傳 32 * `if (!(x >> 16)) { n += 16; x <<= 16; }` 測試前 16 bit 是否為 0 ，是的話 `n` 加 16 ，表示 `n` 計算 0 的數量 * `n = n - (x >> 31);` 因為 `n` 的初始值為 1 ，假設至少有一個 0 ，所以這邊由最高位的值來決定 0 的數量 * 計算輸入數值 `x` 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 32 * M1 = ? * 測試前 8 位是否全為 0，經過 shift 之後，留下 8 位，因此要右移 `32 - 8` * M1 = 24 = 0x18 * M2 = ? * 比照 M1 留下 4 位 * M2 = 32 - 4 = 28 = 0x1C * M3 = ? * 比照 M1 留下 2 位 * M2 = 32 - 2 = 30 = 0x1E #### 參考資料 [重新理解數值](https://hackmd.io/s/SkKZBXZT#Count-Leading-Zero) ## 第 5 週測驗題 (上) 測驗 `2` 延伸測驗 `1`，將 `Func32` 應用於以下程式碼，可輸入給定 64-bit 數值的 10 進位表達方式 (類似 `printf` 函式的 `%d` 格式)，補完程式碼並推測其作用。 ```clike= #include <stdint.h> #include <stdio.h> 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); } 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; } 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; } ``` --- ### 解題想法 & 思考 * `Func64` 的作用為？ * 已知 `Func32`的功能為 計算輸入數值 `x` 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 `x` 為 0x0，則輸出 32 * `Func64` 中先將輸入的數字切成兩個 32bit 的 unsigned int，再測試 `val` 的前 32 是否全為 0 ，之後呼叫 `Func32` 得到開頭 0 的數量 * 基本上功能和 Func32 相似，只差在若 `x` 為 0x0 ，輸出64 * 計算輸入數值 `x` 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 `x` 為 0x0，則輸出 64 * `P1` = ? ```clike=24 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; } ``` * `do_udiv32()` 的功能： 做 32 位元的除法 * 一開始先利用 mask 對齊除數與被除數 * [1U](https://stackoverflow.com/questions/4192440/is-there-any-difference-between-1u-and-1-in-c)： unsigned value 1 * 1ULL: unsigned long long value 1 * do while loop 中變是在做長除法 * 被除數比除數大的話就可以除，不然就一到下一位 * 二進位除法不用考慮倍數，可以用減法做 * 有相減的話，表示該位元的結果為1，因此商 `res` 與 mask 做or * mask 應該每做完一位，就向右移 * 由上述可知， `P1` ＝ `mask >>= 1` * `P2` = ? * `udiv64()` 與 `udiv32()` 在除法的方面很像，最大的不同在於多了一個變數 `bits` ，此變數的功能在於計算商數的位數 * 第 70 行迴圈的條件該是計算到商的最後一位，也就是 bit 為 0 * 因此， `P2` = `bits--` * `P3` = ? ```clike=93 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; } ``` * 進行完一次除法後，要將結果存到 `pos` ， `pos` 是最後要以 char 印出的結果，因此為了使結果符合 ASCII 要加上 `'0'` 也就是 0x30 * `P3` = `0x30` * `P4` = ? `P5` = ? ```clike=100 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); ``` * 要計算十進位，因此，迴圈內每次都除 10 * `P4` = `10` * `pos` 儲存結果，如同 `P3` 要加上 `'0'` * `P5` = `0x30` ### 延伸題目： 將 10 進位輸出改為 16 進位 * 除以 10 的地方改為除以 16 * 輸出 10 以上要以 ABCDEF 代替，在 ASCII 中相當於加 0x37 ```clike=93 while (v.dwords.high != 0) { /* process 64 bit value as long as needed */ /* determine digits from right to left */ udiv64(v.qword, 16, &d); *--pos = d.r.dwords.low + ((d.r.dwords.low > 9) ? 0x37 : 0x30); v.qword = d.q.qword; } do { /* process 32 bit (or reduced 64 bit) value */ nv.dwords.low = v.dwords.low / 16; *--pos = (v.dwords.low - (16 * nv.dwords.low)) + (((v.dwords.low - (16 * nv.dwords.low)) > 9) ? 0x37 : 0x30); } while ((v.dwords.low = nv.dwords.low) != 0); ``` ### 延伸題目： 上方程式碼的 `0xCAFEBABE` 為 [magic number](https://en.wikipedia.org/wiki/Magic_number_(programming))，舉出在真實世界中程式的實際作用 (提示: 如 malloc) * [Java class file](https://en.wikipedia.org/wiki/Java_class_file) 的前 4 byte 為 magic number `CAFEBABE` 主要做用在於辨認 file 是否是能被接受的 class file * 參考[c語言里malloc的最優實現方式是什麼？](https://www.getit01.com/p20180109059544885/)， `malloc()` 中也會設置 magic number，主要是因為避免 free 到沒有 malloc 的位址，藉由 magic number 設置與否就可以檢查 ## 第 5 週測驗題 (中) 測驗 `1` 已知在 x86_64 架構，以下程式碼的執行輸出是 `jserv++C`: ```clike #include <stdio.h> int main() { puts((char *) &(double []){ 3823806048287157.0, 96 }); } ``` 考慮以下程式碼，假設 puts 函式總是可正確運作，那麼程式輸出為何？ ```clike #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; } ``` --- ### 解題想法 & 思考 * `double` 與 `char` 的轉換 * `3823806048287157.0` 轉換成 double 的表示式為 `0x432b2b767265736a` * 考慮到 x86_64 架構使用 little endianness ，實際上儲存的數字為 `0x6a736572762b2b43` * char 大小為 1byte ，因此 8byte 的 double 可以切成 8 個 char 根據 [ASCII](https://zh.wikipedia.org/wiki/ASCII)轉換： |6a|73|65|72|76|2b|2b|43| |--|--|--|--|--|--|--|--| |j|s|e|r|v|+|+|C| * 解讀程式 * `gen()` 的功能為改變 m[0] ，使輸出的字串改變。實際上做的是 m[0] * 2^96^ double 要乘上 2^96^ ，實際上是在 exp 部份加上 96 ，也就是 `0x432 + 0x60 = 0x492` 有改變的地方只有 `0x43` 變成 `0x49` ，也就是 `C` 變成 `I` * 因此，答案為 `jserv++I` ### 延伸題目：修改程式，允許輸出你的 GitHub 帳號名稱 * GitHub 帳號名稱：`TingL7` * ASCII: 0x54696e674c37 * 符合 double 有 8byte ，補上兩個空字元： 0x54696e674c370000 * little-endian: 0x0000374c676e6954 * 十進位： 3.003983e-310 * 程式碼 ```clike #include <stdio.h> int main() { puts((char *) &(double []){ 3.003983e-310, 96 }); } ``` * 結果： ``` յugL7 ``` 結果與預期不符，推測是換算成十進位的精度不足， double 的有效位數是16位，精度應取到那 * 修正： ```clike #include <stdio.h> int main() { puts((char *) &(double []){ 3.0039829763669880E-310, 96 }); } ``` * 結果 ``` TingL7 ``` ### 延伸題目：承上，修改 gen() 函式，透過特定的轉換，讓 m[] 的內容變為你的英文姓氏 (last name)，程式碼應該越短越好，而且不得以字串的形式存在於原始程式碼 * 英文姓氏： Lai * ASCII: 0x4c6169 * 符合 double 有 8byte ，補上 5 個空字元： 0x4c61690000000000 * little endian: 0x000000000069614c * 十進位： 3.4121102345210668E-317 * 目標：`0x0000374c676e6954` 轉換成 `0x000000000069614c` * 差異 ``` TingL7 00000000 00000000 00110111 01001100 01100111 01101110 01101001 01010100 Lai 00000000 00000000 00000000 00000000 00000000 01101001 01100001 01001110 diff 00000000 00000000 00110111 01001100 01100111 00000111 00001000 00011010 ``` * ~~進行 bitwise 的操作？~~ * exp部份都是 0 , 不用變動 * 兩者相差 3.0039826351559646E-310 * 程式碼 ```clike #include <stdio.h> double m[] = { 3.0039829763669880E-310, 3.0039826351559646E-310 }; void gen() { m[0] = m[0] - m[1]; puts((char *) m); } int main() { gen(); return 0; } ``` ### 延伸題目：如果在 big-endian 的環境中，要達到一樣的效果，我們該如何改寫？ * 修改輸入，不需要轉換 * TingL7 * little-endian: 0x0000374c676e6954 = 3.0039829763669880E-310 * big-endian: 0x54696e674c370000 = 4.3456679652866146e+98 * Lai * little-endian: 0x000000000069614c = 3.4121102345210668E-317 * big-endian: 0x4c61690000000000 = 8.7428257608182613e+59 * 差異 * exp: 0x546 - 0x4c6 = 0x080 = 128 * frac: 0x4c696e674c370000 - 0x4c61690000000000 = 4.0279445985412390e+59 * 程式碼 ```clike #include <stdio.h> int main() { puts((char *) &(double []){ 4.3456679652866146e+98, 96 }); } ``` ```clike #include <stdio.h> double m[] = { 4.3456679652866146e+98, 128, 4.0279445985412390e+59 }; void gen() { if (m[1]--) { m[0] *= 2; gen(); } else { m[0] = m[0] - m[2]; puts((char *) m); } int main() { gen(); return 0; } ``` ## 第 5 週測驗題 (下) 考慮某款 MIPS 實作，其 data path 如下: ![](https://i.imgur.com/Y80lxhP.png) 上圖紅色的 `1`, `2`, `3` 對 MIPS 做了對應的修改，請考慮以下狀況，分別解釋對應的程式碼是否能運作。 --- ### 測驗 `1` * Q11: 做了 `1: Stuck at 0 left of cut` 的修改，`sw $s1, 0($s2)` 能否運作？ * 可以 * sw ![](https://i.imgur.com/pK8rKKX.png) * sw 不需要 WB，因此做了 `1: Stuck at 0 left of cut` 也不影響運作 :::info data memory 要 load 或 store 都需要兩個值， address 及 data ，為什麼圖片上的 data memory 只有一個輸入？ ::: * Q12: 承上，下方程式能否運作？ ``` lw $s1, 0($s2) add $s1,$2,$3 ``` * 不可以 * lw ![](https://i.imgur.com/AOFMoEk.png) * add ![](https://i.imgur.com/ecgnxgc.png) * lw 和 add 都需要將結果存回暫存器($s1) ，因此做了這個修改後會無法運作 --- ### 測驗 `2` * Q21: 做了 `2: Cut here` 的修改後，以下程式能否運作？ ``` add $s1, $s1, $s1 add $s1, $t0, $t1 ``` * 可以 * add ![](https://i.imgur.com/jG4quPB.png) * 這條線的作用在於，當 exe 階段的指令會用到 mem 階段的值，才需要先丟回去運算 * e.g. ``` add $t1, $s1, $s1 sub $s1, $t0, $t1 ``` `$t1` 在 `sub` exe 階段時， `add` 的 `$t1` 還沒寫回 reg ，因此 `$t1` 的值是不正確的，修正方法便是將在 mem 階段的結果丟給 sub ，也就是 `2: Cut here` 修改前可以做到的事 --- ### 測驗 `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 ``` * 不可以 * j([參考圖片](https://userpages.umbc.edu/~squire/cs411_l15.html)) ![](https://i.imgur.com/TY3djzM.png) * 是否切掉 `3` 的線都無法做 jump ，因為在本題圖片的架構中，能夠改變 PC 的只有下一道指令 (PC+4) 以及 branch 的結果 :::info 參考其他同學的答案都是可以的，如果可以運作，在題目的 MIPS 實做是如何運作呢？ ::: * Q32: 承上，以下程式能否運作？ ``` addi $s2, $zero, 2 addi $s1, $zero, 2 beq $s2, $s1, exit ``` * 不可以 * beq ![](https://i.imgur.com/5rMhrFP.png) * beq 所儲存的 exit 是指該指令與 exit 的距離，所以必須加上 PC 才會指向正確的地方，因此如果切斷 `3` 會無法運作 ## 第 1 週測驗題 測驗 `5` 考慮以下整數乘法的實作程式碼: ```C int mul(int n, int m) { int ret = 0; for (int c = 0; m; c++, m /= 2) if (!(m % 2 - 1)) OP return ret; } ``` 上述 `OP` 對應到下方哪個程式敘述呢？ --- ### 解題想法 & 思考 * 利用直式乘法的概念實作 e.g. * 1011 * 101 = 110111 (11 * 5 = 55) ``` 1011 * 101 --------- 1011 0000 + 1011 --------- 110111 ``` * 變數 * ret : 乘法結果 * c : 乘數位數 * n : 被乘數 * m : 乘數 * for loop * if 判斷目前 m 的最後一個 bit 為 1 或 0 * 為 1 的話執行 OP * 之後捨棄最後一個 bit 並且提升一個位數 * 因此， OP 的內容必須包括 * 移到適當位數的被乘數加上累積下來的結果 * OP = `ret += n << c;` ## 第 3 週測驗題 測驗 `2` 考慮到下方函式 `shift_right_arith` 和 `shift_right_logical` 分別表示算術右移和邏輯右移，請嘗試補完程式碼。可由 `sizeof(int) * 8` 得知整數型態 `int` 的位元數 `w`，而位移量 `k` 的有效範圍在 0 到 `w - 1`。 ```Clike #include <stdio.h> int shift_right_arith(int x, int k) { int xsrl = (unsigned) x >> k; int w = sizeof(int) << P1; int mask = (int) -1 << (P2); if (x < 0) return xsrl P3 mask; return xsrl; } unsigned shift_right_logical(unsigned x, int k) { unsigned xsra = (int) x >> k; int w = sizeof(int) << P4; int mask = (int) -1 << (P5); return xsra P6 P7; } ``` --- ### 解題想法 & 思考 * P1 = ? P4 = ? * `sizeof()` 回傳的單位是 byte 但是 `w` 是 `int` 的位元數，因此要乘上 8 * `* 8` 等價於 `<< 3 * 因此， P1 = P4 = 3 * P2 = ? P5 = ? * mask 是為了做 x 為負數時使用的遮罩 * 參考[Arithmetic Shift Operations](http://www-mdp.eng.cam.ac.uk/web/library/enginfo/mdp_micro/lecture4/lecture4-3-3.html)、[C/C++ 負整數的 shift](https://fcamel-life.blogspot.tw/2011/10/arithmetic-right-shift.html)中，提到C/C++ 沒有定義 signed shift 的行為，也可以透過 compiler 加參數來改變結果。 right shift ，在 [Visual studio](https://msdn.microsoft.com/zh-tw/library/336xbhcz.aspx) 及 [gcc](https://gcc.gnu.org/onlinedocs/gcc-4.3.3/gcc/Integers-implementation.html#Integers-implementation) 中都是在前面補上 sign bit * mask 的目的為 shift 後，將前面缺漏的 bit 補 1 * 也就是，把前（總 bit 扣掉 位移量）這麼多 bit 補1 * 因此， P2 = P5 = w - k * P3 = ? (為某種 operation) * 前 （w - k） 個 bit 必定是 1， mask 符合條件， `xsrl` 這部份全為 0 * 後 w 個 bit 看位移結果 `xsrl`， mask 這部份全為 0 * 因此， 使用 `|` 便能夠合成兩個變數取出需要的部份 * P3 = `|` * P6 = ? (為某種 operation) P7 = ? * logical 無論正負前面都要補 0 * 因此，`return xsra & ~mask`