Comment détecter un débordement de multiplication d'entiers non signés?

Je rédigeais un programme en C ++ pour trouver toutes les solutions d' un ^b = c , où a , b et c ensemble utiliser tous les chiffres 0-9 exactement une fois. Le programme a bouclé sur les valeurs de a et b , et il a exécuté une routine de comptage de chiffres à chaque fois sur a , b et a ^b pour vérifier si la condition des chiffres était satisfaite.

Cependant, les solutions parasites peuvent être générées lors d' un ^b 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

Existe-t-il un meilleur moyen de tester le débordement? Je sais que certaines puces ont un indicateur interne qui est défini lorsqu'un débordement se produit, mais je ne l'ai jamais vu accessible via C ou C ++.

Attention, le débordement signé int est un comportement indéfini en C et C ++ , et vous devez donc le détecter sans le provoquer réellement. Pour le débordement int signé avant l'ajout, voir Détection d'un débordement signé dans C / C ++ .

Je vois que vous utilisez des entiers non signés. Par définition, en C (je ne connais pas C ++), l'arithmétique non signée ne déborde pas ... donc, au moins pour C, votre point est sans objet :)

Avec les entiers signés, une fois qu'il y a eu débordement, un comportement non défini (UB) s'est produit 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 de générer ledit débordement. La méthode peut également ê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>;
// There may be a need to check for -1 for two's complement machines.
// If one number is -1 and another is INT_MIN, multiplying them we get abs(INT_MIN) which is 1 higher than INT_MAX
if ((a == -1) && (x == INT_MIN)) /* `a * x` can overflow */
if ((x == -1) && (a == INT_MIN)) /* `a * x` (or `a / x`) can overflow */
// general case
if (a > INT_MAX / x) /* `a * x` would overflow */;
if ((a < INT_MIN / x)) /* `a * x` would underflow */;

