Jump to content
Tuts 4 You

Bitwise rotation with C/C++ and Delphi

ghandi

By ghandi
in Programming and Coding

Recommended Posts

ghandi

ghandi

Posted
Posted (edited)

Hi all,

I posted this topic over on ARTeam forum and thought that maybe someone might find this useful here also? If not, disregard this post and forget you ever read it, ;).

I recently tried converting some of my assembler code across to C and Delphi and it required bitwise rotations. Although the C compiler will optimise in rotations, natively they are not accessible that i am aware of. To use them you either have to use intrinsics or inline assembler, the other option is to define macros which use bitwise SHL/SHR and and OR to achieve a psuedo-rotation. I'm not sure whether or not the Delphi 7 compiler will place rotations in, but i know you can use inline assembler or a function (Delphi doesn't support macros :( ) to achieve the same thing.

As always, the first place i look is Google because i normally find a good explanation of what i'm searching for and some code examples. Digging through there were plenty of macros and functions to choose from, but none of them seemed to achieve what my assembler code did and that was a simple ROR on an 8 bit register with position values ranging from 0x00/$00 to 0xFF/$FF. OllyDbg provided the answer and unhappy with the bitwise rotation macros i found while Googling, i decided to write my own instead of using inline assembler.

The problem with the ones i found was although they accomplished a bitwise rotation, this was only accurate if the rotation amount was within the bitsize boundary. So, if it was a 32 bit rotation macro and the rotation called for a rotation of 33 positions, then the value was lost. See the examples below for a clearer picture:


{Delphi}
function ROR32(value : dword ; n : integer) : dword ;
begin
  result := (value shr n) or (value shl (32-n))
end ;/*C/C++*/
#define ROR(x,n) (((x) >> n) | ((x) << (32-n)))

As the above code examples show, the 'rotation' is achieved by shifting the bits N positions to the right, then the resulting value is ORed with the result of shifting the value 32 - N positions to the left. If N > 32, then the value is lost because the shift will push the bits out of the register on both sides.


// Using a 32 bit register, if a 16 or 8 bit is required change the value 
// or use a constant value defined above the function/macro definition.{Delphi}
function ROR(value:dword; n:integer): dword;
var
x:integer;
begin
  x := n mod 32;
  result := (value shr x) or (value shl (32-x)));
end;/*C/C++*/
#define ROR(x,n) (((x) >> (n % 32)) | ((x) << (32-(n % 32))))

In these two however, by dividing the N amount with the register size and keeping the modulus, we get the eventual position of the bits, indexed within the bounds of the register. Then we can shift the value left and right by the modulus amount and OR both results to achieve an accurate psuedo-rotation. If anybody can verify or dispute this for either C/C++ or Delphi (i only tested the Delphi version, not the C/C++), it would be appreciated.

HR,

Ghandi

Edited by ghandi
  • Like 1
Link to comment
BoB

BoB

Posted
Posted

But why do it in pure Pascal? It's simpler and smaller in BAsm function ..

Function  ROR(Value : DWord; N : Integer) : DWord;
Asm
  // In: EAX = Value, EDX = N ..
  XChg EDX, ECX
  Ror  EAX, CL
End;
Link to comment
ghandi

ghandi

Posted
  • Author
Posted

but i know you can use inline assembler or a function (Delphi doesn't support macros ) to achieve the same thing.

But why do it in pure Pascal? It's simpler and smaller in BAsm function ..

Thanks for the feedback BoB. It's mainly because i'm seeing if i can implement some assembler functions as pure Pascal/Delphi and C/C++, just as a personal task/challenge. Inline assembler is handy, coding assembler functions is good also and they're things i'll have to use when i can't translate it to Delphi (i'm only a beginner with Delphi, BoB) :D

HR,

Ghandi

Link to comment
BoB

BoB

Posted
Posted

Ah I see, I was just wondering if there was some reason why it couldn't be in BAsm :)

Well if you ever need any help with Delphi, send me an email ;)

Have fun!

Link to comment
Killboy

Killboy

Posted
Posted

C++ equivalent would be:

template<typename T> T rol(T val, size_t count)

{

size_t bitcount = sizeof(T) * 8;

count %= bitcount;

return (val << count) | (val >> (bitcount-count));

}

template<typename T> T ror(T val, size_t count)

{

size_t bitcount = sizeof(T) * 8;

count %= bitcount;

return (val >> count) | (val << (bitcount-count));

}

Link to comment
hero_hont

hero_hont

Posted
Posted

Thanks Killboy, i've updated the thread over at ARTeam to reflect this (with proper credit of course). :thumbsup:

HR,

Ghandi

hello you.

I am known about programming languages C/C++ and C#.

I can write code assembly and Matlab, AVR but i don't know about Dephi.

hih, not bad//

Link to comment
  • 4 years later...
PleasantStorm

PleasantStorm

Posted
Posted

