This has probably come up before, but I think it would be good if perl
had two additional arithemetic operators:

	>>>	would be a right shift _without_ sign extension
		under use integer (currently, under use integer,
		>> is at the mercy of the underlying C lib).
	<<<	would be a left roll ($x <<< $y would be equivalent
		to ( ($x << $y) | (2**$y-1) & ($x >> (32-$y)) )
		
these two ops would come in handy when implementing cryptographic
algorithms.  I guess you could argue that >>> should be a right roll,
but then I don't see a good way to get >> not to sign extend under
use integer, other than making it _never_ sign extend.

There is probably some aberrent code that adding these ops would break,
but I think it would be worth it.

Any comments?

John.

On 22 Jan 01, at 12:32, John L. Allen wrote:

> 	>>>	would be a right shift _without_ sign extension
> 		under use integer (currently, under use integer,
> 		>> is at the mercy of the underlying C lib).
> 	<<<	would be a left roll ($x <<< $y would be equivalent
> 		to ( ($x << $y) | (2**$y-1) & ($x >> (32-$y)) )

To my mind, this would make these two things nastily asymmetric, since 
they represent fairly different things (rotate vs. shift). Oh, and 
where did the number "32" come from in your description of <<<? (Hint, 
hint.)

> these two ops would come in handy when implementing cryptographic
> algorithms.

Depends. Most algorithms that use rotate, I imagine, specify how many 
bits to rotate. I'm not sure whether you can guarantee that in Perl 
(not if you want to be portable across different Perls, anyway).

> There is probably some aberrent code that adding these ops would break,
> but I think it would be worth it.

Example: <IN>>>4 is now <IN>  >> 4. With maximal munch (does Perl's 
tokeniser use that?), this'd be < IN >>> 4 "unmatched '<'". (Hm, 
obviously not; <IN>>4 is not <IN >> 4 but <IN> > 4. Still. How about 
4<<<IN>, which is now 4 << <IN> -- note that 4<<IN> is a syntax error 
rather than 4 < <IN> (at least, in 5.005_03).

Cheers,
Philip
-- 
Philip Newton <Philip.Newton@gmx.net>

On Tue, 23 Jan 2001 06:57:11 +0100, "Philip Newton" <Philip.Newton@gmx.net> wrote:
> > There is probably some aberrent code that adding these ops would break,
> > but I think it would be worth it.
> 
> Example: <IN>>>4 is now <IN>  >> 4. With maximal munch (does Perl's 
> tokeniser use that?), this'd be < IN >>> 4 "unmatched '<'". (Hm, 
> obviously not; <IN>>4 is not <IN >> 4 but <IN> > 4. Still. How about 

where <IN > would probably be parsed as glob '("IN")' giving back a list which
will be tested against a number, so the test is if <IN > (as a glob) returns
more than 4 elements (which is very unlikely for <IN > ;-))

> 4<<<IN>, which is now 4 << <IN> -- note that 4<<IN> is a syntax error 
> rather than 4 < <IN> (at least, in 5.005_03).

-- 
H.Merijn Brand           Amsterdam Perl Mongers (http://www.amsterdam.pm.org/)
using perl-5.005.03, 5.6.0, 5.6.1, 5.7.1 & 623 on HP-UX 10.20 & 11.00, AIX 4.2
   AIX 4.3, WinNT 4.0 SP-6a, and Win2000pro often with Tk800.022 &/| DBD-Unify
ftp://ftp.funet.fi/pub/languages/perl/CPAN/authors/id/H/HM/HMBRAND/

On Tue, 23 Jan 2001, Philip Newton wrote:
> On 22 Jan 01, at 12:32, John L. Allen wrote:
> 
> > 	>>>	would be a right shift _without_ sign extension
> > 		under use integer (currently, under use integer,
> > 		>> is at the mercy of the underlying C lib).
> > 	<<<	would be a left roll ($x <<< $y would be equivalent
> > 		to ( ($x << $y) | (2**$y-1) & ($x >> (32-$y)) )
> 
> To my mind, this would make these two things nastily asymmetric, since 
> they represent fairly different things (rotate vs. shift). Oh, and 
> where did the number "32" come from in your description of <<<? (Hint, 
> hint.)

I guess I could live _with_ the symmetry. :-)  And I guess you're hinting
about machines with 64 bit integers.

> > these two ops would come in handy when implementing cryptographic
> > algorithms.
> 
> Depends. Most algorithms that use rotate, I imagine, specify how many 
> bits to rotate. I'm not sure whether you can guarantee that in Perl 
> (not if you want to be portable across different Perls, anyway).

Are you referring to 64 bit machines again here?  Things like MD5, for which
I have pure perl that has stuff like this in it:

    $a+=($b&($c^$d)^$d)+$W[ 0]+0xd76aa478;
	$a=($a<< 7|0x0000007f&($a>>25))+$b;
    $d+=($a&($b^$c)^$c)+$W[ 1]+0xe8c7b756; 
	$d=($d<<12|0x00000fff&($d>>20))+$a;
    $c+=($d&($a^$b)^$b)+$W[ 2]+0x242070db; 
	$c=($c<<17|0x0001ffff&($c>>15))+$d;
  
definitely needs specific shift values (like 7 and 12) and these will 
definitely not work on 64 bit int machines.  Hmmm, is there a 
``use integer32;'' ?

John.

John L . Allen <allen@grumman.com> writes:
>Are you referring to 64 bit machines again here?  Things like MD5, for which
>I have pure perl that has stuff like this in it:
>
>    $a+=($b&($c^$d)^$d)+$W[ 0]+0xd76aa478;
>	$a=($a<< 7|0x0000007f&($a>>25))+$b;
>    $d+=($a&($b^$c)^$c)+$W[ 1]+0xe8c7b756; 
>	$d=($d<<12|0x00000fff&($d>>20))+$a;
>    $c+=($d&($a^$b)^$b)+$W[ 2]+0x242070db; 
>	$c=($c<<17|0x0001ffff&($c>>15))+$d;
>  
>definitely needs specific shift values (like 7 and 12) and these will 
>definitely not work on 64 bit int machines.  Hmmm, is there a 
>``use integer32;'' ?

It seems to me that the example MD5 code is more portable and better
documents what is going on that a mystical rotate operator and a pragma
to make the machine behave in an un-natural width. Invent a 3-operand 

    rotate($val,$amount,$word_size) 

or similar.

>
>John.
-- 
Nick Ing-Simmons

On Wed, 24 Jan 2001, Philip Newton wrote:
> On 23 Jan 01, at 16:18, John L. Allen wrote:
> > On Tue, 23 Jan 2001, Philip Newton wrote:
> > > To my mind, this would make these two things nastily asymmetric, since 
> > > they represent fairly different things (rotate vs. shift). Oh, and 
> > > where did the number "32" come from in your description of <<<? (Hint, 
> > > hint.)
> > 
> > I guess I could live _with_ the symmetry. :-)  And I guess you're hinting
> > about machines with 64 bit integers.
> 
> Yes. Or who-knows-how-many bit integers. (Not all the world's a <insert 
> type of machine with which you're familiar here>.)
 
> > 	$c=($c<<17|0x0001ffff&($c>>15))+$d;
> >   
> > definitely needs specific shift values (like 7 and 12) and these will 
> > definitely not work on 64 bit int machines.
> 
> The right shifts will work fine, since you're masking off the higher 
> bits that might result. (At first, I thought that the mask applied to 
> the left shift, but the relative precedence of | and & got me. I would 
> have used more parentheses.) If you want that to work on 64 bit 
> machines, you probably only need an "&0xffffffff" in each line to chop 
> of "extra" bits resulting from left shifts. (Or, alternatively, mask 
> off extra bits before left shifting.) Then you only need >= 32 bits 
> rather than = 32 bits.

Do'h!  What a blunder on my part.  So then, algorithms that emulate 
rolls by shifting right and left and masking _will_ work without change on 
greater int size machines, but if there were a builtin roll operator that 
took the int size into account, algorithms that used it would _fail_ 
unless they were changed to use different roll amounts.  Thanks for 
catching that.  But I still think having <<< and >>> ops, along with 
``use integer 32|64|...'' to govern their operation, would be nice, but I 
gather I'm alone in this view.

Hmmm, doesn't gcc optimize the construct "(a>>n)|(a<<(32-n))" to a single 
machine instruction on those architectures that have one?  Could perl be 
made to optimize the same thing?  

John.

On Tue, 23 Jan 2001, Jarkko Hietaniemi wrote:

> > It seems to me that the example MD5 code is more portable and better
> > documents what is going on that a mystical rotate operator and a pragma
> > to make the machine behave in an un-natural width. Invent a 3-operand 
> > 
> >     rotate($val,$amount,$word_size) 
> > 
> > or similar.
> 
> Agreed.  There is a slew of bit operations we don't support in the
> core (as operators).  For example you cannot shift a bitvector.  You
> can't reverse a bitvector.  You can't find the highest or the lowest
> bit of a bitvector.

One man's precedent is another man's deficiency :-) but I see your point.

John.

John L . Allen <allen@grumman.com> writes:
>
>Hmmm, doesn't gcc optimize the construct "(a>>n)|(a<<(32-n))" to a single 
>machine instruction on those architectures that have one?  

I seem to recall it does attempt to - but was very picky about 
exactly how it was written.

-- 
Nick Ing-Simmons <nik@tiuk.ti.com>
Via, but not speaking for: Texas Instruments Ltd.

> I don't know what you'd do about operator overloading, though. 

It would also fail if the argument were tied.  (A << C1) + (A >> C2)
should perform two FETCH calls on A, and the optimized version would
perform only one.

On Wed, 24 Jan 2001, Stephen McCamant wrote:

> >>>>> "JLA" == John L Allen <allen@grumman.com> writes:
> 
> JLA> Hmmm, doesn't gcc optimize the construct "(a>>n)|(a<<(32-n))" to
> JLA> a single machine instruction on those architectures that have
> JLA> one?
.... 
> JLA> Could perl be made to optimize the same thing?
> 
> Anything is possible. This in fact wouldn't be all that difficult, say
> in a ck_ routine; you'd just have to have a long sequence of ifs. It
> strikes me as a little odd in light of how little other numeric
> optimization perl does, thoug (constant folding is about the only
> thing). You wouldn't need to bother to determine whether your
> architecture really had a rotate instruction, since the big speedup
> wouldn't come from saving bit operations -- it would be in reduced OP
> overhead.

I've now got this odd notion in my head that we could get much better
and more general results by creating an XS Math::Fast module that would
essentially emulate a simple CPU in C code: you'd pass it a string with your
minimalist "program" in it, and it would rip through it maybe 10 times 
faster than perl could, but still maybe 10 times slower than native C.  
For example,

	use Math::Fast;
	$x = 0x12345678; $y = 0x9abcdef0;
	Math::Fast::Do '
		int x, y, t, i;	 # declare some integers
		x = $x; y = $y;  # retrieve scalars from perl
		for (i = 0; i < 1000000; i++) {
		  t += x ^ (y << i); u = y ^ ((x << i) | (x >> (32-i)));
		}
		$t = t;		 # set a perl var when done
	';
	print "t = $t\n";

I guess you could handle ints and floats equally easily, and you would be 
limited to fortran-77-like flow control structures.

This would be a sort of poor man's Inline module, slower, no doubt, but 
not needing a C compiler at runtime.  But maybe I'm overestimating how
much faster than perl such a thing could be.

Ok, maybe I've been smoking something funny...

John.