Discussion :

[Array]

Bonjour,

Voilà je me pose quelques questions au sujet de div et idiv.
Les instruction de division en x86, comme vous le savez, partent avec un dividende d'une taille x, un diviseur d'une taille x/2, et donnent un quotient de taille x/2.

Supposons que EDX:EAX contienne le plus gros nombre possible qu'ils peuvent contenir, soit ffffffffffffffff (soit 64 bits mis à 1), et que ECX contienne 2.

Si je fais

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
mov eax, ffffffffffh;
mov edx, ffffffffffh;
mov ecx, 2;
div ecx;

Le résultat auquel on s'attend serait 7fffffffffffffff. Or, on sait très bien que la division échouera, puisque EAX ne peut contenir qu'un nombre de 32 bits maximum, et que c'est justement à 32bits qu'est consigné le quotient.

Ma question est: Y a-t-il un moyen de circonvenir le problème?
Dans le cas d'une opérande 32 bits divisé par une opérande 16 bits, par example ffffffff divisé par 2, c'est facile: On a qu'à étendre ffffffff à EAX:EDX, et d'étendre le diviseur dans une opérande 32 bits, puis on fait la division et on obtient le bon quotient, puisque ce dernier se trouve consigné dans une opérande 32 bits.


Par contre, je ne vois pas de solution pour diviser un 64 bits par un 2 étendu dans une opérande 32 bits.
Or, en C, c'est parfaitement possible.

Prenons le code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
#include <stdio.h>
 
int main(void) {
	unsigned long long int a = 0xffffffffffffffff, b;
	b = a/2;
	printf ("%ullx\n", b); // %I64x sur Windows
	return 0;
}

Le résultat affiché par printf() sera celui attendu, soit 7fffffffffffffff:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
I:\>a.exe
7fffffffffffffff

Bref, comment est-ce que le compilateur en C fait pour que le bon résultat puisse être obtenu?

Merci bien,
Cordialement,
Array

[Obsidian]

Le résultat auquel on s'attend serait 7fffffffffffffff. Or, on sait très bien que la division échouera, puisque EAX ne peut contenir qu'un nombre de 32 bits maximum, et que c'est justement à 32bits qu'est consigné le quotient.

Effectivement, le micro-processeur déclenchera une exception, dans ce cas.

Ma question est: Y a-t-il un moyen de circonvenir le problème?

Par contre, je ne vois pas de solution pour diviser un 64 bits par un 2 étendu dans une opérande 32 bits. Or, en C, c'est parfaitement possible. Bref, comment est-ce que le compilateur en C fait pour que le bon résultat puisse être obtenu?

On procède comme à l'école, sur papier : on va procéder avec des mots deux fois plus courts (donc 16 bits sur une architecture 32) en commençant par le plus significatif (donc le plus à gauche), en posant le quotient, et en « faisant descendre » la tranche suivante, ce qui va consister, dans notre cas, à faire passer le reste d'un registre à l'autre (pour le « décaler à gauche » en réalité) et à charger la nouvelle tranche dans le registre qui était dédié au reste.

De cette façon, tu peux diviser des nombres de n'importe quelle longueur, ce qui est très utile dans le traitement des CRC, par exemple.

[Array]

Y a-t-il une instruction spécifique pour effectuer le travail, où doit on tout coder manuellement?

[ToutEnMasm]

On peut aussi utiliser le FPU,ce qui est LA solution.

[Obsidian]

Je vois, quelque chose comme (x + y)/2 = x/2 +y/2.
Sauf que s'il y a un "remainder" pour x, et un autre pour y, que se passe-t-il? Y a-t-il une instruction spécifique pour effectuer le travail, où doit on tout coder manuellement? Merci!

L'idée est de faire une boucle. L'algorithme est le même que celui que tu utilises à l'école. Tu as un seul reste à chaque tour de boucle, et celui-ci est directement impliqué dans l'opération suivante, sans avoir à faire d'addition explicite. Comme ce reste est, par définition, inférieur à ton diviseur, il prendra sa place dans la partie haute de ton dividende, certes, mais le résultat tiendra forcément dans l'équivalent de la partie basse, donc dans le registre qui lui est affecté.

Imaginons que tu veuilles diviser 7FFF.FFFF.FFFF.FFFF (donc 64 bits) par 5 sur une machine 32 bits :