Great function and very elegant in it's simplicity. Writing such functions in Pascal rather than assembler is great for the modern Delphi compilers (XE 1 through 7 as of this reply) as well, because many of them are cross platform and some assembler instructions aren't supported between the various cpu compile targets. Assembler is great for tight loops where speed and efficiency really count. Most compilers output code that is nearly as efficient as pure assembler in this day and age of processors that are rapidly approaching the Terahertz range of instruction cycles per second.


 


I hope that it works just as well with Int64 as it does a DWORD with a bit of tinkering.


 


Thanks Ghandi,


 


PleasantStorm


Link to comment
PleasantStorm

PleasantStorm

Posted
Posted
Here's an implementation of your function Ghandi with overloads to handle all of the different integer types possible. As well we use the built in SizeOf(type) * 8 to get the bit width of the type being used. Thanks for sharing. ;-)

 

...

 

interface

 

  (*

    Ror and Rol Function provided at


    Improved and reposted by yours truly.

  *)

  function Ror(Value: Byte; N: Integer): Byte; overload;

  function Rol(Value: Byte; N: Integer): Byte; overload;

  function Ror(Value: ShortInt; N: Integer): ShortInt; overload;

  function Rol(Value: ShortInt; N: Integer): ShortInt; overload;

 

  function Ror(Value: Word; N: Integer): Word; overload;

  function Rol(Value: Word; N: Integer): Word; overload;

  function Ror(Value: SmallInt; N: Integer): SmallInt; overload;

  function Rol(Value: SmallInt; N: Integer): SmallInt; overload;

 

  function Ror(Value: LongWord; N: Integer): LongWord; overload;

  function Rol(Value: LongWord; N: Integer): LongWord; overload;

  function Ror(Value: Integer; N: Integer): Integer; overload;

  function Rol(Value: Integer; N: Integer): Integer; overload;

 

  function Ror(Value: UInt64; N: Integer): UInt64; overload;

  function Rol(Value: UInt64; N: Integer): UInt64; overload;

  function Ror(Value: Int64; N: Integer): Int64; overload;

  function Rol(Value: Int64; N: Integer): Int64; overload;

 

implementation

 


uses SysUtils;

 



function Ror(Value: Byte; N: Integer): Byte; overload;

begin

  Result := (Value shr N) or (Value shl ((SizeOf(Value)*8)-n));

end;

 

function Rol(Value: Byte; N: Integer): Byte; overload;

begin

  Result := (Value shl N) or (Value shr ((SizeOf(Value)*8)-n));

end;

 

function Ror(Value: ShortInt; N: Integer): ShortInt; overload;

begin

  Result := (Value shr N) or (Value shl ((SizeOf(Value)*8)-n));

end;

 

function Rol(Value: ShortInt; N: Integer): ShortInt; overload;

begin

  Result := (Value shl N) or (Value shr ((SizeOf(Value)*8)-n));

end;

 

function Ror(Value: Word; N: Integer): Word; overload;

begin

  Result := (Value shr N) or (Value shl ((SizeOf(Value)*8)-n));

 

end;

 

function Rol(Value: Word; N: Integer): Word; overload;

begin

  Result := (Value shl N) or (Value shr ((SizeOf(Value)*8)-n));

end;

 

function Ror(Value: SmallInt; N: Integer): SmallInt; overload;

begin

  Result := (Value shr N) or (Value shl ((SizeOf(Value)*8)-n));

 

end;

 

function Rol(Value: SmallInt; N: Integer): SmallInt; overload;

begin

  Result := (Value shl N) or (Value shr ((SizeOf(Value)*8)-n));

end;

 

 

function Ror(Value: LongWord; N: Integer): LongWord; overload;

begin

  Result := (Value shr N) or (Value shl ((SizeOf(Value)*8)-n));

end;

 

function Rol(Value: LongWord; N: Integer): LongWord; overload;

begin

  Result := (Value shl N) or (Value shr ((SizeOf(Value)*8)-n));

end;

 

function Ror(Value: Integer; N: Integer): Integer; overload;

begin

  Result := (Value shr N) or (Value shl ((SizeOf(Value)*8)-n));

end;

 

function Rol(Value: Integer; N: Integer): Integer; overload;

begin

  Result := (Value shl N) or (Value shr ((SizeOf(Value)*8)-n));

end;

 

function Ror(Value: UInt64; N: Integer): UInt64; overload;

begin

  Result := (Value shr N) or (Value shl ((SizeOf(Value)*8)-n));

 

end;

 

function Rol(Value: UInt64; N: Integer): UInt64; overload;

begin

  Result := (Value shl N) or (Value shr ((SizeOf(Value)*8)-n));

end;

 

function Ror(Value: Int64; N: Integer): Int64; overload;

begin

  Result := (Value shr N) or (Value shl ((SizeOf(Value)*8)-n));

 

end;

 

function Rol(Value: Int64; N: Integer): Int64; overload;

begin

  Result := (Value shl N) or (Value shr ((SizeOf(Value)*8)-n));

end;

 

end.

 


...

 

That compiles and executes fine in Delphi XE 4 as is should in other versions (not sure of how the presence of the overload specifier in the implementation might be handled on earlier compilers but its easily remedied with conditional directives).

 

Thanks again and enjoy!

 

PleasantStorm

 

