Détection du débordement signé en C / C++

non, votre 2e code n'est pas correct, mais vous êtes proche: si vous mettez

int half = INT_MAX/2;
int half1 = half + 1;

le résultat d'un ajout est INT_MAX . ( INT_MAX est toujours un nombre impair). C'est donc d'entrée valide. Mais dans votre routine, vous aurez INT_MAX - half == half1 et vous abandonner. Un faux positif.

cette erreur peut être corrigée en mettant < au lieu de <= dans les deux vérifications.

mais alors votre code n'est pas optimal. Ce qui suit ferait l'affaire:

int add(int lhs, int rhs)
{
 if (lhs >= 0) {
  if (INT_MAX - lhs < rhs) {
   /* would overflow */
   abort();
  }
 }
 else {
  if (rhs < INT_MIN - lhs) {
   /* would overflow */
   abort();
  }
 }
 return lhs + rhs;
}

pour voir que cela est valable, vous devez ajouter symboliquement lhs des deux côtés des inégalités, et cela vous donne exactement les conditions arithmétiques que votre résultat est hors limites.

IMHO, la manière la plus facile de gérer le débordement du code c++ est d'utiliser SafeInt<T> . Il s'agit d'un modèle de plateforme c++ hébergé sur le code plex qui fournit les garanties de sécurité que vous désirez ici.

• http://safeint.codeplex.com /

je le trouve très intuitif à utiliser car il fournit la plupart des mêmes modèles d'utilisation que les opérations numériques normales et exprime plus et sous flux via exceptions.

Pour les pays du ccg cas, de gcc Version 5.0 notes nous pouvons le voir maintenant, fournit un __builtin_add_overflow pour la vérification de débordement en plus:

Un nouvel ensemble de fonctions intégrées pour l'arithmétique avec vérification de dépassement a été ajouté: __builtin_add_débordement, __builtin_sous_débordement et __ _ _ builtin_mul_débordement et pour la compatibilité avec clang également d'autres variantes. Ces builtins ont deux arguments intégraux (qui n'ont pas besoin d'avoir le même type), les arguments sont étendus à la précision infinie type signé,+, - ou * est effectué sur ceux, et le résultat est stocké dans une variable entière pointée vers par le dernier argument. Si la valeur stockée est égale au résultat de précision infinie, les fonctions intégrées renvoient false, sinon true. Le type de la variable entière qui tiendra le résultat peut être différent des types des deux premiers arguments.

par exemple:

__builtin_add_overflow( rhs, lhs, &result )

nous pouvons voir à partir du document gcc fonctions intégrées pour effectuer L'arithmétique avec contrôle de débordement que:

[...]ces fonctions ont pleinement comportement défini pour toutes les valeurs d'argument.

clang fournit également un ensemble de vérifié arithmétique builtins :

Clang fournit un ensemble de builtins qui mettre en œuvre l'arithmétique vérifiée pour les applications critiques pour la sécurité d'une manière qui est rapide et facile à exprimer en C.

dans ce cas, l'immeuble serait:

__builtin_sadd_overflow( rhs, lhs, &result )

si vous utilisez inline assembler, vous pouvez cocher la case overflow flag . Une autre possibilité est que vous pouvez utiliser un safeint type de données . Je recommande que lire cet article sur entier de sécurité .

Que Diriez-vous de:

int sum(int n1, int n2)
{
  int result;
  if (n1 >= 0)
  {
    result = (n1 - INT_MAX)+n2; /* Can't overflow */
    if (result > 0) return INT_MAX; else return (result + INT_MAX);
  }
  else
  {
    result = (n1 - INT_MIN)+n2; /* Can't overflow */
    if (0 > result) return INT_MIN; else return (result + INT_MIN);
  }
}

je pense que cela devrait fonctionner pour toute légitime INT_MIN et INT_MAX (symétrique ou non); la fonction comme montré clips, mais il devrait être évident comment obtenir d'autres comportements).

vous pourriez avoir plus de chance de convertir en entiers 64 bits et de tester des conditions similaires comme cela. Par exemple:

#include <stdint.h>

...

int64_t sum = (int64_t)lhs + (int64_t)rhs;
if (sum < INT_MIN || sum > INT_MAX) {
    // Overflow occurred!
}
else {
    return sum;
}

vous voudrez peut-être regarder de plus près comment l'extension de signe fonctionnera ici, mais je pense que c'est correct.

le moyen le plus rapide possible est d'utiliser le bâtiment GCC:

int add(int lhs, int rhs) {
    int sum;
    if (__builtin_add_overflow(lhs, rhs, &sum))
        abort();
    return sum;
}

sur x86, GCC compile ceci en:

    mov %edi, %eax
    add %esi, %eax
    jo call_abort 
    ret
call_abort:
    call abort

qui utilise la détection de débordement intégrée du processeur.

si vous n'êtes pas D'accord avec L'utilisation de GCC builtins, le moyen le plus rapide est d'utiliser des opérations de bits sur les bits de signe. En outre, il y a débordement signé lorsque:

• les deux opérandes ont le même signe, et
• le résultat a un signe différent que les opérandes.

