# 2019q3 Homework1 (review)
contributed by < `uccuser159` >
## 題目1
- [ ] 考慮以下 C 程式的 `align4` 巨集的作用是，針對 4-byte alignment，找到給定地址的 round up alignment address。
```cpp
#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;
}
```
預期程式輸出 `align4(p) is 00001998`
`K` = ?
---
### 思考
來看 `#define align4(x) (((x) + K) & (-4))`
* 與 (-4)=1100~2~ 做AND運算，是要抓出4的倍數：0x0000 . 0x0004 . 0x0008 ...
* 1~3 round up to 4
* 5~7 round up to 8
* 9~11 round up to 12
* ...以此類推
此處的`K`即是除以4的最大餘數。==將 `K` 加上去後可以讓 x 往上進位到該有的4的倍數同時不要讓要 x 超過4的下一個倍數==，所以 `K` 值應該為3。
Reference
* [Align macro](https://stackoverflow.com/questions/13122846/align-macro-kernel)
### 延伸問題
* Linux 核心原始程式碼 alignment 巨集
[原始程式碼](https://elixir.bootlin.com/linux/latest/source/include/linux/kernel.h#L33) ( line 33 ~ line 37 )：
```c
#define ALIGN(x, a) __ALIGN_KERNEL((x), (a))
#define ALIGN_DOWN(x, a) __ALIGN_KERNEL((x) - ((a) - 1), (a))
#define __ALIGN_MASK(x, mask) __ALIGN_KERNEL_MASK((x), (mask))
#define PTR_ALIGN(p, a) ((typeof(p))ALIGN((unsigned long)(p), (a)))
#define IS_ALIGNED(x, a) (((x) & ((typeof(x))(a) - 1)) == 0)
```
[__ALIGN_KERNEL & __ALIGN_KERNEL_MASK](https://elixir.bootlin.com/linux/latest/source/include/uapi/linux/kernel.h#L10) ( line 10 & line 11 )
```c
#define __ALIGN_KERNEL(x, a) __ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
#define __ALIGN_KERNEL_MASK(x, mask) (((x) + (mask)) & ~(mask))
```
[應用](https://elixir.bootlin.com/linux/latest/source/arch/arm/kernel/stacktrace.c#L35) ( line 35 )：
為確保堆疊的指標所指向的位址是正確的
```c=
int notrace unwind_frame(struct stackframe *frame)
{
unsigned long high, low;
unsigned long fp = frame->fp;
/* only go to a higher address on the stack */
low = frame->sp;
high = ALIGN(low, THREAD_SIZE);
/* check current frame pointer is within bounds */
if (fp < low + 12 || fp > high - 4)
return -EINVAL;
/* restore the registers from the stack frame */
frame->fp = *(unsigned long *)(fp - 12);
frame->sp = *(unsigned long *)(fp - 8);
frame->pc = *(unsigned long *)(fp - 4);
return 0;
}
```
* -[Linux kernel source code](https://elixir.bootlin.com/linux/latest/source)
:::danger
缺乏實際 Linux 核心原始程式碼及其「應用場景」的解說
:notes: jserv
:::
**為了提高存取效率，例如記憶體存取、分頁，需要將資料對齊到 2^N^ ( N 為非負整數 )**。
而編譯器在分配記憶體時，會按照宣告的型態去做對齊。
```cpp
#include <stdio.h>
#define ALIGN(x, a) __ALIGN_MASK(x, (typeof(x))(a) - 1)
#define __ALIGN_MASK(x, mask) (((x) + (mask)) & ~(mask))
int main() {
for (int i = 0; i < 16; i++)
printf("ALIGN(%d, 4): 0x%08x\n", i, ALIGN(i, 4));
return 0;
}
```
程式執行結果:
```shell
ALIGN(0, 4): 0x00000000
ALIGN(1, 4): 0x00000004
ALIGN(2, 4): 0x00000004
ALIGN(3, 4): 0x00000004
ALIGN(4, 4): 0x00000004
ALIGN(5, 4): 0x00000008
ALIGN(6, 4): 0x00000008
ALIGN(7, 4): 0x00000008
ALIGN(8, 4): 0x00000008
ALIGN(9, 4): 0x0000000c
ALIGN(10, 4): 0x0000000c
ALIGN(11, 4): 0x0000000c
ALIGN(12, 4): 0x0000000c
ALIGN(13, 4): 0x00000010
ALIGN(14, 4): 0x00000010
ALIGN(15, 4): 0x00000010
```
`typeof(x)` 表示取 `x` 的類型，此例的`ALIGN(x,a)`中 `x` 是 int ，則`typeof(x)`為 int ，故 ``(typeof(x))(a)-1`` ，表示把 a 轉化為 x 的類型，再減1，當作`mask`。以`ALIGN(1,4)`來說，`mask=0000...00011(32bits)`，`& ~(mask)`即是在做 round up 成4的倍數。
* [GCC Manual](https://gcc.gnu.org/onlinedocs/gcc-9.2.0/gcc.pdf) **6.1 Statements and Declarations in Expressions** 和 **[6.7] Referring to a Type with typeof** 提到：
>For example, the “maximum” function is commonly defined as a macro in standard C as follows:
>```
>#define max(a,b) ((a) > (b) ? (a) : (b))
>```
>But this definition computes either a or b **twice**, with bad results if the operand has side effects. In GNU C, if you know the type of the operands (here taken as int), you can avoid this problem by defining the macro as follows:
>```
>#define maxint(a,b) \
> ({int _a = (a), _b = (b); _a > _b ? _a : _b; })
>```
>Here is how the two together can be used to define a safe “maximum” macro which operates on any arithmetic type and evaluates each of its arguments exactly once:
>```
>#define max(a,b) \
>({
> typeof (a) _a = (a); \
> typeof (b) _b = (b); \
> _a > _b ? _a : _b;
>})
>```
* [GCC Manual](https://gcc.gnu.org/onlinedocs/gcc-9.2.0/gcc.pdf)
:::danger
TODO: `typeof` 是 GNU extension，找出 GCC Manual 對應描述並解說為何 巨集定義用得到此 extension
:notes: jserv
:::
Reference
* [ALIGN 含意](https://blog.csdn.net/reille/article/details/6329195)
* [Linux 設計 4-byte data 對齊](http://abcdxyzk.github.io/blog/2018/01/08/kernel-align/)
* [記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/BkuMDQ9K7)
---
## 題目2
- [ ] 考慮以下 C 程式碼:
```cpp
#include <stdbool.h>
bool func(unsigned int x) {
return x && ((x & (~x + 1)) == x);
}
```
可改寫為以下等價的程式碼:
```cpp
bool func(unsigned int x) {
unsigned int unknown = 0;
while (x && unknown <= 1) {
if ((x & Z) == 1)
unknown++;
x >>= 1;
}
return (unknown == 1);
}
```
請補完程式。
---
### 思考
* 考慮程式碼：
```cpp
#include <stdbool.h>
bool func(unsigned int x) {
return x && ((x & (~x + 1)) == x);
}
```
先將`func`函式的參數從1(0001~2~)代到8(1000~2~)：
:::danger
工程人員說話應該精確，英文用語怎麼寫，就用對應的中文陳述
:notes: jserv
:::
```c=
#include <stdio.h>
#include <stdbool.h>
bool func(unsigned int x) {
return x && ((x & (~x + 1)) == x);
}
int main(void) {
for (int i = 1; i <= 8; i++){ //try x from 0 to 8
printf("x=%d => Result:%d\n ", i, func_up(i));
}
}
```
執行結果:
```shell
x=1 => Result:1
x=2 => Result:1
x=3 => Result:0
x=4 => Result:1
x=5 => Result:0
x=6 => Result:0
x=7 => Result:0
x=8 => Result:1
```
由結果推論是在判斷一數字 x 是否為2的次方。
* `return x && ((x & (~x+1))==x)`
先來嘗試 ` x & (~x+1) `
x = 1 (0001~2~) :
```
0001
& 1111
-------
0001
```
x = 2 (0010~2~) :
```
0010
& 1110
-------
0010
```
x = 3 (0011~2~) :
```
0011
& 1101
-------
0001
```
x = 6 (0110~2~) :
```
0110
& 1010
-------
0010
```
x = 7 (0111~2~) :
```
0111
& 1001
-------
0001
```
x = 8 (1000~2~) :
```
1000
& 1000
-------
1000
```
發現` x & (~x+1) `的效果為==將數字最右邊 bit 的1保留，其餘 bit 為0==。
所以符合` x & (~x+1)==x `式子的數字 x 應該要是化成二進制時只有其中一個 bit 為1，即2的次方(2^n^) (例如: x=0100~2~ . 0010~2~ ...等等)。
而` x && (x & (~x+1)==x) `即是在 x=0 的狀況下回傳 False，將其狀況排除。
* 考慮等價的函式(判斷數字 x 是否為2的次冪)：
```cpp
bool func(unsigned int x) {
unsigned int unknown = 0;
while (x && unknown <= 1) {
if ((x & Z) == 1)
unknown++;
x >>= 1;
}
return (unknown == 1);
}
```
Z 值就像一個==在LSB檢查"1"的偵測器==，檢查 x 的 LSB 是否為1，否則將 x 做右移運算。
有此可知，Z 值應該為1。
`while(x && unknown <= 1)`會將 x=0 的狀況排除且unknown拿來記錄"1"的個數，當在 if 條件中檢測到"1"即將 unknown 加1，這邊舉三種例子：
例1: x=0000~2~
```
x=0 不會進入 while 迴圈， unknown==0 ，回傳false
```
例2: x=0010~2~
```
Step1. x!=0 且 unknown==0 進入 while 迴圈 → LSB 不為1 → x做算術右移為0001
Step2. x!=0 且 unknown==0 進入 while 迴圈 → LSB 為1 → unknown==1 → x做算術右移為0000
Step3. x=0 不會進入 while 迴圈 → unknown==1，回傳 true
```
例3: x=0110~2~
```
Step1. x!=0 且 unknown==0 進入 while 迴圈 → LSB 不為1 → x做算術右移為0011
Step2. x!=0 且 unknown==0 進入 while 迴圈 → LSB 為1 → unknown==1 → x做算術右移為0001
Step3. x!=0 且 unknown==1 進入 while 迴圈 → LSB 為1 → unknown==2 → x做算術右移為0000
Step4. x=0 不會進入 while 迴圈 → unknown==2，回傳 false
```
此等價的函式只想在 x 中找僅有1個bit為"1"的數，所以回傳的布林判斷條件為`unknown == 1`
---
### 延伸問題
* 透過 bitwise 操作將原有運算改為 const-time 實作的程式
**判斷一整數為正 or 負 or 0**
```c=
/*
if the integer is: positive print +1, negative print -1, zero print 0
*/
int32_t pos_neg_zero(int32_t a){
int32_t sign; // 判斷結果
sign = (a != 0) | (a >> 31);
return sign;
int main(void){
int x = -15;
int y = 15;
int z = 0;
printf("x sign:%d\n",pos_neg_zero(x));
printf("y sign:%d\n",pos_neg_zero(y));
printf("z sign:%d\n",pos_neg_zero(z));
return 0;
/*
x sign:-1
y sign:1
z sign:0
*/
}
```
**判斷一整數為非負整數**
```c=
/*
if the integer is: non-negative print +1, negative print 0
*/
int32_t non_neg(int32_t a){
int32_t sign; // 判斷結果
sign = 1 ^ (a >> 31);
return sign;
}
int main(void){
int x = -15;
int y = 15;
int z = 0;
printf("x sign:%d\n",non_neg(x));
printf("y sign:%d\n",non_neg(y));
printf("z sign:%d\n",non_neg(z));
/*
x sign:-2
y sign:1
z sign:1
*/
```
此方法發現與結果不合，問題出現在數值小於0的狀況。
原因是==當有號數在做右移運算時，會使用正負號位元填補空出的位元位置==，所以小於0的數，經過右移31bits後為1111...111~2~(32bits)，而非0000...001~2~(32bits)
故將程式改成：
```c=
/*
if the integer is: non-negative print +1, negative print 0
*/
int32_t non_neg(int32_t a){
int32_t sign; // 判斷結果
sign = ~(1 & (a >> 31)) +2;
return sign;
}
int main(void){
int x = -15;
int y = 15;
int z = 0;
printf("x sign:%d\n",non_neg(x));
printf("y sign:%d\n",non_neg(y));
printf("z sign:%d\n",non_neg(z));
return 0;
/*
x sign:0
y sign:1
z sign:1
*/
```
Reference
* [Bit Twiddling Hacks](http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax)
* [解讀計算機編碼](https://hackmd.io/@sysprog/rylUqXLsm)
---
## 題目3
- [ ]考慮以下程式碼：
```cpp
#include <stdio.h>
int main() { return (*******puts)("Hello"); }
```
能否編譯並執行呢？若可，為什麼呢？
---
* Why？
先了解 [C99](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf) 規格：
1. [ 6.3.2.1-4 ]
> A function designator is an expression that has function type. **Except** when it is the operand of the **sizeof** operator or the unary **&** operator, ==a function designator with type ‘‘function returning type’’ is converted to an expression that has type ‘‘pointer to function returning type’’.==
2. [ 6.5.3.2-4 ]
> The unary * operator denotes indirection. ==If the operand points to a function, the result is a function designator==
例如：
```cpp
#include <stdio.h>
int (*fptr1)(int);
int test1(int a){
a = a + 1;
return a;
}
int main(){
fptr1 = test1;
printf("test1: %x", test1);
printf("fptr1: %x\n", fptr1);
printf("fptr1: %x\n", *fptr1);
printf("fptr1: %x\n", *****fptr1);
return 0;
/*
test1: 400543
fptr1: 400543
fptr1: 400543
fptr1: 400543
*/
}
```
* **A "function designator" is converted to a "pointer to function returning type"**
=> test1 是一個 function designator 所以它會轉換成一個 pointer to function
* **If the " * " operand points to a function, the result is a function designator**
=> (*fptr1) 的結果會是一個 function designator
從例子可以得知，只要 * operator 指向一函式，==無論 * operater 有幾個最終出來的結果都會是一個function designator，而 function designator 會再轉換成一個 pointer to function，最終指向 test1 此函式。==
* 回頭來看題目
```cpp
#include <stdio.h>
int main() { return (*******puts)("Hello"); }
```
先將`(*******puts)` 可看作 `(*(*(*(*(*(*(*puts)))))))`
根據剛剛的結論：不管有幾個 * operater，最終出來的結果都會是一個function designator，而 function designator 會再轉換成一個 pointer to function，最終還是指向 puts 函式。
`puts` 的 function prototype 是 `int puts(const char *s)`
最終主程式 `main` 將呼叫 `puts` 函式 print 出 "Hello"
Reference
* [Function Pointer](https://hackmd.io/@sysprog/HyBPr9WGl)
* [C99 規格書](http://blog.csdn.net/qll125596718/article/details/6891881)
* [C pointer to function](https://jielite.blogspot.com/2014/11/c-pointer-to-function.html)
Sign in with Wallet
Connect another wallet