Pour la division (à l'exception du cas spécial INT_MINet -1), il n'y a aucune possibilité d'aller au-dessus INT_MINou INT_MAX.

Il existe 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 un peu de connaissances de base en mathématiques binaires.

De plus, deux opérandes quelconques donneront (au plus) un bit de plus que le bit le plus élevé du plus grand opérande. 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 donneront (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 aà la puissance de bceci:

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

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

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

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 la highestOneBitPositionfonction, mais cela pourrait (surtout si vous saviez combien de bits étaient dans les opérandes au préalable).

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

Pour l'exemple de la question de OP, cela fonctionnerait comme ceci:

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 de Clang ne spécifie pas si c_testcontient le résultat de débordement en cas de débordement, mais la documentation de GCC indique que c'est le cas. Étant donné que ces deux aiment être__builtin compatibles, il est probablement sûr de supposer que c'est aussi ainsi que fonctionne Clang.

Il existe __builtinpour chaque opération arithmétique qui peut 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 du nom est __builtin_[us](operation)(l?l?)_overflow:

• upour non signé ou spour signé ;
• l'opération est l'une des add, subou mul;
• aucun lsuffixe signifie que les opérandes sont ints; un lmoyen long; deux ls signifient long long.

Donc, pour un ajout d'entier long signé signé, ce serait __builtin_saddl_overflow. La liste complète se trouve sur la page de documentation de Clang .

GCC 5+ et Clang offrent en outre builtins supérieure à 3,8 génériques qui fonctionnent sans préciser le type des valeurs: __builtin_add_overflow, __builtin_sub_overflowet __builtin_mul_overflow. Ils fonctionnent également sur des types plus petits queint .

Les valeurs intégrées sont inférieures à ce qui est le mieux pour la plateforme. Sur x86, ils vérifient les indicateurs de portage, de débordement et de signature.

Le fichier cl.exe de Visual Studio n'a pas d'équivalents directs. Pour les ajouts et soustractions non signés, notamment <intrin.h>vous permettra d'utiliser addcarry_uNNet subborrow_uNN(où NN est le nombre de bits, comme addcarry_u8ou 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 l'indicateur carry / borrow en entrée et la valeur de retour est le carry / borrow en sortie. Il ne semble pas avoir d'équivalents pour les opérations signées ou les multiplications.

Sinon, Clang pour Windows est maintenant prêt pour la production (assez bon pour Chrome), ce qui pourrait également être une option.

Certains compilateurs donnent accès à l'indicateur de dépassement d'entier dans le processeur 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

Avertissement: GCC peut optimiser une vérification de dépassement lors de la compilation avec -O2. L'option -Wallvous 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 document CERT , et ce serait incroyablement fastidieux à utiliser systématiquement.

La compilation avec -fwrapvré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 de la réalisation d'une optimisation qui repose sur un débordement qui ne se produit pas. La situation actuelle permet au compilateur d'optimiser un contrôle de débordement, ce qui est inacceptable à mon avis.

Clang prend désormais en charge les vérifications de dépassement dynamique pour les entiers signés et non signés. Voir le commutateur -fsanitize = entier . Pour l'instant, c'est le seul compilateur C ++ avec une vérification de débordement dynamique entièrement prise en charge à des fins de débogage.

Je vois que beaucoup de gens ont répondu à la question sur le débordement, mais je voulais aborder son problème d'origine. Il a dit que le problème était de trouver un ^b = c tel que tous les chiffres soient utilisés sans répétition. Ok, ce n'est pas ce qu'il a demandé dans ce post, mais je pense toujours qu'il était nécessaire d'étudier la limite supérieure du problème et de conclure qu'il n'aurait jamais besoin de calculer ou de détecter un débordement (note: je ne suis pas compétent en mathématiques, j'ai donc fait cela étape par étape, mais le résultat final était si simple que cela pourrait avoir une formule simple).

Le point principal est que la limite supérieure que le problème requiert pour a, b ou c est 98.765.432. Quoi qu'il en soit, en commençant par diviser le problème dans les parties triviales et non triviales:

• x ⁰ == 1 (toutes les permutations de 9, 8, 7, 6, 5, 4, 3, 2 sont des solutions)
• x ¹ == x (aucune solution possible)
• 0 ^b == 0 (aucune solution possible)
• 1 ^b == 1 (aucune solution possible)
• a ^b , a> 1, b> 1 (non trivial)

Il suffit maintenant de montrer qu'aucune autre solution n'est possible et que seules les permutations sont valides (et alors le code pour les imprimer est trivial). Nous revenons à la limite supérieure. En fait, la limite supérieure est c ≤ 98,765,432. C'est la limite supérieure car c'est le plus grand nombre à 8 chiffres (10 chiffres au total moins 1 pour chaque a et b). Cette limite supérieure n'est valable que pour c car les limites pour a et b doivent être beaucoup plus faibles en raison de la croissance exponentielle, comme nous pouvons le calculer, variant b de 2 à la limite supérieure:

    9938.08^2 == 98765432
    462.241^3 == 98765432
    99.6899^4 == 98765432
    39.7119^5 == 98765432
    21.4998^6 == 98765432
    13.8703^7 == 98765432
    9.98448^8 == 98765432
    7.73196^9 == 98765432
    6.30174^10 == 98765432
    5.33068^11 == 98765432
    4.63679^12 == 98765432
    4.12069^13 == 98765432
    3.72429^14 == 98765432
    3.41172^15 == 98765432
    3.15982^16 == 98765432
    2.95305^17 == 98765432
    2.78064^18 == 98765432
    2.63493^19 == 98765432
    2.51033^20 == 98765432
    2.40268^21 == 98765432
    2.30883^22 == 98765432
    2.22634^23 == 98765432
    2.15332^24 == 98765432
    2.08826^25 == 98765432
    2.02995^26 == 98765432
    1.97741^27 == 98765432

Remarquez, par exemple la dernière ligne: il est dit que 1,97 ^ 27 ~ 98M. Ainsi, par exemple, 1 ^ 27 == 1 et 2 ^ 27 == 134.217.728 et ce n'est pas une solution car il a 9 chiffres (2> 1,97 donc il est en fait plus grand que ce qui devrait être testé). Comme on peut le voir, les combinaisons disponibles pour tester a et b sont vraiment petites. Pour b == 14, nous devons essayer 2 et 3. Pour b == 3, nous commençons à 2 et nous arrêtons à 462. Tous les résultats sont accordés pour être inférieurs à ~ 98M.

Maintenant, testez toutes les combinaisons ci-dessus et recherchez celles qui ne répètent aucun chiffre:

    ['0', '2', '4', '5', '6', '7', '8'] 84^2 = 7056
    ['1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481
    ['0', '1', '2', '3', '4', '5', '8', '9'] 59^2 = 3481 (+leading zero)
    ['1', '2', '3', '5', '8'] 8^3 = 512
    ['0', '1', '2', '3', '5', '8'] 8^3 = 512 (+leading zero)
    ['1', '2', '4', '6'] 4^2 = 16
    ['0', '1', '2', '4', '6'] 4^2 = 16 (+leading zero)
    ['1', '2', '4', '6'] 2^4 = 16
    ['0', '1', '2', '4', '6'] 2^4 = 16 (+leading zero)
    ['1', '2', '8', '9'] 9^2 = 81
    ['0', '1', '2', '8', '9'] 9^2 = 81 (+leading zero)
    ['1', '3', '4', '8'] 3^4 = 81
    ['0', '1', '3', '4', '8'] 3^4 = 81 (+leading zero)
    ['2', '3', '6', '7', '9'] 3^6 = 729
    ['0', '2', '3', '6', '7', '9'] 3^6 = 729 (+leading zero)
    ['2', '3', '8'] 2^3 = 8
    ['0', '2', '3', '8'] 2^3 = 8 (+leading zero)
    ['2', '3', '9'] 3^2 = 9
    ['0', '2', '3', '9'] 3^2 = 9 (+leading zero)
    ['2', '4', '6', '8'] 8^2 = 64
    ['0', '2', '4', '6', '8'] 8^2 = 64 (+leading zero)
    ['2', '4', '7', '9'] 7^2 = 49
    ['0', '2', '4', '7', '9'] 7^2 = 49 (+leading zero)

Aucun d'entre eux ne correspond au problème (ce qui peut également être constaté par l'absence de «0», «1», ..., «9»).

L'exemple de code qui le résout suit. Notez également que cela est écrit en Python, non pas parce qu'il a besoin d'entiers de précision arbitraires (le code ne calcule rien de plus de 98 millions), mais parce que nous avons découvert que le nombre de tests est si petit que nous devrions utiliser un langage de haut niveau pour utiliser ses conteneurs et bibliothèques intégrés (notez également: le code a 28 lignes).

    import math

    m = 98765432
    l = []
    for i in xrange(2, 98765432):
        inv = 1.0/i
        r = m**inv
        if (r < 2.0): break
        top = int(math.floor(r))
        assert(top <= m)

        for j in xrange(2, top+1):
            s = str(i) + str(j) + str(j**i)
            l.append((sorted(s), i, j, j**i))
            assert(j**i <= m)

    l.sort()
    for s, i, j, ji in l:
        assert(ji <= m)
        ss = sorted(set(s))
        if s == ss:
            print '%s %d^%d = %d' % (s, i, j, ji)

        # Try with non significant zero somewhere
        s = ['0'] + s
        ss = sorted(set(s))
        if s == ss:
            print '%s %d^%d = %d (+leading zero)' % (s, i, j, ji)

Voici une solution "non portable" à la question. Les processeurs Intel x86 et x64 ont le soi-disant registre EFLAGS , qui est rempli par le processeur après chaque opération arithmétique entière. Je vais sauter une description détaillée ici. Les drapeaux concernés sont le drapeau "Overflow" (masque 0x800) et le drapeau "Carry" (masque 0x1). Pour les interpréter correctement, il faut considérer si les opérandes sont de type signé ou non signé.

Voici un moyen pratique de vérifier les indicateurs de C / C ++. Le code suivant fonctionnera sur Visual Studio 2005 ou plus récent (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 étaient multipliés sans débordement, vous obtiendriez une valeur de retour de 0 query_intel_eflags(0x801), c'est-à-dire que ni les indicateurs de report ni de débordement ne sont définis. Dans l'exemple de code fourni de main (), un débordement se produit et les deux indicateurs sont définis sur 1. Cette vérification n'implique aucun calcul supplémentaire, elle devrait donc être assez rapide.

Si vous avez un type de données qui est plus grand que celui que vous souhaitez tester (disons que vous faites un ajout 32 bits et que vous avez un type 64 bits), cela détectera si un débordement s'est produit. Mon exemple est pour un ajout 8 bits. Mais il peut être étendu.

uint8_t x, y;    /* Give these values */
const uint16_t data16    = x + y;
const bool carry        = (data16 > 0xFF);
const bool overflow     = ((~(x ^ y)) & (x ^ data16) & 0x80);

Il est basé sur les concepts expliqués sur cette page: http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html

Pour un exemple 32 bits, 0xFFdevient 0xFFFFFFFFet 0x80devient 0x80000000et uint16_tdevient finalement a uint64_t.

REMARQUE : cela attrape les débordements d'addition / soustraction entiers, et j'ai réalisé que votre question implique la multiplication. Dans ce cas, la division est probablement la meilleure approche. C'est généralement un moyen que les callocimplémentations s'assurent que les paramètres ne débordent pas car ils sont multipliés pour obtenir la taille finale.

Le moyen le plus simple est de convertir vos unsigned longs en unsigned long longs, de faire votre multiplication et de comparer le résultat à 0x100000000LL.

Vous constaterez probablement que c'est plus efficace que de faire la division comme vous l'avez fait dans votre exemple.

Oh, et cela fonctionnera à la fois en C et C ++ (comme vous avez marqué la question avec les deux).

Je viens de jeter un œil au manuel de la glibc . Il y a une mention d'un piège de débordement d'entier ( FPE_INTOVF_TRAP) dans le cadre de SIGFPE. Ce serait idéal, en dehors des méchants morceaux du manuel:

FPE_INTOVF_TRAP Débordement d'entier (impossible dans un programme C sauf si vous activez le recouvrement de débordement d'une manière spécifique au matériel).

Un peu dommage vraiment.

Voici un moyen très rapide de détecter les débordements pour au moins les ajouts, ce qui pourrait donner une avance pour la multiplication, la division et la puissance de.

L'idée est qu'exactement parce que le processeur laissera simplement la valeur revenir à zéro et que C / C ++ doit être extrait de n'importe quel processeur spécifique, vous pouvez:

uint32_t x, y;
uint32_t value = x + y;
bool overflow = value < (x | y);

Cela garantit à la fois que si un opérande est nul et que l'autre ne l'est pas, le débordement ne sera pas faussement détecté et sera beaucoup plus rapide que beaucoup d'opérations NOT / XOR / AND / test comme suggéré précédemment.

Comme indiqué, cette approche, bien que meilleure que d'autres méthodes plus élaborées, est toujours optimisable. Ce qui suit est une révision du code d'origine contenant l'optimisation:

uint32_t x, y;
uint32_t value = x + y;
const bool overflow = value < x; // Alternatively "value < y" should also work

Un moyen plus efficace et moins cher de détecter un débordement de multiplication est:

uint32_t x, y;
const bool overflow = (x >> 16U) * (y >> 16U);
uint32_t value = overflow ? UINT32_MAX : x * y;

Il en résulte soit UINT32_MAX en cas de débordement, soit le résultat de la multiplication. C'est un comportement strictement indéfini de permettre à la multiplication de se poursuivre pour les entiers signés dans ce cas.

Vous ne pouvez pas accéder à l'indicateur de débordement depuis C / C ++.

Certains compilateurs vous permettent d'insérer des instructions d'interruption dans le code. Sur GCC, l'option est -ftrapv.

La seule chose portable et indépendante du compilateur que vous pouvez faire est de vérifier vous-même les débordements. Tout comme vous l'avez fait dans votre exemple.

Cependant, -ftrapvsemble ne rien faire sur x86 en utilisant le dernier GCC. Je suppose que c'est un reste d'une ancienne version ou spécifique à une autre architecture. Je m'attendais à ce que le compilateur insère un opcode INTO après chaque ajout. Malheureusement, cela ne fonctionne pas.

Pour les entiers non signés, vérifiez simplement que le résultat est inférieur à l'un des arguments:

unsigned int r, a, b;
r = a + b;
if (r < a)
{
    // Overflow
}

Pour les entiers signés, vous pouvez vérifier les signes des arguments et du résultat.

Les entiers de signes différents ne peuvent pas déborder et les entiers du même signe ne débordent que si le résultat est d'un signe différent:

signed int r, a, b, s;
r = a + b;
s = a>=0;
if (s == (b>=0) && s != (r>=0))
{
    // Overflow
}

J'avais besoin de répondre à cette même question pour les nombres à virgule flottante, où le masquage et le décalage des bits ne semblent pas prometteurs. L'approche sur laquelle je me suis installé fonctionne pour les nombres signés et non signés, entiers et à virgule flottante. Il fonctionne même s'il n'y a pas de type de données plus volumineux à promouvoir pour des calculs intermédiaires. Ce n'est pas le plus efficace pour tous ces types, mais parce qu'il fonctionne pour tous, il vaut la peine d'être utilisé.

Test de dépassement signé, addition et soustraction:

1. Obtenez les constantes qui représentent les valeurs les plus grandes et les plus petites possibles pour le type, MAXVALUE et MINVALUE.

2. Calculez et comparez les signes des opérandes.

   une. Si l'une des valeurs est nulle, ni l'addition ni la soustraction ne peuvent déborder. Ignorez les tests restants.

   b. Si les signes sont opposés, l'addition ne peut pas déborder. Ignorez les tests restants.

   c. Si les signes sont les mêmes, la soustraction ne peut pas déborder. Ignorez les tests restants.

3. Testez le débordement positif de MAXVALUE.

   une. Si les deux signes sont positifs et MAXVALUE - A <B, l'addition débordera.

   b. Si le signe de B est négatif et MAXVALUE - A <-B, alors la soustraction débordera.

4. Testez le débordement négatif de MINVALUE.

   une. Si les deux signes sont négatifs et MINVALUE - A> B, l'addition débordera.

   b. Si le signe de A est négatif et MINVALUE - A> B, la soustraction débordera.

5. Sinon, pas de débordement.

Test de dépassement signé, multiplication et division:

1. Obtenez les constantes qui représentent les valeurs les plus grandes et les plus petites possibles pour le type, MAXVALUE et MINVALUE.

2. Calculez et comparez les magnitudes (valeurs absolues) des opérandes à un. (Ci-dessous, supposons que A et B sont ces grandeurs, pas les originaux signés.)

   une. Si l'une des valeurs est nulle, la multiplication ne peut pas déborder et la division donnera zéro ou une infinité.

   b. Si l'une ou l'autre valeur est une, la multiplication et la division ne peuvent pas déborder.

   c. Si la grandeur d'un opérande est inférieure à un et que l'autre est supérieur à un, la multiplication ne peut pas déborder.

   ré. Si les grandeurs sont toutes deux inférieures à un, la division ne peut pas déborder.

3. Testez le débordement positif de MAXVALUE.

   une. Si les deux opérandes sont supérieurs à un et MAXVALUE / A <B, la multiplication débordera.

   b. Si B est inférieur à un et MAXVALUE * B <A, la division débordera.

4. Sinon, pas de débordement.

Remarque: le débordement minimum de MINVALUE est géré par 3, car nous avons pris des valeurs absolues. Cependant, si ABS (MINVALUE)> MAXVALUE, alors nous aurons de rares faux positifs.

Les tests de sous-dépassement sont similaires, mais impliquent EPSILON (le plus petit nombre positif supérieur à zéro).

Le CERT a développé une nouvelle approche pour détecter et signaler les dépassements d'entiers signés, les enveloppes d'entiers non signés et la troncature d'entiers en utilisant le modèle d'entier "comme si" à plage infinie (AIR). Le CERT a publié un rapport technique décrivant le modèle et produit un prototype fonctionnel basé sur GCC 4.4.0 et GCC 4.5.0.

Le modèle AIR entier produit une valeur équivalente à celle qui aurait été obtenue à l'aide d'entiers à plage infinie ou entraîne une violation de contrainte d'exécution. Contrairement aux modèles d'entiers précédents, les entiers AIR ne nécessitent pas d'interruptions précises et, par conséquent, ne cassent ni n'inhibent la plupart des optimisations existantes.

Un autre outil intéressant est IOC: An Integer Overflow Checker for C / C ++ .

Il s'agit d'un compilateur Clang patché , qui ajoute des vérifications au code au moment de la compilation.

Vous obtenez une sortie ressemblant à ceci:

CLANG ARITHMETIC UNDEFINED at <add.c, (9:11)> :
Op: +, Reason : Signed Addition Overflow,
BINARY OPERATION: left (int32): 2147483647 right (int32): 1

Une autre variante d'une solution, utilisant le langage d'assemblage, est une procédure externe. Cet exemple de multiplication d'entiers non signés utilisant g ++ et fasm sous Linux x64.

Cette procédure multiplie deux arguments entiers non signés (32 bits) (selon la spécification pour amd64 (section 3.2.3 Passage de paramètres ).

Si la classe est INTEGER, le prochain registre disponible de la séquence% rdi,% rsi,% rdx,% rcx,% r8 et% r9 est utilisé

(registres edi et esi dans mon code)) et renvoie le résultat ou 0 si un débordement s'est produit.

format ELF64

section '.text' executable

public u_mul

u_mul:
  MOV eax, edi
  mul esi
  jnc u_mul_ret
  xor eax, eax
u_mul_ret:
ret

Tester:

extern "C" unsigned int u_mul(const unsigned int a, const unsigned int b);

int main() {
    printf("%u\n", u_mul(4000000000,2)); // 0
    printf("%u\n", u_mul(UINT_MAX/2,2)); // OK
    return 0;
}

Liez le programme avec le fichier objet asm. Dans mon cas, dans Qt Creator , ajoutez-le à LIBSun fichier .pro.

Calculez les résultats avec des doubles. Ils ont 15 chiffres significatifs. Votre exigence a une limite supérieure rigide sur c de 10 ⁸  - elle peut avoir au plus 8 chiffres. Par conséquent, le résultat sera précis s'il est à portée, et il ne débordera pas autrement.

Essayez cette macro pour tester le bit de débordement des machines 32 bits (adapté la solution d'Angel Sinigersky)

#define overflowflag(isOverflow){   \
size_t eflags;                      \
asm ("pushfl ;"                     \
     "pop %%eax"                    \
    : "=a" (eflags));               \
isOverflow = (eflags >> 11) & 1;}

Je l'ai défini comme une macro car sinon le bit de débordement aurait été écrasé.

Ensuite, une petite application avec le segment de code ci-dessus:

#include <cstddef>
#include <stdio.h>
#include <iostream>
#include <conio.h>
#if defined( _MSC_VER )
#include <intrin.h>
#include <oskit/x86>
#endif

using namespace std;

#define detectOverflow(isOverflow){     \
size_t eflags;                      \
asm ("pushfl ;"                     \
    "pop %%eax"                     \
    : "=a" (eflags));               \
isOverflow = (eflags >> 11) & 1;}

