LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
* [PATCH] Add a rounddown_pow_of_two() macro to log2.h.
@ 2007-01-25  9:32 Robert P. J. Day
  2007-01-26  3:20 ` Andrew Morton
  0 siblings, 1 reply; 4+ messages in thread
From: Robert P. J. Day @ 2007-01-25  9:32 UTC (permalink / raw)
  To: Linux kernel mailing list; +Cc: Andrew Morton, dhowells


  In the same way that include/linux/log2.h defines the
roundup_pow_of_two() macro, define the rounddown_pow_of_two() macro so
peopls can stop re-implementing this operation using a loop.

Signed-off-by: Robert P. J. Day <rpjday@mindspring.com>

---

  compile tested on x86 using "make allyesconfig", but there wasn't
much chance of the build failing anyway since the patch only adds the
macro definition, it doesn't change any existing code to use it.
those patches will be submitted later, bit by bit.

diff --git a/include/linux/log2.h b/include/linux/log2.h
index d02e1a5..6cf7081 100644
--- a/include/linux/log2.h
+++ b/include/linux/log2.h
@@ -52,6 +63,15 @@ unsigned long __roundup_pow_of_two(unsigned long n)
 	return 1UL << fls_long(n - 1);
 }

+/*
+ * round down to nearest power of two
+ */
+static inline __attribute__((const))
+unsigned long __rounddown_pow_of_two(unsigned long n)
+{
+	return 1UL << (fls_long(n) - 1);
+}
+
 /**
  * ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value
  * @n - parameter
@@ -154,4 +174,20 @@ unsigned long __roundup_pow_of_two(unsigned long n)
 	__roundup_pow_of_two(n)			\
  )

+/**
+ * rounddown_pow_of_two - round the given value down to nearest power of two
+ * @n - parameter
+ *
+ * round the given value down to the nearest power of two
+ * - the result is undefined when n == 0
+ * - this can be used to initialise global variables from constant data
+ */
+#define rounddown_pow_of_two(n)			\
+(						\
+	__builtin_constant_p(n) ? (		\
+		(n == 1) ? 0 :			\
+		(1UL << ilog2(n)) :		\
+	__rounddown_pow_of_two(n)		\
+ )
+
 #endif /* _LINUX_LOG2_H */

-- 
==============================================================================================
Robert P. J. Day
Linux Consulting, Training and Annoying Kernel Pedantry
Waterloo, Ontario, CANADA

http://www.fsdev.dreamhosters.com/wiki/index.php?title=Kernel_Janitor%27s_Todo_List
==============================================================================================

^ permalink raw reply	[flat|nested] 4+ messages in thread

* Re: [PATCH] Add a rounddown_pow_of_two() macro to log2.h.
  2007-01-25  9:32 [PATCH] Add a rounddown_pow_of_two() macro to log2.h Robert P. J. Day
@ 2007-01-26  3:20 ` Andrew Morton
  2007-01-26  7:24   ` Robert P. J. Day
  0 siblings, 1 reply; 4+ messages in thread
From: Andrew Morton @ 2007-01-26  3:20 UTC (permalink / raw)
  To: Robert P. J. Day; +Cc: Linux kernel mailing list, dhowells

On Thu, 25 Jan 2007 04:32:12 -0500 (EST)
"Robert P. J. Day" <rpjday@mindspring.com> wrote:

> 
>   In the same way that include/linux/log2.h defines the
> roundup_pow_of_two() macro, define the rounddown_pow_of_two() macro so
> peopls can stop re-implementing this operation using a loop.
> 
> Signed-off-by: Robert P. J. Day <rpjday@mindspring.com>
> 
> ---
> 
>   compile tested on x86 using "make allyesconfig", but there wasn't
> much chance of the build failing anyway since the patch only adds the
> macro definition, it doesn't change any existing code to use it.
> those patches will be submitted later, bit by bit.
> 
> diff --git a/include/linux/log2.h b/include/linux/log2.h
> index d02e1a5..6cf7081 100644
> --- a/include/linux/log2.h
> +++ b/include/linux/log2.h
> @@ -52,6 +63,15 @@ unsigned long __roundup_pow_of_two(unsigned long n)
>  	return 1UL << fls_long(n - 1);
>  }
> 
> +/*
> + * round down to nearest power of two
> + */
> +static inline __attribute__((const))
> +unsigned long __rounddown_pow_of_two(unsigned long n)
> +{
> +	return 1UL << (fls_long(n) - 1);
> +}

So __rounddown_pow_of_two(16) returns 8?

>  /**
>   * ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value
>   * @n - parameter
> @@ -154,4 +174,20 @@ unsigned long __roundup_pow_of_two(unsigned long n)
>  	__roundup_pow_of_two(n)			\
>   )
> 
> +/**
> + * rounddown_pow_of_two - round the given value down to nearest power of two
> + * @n - parameter
> + *
> + * round the given value down to the nearest power of two
> + * - the result is undefined when n == 0
> + * - this can be used to initialise global variables from constant data
> + */
> +#define rounddown_pow_of_two(n)			\
> +(						\
> +	__builtin_constant_p(n) ? (		\
> +		(n == 1) ? 0 :			\
> +		(1UL << ilog2(n)) :		\
> +	__rounddown_pow_of_two(n)		\
> + )

But (1UL << ilog2(16)) returns 16?


And, afiact, your __rounddown_pow_of_two() is basically equivalent to (1UL
<< ilog2(n)) anyway.  So a suitable (and less buggy) implementation might be

static inline unsigned long rounddown_pow_of_two(unsigned long n)
{
	return (n == 1) ? 0 : (1UL << ilog2(n));
}

But I'm not sure.  Please create a userspace test harness to test this
patch.

^ permalink raw reply	[flat|nested] 4+ messages in thread

* Re: [PATCH] Add a rounddown_pow_of_two() macro to log2.h.
  2007-01-26  3:20 ` Andrew Morton
