2019q3 Homework1 (review)

contribured by < Ting199708 >

---

第一周測驗1

考慮以下 C 程式的 align4 巨集的作用是，針對 4-byte alignment，找到給定地址的 round up alignment address。

程式目的

• 對齊資料的記憶體位址

題目程式碼

#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代入觀察

align(p) = (0x1997 + K) & (-4) = 0x1998

且依題意，p=0x1995, 0x1996, 0x1997, 0x1998，align§均等於0x1998，將其轉換為二進位觀察，分析如下：

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的概念

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

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

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程式碼：

#include <stdbool.h>
bool func(unsigned int x) {
    return x && ((x & (~x + 1)) == x);
}

可改寫為以下等價程式碼：

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代入程式進行分析，結果如下

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運算計算兩數字中的最大或最小值

程式碼

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)所得到的結果

題目程式碼

#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，很明顯的，此程式對於輸入的數字有所限制。

實際執行程式碼發現輸出數值錯誤：

實驗結果：
Please input the x: -2147483648
abs(-2147483648) = -2147483648

文字訊息不要用圖片來展現

jserv

分析程式原始碼，發現int32_t在儲存有號整數時，其範圍為-2147483647~2147483647，因此-2147483648儲存進去時會發生overflow的現象導致數值不正確

當 x=-2147483647及 x=2147483647時，程式均可正常運作，可見上述分析正確：

實驗結果：
Please input the x: -2147483647
abs(-2147483647) = 2147483647

實驗結果：
Please input the x: 2147483647
abs(-2147483647) = 2147483647

文字訊息不要用圖片來展現

jserv

解決方法

因此，若要解決此問題，可將程式修改如下：

#include <stdint.h>
int64_t abs(int64_t x) {
    int64_t mask = (x >> 63);
    return (x + mask) ^ mask;
}

執行結果：

實驗結果：
Please input the x: -2147483648
abs(-2147483648) = 2147483648

當然，將此程式修改後X仍有限制，其範圍為

$-2^{63}$ ~

$2^{63}$，不過對大多數情況皆已可適用。

Reference

• Wikipedia: Two's complement

避免引用中文 Wikipedia 詞目，因為後者可能會跟英文詞目內容不同步

jserv