Question:
Comment puis-je inverser la division / modulo d'entiers optimisés par des opérations constantes?
Dougall
2013-03-30 12:14:20 UTC
view on stackexchange narkive permalink

Lors de la compilation d'une division ou d'un modulo par une constante, mon compilateur (LLVM GCC) génère une série d'instructions que je ne comprends pas.

Lorsque je compile les exemples minimaux suivants:

  int mod7 (int x) {return x% 7;} int div7 (int x) {return x / 7;}  

Le code suivant est généré:

  _mod7: push rbp mov rbp, rsp mov ecx, 0x92492493 mov eax, edi imul ecx ajouter edx, edi mov eax, edx shr eax, 0x1f sar edx, 0x2 ajouter edx, eax imul ecx, edx, 0x7 mov eax, edi sub eax, ecx pop rbp ret _div7: push rbp mov rbp, rsp mov ecx, 0x92492493 mov eax, edi imul ecx ajouter edx, edi mov ecx, edx shr ecx, 0x1f sar edx, 0x2 mov eax , edx add eax, ecx pop rbp ret  
  • Comment est-ce mathématiquement équivalent et d'où viennent les constantes?
  • Quelle est la façon la plus simple de tourner l'assemblage en C (pour un des constantes arbitraires sur le côté droit)?
  • Comment un outil, tel qu'un décompilateur ou un désassembleur d'analyse, pourrait-il automatiser ce processus?
