Recent

Author Topic: arithmetic shift right - sar  (Read 2546 times)

beepee

  • Newbie
  • Posts: 6
arithmetic shift right - sar
« on: January 10, 2021, 10:45:59 am »
In search for arithmetic shift right, there should be a sar operator (What's new in FPC 2.6.0, at 'Compiler'):

https://forum.lazarus.freepascal.org/index.php/topic,15656.msg84395.html#msg84395

However that is not available:

  for i:=-20 to 20 do
    writeln('i= ',i,' i shr 1= ',i shr 1,' i sar 1= ',i sar 1);


ashr.pas(24,57) Fatal: Syntax error, ")" expected but "identifier SAR" found

Is there a switch to be set before the SAR is recognized?

avk

  • Hero Member
  • *****
  • Posts: 752
Re: arithmetic shift right - sar
« Reply #1 on: January 10, 2021, 11:16:37 am »
It looks like a function, look for SarShortint, SarSmallint, SarLongint, SarInt64.

PascalDragon

  • Hero Member
  • *****
  • Posts: 5446
  • Compiler Developer
Re: arithmetic shift right - sar
« Reply #2 on: January 10, 2021, 11:16:53 am »
In search for arithmetic shift right, there should be a sar operator (What's new in FPC 2.6.0, at 'Compiler'):

You found the entry in the New Features 2.6.0 page, but you didn't read it completely:

Quote
Unlike the SHL and SHR operators, SAR is not implemented as an operator but as an intrinsic. It is also defined using different names for different integer sizes to prevent unexpected results when applying it to expressions.

Thus they're used like functions, not operators.

The linked example on the wiki page shows how to call them. They are named SarShortInt (8-bit), SarSmallInt (16-bit), SarLongInt (32-bit) and SarInt64 (64-bit).

jamie

  • Hero Member
  • *****
  • Posts: 6090
Re: arithmetic shift right - sar
« Reply #3 on: January 10, 2021, 12:38:02 pm »
Nice to know that, I wish I knew that earlier. In any case just sent onto a search looking for a ROR and LoR functions which I would love very much to be intrinsic.

 Currently I have functions but they don't compile down as efficient as they could be and I can do inline assembler but not good practice for other targets.

 This is what I have now..

 RoRWord(Const TheSourceWord; Var CarryBit:Boolean; Amount:integer=1):Word;

It would be nice to have that so could perform a wide range of carry shifts with a more intrinsic way to gain max efficiency from the compiler high level end;

 I am sure you can see how this works, the Carraybit uses the value coming in and internally gets set when the operation is completed for the next carry flag in line. so we just set it to nothing for example at the start of a loop


The only true wisdom is knowing you know nothing

PascalDragon

  • Hero Member
  • *****
  • Posts: 5446
  • Compiler Developer
Re: arithmetic shift right - sar
« Reply #4 on: January 10, 2021, 01:49:57 pm »
Nice to know that, I wish I knew that earlier. In any case just sent onto a search looking for a ROR and LoR functions which I would love very much to be intrinsic.

The compiler has Ror*/Rol* intrinsics since the same time as the Sar* ones (namely 2.6.0). Only without support for the carry bit. You could open a feature request for RorCarry*/RolCarry* variants if you want of course. ;)

jamie

  • Hero Member
  • *****
  • Posts: 6090
Re: arithmetic shift right - sar
« Reply #5 on: January 10, 2021, 02:53:39 pm »
Ok, sounds good. I will put in a feature request because this only makes sense to me..
Thank you..


Btw, I wasn't aware of those function either thanks for pointing them out..

Maybe I can combined these to improve what I have...


P.S.

 Reported:
  I excluded the option of count because I see its actually a bad idea although my version of what I have never goes beyond 1 bit shifts so I think I will for the time being modify what I have and save on compiler bloat.


« Last Edit: January 10, 2021, 03:12:05 pm by jamie »
The only true wisdom is knowing you know nothing

beepee

  • Newbie
  • Posts: 6
Re: arithmetic shift right - sar
« Reply #6 on: January 10, 2021, 03:45:01 pm »
..

Thus they're used like functions, not operators.

The linked example on the wiki page shows how to call them. They are named SarShortInt (8-bit), SarSmallInt (16-bit), SarLongInt (32-bit) and SarInt64 (64-bit).

Thanks! I admit I did not read it to the end. I'm glad there are others that now know it is there and how to use it. ;)

So a test is e.g:
program arithmeticshiftright;
{$apptype console}
var
  i: integer;
begin
  for i:=-4 to 4 do
    writeln('i= ',i,'; i shr 1= ',i shr 1,'; i sar 1= ',sarlongint(i,1));
end.


With results:
i= -4; i shr 1= 2147483646; i sar 1= -2
i= -3; i shr 1= 2147483646; i sar 1= -2
i= -2; i shr 1= 2147483647; i sar 1= -1
i= -1; i shr 1= 2147483647; i sar 1= -1
i= 0; i shr 1= 0; i sar 1= 0
i= 1; i shr 1= 0; i sar 1= 0
i= 2; i shr 1= 1; i sar 1= 1
i= 3; i shr 1= 1; i sar 1= 1
i= 4; i shr 1= 2; i sar 1= 2

Note to all: the "sarlongint(-3,1)" gives a result truncated down (-2) while a "-3 div 2" truncates towards zero (-1)
All in accordance with: a = ( a div b) * b +  (a mod b) where for example -3 mod 2 = -1
« Last Edit: January 10, 2021, 04:05:29 pm by beepee »

jamie

  • Hero Member
  • *****
  • Posts: 6090
Re: arithmetic shift right - sar
« Reply #7 on: January 10, 2021, 04:14:02 pm »
I use something like this in a couple of projects that are years old..

This is a fpc translation of it one of the functions ….

Code: Pascal  [Select][+][-]
  1.  
  2. // Code deleted due to lack of interest..
  3.  

 I don't want to clutter up the network with junk..

 You all have a good day now..


« Last Edit: January 10, 2021, 08:08:28 pm by jamie »
The only true wisdom is knowing you know nothing

PascalDragon

  • Hero Member
  • *****
  • Posts: 5446
  • Compiler Developer
Re: arithmetic shift right - sar
« Reply #8 on: January 12, 2021, 09:08:26 am »
I use something like this in a couple of projects that are years old..

Would have been nice if you hadn't deleted that... So I have to ask: what kind of algorithms require the use of the carry flag? That question came up on the mailing list once I moved the discussion there.

jamie

  • Hero Member
  • *****
  • Posts: 6090
Re: arithmetic shift right - sar
« Reply #9 on: January 12, 2021, 11:09:25 pm »
The Carry flag is just a facsimile to express the idea of the MSb and LSb in a bit shuffle where bleeding bits are stored as a carry over .

 what ever each CPU uses to flag the indication that a (1) bit was lost either on the LSb or MSb side so that the next call to the function can use the state of the last one thus being able to include it to the next

 for example
 
 WORD 1 is RCL (Roll with Carray) and it had a Value of $8000;

  WORD 2 is RCL and it has a valye of 0 but after the ROL it now has $01;

 Just think when you need to scroll bits in a ground of words, bytes etc...

 etc

 
 
The only true wisdom is knowing you know nothing

PascalDragon

  • Hero Member
  • *****
  • Posts: 5446
  • Compiler Developer
Re: arithmetic shift right - sar
« Reply #10 on: January 13, 2021, 08:51:35 am »
The Carry flag is just a facsimile to express the idea of the MSb and LSb in a bit shuffle where bleeding bits are stored as a carry over .

I'm aware what the rotation-with-carry does. The question is for a real world use of it.

what ever each CPU uses to flag the indication that a (1) bit was lost either on the LSb or MSb side so that the next call to the function can use the state of the last one thus being able to include it to the next

Not all CPUs have that or not all have instructions similar to RCL/RCR, thus it would need to be done by hand on those targets and thus it would be useful to know real world algorithms that need this rotation-with-carry and can't easily use something else.

FPK

  • Full Member
  • ***
  • Posts: 118
Re: arithmetic shift right - sar
« Reply #11 on: January 13, 2021, 06:29:03 pm »
Just think when you need to scroll bits in a ground of words, bytes etc...

This is exactly the use case when no rcl should be used. This is why I asked what the use case of it is. rcl has little throughput and high latency in comparison with other instructions. Furthermore, bit scrolling based on rcl causes unnecessary data dependencies. See also my test at https://bugs.freepascal.org/view.php?id=38341#c128290

jamie

  • Hero Member
  • *****
  • Posts: 6090
Re: arithmetic shift right - sar
« Reply #12 on: January 13, 2021, 11:19:31 pm »
This is going off the deep end here.

It has nothing to do with what CPU has a carry flag etc...

 I guess this subject must be over the general population's heads or I am just taking it for granted that others should know better.


 The idea is to shift in a Carry over from the last operation and thus produce a Carry (expended bit) flag in case one  got shot out the back when shifting the bits left or right...

  When shifting a group of objects that in bit format with each other this is need, you need to record the bit that got lost with one shift so that it can be inserted into the next object in line that belongs to the group.

 Code like this is used in shifting 1 bit images , bit stuffing, Serial link compression etc...

The code I posted, which I deleted is used currently now in an application (industrial application) where that code actually compiles down very nicely (efficiently ) in Delphi but will not in fpc. fpc makes a ping out of using common pascal code for doing this where Delphi seems to understand what it is you are doing and generates ASM code that for most part is hard to beat.

 Using Intrinsic functions that obviously I see now only little here understand would help the bloat lag...

Anyways... I deleted the code for two reasons, no on seems to understand it or cares and it was part of code that I most likely should not have posted in the first place.
The only true wisdom is knowing you know nothing

PascalDragon

  • Hero Member
  • *****
  • Posts: 5446
  • Compiler Developer
Re: arithmetic shift right - sar
« Reply #13 on: January 14, 2021, 09:50:40 am »
Code like this is used in shifting 1 bit images , bit stuffing, Serial link compression etc...

You did not provide explicit examples, you just state "code like this is used". Provide examples, please, even if it's a link to some C code or whatever. But it should be real world examples, not some example showing the use of rotate-with-carry in general.

The code I posted, which I deleted is used currently now in an application (industrial application) where that code actually compiles down very nicely (efficiently ) in Delphi but will not in fpc. fpc makes a ping out of using common pascal code for doing this where Delphi seems to understand what it is you are doing and generates ASM code that for most part is hard to beat.

 Using Intrinsic functions that obviously I see now only little here understand would help the bloat lag...

You don't seem to understand that without examples showing your problems (also the ones where according to you less efficient assembly code is generated) then nothing will be done. We don't do "crystal ball" development. Provide examples that show your problems and we'll try to fix/improve them. Especially FPK likes to improve the optimizations that the compiler does.

 

TinyPortal © 2005-2018