[KJ] powers of 2, and the boundary case of zero

[KJ] powers of 2, and the boundary case of zero

[Robert P. J. Day]

  yesterday, i made the off-the-cuff suggestion that you could get
more readable code by replacing the numerous tests of the form "(x &
(x - 1))" with the appropriate power-of-2 test macro, something like:

  #define is_power_of_2(x) (((x) & ((x) - 1)) = 0)

however, i didn't think far enough ahead to wonder how to treat the
boundary case of zero.

  should zero be considered a power of 2 or not?  according to the
above test, it *would* be.  however, there are already some
definitions of that macro in the kernel tree:

  $ grep -r is_power_of_2 .

where the tests specifically disqualify zero from being considered a
power of two, as in:

  #define ... ((x) != 0 && (((x) & ((x) - 1)) = 0))
               ^^^^^^^^
                 DON'T consider zero a power of two!

but all this makes one wonder ... if you see some code that just tests
the expression "(x & (x - 1))", did that programmer understand how
zero would be treated?

  in some cases, it's clear that he/she did, as in:

./fs/hfsplus/btree.c:   if (!size || size & (size - 1))

so whoever wrote the above code to recognize *invalid* values clearly
understood that boundary condition.  but what about, say:

  ./fs/jbd/revoke.c:      J_ASSERT ((hash_size & (hash_size-1)) = 0);

clearly, the above assertion is asserting that "hash_size" should be a
power of 2, but did the programmer realize that a value of zero would
*also* be considered valid?  i have no idea.  could this represent a
possible error?  who knows?  is a hash size of zero meaningful?
according to the above assertion, it would be.

  in any event, i didn't mean to ramble, but it struck me how making
what seemed like an innocuous change suddenly became a bit more
complicated given that boundary case of zero, and how different
programmers might have made different assumptions about it.

rday

p.s.  personally, i would define an "is_power_of_2" macro to
explicitly reject zero, the way the current definitions do.
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Richard Knutsson]

Robert P. J. Day wrote:
>   yesterday, i made the off-the-cuff suggestion that you could get
> more readable code by replacing the numerous tests of the form "(x &
> (x - 1))" with the appropriate power-of-2 test macro, something like:
>
>   #define is_power_of_2(x) (((x) & ((x) - 1)) = 0)
>
> however, i didn't think far enough ahead to wonder how to treat the
> boundary case of zero.
>
>   should zero be considered a power of 2 or not?  according to the
> above test, it *would* be.  however, there are already some
> definitions of that macro in the kernel tree:
>
>   $ grep -r is_power_of_2 .
>
> where the tests specifically disqualify zero from being considered a
> power of two, as in:
>
>   #define ... ((x) != 0 && (((x) & ((x) - 1)) = 0))
>                ^^^^^^^^
>                  DON'T consider zero a power of two!
>
> but all this makes one wonder ... if you see some code that just tests
> the expression "(x & (x - 1))", did that programmer understand how
> zero would be treated?
>
>   in some cases, it's clear that he/she did, as in:
>
> ./fs/hfsplus/btree.c:   if (!size || size & (size - 1))
>
> so whoever wrote the above code to recognize *invalid* values clearly
> understood that boundary condition.  but what about, say:
>
>   ./fs/jbd/revoke.c:      J_ASSERT ((hash_size & (hash_size-1)) = 0);
>
> clearly, the above assertion is asserting that "hash_size" should be a
> power of 2, but did the programmer realize that a value of zero would
> *also* be considered valid?  i have no idea.  could this represent a
> possible error?  who knows?  is a hash size of zero meaningful?
> according to the above assertion, it would be.
>
>   in any event, i didn't mean to ramble, but it struck me how making
> what seemed like an innocuous change suddenly became a bit more
> complicated given that boundary case of zero, and how different
> programmers might have made different assumptions about it.
>
> rday
>
> p.s.  personally, i would define an "is_power_of_2" macro to
> explicitly reject zero, the way the current definitions do.
>   
I agree! But should it not be "IS_POWER_OF_2" to reflect it is a macro?

However, I think the only thing is to check all the occurrences of the 
(x & (x-1)) and see what it really is suppose to be (and if possible, 
ask the maintainer).

What about something like:

#define LESS_THEN_2_BITS(x)  (x & (x - 1))
#define IS_POWER_OF_2(x)   (x != 0 && LESS_THEN_2_BITS(x))

(better names maybe...)

Richard Knutsson

_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Robert P. J. Day]

On Tue, 9 Jan 2007, Richard Knutsson wrote:

> Robert P. J. Day wrote:

... big snip involving power of 2 stuff ...

> > p.s.  personally, i would define an "is_power_of_2" macro to
> > explicitly reject zero, the way the current definitions do.
> >
> I agree! But should it not be "IS_POWER_OF_2" to reflect it is a
> macro?

not necessarily.  currently, the aesthetics of macro names is a bit
inconsistent, as in kernel.h:

  #define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))
  #define roundup(x, y) ((((x) + ((y) - 1)) / (y)) * (y))

and, given that there is already a precedent (albeit a small one) for
the lower case form, i'd be tempted to keep it like that, *if*
anything is to be done along those lines.

> However, I think the only thing is to check all the occurrences of
> the (x & (x-1)) and see what it really is suppose to be (and if
> possible, ask the maintainer).

i agree -- each case should be examined to see what the intent was.
in some cases, the code can be seriously obscure, as in
drivers/pcmcia/i82365.c:

      if (!poll_interval) {
        u_int tmp = (mask & 0xff20);
        tmp = tmp & (tmp-1);		// power of 2 test?
        if ((tmp & (tmp-1)) = 0)       // and test again???
            poll_interval = HZ;

in the case of the above, that first assignment is not actually
testing, it's calculating the bit mask.  the *second* expression
represents a power-of-2 test, though, and it would be fair to replace
that with the macro invocation.

> What about something like:
>
> #define LESS_THEN_2_BITS(x)  (x & (x - 1))
> #define IS_POWER_OF_2(x)   (x != 0 && LESS_THEN_2_BITS(x))

i'm not sure i'd bother with the "LESS_THAN_2_BITS" macro, since i
doubt it would have widespread application.  in any event, this is
just something to think about for future consideration.

rday
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Richard Knutsson]

Robert P. J. Day wrote:
> On Tue, 9 Jan 2007, Richard Knutsson wrote:
>
>   
>> Robert P. J. Day wrote:
>>     
>
> ... big snip involving power of 2 stuff ...
>
>   
>>> p.s.  personally, i would define an "is_power_of_2" macro to
>>> explicitly reject zero, the way the current definitions do.
>>>
>>>       
>> I agree! But should it not be "IS_POWER_OF_2" to reflect it is a
>> macro?
>>     
>
> not necessarily.  currently, the aesthetics of macro names is a bit
> inconsistent, as in kernel.h:
>
>   #define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))
>   #define roundup(x, y) ((((x) + ((y) - 1)) / (y)) * (y))
>
> and, given that there is already a precedent (albeit a small one) for
> the lower case form, i'd be tempted to keep it like that, *if*
> anything is to be done along those lines.
>   
Just quoting "CodingStyle" :)
>> However, I think the only thing is to check all the occurrences of
>> the (x & (x-1)) and see what it really is suppose to be (and if
>> possible, ask the maintainer).
>>     
>
> i agree -- each case should be examined to see what the intent was.
> in some cases, the code can be seriously obscure, as in
> drivers/pcmcia/i82365.c:
>
>       if (!poll_interval) {
>         u_int tmp = (mask & 0xff20);
>         tmp = tmp & (tmp-1);		// power of 2 test?
>         if ((tmp & (tmp-1)) = 0)       // and test again???
>             poll_interval = HZ;
>
> in the case of the above, that first assignment is not actually
> testing, it's calculating the bit mask.  the *second* expression
> represents a power-of-2 test, though, and it would be fair to replace
> that with the macro invocation.
>
>   
>> What about something like:
>>
>> #define LESS_THEN_2_BITS(x)  (x & (x - 1))
>>     
Oops, forgot a '= 0' there...
>> #define IS_POWER_OF_2(x)   (x != 0 && LESS_THEN_2_BITS(x))
>>     
>
> i'm not sure i'd bother with the "LESS_THAN_2_BITS" macro, since i
> doubt it would have widespread application.  in any event, this is
> just something to think about for future consideration.
>   
So just leaving those who are (with right) accepting non-zero alone?

Richard Knutsson

_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Robert P. J. Day]