Ceci est parfois appelé * multiplication réciproque *. Voici une [brève explication] (http://www.nynaeve.net/?p=115) avec des liens vers des ressources plus détaillées. J'ai vu Hex-Rays digérer cela sans problème.
Trois réponses:
#1
+39
Peter Andersson
2013-03-31 14:26:13 UTC
view on stackexchange narkive permalink

Premier

Malheureusement, nous ne semblons pas avoir activé MathJax dans cet échange de pile, donc les parties mathématiques ci-dessous sont assez horriblement formatées. Je suis également loin d'être un mathématicien donc la notation peut être erronée à certains endroits.

Comprendre le nombre magique et le code

Le but du code ci-dessus est de réécrire une division en une multiplication parce que la division prend plus de cycles d'horloge qu'une multiplication. C'est dans la zone d'environ deux fois plus de cycles, en fonction beaucoup du processeur. Nous devons donc trouver une bonne façon de faire cela sans branche. Si nous branchons, nous risquons fort de perdre en faisant simplement la division.

Une façon est simplement de réaliser que la division est la même chose que la multiplication avec l'inverse du nombre, c'est-à-dire . Le problème est que est un nombre assez médiocre à stocker sous forme d'entier. Nous devons donc multiplier le diviseur et le dividende par un certain nombre. Puisque nous opérons sur des nombres 32 bits et que nous obtenons des résultats de multiplication en nombres 64 bits, nous obtenons la meilleure précision avec et nous évitons également les problèmes de débordement. Donc, nous obtenons essentiellement . Maintenant, cette partie fractionnaire est ce qui nous cause des problèmes car elle provoquera des erreurs d'arrondi.

Alors essayons de formaliser ceci:

est notre multiplicande, par exemple , ou vraiment n'importe quel nombre mais fonctionne très bien avec nos tailles de registre car nous pouvons simplement rejeter le registre 32 bits inférieur. est le nombre que vous devez ajouter pour rendre divisible par . est le nombre que nous souhaitons diviser.

Nous pouvons réécrire l'équation ci-dessus, comme

Ce qui illustre le point que nous avons notre dividende divisé par notre diviseur puis un facteur d'erreur de .

En étudiant notre équation originale de , il est clair que nous pouvons affecter très peu. doit être une puissance de 2, ne peut pas être trop grand ou nous risquons un débordement et ne peut pas être trop petit car il a un effet négatif direct sur notre facteur d'erreur . dépend directement de et .

Alors essayons qui donne une fraction d'erreur maximale de avec la valeur maximale de étant , donc , malheureusement ce n'est pas moins de donc nous pouvons obtenir erreurs d'arrondi.

Nous allons augmenter l'exposant de à , ce qui donne , la fraction d'erreur maximale qui est inférieure à . Cela signifie que notre multiplicande est qui n'est pas inférieur ou égal à la valeur signée maximale que nous pouvons stocker dans un registre 32 bits (). Nous faisons donc plutôt le multiplicande . En remarque, grâce à la magie du complément à deux lorsque nous soustrayons le nombre est qui est lorsqu'il est interprété comme un nombre non signé. Mais nous faisons de l'arithmétique signée ici. Nous devons donc corriger l'expression finale en ajoutant . Cela ne résout également le problème que pour , pour les nombres négatifs, nous serons décalés de 1, nous devons donc ajouter 1 si nous avons un nombre négatif.

C'est l'explication de la constante dans la multiplication et comment y arriver. Regardons maintenant le code:

 ; Charge -1840700269mov ecx, 0x92492493; Chargez nmov eax, edi; n * -1840700269imul ecx; ajouter n pour compenser 2 ^ 32 soustraction add edx, edi; vérifiez le bit de signe de notre resultmov ecx, edxshr ecx, 0x1f; divisez par 2 ^ 2 pour nous compenser en utilisant y = 2 ^ 34 au lieu de 2 ^ 32sar edx, 0x2mov eax, edx; ajoutez la valeur du bit de signe au résultat final add eax, ecx  

Calcul du diviseur à partir du nombre magique et du code

Je n'ai pas prouvé cela mathématiquement, cependant si vous voulez pour récupérer le diviseur d'un vidage d'assemblage tel que celui que vous avez montré, nous pouvons faire de simples exercices mentaux. Nous devons d'abord nous rendre compte que ce qui suit est valable

est l'ajustement que nous avons effectué afin d'amener la valeur dans la plage d'une valeur de 32 bits. À partir du code, nous pouvons concevoir ce qui suit, le décalage à droite de deux moyens que nous avons , , , est inconnu. Cela signifie qu'il nous manque une variable pour effectuer une solution parfaite. Cependant, l'effet de est négligeable car son but est de rapprocher le diviseur le plus possible de sa valeur entière. Cela signifie que la solution peut être trouvée en résolvant

Un autre exemple avec le diviseur 31337 qui a le nombre magique multiplicande 140346763 et décale 10 bits à droite.

Enfin

Pour une analyse mathématique complète de la façon dont cela fonctionne, y compris toutes les preuves et algorithmes appropriés pour calculer le nombres magiques, décalages et ajouts, voir Hacker's Delight, chapitre 10-3.

La question n'était pas seulement de savoir comment calculer les constantes magiques, mais aussi comment récupérer le diviseur.
J'ai essayé d'y répondre. Je n'ai pas vraiment eu le temps de formuler une preuve, donc je ne suis pas sûr à 100% qu'elle soit correcte.
Sous les hypothèses de la rétro-ingénierie (si la division const / modulo par multiplication est confondue avec d'autres opérations), on peut convertir la constante de multiplication entière en une fraction binaire, dont l'inverse est lié à l'opérande de la constante division / modulo jusqu'à une inconnue puissance de 2 facteurs multiplicatifs. Il est parfois impossible de déduire la puissance inconnue de 2 facteurs en raison du mélange et de l'optimisation avec d'autres opérations.
FYI: la réponse semble bonne avec l'application d'échange de pile, car mathjax est activé pour chaque site
#2
+7
John Källén
2016-03-30 23:32:39 UTC
view on stackexchange narkive permalink

Voici une réponse tardive. Le décompilateur Reko récupère les diviseurs entiers en effectuant une recherche de division et de conquête à l'aide de médiants.

Reko commence par reconnaître le modèle où le mot haut d'un Un produit 64 bits ( r * c ) est utilisé. Le multiplicateur constant c est divisé par 2 ^ 32 pour donner un nombre à virgule flottante double précision entre 0,0 et 1,0. En commençant par les nombres rationnels 0/0 et 1/1, Reko calcule une séquence de médianes qui entre crochets le nombre à virgule flottante. À partir de cette séquence de médiants, il choisit le nombre rationnel qui se rapproche le plus du nombre à virgule flottante et le renvoie.

Le code n'est pas encore entièrement testé - je n'ai pas eu l'occasion de travailler avec des nombres négatifs pourtant, pour un, mais semble donner des résultats raisonnables. Le code est ici si vous êtes curieux: https://github.com/uxmal/reko/blob/master/src/Decompiler/Analysis/ConstDivisionImplementedByMultiplication.cs

#3
+1
Sebastian Graf
2017-02-21 16:39:42 UTC
view on stackexchange narkive permalink

Ce document pourrait être intéressant: Division par multiplication invariante.

Je suis tombé sur ceci ici.



Ce Q&R a été automatiquement traduit de la langue anglaise.Le contenu original est disponible sur stackexchange, que nous remercions pour la licence cc by-sa 3.0 sous laquelle il est distribué.
Loading...