# Data lab 紀錄
contributed by < `justapig9020` >
###### tags: `CSAPP`
## Link
[data lab](https://github.com/justapig9020/csapp-labs/tree/main/data/datalab-handout)
## Lab 說明
Data lab 要求我們實做數個簡單的函數，然而在實做上包含諸多限制：
1. 只能宣告 int / long 型態的區域變數
2. 不能使用全域變數
3. 定義的常數必須在 [0, 0xff] 區間內
4. 不得轉型為 int / long 以外的型態
且以下的操作是完全禁止的：
1. 使用 if / while / for 等控制描述。
2. 定義或使用巨集( macro )
3. 定義額外的函數
4. 呼叫任何函數
5. 使用每個小題允許範圍外的運算子
6. 使用 int / long 以外的型態，包含 struct / enum / union 等。
## Lab 實做
### copyLSB
```c=
/*
* copyLSB - set all bits of result to least significant bit of x
* Examples:
* copyLSB(5L) = 0xFFFFFFFFFFFFFFFFL,
* copyLSB(6L) = 0x0000000000000000L
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
long copyLSB(long x) {
x <<= 63;
x >>= 63;
return x;
}
```
由於在 C 語言中，決定使用邏輯右移或是算術右移的條件為該型態是否為 signed 。因此，signed 的 long 在右移上會使用算術位移。
因此，我們首先只需要將 `x` 左移，使得原本的 `LSB` 變為 `MSB` ，再右移即可將其填滿整個變數。
### dividePower2
```c=
/*
* dividePower2 - Compute x/(2^n), for 0 <= n <= 62
* Round toward zero
* Examples: dividePower2(15L,1L) = 7L, dividePower2(-33L,4L) = -2L
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 2
*/
long dividePower2(long x, long n) {
long is_negative = !!(x >> 63);
long round = (is_negative << n) + (~is_negative) + 1;
x += round;
return x >> n;
}
```
$\frac{x}{2 ^ n}$ 可以被為寫成為運算 $x >> n$ 。
然而題目另外要求必須向 0 做捨入，也就是當結果為鄭數時做無條件捨去，為負數時則為無條件進位。
此一要求在 x 為負數時就會出現問題，考慮負數時的算術右移，右移後小數點右方的數字會被無條件捨去，因此即便在負數時，算術右移的捨入依然為無條件捨去。
為了彌補損失，當 x 為負數時，我們需要在右移前先補償。規則為，當右移將被抹去的位數不全為零時，需要補償 +1 。因此在右移 n bit 前，我們先行加上 n bit 的 1 ，如此一來，唯有當低 n bits 皆為零時不會進位，反之會進位至第 n+1 bit ，使該位 +1 (n + 1 位為等等右移後的 LSB )。
回到計算本身，首先我們透過算術右移，提取 x 的 MSB ，若 x 為負數時， `is_nagative` 為 1 反之為 0 。
接著我們來製作捨入的素材 `round` 。
要製作 n bits 的連續的 1 方法為， 首先將 1 左移 n bits ，再將其 -1 。這邊會遇到的問題有 2:
1. 我們只需要在 `is_nagative` 為 1 時產生 round
2. 由於無法使用減號，因此需要自行生成 -1
由於第一條要求，我們只要在所有需要 1 的部份皆使用 `is_nagative` 代替，即可確保在 x 為正時所生成的 `round` 為 0 。
此外，我們可以透過 2 得補數的規則來生成 -1 。在 `is_nagative` 為 1 時透過補數產生 -1 來完成 `round` 。若 `is_nagative` 為 0 時，由於 -0 = 0 ，因此結果上 `round` 依舊為 0 。
最後我們只需要先將 `round` 與 x 相加，先完成捨入，再進行右移完成除法。
### distinctNegation
```c=
/*
* distinctNegation - returns 1 if x != -x.
* and 0 otherwise
* Legal ops: ! ~ & ^ | +
* Max ops: 5
* Rating: 2
*/
long distinctNegation(long x) {
long neg = ~x + 1;
return !!(x ^ neg);
}
```
頗為直覺的一題。
透過補數規則算出 -x , `neg` , 並透過 xor 檢測 x 與 neg 是否相等。因為，唯有兩數相等時 xor 的結果為 0 。最後在透過兩次 logic not 來將數值收斂至 0 / 1 。
### anyEvenBit
```c=
/*
* anyEvenBit - return 1 if any even-numbered bit in word set to 1
* where bits are numbered from 0 (least significant) to 63 (most significant)
* Examples anyEvenBit(0xAL) = 0L, anyEvenBit(0xEL) = 1L
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 14
* Rating: 2
*/
long anyEvenBit(long x) {
long mask = 0x55;
mask |= mask << 8;
mask |= mask << 16;
mask |= mask << 32;
return (long)(!!(x & mask));
}
```
依舊是直覺的一題。
透過建構一個在 even bits 為 1 的 `mask` 來檢測 x 在這些 bits 是否為 1 。只考慮單一 byte 的話， mask 的數值為 0b1010 = 0x55 ，因此完整的 `mask` 的數值為 0x5555555555555555 。
稍微需要花點心思的部份為 `mask` 的建制 ，由於規定不能定義大於 0xff 的數字，因此需要透過不斷的位移與或運算來建構 `mask` 。
### isLessOrEqual
```c=
/*
* isLessOrEqual - if x <= y then return 1, else return 0
* Example: isLessOrEqual(4L,5L) = 1L.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 24
* Rating: 3
*/
long isLessOrEqual(long x, long y) {
// If x y have same sign, x ^ y's MSB is 0. 1 otherwise
long sign = !((x ^ y) >> 63);
// If x y have different sign and x is negative. Than x <= y always true
long diff = (x >> 63) & (!sign);
/*
* If x y have same sign, -x and y have different sign. Therefore, y - x
* never overflow. 0 <= y - x, if x is TMIN, -x is also TMIN. Since x, y
* have same sign. y is negative in this case, therefore y + x = y + TMIN
* always lead to a overflow and caused a positive number and always holds 0
* <= y - x
*/
long neg_x = (~x) + 1;
long same = (!((y + neg_x) >> 63)) & sign;
return same | diff;
}
```
若是從純數字上來解釋的話十分直覺。透過簡單的移位即可得到 $0 <= y - x$ ，然而這邊會遭遇到 overflow 的問題。由於 overflow 只會發生在 x, y 不同號的狀況 ( y - x = y + (-x)) ，因此可以將問題分為兩個部份考慮。
1. x, y 同號
2. x, y 不同號
透過 xor x, y 的 MSB 我們可以得出兩數是否同號。若 xor 的結果為 1 則兩者同號，反之則異號。
因此， `sign` 在兩者同號時為 1 。
若 x, y 不同號時，若透過 $0 \le y - x$ 的邏輯去判斷，可能會遭遇 overflow 的問題。然而針對此問題，其實我們只要判斷 x, y 的正負就可以得到答案。邏輯為：當x, y 異號，且 x 為負，則 $x \le y$ (因為 x, y 不同號，因此 y 必定為正)。
透過將 x 的 MSB 右移來判斷 x 的正負，再透過 `!sign` 確保 x, y 異號。
若 x, y 同號時，由於 $y-x$ 不具 overflow 的風險，因此可以透過 $0 \le y-x$ 的邏輯來判斷正負。
這邊需要考慮的問題為： x, y 都有可能為 TMIN ( 0x8000000000000000 )，由於 -TMIN = TMIN ，因此，假設 x 為 TMIN 則 $y-x = y+x$ 。反之亦然。
分開討論 x, y 為 TMIN 的狀況可以發現：
- 若 x 為 TMIN 則 $x \le y$ 永遠為真。
- 若 y 為 TMIN 則 $x \le y$ 在多試情況為假，但當 x 也為 TMIN 時，該命題為真。
基於此討論，發現我應該傾向移動 x ，因為當其為 TMIN 時的狀況只有一種，我們不須額外多討論其他狀況。
思考當 x 為 TMIN 時的狀況，因為 x, y 同號，因此此時 y 必為負，由於在此狀況下 $y - x = y + x = y + TMIN$ ，因此結果為一負數加上 TMIN 。此運算必定會產生 overflow 並產生一個正數，結果剛好符合 $0 \le y - x$ 因此為真，又恰好與 x 為 TMIN 狀態相同。結論，當我們移動 x 時，無須額外考慮 x 為 TMIN 的狀況。
運算上，我們首先透過補數運算出 -x , `neg_x` , 再透過判斷 y + neg_x 的 MSB 來判斷結果是否滿足 $0 \le y - x$ 。最後也要透過 `sign` 確保兩者同號。
最後，只須將同號與異號的結果進行或運算，即可得出結果。
### replaceByte
```c=
/*
* replaceByte(x,n,c) - Replace byte n in x with c
* Bytes numbered from 0 (LSB) to 3 (MSB)
* Examples: replaceByte(0x12345678,1,0xab) = 0x1234ab78
* You can assume 0 <= n <= 7 and 0 <= c <= 255
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 10
* Rating: 3
*/
long replaceByte(long x, long n, long c) {
long shift = n << 3; // n * 8
x &= ~(0xFFL << shift);
x |= c << shift;
return x;
}
```
在嵌入式領域常見的操作，需要特別注意的是 n 的單位是 byte ，然而位移操作的單位是 bit ，因此在位移前，要先將 n << 3 (n * 8) 來完成單位的轉換。
接著，首先透過位移 0xff 的 mask 來將指定的 byte 清 0 ，最後再透過或運算將指定的 byte 填上對應的數值即可。
### conditional
```c=
/*
* conditional - same as x ? y : z
* Example: conditional(2,4L,5L) = 4L
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
long conditional(long x, long y, long z) {
long condition = !!x;
long mask = (condition << 63) >> 63;
return (y & mask) | (z & ~mask);
}
```
思路為：可以透過 0xffffffffffffffff 的 mask 與 y, z 做及運算來達成選擇的效果。因此只要在 x 不為零時造出 0xffffffffffffffff 的 mask ，反之則使 mask 為 0x0000000000000000 即可。
首先透過兩次 logic not 將 x 收斂至 0 / 1 (實際上一次即可)，並透過位移將 0 / 1 擴展至每一 bit 即可造出上述的 mask 。最後只須將 mask / ~mask 分別與 y, z 運算最後在將兩者或運算即可。
### bitMask
```c=
/*
* bitMask - Generate a mask consisting of all 1's
* between lowbit and highbit
* Examples: bitMask(5L,3L) = 0x38L
* Assume 0 <= lowbit < 64, and 0 <= highbit < 64
* If lowbit > highbit, then mask should be all 0's
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
long bitMask(long highbit, long lowbit) {
long neg1 = ~1L + 1;
long hi_mask = (((1L << highbit) + neg1) << 1) + 1;
long lo_mask = (1L << lowbit) + neg1;
return hi_mask & ~lo_mask;
}
```
我們需要製造兩個 mask ，一是從 highbit 到 LSB 這區間中全為 1 ，一是 lowbit 到 MSB 這區間全為 1 。最後只須將兩個 mask 進行及運算，取兩者交集，即可得出我們所須的 bitMask 。
如同前面所言，製造一串 1 最快的方法便是先將 1 左移後再 -1 。然而這邊會遇到一個問題，若 highbit 為 63 ，我們必須造出 63 - 0 bit 皆為 1 的 mask 。按照上面的方法，我們首先需要將 1 左移 64 再將其 -1 ，然而對一個 64 bit 的數字進行大於 63 的位移為未定義行為。為了解決這個問題，我們可以首先將其左移 63 bit ，透過 -1 將其變為除 MSB 外其他 bit 皆為 1 的 mask ，再將其左移一位並 + 1 補足缺少一的一次位移。
而 lowbit 的部份則直接位移即可。
### isPalindrome
```c=
/*
* isPalindrome - Return 1 if bit pattern in x is equal to its mirror image
* Example: isPalindrome(0x6F0F0123c480F0F6L) = 1L
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 70
* Rating: 4
*/
long isPalindrome(long x) {
// 0x00000000ffffffff
long mask = ~((1L << 63) >> 31);
long prefix = (x >> 32) & mask;
long postfix = x & mask;
long rev_mask = (0xff << 8) | 0xff;
// 0x0000ffff 0xffff0000
prefix = ((prefix & rev_mask) << 16) | ((prefix & (~rev_mask)) >> 16);
// 0x00ff00ff 0xff00ff00
rev_mask = (0xff << 16) | 0xff;
prefix = ((prefix & rev_mask) << 8) | ((prefix & (~rev_mask)) >> 8);
// 0x0f0f0f0f 0xf0f0f0f0
rev_mask = (0xf << 8) | 0xf;
rev_mask = (rev_mask << 16) | rev_mask;
prefix = ((prefix & rev_mask) << 4) | ((prefix & (~rev_mask)) >> 4);
// 0x33333333
rev_mask = (0x33 << 8) | 0x33;
rev_mask = (rev_mask << 16) | rev_mask;
prefix = ((prefix & rev_mask) << 2) | ((prefix & (~rev_mask)) >> 2);
// 0x55555555
rev_mask = (0x55 << 8) | 0x55;
rev_mask = (rev_mask << 16) | rev_mask;
prefix = ((prefix & rev_mask) << 1) | ((prefix & (~rev_mask)) >> 1);
return !(prefix ^ postfix);
}
```
核心概念將 64 bit 切割為 prefix / postfix 兩子位元串，並將 prefix 以 bit 為單位反轉後，判斷其是否與 postfix 相等。
為首先將 prefix 以 16 bit 為區間，將相鄰的兩 16 bit 區間兩兩互換。接著將區間減半，以 8 bit 為區間，同樣將相鄰的兩區間互換。依此類推，直到區間縮小至 1 bit 為止。這樣就可以將 prefix 以 bit 為單位反轉。
實行方法也十分簡單，只須製作對應區間長度的 mask 並透過及運算分別提相鄰的兩個區間，在透過位移來交換兩者的位置，最後再將他們透過或運算重新組合即可。
實際上，冗長的程式只是為了滿足題目對常數的要求，因此需要花費較多的操作在建構每一階段的 mask 上。
最後將反轉完的字串透過 xor 運算比較即可。
### trueFiveEighths
```c=
/*
* trueFiveEighths - multiplies by 5/8 rounding toward 0,
* avoiding errors due to overflow
* Examples:
* trueFiveEighths(11L) = 6L
* trueFiveEighths(-9L) = -5L
* trueFiveEighths(0x3000000000000000L) = 0x1E00000000000000L (no overflow)
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 4
*/
long trueFiveEighths(long x) {
/*
* For positive
* x * 5 / 8 = x * (4 + 1) / 8 = (x * 4 + x) / 8
* = x / 2 + x / 8
* (x / 2 - e1) + (x / 8 - e2), e1 + e2 may greater than 1
* e1 = 0.(x & 1), e2 = 0.(x & 0x7)
*/
long neg = !!(x >> 63);
long e1 = (x & 1L) << 2;
long e2 = (x & 7L);
long frac = e1 + e2;
long carry = frac >> 3;
long round = (!!(frac & 7)) & neg;
return (x >> 1) + (x >> 3) + carry + round;
}
```
首先，我們嘗試拆解算式 $x * \frac{5}{8} = x * \frac{4 + 1}{8} = \frac{x * 4}{8} + \frac{x}{8} = \frac{x}{2} + \frac{x}{8}$ 。
因此我們似乎只需要計算 $(x >> 1) + (x >> 3)$ 即可。
然而，在整數除法中，小數的部份會被無條件捨去。因此一旦 $\frac{x}{2}, \frac{x}{8}$ 的小數部份相加大於 1 時，計算的答案便會有誤差。因此，在位移前，需要先行檢查會被捨去的部份。需要的檢查有二。
1. 檢查分數負份相加是否會進位。
2. 檢查分數部份是否不為零。若不為零，且 x 為負數，則需要額外的進位。(因為規則為往 0 進行捨入)。
首先，我們提取 $\frac{x}{2}$ 與 $\frac{x}{8}$ 中會被捨去的部份，並對齊。
程式中的 `frac` 即為在運算後會被捨去的數字。由於有經過對齊，所以 `frac` 的小數點位於第 2, 3 bit 之間。因此，我們可以透過右移來將小數點歸位，並得出 `carry` ，也就是計算後由 $\frac{x}{2}, \frac{x}{8}$ 小數部份所組成的進位。
接著，來處裡負數時的進位問題。思路與 [dividePower2](#dividePower2) 類似，透過判斷低 3 位元是否不全為 0 來決定是否需要做進位。
最後只需要將除法的結果與 `carry` , `round` 相加即可得出正確的答案。
### logicalNeg
```c=
/*
* logicalNeg - implement the ! operator, using all of
* the legal operators except !
* Examples: logicalNeg(3L) = 0L, logicalNeg(0L) = 1L
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
long logicalNeg(long x) {
long tmin = 1L << 63;
x += tmin;
// abs
long mask = x >> 63;
x = (x ^ mask) + (mask & 1);
// Now x is negative only if x is originally 0
x >>= 63;
x = ~x;
x += 1;
return x;
}
```
題目的首要目標便是檢測 x 是否為零。這邊利用的技巧為：在二的補數中，只有 TMIN 在取絕對值後會為負數。
因此，首先我們將 x 加上 TMIN 。唯有當 x 原本為零時， x 此時會為 TMIN 。接著透過對 x 做絕對值運算，再判斷 x 是否為負數即可反推出 x 原本是否為零。
若 x 原本為零，則取完絕對值後， x 會為負數。因此在 x 右移 63 bit 後會為 0xffffffffffffffff (-1) ，否則此時 x 會為 0 。透過將 x += 1 ，即可將 x 變為符合題目要求的格式，當 x 原本為零時， !x 為一。反之， !x 為零。
Sign in with Wallet
Connect another wallet