Re: adding fast bitops to egcs?

Re: adding fast bitops to egcs?

[Mike Stump]

> To: Alfred Perlstein <bright@rush.net>
> cc: egcs@egcs.cygnus.com
> Date: Mon, 26 Apr 1999 21:34:43 -0600
> From: Jeffrey A Law <law@upchuck.cygnus.com>

>   > 2) number of bits set
> True.  No good pop count.

Yes, but one can do it in plain C rather easily and quickly, if one
knows the right algorithm.

Re: adding fast bitops to egcs?

[rich-paul]

On Tue, 27 Apr 1999, Mike Stump wrote:

> >   > 2) number of bits set
> > True.  No good pop count.
> 
> Yes, but one can do it in plain C rather easily and quickly, if one
> knows the right algorithm.
> 

OK, I'll bite ... what's your code?
---
There is a party that  |  Libertarian Party  |  A victimless crime is
supports the right to  |  http://www.lp.org  |     a contradiction in 
free speech and        |    The Party of     |                 terms.
encryption!!           |      Principle      |  

Re: adding fast bitops to egcs?

[Mike Stump]

> To: Alfred Perlstein <bright@rush.net>
> cc: egcs@egcs.cygnus.com
> Date: Mon, 26 Apr 1999 21:34:43 -0600
> From: Jeffrey A Law <law@upchuck.cygnus.com>

>   > 2) number of bits set
> True.  No good pop count.

Yes, but one can do it in plain C rather easily and quickly, if one
knows the right algorithm.

Re: adding fast bitops to egcs?

[rich-paul]

On Tue, 27 Apr 1999, Mike Stump wrote:

> >   > 2) number of bits set
> > True.  No good pop count.
> 
> Yes, but one can do it in plain C rather easily and quickly, if one
> knows the right algorithm.
> 

OK, I'll bite ... what's your code?
---
There is a party that  |  Libertarian Party  |  A victimless crime is
supports the right to  |  http://www.lp.org  |     a contradiction in 
free speech and        |    The Party of     |                 terms.
encryption!!           |      Principle      |  

Re: adding fast bitops to egcs?

[Andreas Schwab]

rich-paul@rich-paul.net writes:

|> On Tue, 27 Apr 1999, Mike Stump wrote:
|> 
|> > >   > 2) number of bits set
|> > > True.  No good pop count.
|> > 
|> > Yes, but one can do it in plain C rather easily and quickly, if one
|> > knows the right algorithm.
|> > 
|> 
|> OK, I'll bite ... what's your code?

Use a 256-byte lookup table.

-- 
Andreas Schwab                                      "And now for something
schwab@issan.cs.uni-dortmund.de                      completely different"
schwab@gnu.org

Re: adding fast bitops to egcs?

[Andreas Schwab]

rich-paul@rich-paul.net writes:

|> On Tue, 27 Apr 1999, Mike Stump wrote:
|> 
|> > >   > 2) number of bits set
|> > > True.  No good pop count.
|> > 
|> > Yes, but one can do it in plain C rather easily and quickly, if one
|> > knows the right algorithm.
|> > 
|> 
|> OK, I'll bite ... what's your code?

Use a 256-byte lookup table.

-- 
Andreas Schwab                                      "And now for something
schwab@issan.cs.uni-dortmund.de                      completely different"
schwab@gnu.org

Re: adding fast bitops to egcs?

[Andi Kleen]

bright@rush.net (Alfred Perlstein) writes:

> Maybe it's too much coffee today, but i've always wondered why C
> doesn't support stronger bit manipulation routines.
> 
> Such as:
> 1) return position of first set/unset bit from MSB to LSB or LSB to MSB

adding fast bitops to egcs?

[Alfred Perlstein]

Maybe it's too much coffee today, but i've always wondered why C
doesn't support stronger bit manipulation routines.

Such as:
1) return position of first set/unset bit from MSB to LSB or LSB to MSB
2) number of bits set
3) bit rotation

this could be done in the optimizer but would be hard to identify afaik...

would it make any sense to add such functionality as an egcs C extention?

as in:

/* assign x the position of the most signifigant bit set in y */
x = msbs(y); 
/* assign x the position of the least signifigant unbit set in y */
x = lsbus(y); 

