Subject: Re: [linux-audio-dev] next power of two
From: Björn Pfeiffer (bjoern_pfeiffer_AT_gmx.de)
Date: Thu Sep 18 2003 - 20:59:32 EEST
Here's another one, using inline x86-gas.
#include <stdint.h>
// One minor difference: will give 1 for x == 0.
static __inline__ uint32_t nextPowerOfTwo_asm (uint32_t x)
{
uint32_t r;
__asm__ (
"dec %1 \n\t"
"bsrl %1,%%ecx \n\t"
"jz end \n\t"
"inc %%ecx \n\t"
"shll %%cl, %0 \n\t"
"end: "
: "=r" (r)
: "r"(x), "0" (1)
: "ecx"
);
return r;
}
I have to admit it's not nearly as elegant as the previous
solution but... hey, it's my first inline-gas-hack. :)
I'm not even sure if this will run any faster than
nextPowerOfTwo() with -O2 turned on...
The idea basically is to find the highest set bit with bsr (Bit
Scan Reverse), add one to that and return 1 shifted left by the
number.
The include/asm* headers in kernel-source and/or /usr are a very
good place to get inspired on these things, btw.
Nice online-places to look are
http://www-106.ibm.com/developerworks/linux/library/l-ia.html
http://www.delorie.com/djgpp/doc/brennan/brennan_att_inline_djgpp.html
cheers,
Björn
On Wed, Sep 17, 2003 at 02:21:32PM +0200, Maarten de Boer wrote:
> Hi,
>
> A colleague of mine found this very clever algoritm to calculate the
> next power of two for a given number. It comes from the Prophecy SDK for
> 3d game development
> http://www.twilight3d.com/modules.php?op=modload&name=Downloads&file=index
>
> Since this is a kind of thing often needed in audio processing, I wanted
> to share it with you. I certainly can not think of a faster (or more
> elegant) way of doing it.
>
> Maarten
>
> //////
> /// Returns the closest power-of-two number greater or equal
> /// to n for the given (unsigned) integer n.
> /// Will return 0 when n = 0 and 1 when n = 1.
> //////
> inline uint32_t nextPowerOfTwo(uint32_t n)
> {
> --n;
> n |= n >> 16;
> n |= n >> 8;
> n |= n >> 4;
> n |= n >> 2;
> n |= n >> 1;
> ++n;
> return n;
> }
This archive was generated by hypermail 2b28 : Thu Sep 18 2003 - 21:21:24 EEST