Is there high level operator/(inline)function for rotating bits?

Am I supposed to implement rotating bits (like ror/rol in i386 asm) by inline assembler or some ugly workarounds (shifts and or-s)?

Пётр Косаревский wrote

Is there high level operator/(inline)function for rotating bits?

No.

Am I supposed to implement rotating bits (like ror/rol in i386 asm) by inline assembler or some ugly workarounds (shifts and or-s)?

Yes. I think there's already a feature request to provide these operations, but no one worked on it yet.

Jonas

Why don't use this code?

{$INLINE ON}
interface
{$IFDEF CPUI386}
 function brol(b: byte; c: byte): byte; assembler; inline;
 function wrol(w: word; c: byte): word; assembler; inline;
 function lrol(l: longword; c: byte): longword; assembler; inline;
 function bror(b: byte; c: byte): byte; assembler; inline;
 function wror(w: word; c: byte): word; assembler; inline;
 function lror(l: longword; c: byte): longword; assembler; inline;
{$ELSE}
 function brol(b: byte; c: byte): byte; inline;
 function wrol(w: word; c: byte): word; inline;
 function lrol(l: longword; c: byte): longword; inline;
 function bror(b: byte; c: byte): byte; inline;
 function wror(w: word; c: byte): word; inline;
 function lror(l: longword; c: byte): longword; inline;
{$ENDIF}
implementation
{$IFDEF CPUI386}
 function brol(b: byte; c: byte): byte; assembler; inline;
   asm
   movb  b,%al
   movb  c,%cl
   rolb  %cl,%al
   movb  %al,result
   end ['al','cl'];
 function wrol(w: word; c: byte): word; assembler; inline;
   asm
   movw  w,%ax
   movb  c,%cl
   rolw  %cl,%ax
   movw  %ax,result
   end ['ax','cl'];
 function lrol(l: longword; c: byte): longword; assembler; inline;
   asm
   movl  l,%eax
   movb  c,%cl
   roll  %cl,%eax
   movl  %eax,result
   end ['eax','cl'];
 function bror(b: byte; c: byte): byte; assembler; inline;
   asm
   movb  b,%al
   movb  c,%cl
   rorb  %cl,%al
   movb  %al,result
   end ['al','cl'];
 function wror(w: word; c: byte): word; assembler; inline;
   asm
   movw  w,%ax
   movb  c,%cl
   rorw  %cl,%ax
   movw  %ax,result
   end ['ax','cl'];
 function lror(l: longword; c: byte): longword; assembler; inline;
   asm
   movl  l,%eax
   movb  c,%cl
   rorl  %cl,%eax
   movl  %eax,result
   end ['eax','cl'];
{$ELSE}
 function brol(b: byte; c: byte): byte; inline;
   var s,r: byte;
   begin
   s:=c and $7;
   r:=byte(b shl s);
   r:=r or byte(b shr (8-s)); // c may be over 8 and should be processed correctly
   brol:=r; // "result" is not supported in inline procedures
   end;
 function wrol(w: word; c: byte): word; inline;
   var s: byte; r: word;
   begin
   s:=c and $f;
   r:=word(w shl s);
   r:=r or word(w shr (16-s)); // c may be over 16 and should be processed correctly
   wrol:=r;
   end;
 function lrol(l: longword; c: byte): longword; inline;
   var s: byte; r: longword;
   begin
   s:=c and $1f;
   r:=longword(l shl s);
   r:=r or longword(l shr (32-s)); // c may be over 32 and should be processed correctly
   lrol:=r;
   end;
 function bror(b: byte; c: byte): byte; inline;
   var s,r: byte;
   begin
   s:=c and $7;
   r:=byte(b shr s);
   r:=r or byte(b shl (8-s)); // c may be over 8 and should be processed correctly
   bror:=r;
   end;
 function wror(w: word; c: byte): word; inline;
   var s: byte; r: word;
   begin
   s:=c and $f;
   r:=word(w shr s);
   r:=r or word(w shl (16-s)); // c may be over 16 and should be processed correctly
   wror:=r;
   end;
 function lror(l: longword; c: byte): longword; inline;
   var s: byte; r: longword;
   begin
   s:=c and $1f;
   r:=longword(l shr s);
   r:=r or longword(l shl (32-s)); // c may be over 32 and should be processed correctly
   lror:=r;
   end;
{$ENDIF}

Comments:
I. style/consistency
I didn't use all needed {$if}s: current code should word with range checks on both on i386 and not.

      {$Asmmode} was not used either.
      First symbol denotes type: while shl/shr emit longword, cyclic shifts shouldn't
      Endianness is not supported, because I don't understand, why it should be.
   II. performance
      "Result" is not supported in the inline mode.
      I don't know how to use "ret" to achieve the same goal with fewer commands.

