Nombres d'Armstrong et Assembleur

**Antacid** · 09/12/2002, 21h44

Bonjour à tous. Je suis à même de me tapper un cours de structureinterne et, en cette magnifique fin de session, mon très peu gentil professeur nous a soumis le devoir suivant:

http://mdbui2.ift.ulaval.ca/devoirs/Dev2_sio_aut2002.htm

La première partie est simpliste, mais moi et mes coéquipiers sommes perplexes face à la partie assembleur. Nous sommes relativement capable de produire un algorithme capable de faire focntionner tout ca. Notre problème réside dans la partie codage. Je vais vous expliquer notre facon de voir les choses... Puisque des nombres supérieurs à puissance 10 avec les types dont nous disposons en C, nous devrons concatèner des 32 bits en ASM à l'aide d'un tableau que nous déclarerons en C. Prenons quatre mots à 32 bits A B X et Y qui forment (AB) 64bits et XY 64 bits. Pour former le 128 nous multiplierons AB et XY. que nous fouterons ensuite dans un tableau.

Ce foutu exercice nous fou les boules et je suis sur le point de lâcher le BAC en informatique pour génie nutritionnel. aidez-moi avant que le pire n'arrive.

**golem** · 10/12/2002, 12h28

Salut,

Voilà ce que je viens de pondre, j'espère que ça répond à la question pour la multiplication de deux entiers 64 bits. L'algo est une multiplication comme on la ferait à la main; je ne connais pas d'autres algo, il en existe surement. J'ai utilisé au maximum les registres mais il y a surement moyen d'optimiser largement plus. Ca tourne sous VC++ (testé sous version 5.0). Ca a l'air de marcher, ya peut etre des valeurs aux limites qui m'ont échappées. A voir. Si tu veux plus d'explications, dis le moi. Le meilleur moyen de comprendre est de le faire tourner pas à pas.

golem
+++

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
 
typedef struct {
	unsigned H, L;
} type64;
 
typedef struct {
	unsigned H, mH, mL, L;
} type128;
 
void mul128( type64 *op1, type64 *op2, type128 *result)
{
	__asm
	{
		push esi				// esi et edi doivent etre sauvés
		push edi				// les registres e?x peuvent etre librement modifiés
 
		mov esi,op1				// esi et edi pointent sur les deux opérandes
		mov edi,op2
 
		mov eax,[esi]type64.L	// poids faible du premier opérande
		mov ebx,[edi]type64.L	// poids faible du deuxième opérande
		mul ebx					// le poids faible (EAX) de la première multiplication...
		push eax				// ...est le poids faible du résultat final, on le stocke sur la pile
		mov ecx,edx				// sauve le poids fort de la première mult. dans ecx
		mov eax,[esi]type64.H	// poids fort premier opérande dans eax
		mul ebx
		add eax,ecx
		adc edx,0
		push eax				// la première ligne de la mult. est complètement stockée dans la pile
		push edx				//
		mov ebx,[edi]type64.H	// poids fort du deuxième opérande
		mov eax,[esi]type64.L	// poids faible premier opérande
		mul ebx
		mov ecx,edx				// sauve le poids fort dans ecx (comme précédemment)
		mov edi,eax				// on n'utilisera plus la dexième opérande jusqu'à la fin, on peut l'utiliser
		mov eax,[esi]type64.H	// poids fort premier opérande
		mul ebx
		add eax,ecx
		adc edx,0
		pop ebx					// restaure la première ligne
		pop ecx
		add ecx,edi				// effectue les sommes partielles
		adc eax,ebx
		adc edx,0
		mov edi,result			// edi pointe sur la struture résultat
		pop [edi]type128.L		// récupère le poids faible du résultat depuis la pile
		mov [edi]type128.mL,ecx
		mov [edi]type128.mH,eax
		mov [edi]type128.H,edx
 
		pop edi
		pop esi
	}
};
 
