# 2019q3 Homework1 (review) contribured by `<` [Ting199708](https://github.com/Ting199708) `>` --- ## 第一周測驗1 考慮以下 C 程式的 align4 巨集的作用是，針對 4-byte alignment，找到給定地址的 round up alignment address。 ### 程式目的 * 對齊資料的記憶體位址 ### 題目程式碼 ``` c #include <stdio.h> #define align4(x) (((x) + K) & (-4)) int main(void) { int p = 0x1997; printf("align4(p) is %08x\n", align4(p)); return 0; } ``` ### Why we need Data Alignment * 早期電腦記憶體只能以word為單位進行存取 * 電腦的記憶體通常設計成以word-sized來存取最有效率，而現代的電腦系統word通常為4 bytes or 8 bytes ### 分析與想法 了解題目後我先將p=0x1997代入觀察 ```c align(p) = (0x1997 + K) & (-4) = 0x1998 ``` 且依題意，p=0x1995, 0x1996, 0x1997, 0x1998，align(p)均等於0x1998，將其轉換為二進位觀察，分析如下： ```c 0x1995: (0001 1001 1001 0101 + K) & 1111 1111 1111 1100 = 0001 1001 1001 1000 0x1996: (0001 1001 1001 0110 + K) & 1111 1111 1111 1100 = 0001 1001 1001 1000 0x1997: (0001 1001 1001 0111 + K) & 1111 1111 1111 1100 = 0001 1001 1001 1000 0x1998: (0001 1001 1001 1000 + K) & 1111 1111 1111 1100 = 0001 1001 1001 1000 ``` 經過二進位觀察後，發現最後4 bit需在加上數值K後變成10xx 所以，K=3，答案為(g) ### 延伸題目 Survey Linux Kernel Document後，我找到了以下function有用到aligment的概念 ```c void blk_quene_aligment_offset(struct request_quene *q, unsigned int offset) Parameters: stuct request_quene *q: the request qune for the device unsigned int offset: alignment offset in bytes ``` 核心文件對此function解釋如下： > Some devices are naturally misaligned to compensate for things like the legacy DOS partition table 63-sector offset. Low-level drivers should call this function for devices whose first sector is not naturally aligned. 程式原始碼(/block/blk-setting.c, line 375)： ```c void blk_quene_alignment_offset(struct request_quene *q, unsigned int offset) { q->limits.alignment_offset = offset & (q->limits.physiccal_block_size - 1); q->limits.misaligned = 0; } ``` 應用範圍(/drivers/scsi/sd.c, line 2333)： ```c alignment = ((buffer[14] & 0x3f) << 8 | buffer[15]) * sector_size blk_quene_alignment_offset(sdp->request_quene, alignment); ``` 由此可見，blk_quene_alignment_offset可根據使用的情況來對request_quene的offset進行alignment。 ### Reference * 關於記憶體對齊: http://opass.logdown.com/posts/743054-about-memory-alignment * The Linux Kernel: https://www.kernel.org/doc/html/latest/core-api/kernel-api.html?highlight=alignment#c.blk_queue_alignment_offset * Linux Source Code: https://elixir.bootlin.com/linux/latest/source --- ## 第一周測驗3 考慮以下C程式碼： ```c #include <stdbool.h> bool func(unsigned int x) { return x && ((x & (~x + 1)) == x); } ``` 可改寫為以下等價程式碼： ```c bool func(unsigned int x) { unsigned int unknown = 0; while (x && unknow <= 1) { if ((x & Z) == 1) unknown++; x >>= 1; } return (unknown == 1); } ``` ### 分析與想法 首先我看到了原始C程式碼我對於將unsigned int x做&&運算有點疑問，因此我實際實驗了一次。 再來我將X=0~8代入程式進行分析，結果如下 ```c x = 0000 -> ((x & (~x + 1))) = 0000 x = 0001 -> ((x & (~x + 1))) = 0001 x = 0010 -> ((x & (~x + 1))) = 0010 x = 0011 -> ((x & (~x + 1))) = 0001 x = 0100 -> ((x & (~x + 1))) = 0100 x = 0101 -> ((x & (~x + 1))) = 0001 x = 0110 -> ((x & (~x + 1))) = 0010 x = 0111 -> ((x & (~x + 1))) = 0001 x = 1000 -> ((x & (~x + 1))) = 1000 ``` 由此可知，當x=0時func輸出為false，x!=0時，因為x在&&運算時視為True，所以func(x)結果為： x==(x & (~x + 1))，即x=2的次冪時，結果為True 再來，分析下方等價程式碼，x=0時，其輸出為False，x!=0時，則需檢測x內所含的1的數量 因此，透過Z=0001和x做&運算，再將x向右移1 bit，即可計算x內1的bit數，若僅有1個"1"，則unknow=1，回傳True；反之，若"1"的數量大於1個，則unknow=2，跳出迴圈，回傳False。 故，此題解答為(e) 1 ### 延伸題目 透過bitwise運算計算兩數字中的最大或最小值 #### 程式碼 ```cpp int find_min(int x, int y) { return y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); } int find_max(int x, int y) { return x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); } ``` #### 分析 假設(x,y)=(14,24) and (24,14) * 當(x,y)=(14,24) ``` (x-y) >> (sizeof(int) * CHAR_BIT -1) = -1 所以(x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)) = (x - y) = -10 find_min(x, y) = y + (-10) = 14 find_max(x, y) = x - (-10) = 24 ``` * 當(x,y)=(24,14) ``` (x-y) >> (sizeof(int) * CHAR_BIT -1) = 0 所以(x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)) = 0 find_min(x, y) = y + 0 = 14 find_max(x, y) = x - 0 = 24 ``` 可見此程式的關鍵為透過(x-y)再右移31 bits，取得sing bit來達成判斷其大小的目的 ### Reference * Bit Twiddling Hacks: https://graphics.stanford.edu/~seander/bithacks.html --- ## 課程說明ppt第15頁 分析程式，並考慮abs(-2147483648)所得到的結果 ### 題目程式碼 ```cpp #include <stdint.h> int32_t abs(int32_t x) { int32_t mask = (x >> 31); return (x + mask) ^ mask; } ``` ### 電腦的2補數表示法 二補數是一種用二進位表示有號數的方法，以下用一簡單範例來說明 ``` 24 -> 0000 0000 0000 0000 0000 0000 0001 1000 -24 -> 1111 1111 1111 1111 1111 1111 1110 1000 ``` 由上方範例可發現，只要將24的每個bit反向再加一，即可得到其負數(-24) 的二進位表示 ### 分析與想法 首先先來分析此程式如何運作，由於電腦在儲存負數時是以二補數方式表示，因此，abs程式只要將負數再做一次二補數運算即可得到abs運算後的數值。 * X為正數 ``` 首先分析X是正數的情況，因為正數的sign-bit為0，因此mask = (x >> 31)會等於0。 而因為mask=0，所以return value會等於x，也驗證了正數做abs運算後數值不變 ``` * X是負數 ``` 再來，若X為負數，因為負數的sign-bit為1，因此mask = (x >> 31)會等於 -1(1111 1111 1111 1111 1111 1111 1111 1111) 將此mask與X相加可以發現變為abs(X)的反向，又任何數和1做xor運算等效為not， 因此(x + mask) ^ mask即會輸出X的abs運算結果。 ``` ### 關於abs(-2147483648)輸出結果 經過實際測試，abs(-2147483648)的輸出結果為-2147483648，很明顯的，此程式對於輸入的數字有所限制。 實際執行程式碼發現輸出數值錯誤： :::success 實驗結果： Please input the x: -2147483648 abs(-2147483648) = -2147483648 ::: :::danger 文字訊息==不要==用圖片來展現 :notes: jserv ::: 分析程式原始碼，發現int32_t在儲存有號整數時，其範圍為-2147483647~2147483647，因此-2147483648儲存進去時會發生overflow的現象導致數值不正確 當 x=-2147483647及 x=2147483647時，程式均可正常運作，可見上述分析正確： :::success 實驗結果： Please input the x: -2147483647 abs(-2147483647) = 2147483647 ::: :::success 實驗結果： Please input the x: 2147483647 abs(-2147483647) = 2147483647 ::: :::danger 文字訊息==不要==用圖片來展現 :notes: jserv ::: ### 解決方法 因此，若要解決此問題，可將程式修改如下： ```c #include <stdint.h> int64_t abs(int64_t x) { int64_t mask = (x >> 63); return (x + mask) ^ mask; } ``` 執行結果： :::success 實驗結果： Please input the x: -2147483648 abs(-2147483648) = 2147483648 ::: 當然，將此程式修改後X仍有限制，其範圍為 $-2^{63}$ ~ $2^{63}$，不過對大多數情況皆已可適用。 ### Reference * [Wikipedia: Two's complement](https://en.wikipedia.org/wiki/Two%27s_complement) :::danger 避免引用中文 Wikipedia 詞目，因為後者可能會跟英文詞目內容不同步 :notes: jserv :::