Be careful with shr

[hakelm]

The little program below gives the interesting output

0
18446744073709551615

i.e. shr works as expected for a byte but not for a larger integer. This happens when the number of shifts is the same as the number of bits in the argument. The behaviour is avoided when the number of shifts is unknown at compile time. An explanation is to be found in the disassembly at the bottom.

program Project1;
var b:byte; l:uint64;
begin
  b:=high(b);
  b:=b shr (sizeof(b) * 8);
  writeln(b);
  l:=high(l);
  l:=l shr ((sizeof(l) * 8));
  writeln(l);
end.         

project1.lpr:5                            b:=b shr (sizeof(b) * 8);
00000000004001D9 c02d90db220008           shrb   $0x8,0x22db90(%rip)        # 0x62dd70 <U_$P$PROJECT1_$$_B>

project1.lpr:8                            l:=l shr ((sizeof(l) * 8));
0000000000400219 488b0570db2200           mov    0x22db70(%rip),%rax        # 0x62dd90 <U_$P$PROJECT1_$$_L>
0000000000400220 48890569db2200           mov    %rax,0x22db69(%rip)        # 0x62dd90 <U_$P$PROJECT1_$$_L>

[WooBean]

Hi hakelm, good shot!

The problem in brief is that we put $FFFFFFFFFFFFFFFF into QWORD or uint64 variable and after shifting right all its bits  (all means 64) we get not zero but unchanged $FFFFFFFFFFFFFFFF.

I guess that it is FPC serious error and comes from the times when the largest integer type was int64 (in 32-bit environment) so safe shifting was only for 63 bits.

To get a proper result of shr something by 64 we need to do it in two steps - for example:
L:=L shr 63;
L:=L shr 1;


WooBean 

[Thaddy]

Nonsense: expect a signed integer type to have a sign bit.

Code: Pascal  [Select][+][-]

1. {$ifdef fpc}{$mode delphi}{$H+}{$I-}{$R+}{$Q+}{$endif}
2. uses math;
3. var
4.  i: longint = high(longint);
5.  d: dword = high(dword);
6. begin
7.  writeln(i shr SizeOf(i));
8.  writeln(d shr SizeOf(d));
9.  writeln(binstr(i shr SizeOf(i),32));
10.  writeln(binstr(d shr SizeOf(d),32));// note extra bit...
11. end.

IOW you must take into account the sign bit when shifting signed integers. Or use SAR. (shift arithmetic right). Or cast to an unsigned type....
Unless you mean that intentionally overflowing should always result in zero... Then it is a bug indeed, but I have to test that first..

[marcov]

It is an intel quirk.  Intel doesn't support this (also not for 32-bit in 32-bit mode), and it requires extra instructions for something that is practically nonsense.

[Thaddy]

I tested this code on arm and intel, Marco...

[WooBean]

Hi Thaddy,

I love such a selfconfident people as you but ...

1) now we are talking about unsigned (uint64 or QWORD) type;
2) try to follow a simply exercise:
  - declare uint64 variable;
  - set it $FFFFFFFFFFFFFFFF;
  - shift this value right (shr) directly by 64;
  - print the result of operation; //I expect $FFFFFFFFFFFFFFFF
  - shift this value right (shr) directly by 63; //I expect 1 (one)
  - shift this value right (shr) directly by 1; //I expect 0 (zero)
  - print the result of operation; //I expect 0 (zero)

Something grumpy?

[Thaddy]

Oh well,

Code: Pascal  [Select][+][-]

1. {$ifdef fpc}{$mode delphi}{$H+}{$I-}{$R+}{$Q+}{$endif}
2. var
3.  i: uint64 = high(uint64);
4.  d: qword = high(qword);
5. begin
6.  writeln(i shr SizeOf(i));
7.  writeln(d shr SizeOf(d));
8.  writeln(binstr(i shr SizeOf(i)-1,64));
9.  writeln(binstr(d shr 1,64));// note extra bit...
10. end.

Is that what you mean?

Code: Bash  [Select][+][-]

1. 72057594037927935
2. 72057594037927935
3. 0000000011111111111111111111111111111111111111111111111111111110
4. 0111111111111111111111111111111111111111111111111111111111111111
5.  

Because that is the correct bit pattern.

[WooBean]

@Thaddy,

I meant this

Code: Pascal  [Select][+][-]