le bit de signe de ~(lhs ^ rhs) est sur iff les opérandes ont le même signe, et le bit de signe de lhs ^ sum est sur iff le résultat a un signe différent que les opérandes. Ainsi, vous pouvez faire l'addition sous forme non signée pour éviter le comportement non défini, puis utiliser le bit de signe de ~(lhs ^ rhs) & (lhs ^ sum) :

int add(int lhs, int rhs) {
    unsigned sum = (unsigned) lhs + (unsigned) rhs;
    if ((~(lhs ^ rhs) & (lhs ^ sum)) & 0x80000000)
        abort();
    return (int) sum;
}

Cette compile:

    lea (%rsi,%rdi), %eax
    xor %edi, %esi
    not %esi
    xor %eax, %edi
    test %edi, %esi
    js call_abort
    ret
call_abort:
    call abort

qui est beaucoup plus rapide que la coulée sur un type 64 bits sur une machine 32 bits (avec gcc):

    push %ebx
    mov 12(%esp), %ecx
    mov 8(%esp), %eax
    mov %ecx, %ebx
    sar , %ebx
    clt
    add %ecx, %eax
    adc %ebx, %edx
    mov %eax, %ecx
    add $-2147483648, %ecx
    mov %edx, %ebx
    adc "151940920", %ebx
    cmp "151940920", %ebx
    ja call_abort
    pop %ebx
    ret
call_abort:
    call abort

par moi, le contrôle le plus simple serait de vérifier les signes des opérandes et des résultats.

examinons la somme: le débordement pourrait se produire dans les deux directions, + ou -, seulement quand les deux opérandes ont le même signe. Et, obviosly, le dépassement sera quand le signe du résultat ne sera pas le même que le signe des opérandes.

vérifier que ce sera suffisant:

int a, b, sum;
sum = a + b;
if  (((a ^ ~b) & (a ^ sum)) & 0x80000000)
    detect_oveflow();

Edit: comme Nils suggéré, ce est la condition correcte if :

((((unsigned int)a ^ ~(unsigned int)b) & ((unsigned int)a ^ (unsigned int)sum)) & 0x80000000)

et depuis lors l'instruction

add eax, ebx 

mène à un comportement non défini? Il n'y a rien de Tel dans le jeu D'instructions Intel x86 refference..

la solution évidente est de convertir en unsigned, pour obtenir le comportement de débordement non signé bien défini:

int add(int lhs, int rhs) 
{ 
   int sum = (unsigned)lhs + (unsigned)rhs; 
   if ((lhs >= 0 && sum < rhs) || (lhs < 0 && sum > rhs)) { 
      /* an overflow has occurred */ 
      abort(); 
   } 
   return sum;  
} 

cela remplace le comportement de débordement signé non défini avec la conversion définie par la mise en œuvre des valeurs hors de gamme entre signé et non signé, donc vous devez vérifier la documentation de votre compilateur pour savoir exactement ce qui va se passer, mais il devrait au moins être bien défini, et devrait faire la bonne chose sur toute machine de complément de deux qui il n'émet pas de signaux sur les conversions, ce qui correspond à peu près à toutes les machines et compilateurs C construits au cours des 20 dernières années.

dans le cas de l'ajout de deux valeurs long , le code portable peut diviser la valeur long en parties basses et hautes int (ou en parties short dans le cas où long a la même taille que int ):

static_assert(sizeof(long) == 2*sizeof(int), "");
long a, b;
int ai[2] = {int(a), int(a >> (8*sizeof(int)))};
int bi[2] = {int(b), int(b >> (8*sizeof(int))});
... use the 'long' type to add the elements of 'ai' and 'bi'

L'utilisation d'un assemblage en ligne est le moyen le plus rapide pour cibler un CPU particulier:

long a, b;
bool overflow;
#ifdef __amd64__
    asm (
        "addq %2, %0; seto %1"
        : "+r" (a), "=ro" (overflow)
        : "ro" (b)
    );
#else
    #error "unsupported CPU"
#endif
if(overflow) ...
// The result is stored in variable 'a'

je pense que cela fonctionne:

int add(int lhs, int rhs) {
   volatile int sum = lhs + rhs;
   if (lhs != (sum - rhs) ) {
       /* overflow */
       //errno = ERANGE;
       abort();
   }
   return sum;
}

en utilisant volatile empêche le compilateur d'optimiser le test parce qu'il pense que sum peut avoir changé entre l'addition et la soustraction.

utilisant gcc 4.4.3 pour x86_64 l'assemblage pour ce code fait l'addition, la soustraction, et le test, bien qu'il stocke tout sur la pile et des opérations de pile inutiles. J'ai même essayé register volatile int sum = mais l'Assemblée a été la même.

Pour une version avec seulement int sum = (non volatile ou registre) la fonction n'a pas fait le test et a fait de plus en utilisant seulement un lea de l'enseignement ( lea est la Charge Effective de l'Adresse et est souvent utilisé pour faire plus sans toucher les drapeaux de registre).

votre version est plus grand code et a beaucoup plus de sauts, mais je ne sais pas qui serait meilleur .