### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

### Author Topic: Be careful with shr  (Read 13731 times)

#### hakelm

• Full Member
• Posts: 153
##### Be careful with shr
« on: March 05, 2018, 09:54:43 am »
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

• Sr. Member
• Posts: 267
##### Re: Be careful with shr
« Reply #1 on: March 05, 2018, 10:38:17 am »
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
« Last Edit: March 05, 2018, 10:53:06 am by WooBean »
Platforms: Win7/64, Linux Mint Ulyssa/64

• Hero Member
• Posts: 15496
• Censorship about opinions does not belong here.
##### Re: Be careful with shr
« Reply #2 on: March 05, 2018, 10:56:12 am »
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..

« Last Edit: March 05, 2018, 11:07:55 am by Thaddy »
My great hero has found the key to the highway. Rest in peace John Mayall.
Playing: "Broken Wings" in your honour. As well as taking out some mouth organs.

#### marcov

• Hero Member
• Posts: 11724
• FPC developer.
##### Re: Be careful with shr
« Reply #3 on: March 05, 2018, 11:13:46 am »
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.

• Hero Member
• Posts: 15496
• Censorship about opinions does not belong here.
##### Re: Be careful with shr
« Reply #4 on: March 05, 2018, 11:16:51 am »
I tested this code on arm and intel, Marco...
My great hero has found the key to the highway. Rest in peace John Mayall.
Playing: "Broken Wings" in your honour. As well as taking out some mouth organs.

#### WooBean

• Sr. Member
• Posts: 267
##### Re: Be careful with shr
« Reply #5 on: March 05, 2018, 11:17:10 am »

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?
« Last Edit: March 05, 2018, 11:19:56 am by WooBean »
Platforms: Win7/64, Linux Mint Ulyssa/64

• Hero Member
• Posts: 15496
• Censorship about opinions does not belong here.
##### Re: Be careful with shr
« Reply #6 on: March 05, 2018, 12:02:45 pm »
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.
« Last Edit: March 05, 2018, 12:09:17 pm by Thaddy »
My great hero has found the key to the highway. Rest in peace John Mayall.
Playing: "Broken Wings" in your honour. As well as taking out some mouth organs.

#### WooBean

• Sr. Member
• Posts: 267
##### Re: Be careful with shr
« Reply #7 on: March 05, 2018, 12:31:09 pm »

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
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
« Last Edit: March 05, 2018, 01:55:09 pm by WooBean »
Platforms: Win7/64, Linux Mint Ulyssa/64

#### hakelm

• Full Member
• Posts: 153
##### Re: Be careful with shr
« Reply #8 on: March 05, 2018, 01:19:43 pm »
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

• Hero Member
• Posts: 517
##### Re: Be careful with shr
« Reply #9 on: March 05, 2018, 01:53:28 pm »
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
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)
« Last Edit: March 05, 2018, 02:34:32 pm by tetrastes »

#### engkin

• Hero Member
• Posts: 3112
##### Re: Be careful with shr
« Reply #10 on: March 05, 2018, 02:40:50 pm »
So I think that fpc is OK (but warning will be good)
Why do you think FPC is OK?

#### tetrastes

• Hero Member
• Posts: 517
##### Re: Be careful with shr
« Reply #11 on: March 05, 2018, 02:48:51 pm »
And you do think fpc is not OK?
Though I wrote aboute this specific case (to "be careful with shr").

#### engkin

• Hero Member
• Posts: 3112
##### Re: Be careful with shr
« Reply #12 on: March 05, 2018, 02:53:51 pm »
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): ');
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

• Hero Member
• Posts: 517
##### Re: Be careful with shr
« Reply #13 on: March 05, 2018, 03:08:19 pm »
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?
« Last Edit: March 05, 2018, 03:11:03 pm by tetrastes »

#### engkin

• Hero Member
• Posts: 3112
##### Re: Be careful with shr
« Reply #14 on: March 05, 2018, 03:15:30 pm »
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).