# 2020q3 Homework2 (quiz2) contributed by < `Tim096` > > [測驗題](https://hackmd.io/@sysprog/2020-quiz2) [TOC] ## 1. ASCII 編碼判斷 目前電腦中用得最廣泛的字元集及其編碼，是美國國家標準局 (ANSI) 制定的 ASCII 碼，被國際標準化組織 (ISO) 採納為 ISO 646 標準。7 位碼 ASCII 是以 7 位元二進位數字進行編碼，可表示 128 個字元，第 128～255 號為擴展字元 (extended ASCII)。 如果我們明確界定 7 位元編碼的字元隸屬於 ASCII，可透過以下函式來判斷指定的記憶體範圍內是否全是有效的 ASCII 字元 ```cpp #include <stddef.h> bool is_ascii(const char str[], size_t size) { if (size == 0) return false; for (int i = 0; i < size; i++) if (str[i] & 0x80) /* i.e. (unsigned) str[i] >= 128 */ return false; return true; } ``` 其中 `str` 是開頭的記憶體地址，`size` 則是要檢驗的範圍。逐一字元比對的效率低，在 64 位元的架構下，我們嘗試一次比對 64 位元的資料 (即 word size)，程式碼改寫如下: ```cpp= #include <stdbool.h> #include <stddef.h> #include <stdint.h> #include <string.h> bool is_ascii(const char str[], size_t size) { if (size == 0) return false; int i = 0; while ((i + 8) <= size) { uint64_t payload; memcpy(&payload, str + i, 8); //保證對齊的情況 if (payload & MMM) //payload : 處理的資料區段 return false; i += 8; } while (i < size) { if (str[i] & 0x80) return false; i++; } return true; } ``` <font color="#f00">Q : 第12行為何要`str+i`?</font> A : 這一行有更動到i值 <font color="#f00">Q : 第17~21行為何還需要 ? (是不是怕說不一定是8的倍數)</font> A : ok :::info `memcpy` 常見的實做是先檢查 memory address 是否 ==word aligned==，如果不是會先 copy 前幾 bytes 使目前位址到 word aligned 的地方，然後以 word 而不是 byte 為單位做資料 copy。 因此同樣一個 instruction 可以搬多個 bytes，會比用迴圈每個 byte 逐一 copy 要快，有時候甚至可以用 Intel cpu 特殊的專用指令做一次 copy 整個區塊。 ::: 已知 7 位元編碼的字元隸屬於 ASCII，透過 `uint64_t` 也就是 `long int` `payload` 截取 `str` 字串陣列中前8位進行判斷，如下圖所示，與 `0x80` 進行 `&` 運算後必須等於==0== 而 `payload` 內有 8 個bytes對應8個字元，因此每個字元對應一組 `0x80` MMM = `0x8080808080808080` 白話版本 : 因為ASCII的合法字元為0~127，轉換成 Binary 會發現和 128 做 &`(And)`運算都會等於 ==0== 然後j會發現了這一件事情`Payload`這一件事情，其實就只是藉由64位元架構，一次比8個變成 `0x80` 有8個就變成 MMM 了~ | Hexadecimal | Binary | Decimal | | ----------- | --------- |---- | | 0x80 | 1000 0000 | 128 | | 0x7F | 0111 1111 | 127 | --- ### 檢測英文大小寫字母(進階題) **給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母** 只要檢測到英文字母，便可`return true` [檢測英文大小寫字母](https://github.com/Rsysz/quiz2/blob/master/test1.c) --- ## 2. 16進位字串轉換 ```cpp= uint8_t hexchar2val(uint8_t in) { const uint8_t letter = in & MASK; const uint8_t shift = (letter >> AAA) | (letter >> BBB); return (in + shift) & 0x0f; } ``` MASK = `0x40` AAA = `3` BBB = `6` 第三行 : 判斷是否為字母可以藉由以下表格發現規律 第四行 : 這邊其實很特別，建議自己帶一個字母和一個數字就會知道其實很酷的，以下我用 pseudo code 來解釋 ```cpp= 第四行程式解釋 if "字母" shift = 0000 1001 (9) else "0~9" shift = 0000 0000 (0) ``` 第五行 : 這邊數字的部分很好理解，但是字母的大小寫的部分之所以可以這樣玩就要追究的到 ASCII ，當初神奇地設計了仔細觀察一下英文字母對應的大小寫都是剛好差距 32(0010 0000)這一個數字就在第三行的時候把利用 `0x40` 剛好的解決掉了這一差異。 > 已知 `in` 一定隸屬於 '0', '1', '2', …, '9' 及 'a', 'b', 'c', …, 'f' (小寫) 及 'A', 'B', 'C', …, 'F' (大寫) 這些字元。預期 `hexchar2val('F')` 和 `hexchar2val('f')` 回傳 15，且 `hexchar2val('0')` 回傳 0，其他輸入都有對應的數值。 [`Aa(10)` `Bb(11)` ... ]。 * 已知 `hexchar2val('F')` 和 `hexchar2val('f')` 回傳 15 * `F` 對應`0x46`, `f` 對應 `0x66` | Character| Hexadecimal | Binary | | ---- | -------- | -------- | | F | 0x46 | 0==1==00 0110 | | E | 0x45 | 0==1==00 0101 | | D | 0x44 | 0==1==00 0100 | | C | 0x43 | 0==1==00 0011 | | B | 0x42 | 0==1==00 0010 | | A | 0x41 | 0==1==00 0001 | | f | 0x66 | 0==1==10 0110 | | e | 0x65 | 0==1==10 0101 | | d | 0x64 | 0==1==10 0100 | | c | 0x63 | 0==1==10 0011 | | b | 0x62 | 0==1==10 0010 | | a | 0x61 | 0==1==10 0001 | | | 0x40 | 0==1==00 0000 | | | 0x0f | 0000 1111 | 再來看到 `return (in + shift) & 0xf` 於是知道 `F` 與 `f` 兩者輸入的 `in + shift` ==最低位的 4 個 bits== 必定為 `1111`，轉為十進位也就是 15 ---- [擴充版本](https://github.com/Rsysz/quiz2/blob/master/test2.c) --- ## 3. 快速除法 ```cpp= const uint32_t D = 3; //M = (0xFFFFFFFFFFFFFFFF / D) + 1 = 0x5555555555555556 #define M ((uint64_t)(UINT64_C(XXX) / (D) + 1)) //D需要小括號，可能是1+2 /* compute (n mod d) given precomputed M */ uint32_t quickmod(uint32_t n) { uint64_t quotient = ((__uint128_t) M * n) >> 64; //為何要用128 ? 可是暫存器只有64 return n - quotient * D; } ``` 查一下無號 * 有號? 有號 * 無號? 要怎麼讀資料是開發人員的責任! (c89 ， c99) 到底是除法還是上面這樣會比較快 ? marco articature 有可能在不同的處理器會有不同的結果 何謂叫做快 ? latency ， throughput(已經很不好) 之後會講!! 為甚麼 XXX = `(f) 0xFFFFFFFFFFFFFFFF` `UINT64_C` = marco 第二行 : <font color="#f00">Q : 看不懂 ? </font> A : ok 如標題所述，除法可以利用$2^N$進行加速，透過將$\dfrac{n}{d}=n\times\dfrac{\dfrac{2^N}{d}}{2^N}$將除法轉換為乘法和位移操作，進而減少運算成本。 已知 `quotient = ((__uint128_t) M * n) >> 64` 對應$\dfrac{1}{2^N}$ 所以 $N=64$ 但對應的$M卻不等於\dfrac{2^N}{d}$而是$M=\dfrac{2^N-1}{d} + 1$ 因此要證明兩者最終結果是相等的。 - 若以數學的角度考量$\dfrac{M \times n}{2 ^ {64}} = \dfrac{(\dfrac{2 ^ {64} - 1}{d} + 1) \times n}{2 ^ {64}} = \dfrac{n \times 2 ^ {64} - n}{d \times 2 ^ {64}} + \dfrac{n}{2 ^ {64}}$ $= \dfrac{n}{d} - \dfrac{n}{d \times 2 ^ {64}} + \dfrac{n}{2 ^ {64}} = \dfrac{n}{d} + (\dfrac{d \times n - n}{d \times 2 ^ {64}}) = \dfrac{n}{d} + (\dfrac{(d - 1) \times n}{d \times 2 ^ {64}}) < \dfrac{n}{d} + \dfrac{n}{2^{64}}$。 由於$n,d < 2^{32} - 1因此\dfrac{n}{2 ^ {64}} < \dfrac{1}{2^{32}} < \dfrac{1}{2^{32} - 1}且\dfrac{n}{d}的餘數部分最大值為\dfrac{2^{32}-2}{2^{32} - 1}$ 所以$\dfrac{n}{d}的餘數部分加上\dfrac{n}{2^{64}}也不會進位$ - 但若以程式碼的角度考量 若$M=\dfrac{2^{64}}{d}為整數(設為K)，因\dfrac{2^{64} - 1}{d} < K所以M=\dfrac{2^{64} - 1}{d}+1=(K-1)+1 = K$ 若$M=\dfrac{2^{64}}{d}為非整數，因\dfrac{2^{64} - 1}{d} > K所以M=\dfrac{2^{64} - 1}{d}+1=K+1$ 兩種情況會讓 `quotient` 分別等於$\dfrac{n}{d}和\dfrac{n}{d}+\dfrac{n}{2^{64}}$但根據上述數學推論的結果，兩者得到的答案相等 因此最後 XXX = `(f) 0xFFFFFFFFFFFFFFFF` ## 4. 倍數判斷 已知 `D = 3` `M = (0xFFFFFFFFFFFFFFFF / D) + 1 = 0x5555555555555556` ```cpp= bool divisible(uint32_t n) { return n * M <= YYY; } ``` YYY = `(c) M - 1` 令 `n=3k, 3k+1, 3k+2` (k為非負整數) `n * M` 等於 若 `k=1` 因為 `3M > 0xFFFFFFFFFFFFFFFF` (overflow) 所以 `3M = 0x0000000000000002` 求三者最小值: * 3kM = 2k * (3k+1)M = 3kM + M = 2k+M * (3k+2)M = 3kM + 2M = 2k + 2M 因此只有 `(c) M - 1, (d) M >> 1` 符合要求 但答案的 YYY = `(c) M - 1` ## 5. 字串大小寫轉換 **考慮 `strlower` 函式的作用是將指定的字串 (或部分字串) 的英文字母全改為小寫，其 in-place 的實作** //測驗寫程式能力 為了美觀和排版也可以說是摩斯密碼全部都是大寫 ```cpp= #include <ctype.h> #include <stddef.h> #include <stdint.h> #define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u) // mask generator 需要過濾特定的範圍 且 必須要在編譯期間建立 /* vectorized implementation for in-place strlower */ void strlower_vector(char *s, size_t n) { size_t k = n / 8; for (size_t i = 0; i < k; i++, s += 8) { uint64_t *chunk = (uint64_t *) s; if ((*chunk & PACKED_BYTE(VV1)) == 0) { /* is ASCII? */ uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + VV2); uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + VV3); uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2; *chunk ^= mask; } else strlower(s, 8); } k = n % 8; if (k) strlower(s, k); } ``` VV1 = `(e) 0x80` VV2 = `(b) 0` VV3 = `(a) (-1)` VV4 = `(e) 0x80` 首先看到`PACKED_BYTE`的效果是將輸入LSB的8bits擷取後重複擴充至64個bits e.g. PACKED_BYTE(0xAB) 會得到 0xABABABABABABABAB **第5行** : <font color="#f00">Q :我知道是上面那個作用且我也知道如何操作，但是不懂`(uint64_t)(b)` 這一個部分 ? </font> A : 確保型態的正確性 ， cast作用是拿來大轉小 或是 小轉大 問一下老師為何要+ **第10~11行** : 檢查傳進來的size多大`第10行`會除8以便讓`第11行`知道說需要跑幾次的迴圈 **第12行** : <font color="#f00">Q : 不太懂在幹嘛?</font> A : cast 而已 把傳進來的文章切8 8 8 進行以便讓下面的運算。 **第13行** : 如同第一題一般以0x80對ASCII範圍內的字元進行檢測 因此 VV1 = `(e) 0x80` **第14行** : <font color="blue">藍色線條的部分</font> **第15行** : <font color="blue">藍色線條的部分</font> ![](https://i.imgur.com/VUvJBl1.jpg) **第16行** : <font color="green">綠色線條的部分</font> <font color="pink"> 粉色線條的部分</font> **第14~16行** : 可以參考 [RusselCK](https://hackmd.io/@RusselCK/syprog2020_quiz2#Q5-%E5%B0%87%E6%8C%87%E5%AE%9A%E7%9A%84%E5%AD%97%E4%B8%B2-%E6%88%96%E9%83%A8%E5%88%86%E5%AD%97%E4%B8%B2-%E7%9A%84%E8%8B%B1%E6%96%87%E5%AD%97%E6%AF%8D%E5%85%A8%E6%94%B9%E7%82%BA%E5%B0%8F%E5%AF%AB)搭配上面這張圖可以幫助理解。 再來看到`uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2`而上課時學到 > ('a' ^ ' ') // 得到 'A' ('A' ^ ' ') // 得到 'a' 此外`0x80` >> 2 = `' '`可以知道`A ^ Z`的數值可以決定這8個字元哪一位要做大小寫轉換 也就是說只有字元為大寫時，`A ^ Z`的MSB才能為1 `(128 - 'A' + char + VV2) ^ (128 - 'Z' + char + VV3)` ASCII | char | Decimal | Binary | | ---- | ------- |------- | | A | 65 |0100 0001| | Z | 90 |0101 1010| | |128 |1000 0000| |sapce |32 |0010 0000| 因此可得知當 `char >= 'A'` 時 `uint64_t A` 的MSB 為1 `char >= 'Z'` 時 `uint64_t Z` 的MSB 為1 但當 `char = Z` 時為了使 `A ^ Z` 的MSB為1 還需額外減1 VV2 = `(b) 0` VV3 = `(a) (-1)` VV4 = `(e) 0x80` ## 6. 單次數尋找 ```cpp= int singleNumber(int *nums, int numsSize) { int lower = 0, higher = 0; for (int i = 0; i < numsSize; i++) { lower ^= nums[i]; lower &= KKK; //KKK = (c) ~higher higher ^= nums[i]; higher &= JJJ; //JJJ = (d) ~lower } return lower; } ``` `KKK` = `(c) ~higher` `JJJ` = `(d) ~lower` - 強烈建議測驗6參考 [Hkoajm0Vw](https://hackmd.io/@joey3639570/Hkoajm0Vw#%E6%B8%AC%E9%A9%976)，我個人覺得寫的超級淺顯易懂。 題目前導知識 : `Melay狀態機` `~代表補數` `各個運算元` 題目須注意事項 : <font color="#f00">Q : 問一下第一點為何會這樣 ? 是不是這一邊所謂 bit 其實有一點瑕疵呢 ? 準確一點來說是不要說每一個不同的 data </font> A : 的確就是每一個bit就是一個狀態機 1. 首先每個 bit 的動作是獨立的，不會互相影響。所以我們其實是在分別計算每個 bit 的出現次數。 2. 推廣到判斷三次，程式內的 lower 和 higher ，其實概念是兩個位元代表2進位的數字，出現第一次`01`,第二次`10`，第三次`00`來代表 ### 開始講解題目 lower 代表的意義是 只出現第一次的 higher 代表的意義是 出現第二次的 e.g. : **nums{2,3,2,2}** | For | i = 0 | i = 1 | i = 2 | i = 3 | | ---- | ------- | ------- | ------- | ------- | | Input | 2(0010) | 3(0011) | 2(0010) | 2(0010) | | lower | 0010 | 0001 | 0001 |**0011** | | higher | 0000 | 0010 | 0000 | 0000 | 綜合上述，其實可以看出來，第一次我們使用 `lower` 保留紀錄，第二次這個紀錄會被傳到 `higher` ，若遇到第三次，則兩者歸零，因此在遇到只有一次的 case ， `lower` 會保留住只出現一次的數字，故在最後 return `lower` 題目限制的關係她只會出現3次或是1次，所以若此 Data 只有出現過那麼一次你就會直接回傳那一個的`lower` 那就會是答案了~ <font color="#f00">Q : 確實很神奇但是為何這樣做可以這樣會對? </font> A : 狀態機可用布林代數去證明 ```cpp= lower ^= nums[i]; //確保傳進來是啥 lower &= ~higher; // 去和higher確認他是否有傳進來過了 higher ^= nums[i]; //如果他是傳進來第二次的等一下可以用 higher &= ~lower; // 去和lower確認他是否有傳進來過 (是不是第二次) ``` :::info * 狀態圖：( 圓圈中的值代表 H~i~L~i~ ) ```graphviz digraph { rankdir = LR 00 -> 01 [label = "input = 1"] 01 -> 10 [label = "input = 1"] 10 -> 00 [label = "input = 1"] 00 -> 00 [label = "input = 0"] 01 -> 01 [label = "input = 0"] 10 -> 10 [label = "input = 0"] } ``` * Truth table | A | B | C | D | E | |:---- | ---- | ------ | -------- |:-------- | | H~i~ | L~i~ | num~i~ | new H~i~ | new L~i~ | | 0 | 0 | 0 | 0 | 0 | | 0 | 0 | 1 | 0 | 1 | | 0 | 1 | 0 | 0 | 1 | | 0 | 1 | 1 | 1 | 0 | | 1 | 0 | 0 | 1 | 0 | | 1 | 0 | 1 | 0 | 0 | * $E = 001 + 010$ $= A'B'C + A'BC'$ $= A'(B'C + BC')$ $= A'(B \oplus C)$ * 因此，**new L~i~ = ~ H~i~ & ( L~i~ $\oplus$ num~i~ )** ::: --- [延伸問題2](https://github.com/Rsysz/quiz2/blob/master/test6.c) [延伸問題3](https://github.com/Rsysz/quiz2/blob/master/test6_extend.c) ---- ###### tags: `進階電腦系統應用2020` `quiz2`
Last changed by  
 
