# 進階電腦系統理論與實作-第一週

## 課程筆記
1. C語言中 Addition/subtraction operator 的優先度大於 bitwise shift operator 的優先度

2. - [x] 以位元運算子實作 x == y 等價的表示
直覺認為答案是︰==!(x ^ y)==
但用到 logical operator `not "!"`不知道算嗎。
`!(x ^ y)`和`(x ^ y)!=0`的行為不同嗎，相同的話那這樣寫有意義嗎
解答︰這題的意義是熟悉硬體行為

3. `x * 31` 等同 `(x << 5) - x`
`x * (-6)` 等同 `(~((x << 3)-(X << 1)))+1`

4. clz應用
- **在浮點數除法的優化**
==在 32-bit float point 除法中，需要走訪全部 32-bit 的數值做運算，可以利用CLZ判斷並跳過前面為0的位元即可加速==
- **乘法的溢位偵測**
==由clz(x) + clz(y)可看出是否溢位==
- **計算以2為底數的對數值**
==log2(x)= 31-clz(x) [取 lowerbound (floor log2(x))]
log2(x)= 32-clz(x) [取 upperbound (ceiling log2(x))]==

5. concurrency
同時執行不相關的任務

6. parallelism
同時執行一樣的任務

7. printf 16進位數值：printf("%x", x);

8. - [x] c語言中

char s[16];
memcpy(s, "0123456789abcde", sizeof s);

printf("%s\n", s);
printf("%x\n", s);      has type ‘char *’
printf("%x\n", &s);     has type ‘char (*)[16]’
printf("%c\n", *s);     correct
printf("%c\n", *(&s));  incorrect
printf("%c\n", **(&s)); correct

疑問︰s 和 &s 印出來結果為什麼一樣。
答案︰
One neat feature of C is that, in most places, when you use the name array again, you will actually be using a pointer to its first element (in C terms, &array[0]). This is called “decaying”: the array “decays” to a pointer. Most usages of array are equivalent to if array had been declared as a pointer.

There are, of course, cases that aren't equivalent. One is assigning to the name array by itself (array = …)—that's illegal.

Another is passing it to the sizeof operator. The result will be the total size of the array, not the size of a pointer (for example, sizeof(array) using the array above would evaluate to (sizeof(int) = 4) × 3 = 12 on a current Mac OS X system). This illustrates that you are really handling an array and not merely a pointer.

In most uses, however, array expressions work just the same as pointer expressions.

So, for example, let's say you want to pass an array to printf. You can't: When you pass an array as an argument to a function, you really pass a pointer to the array's first element, because the array decays to a pointer. You can only give printf the pointer, not the whole array. (This is why printf has no way to print an array: It would need you to tell it the type of what's in the array and how many elements there are, and both the format string and the list of arguments would quickly get confusing.)

Decaying is an implicit &; array == &array == &array[0]. In English, these expressions read “array”, “pointer to array”, and “pointer to the first element of array” (the subscript operator, [], has higher precedence than the address-of operator). But in C, all three expressions mean the same thing.

(They would not all mean the same thing if “array” were actually a pointer variable, since the address of a pointer variable is different from the address inside it—thus, the middle expression, &array, would not be equal to the other two expressions. The three expressions are all equal only when array really is an array.)

9. - [ ] 為什麼可以執行

#include <stdio.h>

int main() 
{ 
    return (*******puts)("Hello"); 
}

找時間去看規格書
答案︰
- C99 [ 6.3.2.1 ] 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’’.
- * is Right associative operator
- C99 [6.5.1 ] It is an lvalue, a function designator, or avoid expression if the unparenthesized expression is, respectively, an lvalue, a function designator, or avoid expression.
- C99 [6.5.3.2-4] The unary * operator denotes indirection. If the operand points to a function, the result is a function designator

10編譯器優化造成的問題

int main()
{
    long double d;
    char s[sizeof d];

    memcpy(&d, "0123456789abcde", sizeof d);
    memcpy(s, &d, sizeof s);

    printf("%s\n", s);
}

gcc -std=c11 -pedantic -Wall -Wextra -O0 memcpy.c
gcc -std=c11 -pedantic -Wall -Wextra -O3 memcpy.c

某些版本編譯器可能造成結果不同

11. 好的程式碼
- [ Correct ] : 做到預期的行為了嗎？能夠處理各式邊際狀況嗎？即便其他人修改程式碼後，主體的行為仍符合預期嗎？
- [ Secure ] : 面對各式輸入條件或攻擊，程式仍可正確運作嗎？
- [ Readable ] : 程式碼易於理解和維護嗎？
- [ Elegant ] : 程式碼夠「美」嗎？可以簡潔又清晰地解決問題嗎？
- [ Altruist ] : 除了滿足現有的狀況，軟體在日後能夠重用嗎？甚至能夠抽離一部分元件，給其他專案使用嗎？

12. bit-wise operator 避免 overflow

(x+y)/2
從硬體加法器實作來思考

x+y：
(x&y)<<1    //進位
(x^y)       //相加

(x+y)/2：
(((x&y)<<1) + (x^y)) >> 1
(x&y) + ((x^y) >> 1)

13. 偉大 Git commit message 的七條規則
1. 用一行空白行分隔標題與內容
2. 限制標題最多只有 50 字元
3. 標題開頭要大寫
4. 標題不以句點結尾
5. 以祈使句撰寫標題
6. 內文每行最多 72 字
7. 用內文解釋 what 以及 why vs. how

14. clz迴圈版本

int clz(uint32_t x)
{
    int n = 32, c = 16;
    
    do
    {
        uint32_t y = x >> c;
        if (y) { n -= c; x = y; }
        c >>= 1;
    } while (c);
    
    return (n - x);
}

這樣會有一個問題，就是可以利用執行時間長短來猜測程式行為，像是 0x80000000 和 0x00000001 的執行時間會差很多，利用大量數值分佈來猜測可能會有資訊安全的隱憂。所以下面改用常數時間的clz版本

int clz(uint32_t x)
{
    int n=0;
    
    if ((x & 0xFFFF0000) == 0){ n = n + 16; x = x << 16;} //16 left bits are 0
    if ((x & 0xFF000000) == 0){ n = n +  8; x = x <<  8;} // 8 left bits are 0
    if ((x & 0xF0000000) == 0){ n = n +  4; x = x <<  4;} // 4 left bits are 0
    if ((x & 0xC0000000) == 0){ n = n +  2; x = x <<  2;} // 2 left bits are 0
    if ((x & 0x80000000) == 0){ n = n +  1; x = x <<  1;} // 1 left bits are 0
    if ((x & 0x80000000) == 0){ n = n +  1; x = x <<  1;} // 1 left bits are 0
    
    return n;
}

## 作業題目
- [ternary](https://hackmd.io/s/Sym0UAk9Z)
- [phonebook](https://hackmd.io/s/HJJUmdXsZ)
- [clz](https://hackmd.io/s/Hyl9-PrjW)

## 我的作業連結
- [ternary](https://hackmd.io/AwYwnARgrCAmCGBaKYAsZGoMwA4BMiEWAZgGyICMFApgOxVjzXVjFA==)

## 參考資料
- [課程說明投影片](https://docs.google.com/presentation/d/1-6ZlaL3vd-a54omTpcTQPudbpxz-eqisyd7PY4e_Ctc/edit#)
- [如何寫一個 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/#rules02)
- [CLZ application and improvement](https://hackmd.io/s/S153n-G1g)
- [Everything you need to know about pointers in C](http://boredzo.org/pointers/)