Add the inline function "is_power_of_2()" to log2.h, where the value
zero is *not* considered to be a power of two.
Signed-off-by: Robert P. J. Day <[email protected]>
---
while people are coming up with more and more clever ways to do
rounding, we can at least add the check for power-of-2 now, so we can
start the cleanup.
arch/powerpc/mm/pgtable_32.c | 5 +----
arch/ppc/mm/pgtable.c | 5 +----
arch/ppc/syslib/ppc85xx_rio.c | 2 --
drivers/net/gianfar_ethtool.c | 2 --
include/linux/log2.h | 11 +++++++++++
5 files changed, 13 insertions(+), 12 deletions(-)
diff --git a/arch/powerpc/mm/pgtable_32.c b/arch/powerpc/mm/pgtable_32.c
index 1891dbe..bd02272 100644
--- a/arch/powerpc/mm/pgtable_32.c
+++ b/arch/powerpc/mm/pgtable_32.c
@@ -294,11 +294,8 @@ void __init mapin_ram(void)
}
}
-/* is x a power of 2? */
-#define is_power_of_2(x) ((x) != 0 && (((x) & ((x) - 1)) == 0))
-
/* is x a power of 4? */
-#define is_power_of_4(x) ((x) != 0 && (((x) & (x-1)) == 0) && (ffs(x) & 1))
+#define is_power_of_4(x) is_power_of_2(x) && (ffs(x) & 1))
/*
* Set up a mapping for a block of I/O.
diff --git a/arch/ppc/mm/pgtable.c b/arch/ppc/mm/pgtable.c
index 354a940..82b06a1 100644
--- a/arch/ppc/mm/pgtable.c
+++ b/arch/ppc/mm/pgtable.c
@@ -313,11 +313,8 @@ void __init mapin_ram(void)
}
}
-/* is x a power of 2? */
-#define is_power_of_2(x) ((x) != 0 && (((x) & ((x) - 1)) == 0))
-
/* is x a power of 4? */
-#define is_power_of_4(x) ((x) != 0 && (((x) & (x-1)) == 0) && (ffs(x) & 1))
+#define is_power_of_4(x) is_power_of_2(x) && (ffs(x) & 1))
/*
* Set up a mapping for a block of I/O.
diff --git a/arch/ppc/syslib/ppc85xx_rio.c b/arch/ppc/syslib/ppc85xx_rio.c
index 05b0e94..2b09780 100644
--- a/arch/ppc/syslib/ppc85xx_rio.c
+++ b/arch/ppc/syslib/ppc85xx_rio.c
@@ -59,8 +59,6 @@
#define DBELL_TID(x) (*(u8 *)(x + DOORBELL_TID_OFFSET))
#define DBELL_INF(x) (*(u16 *)(x + DOORBELL_INFO_OFFSET))
-#define is_power_of_2(x) (((x) & ((x) - 1)) == 0)
-
struct rio_atmu_regs {
u32 rowtar;
u32 pad1;
diff --git a/drivers/net/gianfar_ethtool.c b/drivers/net/gianfar_ethtool.c
index 6d71bea..0d6943d 100644
--- a/drivers/net/gianfar_ethtool.c
+++ b/drivers/net/gianfar_ethtool.c
@@ -42,8 +42,6 @@
#include "gianfar.h"
-#define is_power_of_2(x) ((x) != 0 && (((x) & ((x) - 1)) == 0))
-
extern void gfar_start(struct net_device *dev);
extern int gfar_clean_rx_ring(struct net_device *dev, int rx_work_limit);
diff --git a/include/linux/log2.h b/include/linux/log2.h
index d02e1a5..99922be 100644
--- a/include/linux/log2.h
+++ b/include/linux/log2.h
@@ -44,6 +44,17 @@ int __ilog2_u64(u64 n)
#endif
/*
+ * Determine whether some value is a power of two, where zero is
+ * *not* considered a power of two.
+ */
+
+static inline __attribute__((const))
+bool is_power_of_2(unsigned long n)
+{
+ return (n != 0 && ((n & (n - 1)) == 0));
+}
+
+/*
* round up to nearest power of two
*/
static inline __attribute__((const))
--
========================================================================
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
========================================================================
Robert P. J. Day wrote:
> Add the inline function "is_power_of_2()" to log2.h, where the value
> zero is *not* considered to be a power of two.
>
> Signed-off-by: Robert P. J. Day <[email protected]>
>
> /*
> + * Determine whether some value is a power of two, where zero is
> + * *not* considered a power of two.
> + */
Why the qualifier? Zero *is* not a power of 2, is it?
> +
> +static inline __attribute__((const))
> +bool is_power_of_2(unsigned long n)
> +{
> + return (n != 0 && ((n & (n - 1)) == 0));
> +}
> +
> +/*
> * round up to nearest power of two
> */
> static inline __attribute__((const))
--
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com
On Tue, 30 Jan 2007, Nick Piggin wrote:
> Robert P. J. Day wrote:
> > Add the inline function "is_power_of_2()" to log2.h, where the value
> > zero is *not* considered to be a power of two.
>
> >
> > Signed-off-by: Robert P. J. Day <[email protected]>
> >
> > /*
> > + * Determine whether some value is a power of two, where zero is
> > + * *not* considered a power of two.
> > + */
>
> Why the qualifier? Zero *is* not a power of 2, is it?
no, but it bears repeating since some developers might think it *is*.
if you peruse the current kernel code, you'll find some tests of the
simpler form:
((n & (n - 1)) == 0))
which is clearly testing for "power of twoness" but which will return
true for a value of zero. that's wrong, and it's why it's emphasized
in the comment.
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
========================================================================
>> Why the qualifier? Zero *is* not a power of 2, is it?
No, it is not:
In[1]:= Solve[2^n == 0, n]
Out[1]= {}
So says Mathematica5.
Jan
--
ft: http://freshmeat.net/p/chaostables/
On Tue, 30 Jan 2007, Jan Engelhardt wrote:
>
> >> Why the qualifier? Zero *is* not a power of 2, is it?
>
> No, it is not:
>
> In[1]:= Solve[2^n == 0, n]
>
> Out[1]= {}
>
> So says Mathematica5.
oooookay, that's kind of like taking a sandblaster to a soup cracker.
seriously, though, there is the potential of breaking something with
this change since you can see how there is some inconsistency in how
it's done *now* just for powerpc which, in some places, defines its
own versions of this:
./arch/ppc/mm/pgtable.c:
#define is_power_of_2(x) ((x) != 0 && (((x) & ((x) - 1)) == 0))
./arch/ppc/syslib/ppc85xx_rio.c:
#define is_power_of_2(x) (((x) & ((x) - 1)) == 0)
./arch/powerpc/mm/pgtable_32.c:
#define is_power_of_2(x) ((x) != 0 && (((x) & ((x) - 1)) == 0))
note how the first and third macros *won't* consider zero a power of
two, while the second one *will*. hence the need for a single
standard for all of this, just to play it safe.
rday
p.s. in case you missed it, that was a not-so-subtle plea to please
just apply this patch so we can move on.
--
========================================================================
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
========================================================================
On Jan 30 2007 09:45, Robert P. J. Day wrote:
>On Tue, 30 Jan 2007, Jan Engelhardt wrote:
>>
>> >> Why the qualifier? Zero *is* not a power of 2, is it?
>>
>> No, it is not:
>>
>> In[1]:= Solve[2^n == 0, n]
>>
>> Out[1]= {}
>>
>> So says Mathematica5.
>
>oooookay, that's kind of like taking a sandblaster to a soup cracker.
Hehe. Well, there is a non-representable solution:
In[2]:= 2^-Infinity
Out[2]= 0
>seriously, though, there is the potential of breaking something with
>this change since you can see how there is some inconsistency in how
>it's done *now* just for powerpc which, in some places, defines its
>own versions of this:
>
>./arch/ppc/mm/pgtable.c:
> #define is_power_of_2(x) ((x) != 0 && (((x) & ((x) - 1)) == 0))
>./arch/ppc/syslib/ppc85xx_rio.c:
> #define is_power_of_2(x) (((x) & ((x) - 1)) == 0)
>./arch/powerpc/mm/pgtable_32.c:
> #define is_power_of_2(x) ((x) != 0 && (((x) & ((x) - 1)) == 0))
>
>note how the first and third macros *won't* consider zero a power of
>two, while the second one *will*. hence the need for a single
>standard for all of this, just to play it safe.
Hmpf. Perhaps a second macro "is_intdivisible_by_power_of_2" or so could
catch the "am I zero or 2^n" question.
Jan
--
ft: http://freshmeat.net/p/chaostables/
On Tue, 30 Jan 2007, Jan Engelhardt wrote:
>
> On Jan 30 2007 09:45, Robert P. J. Day wrote:
> >seriously, though, there is the potential of breaking something with
> >this change since you can see how there is some inconsistency in how
> >it's done *now* just for powerpc which, in some places, defines its
> >own versions of this:
> >
> >./arch/ppc/mm/pgtable.c:
> > #define is_power_of_2(x) ((x) != 0 && (((x) & ((x) - 1)) == 0))
> >./arch/ppc/syslib/ppc85xx_rio.c:
> > #define is_power_of_2(x) (((x) & ((x) - 1)) == 0)
> >./arch/powerpc/mm/pgtable_32.c:
> > #define is_power_of_2(x) ((x) != 0 && (((x) & ((x) - 1)) == 0))
> >
> >note how the first and third macros *won't* consider zero a power of
> >two, while the second one *will*. hence the need for a single
> >standard for all of this, just to play it safe.
>
> Hmpf. Perhaps a second macro "is_intdivisible_by_power_of_2" or so could
> catch the "am I zero or 2^n" question.
no. if that's really what the programmer wants, they can code it that
way explicitly. let's not make this overly obscure.
rday
Robert P. J. Day wrote:
> On Tue, 30 Jan 2007, Nick Piggin wrote:
>
>
>>Robert P. J. Day wrote:
>>
>>> Add the inline function "is_power_of_2()" to log2.h, where the value
>>>zero is *not* considered to be a power of two.
>>
>>>Signed-off-by: Robert P. J. Day <[email protected]>
>>>
>>> /*
>>>+ * Determine whether some value is a power of two, where zero is
>>>+ * *not* considered a power of two.
>>>+ */
>>
>>Why the qualifier? Zero *is* not a power of 2, is it?
>
>
> no, but it bears repeating since some developers might think it *is*.
> if you peruse the current kernel code, you'll find some tests of the
> simpler form:
>
> ((n & (n - 1)) == 0))
>
> which is clearly testing for "power of twoness" but which will return
> true for a value of zero. that's wrong, and it's why it's emphasized
> in the comment.
I would have thought you'd comment the broken ones, but that's just me.
--
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com
On Wed, 31 Jan 2007, Nick Piggin wrote:
> Robert P. J. Day wrote:
> > On Tue, 30 Jan 2007, Nick Piggin wrote:
> >
> >
> > > Robert P. J. Day wrote:
> > >
> > > > Add the inline function "is_power_of_2()" to log2.h, where the value
> > > > zero is *not* considered to be a power of two.
> > >
> > > > Signed-off-by: Robert P. J. Day <[email protected]>
> > > >
> > > > /*
> > > > + * Determine whether some value is a power of two, where zero is
> > > > + * *not* considered a power of two.
> > > > + */
> > >
> > > Why the qualifier? Zero *is* not a power of 2, is it?
> >
> >
> > no, but it bears repeating since some developers might think it *is*.
> > if you peruse the current kernel code, you'll find some tests of the
> > simpler form:
> >
> > ((n & (n - 1)) == 0))
> >
> > which is clearly testing for "power of twoness" but which will
> > return true for a value of zero. that's wrong, and it's why it's
> > emphasized in the comment.
>
> I would have thought you'd comment the broken ones, but that's just
> me.
good point, so let's just sum up here. (man, it's hard to believe
that something this simple could drag on so long. i feel like i'm
discussing free device driver development or something. :-)
the new is_power_of_2() macro is defined as:
(n != 0 && ((n & (n - 1)) == 0))
which (correctly, IMHO) does *not* identify zero as a power of two.
if someone truly wants *that* test, they can write it themselves:
if (x == 0 || is_power_of_2(x))
this means that, if someone wants to start rewriting those tests in
the source tree, every time they run across an apparent "power of two"
test of the simpler form:
(n & (n - 1))
they have to ask themselves, "ok, did this coder mean to include zero
or not?" in some cases, it's probably not going to be obvious.
(maybe the maintainers could do a quick check themselves and make the
substitution 'cuz, once the kernel janitors get ahold of this, you
never know what hilarity will ensue. :-)
as far as the patch itself i submitted is concerned, the *only*
place that changed the existing semantics was here:
=================================================
--- a/arch/ppc/syslib/ppc85xx_rio.c
+++ b/arch/ppc/syslib/ppc85xx_rio.c
@@ -59,8 +59,6 @@
#define DBELL_TID(x) (*(u8 *)(x + DOORBELL_TID_OFFSET))
#define DBELL_INF(x) (*(u16 *)(x + DOORBELL_INFO_OFFSET))
-#define is_power_of_2(x) (((x) & ((x) - 1)) == 0)
-
struct rio_atmu_regs {
u32 rowtar;
u32 pad1;
=================================================
so if the powerpc people are ok with that, then the patch itself
should be fine, and it's only the upcoming substitutions in the source
tree that will have to be checked carefully, one by one.
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
========================================================================
On Tue, January 30, 2007 3:12 pm, Jan Engelhardt wrote:
>
>>> Why the qualifier? Zero *is* not a power of 2, is it?
>
> No, it is not:
>
> In[1]:= Solve[2^n == 0, n]
>
> Out[1]= {}
>
> So says Mathematica5.
As a side note, I would just like to point out that Mathematica does not
deal with modular arithmetic by default (which programmers very much do).
In fact, in modular arithmetic, zero IS a power of two.
2^n = 0 (mod 2^n)
To see if it holds for bytes, substitute n = 8, and you get 2^8 = 0 (mod
256). In other words: Zero is the eighth power of two modulo 256.
Modular arithmetic is, however, very often a source of errors in
programming (unchecked-for overflows and underflows), and it is
questionable whether the programmer would really want 0 reported as a
power of two.
Vegard
On Wed, 31 Jan 2007, Vegard Nossum wrote:
> On Tue, January 30, 2007 3:12 pm, Jan Engelhardt wrote:
> >
> >>> Why the qualifier? Zero *is* not a power of 2, is it?
> >
> > No, it is not:
> >
> > In[1]:= Solve[2^n == 0, n]
> >
> > Out[1]= {}
> >
> > So says Mathematica5.
>
> As a side note, I would just like to point out that Mathematica does
> not deal with modular arithmetic by default (which programmers very
> much do). In fact, in modular arithmetic, zero IS a power of two.
>
> 2^n = 0 (mod 2^n)
>
> To see if it holds for bytes, substitute n = 8, and you get 2^8 = 0
> (mod 256). In other words: Zero is the eighth power of two modulo
> 256.
that's a bit esoteric but, yes, you make a good point.
> Modular arithmetic is, however, very often a source of errors in
> programming (unchecked-for overflows and underflows), and it is
> questionable whether the programmer would really want 0 reported as
> a power of two.
precisely. given the definition of "is_power_of_2()" that's been
published, some people will (quite correctly) point out that using
that macro in place of the test "(n & (n - 1))" isn't quite the same
thing. and they would be correct.
but one wonders how many programmers have been using that very test
"((n & (n - 1))" without realizing that it would accept zero, and that
it has been accepting zero all this time, perhaps leading to weird and
inexplicable errors.
rewriting that test as "is_power_of_2()" may, in fact, cause some
things to suddenly break, but perhaps those are things that should
have been *forced* to break anyway, to identify where the condition
check was incorrect all this time, and someone's just been lucky, or
something like that.
***NOTE***: and that's why i suggested that the individual
maintainers might want to make this substitution themselves, to make
sure everything continues to work. because if you leave it as a
project for the kernel janitors, they might not realize what you had
in mind. so it's in your best interest to start cleaning this up on
your own.
just my $0.02 (Cdn.)
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
========================================================================
Nick Piggin <[email protected]> wrote:
> > + * Determine whether some value is a power of two, where zero is
> > + * *not* considered a power of two.
> > + */
>
> Why the qualifier? Zero *is* not a power of 2, is it?
The qualifier is worth leaving in the comment, just so that people who want to
use the function can be certain what it'll do for them.
David
Robert P. J. Day <[email protected]> wrote:
> +#define is_power_of_4(x) is_power_of_2(x) && (ffs(x) & 1))
If this is such a commonly implemented op, it should probably be implemented
globally too.
I also wonder if there's some better way of implementing it than this, but I
can't think of one offhand.
David
On Thu, 1 Feb 2007, David Howells wrote:
>
> Robert P. J. Day <[email protected]> wrote:
>
> > +#define is_power_of_4(x) is_power_of_2(x) && (ffs(x) & 1))
>
> If this is such a commonly implemented op, it should probably be implemented
> globally too.
there are only two checks of the form "is_power_of_4" in the entire
tree, and they're both in the power pc stuff, so i doubt it's worth
trying to formalize that in any way.
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
========================================================================
On Thu, 1 Feb 2007, David Howells wrote:
> Robert P. J. Day <[email protected]> wrote:
>
> > +#define is_power_of_4(x) is_power_of_2(x) && (ffs(x) & 1))
>
> If this is such a commonly implemented op, it should probably be implemented
> globally too.
>
> I also wonder if there's some better way of implementing it than this, but I
> can't think of one offhand.
#define is_power_of_2_or_zero(x) ((x & (x-1))==0)
#define is_power_of_4(x) (is_power_of_2_or_zero(x) \
&& (x & ((typeof(x))0x55555555)))
?
Tim
On Thu, 01 Feb 2007 13:39:15 +0100, Tim Schmielau said:
> #define is_power_of_4(x) (is_power_of_2_or_zero(x) \
> && (x & ((typeof(x))0x55555555)))
Those 5's are going to need more magic if x is a 64-bit typeof?
On Thu, 1 Feb 2007, [email protected] wrote:
> On Thu, 01 Feb 2007 13:39:15 +0100, Tim Schmielau said:
> > #define is_power_of_4(x) (is_power_of_2_or_zero(x) \
> > && (x & ((typeof(x))0x55555555)))
>
> Those 5's are going to need more magic if x is a 64-bit typeof?
Yeah, I can't count. Make that
#define is_power_of_2_or_zero(x) ((x & (x-1))==0)
#define is_power_of_4(x) (is_power_of_2_or_zero(x) \
&& (x & ((typeof(x))0x5555555555555555ull)))
of course.
Thanks,
Tim
Hello,
Please fix the parentheses thing in both arch/powerpc/mm/pgtable_32.c and
arch/ppc/mm/pgtable.c.
> +#define is_power_of_4(x) is_power_of_2(x) && (ffs(x) & 1))
Regards,
Mariusz Kozlowski
On Feb 20, 2007, at 9:29 AM, Mariusz Kozlowski wrote:
> Hello,
>
> Please fix the parentheses thing in both arch/powerpc/mm/
> pgtable_32.c and
> arch/ppc/mm/pgtable.c.
>
>> +#define is_power_of_4(x) is_power_of_2(x) && (ffs(x) & 1))
These should be fixed and pushed upstream by now.
- k
Hello,
> > Please fix the parentheses thing in both arch/powerpc/mm/
> > pgtable_32.c and
> > arch/ppc/mm/pgtable.c.
> >
> >> +#define is_power_of_4(x) is_power_of_2(x) && (ffs(x) & 1))
>
> These should be fixed and pushed upstream by now.
Great. Thanks.
Regards,
Mariusz Kozlowski
Robert P. J. Day wrote:
>
> seriously, though, there is the potential of breaking something with
> this change since you can see how there is some inconsistency in how
> it's done *now* just for powerpc which, in some places, defines its
> own versions of this:
>
> ./arch/ppc/mm/pgtable.c:
> #define is_power_of_2(x) ((x) != 0 && (((x) & ((x) - 1)) == 0))
> ./arch/ppc/syslib/ppc85xx_rio.c:
> #define is_power_of_2(x) (((x) & ((x) - 1)) == 0)
> ./arch/powerpc/mm/pgtable_32.c:
> #define is_power_of_2(x) ((x) != 0 && (((x) & ((x) - 1)) == 0))
>
> note how the first and third macros *won't* consider zero a power of
> two, while the second one *will*. hence the need for a single
> standard for all of this, just to play it safe.
>
I suspect the reason the test for zero was omitted is because the author
didn't want the extra cost (the test for zero needs an extra branch on a
lot of architectures.)
-hpa