Saturated integer addition in C

[Lawrence Crowl]

On 11/4/08, Liam Vrilehen <vrilehen@googlemail.com> wrote:
> Saturated integer addition in C
>
> I'm writing a C application that contains considerable amount of
> saturated integer math. Beeing curious I took a glance on the
> assembler gcc-4.3.1 generates for x86.
>
> The problem seems to be that I haven't found any way of coding
> that would result in overflow/carry dependent jumps or MMX/SSE2
> (MOVD -> PADDD -> MOVD).
>
> Any hints/ideas are welcome on how to write protable C code
> for saturated integer math. (Inline assembler isn't an option.)
>
> Below the C code, generated assembler and hand coded assembler
> for saturated addition of two 32 bit signed integers.
>
> The best C for gcc I've come up with so far:
> | #include <limits.h>
> |
> | int sum_saturated_gcc(int a, int b){
> |    int r = a + b;

This statement generates a signed integer overflow when
saturation would occur, and hence is not portable.  You need
to pre-test the arguments.  E.g.

    if ( b > 0 && MAX_INT - b < a )
        r = INT_MAX;
    else ....


> |
> |    if(0 <= r)
> |       if((a < 0) && (b < 0))
> |          r = INT_MIN;
> |    else if ((0 < a) && (0 < b))
> |       r = INT_MAX;
> |    return r;
> | }
>
> The generated assembler (-m32 -O3 -mmmx -msse  -msse2 -msse3):
> |    .file   "a.c"
> |    .text
> |    .p2align 4,,15
> | .globl sum_saturated_gcc
> |    .type   sum_saturated_gcc, @function
> | sum_saturated_gcc:
> |    pushl   %ebp
> |    movl   %esp, %ebp
> |    movl   12(%ebp), %edx
> |    addl   8(%ebp), %edx
> |    jns   .L6
> | .L2:
> |    movl   %edx, %eax
> |    popl   %ebp
> |    ret
> |    .p2align 4,,7
> |    .p2align 3
> | .L6:
> |    movl   8(%ebp), %eax
> |    testl   %eax, %eax
> |    js   .L7
> | .L3:
> |    movl   8(%ebp), %ecx
> |    testl   %ecx, %ecx
> |    jle   .L2
> |    movl   12(%ebp), %eax
> |    testl   %eax, %eax
> |    movl   $2147483647, %eax
> |    cmovg   %eax, %edx
> |    jmp   .L2
> |    .p2align 4,,7
> |    .p2align 3
> | .L7:
> |    movl   12(%ebp), %eax
> |    testl   %eax, %eax
> |    jns   .L3
> |    movl   $-2147483648, %edx
> |    jmp   .L2
> |    .size   sum_saturated_gcc, .-sum_saturated_gcc
> |    .ident   "GCC: (Gentoo 4.3.1-r1 p1.1) 4.3.1"
> |    .section   .note.GNU-stack,"",@progbits
>
>
> Hand coded assembler: plain x86, no MMX/SSE2 (MOVD -> PADDD -> MOVD)
> |    .text
> | .globl sum_saturated
> |    .type   sum_saturated, @function
> | sum_saturated:
> |    # prolog
> |    pushl   %ebp
> |    movl   %esp, %ebp
> |
> |    # add
> |    movl   8(%ebp), %eax
> |    addl   12(%ebp), %eax
> |
> |    # check overflow
> |    jno   .L_done
> |
> |    # check type of overflow
> |    js   .L_max
> |
> | .L_min:
> |    # overflow to positive
> |    movl   $-2147483648, %eax
> |    jmp   .L_done
> |
> | .L_max:
> |    # overflow to negative
> |    movl   $2147483647, %eax
> |
> | .L_done:
> |    # epilog
> |    popl   %ebp
> |    ret
> |    .size   sum_saturated, .-sum_saturated

--
Lawrence Crowl