Test:
{$INLINE ON}
program testb;
  uses commonthingies;
var i: byte;    b: byte;    w: word;    l: longword;
begin
write('Enter byte (dec):');readln(b);
for i:=0 to 16 do
  writeln('Orig:',binstr(b,8),'   Left:',binstr(brol(b,i),8),'   Right:',binstr(bror(b,i),8));
write('Enter word (dec):');readln(w);
for i:=0 to 32 do
  writeln('Orig:',binstr(w,16),'   Left:',binstr(wrol(w,i),16),'   Right:',binstr(wror(w,i),16));
write('Enter lw (dec)  :');readln(l);
for i:=0 to 64 do
  writeln('Orig:',binstr(l,32),'   Left:',binstr(lrol(l,i),32),'   Right:',binstr(lror(l,i),32));
end.

I don't know how to use "ret" to achieve the same goal with fewer commands.

Well, if I get it right (and it works on my system), the last lines: movb %al,result etc. (6 times) should be commented out.

.
.

.
.

With register calling convention (which is the default calling convention in FPC 2.x), it can be reduced just to:

function brol(b: byte; c: byte): byte; assembler; inline;
asm
  rolb  %cl,%al
end;

(and similarly for all the other functions). The first parameter goes to eax, the second to ecx, and the result is supposed to be in eax again.

Tomas

Well, I am jealous of your knowledge of the calling conventions. Did you notice, that in default compiler mode "mov %al,result" does not work?

Anyway, why don't introduce these functions?

That is by design. "result" only works in Delphi and ObjFPC modes. Otherwise you should use the function name instead of "result".

Jonas

Did you test it?

It does not work for me (one-liner).

("result" line does not seem to be needed, but calling conventions used seem to be somewhat different).

First parameter is in eax, second in edx (third one is ecx)

Jonas

The inline is useless, assembler procedures aren't really inlinable.

Jonas Maebe wrote

On 24 mei 2006, at 17:09, ����

Yes, of course, sorry for confusion... :-( Anyway, loading of the first parameter can be still skipped (and the stack frame is probably not useful in this case either). So you'd get:

function brol(b: byte; c: byte): byte; assembler; nostackframe; asm
movb %dl,%cl
rolb %cl,%al
end ['cl'];

Tomas

There is this page which might help some
http://www.merlyn.demon.co.uk/del-bits.htm

> First parameter is in eax, second in edx (third one is ecx)

TH> Yes, of course, sorry for confusion... :-( Anyway, loading of the first TH> parameter can be still skipped (and the stack frame is probably not useful TH> in this case either). So you'd get:
TH> function brol(b: byte; c: byte): byte; assembler; nostackframe; TH> asm
TH> movb %dl,%cl
TH> rolb %cl,%al
TH> end ['cl'];
TH> Tomas

1. So, is there any problem with including this functions and bit checks (bt./bs. in intel assembler: writing (a and (1 shl i)) isn't great too)?

2. Are calling conventions a subject to change? Are there ways to know about calling convention used (with {$ifdefs} e.g.)?

L> There is this page which might help some
L> http://www.merlyn.demon.co.uk/del-bits.htm

Thank you, it was interesting.

But it was not very helpful.

It's interesting, that they don't seem to care much about rotating bytes or words. (Asm rotating 64-bits was fascinating!)

I guess there is no problem in including it. The
only questions from my point of view are:

1) Are they useful in general, so that it would
make sense to include them either in FPC itself
(as opposed to some standalone unit)?

2) If they are to be included, should they be
included as functions, or possibly even as
operators (similarly to existing shl/shr)?

3) If we decide to include them as functions,
where (which unit)?

I personally don't have an answer for the first
question. What would be the typical use? For the
rest, my suggestion would be operators rather
than functions (if they are really needed), but
that would need somebody else than me to add the
appropriate compiler support (probably not a big
deal, I guess).

2. Are calling conventions a subject to change?

Possibly, although I wouldn't expect it any more.

Are there ways to know about calling convention used (with {$ifdefs} e.g.)?

If you need to support pre-2.x versions (and
especially early 1.9.x betas when the change
happened), then you could use {$IFDEF REGCALL}.
For 2.x+, using {$CALLING REGISTER} can be used
to force that calling convention (regardless of
the default).

Tomas

- they must be available for all cpu platforms, so we need at least a generic implementation
- for an efficient implementation, this needs a compiler patch so the compiler can really efficiently inline

Generic implementation in Pascal has already been provided in this thread as well, so this isn't an issue.

- for an efficient implementation, this needs a compiler patch so the compiler can really efficiently inline

Would this apply for the operator case too? Isn't it then similar to shl/shr (which "just work" now as well - even without special inlining support)?

