C++ Girl
  1. C++ Girl
  3. Ajouter des nombres entiers en toute sécurité et prouver la sécurité
Intereting Posts
Rassembler des bits à des positions spécifiques dans une nouvelle valeur Comment tester votre code sur une machine à architecture big-endian? Algorithme pour découper des plans (en place) à partir d’un tableau de valeurs RVB Erreur lors de l’utilisation de std :: bind et de std :: function en C ++ Quand les tableaux de longueur variable sont-ils légaux? #pragma pack ne comstackra pas? Shrink_to_fit est-il le bon moyen de réduire la capacité d’un `std :: vector` à sa taille? glfw + codeblocks + référence indéfinie à «__gxx_personality_sj0» Comment puis-je appeler la méthode child: le mot clé virtuel ne fonctionne pas? Performances en bande passante réduite avec boost :: asio :: ip :: tcp :: iostream append à un fichier avec ofstream Interface graphique utilisateur c ++ multithread (access aux formulaires) Signification de la syntaxe complexe C Le fait de lancer une exception dans un bloc de prise entraînera-t-il deux exceptions en vol? Quand l’inheritance virtuel EST-IL un bon projet?

Ajouter des nombres entiers en toute sécurité et prouver la sécurité

L’affectation de cours de programmation demande à

  • écrire une fonction (sécurisée) qui ajoute deux entiers, et
  • montrer que la fonction est sans danger.

Le code suivant représente ma solution. Je ne suis pas un expert du standard C (ni des méthodes de vérification formelle). Je voudrais donc poser la question suivante: existe-t-il des solutions meilleures (ou différentes)?

Je vous remercie 

#include  /* Try to add integers op1 and op2. Return 0 (success) or 1 (overflow prevented). In case of success, write the sum to res. */ int safe_int_add(int * res, int op1, int op2) { if (op2  op2 */ /* 0 < - op2 */ /* INT_MIN < - op2 + INT_MIN */ /* INT_MIN < INT_MIN - op2 */ /* INT_MIN = INT_MIN */ /* - op2 <= - INT_MIN */ /* INT_MIN - op2 <= - INT_MIN + INT_MIN */ /* INT_MIN - op2 <= 0 */ /* INT_MIN - op2 <= INT_MAX */ /* */ /** Hence, we have: ***************************************/ /* */ /* INT_MIN <= INT_MIN - op2 <= INT_MAX */ /* */ /* ie the following subtraction does not overflow. */ /* */ /***********************************************************/ if (op1 < INT_MIN - op2) { return 1; } /** We have: *********************************/ /* */ /* INT_MIN - op2 <= op1 */ /* INT_MIN <= op1 + op2 */ /* */ /** Also, we have: ***************************/ /* */ /* op2 < 0 */ /* op1 + op2 < op1 */ /* op1 + op2 < INT_MAX */ /* op1 + op2 <= INT_MAX */ /* */ /** Hence, we have: **************************/ /* */ /* INT_MIN <= op1 + op2 = 0 */ /* - op2 <= 0 */ /* INT_MAX - op2 = op2 */ /* - INT_MAX <= - op2 */ /* INT_MAX - INT_MAX <= - op2 + INT_MAX */ /* 0 <= - op2 + INT_MAX */ /* 0 <= INT_MAX - op2 */ /* INT_MIN <= INT_MAX - op2 */ /* */ /** Hence, we have: ***************************************/ /* */ /* INT_MIN <= INT_MAX - op2  INT_MAX - op2) { return 1; } /** We have: *********************************/ /* */ /* op1 <= INT_MAX - op2 */ /* op1 + op2 <= INT_MAX */ /* */ /** Also, we have: ***************************/ /* */ /* 0 <= op2 */ /* op1 <= op2 + op1 */ /* INT_MIN <= op2 + op1 */ /* INT_MIN <= op1 + op2 */ /* */ /** Hence, we have: **************************/ /* */ /* INT_MIN <= op1 + op2 <= INT_MAX */ /* */ /* ie the addition does not overflow. */ /* */ /**********************************************/ } *res = op1 + op2; return 0; }

L’approche d’OP consiste à restr de manière optimale dans le type int ainsi que dans la sécurité – pas de comportement indéfini (UB) avec une combinaison quelconque d’ int . Il est indépendant d’un format int particulier (complément à 2, complément à 2, magnitude du signe).

En C, int débordement / (débordement) est un comportement indéfini. Donc, le code, si vous restz avec int , doit déterminer le potentiel de débordement à l’avance. Avec op1 positif, INT_MAX - op1 ne peut pas déborder. De plus, avec op1 négatif, INT_MIN - op1 ne peut pas déborder. Donc, avec des arêtes correctement calculées et testées, op1 + op2 ne débordera pas. 

 // Minor re-write: int safe_int_add(int * res, int op1, int op2) { assert(res != NULL); if (op1 >= 0) { if (op2 > INT_MAX - op1) return 1; } else { if (op2 < INT_MIN - op1) return 1; } *res = op1 + op2; return 0; }

Voir également

Si un type plus large connu est disponible, le code pourrait utiliser 

 int safe_int_add_wide(int * res, int op1, int op2) { int2x sum = (int2x) op1 + op2; if (sum < INT_MIN || sum > INT_MAX) return 1; *res = (int) sum; return 0; }

Les approches utilisant unsigned , etc. doivent d’abord qualifier que UINT_MAX > = INT_MAX - INT_MIN . Ceci est généralement vrai, mais n'est pas garanti par la norme C.

Voici comment je le ferais:

Si les arguments d’entrée ont des signes différents, le résultat est toujours calculable sans risque de débordement.

Si les deux arguments d’entrée sont négatifs, alors calculez -safe_int_add(res, -op1, -op2); . (Vous devrez vérifier que op1 ou op2 ne sont pas le plus gros négatif en complément 2).

La fonction qui mérite reflection est celle qui ajoute deux nombres positifs: convertissez vos deux entrées en types non signés. Ajoutez ceux-ci. Cela garantit de ne pas dépasser le type non signé puisque vous pouvez stocker (au moins) deux fois plus de valeurs dans un entier non signé que dans un entier signé (exactement deux fois pour un complément à 1, un de plus pour un complément à 2).

Ne tentez ensuite une conversion en signature si la valeur non signée est suffisamment petite.

Vous pouvez regarder la mise en œuvre de JDK 8, qui fait une référence précise au livre Hacker’s Delight de Henry S. Warren, Jr. ici:

http://hg.openjdk.java.net/jdk8/jdk8/jdk/rev/b971b51bec01 

 public static int addExact(int x, int y) { int r = x + y; // HD 2-12 Overflow iff both arguments have the opposite sign of the result if (((x ^ r) & (y ^ r)) < 0) { throw new ArithmeticException("integer overflow"); } return r; }

Dans ma version du livre, il s'agit toutefois du chapitre 2-13. Vous y trouverez une longue explication sur toute la question.