* is there a "single_bit_set" macro somewhere?
@ 2009-04-23 17:14 Robert P. J. Day
2009-04-23 17:24 ` Randy Dunlap
` (5 more replies)
0 siblings, 6 replies; 7+ messages in thread
From: Robert P. J. Day @ 2009-04-23 17:14 UTC (permalink / raw)
To: kernel-janitors
once upon a time, the kernel source code was replete with
conditional constructs of the form:
if ((n & (n-1)) = 0)
as a way of testing whether something was a power of two. mercifully,
include/linux/log2.h was created which introduced, among other things:
static inline __attribute__((const))
bool is_power_of_2(unsigned long n)
{
return (n != 0 && ((n & (n - 1)) = 0));
}
so we could simply ask whether "is_power_of_2(n)", which is convenient
when we're testing things like, oh, blocksize.
similarly, there are bunches of places which need to test whether an
integer value has only a single set bit (for instance, to make sure
only one flag bit out of a number of mutually exclusive bits are set).
mathematically, that would be the same test, of course, but
semantically, it would be ugly and inappropriate. is there,
somewhere, a corresponding macro/function that asks:
single_bit_set(n)
if not, that would be handy, could be plopped into
include/linux/bitops.h and could be defined exactly the same way, and
would allow piles of code to be simplified.
thoughts?
rday
--
====================================
Robert P. J. Day Waterloo, Ontario, CANADA
Linux Consulting, Training and Annoying Kernel Pedantry.
Web page: http://crashcourse.ca
Linked In: http://www.linkedin.com/in/rpjday
Twitter: http://twitter.com/rpjday
====================================
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: is there a "single_bit_set" macro somewhere?
2009-04-23 17:14 is there a "single_bit_set" macro somewhere? Robert P. J. Day
@ 2009-04-23 17:24 ` Randy Dunlap
2009-04-23 17:26 ` Julia Lawall
` (4 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: Randy Dunlap @ 2009-04-23 17:24 UTC (permalink / raw)
To: kernel-janitors
Robert P. J. Day wrote:
> once upon a time, the kernel source code was replete with
> conditional constructs of the form:
>
> if ((n & (n-1)) = 0)
>
> as a way of testing whether something was a power of two. mercifully,
> include/linux/log2.h was created which introduced, among other things:
>
> static inline __attribute__((const))
> bool is_power_of_2(unsigned long n)
> {
> return (n != 0 && ((n & (n - 1)) = 0));
> }
>
> so we could simply ask whether "is_power_of_2(n)", which is convenient
> when we're testing things like, oh, blocksize.
>
> similarly, there are bunches of places which need to test whether an
> integer value has only a single set bit (for instance, to make sure
> only one flag bit out of a number of mutually exclusive bits are set).
>
> mathematically, that would be the same test, of course, but
> semantically, it would be ugly and inappropriate. is there,
> somewhere, a corresponding macro/function that asks:
>
> single_bit_set(n)
>
> if not, that would be handy, could be plopped into
> include/linux/bitops.h and could be defined exactly the same way, and
> would allow piles of code to be simplified.
>
> thoughts?
single_bit_set(n) is equivalent to
hamming weight(n) = 1
lib/hweight.c implements hamming weights for 8/16/32/64-bit args.
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: is there a "single_bit_set" macro somewhere?
2009-04-23 17:14 is there a "single_bit_set" macro somewhere? Robert P. J. Day
2009-04-23 17:24 ` Randy Dunlap
@ 2009-04-23 17:26 ` Julia Lawall
2009-04-23 17:34 ` Robert P. J. Day
` (3 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: Julia Lawall @ 2009-04-23 17:26 UTC (permalink / raw)
To: kernel-janitors
On Thu, 23 Apr 2009, Robert P. J. Day wrote:
>
> once upon a time, the kernel source code was replete with
> conditional constructs of the form:
>
> if ((n & (n-1)) = 0)
>
> as a way of testing whether something was a power of two. mercifully,
> include/linux/log2.h was created which introduced, among other things:
>
> static inline __attribute__((const))
> bool is_power_of_2(unsigned long n)
> {
> return (n != 0 && ((n & (n - 1)) = 0));
> }
>
> so we could simply ask whether "is_power_of_2(n)", which is convenient
> when we're testing things like, oh, blocksize.
>
> similarly, there are bunches of places which need to test whether an
> integer value has only a single set bit (for instance, to make sure
> only one flag bit out of a number of mutually exclusive bits are set).
>
> mathematically, that would be the same test, of course, but
> semantically, it would be ugly and inappropriate. is there,
> somewhere, a corresponding macro/function that asks:
>
> single_bit_set(n)
>
> if not, that would be handy, could be plopped into
> include/linux/bitops.h and could be defined exactly the same way, and
> would allow piles of code to be simplified.
>
> thoughts?
I found 8 occurrences with the following Coccinelle semantic match:
@@ expression n; @@
* (n & (n-1)) = 0
The most unpleasant was:
(!(((fp)->ipend & ~0x30) & (((fp)->ipend & ~0x30) - 1)))
in the file arch/blackfin/kernel/traps.c.
At least some of them seemed to have comments nearby that suggested that
searching for a single 1-bit was indeed the goal. I haven't looked at all
of them, though.
julia
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: is there a "single_bit_set" macro somewhere?
2009-04-23 17:14 is there a "single_bit_set" macro somewhere? Robert P. J. Day
2009-04-23 17:24 ` Randy Dunlap
2009-04-23 17:26 ` Julia Lawall
@ 2009-04-23 17:34 ` Robert P. J. Day
2009-04-23 20:16 ` Julia Lawall
` (2 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: Robert P. J. Day @ 2009-04-23 17:34 UTC (permalink / raw)
To: kernel-janitors
On Thu, 23 Apr 2009, Julia Lawall wrote:
> I found 8 occurrences with the following Coccinelle semantic match:
>
> @@ expression n; @@
>
> * (n & (n-1)) = 0
>
>
> The most unpleasant was:
>
> (!(((fp)->ipend & ~0x30) & (((fp)->ipend & ~0x30) - 1)))
>
> in the file arch/blackfin/kernel/traps.c.
>
> At least some of them seemed to have comments nearby that suggested
> that searching for a single 1-bit was indeed the goal. I haven't
> looked at all of them, though.
behold, the power of shell and REs, which searches for four
variations of that test:
==
#!/bin/sh
DIR=${1-*}
echo -e " x & (x - 1):\n"
grep -Ern "([^\(\)]+) ?\& ?\(\1 ?- ?1\)" ${DIR}
echo -e " x & ((x) - 1):\n"
grep -Ern "([^\(\)]+) ?\& ?\(\(\1\) ?- ?1\)" ${DIR}
echo -e " (x) & (x - 1):\n"
grep -Ern "\(([^\(\)]+)\) ?\& ?\(\1 ?- ?1\)" ${DIR}
echo -e " (x) & ((x) - 1):\n"
grep -Ern "\(([^\(\)]+)\) ?\& ?\(\(\1\) ?- ?1\)" ${DIR}
==
$ find_pow2_cleanup.sh drivers/staging/comedi
x & (x - 1):
drivers/staging/comedi/drivers/amplc_pci224.c:790: if ((cmd->start_src & (cmd->start_src - 1)) != 0)
drivers/staging/comedi/drivers/amplc_pci224.c:792: if ((cmd->scan_begin_src & (cmd->scan_begin_src - 1)) != 0)
drivers/staging/comedi/drivers/amplc_pci224.c:794: if ((cmd->convert_src & (cmd->convert_src - 1)) != 0)
drivers/staging/comedi/drivers/amplc_pci224.c:796: if ((cmd->scan_end_src & (cmd->scan_end_src - 1)) != 0)
drivers/staging/comedi/drivers/amplc_pci224.c:798: if ((cmd->stop_src & (cmd->stop_src - 1)) != 0)
drivers/staging/comedi/drivers/amplc_pci230.c:1274: if ((cmd->start_src & (cmd->start_src - 1)) != 0)
drivers/staging/comedi/drivers/amplc_pci230.c:1276: if ((cmd->scan_begin_src & (cmd->scan_begin_src - 1)) != 0)
drivers/staging/comedi/drivers/amplc_pci230.c:1278: if ((cmd->convert_src & (cmd->convert_src - 1)) != 0)
drivers/staging/comedi/drivers/amplc_pci230.c:1280: if ((cmd->scan_end_src & (cmd->scan_end_src - 1)) != 0)
drivers/staging/comedi/drivers/amplc_pci230.c:1282: if ((cmd->stop_src & (cmd->stop_src - 1)) != 0)
drivers/staging/comedi/drivers/amplc_pci230.c:1710: if ((cmd->start_src & (cmd->start_src - 1)) != 0)
drivers/staging/comedi/drivers/amplc_pci230.c:1712: if ((cmd->scan_begin_src & (cmd->scan_begin_src - 1)) != 0)
drivers/staging/comedi/drivers/amplc_pci230.c:1714: if ((cmd->convert_src & (cmd->convert_src - 1)) != 0)
drivers/staging/comedi/drivers/amplc_pci230.c:1716: if ((cmd->scan_end_src & (cmd->scan_end_src - 1)) != 0)
drivers/staging/comedi/drivers/amplc_pci230.c:1718: if ((cmd->stop_src & (cmd->stop_src - 1)) != 0)
drivers/staging/comedi/drivers/amplc_dio200.c:843: if ((cmd->start_src & (cmd->start_src - 1)) != 0)
drivers/staging/comedi/drivers/amplc_dio200.c:845: if ((cmd->scan_begin_src & (cmd->scan_begin_src - 1)) != 0)
drivers/staging/comedi/drivers/amplc_dio200.c:847: if ((cmd->convert_src & (cmd->convert_src - 1)) != 0)
drivers/staging/comedi/drivers/amplc_dio200.c:849: if ((cmd->scan_end_src & (cmd->scan_end_src - 1)) != 0)
drivers/staging/comedi/drivers/amplc_dio200.c:851: if ((cmd->stop_src & (cmd->stop_src - 1)) != 0)
drivers/staging/comedi/drivers/pcmmio.c:1123: if ((cmd->start_src & (cmd->start_src - 1)) != 0)
drivers/staging/comedi/drivers/pcmmio.c:1125: if ((cmd->scan_begin_src & (cmd->scan_begin_src - 1)) != 0)
drivers/staging/comedi/drivers/pcmmio.c:1127: if ((cmd->convert_src & (cmd->convert_src - 1)) != 0)
drivers/staging/comedi/drivers/pcmmio.c:1129: if ((cmd->scan_end_src & (cmd->scan_end_src - 1)) != 0)
drivers/staging/comedi/drivers/pcmmio.c:1131: if ((cmd->stop_src & (cmd->stop_src - 1)) != 0)
drivers/staging/comedi/drivers/pcmuio.c:1033: if ((cmd->start_src & (cmd->start_src - 1)) != 0)
drivers/staging/comedi/drivers/pcmuio.c:1035: if ((cmd->scan_begin_src & (cmd->scan_begin_src - 1)) != 0)
drivers/staging/comedi/drivers/pcmuio.c:1037: if ((cmd->convert_src & (cmd->convert_src - 1)) != 0)
drivers/staging/comedi/drivers/pcmuio.c:1039: if ((cmd->scan_end_src & (cmd->scan_end_src - 1)) != 0)
drivers/staging/comedi/drivers/pcmuio.c:1041: if ((cmd->stop_src & (cmd->stop_src - 1)) != 0)
x & ((x) - 1):
(x) & (x - 1):
(x) & ((x) - 1):
and that's out of a single subdirectory of drivers/staging. there's
more. lots more.
rday
--
====================================
Robert P. J. Day Waterloo, Ontario, CANADA
Linux Consulting, Training and Annoying Kernel Pedantry.
Web page: http://crashcourse.ca
Linked In: http://www.linkedin.com/in/rpjday
Twitter: http://twitter.com/rpjday
====================================
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: is there a "single_bit_set" macro somewhere?
2009-04-23 17:14 is there a "single_bit_set" macro somewhere? Robert P. J. Day
` (2 preceding siblings ...)
2009-04-23 17:34 ` Robert P. J. Day
@ 2009-04-23 20:16 ` Julia Lawall
2009-04-23 20:24 ` Robert P. J. Day
2009-04-24 13:43 ` walter harms
5 siblings, 0 replies; 7+ messages in thread
From: Julia Lawall @ 2009-04-23 20:16 UTC (permalink / raw)
To: kernel-janitors
On Thu, 23 Apr 2009, Robert P. J. Day wrote:
> On Thu, 23 Apr 2009, Julia Lawall wrote:
>
> > I found 8 occurrences with the following Coccinelle semantic match:
> >
> > @@ expression n; @@
> >
> > * (n & (n-1)) = 0
> >
> >
> > The most unpleasant was:
> >
> > (!(((fp)->ipend & ~0x30) & (((fp)->ipend & ~0x30) - 1)))
> >
> > in the file arch/blackfin/kernel/traps.c.
> >
> > At least some of them seemed to have comments nearby that suggested
> > that searching for a single 1-bit was indeed the goal. I haven't
> > looked at all of them, though.
>
> behold, the power of shell and REs, which searches for four
> variations of that test:
Actually, it seems that it was specifying = 0 that was not really
necessary. Perhaps the possibility of parentheses is useful too.
With the following semantic patch, I find 93 occurrences.
@@ expression n; @@
* (n) & ((n)-1)
That could indeed be worth doing something about, if they are indeed all
representing a check for a single bit.
julia
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: is there a "single_bit_set" macro somewhere?
2009-04-23 17:14 is there a "single_bit_set" macro somewhere? Robert P. J. Day
` (3 preceding siblings ...)
2009-04-23 20:16 ` Julia Lawall
@ 2009-04-23 20:24 ` Robert P. J. Day
2009-04-24 13:43 ` walter harms
5 siblings, 0 replies; 7+ messages in thread
From: Robert P. J. Day @ 2009-04-23 20:24 UTC (permalink / raw)
To: kernel-janitors
On Thu, 23 Apr 2009, Julia Lawall wrote:
> On Thu, 23 Apr 2009, Robert P. J. Day wrote:
>
> > On Thu, 23 Apr 2009, Julia Lawall wrote:
> >
> > > I found 8 occurrences with the following Coccinelle semantic match:
> > >
> > > @@ expression n; @@
> > >
> > > * (n & (n-1)) = 0
> > >
> > >
> > > The most unpleasant was:
> > >
> > > (!(((fp)->ipend & ~0x30) & (((fp)->ipend & ~0x30) - 1)))
> > >
> > > in the file arch/blackfin/kernel/traps.c.
> > >
> > > At least some of them seemed to have comments nearby that suggested
> > > that searching for a single 1-bit was indeed the goal. I haven't
> > > looked at all of them, though.
> >
> > behold, the power of shell and REs, which searches for four
> > variations of that test:
>
> Actually, it seems that it was specifying = 0 that was not really
> necessary. Perhaps the possibility of parentheses is useful too.
>
> With the following semantic patch, I find 93 occurrences.
>
> @@ expression n; @@
>
> * (n) & ((n)-1)
>
> That could indeed be worth doing something about, if they are indeed all
> representing a check for a single bit.
they're not. we're actually now discussing this on the main LKML,
but that construct -- n & (n - 1) -- has two semantic meanings:
a) power of two?
b) single bit set?
mathematically, those two things have the same form but
*semantically* they're read very differently, which is why i'm
proposing to add a simple function or two for single-bit testing that
would make a lot of the code easier to read.
rday
--
====================================
Robert P. J. Day Waterloo, Ontario, CANADA
Linux Consulting, Training and Annoying Kernel Pedantry.
Web page: http://crashcourse.ca
Linked In: http://www.linkedin.com/in/rpjday
Twitter: http://twitter.com/rpjday
====================================
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: is there a "single_bit_set" macro somewhere?
2009-04-23 17:14 is there a "single_bit_set" macro somewhere? Robert P. J. Day
` (4 preceding siblings ...)
2009-04-23 20:24 ` Robert P. J. Day
@ 2009-04-24 13:43 ` walter harms
5 siblings, 0 replies; 7+ messages in thread
From: walter harms @ 2009-04-24 13:43 UTC (permalink / raw)
To: kernel-janitors
Robert P. J. Day schrieb:
> On Thu, 23 Apr 2009, Julia Lawall wrote:
>
>> On Thu, 23 Apr 2009, Robert P. J. Day wrote:
>>
>>> On Thu, 23 Apr 2009, Julia Lawall wrote:
>>>
>>>> I found 8 occurrences with the following Coccinelle semantic match:
>>>>
>>>> @@ expression n; @@
>>>>
>>>> * (n & (n-1)) = 0
>>>>
>>>>
>>>> The most unpleasant was:
>>>>
>>>> (!(((fp)->ipend & ~0x30) & (((fp)->ipend & ~0x30) - 1)))
>>>>
>>>> in the file arch/blackfin/kernel/traps.c.
>>>>
>>>> At least some of them seemed to have comments nearby that suggested
>>>> that searching for a single 1-bit was indeed the goal. I haven't
>>>> looked at all of them, though.
>>> behold, the power of shell and REs, which searches for four
>>> variations of that test:
>> Actually, it seems that it was specifying = 0 that was not really
>> necessary. Perhaps the possibility of parentheses is useful too.
>>
>> With the following semantic patch, I find 93 occurrences.
>>
>> @@ expression n; @@
>>
>> * (n) & ((n)-1)
>>
>> That could indeed be worth doing something about, if they are indeed all
>> representing a check for a single bit.
>
> they're not. we're actually now discussing this on the main LKML,
> but that construct -- n & (n - 1) -- has two semantic meanings:
>
> a) power of two?
> b) single bit set?
>
> mathematically, those two things have the same form but
> *semantically* they're read very differently, which is why i'm
> proposing to add a simple function or two for single-bit testing that
> would make a lot of the code easier to read.
>
> rday
> --
>
hi all,
glibc provides in sys/param.h a set a macros (seem to come from BSD):
#define NBBY CHAR_BIT
...
#define setbit(a,i) ((a)[(i)/NBBY] |= 1<<((i)%NBBY))
#define clrbit(a,i) ((a)[(i)/NBBY] &= ~(1<<((i)%NBBY)))
#define isset(a,i) ((a)[(i)/NBBY] & (1<<((i)%NBBY)))
#define isclr(a,i) (((a)[(i)/NBBY] & (1<<((i)%NBBY))) = 0)
IMHO this is readable. This could be a nice starting point (or endpoint ?) for a S&R mission.
re,
wh
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2009-04-24 13:43 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2009-04-23 17:14 is there a "single_bit_set" macro somewhere? Robert P. J. Day
2009-04-23 17:24 ` Randy Dunlap
2009-04-23 17:26 ` Julia Lawall
2009-04-23 17:34 ` Robert P. J. Day
2009-04-23 20:16 ` Julia Lawall
2009-04-23 20:24 ` Robert P. J. Day
2009-04-24 13:43 ` walter harms
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.