bitshift outside allowed range

user_1560850 0
Viewed 153

We have a code in production that in some situation may left-shift a 32-bit unsigned integer by more than 31 bits. I know this is considered undefined behavior. Unfortunately we can't fix this right now, but we can work this around, if only we can assume how it works in practice.

On x86/amd64 I know processor for shifts uses only the appropriate less-significant bits of the shift count operand. So that a << b is in fact equivalent to a << (b & 31). From the hardware design this makes perfect sense.

My question is: how does this work in practice on modern popular platforms, such as arm, mips, RISC and etc. I mean those that are actually used in modern PCs and mobile devices, not outdated or esoteric.

Can we assume that those behave the same way?

EDIT:

  1. The code I'm talking about currently runs in a blockchain. It's less important how exactly it works, but at the very least we want to be sure that it yields identical results on all the machines. This is the most important, otherwise this can be exploited to induce a so-called chain split.

  2. Fixing this means hassles, because the fix should be applied simultaneously to all the running machines, otherwise we are yet again at risk of the chain split. But we will do this at some point in an organized (controlled) manner.

  3. Lesser problem with the variety of compilers. We only use GCC. I looked at the code with my own eyes, there's a shl instruction there. Frankly I don't expect it to be anything different given the context (shift operand comes from arbitrary source, can't be predicted at compile time).

  4. Please don't remind me that I "can't assume". I know this. My question is 100% practical. As I said, I know that on x86/amd64 the 32-bit shift instruction only takes 5 least significant bits of the bit count operand.

How does this behave on current modern architectures? We can also restrict the question to little-endian processors.

undefined-behavior bit-shift assembly cpu-architecture c
3 Answers

It is UB in C. Here you have an example: https://godbolt.org/z/5h9f7W6rr

It does not have any practical use unless you use inline assembly. But if you want how particular platforms handle left shift assembly instructions you need to see their assembly language references:

ARM-Thumb



    If n is 32 or more, then all the bits in the result are cleared to 0.

    If n is 33 or more and the carry flag is updated, it is updated to 0.

x86 - shift is performed modulo 32.

user_61100940

With code that triggers undefined behavior, the compiler can just about do anything - well, that's why it's undefined - asking for a safe definition of undefined code doesn't make any sense. Theoretical evaluations or observing the compiler translating similar code or assumptions on what "common practice" might be won't really give you an answer.

Evaluating what a compiler really has translated your UB code to would probably be your only safe bet. If you want to be really sure what happens in the corner cases, have a look at the generated (assembly or machine) code. Modern debuggers give you the toolset to catch those corner cases and tell you what actually happens (the generated machine code is, after all, very well defined). This will be much simpler and much safer than to speculate on what code the compiler might probably emit.

user_57853620

The authors of the Standard seek to classify as Undefined Behavior any action whose behavior might not be easy to describe consistently in a manner consistent with the C abstraction model and with general principles of operation on the target platform, or whose behavior might observably be affected by optimization. Although nearly all processors that have a shift-by-N instruction will handle x<<y for values of y that exceed the bit size by evaluating either (x<<(y-1)<<1) or (x<<(y-bitsize)) without side effects, the phrase "without side effects" could sometimes be a little nebulous. On some processors (such as, IIRC, at least one model of Transputer), straightforwardly processing x<<y when (uint32_t)y is 0xFFFFFFFF would result in the processor taking billions of cycles to execute a single instruction, without being able to service interrupts. While the time to execute an instruction would not normally be considered a side effect, having interrupts ignored for billions of cycles could undermine system stability.

There was never any reason to invite general-purpose compilers for architectures whose shift instructions always behave in one of the two described fashions to do anything other than process the code in one of those fashions, but the Standard makes no distinction between behavioral concessions for implementations that target unusual platforms or seek to flag places where code may be incompatible with them, versus invitations for general-purpose compilers for commonplace architectures to throw behavioral precedents out the window.

If one is using an implementation that is designed to uphold longstanding behavioral precedents in the absence of a compelling reason to do otherwise, without regard for whether the Standard would require such behavior, evaluation of x<<y will behave in one of the two described fashions. If one is using an implementation that interprets the words "Undefined Behavior" as an invitation to behave nonsensically for no reason beyond the fact that the Standard doesn't forbid such behavior, however, all bets are off.

user_3637510
Related