Tim096
474

Read more

Lab1: RV32I Simulator

The lab is to understand how instructions work along with Ripes simulator. It starts from the small program, Factorial number, with recursion, and go on to study each stage of 5-stage-pipeline and hazards. Factorial Number The Factorial number sequence is a recursive method to define: $\ \ \ \ \ \ N_0=0,\ N_1=1$ and $\ \ \ \ \ \ N_n=N_{n-1 }* n$ for $n>1$ Implement in C code

3/19/2023
2021 Linux 核心設計課程預約一對一討論教學

首先先進入 Google calendar 選取自己想要預約並且老師有空的時段，點選編輯 開啟 Google Meet 連結，並且在「新增說明」處打上自己準備的問題(簡介即可) 再邀請對象中填寫「jserv.tw@gmail.com」 記得按儲存，並且傳送出去

3/11/2021
重做 quiz2 及延伸問題，彙整學員們的成果並重現實驗

contributed by < Tim096 > 原始測驗題 [TOC] 1. ASCII 編碼判斷 目前電腦中用得最廣泛的字元集及其編碼，是美國國家標準局 (ANSI) 制定的 ASCII 碼，被國際標準化組織 (ISO) 採納為 ISO 646 標準。7 位碼 ASCII 是以 7 位元二進位數字進行編碼，可表示 128 個字元，第 128～255 號為擴展字元 (extended ASCII)。 如果我們明確界定 7 位元編碼的字元隸屬於 ASCII，可透過以下函式來判斷指定的記憶體範圍內是否全是有效的 ASCII 字元