1. {$ifdef fpc}{$mode delphi}{$H+}{$I-}{$R+}{$Q+}{$endif}
2. uses sysutils;
3. var
4.  i: uint64 = high(uint64);
5.  d: qword = high(qword);
6. begin
7.  writeln(uint64(i).ToHexString);
8.  writeln(qword(d).ToHexString);
9.  
10.  writeln(uint64(i shr (SizeOf(i)*8){=64}).ToHexString); //sizeOf returns bytes but we need bits
11.  // we get here non zero value - opposite to expected result
12.  writeln(qword(d shr (SizeOf(d)*8){=64}).ToHexString); //the same as above
13.  // we get here non zero value - opposite to expected result
14.  writeln(binstr(i shr (8*SizeOf(i)-1),64));  //shift by 63 bits
15.  writeln(binstr((i shr (8*SizeOf(i)-1)) shr 1,64)); //shif by las 1 bit
16.  writeln(binstr(d shr (8*SizeOf(i)-1),64));  //shift by 63 bits
17.  writeln(binstr((d shr (8*SizeOf(i)-1)) shr 1,64)); //shif by last 1 bit
18.  readln;
19. end.    
20.  

I had to make some changes as simple value 64 was replaced by (SizeOf(i))*8{=64}) and lacked ().
I think that we all owe a bucket of beer to hakelm 

[hakelm]

This doesn't seem to be a problem for FPC only. The direct use of gcc gives the same result:

#include <stdio.h>
#include <stdlib.h>
unsigned long long i,j;
int main()
{
    i=0xffffffffffffffff;
    printf("%llu\n",i);
    j=i>>63;
    printf("%llu\n",j);
    j=i>>64;
    printf("%llu\n",j);
    return 0;
}

produces:

18446744073709551615
1
18446744073709551615

H

[tetrastes]

Yes, and gcc gives explicit warning:

Code: Bash  [Select][+][-]

1. D:\work\misc\tests>gcc RSHtest.c -oRSHtest64
2. RSHtest.c: In function 'main':
3. RSHtest.c:8:6: warning: right shift count >= width of type [-Wshift-count-overflow]
4.   u64 >>= 64;
5.       ^~~
6. RSHtest.c:10:6: warning: right shift count >= width of type [-Wshift-count-overflow]
7.   u32 >>= 32;
8.       ^~~
9.  
10. D:\work\misc\tests>RSHtest64.exe
11. 18446744073709551615
12. 4294967295
13.  

32-bit gcc output is the same.

More interesting the output of cl (I have old VC++ 10 32-bit installed on my computer), it gives 0 for Uint64.

Code: Bash  [Select][+][-]

1. D:\work\misc\tests>cl RSHtest.c
2. Оптимизирующий 32-разрядный компилятор Microsoft (R) C/C++ версии 16.00.40219.01 для 80x86
3. (C) Корпорация Майкрософт (Microsoft Corporation). Все права защищены.
4.  
5. RSHtest.c
6. RSHtest.c(8) : warning C4293: >>: отрицательное или слишком большое смещение; поведение не определено
7. (Translation: negative or too large shift; the behavior is undefined)
8. RSHtest.c(10) : warning C4293: >>: отрицательное или слишком большое смещение; поведение не определено
9. Microsoft (R) Incremental Linker Version 10.00.40219.01
10. Copyright (C) Microsoft Corporation.  All rights reserved.
11.  
12. /out:RSHtest.exe
13. RSHtest.obj
14.  
15. D:\work\misc\tests>RSHtest.exe
16. 0
17. 4294967295
18.  

So I think that fpc is OK (but warning will be good)   

[engkin]

So I think that fpc is OK (but warning will be good)   

Why do you think FPC is OK?

[tetrastes]

And you do think fpc is not OK?
Though I wrote aboute this specific case (to "be careful with shr").

[engkin]

And you do think fpc is not OK?
Though I wrote aboute this specific case (to "be careful with shr").

Here is why FPC is not OK in this specific case:

Code: Pascal  [Select][+][-]

1. var
2.   l: uint64;
3.   n: integer;
4. begin
5.   l := high(l);
6.   l := l shr ((sizeof(l) * 8));
7.   writeln(l);
8.   repeat
9.     Write('Enter a number (try 64): ');
10.     ReadLn(n);
11.     if n < 0 then
12.       exit;
13.     l := high(l);
14.     l := l shr n;
15.     writeln(l);
16.   until False;
17. end.

Now can you tell me why you think FPC is ok in this specific case?

[tetrastes]

Do you read the warnings of C compilers?

They conform to C standard:
The result is undefined if the right operand of a shift expression is negative or if the right operand is greater than or equal to the number of bits in the (promoted) left operand.

So why do you think that in Pascal this result must be defined?

[engkin]

Do you read the warnings of C compilers?

Why should I read the warnings of the C compilers?

They conform to C standard:

Who told you that?

So why do you think that in Pascal this result must be defined?

Because the problem is not in the result of the assembly shift instruction.

If you test the code I posted in my previous post. Pass 64 and you get 0 (as expected).