Saturday, March 5th, 2013
A few years ago I came across a snippet of code that was causing problems in a multi-platform product I was working on. The code was attempting to perform a shift-right operation but, in certain circumstances, used negative right hand operands.
The C++ language supports this as valid syntax (it should compile), but the results are undefined (see ISO 9899:1999 6.5.7). Needless to say, use of negative right hand shift operands is highly discouraged!
For the sake of simplicity, I've expanded a series of macros and reduced the offending code down to the following trivial example:
int z = -5 >> -1;
Depending upon the compiler used, z may equal zero or -1:
| Compiler | Target | Result | Mask |
| VS 2010 (CL 16.00.30319.01) | X86 | -1 | 0xFFFFFFFF |
| GCC 4.2.1 | X86 | 0 | 0x00000000 |
| GCC 4.2.1 | ARM | 0 | 0x00000000 |
The original code was relying upon the fact that an arithmetic shift right with a negative left hand operand would perform a sign extension, even if the right hand operand was negative. Unfortunately, the code then used the result of this operation as a mask to perform additional computation. This meant that on certain platforms a mask of 0xFFFFFFFF was used, while on others, the mask was zero.
Stepping Through - Visual Studio
To see more clearly what was going on (and going wrong), we should examine the disassembly of the offending code. The Visual Studio disassembly is similar to the following (comments added):
mov dword ptr [x], 0FFFFFFFFh # load -1 into x mov eax, 0FFFFFFFBh # load -5 into eax mov ecx, dword ptr [x] # load x into ecx sar eax, cl # arithmetic shift right
The first three lines simply load the values into registers. The fourth line performs the arithmetic shift right operation using the lowest byte ($cl) of $ecx. In this case, we've requested a shift by 255, which far exceeds the number of bits in our left hand operand ($eax). The arithmetic shift operator guarantees sign extension however, so we expect $eax to be -1 at completion.
Note that since we're only using the lowest byte of $ecx as the right hand operand of the shift, there is functionally no difference between a shift by 0xFFFFFFFF and 0x000000FF. (On some platforms even fewer bits are used, since you only need to cover the bit range of your registers, e.g. 5 bits on 32 bit platforms).
To further illustrate this, suppose we used the following values in our example:
int x = 0x80000001; int y = 0x80000005; int z = y >> x;
This will simply shift y by the lowest byte of x (0x01), with sign extension. Upon inspection in the debugger we see that z equals our expected value:
$0 = 0xC0000002
Stepping Through - GCC on X86
Returning to GCC to compare the disassembly of our offending snippet we find the following:
movl %esi, -20(%ebp) # set z equal to zero
Something unexpected is happening -- this code simply sets our result (the variable z) to zero. If we change our right hand operand to a positive value, we see more sensible disassembly.
We can remedy this problem by storing one operand in a separate variable, as follows:
int x = -5; int z = x >> -1;
This produces the following disassembly:
movl $4294967291, -20(%ebp) # set x = 0xfffffffb movl -20(%ebp), %eax # load x into eax movl %esi, %ecx # load 0xffffffff into ecx sarl %cl, %eax # arithmetic shift
At this point, the GCC path is now producing the same results as the Visual Studio path. Lines 1-3 effectively prepare our operands, and line 4 performs the expected shift operation.
Stepping Through - GCC on ARM
We now have a working "fix" that manages to produce identical results on x86 even when compiled with Visual Studio and GCC, so next we check our implementation against GCC with an ARM target.
Unfortunately, our modified code produces garbage values for our variable, z. However, if we modify the code further and store both operands in separate variables, we achieve correct results with all three configurations.
int x = -5; int y = -1; int z = x >> y;
At last we arrive at a final version of the code snippet that produces identical results across each of our three configurations.
Conclusion
Ultimately the changes we made in this article to produce identical results on each of our target platforms are unreasonable. While these changes achieved a functional result, they did not address the underlying issue -- that our code was relying upon undefined behavior. There is no guarantee that new or supported platforms will continue to behave as expected, and the changes may be confusing to future readers.
The actual fix that was implemented for the product removed the reliance on both the negative left and right hand operands, and functioned properly on all of our target platforms.
Guidelines for Shift Operators
Avoid using negative right hand operands with shift operations (!)
Avoid shifting by more than the register precision on the platform (!)
Be aware that a negative left hand operand will potentially cause an arithmetic shift operation (as opposed to a logical shift)
Pay attention to type promotion when shifting. The promotion is based on the left hand operand
