[linux-audio-dev] next power of two

[Björn Pfeiffer]

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;
>          }