is there a "single_bit_set" macro somewhere?

is there a "single_bit_set" macro somewhere?

[Robert P. J. Day]

  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
====================================

Re: is there a "single_bit_set" macro somewhere?

[Randy Dunlap]

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.

Re: is there a "single_bit_set" macro somewhere?

[Julia Lawall]

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

Re: is there a "single_bit_set" macro somewhere?

[Robert P. J. Day]

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
====================================

Re: is there a "single_bit_set" macro somewhere?

[Julia Lawall]

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

Re: is there a "single_bit_set" macro somewhere?

[Robert P. J. Day]

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
====================================

Re: is there a "single_bit_set" macro somewhere?

[walter harms]

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