¿Cómo hacer una suma saturada sin signo en C?

Question

¿Cuál es la mejor forma (la más limpia y la más eficiente) de escribir una suma saturada en C?

La función o macro debe agregar dos entradas sin firmar (necesita versiones de 16 y 32 bits) y devolver todos los bits uno (0xFFFF o 0xFFFFFFFF) si la suma se desborda.

El objetivo es x86 y ARM usando gcc (4.1.2) y Visual Studio (solo para simulación, por lo que una implementación alternativa está bien allí).

Answer 1

Probablemente quieras portátil C código aquí, que su compilador convertirá en un ensamblaje ARM adecuado.ARM tiene movimientos condicionales, y estos pueden estar condicionados al desbordamiento.Luego, el algoritmo se convierte en agregar y establece condicionalmente el destino en sin firmar (-1) si se detecta un desbordamiento.

uint16_t add16(uint16_t a, uint16_t b)
{
  uint16_t c = a + b;
  if (c<a) /* Can only happen due to overflow */
    c = -1;
  return c;
}

Tenga en cuenta que esto difiere de los otros algoritmos en que corrige el desbordamiento, en lugar de depender de otro cálculo para detectar el desbordamiento.

x86-64 clang 3.7 -O3 salida para add32:significativamente mejor que cualquier otra respuesta:

    add     edi, esi
    mov     eax, -1
    cmovae  eax, edi
    ret

ARMv7: gcc 4.8 -O3 -mcpu=cortex-a15 -fverbose-asm salida para adiciones32:

    adds    r0, r0, r1      @ c, a, b
    it      cs
    movcs   r0, #-1         @ conditional-move
    bx      lr

16 bits:todavía no utiliza la instrucción de adición de saturación sin signo de ARM (UADD16)

    add     r1, r1, r0        @ tmp114, a
    movw    r3, #65535      @ tmp116,
    uxth    r1, r1  @ c, tmp114
    cmp     r0, r1    @ a, c
    ite     ls        @
    movls   r0, r1        @,, c
    movhi   r0, r3        @,, tmp116
    bx      lr  @

Answer 2

En simple C:

uint16_t sadd16(uint16_t a, uint16_t b)
    { return (a > 0xFFFF - b) ? 0xFFFF : a + b; }

uint32_t sadd32(uint32_t a, uint32_t b)
    { return (a > 0xFFFFFFFF - b) ? 0xFFFFFFFF : a + b;} 

que es casi macroizado y transmite directamente el significado.

Answer 3

En IA32 sin saltos condicionales:

uint32_t sadd32(uint32_t a, uint32_t b)
{
#if defined IA32
  __asm
  {
    mov eax,a
    xor edx,edx
    add eax,b
    setnc dl
    dec edx
    or eax,edx
  }
#elif defined ARM
  // ARM code
#else
  // non-IA32/ARM way, copy from above
#endif
}

Answer 4

Es posible que en ARM ya tenga incorporada la aritmética saturada.Las extensiones DSP ARMv5 pueden saturar registros a cualquier longitud de bits.Además, la saturación de ARM suele ser económica porque puede ejecutar la mayoría de las instrucciones de forma condicional.

ARMv6 incluso tiene sumas, restas y todo lo demás saturado para 32 bits y números empaquetados.

En el x86 obtienes aritmética saturada a través de MMX o SSE.

Todo esto necesita ensamblador, por lo que no es lo que has pedido.

También existen trucos C para hacer aritmética saturada.Este pequeño código realiza una suma saturada de cuatro bytes de una palabra dword.Se basa en la idea de calcular 32 semisumadores en paralelo, p.e.Sumar números sin desbordamiento de acarreo.

Esto se hace primero.Luego, los acarreos se calculan, se suman y se reemplazan con una máscara si la suma se desborda.

uint32_t SatAddUnsigned8(uint32_t x, uint32_t y) 
{
  uint32_t signmask = 0x80808080;
  uint32_t t0 = (y ^ x) & signmask;
  uint32_t t1 = (y & x) & signmask;
  x &= ~signmask;
  y &= ~signmask;
  x += y;
  t1 |= t0 & x;
  t1 = (t1 << 1) - (t1 >> 7);
  return (x ^ t0) | t1;
}

Puedes obtener lo mismo para 16 bits (o cualquier tipo de campo de bits) cambiando la constante de la máscara de signo y los cambios en la parte inferior de esta manera:

uint32_t SatAddUnsigned16(uint32_t x, uint32_t y) 
{
  uint32_t signmask = 0x80008000;
  uint32_t t0 = (y ^ x) & signmask;
  uint32_t t1 = (y & x) & signmask;
  x &= ~signmask;
  y &= ~signmask;
  x += y;
  t1 |= t0 & x;
  t1 = (t1 << 1) - (t1 >> 15);
  return (x ^ t0) | t1;
}

uint32_t SatAddUnsigned32 (uint32_t x, uint32_t y)
{
  uint32_t signmask = 0x80000000;
  uint32_t t0 = (y ^ x) & signmask;
  uint32_t t1 = (y & x) & signmask;
  x &= ~signmask;
  y &= ~signmask;
  x += y;
  t1 |= t0 & x;
  t1 = (t1 << 1) - (t1 >> 31);
  return (x ^ t0) | t1;
}

El código anterior hace lo mismo para valores de 16 y 32 bits.

Si no necesita la característica de que las funciones agregan y saturan múltiples valores en paralelo, simplemente enmascare los bits que necesita.En ARM también desea cambiar la constante de la máscara de señal porque ARM no puede cargar todas las constantes posibles de 32 bits en un solo ciclo.

Editar: Las versiones paralelas probablemente sean más lentas que los métodos sencillos, pero son más rápidas si tiene que saturar más de un valor a la vez.

Answer 5

Si te importa el rendimiento, en realidad Quiero hacer este tipo de cosas en SIMD, donde x86 tiene aritmética de saturación nativa.

Debido a esta falta de aritmética saturada en matemáticas escalares, se pueden encontrar casos en los que las operaciones realizadas en SIMD de 4 variables de ancho son más que 4 veces más rápido que el equivalente C (y correspondientemente cierto con SIMD de 8 variables de ancho):

sub8x8_dct8_c: 1332 clocks
sub8x8_dct8_mmx: 182 clocks
sub8x8_dct8_sse2: 127 clocks

Answer 6

Solución de rama cero:

uint32_t sadd32(uint32_t a, uint32_t b)
{
    uint64_t s = (uint64_t)a+b;
    return -(s>>32) | (uint32_t)s;
}

Un buen compilador optimizará esto para evitar realizar operaciones aritméticas reales de 64 bits (s>>32 será simplemente la bandera de acarreo, y -(s>>32) es el resultado de sbb %eax,%eax).

En x86 asm (sintaxis de AT&T, a y b en eax y ebx, resulta en eax):

add %eax,%ebx
sbb %eax,%eax
or %ebx,%eax

Las versiones de 8 y 16 bits deberían ser obvias.La versión firmada puede requerir un poco más de trabajo.

Answer 7

uint32_t saturate_add32(uint32_t a, uint32_t b)
{
    uint32_t sum = a + b;
    if ((sum < a) || (sum < b))
        return ~((uint32_t)0);
    else
        return sum;
} /* saturate_add32 */

uint16_t saturate_add16(uint16_t a, uint16_t b)
{
    uint16_t sum = a + b;
    if ((sum < a) || (sum < b))
        return ~((uint16_t)0);
    else
        return sum;
} /* saturate_add16 */

Editar: Ahora que has publicado tu versión, no estoy seguro de que la mía sea más limpia, mejor, más eficiente o más estudiada.

Answer 8

No estoy seguro de si esto es más rápido que la solución de Skizz (siempre perfil), pero aquí hay una solución alternativa de ensamblaje sin sucursales.Tenga en cuenta que esto requiere la instrucción de movimiento condicional (CMOV), que no estoy seguro de que esté disponible en su objetivo.

uint32_t sadd32(uint32_t a, uint32_t b)
{
    __asm
    {
        movl eax, a
        addl eax, b
        movl edx, 0xffffffff
        cmovc eax, edx
    }
}

Answer 9

La implementación actual que estamos utilizando es:

#define sadd16(a, b)  (uint16_t)( ((uint32_t)(a)+(uint32_t)(b)) > 0xffff ? 0xffff : ((a)+(b)))
#define sadd32(a, b)  (uint32_t)( ((uint64_t)(a)+(uint64_t)(b)) > 0xffffffff ? 0xffffffff : ((a)+(b)))

Answer 10

El mejor rendimiento normalmente implicará el montaje en línea (como algunos ya han dicho).

Pero para C portátil, estas funciones solo implican una comparación y no tipografía (y por lo tanto creo que es óptima):