On Tue, 9 Jan 2007, Richard Knutsson wrote:

> Robert P. J. Day wrote:
> > On Tue, 9 Jan 2007, Richard Knutsson wrote:

> > > What about something like:
> > >
> > > #define LESS_THEN_2_BITS(x)  (x & (x - 1))
> > >
> Oops, forgot a '= 0' there...
> > > #define IS_POWER_OF_2(x)   (x != 0 && LESS_THEN_2_BITS(x))
> > >
> >
> > i'm not sure i'd bother with the "LESS_THAN_2_BITS" macro, since i
> > doubt it would have widespread application.  in any event, this is
> > just something to think about for future consideration.
> >
> So just leaving those who are (with right) accepting non-zero alone?

as a first pass, i would try a cleanup that left the semantics of the
existing code *exactly* the way it was.  so if there was a
pathological case in the current code, it would still be there in the
new code.  that's clearly the safe way to proceed.

a couple final thoughts on this later.

rday
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Darren Jenkins]

G'day guys

Cleaning this up does seem like a good janitorial task to me.
It should make the code more clear and consistant, it might also
identify a bug or two in this area. :)

On 1/9/07, Richard Knutsson <ricknu-0@student.ltu.se> wrote:
> What about something like:
>
> #define LESS_THEN_2_BITS(x)  (x & (x - 1))
> #define IS_POWER_OF_2(x)   (x != 0 && LESS_THEN_2_BITS(x))

As for names, I would go for something like

#define IS_POWER_OF_2(x) ((x & (x - 1)) = 0)

With either

#define IS_POWER_OF_2_NZ(x) (x != 0 && IS_POWER_OF_2(x))
or
#define IS_SINGLE_BIT_SET(x) (x != 0 && IS_POWER_OF_2(x))

> Robert P. J. Day wrote:
> as a first pass, i would try a cleanup that left the semantics of the
> existing code *exactly* the way it was.  so if there was a
> pathological case in the current code, it would still be there in the
> new code.  that's clearly the safe way to proceed.

Yes, and that way the maintainers should see your initial patches and evaluate
which case is required on their own. ;)

Darren J
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Robert P. J. Day]

  so, some final thoughts on this potential cleanup.  first, i think
it's clear that, *if* this is even going to be submitted as a patch,
the proper definition of a "is_power_of_2()" macro (or inline
function) should ***not*** validate the value zero as a power of 2
(based both on kernel source and mathematical precedent).

  second, just because the expression "(x & (x - 1))" appears
somewhere in the source doesn't necessarily mean that it's testing for
power-of-2ness.  it's always possible (although admittedly not likely)
that someone might be using that expression for something entirely
unconnected, so it's important to look at each case to see what it's
doing, and only make a macro replacement if it makes semantic sense,
and also that it duplicates the current semantics *exactly*.

  also, it might be worth designing a couple companion routines that
do "round up to power of 2" and "round down to power of 2", since that
actually happens occasionally in the source.  if you look for any
"while" loops that incorporate this power-of-2 testing:

  $ grep -Er -A5 "while.*([^\(\)]+) ?\& ?\(\1 ?- ?1\)" .

you see stuff like this:

./drivers/video/vesafb.c:                       while (temp_size & (temp_size - 1))
./drivers/video/vesafb.c-                               temp_size &= (temp_size - 1);

what the above is doing is rounding *down* to the nearest power of 2.

  on the other hand, this:

./drivers/net/pcmcia/pcnet_cs.c:    while ((window_size & (window_size - 1)) != 0)
./drivers/net/pcmcia/pcnet_cs.c-        window_size += window_size & ~(window_size - 1);

is rounding *up* to the nearest power of 2 so, even though there may
not be that many examples of the above, it might still be useful to
define those two macros/functions just to make the code clearer.  (go
on -- tell me you could have looked at that code from pcnet_cs.c above
and thought, "oh, rounding up to the next power of 2."  :-)

  (also note that, occasionally, that rounding is done purely by brute
force:

./drivers/net/myri10ge/myri10ge.c:              while ((big_pow2 & (big_pow2 - 1)) != 0)
./drivers/net/myri10ge/myri10ge.c-                      big_pow2++;

so that could still be made clearer.  i don't suppose there's a single
bitwise operation that could do this rounding without the aid of a
loop, is there?  that would certainly be a performance boost if it's
possible.)

  so, three macros/functions:

	is_power_of_2(x)
	round_up_to_power_of_2(x)
	round_down_to_power_of_2(x)

or something to that effect.

  anyone want to take a crack at this?  i have no territorial views on
this.  i already have enough patches in the system, i don't need
anything else with my name on it.  if anyone wants to adopt this as a
project and see where it goes, it's yours.

rday

p.s.  i would also put these definitions in a new header file, say
include/linux/power_of_2.h or something like that.  there's already
way too much stuff in kernel.h to add even more there.
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Jaco Kroon]

[-- Attachment #1.1: Type: text/plain, Size: 1405 bytes --]

Darren Jenkins wrote:
> G'day guys
> 
> Cleaning this up does seem like a good janitorial task to me.
> It should make the code more clear and consistant, it might also
> identify a bug or two in this area. :)
> 
> On 1/9/07, Richard Knutsson <ricknu-0@student.ltu.se> wrote:
> 
>>What about something like:
>>
>>#define LESS_THEN_2_BITS(x)  (x & (x - 1))
>>#define IS_POWER_OF_2(x)   (x != 0 && LESS_THEN_2_BITS(x))
> 
> 
> As for names, I would go for something like
> 
> #define IS_POWER_OF_2(x) ((x & (x - 1)) == 0)

hmm, doesn't this once more give the problem min/max has where arguments
gets evaluated twice?  Or even in this case, what about something like
IS_POWER_OF_2(x - 1) ... ?

For the complex parameters just put the xs in ()s, something like:

#define IS_POWER_OF_2(x) (((x) & ((x) - 1)) == 0)

Or do I have my order of priority on my operations totally screwed up?

As for the evaluating x twice, min and max has a complex hack which can
easily be duplicated:

#define IS_POWER_OF_2(x)  ({ typeof (x) __tmp = (x); \
	((__tmp & (__tmp - 1)) == 0) })


> With either
> 
> #define IS_POWER_OF_2_NZ(x) (x != 0 && IS_POWER_OF_2(x))
> or
> #define IS_SINGLE_BIT_SET(x) (x != 0 && IS_POWER_OF_2(x))

Personally I like both these namings, but once more it's going to need
to avoid evaluating x twice, or even thrice.

If this was C++ I'd have recommended just using an inline template ...

Jaco

