# 2017q1 Homework1 (clz-tests)
contributed by <`yangyang95`>
###### tags: `sysprog2017` `HW1` `yangyang95`

電腦規格看 [這裡](https://hackmd.io/s/HJ2c_XYKx)
github page 看 [這裡](https://github.com/yangyang95/clz-tests)

### Reviewed by `jack81306`
* 可以對多一點的範圍進行分析,並弄成圖表做比較
* 可以加入一些從圖表內觀察出來的結果
* clz 還可以用在密碼學呦
## CLZ 應用
利用 google book 進行搜尋 count leading zero 的應用

- 影像壓縮處理：

在 [這本](https://books.google.com.tw/books?id=Sa-cEY_ZeEQC&pg=PA545&dq=count+leading+zero&hl=en&sa=X&redir_esc=y#v=onepage&q=count%20leading%20zero&f=false) 看到 CLZ 為對影像進行指數哥倫布編碼時，其中的一個步驟。

哥倫布編碼 (Exponential-Golomb coding) 是 H.264 / MPEG-4 AVC 格式使用到的技術，下方列出步驟，可以看到需要處理到前方零的個數。
1. Write down x+1 in binary
2. Count the bits written, subtract one, and write that number of **starting zero** bits preceding the previous bit string.

詳見：[Exponential-Golomb coding - wiki](https://en.wikipedia.org/wiki/Exponential-Golomb_coding)

- ARM 系統：

在 [這本](https://books.google.com.tw/books?id=vdk4ZGRqMskC&printsec=frontcover&dq=count+leading+zero+optimization&hl=en&sa=X&redir_esc=y#v=onepage&q=clz&f=false) 的 212 頁看到一段 CLZ 的介紹

節錄以下文字

Normalization is also useful for calculating logarithms and priority decoders used by some dispatch rountines. In these applications, we need to know both normalize value and the shift required to reach this value.

This operation is so important that an instructions is avaiable from ARM architeture ARMv5E onwards to accelerate normalization. The CLZ instruction counts the number of leading zeros before the first sinificant one. It returns 32 if there is no one bit at all. The CLZ value is the left shift you need to apply to noemalize the integer so that the leading one is at bit position 31

大意是說正規化是處理器重要的一個指令，然後 CLZ 是正規化的一個步驟，所以也很重要XD

## 程式分析

首先來嘗試驗證程式的正確性 `$ make run PROFILE=1`
使用 PROFILE=1 的標籤就會在 CFLAGS 加入 -Dcorrect

執行下方的程式碼驗證

#if defined(correct)

    for (int try = 0; try < 20; try++) {
        timec = 0;
        get_cycles(&timec_high1, &timec_low1);
        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));
            }
        }
        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);
    }

__builtin_clz() 是 gcc 內建的 CLZ 函式 ，我們拿來比較跟老師提供的實作是否答案一致。
執行一次後並沒有被 assert 中斷，故確定實作為正確。

## 效能圖形分析
執行 `$ make plot` 做圖
>註：圖形的 X 軸是 67100000 ~ 67116384 (0x3FFDD60 ~ 0x4001D60)
> y 軸是執行的 cycle 數 ，由圖中可看出不同數值、方法的時間差異

脈衝版本圖形

## _Generic 實驗
原始版本的程式碼看起來想使用 C++11 實作 overload function (並且是未完成的)
直接嘗試改成 C11 來實作 _Generic 取代 overload function

#define clz(x) _Generic((x), \
     uint8_t : clz8,\
     uint16_t : clz16, \
     default : clz32 \
 )(x)

unsigned clz32(uint32_t x);
unsigned clz16(uint16_t x);
unsigned clz8(uint8_t x);

不過在嘗試編譯的時候原本 asm assembly 卻發生錯誤
`error: 『asm』 undeclared (first use in this function)`

查 [資料](http://stackoverflow.com/questions/35131350/error-asm-undeclared-first-use-in-this-function) 之後才知道，standard C11 沒有包括 asm 的功能，必須改成 -std=gnu11

然而又出現問題 ` /main.c:111: undefined reference to 'clz32' `

clz32 的實作找不到（！？）

還看不出來是那裡的問題 Q_Q

參考資料：
[What is the difference between c11 and c++11 languages?](https://www.quora.com/What-is-the-difference-between-c11-and-c++11-languages)
[0xff07 HackMD 筆記](https://hackmd.io/s/rkTYU0vKx#-generic-修改)