unsigned saturate_add_uint(unsigned x, unsigned y)
{
    if (y>UINT_MAX-x) return UINT_MAX;
    return x+y;
}

unsigned short saturate_add_ushort(unsigned short x, unsigned short y)
{
    if (y>USHRT_MAX-x) return USHRT_MAX;
    return x+y;
}

Como macros, se convierten en:

SATURATE_ADD_UINT(x, y) (((y)>UINT_MAX-(x)) ? UINT_MAX : ((x)+(y)))
SATURATE_ADD_USHORT(x, y) (((y)>SHRT_MAX-(x)) ? USHRT_MAX : ((x)+(y)))

Dejo versiones para 'unsigned long' y 'unsigned long long' como ejercicio para el lector.;-)

Answer 11

En caso de que alguien quiera conocer una implementación sin bifurcaciones utilizando enteros de 32 bits en complemento a 2.

¡Advertencia!Este código utiliza la operación indefinida:"desplazarse a la derecha en -1" y por lo tanto explota la propiedad del Instrucción Intel Pentium SAL para enmascarar el operando de conteo a 5 bits.

int32_t sadd(int32_t a, int32_t b){
    int32_t sum = a+b;
    int32_t overflow = ((a^sum)&(b^sum))>>31;
    return (overflow<<31)^(sum>>overflow);
 }

Es la mejor implementación que conozco.

Answer 12

Supongo que la mejor manera para x86 es usar un ensamblador en línea para verificar el indicador de desbordamiento después de la adición.Algo como:

add eax, ebx
jno @@1
or eax, 0FFFFFFFFh
@@1:
.......

No es muy portátil, pero en mi humilde opinión es la forma más eficiente.

Answer 13

Una alternativa a la solución asm x86 sin sucursales es (sintaxis de AT&T, a y b en eax y ebx, resultado en eax):

add %eax,%ebx
sbb $0,%ebx

Answer 14

Usando C++ podrías escribir una variante más flexible de Remo.DLa solución de:

template<typename T>
T sadd(T first, T second)
{
    static_assert(std::is_integral<T>::value, "sadd is not defined for non-integral types");
    return first > std::numeric_limits<T>::max() - second ? std::numeric_limits<T>::max() : first + second;
}

Esto se puede traducir fácilmente a C, utilizando los límites definidos en limits.h.Tenga en cuenta también que el Tipos de enteros de ancho fijo Es posible que no esté disponible en su sistema.

Answer 15

//function-like macro to add signed vals, 
//then test for overlow and clamp to max if required
#define SATURATE_ADD(a,b,val)  ( {\
if( (a>=0) && (b>=0) )\
{\
    val = a + b;\
    if (val < 0) {val=0x7fffffff;}\
}\
else if( (a<=0) && (b<=0) )\
{\
    val = a + b;\
    if (val > 0) {val=-1*0x7fffffff;}\
}\
else\
{\
    val = a + b;\
}\
})

Hice una prueba rápida y parece funcionar, ¡pero todavía no lo destruí demasiado!Esto funciona con FIRMADO de 32 bits.operación:¡El editor utilizado en la página web no me permite publicar una macro, es decir, no comprende la sintaxis sin sangría, etc.!

Answer 16

int saturating_add(int x, int y)
{
    int w = sizeof(int) << 3;
    int msb = 1 << (w-1);

    int s = x + y;
    int sign_x = msb & x;
    int sign_y = msb & y;
    int sign_s = msb & s;

    int nflow = sign_x && sign_y && !sign_s;
    int pflow = !sign_x && !sign_y && sign_s;

    int nmask = (~!nflow + 1);
    int pmask = (~!pflow + 1);

    return (nmask & ((pmask & s) | (~pmask & ~msb))) | (~nmask & msb);
}

Esta implementación no utiliza flujos de control, operadores campare(==, !=) y el ?: operador.Simplemente utiliza operadores bit a bit y operadores lógicos.

Answer 17

La aritmética de saturación no es estándar para C, pero a menudo se implementa mediante elementos intrínsecos del compilador, por lo que la forma más eficiente no será la más limpia.Debes agregar #ifdef bloques para seleccionar la forma adecuada.La respuesta de MSalters es la más rápida para la arquitectura x86.Para ARM necesitas usar __qadd16 función (compilador ARM) de _arm_qadd16 (Microsoft Visual Studio) para la versión de 16 bits y __qadd para la versión de 32 bits.Se traducirán automáticamente a una instrucción ARM.

Enlaces:

• __qadd16
• _arm_qadd16
• __qadd