Si un nombre est trop grand, est-ce qu'il déborde sur l'emplacement de mémoire suivant?

30

J'ai passé en revue la programmation C et il y a juste quelques choses qui me dérangent.

Prenons ce code par exemple:

int myArray[5] = {1, 2, 2147483648, 4, 5};
int* ptr = myArray;
int i;
for(i=0; i<5; i++, ptr++)
    printf("\n Element %d holds %d at address %p", i, myArray[i], ptr);

Je sais qu'un int peut contenir une valeur maximale positive de 2.147.483.647. Donc, en passant à un autre, cela "déborde" à l'adresse de mémoire suivante, ce qui fait que l'élément 2 apparaît comme "-2147483648" à cette adresse? Mais cela n'a pas vraiment de sens car dans la sortie, il est toujours dit que la prochaine adresse contient la valeur 4, puis 5. Si le nombre avait débordé à l'adresse suivante, cela ne changerait-il pas la valeur stockée à cette adresse ?

Je me souviens vaguement de la programmation dans MIPS Assembly et de regarder les adresses changer les valeurs pendant le programme étape par étape que les valeurs affectées à ces adresses changeraient.

Sauf si je me souviens mal, voici une autre question: si le numéro attribué à une adresse spécifique est plus grand que le type (comme dans mon tableau [2]), cela n'affecte-t-il pas les valeurs stockées à l'adresse suivante?

Exemple: Nous avons int myNum = 4 milliards à l'adresse 0x10010000. Bien sûr, myNum ne peut pas stocker 4 milliards, il apparaît donc comme un nombre négatif à cette adresse. Bien qu'il ne soit pas en mesure de stocker ce grand nombre, cela n'a aucun effet sur la valeur stockée à l'adresse suivante de 0x10010004. Correct?

Les adresses mémoire ont juste assez d'espace pour contenir certaines tailles de nombres / caractères, et si la taille dépasse la limite alors elle sera représentée différemment (comme essayer de stocker 4 milliards dans l'int, mais elle apparaîtra comme un nombre négatif) et cela n'a donc aucun effet sur les nombres / caractères stockés à l'adresse suivante.

Désolé si je suis allé trop loin. J'ai eu un gros problème cérébral toute la journée.

courtaud
la source
10
Vous pourriez être confondu avec les dépassements de chaîne .
Robbie Dee
19
Travail à domicile: Modifier une CPU simple pour qu'il ne déversement. Vous verrez que la logique devient beaucoup plus complexe, le tout pour une «fonctionnalité» qui garantirait des failles de sécurité partout sans être utile en premier lieu.
phihag
4
Si vous avez besoin de nombres vraiment énormes, il est possible d'avoir une représentation numérique qui augmente la quantité de mémoire qu'elle utilise pour s'adapter à de grands nombres. Le processeur lui-même ne peut pas faire cela, et ce n'est pas une caractéristique du langage C, mais une bibliothèque peut l'implémenter - une bibliothèque C commune est la bibliothèque arithmétique GNU Multiple Precision . La bibliothèque doit gérer la mémoire pour stocker les nombres, ce qui a un coût de performance en plus de l'arithmétique. Beaucoup de langues ont ce genre de chose intégré (ce qui n'évite pas les coûts).
Steve314
1
écrire un test simple, je ne suis pas un programmeur C mais quelque chose dans le sens de int c = INT.MAXINT; c+=1;et voir ce qui est arrivé à c.
JonH
2
@JonH: Le problème est ce débordement dans le comportement indéfini. Le compilateur AC peut détecter ce code et en déduire qu'il est inaccessible car il déborde inconditionnellement. Étant donné que le code inaccessible n'a pas d'importance, il peut être éliminé. Résultat final: plus de code.
MSalters

Réponses:

48

Non. En C, les variables ont un ensemble fixe d'adresses mémoire avec lesquelles travailler. Si vous travaillez sur un système à 4 octets ints, et que vous définissez une intvariable sur 2,147,483,647puis ajoutez 1, la variable contiendra généralement -2147483648. (Sur la plupart des systèmes. Le comportement n'est en fait pas défini.) Aucun autre emplacement de mémoire ne sera modifié.

En substance, le compilateur ne vous permettra pas d'attribuer une valeur trop grande pour le type. Cela générera une erreur de compilation. Si vous le forcez avec un cas, la valeur sera tronquée.

