owned this note
owned this note
Published
Linked with GitHub
D06: c-review
=============
contributed by <`workat60474`>
# 第 3 週測驗題1（選擇不熟悉的部分重新作答之一）
延續 [從 $\sqrt{2}$ 的運算談浮點數](https://hackmd.io/s/ryOLwrVtz)，假設 double 為 32-bit 寬度，考慮以下符合 IEEE 754 規範的平方根程式，請補上對應數值，使其得以運作：
```Clike
#include <stdint.h>
/* A union allowing us to convert between a double and two 32-bit integers.
* Little-endian representation
*/
typedef union {
double value;
struct {
uint32_t lsw;
uint32_t msw;
} parts;
} ieee_double_shape_type;
/* Set a double from two 32 bit ints. */
#define INSERT_WORDS(d, ix0, ix1) \
do { \
ieee_double_shape_type iw_u = { \
.parts.msw = ix0, \
.parts.lsw = ix1, \
}; \
(d) = iw_u.value; \
} while (0)
/* Get two 32 bit ints from a double. */
#define EXTRACT_WORDS(ix0, ix1, d) \
do { \
ieee_double_shape_type ew_u; \
ew_u.value = (d); \
(ix0) = ew_u.parts.msw; \
(ix1) = ew_u.parts.lsw; \
} while (0)
static const double one = 1.0, tiny = 1.0e-300;
double ieee754_sqrt(double x)
{
double z;
int32_t sign = 0x80000000;
uint32_t r, t1, s1, ix1, q1;
int32_t ix0, s0, q, m, t, i;
EXTRACT_WORDS(ix0, ix1, x);
/* take care of INF and NaN */
if ((ix0 & KK1) == KK2) {
/* sqrt(NaN) = NaN, sqrt(+INF) = +INF, sqrt(-INF) = sNaN */
return x * x + x;
}
/* take care of zero */
if (ix0 <= 0) {
if (((ix0 & (~sign)) | ix1) == 0)
return x; /* sqrt(+-0) = +-0 */
if (ix0 < 0)
return (x - x) / (x - x); /* sqrt(-ve) = sNaN */
}
/* normalize x */
m = (ix0 >> 20);
if (m == 0) { /* subnormal x */
while (ix0 == 0) {
m -= 21;
ix0 |= (ix1 >> 11);
ix1 <<= 21;
}
for (i = 0; (ix0 & 0x00100000) == 0; i++)
ix0 <<= 1;
m -= i - 1;
ix0 |= (ix1 >> (32 - i));
ix1 <<= i;
}
m -= KK3; /* unbias exponent */
ix0 = (ix0 & 0x000fffff) | 0x00100000;
if (m & 1) { /* odd m, double x to make it even */
ix0 += ix0 + ((ix1 & sign) >> 31);
ix1 += ix1;
}
m >>= 1; /* m = [m/2] */
/* generate sqrt(x) bit by bit */
ix0 += ix0 + ((ix1 & sign) >> 31);
ix1 += ix1;
q = q1 = s0 = s1 = 0; /* [q,q1] = sqrt(x) */
r = 0x00200000; /* r = moving bit from right to left */
while (r != 0) {
t = s0 + r;
if (t <= ix0) {
s0 = t + r;
ix0 -= t;
q += r;
}
ix0 += ix0 + ((ix1 & sign) >> 31);
ix1 += ix1;
r >>= 1;
}
r = sign;
while (r != 0) {
t1 = s1 + r;
t = s0;
if ((t < ix0) || ((t == ix0) && (t1 <= ix1))) {
s1 = t1 + r;
if (((t1 & sign) == sign) && (s1 & sign) == 0)
s0 += 1;
ix0 -= t;
if (ix1 < t1)
ix0 -= 1;
ix1 -= t1;
q1 += r;
}
ix0 += ix0 + ((ix1 & sign) >> 31);
ix1 += ix1;
r >>= 1;
}
/* use floating add to find out rounding direction */
if ((ix0 | ix1) != 0) {
z = one - tiny; /* trigger inexact flag */
if (z >= one) {
z = one + tiny;
if (q1 == (uint32_t) 0xffffffff) {
q1 = 0;
q += 1;
} else if (z > one) {
if (q1 == (uint32_t) KK4)
q += 1;
q1 += 2;
} else
q1 += (q1 & 1);
}
}
ix0 = (q >> 1) + 0x3fe00000;
ix1 = q1 >> 1;
if ((q & 1) == 1)
ix1 |= sign;
ix0 += (m << KK5);
INSERT_WORDS(z, ix0, ix1);
return z;
}
```
## 程式碼分析
* 首先這段程式碼的用途在於將作為參數的 double x做開根號運算，由於double 佔用64bits，為了讓double大小的數字在32-bit的int中表示，首先利用一個c語言中常用的技巧，透過union來做type casting，由於union的大小取決於其member中所佔用空間最大的成員。
* 在以下的union中， double value 和 parts都佔用了64-bit，故我們可以把value的bit分成兩部分，前$63-32bits$放在uint32_t msw中，後$31-0bits$放在 uint32_t lsw中。
```clike=
typedef union {
double value;
struct {
uint32_t lsw;
uint32_t msw;
} parts;
} ieee_double_shape_type;
```
接下來的兩個巨集指令
```clike=
/* Set a double from two 32 bit ints. */
#define INSERT_WORDS(d, ix0, ix1) \
do { \
ieee_double_shape_type iw_u = { \
.parts.msw = ix0, \
.parts.lsw = ix1, \
}; \
(d) = iw_u.value; \
} while (0)
```
```clike=
/* Get two 32 bit ints from a double. */
#define EXTRACT_WORDS(ix0, ix1, d) \
do { \
ieee_double_shape_type ew_u; \
ew_u.value = (d); \
(ix0) = ew_u.parts.msw; \
(ix1) = ew_u.parts.lsw; \
} while (0)
```
* INSERT_WORDS 的作用是將代表數字前 $63-32$ bits 的ix0以及後 $31-0$ bits 的 ix1，透過前述的 union-type-casting 的方式將 bit-pattern 擺進佔 64-bits 的 value 裡面。
* EXTRACT_WORDS 其作用則是把 64-bit 長的 d 其 bit-pattern 前 $6332$ bits 放進 ix0 而後 $31-0$ bits 放進ix1裡面。
* 注意到在這兩個marco中，都使用了 "do...while(0)" 這樣的寫法，雖然看似只執行了一次，但是假設我們寫出以下的巨集指令
```clike=
#define Unsafe_macro(p)
free(p) ;
p=NULL;
//在他處如此使用該指令
if(p) Unsafe_macro(p) ;
else do something else; /*會造成dangling-else 因為編譯器沒辦法在
* 第一個 if-statement 後找到第二個 eles if。
*/
//雖然這樣撰寫即可避免這種錯誤
if(p){
Unsafe_macro(p) ;
}
else do something else;
/*但是考慮其他使用這段程式碼的人，可能沒注意到這點，
* 所以總是盡可能寫出無暇的程式碼，是一種良好的開發風格。*/
```
```clike=
/* take care of INF and NaN */
if ((ix0 & KK1) == KK2) {
/* sqrt(NaN) = NaN, sqrt(+INF) = +INF, sqrt(-INF) = sNaN */
return x * x + x;
}
```
在IEEE-754中 INF 和 NaN 其 Exponent 部份都為 1 ，而雙精度浮點數中的 exponent 佔了 11 個 bits ， 當ix0 其 Exponent 全為 1 時，代表 x 為 INF or NaN。
:::success
KK1=KK2= 0x7FF00000
:::
```clike=
/* take care of zero */
if (ix0 <= 0) {
if (((ix0 & (~sign)) | ix1) == 0)
return x; /* sqrt(+-0) = +-0 */
if (ix0 < 0)
return (x - x) / (x - x); /* sqrt(-ve) = sNaN */
}
```
* 若 x=0 則：
* ix0 ＝ 0 這也代表 ix0 其作為 signed-int(有號整數) 的 sign_bit 為 0
* ix1 = 0
* 此時直接傳回 x (x=0)
* 若 x<0 則：
* 對負數做開根號運算會涉及虛數計算，這會得到 $NaN$ ，因此我們傳回 $sNaN$
* 而要產生 $NaN$可以透過
* 未定義操作：0/0、∞/∞、∞/−∞、−∞/∞、−∞/−∞、0×∞、0×-∞、(∞ + (−∞))、((−∞) + ∞)、(∞ - ∞)、(−∞) - (−∞)
* 產生複數結果的實數運算
* 運算元中至少有一個是涉及了NaN的運算
* 而我們採用 $(x - x) / (x - x)=0/0$的方式來得到 $NaN$
```clike=
/* normalize x */
m = (ix0 >> 20);
if (m == 0) { /* subnormal x */
while (ix0 == 0) {
m -= 21;
ix0 |= (ix1 >> 11);
ix1 <<= 21;
}
for (i = 0; (ix0 & 0x00100000) == 0; i++)
ix0 <<= 1;
m -= i - 1;
ix0 |= (ix1 >> (32 - i));
ix1 <<= i;
}
```
* 上述這段 code 的整體用途在於調整 x (ix0|ix1) 由非正規化至正規化數（調整到x 之 exp_bit=1 即可）。
* m 用以表示 x 的 Signed_bit + exponent_bits
* 因為剛剛沒有進入上一個 if-statement (if (ix0 <= 0)) 這代表 ix0 > 0 故 ix0 之 Signed_bit=0
* 故 m = (ix0 >> 20) 就數值的觀點上等於 x 的 expoenent之值。
* 若 m＝0 代表 x 為非正規化數（x 為非正規化數的定義為 exp==0 但 frac!=0 ），故進入 if (m == 0) 。
* 而整個 while (ix0 == 0) 迴圈的內容其目的在於：透過將 x 的低位部分 bits(ix1) 左移進而調整到 ix!=0 為止
* 而選擇一次左移 21 個bits的理由在於只要左移到 x 之 exp_bits=1 即可。
* 而 m 代表著 x的指數數值，隨著左移 m 之值也要跟著減少（一次減少21)
* m -= i - 1 代表 m= m -i +1 ，其中的 +1 的原因在於：此時 ix0 的 exponent 部分值為 1，得對應地把用來表示指數的 m 也加上 1。
* 因為 x 是非正規化數，假定 x 的 (fraction = $(00111...)_2$)，將其視為$(0.00111...)_2$而假設隨著左移調整為 $(1)1100..._2$ 視為 $(1.1100...)_2$，這在二進位中等價於乘以 2 。
```clike=
m -= KK3; /* unbias exponent */
ix0 = (ix0 & 0x000fffff) | 0x00100000;
if (m & 1) { /* odd m, double x to make it even */
ix0 += ix0 + ((ix1 & sign) >> 31);
ix1 += ix1;
}
m >>= 1; /* m = [m/2] */
```
* 根據上述的討論 m 目前代表 x 的指數數值部分，不過這是“unbias”的數值，在 IEEE754 中指數要減去 bias，才會得到正確的指數數值 ，故
:::success
KK3=$2^{11-1}-1$=$2^{10}-1$=1023
:::
* 考慮到之後開根號運算，避免還要再次考慮 ix0 中的 IEEE-754 編碼，為了計算上的便利，把其 Signed_bit（事實上，到這個步驟，x 的Signed_bit 已確認為 0 了， 因 x 必定是正數 ） 和 Exponent_bits 的部分通通設為 0x001 。
* 把 ix0 的 exp 部分設為 1 。
* 指數部分由 m 來表達。
* 對指數來說，開根號相當於除以 2 ，為了避免 指數部分 m 為奇數， 透過 (m&1) 來判斷 m 是否為奇數
* 若 m 是奇數則把 ix0 和 ix1 乘以二（透過$ix0 += ix0 + ((ix1 & sign) >> 31); ix1 += ix1;$）來補回遺失的部分。
* m >>= 1; /* m = [m/2] */ $\Longrightarrow$ 已經透過將指數除以 2 完成了指數的開根號運算。
* 接著來進行將指數前的數字（[ix0 , ix1]）做開根號運算：
* 可以參閱
* http://highscope.ch.ntu.edu.tw/wordpress/?p=51628
* https://www.youtube.com/watch?v=G_4HE3ek4c4
* https://en.wikipedia.org/wiki/Methods_of_computing_square_roots (digit-by-digit的部分)
* 我用 $\sqrt{625_{10}}$來做說明
* $625_{10}=(1001110001)_2$
```
1 1 0 0 1
--------------------
√ 10, 01, 11, 00, 01
1 10
01 => 01在這裡代表每個回合的減數，也就是下方程式碼中的變數t
---------
101 01, 01
1, 01
--------
1100 0, 11
0
---------
11000 0, 11, 00
0, 00, 00
-------------
110001 0, 11, 00, 01
0, 11, 00, 01
-------------------
0
```
以下程式碼即是透過上述的直式開根號法，對 ix0 和 ix1 分別進行開根號，並把結果保留在[q,q1]中(合在一起視為一個64-bits長的數字) ，我把一些值得注意的地方，直接寫在下方程式碼的註解裡。
```clike=
/* generate sqrt(x) bit by bit */
/* ix0在先前已經被設定為： 0x0001XXXXX (X 可表示0 or 1)
為了要讓數字對齊r=0x00200000，得把(ix0|ix1)乘以2 */
ix0 += ix0 + ((ix1 & sign) >> 31);
ix1 += ix1;
q = q1 = s0 = s1 = 0; /* [q,q1] = sqrt(x) */
r = 0x00200000; /* r = moving bit from right to left */
while (r != 0) {
t = s0 + r;
if (t <= ix0) {
s0 = t + r;
ix0 -= t;
q += r;
}
ix0 += ix0 + ((ix1 & sign) >> 31);
ix1 += ix1;
r >>= 1;
}
r = sign; //r改成由0x80000000 開始往右移
while (r != 0) {
t1 = s1 + r;
t = s0;
if ((t < ix0) || ((t == ix0) && (t1 <= ix1))) {
s1 = t1 + r;
if (((t1 & sign) == sign) && (s1 & sign) == 0)
//減數t1＝0x80000000，且s1為0x0XXXXXXXX
//代表在s1=t1+r的時候，s1發生了overflow
//得將s0+1來進行減數的進位。
s0 += 1;
ix0 -= t;
if (ix1 < t1)
ix0 -= 1;
ix1 -= t1;
q1 += r;
}
ix0 += ix0 + ((ix1 & sign) >> 31);
ix1 += ix1;
r >>= 1;
}
```
* 以下程式碼接著進行數字的 rounding (捨入)。
* 首先檢查 （ix0|ix1） 是否為0，若為 0 代表 x 為平方數，沒有捨入的必要。
* 若 （ix0|ix1）不為 0，透過設定 z=1.0-1.0-e300 來檢查是不是會觸發 INEXACT flag 的例外。
* 上網查找了一下資料，https://docs.oracle.com/cd/E19957-01/806-3568/ncg_handle.html
* 看到 inexact-flag 發生在“ The rounded result of a valid operation is different from the infinitely precise result.”
* 沒有觸發例外，接著判定系統如何看待 z = 1.0 + 1.0e-300 這樣的數字，會將 z 視為 >1.0 的數字，還是忽略 1.0e-300，直接將 z 視為1?
* 若 q1 為 0xffffffff ，將 0xffffffff 捨入到 1 故將 q1設為 0，並把 q+1。
* 若系統將 z 看作 >1 的數 ，對其做 round up(round to $+\infty$)，把 q1+2，使其為偶數，且若
* (q1 == (uint32_t) 0xfffffffe ) 因為( 0xfffffffe+2 會需要進位到 q ) 還要記得把進位的 1 加到q。
* 若系統將 z 看作 1 ，我們就只需要單純做 round to nearest even，透過(q1＆1)做對偶數捨入。
:::success
KK4=0xfffffffe
:::
```clike=
/* use floating add to find out rounding direction */
if ((ix0 | ix1) != 0) {
z = one - tiny; /* trigger inexact flag */
if (z >= one) {
z = one + tiny;
if (q1 == (uint32_t) 0xffffffff) {
q1 = 0;
q += 1;
} else if (z > one) {
if (q1 == (uint32_t) KK4)
q += 1;
q1 += 2;
} else
q1 += (q1 & 1);
}
}
```
* 最後把為了要利用 INSERT_WORDS(z, ix0, ix1) 把 （ix0|ix1）放回 z 裡面，得將 ix0 和 ix1 調整回符合IEEE-754的編碼方式。
* 我把一些注意事項寫在下方的註解裡面。
```clike=
ix0 = (q >> 1) + 0x3fe00000; //將 q>>1 空出一個 bit 用以表達 signed-bit ，並且將 bias=1023=ox3fe00000 加回去。
ix1 = q1 >> 1; //隨著 q>>1 ，q1也得跟著右移一個bit。
if ((q & 1) == 1) // 若 q 的最後一個bit為 1，在進行 q>>1時會隨著右移將其忽略掉，把 1 補回 ix1 。
ix1 |= sign;
ix0 += (m << KK5); //並且把代表指數部分的 m 左移到位置為 30-20 的 bit（ IEEE-754 中， exp 的 bit 位置）
INSERT_WORDS(z, ix0, ix1);
return z;
```
:::success
KK5=20;
:::
## 延伸問題：將其改為float版本
* 比起double的版本較為容易，概念雷同，而且需要考慮的部分較少。
```clike=
#include <stdint.h>
typedef union {
float value;
uint32_t sw;
} ieee_float_shape_type;
#define INSERT_WORDS(d, ix0) \
do { \
ieee_float_shape_type iw_u; \
iw_u.sw = (ix0); \
(d) = iw_u.value; \
} while (0)
#define EXTRACT_WORDS(ix0, d) \
do { \
ieee_float_shape_type ew_u; \
ew_u.value = (d); \
(ix0) = ew_u.sw; \
} while (0)
static const float one = 1.0, tiny = 1.0e-30;
float ieee754_sqrt_float(float x)
{
float z;
int32_t sign = 0x80000000;
uint32_t r;
int32_t ix0, s0, q, m, t, i;
EXTRACT_WORDS(ix0, x);
/* take care of zero */
if (ix0 <= 0) {
if ((ix0 & (~sign)) == 0)
return x; /* sqrt(+-0) = +-0 */
if (ix0 < 0)
return (x - x) / (x - x); /* sqrt(-ve) = sNaN */
}
/* take care of +INF and NaN */
if ((ix0 & 0x7ff00000) == 0x7ff00000) {
/* sqrt(NaN) = NaN, sqrt(+INF) = +INF,*/
return x;
}
/* normalize x */
m = (ix0 >> 23); // bit 2-10 are for exponent-bits
if (m == 0) {
for (i = 0; (ix0 & 0x00800000) == 0; i++)
ix0 <<= 1;
m -= i - 1;
}
m -= 127; /* unbias exponent */
ix0 = (ix0 & 0x007fffff) | 0x00800000;
if (m & 1) {
ix0 += ix0;
}
m >>= 1; /* m = [m/2] */
/* generate sqrt(x) bit by bit */
ix0 += ix0;
q = s0 = 0; /* q = sqrt(x) */
r = 0x01000000;
while (r != 0) {
t = s0 + r;
if (t <= ix0) {
s0 = t + r;
ix0 -= t;
q += r;
}
ix0 += ix0;
r >>= 1;
}
/* use floating add to find out rounding direction */
if (ix0 != 0) {
z = one - tiny; /* trigger inexact flag */
if (z >= one) {
z = one + tiny;
if (z > one)
q += 2;
else
q += (q & 1);
}
}
ix0 = (q >> 1) + 0x3f000000;
ix0 += (m << 23);
INSERT_WORDS(z, ix0);
return z;
}
```
# 第 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;
}
```
* 在 xsrl = (unsigned) x >> k 中，利用 unsiged 來表示 x ， 在c語言中，unsined 數的右移皆是以補 0 來處理左邊被空出的bit。
* 若 x>=0 則 logic_shift_right 和 arithmetic_shift_right 行為是一致的，因此我們只考慮 x<0 的情況。
* 透過提示： 可由 sizeof(int) * 8 得知整數型態 int 的位元數 w ， 乘以 8 相當於 左移 3 個 bits，也就是說 w=4<<3 。
:::success
P1=3;
:::
* 先舉個例子來思考 P2 和 P3的可能的用途
* 假設 某種 type 只有 5 個 bits ( w = 5 )， x = $(11000)_2$ ，且 k = 2
* (unsigned) x >> 2 = $00110_2$
* ( signed) x >> 2 = $11110_2$ （這才是算數右移的正確結果）
* $(11110)_2$ $=$ $(00110)_2|(11000)_2$ 而 $(11000)_2$
* $\Longrightarrow$$(11111)_2<<(5-2)$
* $\Longrightarrow$$(11111)_2<<(w-k)$
根據上述討論得到
:::success
P2=(w-k) 而 P3=|
:::
```clike=
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;
}
```
* 同上述的討論可知 w = 32
:::success
P4=3;
:::
* 假設 某種 type 只有 5 個 bits ( w = 5 )， unsigned x = $(11000)_2$ ，且 k = 2
* (int ) x >> 2 = $11110_2$
* (unsigned) x >> 2 = $00110_2$ （這才是邏輯右移的正確結果）
* $(00110)_2$ $=$ $(11110)_2 & ~(11000)_2$ 而 $(11000)_2$
* $\Longrightarrow$$(11111)_2<<(5-2)$
* $\Longrightarrow$$(11111)_2<<(w-k)$
* 其實考慮效率的話，利用 xsra ^ = mask 較快。
:::success
P5=(w-k) ， P6=＆ ， P7=~mask
:::
## 延伸題目: 在 x86_64 和 Aarch32/Aarch64 找到對應的指令，並說明其作用和限制
* 在 x86_64 中logic_shift（或稱 unsigned shift ）
* 採用 AT&T syntax : shr src, dest
* 採用 Intel syntax : shr dest, src
* 上述兩者指令作用一致，即是把 dest 之值右移 src 個 bits ，而因為右移被移出暫存器的（移到 last bit之後）bit，會被存入 x86 中的 FLAG 暫存器裡面的 CF（Carry FLAG） 欄位。
* CF（Carry FLAG） 欄位 在x86架構裡面，屬於 Status 狀態的表明，佔用一個 bit 的大小，用以指名有無 Carry 的發生，例如加法/減法中涉及超出一個word能表示的大小時，會把進位的 carry 放置在CF欄位，或者左移/右移時bit因為移動被移出暫存器時，就會被放置在CF欄位中。
* 關於 AT&T syntax 和 Intel syntax之差異可參考：http://web.mit.edu/rhel-doc/3/rhel-as-en-3/i386-syntax.html
* 概念相同的還有 shift left
* 採用 AT&T syntax : shl src, dest
* 採用 Intel syntax : shl dest, src
舉例：
```
movw $ff00,%ax # ax=1111.1111.0000.0000 (0xff00, unsigned 65280, signed -256)
shrw $3,%ax # ax=0001.1111.1110.0000 (0x1fe0, signed and unsigned 8160)
shlw $1,%ax #ax=0011.1111.1100.0000 (0x3fc0, signed and unsigned 16320)
```
除了上例所述的 Logic Shift 等進行左移/右移的指令，x86 也支援 Arithmetic Shift 以及 Rotate Instructions：
* Arithmetic Shift Right
* 採用 AT&T syntax : sar src, dest
* 採用 Intel syntax : sar dest, src
* Arithmetic Shift Left
* 採用 AT&T syntax : sal src, dest
* 採用 Intel syntax : sal dest, src
* Rotate Shift Right
* 採用 AT&T syntax : ror src, dest
* 採用 Intel syntax : ror dest, src
* Rotate Shift Left
* 採用 AT&T syntax : rol src, dest
* 採用 Intel syntax : rol dest, src
* 還有涉及上述所提到的 CF 欄位的 Rotate 指令，會將 CF 欄位的值視作 extended-bit 一同考慮在 rotate 的範圍內。
* Rotate Shift Right With Carry
* 採用 AT&T syntax : rcr src, dest
* 採用 Intel syntax : rcr dest, src
* Rotate Shift Left With Carry
* 採用 AT&T syntax : rcl src, dest
* 採用 Intel syntax : rcl dest, src
# 第 4 週測驗題1
分析以下程式碼，推敲 `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的用途：
* 傳入指標的指標 ：**start 指向 linked-list 的開始。
* 若 （*start）為 null ，代表 linked-list 為空，為其配置第一個 node，接著因為這是一個 doubly-circular-linked-list 故將 prev 和 next 都指向自己 ，最後將 *start 指向該 node，之後返回。
* 若 （*start）不為 null，代表 linked-list 不為空，透過 malloc 產生新的 node，將其接在最後一個 node 之後 (透過last 指標) (安插在結尾) ，並做
(1) 將 last 指標指向自己。
(2) new-node 的 next 指標指向 *start 所指向的 node
(3) new-node 的 prev 指標指向前一個 node (last->prev)
(4) 前一個 node 的next 指標指向 new-node
(5) *start 的 prev指標指向 new-node
根據上述討論
:::success
FuncA的作用為：（e) 建立新節點，內容是 value ，並安插在結尾 。
:::
* FuncB的用途：
* 傳入指標的指標 ：**start 指向 linked-list 的開始。
* 注意到：在使用 FuncB 之前，得確保 linked-list 已經被初始化過了，否則由於沒有在 FuncB 中檢查傳入的 *start 是否為 NULL ， 倘若 *start 為 NULL ， struct node *last = (*start)->prev; 會造成 Segmentation fault。
* FuncB 首先透過 malloc 配置一個 new-node，在 *start 前插入 new-node ，接著調整一些指標的指向使其符合 doubly-circular-linked-list ，最後將 *start 指標指向 new-node。
根據上述討論
:::success
FuncB的作用為： (d) 建立新節點，內容是 value ，並安插在開頭。
:::
* FuncC的用途：
* 傳入指標的指標 ：**start 指向 linked-list 的開始，以及用來建立 new-node 的 value1 以及用以尋找的 value2。
* 先透過 malloc 配置 new-node 並且設定其 data欄位之值為 value1
* 接著在 linked-list 由 *start 開始由後尋找有無 node 其 data 欄位之值為 value2，將其 new-node 插入在其之後，值得注意的是 FuncC 並沒有撰寫如果已經走訪所有 linked-list 仍然沒有找到 value2 的情況，在這種前提下，會造成無窮迴圈
根據上述討論
:::success
FuncC的作用為： (e) 找到節點內容為 value2 的節點，並在之後插入新節點，內容為 value1
:::
* display 的用途：
* 傳入指標的指標 ：**start 指向 linked-list 的開始
* 先從 *start 開始不斷走訪 linked-list 直到下一個 node 為 last，並在沿途印出所有 node 的 data 值， 接著印出 last node 之 data，簡單來說就是由起點開始由前往後印出所有 node 的 data。
* 接著由 *last 開始往前拜訪 linked-list，由後往前印出所有 linked-list 的 data。
* 解讀 main：
* 根據上述的討論 在 main 中 display(start) 之前，linked-list 如下：
[48] $\Leftrightarrow$ [51] $\Leftrightarrow$ [63] $\Leftrightarrow$ [72]$\Leftrightarrow$[86]
$\uparrow*Start$
印出後：
:::success
Traverse in forward direction 48 51 63 72 86
traverse in reverse direction 86 72 63 51 48
:::
# 第 4 週測驗題2
* node_new 的用途：傳入 int data ，透過 malloc 建立一個 new-node 將其 data 欄位之值設為 data，傳回 new-node 。
* FuncX 的用途:
* 首先 c語言只接受 call-by-reference ,在呼叫 funtion 時直接傳入 &count 是不會真正改變 count （count 為 int）的值的，改變的只是 count 的副本，故 count 仍為 0。
* 首先觀察 for-loop 的終止條件 : node != NULL && node!=head
* 由 node!=head 可看出當走訪 linked-list 走回 head 迴圈終止，且 return (head-head)=0 ，這代表 FuncX 可用以判斷是否為 circular-linked-list ，若為 circular-linked-list 則回傳0。
* 接著 若 node==NULL ，迴圈也會終止，這代表已經走到 singly-linked-list的終點 ，傳回非零值（因為node此時為NULL，代表著一段尚未定義的位址，return node-head 只能說是非零值）
:::success
FuncX 的作用是 (涵蓋程式執行行為的正確描述最多者) ：（e） 判斷是否為 circular linked list，若為 circular 則回傳 0，其他非零值
:::
* 觀察main :
* 在 printf("K1 >> %s\n", FuncX(head, &count) ? "Yes" : "No"); 之前的 linked-list 為：
[0] $\rightarrow$ [1] $\rightarrow$ [2] $\rightarrow$ [3] $\rightarrow$ [4] $\rightarrow$NULL
則 FuncX(head,&count) 傳回非零值。
:::success
K1 >> 後面接的輸出為何 : YES
:::
* 接著執行完 head->next->next->next->next = head; 會使得該 linked-list 變成環狀串列。
:::success
K2 >> 後面接的輸出為何 : NO
:::
* 執行完 head->next->next->next->next->next = head->next; list不變，仍為環狀串列。
:::success
K3 >> 後面接的輸出為何 : YES
:::
* 執行完 head->next = head->next->next->next->next->next->next->next->next; 變為 head指向自己的環狀串列。
且此時 linked-list 為
:::success
K4 >> 後面接的輸出為何 : NO
:::
* printf("K5 >> %d\n", head->next->data); 會印出 head 之 data值。
:::success
K5 >> 後面接的輸出為何 : 0
:::
而 printf("count >> %d\n", count);由前面所提的，只會印出 0 。
:::success
count >> 後面接的輸出為何 ： 0
:::
# 第 5 週測驗題 （上-1）
## 程式碼分析
考慮以下程式碼，推敲其作用 (選出最符合行為的描述)
```clike
uint8_t Func32(uint32_t x) {
return x ? Func32(x >> 1) - 1 : 32;
}
```
* 觀察Func32:
* 當 x = 0 傳回 32
* 當 x=0x00000001 傳回 32-1=31
* 當 x=0x00000003 傳回 31-1=30
* 當 x=0x00000007 傳回 30-1=29
* 以此類推，這個函式用以計算從高位到低位中，直到遇到第一個 1 之前，共有多少個 0 ，簡單來說就是 count-leading-zero。
:::success
Func32 = ?(c) 計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 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;
}
```
* 觀察FuncI:
* 當 x=0 ，代表 leading-zero 等於 32，回傳 32。
* 因為 funtion 的功能是 clz，為此我們盡可能去尋找高位元處是否有 bit 為 1 ，再將 32 減去 該leading-one 之 bit 位數，就是 leading-zero 的個數。
* 接著檢查 x 的前 16 bits，若前 16-bits 皆為 0，代表 leading-zero 至少為 16 ，將 n+16，並把前 16-bits 清除。
* 接著檢查 x 的前 8 個bits(透過將 x 右移 24 個 bits)，若前 8-bits 皆為 0，代表 leading-zero 至少為 8 ，將 n+8，並把前 8-bits 清除。
* 這麼做的原因是，若上一個 if (!(x >> 16)) 有發生，則代表前 16-bits 都為 0，我們可以繼續接著檢查，尚未檢查到的後 16-bits 有多少 leading-zero。
* 若上一個 if (!(x >> 16)) 沒有發生，則代表前 16-bits 不全 0，代表 leading-zero 的個數只要檢查這 16-bits 看看第一個 leading-one 發生在哪個 bit 位數就可以了，再將 32 減去 該 leading-one 之 bit 位數，就是 leading-zero 的個數。
* 只要上述的 if（x>>M）敘述，有一個不成立，那麼代表 leading-one，就在前 (32-M) bits 中，而後面的 bits 對我們來說可以視為 dont-care-term。
由上所述：
:::success
M1=24=0x18 , M2=24+4=28=0X1C ,M3 = 28+2 =30 =0X1E
:::
# 第 5 週測驗題 （上-2）
## 程式碼分析
```clike=
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;
}
```
* Func64: 延續之前的 Func32 ， 檢查前 32-bits (hi) 之 leading-zero，若 hi 全為 0 , 則檢查後 32-bit (lo) 並把 Func32(lo) + 32 ， 如此一來可以檢查出 64-bits 數中的 leading-zero 數目 。
:::success
Func64 的作用為？(c) 計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 64
:::
* do_udiv32 : 其作用是做 32-bits 的除法運算， 首先利用 count-leading-zero 來將除數（透過左移 mask ）對齊被除數，
接著調整 mask = 1 << mask ， 這是用來作為除法後的商數。
而何時會停止這個 while loop，就常理上來說：
(1) 被除數為0 (dividend==0)
(2) 被除數小於除數時 ， 但是在這裡因為除數已經透過 mask 左移過了， 在每個回合檢查 (mask >>= 1 ) ， 同時檢查 mask 是否為 0 ， 當 mask 為 0 的時候，代表商數已經無法更新了，也代表被除數小於除數。
:::success
P1 應該為？ (b) mask >>= 1
:::
```clike=
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：延續了 32-bits 的無號數除法的想法，將其擴充為 64-bits 的版本，並且為其加入了許多除錯條件 (例如除以 0 ) ，並且為了加速運算，當偵測除數和被除數若其實只有低位 32-bits 不為0，而高位都為 0 時，可直接進行 32-bits 除法。
* mask 用以將除數對齊被除數（在被除數>除數的前提下），而 bits 變數其目的用以紀錄除法的最長可能的回合數，且 bits 每回合遞減，當 bits 為 0 時，代表所有回合已經結束
:::success
P2 應該為？ (c) bits–-
:::
```clike=
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;
}
```
* main分析：
* 利用 char digitbuff[20] 存放結果，先利用利用 *pos = digitbuff + sizeof(digitbuff) 來設定 pos 指向 digitbuff 的末端。
* 接著在第一個 while-loop 裡面進行 一直到 v.qword (也就是被除數)，的高位 32-bits 為 0 才終止，並將餘數（d.r.dwords.low ）記錄在 digitbuff 中，透過 *--pos = d.r.dwords.low + P3; ，將餘數由右到左輸出。而因為 pos 代表指向 char 的指標，而 d.r.dwords.low 為 unsigned，得將 unsigned 加上 '0' 的 ASCII 碼 （也就是 0x30) 才會正確將其設定成 char 來輸出。
* 而 P5 和 P3 目的都一樣 。
:::success
P3 = ? 0x30
P5 = ? 0x30
:::
* 在下一個 do-while loop 中利用 nv.dwords.low = v.dwords.low / P4; 來輸出 10 進位數字 ，故 P4 = 10
:::success
P4 = 10
:::
# 第 5 週測驗題 (中)
## 程式碼分析
已知在 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; }
```
* 解釋： puts((char *) &(double []){ 3823806048287157.0, 96 });
* &(double []) : 對 double[0] 也就是 3823806048287157.0 取址，得到 double*
* (char *) 代表轉換成字元形態的指標
* 也就是將 double* 轉型（cast） 成 char*，並透過 puts()印出來。
* 3823806048287157.0 起初資料型態為 double 佔了 64-bits，而其 IEEE-754表示法為
* 01000011 :C (可參考ASCII)
* 00101011 :+
* 00101011 :+
* 01110110 :v
* 01110010 :r
* 01100101 :e
* 01110011 :s
* 01101010 :j
* 但 C++versj 是在 Big-endian 的狀況，在 x86_64 上為 little-endian，故印出 jserv++C
* 解釋：void gen():
* 將 m[0]（double） 乘以 $2^{96}$ 後將 double* 轉型（cast） 成 char*，並透過 puts() 印出來。
* 乘以 $2^{96}$ 對 double 型別來說，相當於在其 exponent 欄位加上 96，所以只需要考慮 $(10000110010)_2+96$，等於$(10010010010)_2$，而加上 96 之後，其 IEEE-754 表示法變為：
* 01001001 :I (可參考ASCII)
* 00101011 :+
* 00101011 :+
* 01110110 :v
* 01110010 :r
* 01100101 :e
* 01110011 :s
* 01101010 :j
* 也就是 jserv++I
:::success
(i) jserv++I
:::
## 延伸題目
1. 修改程式，允許輸出你的 GitHub 帳號名稱
2. 承上，修改 gen() 函式，透過特定的轉換，讓 m[] 的內容變為你的英文姓氏 (last name)，程式碼應該越短越好，而且不得以字串的形式存在於原始程式碼
3. 如果在 big-endian 的環境中，要達到一樣的效果，我們該如何改寫？
1.
* 我的 GitHub 帳號: workat60474 ，將其拆成： workat60 以及 474 兩個部分印出。
* workat60 先將其轉為 littel-endian 後的輸出為 06takrow 其 Binary 表示法為 ： 00110000 00110110 01110100 01100001 01101011 01110010 01101111 01110111 ， 轉換成 Decimal 為： 1.93921809812580006340396732583E-76
* 474 先將其轉為 littel-endian 後的輸出為 474 其 Binary 表示法為 ： 00100000 00100000 00100000 00100000
00100000 00110100 00110111 00110100 ， 轉換成 Decimal 為： 6.01347001874342607634226915913E-154
```clike=
#include <stdio.h>
int main() {
printf("%s",(char *) &(double []){
1.93921809812580006340396732583E-76
, 96 });
puts((char *) &(double []){
6.01347001874342607634226915913E-154
, 96 });
}
```
2.修改 gen() 函式，透過特定的轉換，讓 m[] 的內容變為輸出 Huang:
```clike=
#include <stdio.h>
double m[] = {
6.01387576505380499033950727405E-154, 0 };
void gen() {
while (m[1]--) {
m[0] *= 2;
}
puts((char *) m);
}
int main() { gen(); return 0; }
```
3. 如果在 big-endian 的環境中，要達到一樣的效果，我們該如何改寫？
* 改寫程式，將欲輸出的字串轉為 big-endian 的 encoding 方式，這是最直觀的做法 。
* 在不更改程式碼的前提下，撰寫 Convert "Little-Endian" to "Big-Endian" 的函式，也是可行的做法：
* 自己撰寫一個：
```clike=
static void Little_to_Big_swap(void *v)
{
char in[8], out[8];
memcpy(in, v, 8);
out[0] = in[7];
out[1] = in[6];
out[2] = in[5];
out[3] = in[4];
out[4] = in[3];
out[5] = in[2];
out[6] = in[1];
out[7] = in[0];
memcpy(v, out, 8);
}
```
# 第 5 週測驗題 (下)
考慮某款 MIPS 實作，其 data path 如下:
上圖紅色的 `1`, `2`, `3` 對 MIPS 做了對應的修改，請考慮以下狀況，分別解釋對應的程式碼是否能運作。
1.首先探討 "Stuck at 0 left of cut "
阻斷了 "write-back " 信號傳回Registers File，會造成任何需要將結果寫回暫存器的指令無法正常運作。
:::success
lw $s1, 0($s2)=> 無法將結果寫回 $s1 ，無法正常運作
add $s1,$2,$3=> 無法將結果寫回 $s1 ，無法正常運作
:::
2. 探討 "Cut here"
阻斷了透過 Forwarding 機制，預先將結果從 MeM-Stage寫回 Rs 暫存器的可能。
:::success
add $s1, $s1, $s1 ＃兩指令之間為 WAW (Write after write ) ，這並不會需要做 Forwarding ， 結果仍然可以正常運作
add $s1, $t0, $t1
:::
3.探討 "Cut here"
阻斷了 "shift left 2" 這個 unit，這會造成採取
(1)Base or displacement addressing (如 lw,sw)
(2)PC-relative addressing (如：beq ,bne)
等採取上述定址模式的指令無法正常運作。
而 j, jal , jr 等指令採取 Pseudodirect addressing ，其跳躍目的位址為指令的後 26 位元和 Program-counter 高位（前 4 bits）結合而成，不涉及需要 shift 2 的運作，仍可正常運作。
由上述討論：
:::success
Q31:
cmp:
xor $t1, $s2, $s1
slt $t2, $zero, $t1
sll $t2, 2
add $ra, $ra, $t2
jr $ra #jr仍可正常運作
entry:
addi $s2, $zero, 2
addi $s1, $zero, 2
jal cmp #jal仍可正常運作
j exit #j仍可正常運作
故以上指令皆運作正確
Q32:
addi $s2, $zero, 2
addi $s1, $zero, 2
beq $s2, $s1, exit #beq無法正常運作
故以上指令無法運作正確
:::
Google Drive
Gist
Clipboard
Sign in with Wallet