Of course, this would only make sense if we're convinced about the general usefulness of such operators.

Tomas

They give the programmer access to CPU instructions which can speed up certain algorithms without the need to write assembler.

We can include them in some separate unit, but I would highly object against putting them in the system unit.

They make no sense then. Going through the whole calling sequence is
slower imo than or'ing shl/shr:
function brol(b: byte; c: byte): byte;inline;
  begin
    result:=(b shr (8-c)) or (b shl c);
  end;

which can be inlined perfectly by the compiler.

That's also why I added the endian conversion functions to the system unit, e.g. the compiler can benefit a lot if they are implemented in a CPU dependend way.

I don't think these functions are so useful that they warrant a compiler patch. We can include them in some separate unit, but I would highly object against putting them in the system unit.

Michael.

Well, they are useful for specific tasks and algorithms. There were reasons to include them in i386 architecture. But they are obviously less common, than shl/shr. My answer on question two explains, why their place is in units.

> > 2) If they are to be included, should they be > > included as functions, or possibly even as > > operators (similarly to existing shl/shr)?

Shl/shr already have a little issue: var b0,b1: byte; begin b0:=70; b1:=b0 shl 3; end. emits warning. They do not really pay attention (on intention?) to the size of what they shift.

Rol/ror should pay great attention to the size of data they shift. They cannot be implemented in the same manner.

> > 3) If we decide to include them as functions, > > where (which unit)?

Any rtl unit without a lot of $defines, overloading and redefinings should fit. Functions should have names, indicating size: unexpected typecasting may be fatal.

> - they must be available for all cpu platforms, so we need at least a > generic implementation

Even I have supplied some bulky implementation in one of the previous messages (I only wanted them to work, because my knowledge of FPC intrinsics is obviously not enough to ensure fast work).

> - for an efficient implementation, this needs a compiler patch so the > compiler can really efficiently inline

Maybe, it should be done regardless of "rotating bits" topic.

I don't think these functions are so useful that they warrant a compiler patch. We can include them in some separate unit, but I would highly object against putting them in the system unit. Michael.

I don't understand any of your arguments, but it doesn't matter much. Any rtl unit without much overhead suits great: I mean, including them to objfpc or sysutils would be strange.

While I do think having inlinable assembler would be a nice thing to have, I think it'd be a lot of work (one would have to assign params and results to registers as well as used regs).

But the problem with ROR/ROL is that any real use over shr/shl uses a hard to model carry flag?

What has rol/ror to do with the carry flag on pascal side? It means only rotate a variable.

But the problem with ROR/ROL is that any real use over shr/shl uses a hard to model carry flag?

Ugh, I don't understand well, but the talk is about rotating bits, no low level features like CF are requested (it doesn't mean very much if you rotate by several bits).

Who talked about CF? I didn't talk about RCL/RCR either.

2002-07-23 21:42 michael

* packages/base/md5/: Makefile, Makefile.fpc, md5.pp, md5.ref, md5test.pp:

+ Initial implementation

From packages/base/hash/md5.pp

procedure rot(var x: Cardinal; n: Byte);
begin
  x:=(x shl n) or (x shr (32 - n));
end;

You even implemented a rol :)

That's the point why I want to include compiler support: rol/ror is very important for several cryptographic algorithms.

The are somehow exotic but the key to speed up several cryptographic algorithms.

I program since 1984, and I have never seen these instructions used.

Well, if we're going in that direction anyway:
Why not include all possible assembler instructions then ?

Let's be serious. You must draw the line somewhere. I think these instructions are so exotic, they are pollution of the system unit.

Michael.

Well, if we're going in that direction anyway: Why not include all possible assembler instructions then ?

Because some of them are not designed for calculations. But ror/rol are.

Let's be serious. You must draw the line somewhere. I think these instructions are so exotic, they are pollution of the system unit. Michael.

They are widely used in encryption/decryption algorithms. Unfortunately, I don't really know why they were introduced in 8086 assembler.

That's the point why I want to include compiler support: rol/ror is very important for several cryptographic algorithms.

Agree! Since these are very important and relatively commonly used, I think it'd be better if they're implemented as new operators ("ror" and "rol") rather than as functions. Say we'll able to code like this:

a := b ror c;
x := y rol z;

Just what we have now with "shr" and "shl". I believe it won't break any compatibility with Delphi code, even we have new "feature" of FPC. :)

What do you think?

-Bee-

has Bee.ography at
http://beeography.wordpress.com

Adding new operators is much more work and error prone than simply adding new internal functions.

It would wreck havoc with typing. What should the result be of "1 ror 1"? $80? $8000? $80000000? $8000000000000000? $80000000 on 32 bit and $8000000000000000 on 64 bit cpus?