int main(int argc, char **argv) {

    bool endTest = false;
    bool isOverflow;

    do {
        cout << "Enter two intergers" << endl;
        int x = 0;
        int y = 0;
        cin.clear();
        cin >> x >> y;
        int z = x * y;
        detectOverflow(isOverflow)
        printf("\nThe result is: %d", z);
        if (!isOverflow) {
            std::cout << ": no overflow occured\n" << std::endl;
        } else {
            std::cout << ": overflow occured\n" << std::endl;
        }

        z = x * x * y;
        detectOverflow(isOverflow)
        printf("\nThe result is: %d", z);
        if (!isOverflow) {
            std::cout << ": no overflow ocurred\n" << std::endl;
        } else {
            std::cout << ": overflow occured\n" << std::endl;
        }

        cout << "Do you want to stop? (Enter \"y\" or \"Y)" << endl;

        char c = 0;

        do {
            c = getchar();
        } while ((c == '\n') && (c != EOF));

        if (c == 'y' || c == 'Y') {
            endTest = true;
        }

        do {
            c = getchar();
        } while ((c != '\n') && (c != EOF));

    } while (!endTest);
}

Catching Integer Overflows in C indique une solution plus générale que celle discutée par CERT (elle est plus générale en termes de types gérés), même si elle nécessite des extensions GCC (je ne sais pas dans quelle mesure elles sont largement prises en charge).

