ROTL/R

I have already done it in C++/asm for the work item that
required it.
Of course doing this brings its own overhead so my routine
now pretty
much sucks for small sets (well by suck I mean it took on a
good bit
of overhead) so I also included a managed version using the
shifts for
doing lots of small tasks.

I also have a "for fun" item that could use this
that I have been working on.

As of now its x86 only but many other processors have ways
of doing
this ... I am still attempting to get mono to compile (spent
4 hours
on it last night) ... Between installing cygwin and
downloading from
svn took well over 2, now I am fighting with a glib2-devel
problem on
my installation.

Adding the instructions seems like it will be rather
straight forward
from looking at how the shifts are handled ... I have not
yet looked
at the optimization possibility there but if I can ever get
it to
build I will.

Cheers,

Greg
On 7/22/06, Peter Ritchie
<dotnetclr.discuss.develop.competerritchie.com> wrote:
> >I would also be perfectly happy with Barry's
suggesting of recognizing
> >the shift pattern and replacing accordingly during
JIT.
>
> I think this should be part of each JIT regardless. 
This would allow the
> two aforementioned methods to be added the the BCL in
the Math namespace
> (I'm too lazy to check if Math is part of BCL, I'm
assuming) which would
> provide a most optimized method.
>
> If, from there, a set of ROT instructions were added to
IL, BCL
> implementers could use it at their leisure.
>
> Really, you're looking at a couple of scenarios:
optimizing a ROT pattern
> and implementing a quick ROT.  Both should be covered,
IMHO.
>
> Having said that.  Short term, you're going to have to
go unmanaged...
> Have you considered writing a really small assembly
written in C++ with a
> method attributed as native and embed some assembly
language into the
> method to force a call to Intel instructions (pick one:
RCL, RCR, ROL,
> ROR)?  It would have some security overhead; but, would
at least let you
> get a faster ROT (although the method invocation may
increase it...)
>
> You may have to perform the whole loop in within a C++
assembly to get the
> lovely inline keyword, if speed is that much of an
issue, and a C++ method
> does what you want (it certainly would be the fastest
solution).
>
> Out of curiosity, are you targeting anything other than
Intel?
>
> On Sat, 22 Jul 2006 13:03:19 -0400, gregory young
> <gregoryyoung1GMAIL.COM> wrote:
>
> >The problem is I am dealing with a situation where
that is too slow
> >even a hardcoded shift pattern to remove the ands +
the modulus is too
> >slow.
> >
> >The MS JIT also produces some un-needed code when
dealing with the
> >pattern (val >> 16) | (val << 16)
contains an extra mov... This may
> >not sound like much but this happens twice within a
tight loop.
> >
> >                    val = ((val) << 16) |
(val >> 16);
> >00000031  mov         eax,edx
> >00000033  shl         eax,10h
> >00000036  shr         edx,10h
> >00000039  or          eax,edx
> >0000003b  mov         edx,eax
> >                    *end = val;
> >0000003d  mov         dword ptr [ecx],edx
> >
> >ok maybe I am being too picky but I would really
like to do this in
> >managed code  I could
just do this by copying 16 bits of memory at a
> >time instead of 32 (but using this method with a
rotl would give me a
> >20% speed up)
> >
> >I would argue that the precedent to put it in IL
does not need to come
> >from C/C++, the precedent exists in the processors
it targets. Even
> >the processors that don't have a hardware
instruction i.e. PPC tend to
> >have a better way of doing this (on the PPC it
(atleast at some point)
> >used 2 32 bit registers to emulate a 64 bit
register and overflowed to
> >the second register then split and or'ed them back
together)
> >
> >I guess the point is when you need one, you
_really_ need one. Take a
> >look at performance differences in md5
implementations with and
> >without a hardware rot.
> >
> >I would also be perfectly happy with Barry's
suggesting of recognizing
> >the shift pattern and replacing accordingly during
JIT.
> >
> >Cheers,
> >
> >Greg
> >
> >On 7/22/06, Peter Ritchie
> ><dotnetclr.discuss.develop.competerritchie.com> wrote:
> >> public static uint RotateRight ( uint x, int
nBits )
> >> {
> >>  nBits = nBits % 0x20;
> >>  return ((x >> (nBits & 0x1f)) | (x
<< ((0x20 - nBits) & 0x1f)));
> >> }
> >> public static int RotateLeft ( int value, int
nBits )
> >> {
> >>  nBits = nBits % 0x20;
> >>  return ((value << (nBits & 0x1f)) |
(value >> ((0x20 - nBits) &
> >> 0x1f)));
> >> }
> >>
> >> License granted for unrestricted use as long
as changes
> >> (like "genericising") are
reposted. 
> >>
> >> I wouldn't hold your breath waiting for ROTn
to make into IL, there's
> not
> >> much precedence for those operations being
primitives. (or C/C++ and C#
> >> for that matter. See the CRT functions _rotl
and _rotr, et al.)  It
> would
> >> be nice to have these functions in the Math
namespace...
> >>
> >> On Fri, 21 Jul 2006 22:01:36 -0400, gregory
young
> >> <gregoryyoung1GMAIL.COM> wrote:
> >>
> >> >Thoughts on putting a ROTL ROTR
instruction into IL? The alternative
> >> >of shifting and oring is rather annoying
(and slow). If a processor
> >> >does not have a native ROTL/ROTR I would
imagine the JIT could emit
> >> >the shifting code but in the case that
there is a native instruction
> >> >you would probably get a good performance
gain.
> >> >
> >> >Naturally I bring this up for a greedy
reason in that right now I am
> >> >in desperate need of a ROTL 
>
> ===================================
> This list is hosted by DevelopMentor(r)  http://www.develop.com
>
> View archives and manage your subscription(s) at http://discuss.develop.com

>


--
If knowledge can create problems, it is not through
ignorance that we
can solve them.

Isaac Asimov

===================================
This list is hosted by DevelopMentorŪ  http://www.develop.com

View archives and manage your subscription(s) at http://discuss.develop.com