Does MSIL have ROL and ROR instructions?

Question

I wrote an Int128 type and it works great. I thought I could improve on its performance with a simple idea: Improve the shift operations which are a bit clumsy.

Because they are heavily used in multiplication and division, an improvement would have a ripple effect. So I began creating a dynamic method (to shift low and rotate high), only to discover that there are no OpCodes.Rol or OpCodes.Ror instructions.

Is this possible in IL?

Germinal

Even if it turns out that there is no CIL op-code for bit rotations, the JIT compiler might still be smart enough to map several CIL op-codes to ROL and ROR instructions on the underlying machine's instruction set. (I don't actually think that the JIT compiler is that smart, but at least it's possible). I mean to say: I wouldn't worry too much. Compared to real assembly language, CIL code seems very inefficient anyway, but the JIT compiler will most likely alleviate this somewhat. – Lewislewisite

Answer 1

No.

You need to implement it with bit shifts

UInt64 highBits = 0;
UInt64 lowBits = 1;
Int32 n = 63;
var altShift = (n - 63);

var lowShiftedOff = (n - 63) > 0 ? 0 : (lowBits << n);
var highShiftedOff = (n - 63) > 0 ? 0 : (highBits << n);

var highResult = (UInt64)(highShiftedOff | (altShift > 0 ? (lowBits << altShift - 1) : 0));
var lowResult= (UInt64)(lowShiftedOff | (altShift > 0 ? (highBits << altShift - 1) : 0));

Imena

Thank you. You confirmed what I feared. I dug around in .NET 4.0's BigInteger to see how they did it and now I don't feel quite so bad about mine. – Germinal

Not only is it bad, but I had neglected that SHL and SHR only look at the last 5 (for U/Int32) or 6 (for U/Int64) bits of the shift operand, effectively creating a modulus for the full shift value. This is a big pain when trying to shift bits through, and I can't understand why it was implemented like this. – Imena

The shift operands are only defined for shifts less than the size of the type involved, since shifting more than n bits for an n-bit type doesn't make much sense. The standard (ECMA 335: §3.59) says: The return value is unspecified if 'shiftAmount' is greater than or equal to the width of 'value'. – Interface

@Porges - It makes sense when you are trying to shift through like this. – Imena

Answer 2

To partially answer this question 7 years later, in case someone should need it.

You can use ROR/ROL in .Net.

MSIL doesn't directly contain ROR or ROL operations, but there are patterns that will make the JIT compiler generate ROR and ROL. RuyJIT (.Net and .Net core) supports this.

The details of improving .Net Core to use this pattern was discussed here and a month later .Net Core code was updated to use it.

Looking at the implementation of SHA512 we find examples of ROR:

    public static UInt64 RotateRight(UInt64 x, int n) {
        return (((x) >> (n)) | ((x) << (64-(n))));
    }

And extending by same pattern to ROL:

    public static UInt64 RotateLeft(UInt64 x, int n) {
        return (((x) << (n)) | ((x) >> (64-(n))));
    }

To do this on 128-bit integer you can process as two 64-bit, then AND to extract "carry", AND to clear destination and OR to apply. This has to be mirrored in both directions (low->high and high->low). I'm not goin to bother with an example since this question is a bit old.

Infrastructure

Any idea how you would convert this to a generic ROL/ROR for common types (byte, short, int, long, and their unsigned counter parts) ? (e.g. public T RotateLeft<T>(T val, int n) { var bits = Marshal.SizeOf(val) * 8; n %= bits; return ((val << (n) | (val >> (bits - n))); /* ?? */ }) – Embayment

I would think you are better off overloading them, there are not that many. Generic type constraint for value type is limited to "struct". And use of Marshal.SizeOf() (Windows API call iirc) instead of sizeof() (compile time constant) would negate any performance benefits from a potential ROL/ROR. So even if you got the generic to compile the right code the benefit would not be there. – Infrastructure

Thank you for the reply. Your insight was valuable. – Embayment

I ended up writing a quick blog post on the difference between sizeof() and Marshal.SizeOf(): blog.tedd.no/2018/03/18/sizeof-vs-marshal-sizeof :) – Infrastructure

I've bookmarked it, if I ever run into any questions where I find mentioning this applicable I'll point them to that page. :) – Embayment