www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Bitwise rotate of integral

reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
What's the preferred way of doing bitwise rotate of an integral 
value in D?

Are there intrinsics for bitwise rotation available in LDC?
Jan 07 2019
next sibling parent reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Monday, 7 January 2019 at 14:39:07 UTC, Per Nordlöw wrote:

 What's the preferred way of doing bitwise rotate of an integral 
 value in D?

 Are there intrinsics for bitwise rotation available in LDC?


I just found this

     ulong rotateLeft(ulong x, ubyte bits)
     {
         return (x << bits) | (x >> (64 - bits));
     }

Questions:
- Is this a good implementation for the ulong case?
- Should we use >> or >>> ?
- What's the preferred type for `bits`, ubyte, or uint or making 
it a template parameter?
Jan 07 2019
parent reply Alex <sascha.orlov gmail.com> writes:
On Monday, 7 January 2019 at 14:43:29 UTC, Per Nordlöw wrote:

 On Monday, 7 January 2019 at 14:39:07 UTC, Per Nordlöw wrote:

 What's the preferred way of doing bitwise rotate of an 
 integral value in D?

 Are there intrinsics for bitwise rotation available in LDC?


 I just found this

     ulong rotateLeft(ulong x, ubyte bits)
     {
         return (x << bits) | (x >> (64 - bits));
     }

 Questions:
 - Is this a good implementation for the ulong case?
 - Should we use >> or >>> ?
 - What's the preferred type for `bits`, ubyte, or uint or 
 making it a template parameter?


There are
https://dlang.org/phobos/core_bitop.html#.rol
and
https://dlang.org/phobos/core_bitop.html#.ror

But it seems the implementation is like yours.
Jan 07 2019
parent reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Monday, 7 January 2019 at 14:53:26 UTC, Alex wrote:

 There are
 https://dlang.org/phobos/core_bitop.html#.rol
 and
 https://dlang.org/phobos/core_bitop.html#.ror

 But it seems the implementation is like yours.


Ahh, missed that. Thanks.
Jan 07 2019
parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 1/7/19 10:10 AM, Per Nordlöw wrote:

 On Monday, 7 January 2019 at 14:53:26 UTC, Alex wrote:

 There are
 https://dlang.org/phobos/core_bitop.html#.rol
 and
 https://dlang.org/phobos/core_bitop.html#.ror

 But it seems the implementation is like yours.


 
 Ahh, missed that. Thanks.


Use the core.bitop ones. Chances are they are intrinsics on certain 
platforms.

-Steve
Jan 07 2019
prev sibling next sibling parent reply Guillaume Piolat <first.last gmail.com> writes:
On Monday, 7 January 2019 at 14:39:07 UTC, Per Nordlöw wrote:

 What's the preferred way of doing bitwise rotate of an integral 
 value in D?

 Are there intrinsics for bitwise rotation available in LDC?


Turns out you don't need any:

https://d.godbolt.org/z/C_Sk_-

Generates ROL instruction.
Jan 07 2019
parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Mon, Jan 07, 2019 at 11:13:37PM +0000, Guillaume Piolat via
Digitalmars-d-learn wrote:

 On Monday, 7 January 2019 at 14:39:07 UTC, Per Nordlöw wrote:

 What's the preferred way of doing bitwise rotate of an integral
 value in D?
 
 Are there intrinsics for bitwise rotation available in LDC?


 
 Turns out you don't need any:
 
 https://d.godbolt.org/z/C_Sk_-
 
 Generates ROL instruction.


There's a certain pattern that dmd looks for, that it transforms into a
ROL instruction. Similarly for ROR.  Deviate too far from this pattern,
though, and it might not recognize it as it should.  To be sure, always
check the disassembly.


T

