取数的最高二进制阶数rounddown_pow_of_two

取数的最高二进制阶数

(2012-03-27 10:02:05)

标签： 杂谈

分类： Linux-2.6.35.13源码学习

在内核头文件linux/log2.h中定义：

#define rounddown_pow_of_two(n)

(

_builtin_constant_p(n) ? ((n == 1) ? 0 :(1UL << ilog2(n))) :__rounddown_pow_of_two(n)

)

1、如果n是常数则调用宏ilog2,这是因为宏是在编译(不仅在预处理阶段，而且在编译阶段)中处理的，不会影响到执行效率。

例如：

 

#define bigger(n) n > 3 ? n : 3

int i = bigger(4);

预处理后为：

 

# 1 "temp.c"

# 1 "<built-in>"

# 1 "<command-line>"

# 1 "temp.c"

# 15 "temp.c"

int i = 4 > 3 ? 4 : 3;

已经将预处理命令扩展开

编译后为：

.globl _i

        .data

        .align 2

_i:

        .long   4

        .subsections_via_symbols

已经将变量i的值设置为4，说明在编译阶段已经对bigger宏进行了执行。

宏 ilog2的定义为：

#define ilog2(n) \

( \

__builtin_constant_p(n) ? ( \

(n) < 1 ? ____ilog2_NaN() : \

(n) & (1ULL << 63) ? 63 : \

(n) & (1ULL << 62) ? 62 : \

(n) & (1ULL << 61) ? 61 : \

(n) & (1ULL << 60) ? 60 : \

(n) & (1ULL << 59) ? 59 : \

(n) & (1ULL << 58) ? 58 : \

(n) & (1ULL << 57) ? 57 : \

(n) & (1ULL << 56) ? 56 : \

(n) & (1ULL << 55) ? 55 : \

(n) & (1ULL << 54) ? 54 : \

(n) & (1ULL << 53) ? 53 : \

(n) & (1ULL << 52) ? 52 : \

(n) & (1ULL << 51) ? 51 : \

(n) & (1ULL << 50) ? 50 : \

(n) & (1ULL << 49) ? 49 : \

(n) & (1ULL << 48) ? 48 : \

(n) & (1ULL << 47) ? 47 : \

(n) & (1ULL << 46) ? 46 : \

(n) & (1ULL << 45) ? 45 : \

(n) & (1ULL << 44) ? 44 : \

(n) & (1ULL << 43) ? 43 : \

(n) & (1ULL << 42) ? 42 : \

(n) & (1ULL << 41) ? 41 : \

(n) & (1ULL << 40) ? 40 : \

(n) & (1ULL << 39) ? 39 : \

(n) & (1ULL << 38) ? 38 : \

(n) & (1ULL << 37) ? 37 : \

(n) & (1ULL << 36) ? 36 : \

(n) & (1ULL << 35) ? 35 : \

(n) & (1ULL << 34) ? 34 : \

(n) & (1ULL << 33) ? 33 : \

(n) & (1ULL << 32) ? 32 : \

(n) & (1ULL << 31) ? 31 : \

(n) & (1ULL << 30) ? 30 : \

(n) & (1ULL << 29) ? 29 : \

(n) & (1ULL << 28) ? 28 : \

(n) & (1ULL << 27) ? 27 : \

(n) & (1ULL << 26) ? 26 : \

(n) & (1ULL << 25) ? 25 : \

(n) & (1ULL << 24) ? 24 : \

(n) & (1ULL << 23) ? 23 : \

(n) & (1ULL << 22) ? 22 : \

(n) & (1ULL << 21) ? 21 : \

(n) & (1ULL << 20) ? 20 : \

(n) & (1ULL << 19) ? 19 : \

(n) & (1ULL << 18) ? 18 : \

(n) & (1ULL << 17) ? 17 : \

(n) & (1ULL << 16) ? 16 : \

(n) & (1ULL << 15) ? 15 : \

(n) & (1ULL << 14) ? 14 : \

(n) & (1ULL << 13) ? 13 : \

(n) & (1ULL << 12) ? 12 : \

(n) & (1ULL << 11) ? 11 : \

(n) & (1ULL << 10) ? 10 : \

(n) & (1ULL <<  9) ?  9 : \

(n) & (1ULL <<  8) ?  8 : \

(n) & (1ULL <<  7) ?  7 : \

(n) & (1ULL <<  6) ?  6 : \

(n) & (1ULL <<  5) ?  5 : \

(n) & (1ULL <<  4) ?  4 : \

(n) & (1ULL <<  3) ?  3 : \

(n) & (1ULL <<  2) ?  2 : \

(n) & (1ULL <<  1) ?  1 : \

(n) & (1ULL <<  0) ?  0 : \

____ilog2_NaN() \

  ) : \

(sizeof(n) <= 4) ? \

__ilog2_u32(n) : \

__ilog2_u64(n) \

 )

太麻烦，可见如果n不是常数，不能在编译阶段处理的化，这种处理方式不可取，于是有了第二种处理方式。

2、如果n不是常数，则用汇编处理

unsigned long __rounddown_pow_of_two(unsigned long n)

{

return 1UL << (fls_long(n) - 1);

}

在/linux/bitops.h：

static inline unsigned fls_long(unsigned long l)

{

if (sizeof(l) == 4)

return fls(l);

return fls64(l);

}

在arch/frv/include/asm/bitops.h：

#define fls(x) \

({ \

int bit; \

\

asm(" subcc %1,gr0,gr0,icc0 \n" \

   " ckne icc0,cc4 \n" \

   " cscan.p %1,gr0,%0 ,cc4,#1 \n" \

   " csub %0,%0,%0 ,cc4,#0 \n" \

   "   csub    %2,%0,%0 ,cc4,#1 \n" \

   : "=&r"(bit) \

   : "r"(x), "r"(32) \

   : "icc0", "cc4" \

   ); \

\

bit; \

})

static inline __attribute__((const))

int fls64(u64 n)

{

union {

u64 ll;

struct { u32 h, l; };

} _;

int bit, x, y;

_.ll = n;

asm(" subcc.p %3,gr0,gr0,icc0 \n"

   " subcc %4,gr0,gr0,icc1 \n"

   " ckne icc0,cc4 \n"

   " ckne icc1,cc5 \n"

   " norcr cc4,cc5,cc6 \n"

   " csub.p %0,%0,%0 ,cc6,1 \n"

   " orcr cc5,cc4,cc4 \n"

   " andcr cc4,cc5,cc4 \n"

   " cscan.p %3,gr0,%0 ,cc4,0 \n"

   "   setlos #64,%1 \n"

   " cscan.p %4,gr0,%0 ,cc4,1 \n"

   "   setlos #32,%2 \n"

   " csub.p %1,%0,%0 ,cc4,0 \n"

   " csub %2,%0,%0 ,cc4,1 \n"

   : "=&r"(bit), "=r"(x), "=r"(y)

   : "0r"(_.h), "r"(_.l)

   : "icc0", "icc1", "cc4", "cc5", "cc6"

   );

return bit;

}

为了追求效率可见用心。