Greetings,

In C/C++, I'm wondering, how to I simulate a bit-rotate operation? I can do the shift with the "<<" ">>" operators but the only way I can think to rotate (I can't inline, because it'll be managed C++)...



if rotate left and high bit not set
shift-left
if rotate left and high bit set
test high-bit
shift-left

if high bit set
set low-bit

if rotate right and low bit not set
shift-right
if rotate right and low bit set
test low-bit
shift-right

if low bit set
set high-bit



Is this roughly what I would need to do?


Thanks,
_Shawn
Posted on 2003-10-08 19:06:30 by _Shawn
Posted on 2003-10-08 21:19:03 by bitRAKE
I'm no coding guru, but your method seems to use excessive jumping (with "if"s)...all you really need to do is use a couple shifts and an OR.

Also I don't know a ton about C/C++...maybe there is a rotate operand?

I don't know exactly what you mean by "managed C++", but assuming you can use shifts, subtract, and bitwise OR operand:



// (C/C++ code...)
// "rolvar" is a variable...rotating "x" bits to left
rolvar = (rolvar << x) | (rolvar >> (sizeof(rolvar) - x) )

// "rorvar" is a variable...rotating "x" bits to right
rorvar = (rolvar >> x) | (rolvar << (sizeof(rorvar) - x) )




Example: rolvar==01101010b, x==3

sizeof(rolvar)-x == 8-3 == 5
rolvar << 5 == 01000000b
rolvar >> 3 == 00001101b
OR == 01001101b

---

This method is still a lot slower than an asm rol instruction, but better than the (relatively) complex system of jmps you were proposing...

Like I said, I'm no ASM/C/C++ master...probably someone else will show me up in a sec here, but maybe this can get you started :)

/Edit: AHHH!!! Beaten to the post :grin: . (Interestingly, my method was the same used in the rotate lib on the website BitRAKE linked to...guess I had the right idea ;) )
Posted on 2003-10-08 21:20:10 by sirchess2
There's no rotation in C++, for the simple reason that the C++ standard does not define the number of bits in its data types (int, long, short etc.). And what's the use of rotating if you don't know that :) Sure, on x86 you can assume an int will be 4 bytes but rotating bits is too platform specific to be part of the standard.

Thomas
Posted on 2003-10-09 02:02:33 by Thomas
I wonder whether late MS compilers will optimize an instruction sequence like that to rol/ror? Also, there's the (non-standard, implementatoin-specific etc) _lrotl/_lortr functions - but I don't know whethre they can be used with managed code.
Posted on 2003-10-09 07:34:14 by f0dder
Managed C++ is when it gets compiled for the .NET runtime. I can't use inline assembly so I have to do it with the operators (I'm also trying this in C# because I don't want to rewrite the application in MC++ if I don't have to).

I'm trying to create a Binary object that does low-level bit manipulation because, of all things, laugh be down if you will, I'm writing a 65c02 simulator in C#. It won't matter if I write it in MC++ because it'll still end up in the JITter the same way. But it produces really tight code.

I'll look further into the link above... I did get the number to binary algorithm working...



[C#]

public override string ToString() {
string result = "";

uint num = Value;
byte no_bits = Bits(num);
byte count;

if (no_bits > 0) {
no_bits--;
}

for( count=no_bits; count>=0 && count<=80; count-- ) {
result += Convert.ToString(((num >> count) & 01));
}

return result;
}

private byte Bits(uint value) {
byte i=0;

for(; value !=0; value >>= 1 ) {
i++;
}

return i;
}


I also got the part working where I can extract low and high byte from a WORD



[C#]

public struct Register {
public byte PCL; // Program Counter Low-byte
public byte PCH; // Program Counter High-byte

public ushort Address {
get {
if (this.PCH != 0) {
return (ushort)((this.PCH * 0x0100) + this.PCL);
}
else {
return (ushort)(this.PCL);
}
}
set {
ushort t = (value << 8);

this.PCH = (byte)(value >> 8);
this.PCL = (byte)(t >> 8);
}
}
}


Now I have to get the binary to number working and the rotate.


Thanks,
_Shawn
Posted on 2003-10-09 11:07:26 by _Shawn
That bit wizardy link was very useful, can't believe how simple it is. The problem I'm having is that I need to rotate 8 and 16 bit values also and the framework only allows these bit shift operations on 32-bit and 64-bit values (both signed and unsigned).

So what I need to do in the case of a 8 or 16-bit value, for the rotate, somehow allow it to take place but set the low or high bit if necessary and then down-cast the result to a byte or short if need be...

How would I do that?


Thanks,
Shawn
Posted on 2003-10-09 15:40:51 by _Shawn
Posted on 2003-10-09 20:12:16 by bitRAKE
I wrote these macros some time ago. Maybe they will be useful to you.


[b]#define ROR(n,r) ((n>>r)|(n<<((sizeof(n)*8)-r)))


#define ROL(n,r) ((n<<r)|(n>>((sizeof(n)*8)-r)))[/b]



Edit: Ooops. :grin: I should really read these threads before I post. ;)
Posted on 2003-10-09 22:26:21 by iblis
this works better than the bitmrotate link above:

rotateleft
return (((val << count) | (val >> (SIZE-count))) & 0xFF);

rotateright
return ((val >> count) | (val << (SIZE-count))) & 0xFF);


you would mask the end 0xFFFF for 16-bit rotates. Works like a charm.


Thanks,
_Shawn
Posted on 2003-10-10 15:56:53 by _Shawn