[-- Attachment #1.2: S/MIME Cryptographic Signature --]
[-- Type: application/x-pkcs7-signature, Size: 3233 bytes --]

[-- Attachment #2: Type: text/plain, Size: 168 bytes --]

_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Robert P. J. Day]

On Wed, 10 Jan 2007, Darren Jenkins wrote:

> As for names, I would go for something like
>
> #define IS_POWER_OF_2(x) ((x & (x - 1)) = 0)
>
> With either
>
> #define IS_POWER_OF_2_NZ(x) (x != 0 && IS_POWER_OF_2(x))
> or
> #define IS_SINGLE_BIT_SET(x) (x != 0 && IS_POWER_OF_2(x))

i would disagree.  as i wrote just a bit earlier, i think the
fundamental definition of a power of 2 should *not* include zero,
because of both mathematical and source code precedent.

if anything, i would propose something like:

#define IS_POWER_OF_2(x) 		(x != 0 && ((x & (x - 1)) = 0))
#define IS_POWER_OF_2_OR_ZERO(x)	(IS_POWER_OF_2(x) || x = 0)

that way, the case of accepting zero becomes the *exception*, not the
rule.

rday

p.s.  and as darren pointed out as well, it might be interesting to
see how many instances of the current tests "((x & (x - 1) = 0)" were
really meant to *not* accept zero as a valid value -- they've just
been lucky all this time.  :-)
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Robert P. J. Day]

On Tue, 9 Jan 2007, Jaco Kroon wrote:

> Darren Jenkins wrote:

> > As for names, I would go for something like
> >
> > #define IS_POWER_OF_2(x) ((x & (x - 1)) = 0)
>
> hmm, doesn't this once more give the problem min/max has where arguments
> gets evaluated twice?  Or even in this case, what about something like
> IS_POWER_OF_2(x - 1) ... ?
>
> For the complex parameters just put the xs in ()s, something like:
>
> #define IS_POWER_OF_2(x) (((x) & ((x) - 1)) = 0)
>
> Or do I have my order of priority on my operations totally screwed up?
>
> As for the evaluating x twice, min and max has a complex hack which can
> easily be duplicated:
>
> #define IS_POWER_OF_2(x)  ({ typeof (x) __tmp = (x); \
> 	((__tmp & (__tmp - 1)) = 0) })

that's why i mentioned inline functions earlier.  obviously, these
macros would have to be carefully designed to avoid the well-known
macro side effects, if you choose to use macros.

rday

p.s.  that's not really a "complex hack," just a well-known gcc
extension.
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Darren Jenkins]

> Robert P. J. Day wrote:

> i would disagree.  as i wrote just a bit earlier, i think the
> fundamental definition of a power of 2 should *not* include zero,
> because of both mathematical and source code precedent.
>
> if anything, i would propose something like:
>
> #define IS_POWER_OF_2(x)                (x != 0 && ((x & (x - 1)) = 0))
> #define IS_POWER_OF_2_OR_ZERO(x)        (IS_POWER_OF_2(x) || x = 0)

Hmm mathematically you are right, so I guess that this naming would be better.
I would swap the logic between the two though.

#define IS_POWER_OF_2(x)                ((x) != 0 && IS_POWER_OF_2_OR_ZERO(x))
#define IS_POWER_OF_2_OR_ZERO(x)        (((x) & ((x) - 1)) = 0)

GCC would probably evaluate it the same, but it looks a little more
logical to me



> On Tue, 9 Jan 2007, Jaco Kroon wrote:

> hmm, doesn't this once more give the problem min/max has where arguments
> gets evaluated twice?  Or even in this case, what about something like
> IS_POWER_OF_2(x - 1) ... ?

Yes, this does have the multiple evaluation bug, and complex evaluation bug.
I should of put the x in brackets (my bad) however I don't know about the
macro multiple evaluation bug, it does not seem like standard practice
in the headers to
fix this. Is there an example in the code where someone uses a function ?
Is this actually needed or is it overkill ?
If we do need this, should someone look at fixing the multiple
evaluation bug in all the kernel macro's?

Darren J.
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Robert P. J. Day]

On Wed, 10 Jan 2007, Darren Jenkins wrote:

> > Robert P. J. Day wrote:
>
> > i would disagree.  as i wrote just a bit earlier, i think the
> > fundamental definition of a power of 2 should *not* include zero,
> > because of both mathematical and source code precedent.
> >
> > if anything, i would propose something like:
> >
> > #define IS_POWER_OF_2(x)                (x != 0 && ((x & (x - 1)) = 0))
> > #define IS_POWER_OF_2_OR_ZERO(x)        (IS_POWER_OF_2(x) || x = 0)
>
> Hmm mathematically you are right, so I guess that this naming would
> be better. I would swap the logic between the two though.
>
> #define IS_POWER_OF_2(x)                ((x) != 0 && IS_POWER_OF_2_OR_ZERO(x))
> #define IS_POWER_OF_2_OR_ZERO(x)        (((x) & ((x) - 1)) = 0)
>
> GCC would probably evaluate it the same, but it looks a little more
> logical to me

sure, either way works for me.  as you say, gcc would probably end up
doing the same thing in either case.

rday
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Robert P. J. Day]

On Wed, 10 Jan 2007, Darren Jenkins wrote:

> > Robert P. J. Day wrote:
>
> > i would disagree.  as i wrote just a bit earlier, i think the
> > fundamental definition of a power of 2 should *not* include zero,
> > because of both mathematical and source code precedent.
> >
> > if anything, i would propose something like:
> >
> > #define IS_POWER_OF_2(x)                (x != 0 && ((x & (x - 1)) = 0))
> > #define IS_POWER_OF_2_OR_ZERO(x)        (IS_POWER_OF_2(x) || x = 0)
>
> Hmm mathematically you are right, so I guess that this naming would
> be better.

just for some final entertainment value, i googled on the notion of
testing for power-of-2ness in C, and found the following:

  http://www.parashift.com/c++-faq-lite/intrinsic-types.html#faq-26.12

so that seems to finalize the rule that zero is not considered a power
of two.  now if someone wants to propose an initial power-of-2.h
header file with the appropriate routines, we can argue about *that*.
:-)

rday

_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Randy Dunlap]

On Tue, 9 Jan 2007 11:16:50 -0500 (EST) Robert P. J. Day wrote:

> On Wed, 10 Jan 2007, Darren Jenkins wrote:
> 
> > > Robert P. J. Day wrote:
> >
> > > i would disagree.  as i wrote just a bit earlier, i think the
> > > fundamental definition of a power of 2 should *not* include zero,
> > > because of both mathematical and source code precedent.
> > >
> > > if anything, i would propose something like:
> > >
> > > #define IS_POWER_OF_2(x)                (x != 0 && ((x & (x - 1)) = 0))
> > > #define IS_POWER_OF_2_OR_ZERO(x)        (IS_POWER_OF_2(x) || x = 0)
> >
> > Hmm mathematically you are right, so I guess that this naming would
> > be better.
> 
> just for some final entertainment value, i googled on the notion of
> testing for power-of-2ness in C, and found the following:
> 
>   http://www.parashift.com/c++-faq-lite/intrinsic-types.html#faq-26.12
> 
> so that seems to finalize the rule that zero is not considered a power
> of two.  now if someone wants to propose an initial power-of-2.h
> header file with the appropriate routines, we can argue about *that*.
> :-)

Looks like using an inline function would be safer and probably
more in the current vogue.

---
~Randy
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Robert P. J. Day]

On Tue, 9 Jan 2007, Randy Dunlap wrote:

> On Tue, 9 Jan 2007 11:16:50 -0500 (EST) Robert P. J. Day wrote:
>
> > On Wed, 10 Jan 2007, Darren Jenkins wrote:
> >
> > > > Robert P. J. Day wrote:
> > >
> > > > i would disagree.  as i wrote just a bit earlier, i think the
> > > > fundamental definition of a power of 2 should *not* include zero,
> > > > because of both mathematical and source code precedent.
> > > >
> > > > if anything, i would propose something like:
> > > >
> > > > #define IS_POWER_OF_2(x)                (x != 0 && ((x & (x - 1)) = 0))
> > > > #define IS_POWER_OF_2_OR_ZERO(x)        (IS_POWER_OF_2(x) || x = 0)
> > >
> > > Hmm mathematically you are right, so I guess that this naming would
> > > be better.
> >
> > just for some final entertainment value, i googled on the notion of
> > testing for power-of-2ness in C, and found the following:
> >
> >   http://www.parashift.com/c++-faq-lite/intrinsic-types.html#faq-26.12
> >
> > so that seems to finalize the rule that zero is not considered a power
> > of two.  now if someone wants to propose an initial power-of-2.h
> > header file with the appropriate routines, we can argue about *that*.
> > :-)
>
> Looks like using an inline function would be safer and probably
> more in the current vogue.