@ 2007-01-26  7:24   ` Robert P. J. Day
  2007-01-26 15:57     ` Kyle Moffett
  0 siblings, 1 reply; 4+ messages in thread
From: Robert P. J. Day @ 2007-01-26  7:24 UTC (permalink / raw)
  To: Andrew Morton; +Cc: Linux kernel mailing list, dhowells

On Thu, 25 Jan 2007, Andrew Morton wrote:

> On Thu, 25 Jan 2007 04:32:12 -0500 (EST)
> "Robert P. J. Day" <rpjday@mindspring.com> wrote:

> > +/*
> > + * round down to nearest power of two
> > + */
> > +static inline __attribute__((const))
> > +unsigned long __rounddown_pow_of_two(unsigned long n)
> > +{
> > +	return 1UL << (fls_long(n) - 1);
> > +}
>
> So __rounddown_pow_of_two(16) returns 8?

it does?  but if that was true, so would 17, and 18, and 19 ...  i
didn't actually test this since it seemed so straightforward.
doesn't fls_long() return the most significant bit?  oh, wait ...
reading further ...
 >
> >  /**
> >   * ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value
> >   * @n - parameter
> > @@ -154,4 +174,20 @@ unsigned long __roundup_pow_of_two(unsigned long n)
> >  	__roundup_pow_of_two(n)			\
> >   )
> >
> > +/**
> > + * rounddown_pow_of_two - round the given value down to nearest power of two
> > + * @n - parameter
> > + *
> > + * round the given value down to the nearest power of two
> > + * - the result is undefined when n == 0
> > + * - this can be used to initialise global variables from constant data
> > + */
> > +#define rounddown_pow_of_two(n)			\
> > +(						\
> > +	__builtin_constant_p(n) ? (		\
> > +		(n == 1) ? 0 :			\
> > +		(1UL << ilog2(n)) :		\
> > +	__rounddown_pow_of_two(n)		\
> > + )
>
> But (1UL << ilog2(16)) returns 16?
>
>
> And, afiact, your __rounddown_pow_of_two() is basically equivalent to (1UL
> << ilog2(n)) anyway.  So a suitable (and less buggy) implementation might be
>
> static inline unsigned long rounddown_pow_of_two(unsigned long n)
> {
> 	return (n == 1) ? 0 : (1UL << ilog2(n));
> }

i think you're right.  it's been a long day so give me a few minutes
to convince myself.

rday

-- 
========================================================================
Robert P. J. Day
Linux Consulting, Training and Annoying Kernel Pedantry
Waterloo, Ontario, CANADA

http://www.fsdev.dreamhosters.com/wiki/index.php?title=Main_Page
========================================================================

^ permalink raw reply	[flat|nested] 4+ messages in thread

* Re: [PATCH] Add a rounddown_pow_of_two() macro to log2.h.
  2007-01-26  7:24   ` Robert P. J. Day
@ 2007-01-26 15:57     ` Kyle Moffett
  0 siblings, 0 replies; 4+ messages in thread
From: Kyle Moffett @ 2007-01-26 15:57 UTC (permalink / raw)
  To: Robert P. J. Day; +Cc: Andrew Morton, Linux kernel mailing list, dhowells

On Jan 26, 2007, at 02:24:35, Robert P. J. Day wrote:
> On Thu, 25 Jan 2007, Andrew Morton wrote:
>> On Thu, 25 Jan 2007 04:32:12 -0500 (EST)
>> "Robert P. J. Day" <rpjday@mindspring.com> wrote:
>>> +/*
>>> + * round down to nearest power of two
>>> + */
>>> +static inline __attribute__((const))
>>> +unsigned long __rounddown_pow_of_two(unsigned long n)
>>> +{
>>> +	return 1UL << (fls_long(n) - 1);
>>> +}
>>
>> So __rounddown_pow_of_two(16) returns 8?
>
> it does?  but if that was true, so would 17, and 18, and 19 ...  i  
> didn't actually test this since it seemed so straightforward.  
> doesn't fls_long() return the most significant bit?  oh, wait ...  
> reading further ...

The way that "ilog2" is defined this should be really  
straightforward, I dunno why those functions seem so
overly complicated:
   roundup_pow_of_two(x) := 1 << ilog2(2*x - 1)
   rounddown_pow_of_two(x) := 1 << ilog2(x)

Where ilog2(x) simply returns the first bit set in the word:
   ilog2(0) => undefined or -1 or something
   ilog2(1) => 0
   ilog2(2) => 1
   ilog2(3) => 1
   ilog2(4) => 2
   [...]

The results:
   roundup_pow_of_two(1) = 1    rounddown_pow_of_two(1) = 1
   roundup_pow_of_two(2) = 2    rounddown_pow_of_two(2) = 2
   roundup_pow_of_two(3) = 4    rounddown_pow_of_two(3) = 2
   roundup_pow_of_two(4) = 4    rounddown_pow_of_two(4) = 4
   roundup_pow_of_two(5) = 8    rounddown_pow_of_two(5) = 4
   [...]

Cheers,
Kyle Moffett


^ permalink raw reply	[flat|nested] 4+ messages in thread

end of thread, other threads:[~2007-01-26 15:57 UTC | newest]

Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2007-01-25  9:32 [PATCH] Add a rounddown_pow_of_two() macro to log2.h Robert P. J. Day
2007-01-26  3:20 ` Andrew Morton
2007-01-26  7:24   ` Robert P. J. Day
2007-01-26 15:57     ` Kyle Moffett

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).