Vous ne pouvez pas accéder à l'indicateur de débordement depuis C / C ++.

Je ne suis pas d'accord avec ça. Vous pouvez écrire un langage d'assemblage en ligne et utiliser une joinstruction (saut de débordement) en supposant que vous êtes sur x86 pour intercepter le débordement. Bien sûr, votre code ne serait plus portable sur d'autres architectures.

Regardez info aset info gcc.

Pour développer la réponse de Head Geek, il existe un moyen plus rapide de faire le addition_is_safe;

bool addition_is_safe(unsigned int a, unsigned int b)
{
    unsigned int L_Mask = std::numeric_limits<unsigned int>::max();
    L_Mask >>= 1;
    L_Mask = ~L_Mask;

    a &= L_Mask;
    b &= L_Mask;

    return ( a == 0 || b == 0 );
}

Cela utilise l'architecture de la machine en toute sécurité, dans la mesure où les entiers non signés 64 bits et 32 ​​bits fonctionneront toujours correctement. Fondamentalement, je crée un masque qui masquera tout sauf le bit le plus significatif. Ensuite, je masque les deux entiers, et si aucun d'entre eux n'a ce bit défini, l'addition est sûre.

Ce serait encore plus rapide si vous pré-initialisez le masque dans un constructeur, car il ne change jamais.

