# B04: clz
###### tags: `sysprog2017`
:::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/Hy-pTh8Fl) 裡頭關於 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/Hy-pTh8Fl) 列出的程式，詳閱[劉亮谷的實驗紀錄](/s/BJBZn6Q6)，予以重現並解釋個別實作的運作原理
* 解說影片: [Count Leading Zero](https://www.youtube.com/watch?v=DRkXFjLfaVg) [必看!]
* 走訪全部的 32-bit 數值，用上述演算法帶入計算 clz 值，先驗證正確性，如果演算法不正確，試圖改正
* 在 GitHub 上 fork [clz-tests](https://github.com/sysprog21/clz-tests)，以此為基礎進行以下調整
* 用 C99 或 C11 改寫程式碼，其中 C11 的 [_Generic](http://www.robertgamble.net/2012/01/c11-generic-selections.html) 非常好用，詳情可見 [你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/s/S1maxCXMl)
* 比照 [phonebook](/s/rJYD4UPKe) 和 [compute-pi](/s/HkiJpDPtx)，設計一套 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` 來抑制最佳化
* 找至少 3 個案例，說明 clz 的應用場合
* 示範: [A Fast Hi Precision Fixed Point Divide](http://me.henri.net/fp-div.html)
* 提示：透過 [Google Books](https://books.google.com/) 可以找到一些專門探討 optimization 的書籍，裡頭會有 clz 的應用
* 將你的觀察、上述要求的解說、應用場合探討，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於「[作業區](/s/Hy2rieDYe)」

## 截止日期

* Mar 4, 2017 (含) 之前
* 越早在 GitHub 上有動態、越早接受 code review，評分越高

## 參考資料
:::warning
引用過往作業成果時，務必標註出處 (包含 GitHub 帳號或人名)，連帶相關的超連結
:::
* [2016 年秋季班課程作業區](https://hackmd.io/s/H1B7-hGp): 提供錄影解說