x86 left shift arithmetically overflow control

Question

Do you know any way to efficient check if overflow/underflow occurs on x86 left shift arithmetically?

using SAL instead SHL. I forgot to tell I am working with signed integers — LooPer, Sep 14 '11 at 12:26
SAL and SHL are identical. After all, the only difference between SAR and SHR is that SAR passes in the sign bit. what difference does that make for left-shifts? — Nathan Fellman, Sep 14 '11 at 12:35
You could check whether `abs(x_shifted) < abs(x)`, dunno if that's the most efficient way though. — user786653, Sep 14 '11 at 16:02
@user786653: That doesn't detect all overflows, though. e.g. `5 << 30` is `0x40000000`, shifting out the high bit of the `0b101` starting value and keeping the low one. (I chose that instead of `3<<31` because it doesn't even change sign, still positive). — Peter Cordes, Mar 20 '22 at 19:37

score 5 · Accepted Answer · edited Mar 20 '22 at 19:56

A good option is to perform an arithmetic shift right after the shift left and see if you got the same number:

    mov ebx, eax      ; keep a copy of the original
    sal eax, cl         ;  TODO: also copy the shifted EAX somewhere
    sar eax, cl
    cmp ebx, eax      ;  (x << n) >> n == x
    jne overflow
 ; result: not stored anywhere by this snippet.

BMI2 3-operand shifts can save some mov instructions:

; input: x in EDI, shift count n in ESI
    shlx  eax, edi, esi       ; there is no salx, it's the same operation
    sarx  edx, eax, esi       ; (x << n) >> n
    cmp   edx, eax
    jne   overflow
   ; else EAX = x<<n  without overflow

(This part of the answer is based on a misreading of the spec.)

If you're worried about the shift-count being so large it wraps, just check the shift count before shifting. If the shift count is greater than the number of bits, you'll get an overflow. (Except with 8 and 16-bit shifts, where you can shift out all the bits if you want; the count is masked to 5 bits for all operand-sizes below 64-bit.)

Usually you'd check the flags for this. However, you can't really rely on them for SHL (or SAL which is the same instruction). Look at the Software Developer's Manual, or an HTML extract:

Flags Affected

The CF flag contains the value of the last bit shifted out of the destination operand; it is undefined for SHL and SHR instructions where the count is greater than or equal to the size (in bits) of the destination operand. The OF flag is affected only for 1-bit shifts (see “Description” above); otherwise, it is undefined. The SF, ZF, and PF flags are set according to the result. If the count is 0, the flags are not affected. For a nonzero count, the AF flag is undefined.

The best way is to ensure that the shift count is <8 for byte operations, <16 for words, <32 for doublewords and <64 for quadwords, before shifting.

For detecting overflow of the result using FLAGS:

If the shift count is not greater than the destination operand, you can check the CF flag to see the last bit shifted out. If you perform the shift one bit at a time, you can test the CF after each shift to see if there was a 1 shifted out at any point, which would indicate an overflow.

But that would detect unsigned overflow. To detect signed overflow, it's not a problem when -1 (0x...ff) becomes -2 (0x...fe). But the key is that the sign bit didn't change. 1-bit shifts set OF according to actual signed overflow, with OF ← MSB(DEST) XOR CF;

This only works for shifting 1 bit at a time; x86 doesn't even define the value of OF for shift counts other than 1, unfortunately not recording whether any sign-flips happened along the way.

If you have one number near INT_MAX and make 1 bit SAL (or SAL) you will get an overflow as result is bigger than register size. — LooPer, Sep 14 '11 at 14:19

x86 left shift arithmetically overflow control

1 Answers1

Flags Affected