2017q1 Homework1 (clz)

tags: embedded

contributed by <Cayonliow>
tags:

Reviewed by Billy4195

• 可以稍微解釋一下產生出來的圖表具有什麼意義
• 圖表上為什麼會有些不穩定的點??(起伏很大的)
• 要提出clz的應用
• 嘗試C11 的 _Generic 可以參考別人寫的laochanlam clz

作業

• 題目： B04: clz
• github(原來的): clz-tests
• 解說影片: Count Leading Zero
• 劉亮谷的實驗紀錄
• 你所不知道的 C 語言：前置處理器應用篇

開發環境

cayon@cayon-X550JX:~$ lscpu
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                8
On-line CPU(s) list:   0-7
Thread(s) per core:    2
Core(s) per socket:    4
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 60
Model name:            Intel(R) Core(TM) i7-4720HQ CPU @ 2.60GHz
Stepping:              3
CPU MHz:               2423.484
CPU max MHz:           3600.0000
CPU min MHz:           800.0000
BogoMIPS:              5188.45
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              6144K
NUMA node0 CPU(s):     0-7

工具

原理與概念

• 數值
  • 文章： 重新理解數值

開發記錄

影片筆記

實作方式的講解

• iteration version
  • 對切 （c = 16）
  • 跑 5 次後跳出迴圈
  • 計算 0 的次數

include "clz.h"

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); 
}

• binary search version
  • max 一半

#include "clz.h"
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 verison
  • 位移

#include "clz.h"
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;
}

• Harley’s algorithm version
  • 數字 0 或 0xFF 在 CTZ table 跟 CLZ table 裏頭是沒有意義的數字 （不會用到的）
  • 在 CLZ table裏， 存有數字 0 的位置是代表計算後不會存取到的位置

#include "clz.h"

static inline __attribute((always_inline))
unsigned clz(uint32_t x)
{
    // CTZ table
#ifdef CTZ
    static 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,
    };

    // CLZ table
#else
    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
    };
#endif

    /* 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)];
}

• $ make plot 看圖