OpenEuphoria

Re: fast bit rotation

• Posted by Tommy Carlier <tommy.carlier at pandora.be> Dec 31, 2003
• 454 views

Pete wrote:
> Another thing you could try is to build tables of pre-computed shifts,
> eg:
>
> sequence shl, shr
> shl=repeat(0,256)
> shr=repeat(0,256)
> for i = 0 to 255 do
> if i<=127 then
> shl[i+1]=i*2
> else
> shl[i+1]=and_bits(i,#7F)*2+1
> end if
> shr[shl[i+1]+1]=i
> end for
>
> Use k=shl[k+1] when k is 0..255, to avoid zero index problems.
>
> You can do your own test/timings, though I got 3.9 million/sec on a
> 233MHz PII with 48Mb ram, sorry Tommy, CNR )

Of course lookup tables are a lot faster. But the sequences above only 
work on 8-bit values between 0 and 255, and shift instead of rotate, and I 
think that jiri asked for integer (=32-bit) rotations. If you only need 
8-bit rotations, you should definitely go for the pre-computed lookup 
sequences. Perhaps my machine-code version (which BTW only works on 
Intel-compatible microprocessors) could even be tweaked a little further: 
does anybody know if it's OK to replace PUSHA/POPA with PUSH EAX/POP EAX, 
if I only modify EAX? I think it would definitely be faster.

>
> Pete
> PS No warranty on the above code, btw.

-- 

Tommy Carlier
tommy online: http://users.pandora.be/tommycarlier