The reason is that the C primatives for bit ops are quite poor for scanning
bit strings and most modern hardware supports some of these ops with a 
single fast instruction (instead of forcing the coder to use a clumsy
for loop).

This can really help people doing low end harware work that have to decode
bit encoded registers...

thanks,
-Alfred 

Re: adding fast bitops to egcs?

[Jeffrey A Law]

  In message < Pine.BSF.3.96.990426182434.2095D-100000@cygnus.rush.net >you write:
  > Such as:
  > 1) return position of first set/unset bit from MSB to LSB or LSB to MSB
ffs, which gcc will recognize and attempt to use a hardware intrinsic to
implement.

  > 2) number of bits set
True.  No good pop count.


  > 3) bit rotation
Easily synthesized.  GCC recognizes rotate synthesis and will attempt to use
a rotate instruction if the hardware supports it.

  > The reason is that the C primatives for bit ops are quite poor for scanning
  > bit strings and most modern hardware supports some of these ops with a 
  > single fast instruction (instead of forcing the coder to use a clumsy
  > for loop).
Actually, few targets have this stuff these days.  I have the, err, pleasure
of looking at 2-5 new ISAs every year.  ffs, pop count are rarer and rarer. 
rotates are still fairly common though.

jeff

Re: adding fast bitops to egcs?

[Andi Kleen]

bright@rush.net (Alfred Perlstein) writes:

> Maybe it's too much coffee today, but i've always wondered why C
> doesn't support stronger bit manipulation routines.
> 
> Such as:
> 1) return position of first set/unset bit from MSB to LSB or LSB to MSB

From LSB is __builtin_ffs().

> 2) number of bits set

Can be done using gcc inline assembly (on most CPUs that implement
the "NSA instruction" with a single opcode) 

> 3) bit rotation

Dito. 

e.g. on the x86:

extern inline unsigned int rotate_left(int i, unsigned int word)
{
	asm("roll %%cl,%0"
		:"=r" (word)
		:"0" (word),"c" (i));
	return word;
}

> this could be done in the optimizer but would be hard to identify afaik...

gcc tries to spot some of the constructs used to simulate rotation
in C ((x<<i) | (x>>(wordsize-i))) and output it as a single rotate
instruction, but this seems to only work for constant rotate counts.


-Andi

-- 
This is like TV. I don't like TV.

Re: adding fast bitops to egcs?

[Jeffrey A Law]

  In message < Pine.BSF.3.96.990426182434.2095D-100000@cygnus.rush.net >you write:
  > Such as:
  > 1) return position of first set/unset bit from MSB to LSB or LSB to MSB
ffs, which gcc will recognize and attempt to use a hardware intrinsic to
implement.

  > 2) number of bits set
True.  No good pop count.


  > 3) bit rotation
Easily synthesized.  GCC recognizes rotate synthesis and will attempt to use
a rotate instruction if the hardware supports it.

  > The reason is that the C primatives for bit ops are quite poor for scanning
  > bit strings and most modern hardware supports some of these ops with a 
  > single fast instruction (instead of forcing the coder to use a clumsy
  > for loop).
Actually, few targets have this stuff these days.  I have the, err, pleasure
of looking at 2-5 new ISAs every year.  ffs, pop count are rarer and rarer. 
rotates are still fairly common though.

jeff

adding fast bitops to egcs?

[Alfred Perlstein]

Maybe it's too much coffee today, but i've always wondered why C
doesn't support stronger bit manipulation routines.

Such as:
1) return position of first set/unset bit from MSB to LSB or LSB to MSB
2) number of bits set
3) bit rotation

this could be done in the optimizer but would be hard to identify afaik...

would it make any sense to add such functionality as an egcs C extention?

as in:

/* assign x the position of the most signifigant bit set in y */
x = msbs(y); 
/* assign x the position of the least signifigant unbit set in y */
x = lsbus(y); 

The reason is that the C primatives for bit ops are quite poor for scanning
bit strings and most modern hardware supports some of these ops with a 
single fast instruction (instead of forcing the coder to use a clumsy
for loop).

This can really help people doing low end harware work that have to decode
bit encoded registers...

thanks,
-Alfred