int main()
{
	type64 a, b;
	type128 r;
 
	a.H=0xFFFFFFFF;
	a.L=0xFFFFFFFF;
	b.H=0xEEEEEEEE;
	b.L=0xEEEEEEEE;
 
	mul128(&a, &b, &r);
	printf("%08X%08X * %08X%08X = %08X%08X%08X%08X\r\n", a.H, a.L, b.H, b.L, r.H, r.mH, r.mL, r.L);
 
	return 0;
};

**Blustuff** · 10/12/2002, 12h41

C'est quoi la question exactement ?

Si j'azi bien compris :

Resultat = (X + Y * 2^32) * (A + B * 2^32)

Admettons que resultat sur 128 soit composé de quatre nombres 32bits d1, d2, d3, d4 tels que

Resultat = d1 + d2 * 2^32 + d3 * 2^64 + d4 * 2^96

En asembleur les multiplications sont très bien faites, puisque en multipliant deux entier 32 bits, par ex

eax * edx

on ontiens non pas un 32bits mais un nombre 64 bits contenu dans edx:eax. Donc il faut décomposer la multiplications en multiplications 32 bits par 32 bits :

Resultat = (X + Y * 2^32) * (A + B * 2^32) = (X * A) + (Y * A + B * X) * 2^32 + (Y*B) * 2^64

Ou on a que des multiplciations 32 bits.

Concretement :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
mov eax, X
mov edx, A
mul edx  ;X * A
mov d1, eax
mov ebx, edx
 
mov eax, Y
mov edx, A
mul edx ;Y * A
add ebx, eax
mov ecx, edx
adc ecx, 0 ;Au cas ou ebx + eax > 2^32 - 1
 
mov eax, B
mov edx, X
mol edx ; B * X
add ebx, eax
adc ecx, 0
mov d2, ebx
xor ebx, ebx
add ecx, edx
adc ebx, 0
 
mov eax, Y
mov edx, B
mul edx ; Y * B
add ecx, eax
adc ebx, 0
add ebx, edx
mov d3, ecx
mov d4, ebx

Donc theoriquement ca donne le resultat sur 128 bits d'une multiplication 64 * 64 bits. (A verifier, je peux pas la verifier tout de suite).
Il y a certainement des optimisations a faire au niveau de l'utilisation des registres. Cela dit j'ai déja répondu a des questions sur les nombtres d'armstrong (L'exemple c++ qu'on vus a donné est pas terrible, il est pas loin de 20 fois trop lent)

Blustuff.

**Antacid** · 10/12/2002, 19h03

Notre magnifique prof nous a envoyé une piste.. en effet il nous a soumis le code qui travaille en 32 bits, ne nous reste qu'a le modifier pour qu'il puisse travailler en 64.

La vitesse de traitement est de loin plus rapide que le code C++ de départ. Alors que le C++ se traitait en 10 minutes, celui-ci s'effectue en 3 environ.

http://mdbui2.ift.ulaval.ca/tmp/E20_1/armstrong1.cpp

j'hésite a le copier sur cette page car le code en possede presque 3..!

moi et mes coéquipiers s'obstinons, au départ, sur le type de tableau a utiliser. Devrions nous utiliser des tableaux parrallèles pour stocker 2 nombres à 32 bits qui forment un 64?

Il nous a dit aussi qu'il y aurait une amélioration a apporter pour que le traitement s'effectue en 1.30 minute.. Mais comme nous avons commencé l'ASM que depuis 3 semaines il nous est diffcile de voir du premier coup d'oeil.

Ce code, pour des débutant, est d'une complexité monstre, n'est-ce pas?

Et dire que 50% de notre futur examen portera là-dessus, de quoi faire peur.

Merci à vous.

**Blustuff** · 11/12/2002, 00h00

