# 2017q1 Homework1 (clz)
contributed by <`petermouse`>
### Reviewed by `heathcliffYang`
- 用`__builtin_clz()`驗證程式的正確性是很好的想法
- 期待可以看到關於這些方法的效能分析
- 可以查詢CLZ的應用
### Reviewed by `andycom12000`
- 2^31^~2^32^-1的正確性真的有必要驗證嗎?
- Commit [237f5da761f4d9c3e5a0d400781437a009dbe7d7](https://github.com/petermouse/clz-tests/commit/237f5da761f4d9c3e5a0d400781437a009dbe7d7)可以分為三個commit，不要將所有東西都混在一個commit裡面
## 開發環境
>進度有些落後囉~
>[name=課程助教][color=red]
>我會加油的QQ
>[name=petermouse]
* OS: Ubuntu 16.04 LTS
* Memory: 8 GB
* CPU:
* Name:
* Intel(R) Core(TM) i5-4200H CPU @ 2.80GHz
* Cache:
* L1d Cache： 32K
* L1i Cache： 32K
* L2 Cache： 256K
* L3 Cache： 3072K
## 驗證程式正確性
`make PROFILE=1` 可以使程式驗證 `uint32_t` 從 1 至 2^31^-1 的正確性
不過並沒有驗證 0 與 2^31^ ~ 2^32^ - 1的狀況，所以我新增程式碼檢查 (第4-5行、第12-15行)
[gcc 手冊](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)對 `__builtin_clz()` 的說明
>Built-in Function: int __builtin_clz (unsigned int x)
> Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
所以 0 直接使用 `sizeof(uint32_t) * 8` 做檢查
```clike=
for (int try = 0; try < 20; try++) {
timec = 0;
get_cycles(&timec_high1, &timec_low1);
printf("%u:%d \n", 0, clz(0));
assert((sizeof(uint32_t) * 8) == clz(0));
for (uint32_t i = 0; i < 31; i++) {
printf("%u:%d \n", 1 << i, clz(1 << i));
for (uint32_t j = (1 << i); j < (1 << (i + 1)); j++) {
assert( __builtin_clz (j) == clz(j));
}
}
printf("%u:%d \n", 1u << 31, clz(1u << 31));
for (uint32_t j = (1u << 31); j < UINT32_MAX; j++)
assert(__builtin_clz(j) == clz(j));
assert(__builtin_clz(UINT32_MAX) == clz(UINT32_MAX));
get_cycles_end(&timec_high2, &timec_low2);
timec = diff_in_cycles(timec_high1, timec_low1, timec_high2, timec_low2);
printf("executiom time : %lu cycles\n", timec);
}
```
重新執行各個程式，沒有 `assert()` 錯誤訊息跳出，確認每個演算法在 32-bit 的範圍內都可以運作成功
## 解釋個別 clz 運作原理
### recursive version
### iteration version
原程式碼：
```clike=
static inline __attribute((always_inline))
unsigned 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);
}
```
原理：以二分法的方式檢查
先初始假定 clz 值為 32 (n = 32)
每次先檢查前半 bit field 是否為零(平移一半 ( = c) )，分為兩種狀況
* 前半 bit field 不為零：
* 更新 n 值，已經確保 n 需減去 x 後半 bit 數 ( = c)
* 更新 x 值，接下來只檢查這一半 bit field
* 對應的 c 值更新，檢查的範圍剩一半，平移量也更新為一半
* 前半 bit field 為零：
* 繼續檢查後半 bit field，檢查的範圍剩一半，平移量( = c)也更新為一半
最後的 n-x 才是 clz 之值，因為最後的 x 之值為 0 或 1
已經沒有辦法對半檢驗( c == 0 )，也就是說迴圈並沒有檢查剩餘一個 bit 的 x
如果為 1 需從 n 值扣除 1
### byte shift technique
為了方便檢視，就先不遵守 coding style 了
```clike=
static inline __attribute((always_inline))
unsigned clz(uint32_t x)
{
if (x == 0) return 32;
int n = 1;
if ((x >> 16) == 0) { n += 16; x <<= 16; }
if ((x >> 24) == 0) { n += 8; x <<= 8; }
if ((x >> 28) == 0) { n += 4; x <<= 4; }
if ((x >> 30) == 0) { n += 2; x <<= 2; }
n = n - (x >> 31);
return n;
}
```
很像 iteration version，但稍微不一樣
先檢查 x 是否為 0
(x 為 0 在這個演算法沒辦法使用，其實可以使用但將多一個更複雜的 `if` 述句，見底下說明)
是的話直接 return 32
先不管 n 初始化為 1 代表什麼，再來檢驗前半 bit field
* 前半 bit field 為零：
* 將 n 值加上對應的 bit 數量，已經得知 clz 要加上該數量
* 將 x 平移至前半 bit field ，之後將檢驗該 bit field
* 前半 bit field 不為零：
* 不做任何事情，之後將檢驗前半 bit field
可以發現是不斷平移 16 、 24 、 28 、 30，也就是不斷檢驗前半 bit field，即使前半 bit field 為 0 ，接下來也將拉升至前半繼續做檢驗，實際上還是在檢驗原本後半的 bit field
本來程式若初始化 n = 0 ，且考慮 x = 0應該寫成以下形式
```clike
if((x >> 31) == 0) { n += 1; x <<= 1;}
if((x >> 31) == 0) { n += 1;}
return n;
```
也就是底下為目前剩下的考慮情況 (most significant 的 2 bits)
```clike
00: n = n + 2
01: n = n + 1
10: n = n + 0
11: n = n + 0
```
不過如果有 `if (x == 0) return 32;` ， `00` 其實是不可能出現的，`00`代表全為 0，但全為 0 已經排除
所以重新整理上面
本來程式若初始化 n = 0 應該寫成以下形式
```clike
if((x >> 31) == 0) { n += 1;}
return n;
```
對應的考慮情況
```clike
01: n = n + 1
10: n = n + 0
11: n = n + 0
```
不過一開始 `n = 1`，就是已經先加 1 了
現在變成
```clike
01: n = n + 0
10: n = n - 1
11: n = n - 1
```
`n = n - (x >> 31)`就是正確的數值！而且不用再多一個 `if` 判斷，就像 [Programming Small](https://hackmd.io/s/HkO2ZpIYe) 裡面提到的「原本涉及到分支的陳述，可更換為沒有分支的版本」，沒想到也應用在這裡！
### binary search version
```clike=
static inline __attribute((always_inline))
unsigned clz(uint32_t x)
{
if (x == 0) return 32;
int n = 0;
if (x <= 0x0000FFFF) { n += 16; x <<= 16; }
if (x <= 0x00FFFFFF) { n += 8; x <<= 8; }
if (x <= 0x0FFFFFFF) { n += 4; x <<= 4; }
if (x <= 0x3FFFFFFF) { n += 2; x <<= 2; }
if (x <= 0x7FFFFFFF) { n += 1; x <<= 1; }
return n;
}
```
原理本質上和 byte shift technique 相等
另外最後的 `x <<= 1` 是多餘的，因為已經不需要再使用到了(不需要再用來判斷 0 了)
### Harley's algorithm
```clike=
static inline __attribute((always_inline))
unsigned clz(uint32_t x)
{
// CLZ table
static uint8_t const Table[] = {
32, 31, 0, 16, 0, 30, 3, 0, 15, 0, 0, 0, 29, 10, 2, 0,
0 , 0, 12, 14, 21, 0, 19, 0, 0, 28, 0, 25, 0, 9, 1, 0,
17, 0, 4, 0, 0, 0, 11, 0, 13, 22, 20, 0, 26, 0, 0, 18,
5 , 0, 0, 23, 0, 27, 0, 6, 0, 24, 7, 0, 8, 0, 0, 0
};
/* Propagate leftmost 1-bit to the right */
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
/* x = x * 0x6EB14F9 */
x = (x << 3) - x; /* Multiply by 7. */
x = (x << 8) - x; /* Multiply by 255. */
x = (x << 8) - x; /* Again. */
x = (x << 8) - x; /* Again. */
return Table[(x >> 26)];
}
```
比起前面其他的演算法來說，Robert Harley's algorithm 未使用到任何的條件述句，分為兩個部份。
* 第一部份：我只看得懂這裡
* 由左至右將遇到第一個 1 後的所有 bit 都變為 1
* 第二部份
* 將 x * 7 * 255 * 255 再右移 26 位，查個表就有答案了？！
* 感覺跟之前資訊安全課瞄到的 finite field 、 GF(2^n^) 有關係的樣子？
[Hacker's Delight](https://books.google.com.tw/books?id=VicPJYM0I5QC&pg=PA101&lpg=PA101&dq=robert+harley+counting+leading+zero&source=bl&ots=2n6VQWyzWr&sig=eOTAdwGsH7bSd1PuzV-Xc9weQL4&hl=zh-TW&sa=X&ved=0ahUKEwiUquTmtsHSAhWGsJQKHUUUAKsQ6AEILTAC#v=onepage&q=robert%20harley%20counting%20leading%20zero&f=false) 內有提及一些各種 clz 的演算法，也提到了 Harley's algorithm ，但是我看不太懂，也還不曉得使用上的好處
## 設計實驗
## clz 應用
*
## 參考資料
[2016秋季班 team 9 Natural merge sort 在特定硬體的加速](https://hackmd.io/s/B1_V03Vlg#)
亮谷學長的[共筆](https://hackmd.io/s/BJBZn6Q6)與[錄影](https://www.youtube.com/watch?v=DRkXFjLfaVg)
[](https://books.google.com.tw/books?id=x_-Zsra5IAEC&pg=PA134&dq=counting+leading+zero&hl=zh-TW&sa=X&redir_esc=y#v=onepage&q=counting%20leading%20zero&f=false)
[](https://books.google.com.tw/books?id=VicPJYM0I5QC&printsec=frontcover&dq=counting+leading+zero&hl=zh-TW&sa=X&redir_esc=y#v=onepage&q=counting%20leading%20zero&f=false)
[](http://www.hackersdelight.org/corres.txt)
[](http://embeddedgurus.com/state-space/2014/09/fast-deterministic-and-portable-counting-leading-zeros/)
[](https://books.google.com.tw/books?id=VicPJYM0I5QC&pg=PA101&lpg=PA101&dq=robert+harley+counting+leading+zero&source=bl&ots=2n6VQWyzWr&sig=eOTAdwGsH7bSd1PuzV-Xc9weQL4&hl=zh-TW&sa=X&ved=0ahUKEwiUquTmtsHSAhWGsJQKHUUUAKsQ6AEILTAC#v=onepage&q=robert%20harley%20counting%20leading%20zero&f=false)
Sign in with Wallet
Connect another wallet