• Tu prends le premier mot de 32 bits à gauche et tu le places dans EAX (à droite), en mettant EDX (à gauche) à zéro. Donc EDX=00000000 et EAX=7FFFFFFF ;
• Tu divises par 5. EAX contient le quotient en totalité et EDX le reste, soit respectivement 19999999h et 00000002h ;
• Tu poses EAX (en mémoire, donc, soit dans la pile, soit avec un registre d'index tel que DI), et tu passes le reste dans EAX pour en fait le multiplier par la taille du mot, et tu descends la suite (donc FFFF.FFFF) dans EAX. Tu redivises le tout par 5 : 0000.0002.FFFF.FFFF ÷ 5 ;
• Le résultat tient forcément dans 32 bits : 00000000.99999999. Donc EAX=99999999h et EDX=2. Tu poses EAX comme à l'étape précédente.

À ce stade, tu as fini ta division car tu as épuisé tous les mots, mais tu as effectivement un reste : c'est normal car 7FFFFFFFFFFFFFFF n'est pas divisible par cinq.

Reste à vérifier si le résultat est correct : 1999999999999999 × 5 = 7FFFFFFFFFFFFFFD ; + 2 (reste) = 7FFFFFFFFFFFFFFF. Ça colle.

[Obsidian]

On peut aussi utiliser le FPU,ce qui est LA solution.

Tous les CPU ne sont pas équipés d'un FPU, loin s'en faut. À vrai dire, rares sont les micro-processeurs qui en sont équipés. Même sur PC, il a fallu attendre le 486DX pour qu'ils en soient équipés par défaut.

Par ailleurs, savoir faire des calculs élémentaires est exigible de tout programmeur, spécialement s'il développe en assembleur. Enfin, dans le cas d'absence d'un copro, on utilise tout naturellement une routine pour faire ces calculs… routine qui a bien dû être conçue et écrite par un programmeur.

Sinon, cela veut dire que les informaticiens délèguent leur travail aux électroniciens et aux fondeurs de puce.

[edfed]

c'est sur que du point du vue du puriste de l'asm qui aime le risc, il ne faut pas utiliser fpu et autres extension.
par contre, pour les puristes du x86, qui aiment bien le cisc et les new technologies, ça le fait, utiliser la fpu ou pire, les extensions vectorielles SIMD et autres, ça peut etre un sacré plus.

mais il faut la solution risc, à base de code purement 32 bits ou 16 bits.

la solution proposée par obsidian est pas mal, mais je rappele qu'en contexte d'utilisation de div et idiv, le registre (e)dx est supposé etre l'extension de signe (ou de zero) du registre (e)ax, et donc, aucune valeur d'entrée ne peut depasser les 32 bits en 32 bits, ou 16 bits en 16 bits.
ce qui n'empeche pas evidement d'avoir un registre edx avec des chiffres significatifs avant division... mais bon, c'est pas conseillé de bosser trop près des limites sur une machine comme les PC, vu la quantité de données qu'on peut être amené à traiter, on ne peut se permettre d'avoir des sources d'erreurs potentielles.

[Array]

La question de départ étiat: Comment les compilateurs C implémentent la division en 64 bits.
Le compilateur n'utilise donc pas le FPU, right?

[ToutEnMasm]

Tous les CPU ne sont pas équipés d'un FPU, loin s'en faut. À vrai dire, rares sont les micro-processeurs qui en sont équipés. Même sur PC, il a fallu attendre le 486DX pour qu'ils en soient équipés par défaut

Vrai et comme le 486 ne date pas d'hier ,je suis curieux de voir un pc fonctionnant aujourdh'ui sans le FPU par défaut.
Il est vrai aussi qu'a titre d'exercice on peut utiliser les registres 32 bits.C'est instructif.
Des sources intel fourni avec la crt (c++ express) en donne de bons exemples.

[Obsidian]

Le compilateur n'utilise donc pas le FPU, right?

Si. Il l'utilise si elle est disponible et s'il estime que c'est le choix le plus efficace, ce qui est généralement le choix. Dans le cas contraire, en fonction du paramétrage, il fait soit appel à une routine existante dans une bibliothèque de runtime, soit il génère lui-même la routine inline en choisissant un algorithme tel que celui que je t'ai donné, et essaie autant que faire se peut de l'optimiser en fonction de l'entourage.

Avec GCC, par exemple, tu peux faire « gcc -S » pour voir le code assembleur produit.

[Array]

Obsidian, il y a une exception que je crois percevoir avec l'algorithme.
Supposons que je souhaite faire la division suivante (les crochets ne sont là que pour délimiter chaque "quadword"):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
[00000000000007ff][ffffffffffffffff] / 00ffffff

Ici, on divise en chaîne un 128 bits avec un ffffffh contenu dans un 32 bits.

Donc, la division commencera par faire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
7ff / ffffff
Remainder=7ff
Quotient=0

Mais comme le remainder restera le chiffre qu'il faut diviser, la boucle ne s'arrêtera jamais, si bien que la division se pousuivra comme suit indéfiniment:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
7ff / ffffff
Remainder=7ff
Quotient=0
 
bla bla bla

La seule solution que je vois est de décaler vers la gauche le nombre, pour que le premier "quadword" à diviser soit rempli complètement:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
[7fffffffffffffff][fff0000000000000] / 00ffffff
 
De cette façon la première partie de la division se fera ainsi:
7fffffffffffffff / ffffff
Remainder=7fff
Quotient=8000008000

Voyez-vous ce que je veux dire? Est-ce exact?

[Obsidian]

Mais comme le remainder restera le chiffre qu'il faut diviser, la boucle ne s'arrêtera jamais, si bien que la division se pousuivra comme suit indéfiniment:

Non, puisqu'à chaque fois, tu décales ton reste vers la gauche, en le transférant dans l'autre registre, pour faire descendre à sa place la tranche suivante. Tu vas donc commencer à poser ton quotient (ici, zéro) puis le décaler, de sorte que tu vas finir par te retrouver naturellement dans une situation analogue à celle que tu préconises.

Il est aisé de faire le parallèle avec la bonne vieille division sur papier : on nous apprend à l'école à commencer avec un certain nombre de chiffres à gauche du dividende. En fait, plus précisément, on va prendre le nombre minimum de chiffres tels que le nombre qu'il forme soit égal ou supérieur au diviseur. Mais il en reste que ça fonctionne quand même dans tous les cas : si tu en prends trop, tu vas effectuer un nombre inutile de soustractions. Si tu n'en prends pas assez, le résultat sera égal à zéro, le dividende sera intact, et tu vas descendre un chiffre supplémentaire jusqu'à ce que la division soit possible.

Par exemple : 123456 ÷ 73.
— 1 ÷ 73 = 0. Je pose zéro et il reste 1. Je descends le 2 d'à côté et obtiens 12 ;
— 12 ÷ 73 = 0. Je pose zéro et il reste 12. Je descends le 3 d'à côté et obtiens 123 ;
— 123 ÷ 73 = 1. Je pose un et il reste 50. La division était possible à partir de ce stade.

Au final, le résultat est à peu près égal à 1691,17. En commençant avec le nombre minimum de chiffres (un seul), j'obtiens 001691,17. Donc, des zéros non significatifs mais c'est tout. Or, en informatique, non seulement ce n'est pas gênant mais c'est même nécessaire pour conserver le bon format du nombre.

[Array]

Merci pour l'explication, je n'avais pas porté suffisamment attention.

Une autre question me tracasse.

On peut aussi utiliser le FPU,ce qui est LA solution.

Comment est-ce qu'on procède pour résoudre le problème avec la solution FPU? Le floating n'est-t-il pas censé être plus lent que lorsqu'on utilise uniquement des entiers?

Cordialement,
Array

[ToutEnMasm]

Comment est-ce qu'on procède pour résoudre le problème avec la solution FPU?

Le fpu a son propre jeu d'instruction.
Il utilise courrament des registres de 64 bits et + ou - , entiers,reel.....
Donc aucun souci pour additionner deux nombres de 32 bits.
Se munir d'exemples,de la doc et c'est parti.
Il est muni d'une pile (str(0) a str(7)),elle doit etre a zero en fin de calcul
Il offre plusieurs manieres de travailler avec des nombres (MMX mode).
Un utilitaire ,écrit par moi,est fort utile pour la mise au point (code source).

[edfed]

j'ai recement (re)decouvert un sujet très interressant sur les divisions par multiplication de la reciproque.

j'en profite donc pour poster le lien vers cette discussion (en anglais)

il est question des nombre P-adic, avec une explication assez claire sur les particularités de ces nombres, entre autres, les 2-adic.

les chercheurs matheux trouverons le temps et l'interet d'approfondir.

Mais ce qu'il faut retenir, c'est que si l'on multiplie par la reciproque du diviseur, on recupere le resultat de la division.
et que la reciproque se calcule comme ça:
reciproque = ( MAX register value / YOUR VALUE ) + 1
cela ne fonctionne que pour les nombre positifs et non signés.

[ToutEnMasm]

reciproque = ( MAX register value / YOUR VALUE ) + 1

Si avec le FPU il n'est pas difficile de trouver le réciproque 1/N ou N est le diviseur, j'avoue avoir du mal à trouver le réciproque pour des registres de 32.

Exemple : diviser 3000 / 20

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
mov edx,0
mov ecx,20
mov eax,3000
div ecx

et on a le résultat, maintenant avec le réciproque :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
mov edx,0
mov ecx,????????  ;
mov eax,3000
mul ecx

Si je pouvais remplacer le ???????? par le réciproque avec explication de son mode de calcul,ça serait au poil.

[edfed]

mov ecx,(FFFFFFFFh/30)+1

[ToutEnMasm]

J'ai deux valeurs 3000 et 20

mov ecx,(FFFFFFFFh/30)+1

Le 30 est-il une erreur ? sinon d'ou sort-il ?

[ToutEnMasm]

après essai ni 20 ni 30

mov edx,0
mov ecx,20
mov eax,400
div ecx ;correct 14h dns eax
mov edx,0
mov ecx,(0FFFFFFFFh/30)+1
mov eax,400
mul ecx
;eax 50h pour 20, out avec 30

[ToutEnMasm]

Solution:

;division normale
mov edx,0
mov ecx,20
mov eax,400
div ecx
mov edx,0
;----- en utilisant la calculatrice windows -----------
;FFFFFFFF/20=214748364,75 on suprime les chiffres après la ,
;on ajoute 1 = 214748365
mov ecx,214748365
mov eax,400
mul ecx
------- résultat dans edx 14h correct ---------------