suma - como declarar fracciones en c++

¿Cómo hacer la adición de saturación en C?

Question

¿Cuál es la mejor (más limpia, más eficiente) forma de escribir la adición de saturación en C?

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

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

Answer 1

El mejor rendimiento generalmente implicará el ensamblaje en línea (como algunos ya lo han indicado).

Pero para C portátil, estas funciones solo implican una comparación y ningún tipo de conversión (y, por lo tanto, creo que es óptimo):

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 las versiones para ''unsigned long'' y ''unsigned long long'' como un ejercicio para el lector. ;-)

Answer 2

En ARM, es posible que ya tenga una aritmética saturada incorporada. Las extensiones DSP de ARMv5 pueden saturar registros a cualquier longitud de bit. También en ARM la saturación suele ser barata porque puede ejecutar la mayoría de las instrucciones condicional.

ARMv6 incluso tiene adiciones, restas y todas las otras cosas saturadas 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 ha pedido.

Hay C-tricks para hacer aritmética saturada también. Este pequeño código tiene una adición saturada en cuatro bytes de un dword. Se basa en la idea de calcular 32 medias sumadores en paralelo, por ejemplo, sumar números sin desbordamiento de carga.

Esto se hace primero. Luego, los acarreos se calculan, se agregan y se reemplazan con una máscara si la adición 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;
}

Puede obtener lo mismo para 16 bits (o cualquier tipo de campo de bits) cambiando la constante de 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 los valores de 16 y 32 bits.

Si no necesita la función 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 máscara de signo porque ARM no puede cargar todas las posibles constantes de 32 bits en un solo ciclo.

Editar: las versiones paralelas son muy probablemente 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 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

En llana 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 está casi macro -ized y transmite directamente el significado.

Answer 5

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 6

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

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

Answer 7

Probablemente desee un código C portátil aquí, que su compilador convertirá en el ensamblado correcto de ARM. ARM tiene movimientos condicionales, y estos pueden ser condicionales al desbordamiento. El algoritmo se convierte en add y establece condicionalmente el destino en unsigned (-1) si se detectó overflow.

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 adds32 : 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 adds32 :

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

16 bits: todavía no usa la instrucción de adición sin saturación 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 8

Si te preocupa el rendimiento, realmente quieres hacer este tipo de cosas en SIMD, donde x86 tiene una aritmética de saturación nativa.

Debido a esta falta de aritmética de saturación en la matemática escalar, se pueden obtener casos en los que las operaciones realizadas en SIMD de 4 variables son más de 4 veces más rápidas que la C equivalente (y correspondientemente cierto con SIMD de 8 variables):

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

Answer 9

Solo en caso de que alguien quiera saber una implementación sin ramificación usando enteros de 2 enteros de 32 bits.

¡Advertencia! Este código utiliza la operación no definida: "cambiar a la derecha por -1" y, por lo tanto, explota la propiedad de la 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 10

Solución de ramificación 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 hacer una aritmética real 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 AT & T, b en eax y ebx , dan como resultado 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 podría requerir un poco más de trabajo.

Answer 11

Supongo que la mejor manera para x86 es usar el 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 12

Una alternativa a la solución de asm x86 libre de ramificación es (sintaxis AT & T, ayb en eax y ebx, como resultado eax):

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

Answer 13

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

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, usando los límites definidos en los límites. Tenga en cuenta también que los tipos enteros de ancho fijo podrían no estar disponibles en su sistema.

Answer 14

//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 que funciona, ¡pero aún no lo he atacado! Esto funciona con SIGNED 32 bit. op: el editor utilizado en la página web no me permite publicar una macro, es decir, no entiende la sintaxis sin sangrados, etc.

Answer 15

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 de campare ( == ,! != ) Y el operador ?: . Solo usa operadores bit a bit y operadores lógicos.

Answer 16

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 ha publicado su versión, no estoy seguro de que la mía sea más limpia / mejor / más eficiente / más estudiada.