iofbirddaemon / lib / bitops.c @ fe9f1a6d
History  View  Annotate  Download (1.67 KB)
1 
/*


2 
* BIRD Library  Generic Bit Operations

3 
*

4 
* (c) 1998 Martin Mares <mj@ucw.cz>

5 
*

6 
* Can be freely distributed and used under the terms of the GNU GPL.

7 
*/

8  
9 
#include "nest/bird.h" 
10 
#include "bitops.h" 
11  
12 
/**

13 
* u32_mkmask  create a bit mask

14 
* @n: number of bits

15 
*

16 
* u32_mkmask() returns an unsigned 32bit integer which binary

17 
* representation consists of @n ones followed by zeroes.

18 
*/

19 
u32 
20 
u32_mkmask(uint n) 
21 
{ 
22 
return n ? ~((1 << (32  n))  1) : 0; 
23 
} 
24  
25 
/**

26 
* u32_masklen  calculate length of a bit mask

27 
* @x: bit mask

28 
*

29 
* This function checks whether the given integer @x represents

30 
* a valid bit mask (binary representation contains first ones, then

31 
* zeroes) and returns the number of ones or 255 if the mask is invalid.

32 
*/

33 
uint 
34 
u32_masklen(u32 x) 
35 
{ 
36 
int l = 0; 
37 
u32 n = ~x; 
38  
39 
if (n & (n+1)) return 255; 
40 
if (x & 0x0000ffff) { x &= 0x0000ffff; l += 16; } 
41 
if (x & 0x00ff00ff) { x &= 0x00ff00ff; l += 8; } 
42 
if (x & 0x0f0f0f0f) { x &= 0x0f0f0f0f; l += 4; } 
43 
if (x & 0x33333333) { x &= 0x33333333; l += 2; } 
44 
if (x & 0x55555555) l++; 
45 
if (x & 0xaaaaaaaa) l++; 
46 
return l;

47 
} 
48  
49 
/**

50 
* u32_log2  compute a binary logarithm.

51 
* @v: number

52 
*

53 
* This function computes a integral part of binary logarithm of given

54 
* integer @v and returns it. The computed value is also an index of the

55 
* most significant nonzero bit position.

56 
*/

57  
58 
u32 
59 
u32_log2(u32 v) 
60 
{ 
61 
/* The code from http://wwwgraphics.stanford.edu/~seander/bithacks.html */

62 
u32 r, shift; 
63 
r = (v > 0xFFFF) << 4; v >>= r; 
64 
shift = (v > 0xFF ) << 3; v >>= shift; r = shift; 
65 
shift = (v > 0xF ) << 2; v >>= shift; r = shift; 
66 
shift = (v > 0x3 ) << 1; v >>= shift; r = shift; 
67 
r = (v >> 1);

68 
return r;

69 
} 
70 