Considéré de manière binaire, si le type ne peut stocker que 8 bits et que vous essayez de forcer la valeur 1010101010101avec un cas, vous vous retrouverez avec les 8 derniers bits, ou 01010101.

Dans votre exemple, quelle que soit votre action myArray[2], myArray[3]contiendra «4». Il n'y a pas de "débordement". Vous essayez de mettre quelque chose de plus de 4 octets, il se contentera de tout couper en haut de gamme, laissant les 4 derniers octets. Sur la plupart des systèmes, cela se traduira par -2147483648.

D'un point de vue pratique, vous voulez simplement vous assurer que cela n'arrive jamais. Ces sortes de débordements entraînent souvent des défauts difficiles à résoudre. En d'autres termes, si vous pensez qu'il y a une chance que vos valeurs se chiffrent en milliards, n'utilisez pas int.

Gort le robot
la source
52
Si vous travaillez sur un système avec des octets de 4 octets et que vous définissez une variable int sur 2 147 483 647, puis ajoutez 1, la variable contiendra -2147483648. => Non , c'est un comportement indéfini , il peut donc se répéter ou il peut faire autre chose entièrement; J'ai vu des compilateurs optimiser les contrôles basés sur l'absence de débordement et j'ai obtenu des boucles infinies par exemple ...
Matthieu M.
Désolé, oui, vous avez raison. J'aurais dû y ajouter un "habituellement".
Gort the Robot
@MatthieuM du point de vue de la langue , c'est vrai. En termes d'exécution sur un système donné, ce dont nous parlons ici, c'est un non-sens absolu.
Hobbs
@hobbs: Le problème est que lorsque les compilateurs gèrent le programme en raison d'un comportement indéfini, l'exécution du programme produit en effet un comportement inattendu, comparable en effet à l'écrasement de la mémoire.
Matthieu M.
24

Le dépassement d'entier signé est un comportement non défini. Si cela se produit, votre programme n'est pas valide. Le compilateur n'est pas tenu de vérifier cela pour vous, il peut donc générer un exécutable qui semble faire quelque chose de raisonnable, mais il n'y a aucune garantie qu'il le fera.

Cependant, le dépassement d'entier non signé est bien défini. Il encapsulera le modulo UINT_MAX + 1. La mémoire non occupée par votre variable ne sera pas affectée.

Voir aussi https://stackoverflow.com/q/18195715/951890

Vaughn Cato
la source
le débordement d'entier signé est tout aussi bien défini que le débordement d'entier non signé. si le mot a $ N $ bits, la limite supérieure du débordement d'entier signé est à $$ 2 ^ {N-1} -1 $$ (où il passe à $ -2 ^ {N-1} $) alors que le la limite supérieure pour le dépassement d'entier non signé est à $$ 2 ^ N - 1 $$ (où elle se termine à $ 0 $). mêmes mécanismes d'addition et de soustraction, même taille de la gamme de nombres ($ 2 ^ N $) qui peuvent être représentés. juste une limite différente de débordement.
robert bristow-johnson
1
@ robertbristow-johnson: Pas selon la norme C.
Vaughn Cato
eh bien, les normes sont parfois anachroniques. en regardant la référence SO, il y a un commentaire qui le frappe directement: "La note importante ici, cependant, est qu'il n'y a pas d'architectures dans le monde moderne utilisant autre chose que l'arithmétique signée du complément de 2. Que les normes de langage permettent toujours la mise en œuvre par exemple, un PDP-1 est un pur artefact historique. - Andy Ross 12 août 13 à 20:12 "
robert bristow-johnson
je suppose que ce n'est pas dans la norme C, mais je suppose qu'il pourrait y avoir une implémentation où l'arithmétique binaire régulière n'est pas utilisée pour int. je suppose qu'ils pourraient utiliser le code Gray ou BCD ou EBCDIC . Je ne sais pas pourquoi quelqu'un concevrait du matériel pour faire de l'arithmétique avec du code Gray ou EBCDIC, mais là encore, je ne sais pas pourquoi quelqu'un ferait du unsignedbinaire et signerait intavec autre chose que le complément de 2.
robert bristow-johnson
14

Donc, il y a deux choses ici:

  • le niveau de langage: quelle est la sémantique de C
  • le niveau machine: quelle est la sémantique de l'assemblage / CPU que vous utilisez

Au niveau linguistique:

