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
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
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
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
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
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
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 Nordlw 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
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
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
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
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
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