At first,hello and from me to the list.
To the point now:
On Wed, 10 Aug 2005, Oliver Korpilla wrote:
Hello!
Upon looking for a function/macro for computing the logarithm to the base 2 I
found multiple implementations in the kernel source (2.6.10-rc3), but none
fitting my requirements:
* generic (will compute logarithm instead of a table lookup)
* portable (unlike e.g. ceil_log2 only in asm-alpha)
It kind of looks like everyone is reinventing the wheel with several
implementations under differing names are within the kernel. Sometimes they
are hardcoded (results already put in as constant), sometimes a lookup table
is used, and several slightly different algorithms with bit shift are used.
Accurate logarithm algorithms are costly,and I don't think
are needed from kernel developers, usually a approximation is enough.
So if u want something realy accurate,
u must look how it is implemented on libc.
The easiest(and fastest) way to compute a logarithm
(with or without base 2) is to make bit shifts.
Is this desirable? While it may be some reduction for special cases using a
table (like in the log2_2048 function I found - it computes only a certain of
log2 and multiplies this with 2048), wouldn't a more generic implementation
like ceil_log2 and floor_log2 not be desirable for all platforms?
U can simply use the functions of bitops.h (of asm-alpha) inline
functions, removing the alpha special comands:
static inline int floor_log2(unsigned long word)
{
long bit;
//#if defined (_alpha_)..
// removed alpha code
//#else
for (bit = -1; word ; bit++)
word >>= 1;
return bit;
//#endif
}
static inline int ceil_log2(unsigned int word)
{
long bit = floor_log2(word);
return bit + (word > (1UL << bit));
}
Or have I simply overlooked the right function?
Thanks and with kind regards,
Oliver Korpilla
Hope to help you.
Stavros Passas
--
Kernelnewbies: Help each other learn about the Linux kernel.
Archive: http://mail.nl.linux.org/kernelnewbies/
FAQ: http://kernelnewbies.org/faq/