agreed.  and, as i wrote earlier, i'd like to see this stuff in its
own header file in include/linux, and not dumped into kernel.h to make
that file even more chaotic than it already is.

so ... who's up for it?

rday
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Arnaldo Carvalho de Melo]

On Tue, Jan 09, 2007 at 01:57:19PM -0500, Robert P. J. Day wrote:
> On Tue, 9 Jan 2007, Randy Dunlap wrote:
> 
> > On Tue, 9 Jan 2007 11:16:50 -0500 (EST) Robert P. J. Day wrote:
> >
> > > On Wed, 10 Jan 2007, Darren Jenkins wrote:
> > >
> > > > > Robert P. J. Day wrote:
> > > >
> > > > > i would disagree.  as i wrote just a bit earlier, i think the
> > > > > fundamental definition of a power of 2 should *not* include zero,
> > > > > because of both mathematical and source code precedent.
> > > > >
> > > > > if anything, i would propose something like:
> > > > >
> > > > > #define IS_POWER_OF_2(x)                (x != 0 && ((x & (x - 1)) = 0))
> > > > > #define IS_POWER_OF_2_OR_ZERO(x)        (IS_POWER_OF_2(x) || x = 0)
> > > >
> > > > Hmm mathematically you are right, so I guess that this naming would
> > > > be better.
> > >
> > > just for some final entertainment value, i googled on the notion of
> > > testing for power-of-2ness in C, and found the following:
> > >
> > >   http://www.parashift.com/c++-faq-lite/intrinsic-types.html#faq-26.12
> > >
> > > so that seems to finalize the rule that zero is not considered a power
> > > of two.  now if someone wants to propose an initial power-of-2.h
> > > header file with the appropriate routines, we can argue about *that*.
> > > :-)
> >
> > Looks like using an inline function would be safer and probably
> > more in the current vogue.
> 
> agreed.  and, as i wrote earlier, i'd like to see this stuff in its
> own header file in include/linux, and not dumped into kernel.h to make
> that file even more chaotic than it already is.
> 
> so ... who's up for it?

You? Step up! :-) I'd gladly sign-off it

- arnaldo
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Martin Olsen]

On Tuesday 09 January 2007 19:57, Robert P. J. Day wrote:
> so ... who's up for it?

I'd love to take a crack on this.

I have yet to submit my first patch to The Kernel so if anyone would like to 
support me while doing this it would be great.

Martin
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Robert P. J. Day]

On Tue, 9 Jan 2007, Martin Olsen wrote:

> On Tuesday 09 January 2007 19:57, Robert P. J. Day wrote:
> > so ... who's up for it?
>
> I'd love to take a crack on this.
>
> I have yet to submit my first patch to The Kernel so if anyone would
> like to support me while doing this it would be great.

feel free.  i'll give you a hand if you need it.  like i said before,
i've got enough patches in the system, i have no overwhelming need to
create any more at the moment.

first order of business:  let's see a header file with some inline
functions that we can agree on.

rday
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Robert P. J. Day]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1429 bytes --]

On Tue, 9 Jan 2007, Martin Olsen wrote:

> On Tuesday 09 January 2007 19:57, Robert P. J. Day wrote:
> > so ... who's up for it?
>
> I'd love to take a crack on this.
>
> I have yet to submit my first patch to The Kernel so if anyone would
> like to support me while doing this it would be great.

to help you get things going, i've attached my style.sh script, which
scans the source tree to find questionable constructs that might
represent possible cleanups.  in the attached version, i've commented
out every check except for the power of 2 stuff, so you can see the
potential for cleanup.

(note how i've specifically scanned for the four similar variations of
the test, depending on the possibility for parentheses.  if someone
knows a better way to express these patterns that would handle
matching parentheses (without getting into perl, that is), i'd love to
hear it.)

note how almost all of the tests are just one of those variations.  a
couple notes:

1) ignore the FIND_FIRST_BIT macro in cardbus.c -- i've already
submitted a patch to delete that entirely, it's useless.

2) for the time being, don't mess with anything related to powerpc --
i get the impression they do things differently there so just give
that a pass for now.

  first things first, though -- let's see a proposed power_of_2.h
header file with inline functions:

  is_power_of_2(x)
  round_up_to_power_of_2(x)
  round_down_to_power_of_2(x)

rday

[-- Attachment #2: Type: APPLICATION/x-sh, Size: 2323 bytes --]

[-- Attachment #3: Type: text/plain, Size: 168 bytes --]

_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Martin Olsen]

[-- Attachment #1: Type: text/plain, Size: 1586 bytes --]

On Wednesday 10 January 2007 09:25, you wrote:
> On Tue, 9 Jan 2007, Martin Olsen wrote:
> > On Tuesday 09 January 2007 19:57, Robert P. J. Day wrote:
> > > so ... who's up for it?
> >
> > I'd love to take a crack on this.
> >
> > I have yet to submit my first patch to The Kernel so if anyone would
> > like to support me while doing this it would be great.
>
> to help you get things going, i've attached my style.sh script, which
> scans the source tree to find questionable constructs that might
> represent possible cleanups.  in the attached version, i've commented
> out every check except for the power of 2 stuff, so you can see the
> potential for cleanup.
>
> (note how i've specifically scanned for the four similar variations of
> the test, depending on the possibility for parentheses.  if someone
> knows a better way to express these patterns that would handle
> matching parentheses (without getting into perl, that is), i'd love to
> hear it.)
>
> note how almost all of the tests are just one of those variations.  a
> couple notes:
>
> 1) ignore the FIND_FIRST_BIT macro in cardbus.c -- i've already
> submitted a patch to delete that entirely, it's useless.
>
> 2) for the time being, don't mess with anything related to powerpc --
> i get the impression they do things differently there so just give
> that a pass for now.
>
>   first things first, though -- let's see a proposed power_of_2.h
> header file with inline functions:
>
>   is_power_of_2(x)
>   round_up_to_power_of_2(x)
>   round_down_to_power_of_2(x)
>
> rday

What do you say to this patch?

Martin

