# 2020q3 Homework4 (quiz4)
###### Contributed by < `haung-me` >
###### tags: `embedded_master`
# 測驗1 Hamming Distance
```c
int hammingDistance(int x, int y) {
return __builtin_popcount(x ^ y);
}
```
因為 hamming distance 就是要找出兩個數值在2進位時數值不一樣的 bit 個數，將輸入的兩個數做 XOR 後，就只有兩個數值不同的 bit 才會被 set 為1，此時再利用 __builtin_popcount 就可以計算出正確的 hamming distance。
## 不使用 gcc extension 的 C99 實作程式碼
```c
int my_hamming(int x, int y)
{
x ^= y;
y = 0;
while (x) {
x &= (x - 1);
y++;
}
return y;
}
```
利用傳入數字的空間先計算 x ^ y 並且存在 x 原本的位置，y 則設定為0，迴圈計算 x 中有多少 set bits 並將結果記錄於 y 中。
- Leetcode 結果
## LeetCode 477. Total Hamming Distance
```c
int totalHammingDistance(int* nums, int numsSize){
int total=0;
for(int i=0;i<numsSize;i++){
for(int j=0;j<numsSize;j++) {
if(i >= j)
continue;
total += __builtin_popcount(nums[i] ^ nums[j]);
}
}
return total;
}
```
- 一開始的想法就是利用兩個 for 迴圈找尋所有的 couple，並且利用 __builtin_popcount 計算兩個數字的 Hamming Distance 再相加。
- 不過經過嘗試之後發現這樣子兩個 for 迴圈的做法執行時間太高，因此在 leetcode 會遭遇 Time Limit Exceeded
```c
int totalHammingDistance(int* nums, int numsSize){
int setbits[32];
memset(setbits, 0, sizeof(int) * 32);
int total = 0;
for(int i=0;i<numsSize;i++){
while(nums[i]){
setbits[__builtin_ctz(nums[i])]++;
nums[i] &= (nums[i] - 1);
}
}
for(int i=0;i<32;i++){
total += (setbits[i] * (numsSize - setbits[i]));
}
return total;
}
```
- 之後不管怎麼思考，如果要使用找尋兩個計算 distance 的話，一定需要使用兩個 for 迴圈，因此改變想法為：先計算資料集中各個 bit 各有幾個資料是1，最後再將 setbit 數量乘以此 bit 為0的數量即為當前 bit 的 distance。
## Hamming Distance/Weight in ECC
> Hamming Distance: Number of diffierent bits between two vector.
> Hamming weight: Number of set bits in the vector.
- 兩個向量 a, b 的 Hamming Distance 等於兩個向量的 minimun Hamming Weight，因為 Hamming Distance 等於 a+b 的 Hamming Weight。
- 在 $3*7$ 的矩陣 H 中，minimun Hamming Distance 以及 minimun Hamming Weight 都在 null space 中。因此，如果我們想要找到 null space 的其中一個向量，就至少要有 minimun Hamming Distance 個 set bits。
- 另一方面，如果我們希望找出 t 個錯誤，兩個向量間的距離必須要大於等於 2t + 1，因為如果距離小於 2t + 1 就有可能兩個向量有所重疊，如果錯誤在重疊區域內的話，無法辨別哪一個向量的內容才是正確的。
:::success
綜合以上兩點，我們可以得到以下結論：
將 Hamming Distance 代入 2t + 1 中，即可找到相對應的 t 值，同時也是可以找到的錯誤數量至多 t 個。
:::
### BCH code
> [Hamming codes, h■w to ov■rco■e n■ise.](https://youtu.be/X8jsijhllIA)
- 資料集中除了放資料，也加入一些判斷是否有資料傳輸錯誤的 bit，在上圖中 15 個 bit 中有 5 個 bit 就是用來判斷錯誤，而不同的 bit 判斷的範圍也不相同。
> 0: 判斷整個資料集中是否有兩個錯誤存在
> 1: 000==1== 判斷最後一個 bit 是否為 1
> 2: 00==1==0 判斷倒數第二個 bit 是否為 1
> 4: 0==1==00 判斷第二個 bit 是否為 1
> 8: ==1==000 判斷第一個 bit 是否為 1
- 利用以上 5 個不同的 bit 不僅可以確定有資料傳輸錯誤，經過交叉比對還可以確定錯誤的 bit 為哪一個。
### Encoding
`hammingCode` 一開始設定為 0b000x0xxx0xxxxxxx，x 取決於要傳輸資料的內容。
```c
hammingCode |= \
(__builtin_popcount(0x5555 & hammingCode) & 1) << 14;
hammingCode |= \
(__builtin_popcount(0x3333 & hammingCode) & 1) << 13;
hammingCode |= \
(__builtin_popcount(0x0f0f & hammingCode) & 1) << 12;
hammingCode |= \
(__builtin_popcount(0x00ff & hammingCode) & 1) << 10;
hammingCode |= \
(__builtin_popcount(0xefff & hammingCode) & 1) << 15;
```
計算資料在各區塊中的 setbits 數量，並且使得每個區塊中的 setbits 都為偶數個。
### Decoding
> [Hamming codes, h■w to ov■rco■e n■ise.](https://youtu.be/X8jsijhllIA)
- 將資料集中所有的 setbits 位置進行一次 XOR 就可以計算出有錯誤的 bit，重複執行此步驟直到沒有計算完的結果為 0 即代表資料正確。
```c
int tmp = hammingCode;
int toggle = 0;
while (tmp) {
toggle ^= __builtin_ctz(tmp);
tmp &= (tmp - 1);
}
if (toggle != 0)
hammingCode ^= (1 << toggle);
```
## Reed-solomon
我們要傳送的資料集為 $C = {c_1, c_2, ..., c_k}$，總共有 k 個數字，傳送時我們需要加上 m 個 parity bit 使得接收訊息端 decode 時可以找到錯誤並且修正。
### Encoding
傳送資料前，我們要先把資料的數字集代入 $f(x) = \sum_{i=0}^{n-1}c_ix^i$，此時可以得到一個多項式 (polynomial)。
同時，再代入另一個函式 $g(x) = \prod_{i=0}^{n-k}(x - \alpha^j)$
> $\alpha$ is a [primitive root](https://brilliant.org/wiki/primitive-roots/), and $\prod$ means product of all elements in the set.
而 $S(x) = f(x)x^m - [(f(x)x^m) \mod g(x)]$，且可以整理為 $S(x) = \sum_{i=0}^{n-1}s_ix^i$
==上述 $S(x)$ 的係數即為我們要傳送出去的資料。==
### Decoding
假設接受端接收到的資料為 $r(x) = \sum_{i=0}^{n-1}r_ix^i = \sum_{i=0}^{n-1}(S(x^i) + e(x^i))$
==$e(x)$ means the error while transmitting==
如果將任意一個 primitive root 代入 x 中，$S(x)$ 為 0，因此 $r(\alpha) = \sum_{i=0}^{n-1}(0 + e(\alpha^i)) = \sum_{i=0}^{n-1}e(\alpha^i)$
因此可以把結果組合為以下矩陣以計算並修復為正確的值
\begin{equation}
% matrix alpha
\begin{bmatrix}
\alpha^{0\times0} & \alpha^{1\times0} & ... & \alpha^{(n-1)\times0} \\
\alpha^{0\times1} & \alpha^{1\times1} & ... & \alpha^{(n-1)\times1} \\
\vdots & \vdots & \ddots & \vdots \\
\alpha^{0\times(n-1)} & \alpha^{1\times(n-1)} & ... & \alpha^{(n-1)\times(n-1)} \\
\end{bmatrix}
% matrix error
\begin{bmatrix}
e_0 \\ e_1 \\ \vdots \\ e_{n-1}\\
\end{bmatrix}=
% matrix s
\begin{bmatrix}
S_0 \\ S_1 \\ \vdots \\ S_{n-1} \\
\end{bmatrix}
\end{equation}
- 在加入 m 個 parity bit 時，最多可以找出 $\lfloor \frac{m}{2} \rfloor$ 個錯誤的 bit 並且修正為正確的資料，或者找出 m 個錯誤不過不知道位置。
# 測驗2 Tree Ancestor
```c
typedef struct {
int **parent; // Array to store the parents of the node
int max_level, n; // Total depth of the Tree, and number of nodes
} TreeAncestor;
```
- Define the structure of TreeAncestor
```c
TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize)
{
TreeAncestor *obj = malloc(sizeof(TreeAncestor));
obj->parent = malloc(n * sizeof(int *));
int max_level = 32 - __builtin_clz(n) + 1;
for (int i = 0; i < n; i++) {
obj->parent[i] = malloc(max_level * sizeof(int));
for (int j = 0; j < max_level; j++)
obj->parent[i][j] = -1;
}
for (int i = 0; i < parentSize; i++)
obj->parent[i][0] = parent[i];
for (int j = 1;; j++) {
int quit = 1;
for (int i = 0; i < parentSize; i++) {
obj->parent[i][j] = obj->parent[i][j - 1] == -1
? -1
: obj->parent[obj->parent[i][j - 1]][j - 1];
if (obj->parent[i][j] != -1) quit = 0;
}
if (quit) break;
}
obj->max_level = max_level - 1;
obj->n = n;
return obj;
}
```
1. 先建立一個 n $\times$ max_level 的 2D array 並且初始化為 -1，之後用來存取各個 node 的 parent。
2. 把輸入的 parents array 直接先放進去 2D array 的第一個 element。
3. 每往後一個 column 代表上一層的 parent，因此只有前一個 column 不為 -1 才有可能有更上一層的 column，找尋上一層的 column 要從當前位置的 parent 往前找一個，
因此 `obj->parent[i][j] = obj->parent[obj->parent[i][j - 1]][j - 1]`
```c
int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)
{
int max_level = obj->max_level;
for (int i = 0; i < max_level && node != -1; ++i)
if (k & (1 << i))
node = obj->parent[node][i];
return node;
}
```
- 如果 `k & (1 << i) == 1` 代表可以先找尋第 i 個 parent 是哪一個 node，之後再從第 i 個 parent 往上找。
## treeAncestorCreate 記憶體浪費測試與修正
### Memory leak
拿老師的 code 直接 compile 會有 struct TreeAncestor 沒有定義 obj->n 的 error，一開始想說可能是老師輸入錯誤，因此直接把 obj->n 更改為 obj->max_level，在做記憶體測試的時候發現有 memory leak。
```
$ valgrind --leak-check=full ./ancestor
==4290== Memcheck, a memory error detector
==4290== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==4290== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==4290== Command: ./ancestor
==4290==
==4290==
==4290== HEAP SUMMARY:
==4290== in use at exit: 64 bytes in 4 blocks
==4290== total heap usage: 9 allocs, 5 frees, 184 bytes allocated
==4290==
==4290== 64 bytes in 4 blocks are definitely lost in loss record 1 of 1
==4290== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4290== by 0x10920C: treeAncestorCreate (ancestor.c:16)
==4290== by 0x10950E: main (ancestor.c:59)
==4290==
==4290== LEAK SUMMARY:
==4290== definitely lost: 64 bytes in 4 blocks
==4290== indirectly lost: 0 bytes in 0 blocks
==4290== possibly lost: 0 bytes in 0 blocks
==4290== still reachable: 0 bytes in 0 blocks
==4290== suppressed: 0 bytes in 0 blocks
==4290==
==4290== For lists of detected and suppressed errors, rerun with: -s
==4290== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
```
因為宣告了 n 個 array 存取每個 node 的部分 ancestor，不過如果只 free max_level 個就必定有部分記憶體沒有被歸還，因此修改 struct TreeAncestor 增加一個 int 存取整個 tree 的 node 數量。
```
$ valgrind --leak-check=full ./ancestor
==17441== Memcheck, a memory error detector
==17441== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==17441== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==17441== Command: ./ancestor
==17441==
==17441==
==17441== HEAP SUMMARY:
==17441== in use at exit: 0 bytes in 0 blocks
==17441== total heap usage: 9 allocs, 9 frees, 184 bytes allocated
==17441==
==17441== All heap blocks were freed -- no leaks are possible
==17441==
==17441== For lists of detected and suppressed errors, rerun with: -s
==17441== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
```
修改完之後就沒有 memory leak 了。
### Memory Waste
#### Attempt 1
其實每個 node 只要記憶一個 parent 並且找尋的時候重複執行 k 次就可以找到 Kth ancestor。
```c
TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize)
{
TreeAncestor *obj = malloc(sizeof(TreeAncestor));
obj->parent = malloc(n * sizeof(int));
int max_level = 32 - __builtin_clz(n) + 1;
for (int i = 0; i < parentSize; i++)
obj->parent[i] = parent[i];
obj->max_level = max_level - 1;
obj->n = n;
return obj;
}
int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)
{
int max_level = obj->max_level;
while (k) {
node = obj->parent[node];
k -= 1;
if (node == -1 && k > 0)
return -1;
}
return node;
}
void treeAncestorFree(TreeAncestor *obj)
{
free(obj->parent);
free(obj);
return;
}
```
不過毫不意外的，執行時間已經超過 leetcode 的限制，畢竟在 testcase 9 就已經有 50000 筆資料了。
#### Attempt 2
嘗試直接把所有的 parent 都放在一個 array 裡面，希望能夠提升找尋 ancestor 的速度
```c
typedef struct {
int **parent;
int *num_parents;
} TreeAncestor;
TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize)
{
TreeAncestor *obj = malloc(sizeof(TreeAncestor));
obj->parent = malloc(n * sizeof(int *));
obj->num_parents = malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
if (i == 0)
obj->parent[i] = malloc(sizeof(int));
else
obj->parent[i] =
malloc((obj->num_parents[parent[i]] + 1) * sizeof(int));
obj->parent[i][0] = parent[i];
if (i != 0) {
int j = 1;
for (j = 1; j < obj->num_parents[parent[i]]; j++) {
obj->parent[i][j] = obj->parent[parent[i]][j - 1];
}
obj->parent[i][j] = -1;
obj->num_parents[i] = obj->num_parents[parent[i]] + 1;
} else
obj->num_parents[i] = 1;
}
return obj;
}
int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)
{
if (k >= obj->num_parents[node])
return -1;
return obj->parent[node][k - 1];
}
void treeAncestorFree(TreeAncestor *obj)
{
for (int i = 0; i < obj->num_parents[i]; i++)
free(obj->parent[i]);
free(obj->parent);
free(obj->num_parents);
free(obj);
}
```
不過卻造成建立 tree 所需要的時間過長，甚至執行的時間比一次往上走一層更慢。
- 從 callgrind 可以看出 create 占了 99.99% 的 instructions
#### Attempt 3
此時，再嘗試回到老師使用的 Binary lifting 的方式，把多餘的最後一個 -1 刪除，因為每個 node 最後都記憶 -1 單純為了確認停止點。
```c
int max_level = 32 - __builtin_clz(n);
...
obj->max_level = max_level;
```
提交到 leetcode 後，記憶體用量確實減少了，不過執行時間也進步了一些些。
- 在思考如何提升執行時間時，發現`YLowy`同學刪除多餘的 -1 之後竟然執行時間就進步到 81%，不過我的卻只有 58.56%，於是我開始找尋我們之間的差別，發現他在最後 free 的時候並沒有將所有的 `obj->parent[i]` 記憶體歸還，我在前面提到過這個問題。既然 leetcode 不管有沒有 free 記憶體那時不是直接不歸還記憶體就好 :rolling_on_the_floor_laughing:
```c
void treeAncestorFree(TreeAncestor *obj)
{
}
```
- 把 free 內的動作全部刪除，變成上面這樣還真的進步到 90% :face_palm:
- 初始化每個 node 的第一個 parent 就要自己一個 for 迴圈實在是有點浪費，因此我選擇直接把初始化的動作放到前面 malloc 記憶體的 for 迴圈裡面。
```c
for (int i = 0; i < n; i++) {
obj->parent[i] = malloc(max_level * sizeof(int));
for (int j = 0; j < max_level; j++)
obj->parent[i][j] = -1;
obj->parent[i][0] = parent[i];
}
```
原來光是減少一個 for 迴圈竟然可以縮減這麼多的執行時間
# 測驗3 FizzBuzz
- 此題運用到之前的除法計算加速方法，只要先將 `0xFFFFFFFF / n + 1` 計算完成並且儲存好就不需要一直進行除法的運算，畢竟除法需要更多的 instruction。把前面計算好的 mask 乘上要判斷的數值後，如果此數不是 n 的倍數的話就會得到一個很大的值(正或負)，反之則會得到比較小的值(小於 mask 本身)。
- `length = (2 << div3) << div5` 可以利用 shift 的方式就計算 output 的長度，如果都不是的話只需要 2 bit，是 3 或 5 其中一個的倍數的話則需要 `2 << 1` 個 bit，同時是 3 和 5 的倍數則需要 `2 << 2` 個 bit。
- `(MSG_LEN >> div5) >> (div3 << 2)` 可以控制字串的開始位置。如果有 3 這個因數就應該要右移 4 次，使得起始點為0，而如果因數有 5，則需要右移一次，兩個都是就需要 4 次(不過 5 次也不會影響)。
利用 callgrind 可以看出 naive 以及 bitwise 兩個方法的 Ir per call 幾乎差了一倍。
# 測驗4 Page_queues
因為在進行 `divident >>= ffs32(divident)` 時，我們已經把所有的 2 的倍數都消除了，且 page_queue 最大就是 $8\times2^{n}$，因此後面 `switch (divident)` 就只需要判斷 3, 5, 7 即可。
## Leetcode 51. N-Queens
Sign in with Wallet
Connect another wallet