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