[-- Attachment #2: patch --]
[-- Type: text/x-diff, Size: 668 bytes --]

diff -uprN -X linux-2.6.19-vanilla/Documentation/dontdiff linux-2.6.19-vanilla/include/linux/power_of_2.h linux-2.6.19-changed/include/linux/power_of_2.h
--- linux-2.6.19-vanilla/include/linux/power_of_2.h	1970-01-01 01:00:00.000000000 +0100
+++ linux-2.6.19-changed/include/linux/power_of_2.h	2007-01-10 12:42:03.000000000 +0100
@@ -0,0 +1,20 @@
+static inline bool is_power_of_2(int i)
+{
+	return i > 0 && (i & (i - 1)) == 0;
+}
+
+static inline int round_up_to_power_of_2(int i)
+{
+	while ((i & (i - 1)) != 0)
+		i += i & ~(i - 1);
+	
+	return i;
+}
+
+static inline int round_down_to_power_of_2(int i)
+{
+	while (i & (i - 1))
+		i &= (i - 1);
+	
+	return i;
+}

[-- Attachment #3: Type: text/plain, Size: 168 bytes --]

_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Jaco Kroon]

[-- Attachment #1.1: Type: text/plain, Size: 1264 bytes --]

Martin Olsen wrote:

> What do you say to this patch?
> 
> Martin

Circular inclusion protection or multiple inclusion protection at least?

> ------------------------------------------------------------------------
> 
> diff -uprN -X linux-2.6.19-vanilla/Documentation/dontdiff linux-2.6.19-vanilla/include/linux/power_of_2.h linux-2.6.19-changed/include/linux/power_of_2.h
> --- linux-2.6.19-vanilla/include/linux/power_of_2.h	1970-01-01 01:00:00.000000000 +0100
> +++ linux-2.6.19-changed/include/linux/power_of_2.h	2007-01-10 12:42:03.000000000 +0100
> @@ -0,0 +1,20 @@

#ifndef _LINUX_POWER_OF_2_H
#define _LINUX_POWER_OF_2_H

> +static inline bool is_power_of_2(int i)
> +{
> +	return i > 0 && (i & (i - 1)) == 0;
> +}

/* perhaps rather - to be able to get those cases
   where 0 is acceptable as well? */
static inline bool is_power_of_2_or_zero(int i)
{
        return (i & (i - 1)) == 0;
}

static inline bool is_power_of_2(int i)
{
        return i && is_power_of_2_or_zero(i);
}

> +static inline int round_up_to_power_of_2(int i)
> +{
> +	while ((i & (i - 1)) != 0)
> +		i += i & ~(i - 1);
> +	
> +	return i;
> +}
> +
> +static inline int round_down_to_power_of_2(int i)
> +{
> +	while (i & (i - 1))
> +		i &= (i - 1);
> +	
> +	return i;
> +}

#endif

[-- Attachment #1.2: S/MIME Cryptographic Signature --]
[-- Type: application/x-pkcs7-signature, Size: 3233 bytes --]

[-- Attachment #2: Type: text/plain, Size: 168 bytes --]

_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Martin Olsen]

On Wednesday 10 January 2007 13:12, you wrote:
> Martin Olsen wrote:
> > What do you say to this patch?
> >
> > Martin
>
> Circular inclusion protection or multiple inclusion protection at least?
>
> > ------------------------------------------------------------------------
> >
> > diff -uprN -X linux-2.6.19-vanilla/Documentation/dontdiff
> > linux-2.6.19-vanilla/include/linux/power_of_2.h
> > linux-2.6.19-changed/include/linux/power_of_2.h ---
> > linux-2.6.19-vanilla/include/linux/power_of_2.h	1970-01-01
> > 01:00:00.000000000 +0100 +++
> > linux-2.6.19-changed/include/linux/power_of_2.h	2007-01-10
> > 12:42:03.000000000 +0100 @@ -0,0 +1,20 @@
>
> #ifndef _LINUX_POWER_OF_2_H
> #define _LINUX_POWER_OF_2_H
>
> > +static inline bool is_power_of_2(int i)
> > +{
> > +	return i > 0 && (i & (i - 1)) = 0;
> > +}
>
> /* perhaps rather - to be able to get those cases
>    where 0 is acceptable as well? */
> static inline bool is_power_of_2_or_zero(int i)
> {
>         return (i & (i - 1)) = 0;
> }
>
> static inline bool is_power_of_2(int i)
> {
>         return i && is_power_of_2_or_zero(i);
> }
>
> > +static inline int round_up_to_power_of_2(int i)
> > +{
> > +	while ((i & (i - 1)) != 0)
> > +		i += i & ~(i - 1);
> > +
> > +	return i;
> > +}
> > +
> > +static inline int round_down_to_power_of_2(int i)
> > +{
> > +	while (i & (i - 1))
> > +		i &= (i - 1);
> > +
> > +	return i;
> > +}
>
> #endif

Done.

Should I add a license/copyright notice at the top of the file?

Martin
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Robert P. J. Day]

On Wed, 10 Jan 2007, Martin Olsen wrote:

> What do you say to this patch?

could you *not* submit these things as attachments, to make them
easier to reply to?

rday
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Robert P. J. Day]

On Wed, 10 Jan 2007, Jaco Kroon wrote:

> Martin Olsen wrote:
>
> > What do you say to this patch?
> >
> > Martin
>
> Circular inclusion protection or multiple inclusion protection at least?
>
> > ------------------------------------------------------------------------
> >
> > diff -uprN -X linux-2.6.19-vanilla/Documentation/dontdiff linux-2.6.19-vanilla/include/linux/power_of_2.h linux-2.6.19-changed/include/linux/power_of_2.h
> > --- linux-2.6.19-vanilla/include/linux/power_of_2.h	1970-01-01 01:00:00.000000000 +0100
> > +++ linux-2.6.19-changed/include/linux/power_of_2.h	2007-01-10 12:42:03.000000000 +0100
> > @@ -0,0 +1,20 @@
>
> #ifndef _LINUX_POWER_OF_2_H
> #define _LINUX_POWER_OF_2_H
>
> > +static inline bool is_power_of_2(int i)
> > +{
> > +	return i > 0 && (i & (i - 1)) = 0;
> > +}
>
> /* perhaps rather - to be able to get those cases
>    where 0 is acceptable as well? */

we already decided that the definition of "power of 2" would *not*
accept zero.  if a programmer needs that, he/she should have to check
that explicitly.

but it might be safer to make the argument "unsigned" (if not
"unsigned long").  does anyone have a good argument for the proper
argument type?  certainly, a negative argument makes little sense.

rday
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Robert P. J. Day]

On Wed, 10 Jan 2007, Jaco Kroon wrote:

> Martin Olsen wrote:
>
> > What do you say to this patch?
> >
> > Martin
>
> Circular inclusion protection or multiple inclusion protection at least?
>
> > ------------------------------------------------------------------------
> >
> > diff -uprN -X linux-2.6.19-vanilla/Documentation/dontdiff linux-2.6.19-vanilla/include/linux/power_of_2.h linux-2.6.19-changed/include/linux/power_of_2.h
> > --- linux-2.6.19-vanilla/include/linux/power_of_2.h	1970-01-01 01:00:00.000000000 +0100
> > +++ linux-2.6.19-changed/include/linux/power_of_2.h	2007-01-10 12:42:03.000000000 +0100
> > @@ -0,0 +1,20 @@
>
> #ifndef _LINUX_POWER_OF_2_H
> #define _LINUX_POWER_OF_2_H
>
> > +static inline bool is_power_of_2(int i)
> > +{
> > +	return i > 0 && (i & (i - 1)) = 0;
> > +}
>
> /* perhaps rather - to be able to get those cases
>    where 0 is acceptable as well? */
> static inline bool is_power_of_2_or_zero(int i)
> {
>         return (i & (i - 1)) = 0;
> }

whoops, ignore my last whining, i totally missed that you were
suggesting an *additional* routine for checking for zero as well.

rday
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Robert P. J. Day]

On Wed, 10 Jan 2007, Martin Olsen wrote:

> Done.
>
> Should I add a license/copyright notice at the top of the file?
>
> Martin

just use any of the current include/linux header files as a model.

rday
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Martin Olsen]

On Wednesday 10 January 2007 14:40, you wrote:
> On Wed, 10 Jan 2007, Jaco Kroon wrote:
> > Martin Olsen wrote:
> > > What do you say to this patch?
> > >
> > > Martin
> >
> > Circular inclusion protection or multiple inclusion protection at least?
> >
> > > -----------------------------------------------------------------------
> > >-
> > >
> > > diff -uprN -X linux-2.6.19-vanilla/Documentation/dontdiff
> > > linux-2.6.19-vanilla/include/linux/power_of_2.h
> > > linux-2.6.19-changed/include/linux/power_of_2.h ---
> > > linux-2.6.19-vanilla/include/linux/power_of_2.h	1970-01-01
> > > 01:00:00.000000000 +0100 +++
> > > linux-2.6.19-changed/include/linux/power_of_2.h	2007-01-10
> > > 12:42:03.000000000 +0100 @@ -0,0 +1,20 @@
> >
> > #ifndef _LINUX_POWER_OF_2_H
> > #define _LINUX_POWER_OF_2_H
> >
> > > +static inline bool is_power_of_2(int i)
> > > +{
> > > +	return i > 0 && (i & (i - 1)) = 0;
> > > +}
> >
> > /* perhaps rather - to be able to get those cases
> >    where 0 is acceptable as well? */
>
> ...
>
> but it might be safer to make the argument "unsigned" (if not
> "unsigned long").  does anyone have a good argument for the proper
> argument type?  certainly, a negative argument makes little sense.

