CODEWITHSUNDEEP
assemblyx86integer-overflow
Kolodez
Kolodez

Reputation: 635

Checking the SHL x86 assembly instruction for overflow

What is an easy way to check after the SHL EAX, CL instruction whether the theoretical result (EAX times (2 power CL)) fits into EAX? The question is about unsigned integers.

I hoped for something like checking the carry flag in the case of ADD instructions or checking EDX in the case of MUL instructions.

Upvotes: 3

Views: 467

Answers (2)

Netch
Netch

Reputation: 4572

You have not defined in what sense a method should be "easy", but if you afford two registers for temporary values, the check is trivial - just shift back (reverse direction) by the same width with the same shift kind ("logical" vs. "arithmetic"), and compare with the original value. This would look like:

    ; esi, edi - arbitrary choice
    mov esi, eax ; save the original value to later comparison
    shl eax, cl ; <-- the shift to check
    mov edi, eax
    shr edi, cl  ; <-- the opposite action
    cmp esi, edi ; equal to the original value?
    jne overflow_happened

This method is universal for processors that have cheap shifts (99.9%, with barrel shifter), and among all four variants of single linear shifts (sal, shl, sar, shr - for x86). It automatically "adjusts" its logic for the shift type. Also, you don't need to calculate a mask, test against two different signs (for signed values), etc.

For ISAs where shifts donʼt set condition codes at all (even if they are present, like in AArch64), or condition codes donʼt reflect full-width number interpretation (like in x86), the described method is the only really easy. So universal compilers tend to use it over different architectures. A few architectures (example: SystemZ) reflect arithmetic result in condition codes, but legacy - and easiness of reverse check - resulted in absence of this beside rare cases.

Upvotes: 3

Nate Eldredge
Nate Eldredge

Reputation: 58548

You can't do this by checking after the instruction. It does not record information about unsigned overflow, i.e. whether any 1 bits were shifted out. The carry flag only contains the last bit that was shifted out.

For instance, if EAX = 0xF0000000 and CL = 7, then SHL EAX, CL will leave EAX = 0 and the carry flag clear. You would get exactly the same architectural result, including all the other flag values, if the input was EAX = 0x00000000. So even though one has an overflow and the other does not, there is no way to distinguish them after the fact.

You can test before the instruction whether it will overflow, by checking if the top CL bits of EAX are zero. For instance (untested):

    MOV    EBX, 0x80000000
    SAR    EBX, CL    ; now top CL+1 bits of EBX are 1
    SHL    EBX, 1     ; now top CL bits of EBX are 1
    TEST   EBX, EAX   ; mask off all lower bits
    JNZ    will_overflow

Some other possible algorithms (maybe better) were suggested in the comments, such as SHLD.

Just because I happened to be thinking about it, here's a check for signed overflow, which occurs if and only if the top CL+1 bits are not all equal.

    MOV    EBX, 0x80000000
    SAR    EBX, CL      ; now top CL+1 bits of EBX are 1
    MOV    EDX, EAX     ; copy the input to be shifted
    AND    EDX, EBX     ; mask off all but top CL+1 bits
    JZ     no_overflow  ; top bits all 0
    CMP    EDX, EBX     
    JE     no_overflow  ; top bits all 1
    ; else handle overflow

For the one-bit shift instruction SHL EAX, 1, then the carry flag does exactly indicate whether unsigned overflow occurs. Also, the overflow flag indicates whether signed overflow occurs. In fact, all of CF, OF, ZF, SF, PF are set exactly the same as they would be for the mathematically equivalent ADD EAX, EAX. So if you are optimizing for space over speed, then instead of SHL EAX, CL, you could consider a loop, iterating CL times and executing SHL EAX, 1 followed by JC overflow_occurred on each iteration.

Upvotes: 2

Related Questions