Question Comment détecter un débordement d'entier?


J'écrivais un programme en C ++ pour trouver toutes les solutions de uneb = c, où une, b et c ensemble, utilisez tous les chiffres 0-9 exactement une fois. Le programme a bouclé sur les valeurs de une et b, et a exécuté une routine de comptage de chiffres à chaque fois sur une, b et uneb pour vérifier si la condition de chiffres a été satisfaite.

Cependant, des solutions fausses peuvent être générées quand uneb déborde la limite entière. J'ai fini par vérifier cela en utilisant du code comme:

unsigned long b, c, c_test;
...
c_test=c*b;         // Possible overflow
if (c_test/b != c) {/* There has been an overflow*/}
else c=c_test;      // No overflow

Y a-t-il une meilleure façon de tester le débordement? Je sais que certaines puces ont un drapeau interne qui est défini quand le débordement se produit, mais je n'ai jamais vu l'accès par C ou C ++.


512
2017-10-13 22:53


origine


Réponses:


est un moyen de déterminer si une opération est susceptible de déborder, en utilisant les positions des bits les plus significatifs dans les opérandes et une petite connaissance de base en mathématiques binaires.

De plus, deux opérandes donneront (au plus) un bit de plus que le bit le plus élevé de l'opérande la plus grande. Par exemple:

bool addition_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
    return (a_bits<32 && b_bits<32);
}

Pour la multiplication, deux opérandes quelconques entraîneront (au plus) la somme des bits des opérandes. Par exemple:

bool multiplication_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
    return (a_bits+b_bits<=32);
}

De même, vous pouvez estimer la taille maximale du résultat de a à la puissance de b comme ça:

bool exponentiation_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a);
    return (a_bits*b<=32);
}

(Substituez le nombre de bits pour votre entier cible, bien sûr.)

Je ne suis pas sûr du moyen le plus rapide de déterminer la position du bit le plus élevé dans un nombre, voici une méthode brute-force:

size_t highestOneBitPosition(uint32_t a) {
    size_t bits=0;
    while (a!=0) {
        ++bits;
        a>>=1;
    };
    return bits;
}

Ce n'est pas parfait, mais cela vous donnera une bonne idée si deux nombres peuvent déborder avant de faire l'opération. Je ne sais pas si ce serait plus rapide que de simplement vérifier le résultat comme vous l'avez suggéré, à cause de la boucle dans le highestOneBitPosition fonction, mais cela pourrait être le cas (surtout si vous saviez combien de bits étaient dans les opérandes auparavant).


159
2017-10-13 23:44



Je vois que vous utilisez des entiers non signés. Par définition, en C (ne sais pas à propos de C ++), l'arithmétique non signée ne déborde pas ... donc, au moins pour C, votre point est sans intérêt :)

Avec des entiers signés, une fois qu'il y a eu débordement, Comportement non défini a eu lieu et votre programme peut faire n'importe quoi (par exemple: rendre les tests non concluants).

#include <limits.h>
int a = <something>;
int x = <something>;
a += x;              /* UB */
if (a < 0) {         /* unreliable test */
  /* ... */
}

Pour créer un programme conforme, vous devez tester le débordement avant générer ledit débordement. La méthode peut aussi être utilisée avec des entiers non signés

// for addition
#include <limits.h>
int a = <something>;
int x = <something>;
if ((x > 0) && (a > INT_MAX - x)) /* `a + x` would overflow */;
if ((x < 0) && (a < INT_MIN - x)) /* `a + x` would underflow */;

// for subtraction
#include <limits.h>
int a = <something>;
int x = <something>;
if ((x < 0) && (a > INT_MAX + x)) /* `a - x` would overflow */;
if ((x > 0) && (a < INT_MIN + x)) /* `a - x` would underflow */;

// for multiplication
#include <limits.h>
int a = <something>;
int x = <something>;
if (a > INT_MAX / x) /* `a * x` would overflow */;
if ((a < INT_MIN / x)) /* `a * x` would underflow */;
// there may be need to check for -1 for two's complement machines
if ((a == -1) && (x == INT_MIN)) /* `a * x` can overflow */
if ((x == -1) && (a == INT_MIN)) /* `a * x` (or `a / x`) can overflow */