Using "unsigned long" certainly seems more sane than int.

I've split the code up in is_power_of_2{,_or_zero} functions, changed "int" 
to "unsigned long" and added the circular inclusion protection. 

---

diff -uprN -X linux-2.6.19-vanilla/Documentation/dontdiff 
linux-2.6.19-vanilla/include/linux/power_of_2.h 
linux-2.6.19-changed/include/linux/power_of_2.h
--- linux-2.6.19-vanilla/include/linux/power_of_2.h	1970-01-01 
01:00:00.000000000 +0100
+++ linux-2.6.19-changed/include/linux/power_of_2.h	2007-01-10 
16:05:28.000000000 +0100
@@ -0,0 +1,30 @@
+#ifndef _LINUX_POWER_OF_2_H
+#define _LINUX_POWER_OF_2_H
+
+static inline bool is_power_of_2_or_zero(unsigned long i)
+{
+	return (i & (i - 1)) = 0;
+}
+
+static inline bool is_power_of_2(unsigned long i)
+{
+	return i && is_power_of_2_or_zero(i);
+}
+
+static inline unsigned long round_up_to_power_of_2(unsigned long i)
+{
+	while ((i & (i - 1)) != 0)
+		i += i & ~(i - 1);
+	
+	return i;
+}
+
+static inline unsigned long round_down_to_power_of_2(unsigned long i)
+{
+	while (i & (i - 1))
+		i &= (i - 1);
+	
+	return i;
+}
+
+#endif /* !_LINUX_POWER_OF_2_H */
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Robert P. J. Day]

On Wed, 10 Jan 2007, Martin Olsen wrote:

> Using "unsigned long" certainly seems more sane than int.
>
> I've split the code up in is_power_of_2{,_or_zero} functions, changed "int"
> to "unsigned long" and added the circular inclusion protection.
>
> ---
>
> diff -uprN -X linux-2.6.19-vanilla/Documentation/dontdiff
> linux-2.6.19-vanilla/include/linux/power_of_2.h
> linux-2.6.19-changed/include/linux/power_of_2.h
> --- linux-2.6.19-vanilla/include/linux/power_of_2.h	1970-01-01
> 01:00:00.000000000 +0100
> +++ linux-2.6.19-changed/include/linux/power_of_2.h	2007-01-10
> 16:05:28.000000000 +0100
> @@ -0,0 +1,30 @@
> +#ifndef _LINUX_POWER_OF_2_H
> +#define _LINUX_POWER_OF_2_H
> +
> +static inline bool is_power_of_2_or_zero(unsigned long i)
> +{
> +	return (i & (i - 1)) = 0;
> +}
> +
> +static inline bool is_power_of_2(unsigned long i)
> +{
> +	return i && is_power_of_2_or_zero(i);
> +}
> +
> +static inline unsigned long round_up_to_power_of_2(unsigned long i)
> +{
> +	while ((i & (i - 1)) != 0)
> +		i += i & ~(i - 1);
> +
> +	return i;
> +}
> +
> +static inline unsigned long round_down_to_power_of_2(unsigned long i)
> +{
> +	while (i & (i - 1))
> +		i &= (i - 1);
> +
> +	return i;
> +}
> +
> +#endif /* !_LINUX_POWER_OF_2_H */
             ^^^^^^^^^^^^^^^^^^^^  i think that might be overkill.  at
most, the existing header files rarely add the "!".

looks reasonably sane, i don't see any immediate problems.  i'm still
interested if there's a single (bitwise?) operation to do the rounding
up or down without involving a loop, which would be cool, but i don't
know if that's possible.  anyone?

at this point, i would submit this as an official patch to the KJ
list.  um ... you *have* tested this code to see what it does in
various situations, right?  :-)

rday

p.s.  don't forget to add the copyright/license stuff at the top.
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Darren Jenkins]

On 1/11/07, Robert P. J. Day <rpjday@mindspring.com> wrote:

>  i'm still
> interested if there's a single (bitwise?) operation to do the rounding
> up or down without involving a loop, which would be cool, but i don't
> know if that's possible.  anyone?

I don't think it is possible.

Here is something to think about though.
It is late and I am tired, but I think it works

It should only do as many loops as there are 01 bit transitions in the input.
So I am guessing on average half as many as an algo that does a loop
for every bit set.

static inline unsigned long round_up_to_power_of_2(unsigned long i)
{
    i = (i & (i-1)) ? ((i<<1) & ~i) : i )

    while (i & (i - 1))
        i &= (i - 1);

    return i;
}

Anyway It's time for me to sleep.


Darren J
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Martin Olsen]

On Wednesday 10 January 2007 16:40, you wrote:
> On Wed, 10 Jan 2007, Martin Olsen wrote:
> > Using "unsigned long" certainly seems more sane than int.
> >
> > I've split the code up in is_power_of_2{,_or_zero} functions, changed
> > "int" to "unsigned long" and added the circular inclusion protection.
> >
> > ---
> >
> > diff -uprN -X linux-2.6.19-vanilla/Documentation/dontdiff
> > linux-2.6.19-vanilla/include/linux/power_of_2.h
> > linux-2.6.19-changed/include/linux/power_of_2.h
> > --- linux-2.6.19-vanilla/include/linux/power_of_2.h	1970-01-01
> > 01:00:00.000000000 +0100
> > +++ linux-2.6.19-changed/include/linux/power_of_2.h	2007-01-10
> > 16:05:28.000000000 +0100
> > @@ -0,0 +1,30 @@
> > +#ifndef _LINUX_POWER_OF_2_H
> > +#define _LINUX_POWER_OF_2_H
> > +
> > +static inline bool is_power_of_2_or_zero(unsigned long i)
> > +{
> > +	return (i & (i - 1)) = 0;
> > +}
> > +
> > +static inline bool is_power_of_2(unsigned long i)
> > +{
> > +	return i && is_power_of_2_or_zero(i);
> > +}
> > +
> > +static inline unsigned long round_up_to_power_of_2(unsigned long i)
> > +{
> > +	while ((i & (i - 1)) != 0)
> > +		i += i & ~(i - 1);
> > +
> > +	return i;
> > +}
> > +
> > +static inline unsigned long round_down_to_power_of_2(unsigned long i)
> > +{
> > +	while (i & (i - 1))
> > +		i &= (i - 1);
> > +
> > +	return i;
> > +}
> > +
> > +#endif /* !_LINUX_POWER_OF_2_H */
>
>              ^^^^^^^^^^^^^^^^^^^^  i think that might be overkill.  at
> most, the existing header files rarely add the "!".
>
> looks reasonably sane, i don't see any immediate problems.  i'm still
> interested if there's a single (bitwise?) operation to do the rounding
> up or down without involving a loop, which would be cool, but i don't
> know if that's possible.  anyone?

A quick search on Google Code found this snippet:

/* rounding macros, assumes ALIGN is a power of two */
#define ROUND_UP(N,ALIGN)       (((N) + ((ALIGN)-1)) & ~((ALIGN)-1))
#define ROUND_DOWN(N,ALIGN)     ((N) & ~((ALIGN)-1))

I am no mathematician, but wouldn't the above code work if ALIGN was set to 2?

> at this point, i would submit this as an official patch to the KJ
> list.  um ... you *have* tested this code to see what it does in
> various situations, right?  :-)