Faut le voulopir pour le lire ce code. Si ca prends 10 min en C alors que ca prends que 3 en asm c'est que c'est mal ecrit en C. Faut pas esperer gagner plus ded 10 % de vitesse (ca arrive mais c'est rare) Quelqu'un d'autre m'a demandé la traduction d'un code C++ vers asm.

Y'a plusieures optimiosations a effectuer :

- Supprimer une bonne quatitée de push, pop et call qui sont inuriles. (Dans ce programme aucun call n'est indispensable).

- Votre tableau powerofdigit (quelle horreur ces noms de variables en anglais, je croyais qu'on était pas encore absorbés par microsoft) est constitué de lignes de 40 octets. Etendez les lignes à 64 octets. Vous aurez 6 entiers certes inutiles, mais vous pourrez remplacer la multiplication par 40 par un decalage de 6 bits vers la droite ce qui peut etree j'usqu'a 40 fois plus rapide.

- Utiliser le BCD. On peut dans un entier 32 bits stocker 8 chiffres en BCD. Avec des entiers 64 bits vous pourrez calculer jusqu'a l'ordre 16 (c'est peut etre suffisant non ?). Cette reduction dee taille permetra notement d'utiliser dees registres processeurs plutot qu'utiliser la pile comme des tarés (c'est les echange avec la mémoire qui vont limiter la vitesse de votre prog ensuite)

**Blustuff** · 11/12/2002, 00h57

Vous pouvez vous servir de ca si vous voulez :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
 
#include <iostream.h>
 
//Declarations dans le segment de donnéees pour optimisation
unsigned long Puissances[256];      //16 au lieu de 10 pour optimisations
unsigned char Chiffres[10];
 
/*
Note : le tableau des puissances est organisé par lignes de 64 octets. Chaque
ligne représente un exposant, la ligne 0 est l'esposant 0. Chaque colonne compte
4 octets, et chaque colonne représente le chiffre que l'on veut élever a la
puissance n
*/
 
 
void main()
{
  //---- Precalcul des puissances : ----
 
  //Repeter pour chaque chiffre a partir de 1 (pour exposant 0 le segment de donnees et déja initialisé à 0 - ecx = chiffre courant)
  asm mov ecx, 1
 
  BoucleNombre:
    //Demaraer a ebx = 64 (ebx = Exposant en cours * 4)
    asm mov ebx, 64
 
    //n ^ 1 = n
    asm mov eax, ecx
    asm mov Puissances[ecx*4], eax
 
    //Repeter pour chaque exposant
    BoucleExposant:
      //Multiplier la valeur précédente par le nombre en cours et la stocker
      asm mul ecx
      asm mov Puissances[ecx*4+ebx], eax
 
    asm add ebx, 64
    asm cmp ebx, 1024
    asm jne BoucleExposant
 
  asm inc ecx
  asm cmp ecx, 10
  asm jne BoucleNombre
 
 
  //---- Affichage d'information ----
 
  cout << "Recherche des nombres d'Armstrong jusqu'a l'ordre 9\n\n";
 
 
  //---- Recherche des nombres d'Armstrong ----
 
  for (int Ordre = 1 ; Ordre <= 9 ; Ordre++)
  {
    unsigned long i = 0 ;
 
    cout << "Ordre ............. " << Ordre << "\n\n";
 
    //Initialisation des Chiffres
    asm mov ecx, 8
    InitialisationChiffres:
      asm mov Chiffres[ecx], 0
    asm dec ecx
    asm jns InitialisationChiffres
 
    //eax = 0
    asm xor eax, eax
 
    //(ecx = (Ordre - 1) * 64)
    asm mov ecx, Ordre
    asm dec ecx
    asm shl ecx, 6
 
    Boucle1:
 
      //esi = 0
      asm xor esi, esi
 
      //Pour edi allant de Ordre - 1 à 0 inclu (Pour chaque chiffre)
      asm mov edi, Ordre
      asm dec edi
 
      Boucle:
        //eax = Chiffre
        asm mov al, BYTE PTR Chiffres[edi]
 
        //Resultat += eax^ecx
        asm add esi, Puissances[eax*4+ecx]
 
        //Fin de la boucle. Decrementer edi et verifier si il faut sortir
        asm dec edi
        asm jns Boucle
 
      //Recuperer le resultat
      asm cmp esi, i
      asm jne Incrementation
 
        asm push eax
        asm push ecx
 
        cout << i << " ";
 
        asm pop ecx
        asm pop eax
 
 
      //Incrementaion des chiffres
      Incrementation:
      asm inc i
      asm inc Chiffres
      asm cmp BYTE PTR Chiffres, 0Ah
      asm jne Boucle1
      asm mov edx, 1
      IncrementerChiffres:
        asm add WORD PTR Chiffres[edx-1], 0F6h
        asm cmp BYTE PTR Chiffres[edx], 0Ah
        asm jne Boucle1
        asm inc edx
        asm cmp edx, Ordre
        asm jb IncrementerChiffres:
 
    cout << "\n\n";
  }
}

Notes :

- Si vous pouvez pas compiler rempalcez les asm par des blocs de __asm{} moi c'était pour mon compilateur.

- J'ai gardé quelques bouts de C++ et des alinéas du C++ pour la lisibilité.

Blustuff.

**Antacid** · 11/12/2002, 04h38

Merci beaucoup! ca semble plus rapide! mais le hic c'est que l'objet principal du travail est de pouvoir calculer des nombres comprenant plus de 9 digits.. je vais essayer de voir si je peux le faire tout de même! merci encore!!

**Blustuff** · 11/12/2002, 11h06

Ce que j'ai ecrit est déja prévu pour l'extension 64 bits. J'ai reservé edi et edi, esi et eax. (Sachant que je reserve juste eax pour que les 24 bits de poids fort restes nuls donc on peut liberer facilement eax, en rajoutant un xor eax, eax. C'est vrai j'ai pas été très malin sur le choix des registres. Mais on pourrait imaginer

edi:esi pour contenir la somme
edx:ecx pour contenir le nombre, ccours
ebx comme variable muette pour les boucles remplacant edi dans la boucle d'addition des chiffres ^ n et edx dans la boucle d'incrementation des chiffre.

- Ensuite il faut elargir le tableau de chiffres à n+1 ou n est le nombrec de chiffres max. (+1 car j'utilise un add WORD PTR Chiffres[edx-1], 0F6h qui d'une part remet le chiffre edx-1 à 0 mais augmente le chiffre suivant.

-Il faut egalement elargir le tableau de puissances à des entiers 64 bits et donc remplacer le shl ecx, 6 par shl ecx, 7. Et egalement modifier la fonction de calcul de puissance. Les multiplications en asm comme je l'ai dit dans un message precedent sont 32*32 = 64 bits. La tu vas avoir une multiplication 32*64 = 64bits. donc deux multiplications et une addition.

- Puis convertir les additions 32 bits en additions 64 bits. Tu as adc qui est prévu en autres pour ca. De la même manière utiliser adc après inc.

C'est pas très long finalement.

Blustuff.

**noox** · 18/12/2002, 13h29

ya pas moyen de faire des choses sur 128 bits avec le mmx ou bien sse , je sais que cest pas lobjectif mais par curiosité .

**Prof Vince** · 02/01/2003, 22h59

on peut gagner une multiplication peut être ?

on calcule xa, yb et (x+y)*(a+b)-xa-yb (seulement 3 mul)

**Blustuff** · 03/01/2003, 01h53

il faudrait que je me remette le truc en tête mais (x + y) tiens sur 33 bits non ? donc ca pose problème, il y a des cas ou il y overflow si le bit 32 de x et de y sont tous les deux 1 par ex.

blustuff.

**Prof Vince** · 03/01/2003, 09h44

exact

ne pourrait t'on pas l'utiliser l'OF comme 33ème bit ?

**Blustuff** · 07/01/2003, 09h47

Sii on peut euh au final ca dezmandera peut etre plus d'instruction en plus que la simple multiplication economisée en prenait.

Blustuff

**Prof Vince** · 07/01/2003, 16h55

ça risque bien malheureusement !

**Blustuff** · 08/01/2003, 11h56

Quoiqu'il en soit, si je me souviens du prog que j'ai fait, il n'y a pas besoin de rapidité pour Qles multiplications 64 bits. Elles sont utilisés au début pour le calcul des puissances mais c'est l'affaire que d'une centaine de multiplications.

Nombres d'Armstrong et Assembleur

Assembleur

Discussions similaires

Partager

Partager