Link to comment
PleasantStorm

PleasantStorm

Posted
Posted
Sorry, Here's the corrected implementation...

 


 

...

 

interface

 

  (*

    Ror and Rol Function provided at


    Improved and reposted by yours truly.

  *)

  function Ror(Value: Byte; N: Integer): Byte; overload;

  function Rol(Value: Byte; N: Integer): Byte; overload;

  function Ror(Value: ShortInt; N: Integer): ShortInt; overload;

  function Rol(Value: ShortInt; N: Integer): ShortInt; overload;

 

  function Ror(Value: Word; N: Integer): Word; overload;

  function Rol(Value: Word; N: Integer): Word; overload;

  function Ror(Value: SmallInt; N: Integer): SmallInt; overload;

  function Rol(Value: SmallInt; N: Integer): SmallInt; overload;

 

  function Ror(Value: LongWord; N: Integer): LongWord; overload;

  function Rol(Value: LongWord; N: Integer): LongWord; overload;

  function Ror(Value: Integer; N: Integer): Integer; overload;

  function Rol(Value: Integer; N: Integer): Integer; overload;

 

  function Ror(Value: UInt64; N: Integer): UInt64; overload;

  function Rol(Value: UInt64; N: Integer): UInt64; overload;

  function Ror(Value: Int64; N: Integer): Int64; overload;

  function Rol(Value: Int64; N: Integer): Int64; overload;

 

implementation

 

uses SysUtils;

 


function Ror(Value: Byte; N: Integer): Byte; overload;

begin

  N := N mod (SizeOf(Value)*8);

  Result := (Value shr N) or (Value shl ((SizeOf(Value)*8)-n));

end;

 

function Rol(Value: Byte; N: Integer): Byte; overload;

begin

  N := N mod (SizeOf(Value)*8);

  Result := (Value shl N) or (Value shr ((SizeOf(Value)*8)-n));

end;

 

function Ror(Value: ShortInt; N: Integer): ShortInt; overload;

begin

  N := N mod (SizeOf(Value)*8);

  Result := (Value shr N) or (Value shl ((SizeOf(Value)*8)-n));

end;

 

function Rol(Value: ShortInt; N: Integer): ShortInt; overload;

begin

  N := N mod (SizeOf(Value)*8);

  Result := (Value shl N) or (Value shr ((SizeOf(Value)*8)-n));

end;

 

function Ror(Value: Word; N: Integer): Word; overload;

begin

  N := N mod (SizeOf(Value)*8);

  Result := (Value shr N) or (Value shl ((SizeOf(Value)*8)-n));

end;

 

function Rol(Value: Word; N: Integer): Word; overload;

begin

  N := N mod (SizeOf(Value)*8);

  Result := (Value shl N) or (Value shr ((SizeOf(Value)*8)-n));

end;

 

function Ror(Value: SmallInt; N: Integer): SmallInt; overload;

begin

  N := N mod (SizeOf(Value)*8);

  Result := (Value shr N) or (Value shl ((SizeOf(Value)*8)-n));

end;

 

function Rol(Value: SmallInt; N: Integer): SmallInt; overload;

begin

  N := N mod (SizeOf(Value)*8);

  Result := (Value shl N) or (Value shr ((SizeOf(Value)*8)-n));

end;

 

 

function Ror(Value: LongWord; N: Integer): LongWord; overload;

begin

  N := N mod (SizeOf(Value)*8);

  Result := (Value shr N) or (Value shl ((SizeOf(Value)*8)-n));

end;

 

function Rol(Value: LongWord; N: Integer): LongWord; overload;

begin

  N := N mod (SizeOf(Value)*8);

  Result := (Value shl N) or (Value shr ((SizeOf(Value)*8)-n));

end;

 

function Ror(Value: Integer; N: Integer): Integer; overload;

begin

  N := N mod (SizeOf(Value)*8);

  Result := (Value shr N) or (Value shl ((SizeOf(Value)*8)-n));

end;

 

function Rol(Value: Integer; N: Integer): Integer; overload;

begin

  N := N mod (SizeOf(Value)*8);

  Result := (Value shl N) or (Value shr ((SizeOf(Value)*8)-n));

end;

 

function Ror(Value: UInt64; N: Integer): UInt64; overload;

begin

  N := N mod (SizeOf(Value)*8);

  Result := (Value shr N) or (Value shl ((SizeOf(Value)*8)-n));

end;

 

function Rol(Value: UInt64; N: Integer): UInt64; overload;

begin

  Result := (Value shl N) or (Value shr ((SizeOf(Value)*8)-n));

end;

 

function Ror(Value: Int64; N: Integer): Int64; overload;

begin

  N := N mod (SizeOf(Value)*8);

  Result := (Value shr N) or (Value shl ((SizeOf(Value)*8)-n));

end;

 

function Rol(Value: Int64; N: Integer): Int64; overload;

begin

  N := N mod (SizeOf(Value)*8);

  Result := (Value shl N) or (Value shr ((SizeOf(Value)*8)-n));

end;

 

end.

 

PleasantStorm
Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Go to topic listing
×
×
  • Create New...