Heh.. No, I forgot that. A quick testcase compiled against my header file 
correctly denies any knowledge of "bool" (not defined in C). Should I include 
linux/types.h or just use "_Bool" (is _Bool part of C? I cant find any 
definitions of it in my include directories)?

But other than that the code looks okay.
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Robert P. J. Day]

On Wed, 10 Jan 2007, Martin Olsen wrote:

> A quick search on Google Code found this snippet:
>
> /* rounding macros, assumes ALIGN is a power of two */
> #define ROUND_UP(N,ALIGN)       (((N) + ((ALIGN)-1)) & ~((ALIGN)-1))
> #define ROUND_DOWN(N,ALIGN)     ((N) & ~((ALIGN)-1))
>
> I am no mathematician, but wouldn't the above code work if ALIGN was
> set to 2?

but that would only round up/down to the next *multiple* of two, not
*power* of two.  big difference.

> > at this point, i would submit this as an official patch to the KJ
> > list.  um ... you *have* tested this code to see what it does in
> > various situations, right?  :-)
>
> Heh.. No, I forgot that. A quick testcase compiled against my header
> file correctly denies any knowledge of "bool" (not defined in C).
> Should I include linux/types.h or just use "_Bool" (is _Bool part of
> C? I cant find any definitions of it in my include directories)?

if you want to use "bool" in kernel space, you should include
<linux/types.h>, which has the line:

  typedef _Bool                   bool;

that should be sufficient.  add that "include" line to your
power_of_2.h header file.

rday
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Martin Olsen]

On Wednesday 10 January 2007 19:04, you wrote:
> On Wed, 10 Jan 2007, Martin Olsen wrote:
> > A quick search on Google Code found this snippet:
> >
> > /* rounding macros, assumes ALIGN is a power of two */
> > #define ROUND_UP(N,ALIGN)       (((N) + ((ALIGN)-1)) &
> > ~((ALIGN)-1)) #define ROUND_DOWN(N,ALIGN)     ((N) & ~((ALIGN)-1))
> >
> > I am no mathematician, but wouldn't the above code work if ALIGN
> > was set to 2?
>
> but that would only round up/down to the next *multiple* of two, not
> *power* of two.  big difference.

You're right!

> > > at this point, i would submit this as an official patch to the KJ
> > > list.  um ... you *have* tested this code to see what it does in
> > > various situations, right?  :-)
> >
> > Heh.. No, I forgot that. A quick testcase compiled against my
> > header file correctly denies any knowledge of "bool" (not defined
> > in C). Should I include linux/types.h or just use "_Bool" (is _Bool
> > part of C? I cant find any definitions of it in my include
> > directories)?
>
> if you want to use "bool" in kernel space, you should include
> <linux/types.h>, which has the line:
>
>   typedef _Bool                   bool;
>
> that should be sufficient.  add that "include" line to your
> power_of_2.h header file.
>
> rday

Looks like it is almost there.

Should i change the short description at beginning of the file?

---

diff -uprN -X linux-2.6.19-vanilla/Documentation/dontdiff 
linux-2.6.19-vanilla/include/linux/power_of_2.h 
linux-2.6.19-changed/include/linux/power_of_2.h
--- linux-2.6.19-vanilla/include/linux/power_of_2.h	1970-01-01 
01:00:00.000000000 +0100
+++ linux-2.6.19-changed/include/linux/power_of_2.h	2007-01-10 
19:26:40.000000000 +0100
@@ -0,0 +1,54 @@
+/*
+ * linux/include/power_of_2.h - Power of 2 helper functions.
+ *
+ * Copyright (C) 2006 Martin Olsen <triplefault@gmail.com>
+ *
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 
+ * USA
+ *
+ */
+#ifndef _LINUX_POWER_OF_2_H
+#define _LINUX_POWER_OF_2_H
+
+#include <linux/types.h>
+
+static inline bool is_power_of_2_or_zero(unsigned long i)
+{
+	return (i & (i - 1)) = 0;
+}
+
+static inline bool is_power_of_2(unsigned long i)
+{
+	return i && is_power_of_2_or_zero(i);
+}
+
+static inline unsigned long round_up_to_power_of_2(unsigned long i)
+{
+	while ((i & (i - 1)) != 0)
+		i += i & ~(i - 1);
+	
+	return i;
+}
+
+static inline unsigned long round_down_to_power_of_2(unsigned long i)
+{
+	while (i & (i - 1))
+		i &= (i - 1);
+	
+	return i;
+}
+
+#endif
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Alexey Dobriyan]

On Wed, Jan 10, 2007 at 07:29:43PM +0100, Martin Olsen wrote:
> @@ -0,0 +1,54 @@
> +/*
> + * linux/include/power_of_2.h - Power of 2 helper functions.
> + *
> + * Copyright (C) 2006 Martin Olsen <triplefault@gmail.com>
> + *
> + *
> + * This program is free software; you can redistribute it and/or modify
> + * it under the terms of the GNU General Public License as published by
> + * the Free Software Foundation; either version 2 of the License, or
> + * (at your option) any later version.
> + *
> + * This program is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
> + * GNU General Public License for more details.
> + *
> + * You should have received a copy of the GNU General Public License
> + * along with this program; if not, write to the Free Software
> + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 
> + * USA
> + *
> + */
> +#ifndef _LINUX_POWER_OF_2_H
> +#define _LINUX_POWER_OF_2_H
> +
> +#include <linux/types.h>
> +
> +static inline bool is_power_of_2_or_zero(unsigned long i)
> +{
> +	return (i & (i - 1)) = 0;
> +}
> +
> +static inline bool is_power_of_2(unsigned long i)
> +{
> +	return i && is_power_of_2_or_zero(i);
> +}
> +
> +static inline unsigned long round_up_to_power_of_2(unsigned long i)
> +{
> +	while ((i & (i - 1)) != 0)
> +		i += i & ~(i - 1);
> +	
> +	return i;
> +}
> +
> +static inline unsigned long round_down_to_power_of_2(unsigned long i)
> +{
> +	while (i & (i - 1))
> +		i &= (i - 1);
> +	
> +	return i;
> +}

Some actual users, please. ;-)

_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Paul Bonser]

On 1/10/07, Darren Jenkins <darrenrjenkins@gmail.com> wrote:
> On 1/11/07, Robert P. J. Day <rpjday@mindspring.com> wrote:
>
> >  i'm still
> > interested if there's a single (bitwise?) operation to do the rounding
> > up or down without involving a loop, which would be cool, but i don't
> > know if that's possible.  anyone?
>
> I don't think it is possible.

Here's a constant-time version:


static inline unsigned long round_up_to_power_of_2(unsigned long i)
{
        // if it's already a power of 2, return
        if (!(i & (i-1))) return i;

        int shift_by = 0;

        #if BITS_PER_LONG = 64
        if (i & 0xffffffff00000000) {
                shift_by += 32;
                i >>= 32;
        }
        #endif

        if (i & 0xffff0000) {
                shift_by += 16;
                i >>= 16;
        }
        if (i & 0xff00) {
                shift_by += 8;
                i >>= 8;
        }
        if (i & 0xf0) {
                shift_by += 4;
                i >>= 4;
        }
        if (i & 0xc) {
                shift_by += 2;
                i >>= 2;
        }
        if (i & 0x2)
                shift_by += 2;
        else
                shift_by += 1;

        return 1 << shift_by;
}

you could avoid doing shifts altogether if you wanted to do the binary
search using a (very large) series of nested if's. That would trim it
down to just 6 if statements (with a bitwise and each) per call, no
shifting needed.
I have another hour and a half at "work", I'll see if I can do it in that time.

-- 
Paul Bonser
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Paul Bonser]