12/21/2020
2020 Q2 NIO 財報分析 #1

contributed by <Tim096> 最近很夯的中國電動車蔚来 NIO，Q2 財報分析。在前一年一家分析師評估 1 美元都嫌貴的股票，沒有人可以想像的到今年他會來到 40 幾塊錢。 財報分析 首先這一次財報當中的大亮點在 Q1 中他們特別提到他們會趁者 COV-19 的肆虐的期間加強的成本控制，因此在這一季的車輛毛利率以及季度毛利率都有明顯的增長第一次實現了正的車輛毛利率(9.7%)，相較上一季度成長了17.1%，非常驚人的成長，讓人想起來 Elon Musk 之前也是為了優化毛利率這一件事情住在工廠當中。或許以前大家都會質疑這一家公司這麼多服務，甚至是為了凸顯 CP 值瘋狂的在產品上琢磨，這一件事情上這一家公司真的會賺錢嗎 ? 而這一季公司則用了數據告訴大家他們賣車也是可以賺錢的! 再來提到 NIO 的營收的部分。在2020年第二季，NIO 的營收創下新高 5.264 億美元，比起去年同期，YoY 的成長率是 146.5%，跟上一季相比甚至是成長了 171.1％ ，比起特斯拉更為驚人的成長成績。2020年第二季度的淨虧損為1.665億美元，下降64.2％從2019年第二季度開始，比2020年第一季度減少30.4％。比起卻年同期已經下降了非常多，因此要說依照他現在來看成績單算是很好了。不僅在營收方面有所上升，成本控制方面看起來也作很不錯，在開源同時也做到了節流。 這一季財報發佈以前，其實 NIO 有遇到一個很大的危機，那就是電池召回事件不僅損失了 4,940萬美元也遇到了相當大的公關危機，但是從處理方法就可以發現他們和特斯拉相當不同的且想要走的路也不同了，發生了這樣的危安事件，雖然七月份的銷售的確受到了相當大的影響，但是我們可以發現最後 Q2 的銷量總體來看還是很好的，代表至少在中國人的心中 NIO 處理的態度是相當正確的，因此不影響後續的銷售。

11/24/2020
Read more from Tim096
Published on HackMD