# A04: clz
###### tags: `sysprog2016`
:::info
主講人: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2016 年系統軟體課程](https://www.facebook.com/groups/system.software2016/)
:mega: 返回「[進階電腦系統理論與實作](http://wiki.csie.ncku.edu.tw/sysprog/schedule)」課程進度表
:::
## 作業要求
閱讀 [重新理解數值](/s/SkKZBXZT) 裡頭關於 count leading zero ([clz](https://en.wikipedia.org/wiki/Find_first_set#CLZ)) 的描述,設計實驗,比較 32-bit 數值對以下實做的效能差異:
* recursive version
* iteration version
* binary search technique
* byte-shift version
* Harley's algorithm
### 參考的程式碼
* 除了在 [重新理解數值](/s/SkKZBXZT) 列出的程式,以下也要評估:
- [ ] recursive version (注意: 以下的程式碼存在瑕疵,需要自行修正)
```c
uint8_t clz(uint32_t x)
{
/* shift upper half down, rest is filled up with 0s */
uint16_t upper = (x >> 16);
// mask upper half away
uint16_t lower = (x & 0xFFFF);
return upper ? clz(upper) : 16 + clz(lower);
}
```
- [ ] Harley's algorithm
```c
uint8_t clz(uint32_t x)
{
static prog_uint8_t const Table[] = {
0xFF, 0, 0xFF, 15, 0xFF, 1, 28, 0xFF,
16, 0xFF, 0xFF, 0xFF, 2, 21, 29, 0xFF,
0xFF, 0xFF, 19, 17, 10, 0xFF, 12, 0xFF,
0xFF, 3, 0xFF, 6, 0xFF, 22, 30, 0xFF,
14, 0xFF, 27, 0xFF, 0xFF, 0xFF, 20, 0xFF,
18, 9, 11, 0xFF, 5, 0xFF, 0xFF, 13,
26, 0xFF, 0xFF, 8, 0xFF, 4, 0xFF, 25,
0xFF, 7, 24, 0xFF, 23, 0xFF, 31, 0xFF,
};
/* 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 pgm_read_byte(&Table[x >> 26]);
}
```
### 測試方式
* 走訪全部的 32-bit 數值,用上述演算法帶入計算 clz 值,先驗證正確性,如果演算法不正確,試圖改正
* 比照 [phonebook](/s/S1RVdgza) 和 [compute-pi](/s/rJARexQT),設計一套 benchmark suite,得以針對所有的 32-bit 數值進行個別 clz 實做效能的分析,並透過 gnuplot 製圖
* 要附上個別數值實際耗費時間,不能只列出平均值
* 落點分析圖,類似 [tcp-anaysis](https://upload.wikimedia.org/wikipedia/commons/6/65/Gnuplot_tcp_analysis.png) ([with-code](https://commons.wikimedia.org/wiki/File:Gnuplot_tcp_analysis.png))
* 為了避免編譯器最佳化的影響,務必指定編譯參數 `-O0` 來抑制最佳化
### 作業繳交方式
* 在 GitHub 上建立一個名為 `clz-tests` 的 repository
* 將你的觀察、分析,以及各式效能改善過程,並善用 gnuplot 製圖,紀錄於「[作業區](https://hackmd.io/s/H1B7-hGp)」
* 找至少 3 個案例,說明 clz 的應用場合
* 示範: [A Fast Hi Precision Fixed Point Divide](http://me.henri.net/fp-div.html)
* 提示:透過 [Google Books](https://books.google.com/) 可以找到一些專門探討 optimization 的書籍,裡頭會有 clz 的應用