On 1/10/07, Paul Bonser <misterpib@gmail.com> wrote:
> On 1/10/07, Darren Jenkins <darrenrjenkins@gmail.com> wrote:
> > On 1/11/07, Robert P. J. Day <rpjday@mindspring.com> wrote:
> >
> > >  i'm still
> > > interested if there's a single (bitwise?) operation to do the rounding
> > > up or down without involving a loop, which would be cool, but i don't
> > > know if that's possible.  anyone?
> >
> > I don't think it is possible.
>
> Here's a constant-time version:

Whoops, I just realized that this doesn't give the right answer for
values over a certain amount. Is it proper to just return zero when
the next highest power of 2 is bigger than ULONG_MAX?

-- 
PaulB
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Darren Jenkins]

On 1/11/07, Paul Bonser <misterpib@gmail.com> wrote:
> Here's a constant-time version:
>
>
> static inline unsigned long round_up_to_power_of_2(unsigned long i)
> {
>         // if it's already a power of 2, return
>         if (!(i & (i-1))) return i;
>
>         int shift_by = 0;
>
>         #if BITS_PER_LONG = 64
>         if (i & 0xffffffff00000000) {
>                 shift_by += 32;
>                 i >>= 32;
>         }
>         #endif
>
>         if (i & 0xffff0000) {
>                 shift_by += 16;
>                 i >>= 16;
>         }
>         if (i & 0xff00) {
>                 shift_by += 8;
>                 i >>= 8;
>         }
>         if (i & 0xf0) {
>                 shift_by += 4;
>                 i >>= 4;
>         }
>         if (i & 0xc) {
>                 shift_by += 2;
>                 i >>= 2;
>         }
>         if (i & 0x2)
>                 shift_by += 2;
>         else
>                 shift_by += 1;
>
>         return 1 << shift_by;
> }
>
> you could avoid doing shifts altogether if you wanted to do the binary
> search using a (very large) series of nested if's. That would trim it
> down to just 6 if statements (with a bitwise and each) per call, no
> shifting needed.

Clever idea, but is this to big to inline ?

also was thinking we should add

static inline unsigned long round_down_to_power_of_2(unsigned long i)
{

+     i &= ~(i>>1);
    while (i & (i - 1))
        i &= (i - 1);

    return i;
}

which follows from my eirlier idea.


Darren J.
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Robert P. J. Day]

On Thu, 11 Jan 2007, Darren Jenkins wrote:

> also was thinking we should add
>
> static inline unsigned long round_down_to_power_of_2(unsigned long i)
> {
>
> +     i &= ~(i>>1);    ????
>    while (i & (i - 1))
>        i &= (i - 1);
>
>    return i;
> }
>
> which follows from my eirlier idea.

sorry, what was the rationale for that extra line up there?

rday
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Jaco Kroon]

[-- Attachment #1.1: Type: text/plain, Size: 1275 bytes --]

Robert P. J. Day wrote:
> On Thu, 11 Jan 2007, Darren Jenkins wrote:
> 
> 
>>also was thinking we should add
>>
>>static inline unsigned long round_down_to_power_of_2(unsigned long i)
>>{
>>
>>+     i &= ~(i>>1);    ????
>>   while (i & (i - 1))
>>       i &= (i - 1);
>>
>>   return i;
>>}
>>
>>which follows from my eirlier idea.
> 
> 
> sorry, what was the rationale for that extra line up there?

It presumably gets rids of a few zeros.  Take for example 11111 as
input.  The first line will actually get the right answer off the bat as
it'll mask out the bottom 4 bits.  However, with something like 11011
it'll leave us with 10010 which will again at the very least reduce the
number of iterations through the loop.  In this case one iteration vs three.

I saw a similar idea for the round-up case where we actually test if we
don't already have a power of two, shift-left by one and and with ~i
(which is then essentially the exact same of what happens above).
Whilst it took me a few minutes to just convince myself that the
orriginal algorithms even work (one of those jewel cases) these
enhancements are pretty impressive and make mathematical sense.

For reference, here is the round-up "initialisation" statement:

    i = (i & (i-1)) ? ((i<<1) & ~i) : i )

Jaco

[-- Attachment #1.2: S/MIME Cryptographic Signature --]
[-- Type: application/x-pkcs7-signature, Size: 3233 bytes --]

[-- Attachment #2: Type: text/plain, Size: 168 bytes --]

_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Robert P. J. Day]

On Thu, 11 Jan 2007, Jaco Kroon wrote:

> Robert P. J. Day wrote:
> > On Thu, 11 Jan 2007, Darren Jenkins wrote:
> >
> >
> >>also was thinking we should add
> >>
> >>static inline unsigned long round_down_to_power_of_2(unsigned long i)
> >>{
> >>
> >>+     i &= ~(i>>1);    ????
> >>   while (i & (i - 1))
> >>       i &= (i - 1);
> >>
> >>   return i;
> >>}
> >>
> >>which follows from my eirlier idea.
> >
> >
> > sorry, what was the rationale for that extra line up there?
>
> It presumably gets rids of a few zeros.  Take for example 11111 as
> input.  The first line will actually get the right answer off the
> bat as it'll mask out the bottom 4 bits.  However, with something
> like 11011 it'll leave us with 10010 which will again at the very
> least reduce the number of iterations through the loop.  In this
> case one iteration vs three.
>
> I saw a similar idea for the round-up case where we actually test if
> we don't already have a power of two, shift-left by one and and with
> ~i (which is then essentially the exact same of what happens above).
> Whilst it took me a few minutes to just convince myself that the
> orriginal algorithms even work (one of those jewel cases) these
> enhancements are pretty impressive and make mathematical sense.
>
> For reference, here is the round-up "initialisation" statement:
>
>     i = (i & (i-1)) ? ((i<<1) & ~i) : i )

ok, i'll have to look at that for a few minutes to satisfy myself that
it's correct.

rday
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Robert P. J. Day]

  well, apparently, there *is* some power of 2 stuff in the kernel
already, i just never noticed it:  include/linux/log2.h.

  i'm guessing that would be a more appropriate starting point for any
additional work along those lines.

  dang.

rday
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Paul Bonser]

Okay, here's a much better, faster, shorter version. You need to
include asm/bitops.h.
fls is (for most architectures) an inline function which has a single
assembly instruction to find the most significant set bit. Shift a 1
over by that same amount (which will put it one to the left of the MSB
that was just found), and you have the next highest power of two.

The first little bit is there to make it just return zero if there's
not a higher power of two to round up to, which is what the initially
proposed version does.
The second bit in there is checking if it's already a power of two.
Rounding down is simply the same thing, but moving the set bit to the right one.

static inline unsigned long round_up_to_power_of_2(unsigned long i)
{
#if BITS_PER_LONG = 64
	return i > i<<62? 0 : i&(i-1) ? 1ul << fls64(i) : i;
#else
	return i > i<<30? 0 : i&(i-1) ? 1ul << fls(i) : i;
#endif
}
static inline unsigned long round_down_to_power_of_2(unsigned long i)
{
#if BITS_PER_LONG = 64
	return i&(i-1) ? 1ul << (fls64(i)-1) : i;
#else
	return i&(i-1) ? 1ul << (fls(i)-1) : i;
#endif
}

running this code on the numbers 1 through 500,000,000 took 15
seconds, versus 38 seconds with the old code, so it looks like a good
improvement. Plus it was a fun challenge tracking down the best way
(i.e. a cross-platform way) to find the biggest set bit.

-Paul Bonser
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] powers of 2, and the boundary case of zero

[Paul Bonser]

On 1/11/07, Robert P. J. Day <rpjday@mindspring.com> wrote:
>
>   well, apparently, there *is* some power of 2 stuff in the kernel
> already, i just never noticed it:  include/linux/log2.h.
>
>   i'm guessing that would be a more appropriate starting point for any
> additional work along those lines.
>
>   dang.
>
> rday

Yeah dang, somebody else already made a round up to power of 2
function almost exactly like the one I just posted...

-- 
PaulB
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors