2017q3 Homework1 (clz)

contributed by <kevin550029>

De Bruijn sequence

• a de Bruijn sequence of order n on a size-k alphabet A is a cyclic sequence
  in which every possible length-n string on A occurs exactly once as a substring
• 給定 m 個字母，以及字串長度 k, 這個數列向左做旋轉後, 取出前 k 個字母。
  恰好可以湊出所有這 k 個字母可能的組合

Count Leading Zero

• 參考 wikipedia: clz
• 計算 2 進位數自 MSB(Most sSignificant Bit) 開始往右, 遇到的第一個 1 之前, 所有 0 的數量
• For example, the clz of 0x00000F00 is 20, and the clz of 0x00000001 is 31.
  0x00000001
  -> 0000 0000 0000 0000 0000 0000 0000 0001
  在第一個1前有31個為0的位元, 則 clz 為31
• 計算 clz 的 sample code
  ​​​​int clz1( uint32_t x )
  ​​​​{
  ​​​​  int n;
  ​​​​  if (x == 0) return 32;
  ​​​​  for (n = 0; ((x & 0x80000000) == 0); n++, x <<= 1);
  ​​​​  return n;
  ​​​​}
  

  line4: x=0時, 直接回傳clz=32
  line5: 0x80000000 為 1000…0000, 當 x 的 MSB=1 和 0x80000000 做 & 之後,
  會不等於 0 並跳出迴圈, 因此只要一直將 左移 X,
  當迴圈跳出時代表他已經遇到了第一個為1的位元

解釋並比較 32-bit 數值對各種實做的效能差異

Iteration Version

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

x 傳入後, 會先取出其 upper bits 並放入 y, 再藉由迴圈來增減需要移動的 bits 數
最後用減法來計算 leading zero 的個數

Binary Search Version

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

用 bit mask 判斷第一個為1的位元會出現在哪,
找出位置後進行適當長度的左移, 並繼續判斷
line5: 當 x <= 0x0000FFFF 表示 x的前16位元皆為零,
則將 x 左移 16位元, 並繼續判斷

Byte-Shift Version

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

Byte-Shift 和 Binary Search 的原理相似,
Byte-Shift 是將 x 往右移之後, 再判斷是否為 0

Harley’s Algorithm

unsigned clz(uint32_t x)
{
#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,
    };

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

Harley’s algorithm 是使用雜湊法來判斷 leading zero 的個數,
Table 代表的是 hash table

x 輸入後, 會先經過 line:25~29 的處理, 將第一個為1位元後的bits都設為 0
例如 0100 0000 0000 0000 0000 0000 0000 0000
變成 0111 1111 1111 1111 1111 1111 1111 1111

經由這個例子可以知道, 這樣處理之後, 真正會進入雜湊函數運算的值只會有32種
最後經由查表, 便可以快速地得到 leading zero 的個數

Recursive Version

static const int mask[] =  { 0, 8, 12,14 };
static const int magic[] = { 2, 1,  0, 0 };

unsigned clz2(uint32_t x,int c)
{
    if (!x && !c) return 32;

    uint32_t upper = (x >> (16 >> c));
    uint32_t lower = (x & (0xFFFF >> mask[c]));
    if (c == 3) return upper ? magic[upper] : 2 + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
}

比較效能

• Binary (圖中淡藍色區塊) 所需要的 cycles 數較少
• Byte 所耗費的 cycles 數 看起來比 Binary 稍長, 但相對於其他方法也算少的
• recursive method 比較不穩定

參考資料

De Bruijn sequence
共筆 tina0405
共筆 jack81306
wikipedia: clz
你所不知道的C語言：數值系統篇