2016q3 Homework1 (clz)

contributed by <jeff60907>

比較效能差異
- [ ]recursive version
- [x]iteration version
- [x]binary search technique
- [x]byte-shift version
- [ ]Harley’s algorithm

iteration version

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

1bit 比對

binary search technique

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

上次上課有介紹過先將32bit拆成對半比較，然後接著依序對照，
32bit最多比對5次，64bit最多6次執行次數為 log₂N

byte-shift version

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

先shift bits數再進行比對，可以少了一次 if 判別

recursive version








uint8_t clz(uint32_t x)
{
	/* shift upper half down, rest is filled up with 0s */
	uint16_t upper = (x >> 16); 
	// mask upper half away
	uint16_t lower = (x & 0xFFFF);
	return upper ? clz(upper) : 16 + clz(lower);
}

未修改版先了解運作模式
參考多位同學的recursive，使用一個shift紀錄切割的bit位數









uint8_t clz_recursive(uint32_t x, int shift) {
    if(shift == 0)
        return 0;
    /* shift upper half down, rest is filled up with 0s */
    uint16_t upper = (x >> shift); 
    // mask upper half away
    uint16_t lower = (x & 0xFFFF);
    return upper ? clz_recursive(upper, shift>>1) : shift + clz_recursive(lower, shift>>1);
}

Harley’s algorithm




























uint8_t clz(uint32_t x)
{
    static prog_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,
    };

    /* 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 pgm_read_byte(&Table[x >> 26]);
}

未修改版
參考<heathcliffYang>, <janetwei>共筆，了解harly運作






















uint8_t clz_harley(uint32_t x) {
    const char table[64] =
     {32,31, u,16, u,30, 3, u,  15, u, u, u,29,10, 2, u,
       u, u,12,14,21, u,19, u,   u,28, u,25, u, 9, 1, u,
      17, u, 4, u, u, u,11, u,  13,22,20, u,26, u, u,18,
5, u, u,23, u,27, u, 6, u,24, 7, u, 8, u, 0, u};

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

測試比較效能並驗證

test.c 驗證演算法資料正確參考Tempo JiJi














    for(int i=1; i<UINT_MAX; i++)
    {
        if( __builtin_clz(i) != clz_iteration(i))
            printf("%d\n",i);
        if( __builtin_clz(i) != clz_binary_search(i))
            printf("%d\n",i);
        if( __builtin_clz(i) != clz_binary_shift(i))
            printf("%d\n",i);
        if( __builtin_clz(i) != clz_recursive(i,16))
            printf("%d\n",i);
        if( __builtin_clz(i) != clz_harley(i))
            printf("%d\n",i);
    }
    printf("all right\n");