| 1 | #ifndef _LINUX_LOG2_H
|
|---|
| 2 | #define _LINUX_LOG2_H
|
|---|
| 3 |
|
|---|
| 4 | #include <linux/bitops.h>
|
|---|
| 5 | #include <linux/types.h>
|
|---|
| 6 |
|
|---|
| 7 | /*
|
|---|
| 8 | * Determine whether some value is a power of two, where zero is
|
|---|
| 9 | * *not* considered a power of two.
|
|---|
| 10 | */
|
|---|
| 11 |
|
|---|
| 12 | static inline
|
|---|
| 13 | bool is_power_of_2(unsigned long n)
|
|---|
| 14 | {
|
|---|
| 15 | return (n != 0 && ((n & (n - 1)) == 0));
|
|---|
| 16 | }
|
|---|
| 17 |
|
|---|
| 18 | /**
|
|---|
| 19 | * __roundup_pow_of_two() - round up to nearest power of two
|
|---|
| 20 | * @n: value to round up
|
|---|
| 21 | */
|
|---|
| 22 | static inline /*__attribute__((const))*/
|
|---|
| 23 | unsigned long __roundup_pow_of_two(unsigned long n)
|
|---|
| 24 | {
|
|---|
| 25 | return 1UL << fls_long(n - 1);
|
|---|
| 26 | }
|
|---|
| 27 |
|
|---|
| 28 | /**
|
|---|
| 29 | * __rounddown_pow_of_two() - round down to nearest power of two
|
|---|
| 30 | * @n: value to round down
|
|---|
| 31 | */
|
|---|
| 32 | static inline /*__attribute__((const))*/
|
|---|
| 33 | unsigned long __rounddown_pow_of_two(unsigned long n)
|
|---|
| 34 | {
|
|---|
| 35 | return 1UL << (fls_long(n) - 1);
|
|---|
| 36 | }
|
|---|
| 37 |
|
|---|
| 38 | /***********************************************/
|
|---|
| 39 | /* Locate the position of the highest bit set. */
|
|---|
| 40 | /* A binary search is used. The result is an */
|
|---|
| 41 | /* approximation of log2(n) [the integer part] */
|
|---|
| 42 | /***********************************************/
|
|---|
| 43 | static inline int ilog2(unsigned long n)
|
|---|
| 44 | {
|
|---|
| 45 | int i = (-1);
|
|---|
| 46 |
|
|---|
| 47 | /* Is there a bit on in the high word? */
|
|---|
| 48 | /* Else, all the high bits are already zero. */
|
|---|
| 49 | if (n & 0xffff0000) {
|
|---|
| 50 | i += 16; /* Update our search position */
|
|---|
| 51 | n >>= 16; /* Shift out lower (irrelevant) bits */
|
|---|
| 52 | }
|
|---|
| 53 | /* Is there a bit on in the high byte of the current word? */
|
|---|
| 54 | /* Else, all the high bits are already zero. */
|
|---|
| 55 | if (n & 0xff00) {
|
|---|
| 56 | i += 8; /* Update our search position */
|
|---|
| 57 | n >>= 8; /* Shift out lower (irrelevant) bits */
|
|---|
| 58 | }
|
|---|
| 59 | /* Is there a bit on in the current nybble? */
|
|---|
| 60 | /* Else, all the high bits are already zero. */
|
|---|
| 61 | if (n & 0xf0) {
|
|---|
| 62 | i += 4; /* Update our search position */
|
|---|
| 63 | n >>= 4; /* Shift out lower (irrelevant) bits */
|
|---|
| 64 | }
|
|---|
| 65 | /* Is there a bit on in the high 2 bits of the current nybble? */
|
|---|
| 66 | /* 0xc is 1100 in binary... */
|
|---|
| 67 | /* Else, all the high bits are already zero. */
|
|---|
| 68 | if (n & 0xc) {
|
|---|
| 69 | i += 2; /* Update our search position */
|
|---|
| 70 | n >>= 2; /* Shift out lower (irrelevant) bits */
|
|---|
| 71 | }
|
|---|
| 72 | /* Is the 2nd bit on? [ 0x2 is 0010 in binary...] */
|
|---|
| 73 | /* Else, all the 2nd bit is already zero. */
|
|---|
| 74 | if (n & 0x2) {
|
|---|
| 75 | i++; /* Update our search position */
|
|---|
| 76 | n >>= 1; /* Shift out lower (irrelevant) bit */
|
|---|
| 77 | }
|
|---|
| 78 | /* Is the lowest bit set? */
|
|---|
| 79 | if (n)
|
|---|
| 80 | i++; /* Update our search position */
|
|---|
| 81 | return i;
|
|---|
| 82 | }
|
|---|
| 83 |
|
|---|
| 84 | /**
|
|---|
| 85 | * roundup_pow_of_two - round the given value up to nearest power of two
|
|---|
| 86 | * @n: parameter
|
|---|
| 87 | *
|
|---|
| 88 | * round the given value up to the nearest power of two
|
|---|
| 89 | * - the result is undefined when n == 0
|
|---|
| 90 | * - this can be used to initialise global variables from constant data
|
|---|
| 91 | */
|
|---|
| 92 | #define roundup_pow_of_two(n) \
|
|---|
| 93 | ( \
|
|---|
| 94 | __roundup_pow_of_two(n) \
|
|---|
| 95 | )
|
|---|
| 96 |
|
|---|
| 97 | /**
|
|---|
| 98 | * rounddown_pow_of_two - round the given value down to nearest power of two
|
|---|
| 99 | * @n: parameter
|
|---|
| 100 | *
|
|---|
| 101 | * round the given value down to the nearest power of two
|
|---|
| 102 | * - the result is undefined when n == 0
|
|---|
| 103 | * - this can be used to initialise global variables from constant data
|
|---|
| 104 | */
|
|---|
| 105 | #define rounddown_pow_of_two(n) \
|
|---|
| 106 | ( \
|
|---|
| 107 | __rounddown_pow_of_two(n) \
|
|---|
| 108 | )
|
|---|
| 109 |
|
|---|
| 110 | #endif /* _LINUX_LOG2_H */
|
|---|
