What is the fastest way (in SPIN) to rotate a specific number of bits

Bobb Fwed

I need a method that rotates a specified number of bits (not necessarily 32, so I can't use ->/<-).

For example, the method could be called light this smallROR(%11_1011_0100 {value}, 10 {bit count}, 3 {bits to rotate}) and the result should be %10_0111_0110. I need both rotate left and right.
And just like how the rotate instructions work, I need it to accept rotate values larger than the number of bits being rotated. So for our 10-bit example, if bits to rotate were 13, it would yield the same result.

Here is what I have so far, but I know you guys will come up with a much better way of doing it:

PUB smallROR (value, bitsize, rotatebits)
'' Mimics rotate instruction, but for a bit count less than 32 (great for rotating a byte or a word)
'' bitsize is the rotation bountries (everything outside of the lower bits will be removed)
'' rotatebits is the number of bits to rotate

  RETURN (((value &= (|< bitsize) - 1) & ((|< (rotatebits //= bitsize)) - 1)) << (bitsize - rotatebits)) | (value >> rotatebits)                           

{PUB smallROR (value, bitsize, rotatebits) | upper
'' Expanded version of the above method

  rotatebits //= bitsize                                                        ' constrain rotation
  value &= (|< bitsize) - 1                                                     ' constrain value
  upper := value & ((|< rotatebits) - 1)                                        ' get what will go in the upper bits
  value >>= rotatebits                                                          ' shift bits lower
  value |= upper << (bitsize - rotatebits)                                      ' put upper bits in place
  RETURN value                             
}
PUB smallROL (value, bitsize, rotatebits) | dif
'' Mimics rotate instruction, but for a bit count less than 32 (great for rotating a byte or a word)
'' bitsize is the rotation bountries (everything outside of the lower bits will be removed)
'' rotatebits is the number of bits to rotate

  RETURN ((((|< (rotatebits //= bitsize) - 1) << (dif := (bitsize - rotatebits))) & value) >> dif) | (value << rotatebits) & ((|< bitsize) - 1)

{PUB smallROL (value, bitsize, rotatebits) | lower, dif
'' Expanded version of the above method 

  rotatebits //= bitsize                                                        ' constrain rotation
  dif := (bitsize - rotatebits)                                                 ' number of bits to shift
  lower := ((|< (rotatebits) - 1) << dif & value) >> dif                        ' get what will go to the lower bits
  value <<= rotatebits                                                          ' shift bits higher
  value &= (|< bitsize) - 1                                                     ' constrain value
  value |= lower                                                                ' put lower bits in place
  RETURN value                                                                  
}

lonesock

I think this works, at least for rotatebits < bitsize:

PUB smallROR( value, bitsize, rotatebits )
  return {
    } (value >> rotatebits) | {
    } (value << (32 - rotatebits) >> (32 - bitsize))

Jonathan

Bobb Fwed

Doesn't work with the larger rotate bits as specified, but easy to add the modulus on it.

Anyone else with a potentially better solution (seems hard).

And here is why I ask on the forums, because that is so much more ellegant and so much faster it's not even comparable.

Bobb Fwed

lonesock wrote: »

I think this works, at least for rotatebits < bitsize:

PUB smallROR( value, bitsize, rotatebits )
  return {
    } (value >> rotatebits) | {
    } (value << (32 - rotatebits) >> (32 - bitsize))

Jonathan

So here is the fixed method and the counterpart method (is this the best way?):

PUB smallROR (value, bitsize, rotatebits)
  RETURN (value >> (rotatebits //= bitsize)) | (value << (32 - rotatebits) >> (32 - bitsize))

PUB smallROL (value, bitsize, rotatebits)  
  RETURN ((value << (rotatebits //= bitsize)) | (value >> (bitsize - rotatebits))) & ((|< bitsize) - 1)

lonesock

smallROL is one byte smaller than smallROR...good job!

Jonathan

kuroneko

This sounds familiar, see http://forums.parallax.com/showthread.php/145536-Special-form-of-ROL-and-ROR-spin-instruction-with-arbitrary-length-rotate-distance?p=1160228&viewfull=1#post1160228. Maybe not entirely the same but close enough I'd say (before morning coffee).