pour la division (à l'exception de INT_MIN et -1 cas particulier) il n'y a aucune possibilité de passer en revue INT_MIN ou INT_MAX.


156
2017-10-03 17:15



Clang 3.4+ et GCC 5+ offre des builtins arithmétiques vérifiés. Ils offrent une solution très rapide à ce problème, en particulier par rapport aux contrôles de sécurité des tests de bits.

Pour l'exemple de la question d'OP, cela fonctionnerait comme ça:

unsigned long b, c, c_test;
if (__builtin_umull_overflow(b, c, &c_test))
{
    // returned non-zero: there has been an overflow
}
else
{
    // return zero: there hasn't been an overflow
}

La documentation Clang ne précise pas si c_test contient le résultat débordé si un débordement s'est produit, mais la documentation du GCC indique que c'est le cas. Étant donné que ces deux aiment être __builtin-compatible, il est probablement sûr de supposer que c'est ainsi que fonctionne Clang aussi.

Il y a un __builtin pour chaque opération arithmétique pouvant déborder (addition, soustraction, multiplication), avec des variantes signées et non signées, pour les tailles int, les tailles longues et les tailles longues et longues. La syntaxe pour le nom est __builtin_[us](operation)(l?l?)_overflow:

  • u pour non signé ou s pour signé;
  • l'opération est l'un des add, sub ou mul;
  • non l suffixe signifie que les opérandes sont ints; un l veux dire long; deux ls méchant long long.

Donc, pour une addition entière signée, il serait __builtin_saddl_overflow. La liste complète peut être trouvée sur le Clang page de documentation.

GCC 5+ et Clang 3.8+ offrent en outre des intégrations génériques qui fonctionnent sans spécifier le type des valeurs: __builtin_add_overflow, __builtin_sub_overflow et __builtin_mul_overflow. Ceux-ci fonctionnent également sur les types plus petits que int.

Les commandes intégrées sont optimales pour la plate-forme. Sur x86, ils vérifient les indicateurs de report, de débordement et de signature.

Le fichier cl.exe de Visual Studio n'a pas d'équivalent direct. Pour les additions et soustractions non signées, y compris <intrin.h> vous permettra d'utiliser addcarry_uNN et subborrow_uNN (où NN est le nombre de bits, comme addcarry_u8 ou subborrow_u64). Leur signature est un peu obtuse:

unsigned char _addcarry_u32(unsigned char c_in, unsigned int src1, unsigned int src2, unsigned int *sum);
unsigned char _subborrow_u32(unsigned char b_in, unsigned int src1, unsigned int src2, unsigned int *diff);

c_in/b_in est le drapeau carry / emprunter en entrée, la valeur de retour est le carry / emprunter en sortie. Il ne semble pas avoir d'équivalents pour les opérations ou les multiplications signées.

Sinon, Clang for Windows est maintenant prêt pour la production (assez bon pour Chrome), donc cela pourrait être une option.


111
2018-01-06 18:28



Certains compilateurs donnent accès à l'indicateur de débordement d'entier dans la CPU, que vous pouvez ensuite tester mais ce n'est pas standard.

Vous pouvez également tester la possibilité de débordement avant d'effectuer la multiplication:

if ( b > ULONG_MAX / a ) // a * b would overflow

49
2017-10-13 23:02



Attention: GCC peut optimiser une vérification de débordement lors de la compilation avec -O2. L'option -Wall vous donnera un avertissement dans certains cas, comme

if (a + b < a) { /* deal with overflow */ }

mais pas dans cet exemple:

b = abs(a);
if (b < 0) { /* deal with overflow */ }

Le seul moyen sûr est de vérifier le débordement avant qu'il ne se produise, comme décrit dans le Papier CERT, et cela serait incroyablement fastidieux à utiliser systématiquement.

Compiler avec -fwrapv résout le problème mais désactive certaines optimisations.

Nous avons désespérément besoin d'une meilleure solution. Je pense que le compilateur devrait émettre un avertissement par défaut lors d'une optimisation qui repose sur le dépassement de capacité. La situation actuelle permet au compilateur d'optimiser un contrôle de débordement, ce qui est inacceptable à mon avis.


35
2017-07-25 21:40



bruit prend désormais en charge les contrôles de dépassement de capacité dynamiques pour les entiers signés et non signés. Voir -fsanitize = entier commutateur. Pour l'instant, il s'agit d'un seul compilateur C ++ avec contrôle de débordement dynamique entièrement pris en charge à des fins de débogage.


27
2018-01-28 17:51



Voici une solution "non portable" à la question. Les processeurs Intel x86 et x64 ont ce qu'on appelle le registre EFLAGS ( http://en.wikipedia.org/wiki/EFLAGS ), qui est rempli par le processeur après chaque opération arithmétique entière. Je vais passer une description détaillée ici. Les indicateurs pertinents sont l'indicateur "Dépassement" (masque 0x800) et l'indicateur "Transporter" (masque 0x1). Pour les interpréter correctement, il faut considérer si les opérandes sont de type signé ou non.

Voici un moyen pratique de vérifier les drapeaux de C / C ++. Le code suivant fonctionnera sur Visual Studio 2005 ou plus récent (à la fois 32 et 64 bits), ainsi que sur GNU C / C ++ 64 bits.

#include <cstddef>
#if defined( _MSC_VER )
#include <intrin.h>
#endif

inline size_t query_intel_x86_eflags( const size_t query_bit_mask )
{
#if defined( _MSC_VER )
    return __readeflags() & query_bit_mask;
#elif defined( __GNUC__ )
    // this code will work only on 64-bit GNU-C machines;
    // Tested and does NOT work with Intel C++ 10.1!
    size_t eflags;
    __asm__ __volatile__(
        "pushfq \n\t"
        "pop %%rax\n\t"
        "movq %%rax, %0\n\t"
        :"=r"(eflags)
        :
        :"%rax"
        );
    return eflags & query_bit_mask;
#else
#pragma message("No inline assembly will work with this compiler!")
    return 0;
#endif
}

int main(int argc, char **argv)
{
    int x = 1000000000;
    int y = 20000;
    int z = x * y;
    int f = query_intel_x86_eflags( 0x801 );
    printf( "%X\n", f );
}

Si les opérandes ont été multipliés sans débordement, vous obtiendrez une valeur de retour de 0 à partir de query_intel_eflags (0x801), c’est-à-dire que les indicateurs carry et overflow ne sont pas définis. Dans l'exemple de code fourni par main (), un débordement se produit et les deux indicateurs sont mis à 1. Cette vérification n'implique aucun autre calcul, elle devrait donc être assez rapide.


20
2017-12-07 13:48