Comment faire une addition saturante non signée en C ?

Question

Quelle est la meilleure façon (la plus propre, la plus efficace) d'écrire une addition saturante en C ?

La fonction ou la macro doit additionner deux entrées non signées (il faut des versions 16 et 32 bits) et renvoyer la valeur un (0xFFFF ou 0xFFFFFF) si la somme dépasse la limite.

La cible est x86 et ARM et utilise gcc (4.1.2) et Visual Studio (pour la simulation seulement, donc une implémentation de repli est OK ici).

Answer 1

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

qui est presque macroscopique et transmet directement le sens.

Answer 2

En IA32 sans sauts conditionnels :

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 3

En ARM, vous avez peut-être déjà intégré l'arithmétique saturée. Les extensions DSP ARMv5 peuvent saturer les registres à n'importe quelle longueur de bit. De plus, sur ARM, la saturation est généralement bon marché car vous pouvez excuter la plupart des instructions conditionnelles.

ARMv6 a même l'addition saturée, la soustraction et tous les autres trucs pour les 32 bits et les nombres emballés.

Sur le x86, vous obtenez une arithmétique saturée via MMX ou SSE.

Tout cela nécessite un assembleur, ce n'est donc pas ce que vous avez demandé.

Il existe également des astuces C pour faire de l'arithmétique saturée. Ce petit code fait une addition saturée sur quatre octets d'un dword. Il est basé sur l'idée de calculer 32 demi-additionneurs en parallèle, par exemple pour additionner des nombres sans débordement de retenue.

Ceci est fait en premier. Ensuite, les reports sont calculés, additionnés et remplacés par un masque si l'addition déborde.

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

Vous pouvez obtenir la même chose pour 16 bits (ou n'importe quel type de champ de bits) en modifiant la constante signmask et les décalages en bas comme ceci :

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

Le code ci-dessus fait la même chose pour les valeurs de 16 et 32 bits.

Si vous n'avez pas besoin de la fonction d'addition et de saturation de plusieurs valeurs en parallèle, masquez simplement les bits dont vous avez besoin. Sur ARM, vous devez également modifier la constante signmask car ARM ne peut pas charger toutes les constantes 32 bits possibles en un seul cycle.

Editar: Les versions parallèles sont très probablement plus lentes que les méthodes directes, mais elles sont plus rapides si vous devez saturer plus d'une valeur à la fois.

Answer 4

Si vous vous souciez des performances, vous vraiment veulent faire ce genre de choses en SIMD, où x86 a une arithmétique saturante native.

En raison de cette absence de saturation arithmétique dans les mathématiques scalaires, on peut obtenir des cas dans lesquels les opérations effectuées sur des SIMD à 4 variables sont les suivantes plus plus de 4 fois plus rapide que le C équivalent (et de manière correspondante avec 8-variables SIMD) :

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

Answer 5

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: Maintenant que vous avez posté votre version, je ne suis pas sûr que la mienne soit plus propre/meilleure/efficace/étonnante.