mozilla::CheckedInt<T>fournit des mathématiques entières vérifiées par débordement pour le type entier T(en utilisant les caractéristiques intrinsèques du compilateur sur clang et gcc selon les disponibilités). Le code est sous MPL 2.0 et dépend de trois ( IntegerTypeTraits.h, Attributes.het Compiler.h) autres en-têtes de bibliothèque non standard uniquement en-tête ainsi que des mécanismes d'assertion spécifiques à Mozilla . Vous souhaiterez probablement remplacer le mécanisme d'assertion si vous importez le code.

Réponse de MSalter est une bonne idée.

Si le calcul de l'entier est requis (pour plus de précision), mais qu'une virgule flottante est disponible, vous pouvez faire quelque chose comme:

uint64_t foo(uint64_t a, uint64_t b) {
    double dc;

    dc = pow(a, b);

    if (dc < UINT_MAX) {
       return (powu64(a, b));
    }
    else {
      // Overflow
    }
}

Le jeu d'instructions x86 comprend une instruction de multiplication non signée qui stocke le résultat dans deux registres. Pour utiliser cette instruction de C, on peut écrire le code suivant dans un programme 64 bits (GCC):

unsigned long checked_imul(unsigned long a, unsigned long b) {
  unsigned __int128 res = (unsigned __int128)a * b;
  if ((unsigned long)(res >> 64))
    printf("overflow in integer multiply");
  return (unsigned long)res;
}