En C:

  • le débordement et le sous-dépassement sont définis comme une arithmétique modulo pour les entiers non signés , ainsi leur valeur "boucles"
  • le débordement et le débordement sont un comportement indéfini pour les entiers signés , donc tout peut arriver

Pour ceux qui voudraient un exemple "quoi que ce soit", j'ai vu:

for (int i = 0; i >= 0; i++) {
    ...
}

changer en:

for (int i = 0; true; i++) {
    ...
}

et oui, c'est une transformation légitime.

Cela signifie qu'il existe en effet des risques potentiels d'écrasement de la mémoire en cas de débordement en raison d'une transformation étrange du compilateur.

Remarque: sur Clang ou gcc, utilisez -fsanitize=undefineddans Debug pour activer le Sanitaire de comportement non défini qui abandonnera en cas de dépassement / dépassement d'entiers signés.

Ou cela signifie que vous pouvez remplacer la mémoire en utilisant le résultat de l'opération d'indexation (non cochée) dans un tableau. Ceci est malheureusement beaucoup plus probable en l'absence de détection de débordement / débordement.

Remarque: sur Clang ou gcc, utilisez -fsanitize=addressdans Debug pour activer l' assainisseur d'adresses qui abandonnera l'accès hors limites.


Au niveau de la machine :

Cela dépend vraiment des instructions d'assemblage et du processeur que vous utilisez:

  • sur x86, ADD utilisera 2 compléments en cas de débordement / débordement et définira le OF (drapeau de débordement)
  • sur le futur CPU Mill, il y aura 4 modes de débordement différents pour Add:
    • Modulo: modulo à 2 compléments
    • Piège: un piège est généré, interrompant le calcul
    • Saturer: la valeur est bloquée sur min en cas de sous-débit ou max en cas de débordement
    • Double largeur: le résultat est généré dans un registre double largeur

Notez que si des choses se produisent dans les registres ou la mémoire, dans aucun cas le CPU n'écrase la mémoire en cas de débordement.

Matthieu M.
la source
Les trois derniers modes sont-ils signés? (Peu importe pour le premier, car il s'agit de 2 compléments.)
Déduplicateur
1
@Deduplicator: Selon l' introduction au modèle de programmation CPU Mill, il existe différents opcodes pour l'addition signée et l'addition non signée; Je m'attends à ce que les deux opcodes prennent en charge les 4 modes (et puissent fonctionner sur différentes largeurs de bits et scalaires / vecteurs). Là encore, c'est du matériel vapeur pour l'instant;)
Matthieu M.
4

Pour approfondir la réponse de @ StevenBurnap, la raison pour laquelle cela se produit est à cause du fonctionnement des ordinateurs au niveau de la machine.

Votre baie est stockée en mémoire (par exemple en RAM). Lorsqu'une opération arithmétique est effectuée, la valeur en mémoire est copiée dans les registres d'entrée du circuit qui effectue l'arithmétique (l'ALU: Arithmetic Logic Unit ), l'opération est ensuite effectuée sur les données dans les registres d'entrée, produisant un résultat dans le registre de sortie. Ce résultat est ensuite recopié en mémoire à la bonne adresse en mémoire, laissant les autres zones de mémoire intactes.

Pharap
la source
4

Tout d'abord (en supposant la norme C99), vous souhaiterez peut-être inclure <stdint.h>un en-tête standard et utiliser certains des types définis ici, notamment int32_tqui est exactement un entier signé 32 bits, ou uint64_tqui est exactement un entier non signé 64 bits, et ainsi de suite. Vous souhaiterez peut-être utiliser des types comme int_fast16_tpour des raisons de performances.

Lisez les autres réponses expliquant que l'arithmétique non signée ne se déverse pas (ou ne déborde pas) vers des emplacements de mémoire adjacents. Méfiez-vous des comportements non définis lors d'un débordement signé .

Ensuite, si vous devez calculer des nombres entiers exactement énormes (par exemple, vous voulez calculer la factorielle de 1000 avec tous ses 2568 chiffres en décimal), vous voulez des bigints aka nombres de précision arbitraires (ou bignums). Les algorithmes pour une arithmétique bigint efficace sont très intelligents et nécessitent généralement l'utilisation d'instructions machine spécialisées (par exemple, certains ajoutent un mot avec carry, si votre processeur en dispose). Par conséquent, je recommande fortement dans ce cas d'utiliser une bibliothèque bigint existante comme GMPlib

Basile Starynkevitch
la source