-- 
I don't trust computers, I've spent too long programming to think that they can
get anything right. -- James Miller
Jan 07 2019
parent reply Patrick Schluter <Patrick.Schluter bbox.fr> writes:
On Monday, 7 January 2019 at 23:20:57 UTC, H. S. Teoh wrote:

 On Mon, Jan 07, 2019 at 11:13:37PM +0000, Guillaume Piolat via 
 Digitalmars-d-learn wrote:

 On Monday, 7 January 2019 at 14:39:07 UTC, Per Nordlöw wrote:

 What's the preferred way of doing bitwise rotate of an 
 integral value in D?
 
 Are there intrinsics for bitwise rotation available in LDC?


 
 Turns out you don't need any:
 
 https://d.godbolt.org/z/C_Sk_-
 
 Generates ROL instruction.


 There's a certain pattern that dmd looks for, that it 
 transforms into a ROL instruction. Similarly for ROR.  Deviate 
 too far from this pattern, though, and it might not recognize 
 it as it should.  To be sure, always check the disassembly.


Are you sure it's dmd looking for the pattern. Playing with the 
godbolt link shows that dmd doesn't generate the rol code (gdc 
4.8.2 neither).
Jan 08 2019
next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Jan 08, 2019 at 09:15:09AM +0000, Patrick Schluter via
Digitalmars-d-learn wrote:

 On Monday, 7 January 2019 at 23:20:57 UTC, H. S. Teoh wrote:


[...]

 There's a certain pattern that dmd looks for, that it transforms
 into a ROL instruction. Similarly for ROR.  Deviate too far from
 this pattern, though, and it might not recognize it as it should.
 To be sure, always check the disassembly.
 


 Are you sure it's dmd looking for the pattern. Playing with the
 godbolt link shows that dmd doesn't generate the rol code (gdc 4.8.2
 neither).


I vaguely remember a bug about this. There is definitely explicit
checking for this in dmd; I don't remember if it was a bug in the
pattern matching code itself, or some other problem, that made it fail.
You may need to specify -O for the code to actually be active. Walter
could point you to the actual function that does this optimization.


T

-- 
Never wrestle a pig. You both get covered in mud, and the pig likes it.
Jan 08 2019
parent Patrick Schluter <Patrick.Schluter bbox.fr> writes:
On Tuesday, 8 January 2019 at 12:35:16 UTC, H. S. Teoh wrote:

 On Tue, Jan 08, 2019 at 09:15:09AM +0000, Patrick Schluter via 
 Digitalmars-d-learn wrote:

 On Monday, 7 January 2019 at 23:20:57 UTC, H. S. Teoh wrote:


 [...]

 [...]


 Are you sure it's dmd looking for the pattern. Playing with 
 the godbolt link shows that dmd doesn't generate the rol code 
 (gdc 4.8.2 neither).


 I vaguely remember a bug about this. There is definitely 
 explicit checking for this in dmd; I don't remember if it was a 
 bug in the pattern matching code itself, or some other problem, 
 that made it fail. You may need to specify -O for the code to 
 actually be active. Walter could point you to the actual 
 function that does this optimization.


I did use the -O flag. The code generated did not use rol.
Jan 08 2019
prev sibling parent Reimer Behrends <behrends gmail.com> writes:
On Tuesday, 8 January 2019 at 09:15:09 UTC, Patrick Schluter 
wrote:

 Are you sure it's dmd looking for the pattern. Playing with the 
 godbolt link shows that dmd doesn't generate the rol code (gdc 
 4.8.2 neither).


Looking at the dmd compiler source code, it requires the value to 
be rotated to be of a type no larger than an int and the amount 
that the value is rotated by to be a constant.

Example: https://d.godbolt.org/z/m3HiPq

Interestingly, if you rotate by exactly 16 bits, it will generate 
less optimal code.
Jan 08 2019
prev sibling parent Johan Engelen <j j.nl> writes:
On Monday, 7 January 2019 at 14:39:07 UTC, Per Nordlöw wrote:

 What's the preferred way of doing bitwise rotate of an integral 
 value in D?

 Are there intrinsics for bitwise rotation available in LDC?


LDC does not expose this intrinsic currently, but you can use 
LLVM's fshl:
https://llvm.org/docs/LangRef.html#llvm-fshl-intrinsic
It's a fairly new intrinsic, so won't work with older LLVM 
versions.

https://d.godbolt.org/z/SBnJFJ

As noted by others, the optimizer is strong enough to recognize 
what you are doing (without intrinsic) and use ror/rol if it 
deems it advantageous to do so.

-Johan
Jan 08 2019