Pour un programme 32 bits, il faut rendre le résultat 64 bits et les paramètres 32 bits.

Une alternative consiste à utiliser intrinsèque dépendant du compilateur pour vérifier le registre des indicateurs. La documentation GCC pour le débordement intrinsèque peut être trouvée dans 6.56 Fonctions intégrées pour effectuer l'arithmétique avec la vérification du débordement .

#include <stdio.h>
#include <stdlib.h>

#define MAX 100 

int mltovf(int a, int b)
{
    if (a && b) return abs(a) > MAX/abs(b);
    else return 0;
}

main()
{
    int a, b;

    for (a = 0; a <= MAX; a++)
        for (b = 0; b < MAX; b++) {

        if (mltovf(a, b) != (a*b > MAX)) 
            printf("Bad calculation: a: %d b: %d\n", a, b);

    }
}

Une manière propre de le faire serait de remplacer tous les opérateurs (+ et * en particulier) et de vérifier un débordement avant d'effectuer les opérations.

Cela dépend de l'utilisation que vous en faites. Pour effectuer une addition ou une multiplication DWORD longue non signée, la meilleure solution consiste à utiliser ULARGE_INTEGER.

ULARGE_INTEGER est une structure de deux DWORD. La valeur complète est accessible en tant que "QuadPart" tandis que le DWORD élevé est accessible en tant que "HighPart" et le DWORD faible est accessible en tant que "LowPart".

