# 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)
Last changed by  
 
Peter Lin
321
Published on HackMD