Jonas

Adding new operators is much more work and error prone than

Agree. I never made a compiler, and I hope I won't, nor interested. :D

I did make a simple SQL engine, though. AFAIK, adding a new operator, especially when a "similar" operator has existed before, wouldn't be too difficult. But, I believe this is not a fair comparison. :)

simply adding new internal functions.

It's okay, I can live with this too. :)

-Bee-

has Bee.ography at
http://beeography.wordpress.com

I believe the compiler knows the datatype and make an appropriate rotate action based on it. And knowing what the datatype is -I pressume- the programmer's responsibility. I think that's why we have bror (byte ror), wror (word ror), and lror (longint ror) functions within the sample code attached in this thread. :)

-Bee-

has Bee.ography at
http://beeography.wordpress.com

unit.

I agree with Michael. And I think the line is clearly drawn. The FPC (and more importantly the language syntax itself) design goal, as I understand it, is to be, as much as possible, platform and architecture independent and doesn't need to be "polluted" by adding esoteric functions/(worst yet)operators becuase they are neat on one particular type of machine and we just program around them everywhere else.
Rather, if your application really needs that function, you have a number of suggestions on how to implement that within your own application, so do that, but I don't think the compiler should be expected to do it for you.

Dave

This conclusion is drawn on wrong assumptions: the rot instructions aren't esoteric but supported by at least the four most important CPU platforms (i386, x86_64, powerpc and arm) and needed for efficient cryptographic and graphics algorithms.

Rather, if your application really needs that function, you have a number of suggestions on how to implement that within your own application, so do that, but I don't think the compiler should be expected to do it for you.

I didn't saw usable suggestions for non i386 platforms :)

I agree with Michael. And I think the line is clearly drawn. The FPC (and more importantly the language syntax itself) design goal, as I understand it, is to be, as much as possible, platform and architecture independent and

I believe the bit rotation support can be made platform and architecture indepedent. This operation obviously needed regardless the platform or the architecture. It is very important for calculation algorithms and the implementation (e.g. simulation, graphics, encoding, math, etc) and that's why it IS available almost on all modern architectures. Is there any platform/architecture that does not require or provide this operation?

doesn't need to be "polluted" by adding esoteric functions/(worst yet)operators becuase they are neat on one particular type of machine and we just program around them everywhere else.

As function it'll pollute pascal syntax, but not if it is as operator. And clearly the bit rotation operation is not esoteric. It's just like the reason why shl/shr operator exist. Make rol/ror as operator even make FPC syntax more clear and clean. If shl/shr can exist as operator, then why ror/rol can't? Of course, I also can be on contra side for the shl/shr operator if I want... with the exact reasons as yours. :)

Rather, if your application really needs that function, you have a number of suggestions on how to implement that within your own application, so do that, but I don't think the compiler should be expected to do it for you.

The problem is... almost everyone need it. Even the compiler itself! Like what Florian has told us in this thread. :)

-Bee-

has Bee.ography at
http://beeography.wordpress.com

It is possible to implement a peephole optimization to change the shift/or into the native variant of rol/ror if it exists. And I don't think any architecture apart from x86 support rol/ror for anything but the native word size (at least ppc doesn't).

Functions never pollute a syntax, since they are inherently part of the syntax.

As explained earlier, for rol/ror the size of the operands matters. For shl/shr it doesn't, and the compiler can covert all operands to the native word size before performing the operation (just like it does for all other mathematical and logical operations).

The problem is... almost everyone need it.

That is not true, unless almost everyone implements cryptographic algorithms.

Even the compiler itself! Like what Florian has told us in this thread. :)

No, the compiler doesn't need it. The post from Florian was about a unit in packages.

Jonas

The code currently generated is rather lengthy.

And I don't think any architecture apart from x86 support rol/ror for anything but the native word size (at least ppc doesn't).

But it can be done on ppc with two rlw* instructions which is also ok, no? But dword ror/rol is anyways enough for md5, sha et al iirc.

Actually it does, but it's neither speed critical nor used on all platforms: search for rotl in
http://svn.freepascal.org/svn/fpc/trunk/compiler/arm/cpubase.pas

Florian Klaempfl wrote

> It is possible to implement a peephole optimization to change the > shift/or into the native variant of rol/ror if it exists. The code currently generated is rather lengthy.

Of course, but it's going to be a pretty consistent pattern which can be recognised by the peephole optimizer (if someone implements it).

I think it needs three: to to rotate left/right, one to insert the overflow at the end/start, and one to mask the overfow at the end/ start. But peephole optimizations to turn a number of shift and or operations into a sequence of rlw* is needed for ppc anyway (e.g. for record regvars).

Jonas

No, two is actually indeed enough if you use two different registers.

Jonas