Par exemple:

DWORD
My Addition(DWORD Value_A, DWORD Value_B)
{
    ULARGE_INTEGER a, b;

    b.LowPart = Value_A;  // A 32 bit value(up to 32 bit)
    b.HighPart = 0;
    a.LowPart = Value_B;  // A 32 bit value(up to 32 bit)
    a.HighPart = 0;

    a.QuadPart += b.QuadPart;

    // If  a.HighPart
    // Then a.HighPart contains the overflow (carry)

    return (a.LowPart + a.HighPart)

    // Any overflow is stored in a.HighPart (up to 32 bits)

Pour effectuer une multiplication non signée sans déborder de manière portable, les éléments suivants peuvent être utilisés:

... /* begin multiplication */
unsigned multiplicand, multiplier, product, productHalf;
int zeroesMultiplicand, zeroesMultiplier;
zeroesMultiplicand = number_of_leading_zeroes( multiplicand );
zeroesMultiplier   = number_of_leading_zeroes( multiplier );
if( zeroesMultiplicand + zeroesMultiplier <= 30 ) goto overflow;
productHalf = multiplicand * ( c >> 1 );
if( (int)productHalf < 0 ) goto overflow;
product = productHalf * 2;
if( multiplier & 1 ){
   product += multiplicand;
   if( product < multiplicand ) goto overflow;
}
..../* continue code here where "product" is the correct product */
....
overflow: /* put overflow handling code here */

int number_of_leading_zeroes( unsigned value ){
   int ctZeroes;
   if( value == 0 ) return 32;
   ctZeroes = 1;
   if( ( value >> 16 ) == 0 ){ ctZeroes += 16; value = value << 16; }
   if( ( value >> 24 ) == 0 ){ ctZeroes +=  8; value = value <<  8; }
   if( ( value >> 28 ) == 0 ){ ctZeroes +=  4; value = value <<  4; }
   if( ( value >> 30 ) == 0 ){ ctZeroes +=  2; value = value <<  2; }
   ctZeroes -= x >> 31;
   return ctZeroes;
}

Le moyen simple de tester le débordement consiste à effectuer la validation en vérifiant si la valeur actuelle est inférieure à la valeur précédente. Par exemple, supposons que vous disposiez d'une boucle pour imprimer les puissances de 2:

long lng;
int n;
for (n = 0; n < 34; ++n)
{
   lng = pow (2, n);
   printf ("%li\n", lng);
}

L'ajout d'un débordement vérifiant la façon dont j'ai décrit les résultats dans ceci:

long signed lng, lng_prev = 0;
int n;
for (n = 0; n < 34; ++n)
{
    lng = pow (2, n);
    if (lng <= lng_prev)
    {
        printf ("Overflow: %i\n", n);
        /* Do whatever you do in the event of overflow.  */
    }
    printf ("%li\n", lng);
    lng_prev = lng;
}

Il fonctionne pour les valeurs non signées ainsi que pour les valeurs signées positives et négatives.

Bien sûr, si vous vouliez faire quelque chose de similaire pour diminuer les valeurs au lieu d'augmenter les valeurs, vous renverseriez le <=signe pour le faire >=, en supposant que le comportement de sous-dépassement est le même que le comportement de débordement. En toute honnêteté, c'est à peu près aussi portable que vous aurez sans accès à l'indicateur de débordement d'un processeur (et cela nécessiterait du code d'assemblage en ligne, ce qui rend votre code non portable dans toutes les implémentations de toute façon).