Comment faire l'addition saturante en C?

En C Simple:

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 macro-isé et transmet directement le sens.

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

Dans ARM, vous avez peut-être déjà intégré l'arithmétique saturée. Les ARMv5 DSP-extensions peuvent saturer les registres à n'importe quelle longueur de bits. Aussi sur la saturation du bras est généralement pas cher parce que vous pouvez excuser la plupart des instructions conditionnelles.

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

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

Tout cela a besoin d'assembleur, donc ce n'est pas ce que vous avez demandé pour.

Il y a aussi 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 en ajoutant des nombres sans débordement de report.

Ceci est fait en premier. Ensuite, les carries sont calculés, ajoutés et remplacés par un masque si l'addition débordait.

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 tout type de champ de bits) en changeant la constante signmask et le se déplace 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 de même pour les valeurs de 16 et 32 bits.

Si vous n'avez pas besoin de la fonctionnalité que les fonctions ajoutent et saturent plusieurs valeurs en parallèle, masquez simplement les bits dont vous avez besoin. Sur ARM, vous voulez également changer la constante signmask car ARM ne peut pas charger toutes les constantes 32 bits possibles en un seul cycle.

Edit: les versions parallèles sont probablement plus lentes que les méthodes simples, mais elles sont plus rapides si vous avez saturer plus d'une valeur à la fois.

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

En raison de ce manque d'arithmétique saturante en mathématiques scalaires, on peut obtenir des cas dans lesquels les opérations effectuées sur SIMD à 4 variables sont Plus que 4 fois plus rapides que l'équivalent C (et par conséquent vrai avec SIMD à 8 variables):

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

Solution de branche Zéro:

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

Un bon compilateur optimisera cela pour éviter de faire une arithmétique 64 bits réelle ({[2] } sera simplement le drapeau de portage, et -(s>>32) est le résultat de sbb %eax,%eax).

En asm x86 (AT&T syntaxe, a et b dans eax et ebx, résultat dans eax):

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

Les versions 8 et 16 bits devraient être évidentes. Version signée peut nécessiter un peu plus de travail.

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

Je ne suis pas sûr que ce soit plus rapide que la solution de Skizz (toujours profil), Mais voici une solution alternative d'assemblage sans branche. Notez que cela nécessite l'instruction conditionnelle move (CMOV), que je ne suis pas sûr d'être disponible sur votre cible.

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

L'implémentation actuelle que nous utilisons est:

#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)))

Je suppose que la meilleure façon pour x86 est d'utiliser l'assembleur en ligne pour vérifier l'indicateur de débordement après l'addition. Quelque chose comme:

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

Ce n'est pas très portable, mais à mon humble avis le moyen le plus efficace.

Les meilleures performances impliquent généralement un assemblage en ligne (comme certains l'ont déjà indiqué).

Mais pour le portable C, ces fonctions n'impliquent qu'une seule comparaison et aucun type-casting (et donc je crois optimal):

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

En tant que macros, elles deviennent:

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)))

Je laisse les versions pour "unsigned long" et "unsigned long long" comme un exercice pour le lecteur. ;-)

Juste au cas où quelqu'un voudrait connaître une implémentation sans brancher en utilisant les entiers 32 bits du complément 2.

Attention! Ce code utilise l'opération indéfinie: "shift right by -1" et exploite donc la propriété de l'instruction Intel Pentium SAL pour masquer l'opérande count à 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);
 }

C'est la meilleure implémentation que je connaisse

En utilisant C++ , vous pouvez écrire une variante plus flexible de Remo.Solution de 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;
}

Cela peut être facilement traduit en C-en utilisant les limites définies dans limits.h. Veuillez également noter que les types entiers à Largeur fixe peuvent ne pas être disponibles sur votre système.

Une alternative à la solution ASM x86 sans branche est (syntaxe AT&T, A et B dans EAX et ebx, résultat dans eax):

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

//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;\
}\
})

J'ai fait un test rapide et semble fonctionner, mais pas beaucoup défoncé encore! Cela fonctionne avec signé 32 bits. op: l'éditeur utilisé sur la page web ne me laisse pas poster une macro, c'est-à-dire ne pas comprendre la syntaxe Non indentée, etc.!

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

Cette implémentation n'utilise pas de flux de contrôle, les opérateurs campare(==, !=) et l'opérateur ?:. Il utilise simplement des opérateurs binaires et des opérateurs logiques.

L'arithmétique de Saturation n'est pas standard pour C, mais souvent elle est implémentée via les intrinsèques du compilateur, donc le moyen le plus efficace ne sera pas le plus propre. Vous devez ajouter des blocs # ifdef pour sélectionner la bonne façon. La réponse de MSalters est la plus rapide pour l'architecture x86. Pour ARM, vous devez utiliser la fonction _ _ qadd16 (compilateur ARM) de _arm_qadd16 (Microsoft Visual Studio) pour la version 16 bits et __qadd pour la version 32 bits. Il sera automatiquement traduit à un bras instruction.

Liens:

__qadd16 http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0491c/CJAICDDF.html

_arm_qadd16 https://msdn.microsoft.com/en-US/library/hh875058.aspx

__qadd http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0472m/chr1359125002575.html