30 votos

Saturar Además en la C

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

La función o macro debe agregar dos unsigned entradas (necesidad de ambos de 16 y 32 bits) y devolver todos los bits de un (0xFFFF o 0xFFFFFFFF) si la suma se desborda.

Objetivo es x86 y ARM con gcc (4.1.2) y Visual Studio (para la simulación sólo, por lo que un retroceso de la aplicación es ACEPTAR que hay).

25voto

Remo.D Puntos 9841

En la llanura 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 el macro-izada y directamente transmite el significado.

17voto

Skizz Puntos 30682

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
}

10voto

Nils Pipenbrinck Puntos 41006

En el BRAZO de ustedes ya han saturado la aritmética incorporado. El ARMv5 DSP-extensiones se puede saturar de los registros de cualquier longitud de bits. También en el BRAZO de saturación es generalmente barato porque puede excute la mayoría de las instrucciones condicionales.

Binarios armv6 incluso se ha saturado la suma, la resta y todas las otras cosas para 32 bits y lleno de números.

En el x86 saturados de la aritmética, ya sea a través de MMX o SSE.

Todo esto necesita de ensamblador, por lo que no es lo que pediste.

Hay C-trucos para hacer saturada aritmética así. Este pequeño código saturadas, además de cuatro bytes de un valor dword. Se basa en la idea de calcular 32 de la mitad-serpientes en paralelo, por ejemplo, la adición de números sin llevar desbordamiento.

Esto se hace primero. Luego la lleva se calculan, agregó y se reemplaza con una máscara si la suma se desborde.

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;
}

Usted puede obtener el mismo para 16 bits (o cualquier tipo de bits de campo) cambiando el signmask constante y los cambios en la parte inferior como este:

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;
}

Código anterior hace lo mismo para los de 16 y 32 bits de los valores.

Si usted no necesita la característica de que las funciones de agregar y saturar los valores múltiples en paralelo sólo enmascarar los bits que necesita. En el BRAZO usted también desea cambiar el signmask constante debido a que el BRAZO no se puede cargar todos los posibles 32 bits constantes en un solo ciclo.

Edit: Las versiones paralelas son probablemente más lento que la recta de avance de los métodos, pero ellos son más rápidos si usted tiene que saturar más de un valor en un momento.

8voto

Dark Shikari Puntos 6178

Si usted se preocupa por el rendimiento, usted realmente quiere hacer este tipo de cosas en SIMD, donde x86 nativo para saturar la aritmética.

Debido a esta falta de saturación de la aritmética en escalar las matemáticas, uno puede obtener de los casos en los que las operaciones que se realicen en 4-variable-amplia SIMD es más de 4 veces más rápido que el equivalente a C (y, en consecuencia, cierto con 8-variable-amplia SIMD):

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

7voto

DGentry Puntos 10759
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 */

Edit: Ahora que usted ha publicado su versión, no estoy seguro de que la mía es cualquier limpiador/mejor/más eficiente y más studly.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X