Chapitre 95 : Assembleur ARM 32bits : calculs en multiprécision

 

Dans ce chapitre, je me suis lancé dans l’écriture de routines de calcul avec un grand nombre de chiffres. Il existe des librairies pour effectuer ce genre de calcul comme gmp et que j’ai déjà utilisée.

Mais ici, l’intérêt est de comprendre le fonctionnement des routines et la possibilité de les modifier ou d’en écrire des nouvelles plus optimisées ou plus utiles directement en assembleur.

Ces routines posent aussi des problèmes intéressants et la version proposée ici est la dernière après de nombreux essais et évolutions.

Tout d’abord, il faut choisir une structure de représentation de ces grands nombres. J’ai décidé d’écrire une structure qui contient le nombre d’entiers de 32 bits qui composent un nombre, le signe du nombre par un entier de 32 bits puis la table des entiers qui seront appelés des chunks par la suite. Cette table aura un nombre maximum de chunks donnée par la constante NBCHUNKMAXI.

Voici la description de la structure :

/* Définition pour multiEntier */

.struct 0

multi_taille: // nombre de chunk

.struct multi_taille + 4

multi_signe: // signe 0 positif, -1 négatif

.struct multi_signe + 4

multi_chunk: // debut des chunks

.struct multi_chunk + 4 * NBCHUNKMAXI // nombre de chunks maxi

multi_fin:

Ainsi le nombre 4294967297 (soit 0x100000001) est représenté par 2,0,1,1 car il contient 2 chunks, est positif Le premier chunk vaut 1 et le deuxième vaut aussi 1 mais il représente la valeur 1 * 2 puissance 32 soit 4294967296

Le nombre 1 sera représenté par 1,-1,1 soit un chunk de signe négatif et de valeur 1.

Pour simplifier la gestion de la mémoire, tous les nombres utilisés devront être déclarés avant leur utilisation. Les nombres utilisés en interne dans les routines seront déclarés sur la pile.

Vous trouverez les fichiers nécessaires à la compilation et au lien dans le répertoire :

https://github.com/vincentARM/Arm-assembly/tree/master/Chapitre95

Les routines se trouvent dans le fichier utilCalcul.s et un exemple de calcul dans le fichier testCalcul.s. la compilation s’effectue en saisissant make PGM=testcalcul, le résultat se trouvera dans le répertoire build.

Attention : il peut rester des anomalies dans ces routines car j’ai pu oublier des cas de tests. (me signaler éventuellement les cas d’erreurs pour correction)

La première routine est celle qui permet d’initialiser un nombre avant son utilisation : initMultiEntier. Elle attend en paramètre l’adresse d’une zone réservée et le nombre de chunks qui seront initialisés à zéro. Ce nombre alimentera la zone multi_taille, la zone multi_signe sera mise à 0, et une boucle initialisera les chunks à partir de l’adresse multi_chunk.

Nous retrouverons ce type de boucle dans presque toutes les routines puisqu’il faudra traiter tous les chunks d’un nombre.

Pour tester cette sousroutine dans le programme testcalcul, il nous faut avoir une routine d’affichage de ce type de nombre. Celle ci fait appel à une routine de conversion d’un nombre en une chaîne de caractères : convertirMultiVersChaine qui fait appel à d’autres sous routines (voir les commentaires pour les explications).

Ensuite nous trouvons les sousroutines pour initialiser un grand nombre à partir d’un entier, ou à partir d’une chaîne de caractères.

Enfin nous trouvons les routines d’addition de soustraction de multiplication et de division. A partir de ces routines, il est possible de les compléter pour effectuer d’autres calculs (puissance,modulo etc.)

Vous trouverez des exemples d’utilisation des routines principales dans le programme testCalcul.s

Chapitre 94 : Blockchain suite : gestion des clés publique et privée avec la librairie openssl

 

Dans le chapitre précédent, nous avons vu la création des clés publique et privée avec openssl dans le source portefeuille.s. Mais si nous voulons avoir des portefeuilles indépendants, il est nécessaire de pouvoir sauvegarder les clés sur des fichiers.

Dans les fonctions de openssl, il existe bien des fonctions pour sauvegarder les clés mais elles font appel à des fichiers adaptés au langage C et pas aux fichiers gérés directement par les appels système de Linux.

Heureusement, en cherchant dans le fouillis des fonctions proposées par openssl, j’ai trouvé des fonctions qui recopient les clés dans des zones mémoire que nous pouvons exploitées pour les sauvegarder sur des fichiers.

Dans le répertoire suivant sur github :

https://github.com/vincentARM/ARMassembly64/tree/master/projet64_014

vous trouverez plusieurs programmes pour gérer les clés, signer, vérifier, chiffrer et déchiffrer un fichier.

Dans le premier programme genkey64.s nous retrouvons la fonction de génération des clés que nous avons utilisée pour la blockchain. Cette fonction appelle les fonctions d’openssl qui créent les clés dans des structures internes.

Puis nous trouvons 2 fonctions qui vont écrire les clés sur les fichiers. Dans la fonction ecrireClePublique, nous créons d’abord une entité BIO et grâce à la fonction openssl PEM_write_bio_PUBKEY nous transférons la clé publique dans cette entité puis avec la fonction BIO_read nous transférons la clé dans un buffer sous le format standard de clé publique. Il ne nous reste plus qu’à écrire le buffer sur le fichier avec les appels système Linux 64 bits.

La fonction ecrireClePrivée effectue les mêmes opérations mais en utilisant la fonction PEM_write_bio_PrivateKey qui nécessite en plus le passage dans les paramètres d’une phrase de mot de passe (pass phrase)qui va permettre de chiffre la clé privée avant son écriture sur le fichier.

Cette phrase sera redemandée à chaque utilisation de la clé privée, ce qui assure sa confidentialité.

Dans le programme traiket64.s nous trouvons les fonctions pour relire les clés des fichiers et alimenter les structures BIO puis les structures internes d’openssl.

Mais la question qui se pose maintenant est celle de savoir si ces opérations sont correctes et si les clés sont utilisables.

Pour cela dans les programmes signerFichier64.s et verifierSign64.s, nous allons utiliser les fonctions de signature et de vérification utilisée pour la blockchain.

Dans le programme signerFichier64, nous allons utiliser le fichier de clé privée pour extraire la clé, signer un petit fichier texte, et générer la signature.

Puis dans le programme verifierSign64.s, nous allons utiliser le fichier de clé publique pour extraire la clé et l’utiliser pour vérifier la signature.

Tout fonctionne parfaitement !!!

Les 2 derniers programmes chiffrerFichier64.s et dechiffrerFichier64.s montre l’utilisation des clés pour chiffrer et déchiffrer un fichier texte. Je me suis servi des exemples en langage C d’openssl pour écrire ces programmes en assembleur.

Il y a donc une bizarrerie car le chiffrage exige l’utilisation d’une clé secondaire et d’une entité appelée IV qui doivent être passées au programme de déchiffrement. Normalement dans le cas d’un chiffrement asymétrique seules les clés publiques et privées devraient être utilisées. Ce point reste à éclaircir !!

Les programmes fonctionnent correctement.

Chapitre 93 : création d"une blockchain en assembleur ARM 64 bits

 

En parcourant les divers forums sur internet, je trouve une proposition de développer un exemple de blockchain dans divers langages .

Bon dans mon inconscience je décide de voir ce que cela peut donner en assembleur. Après quelques recherches je découvre le site suivant qui propose un exemple en Java :

https://medium.com/programmers-blockchain/create-simple-blockchain-java-tutorial-from-scratch-6eeed3cb03fa

Je vais donc m’en inspirer pour créer ma propre blockchain locale. En effet pour cette première approche il n’est pas question d’écrire toute la partie distribuée du fonctionnement d’une blockchain. L’exemple propose la création des blocs, des portefeuilles, et des transactions ainsi que la vérification complète de la blockchain créée.

Le projet complet se trouve dans github à cette adresse :

https://github.com/vincentARM/ARMassembly64/tree/master/projet64_013

Le programme source blockchain1.s contient le programme maître, les routines de création de bloc, d’ajout d’un bloc dans la blockchain, d’ajout d’une transaction et la vérification complète de la blockchain.

Le programme effectue les initialisations, la création des portefeuilles, la création de la première transaction qui effectue un virement de 100 totos puis la création des blocs et des transactions des virements entre les portefeuilles.

La blockchain est une double liste chaînée, ce qui permet l’insertion d’un bloc à la fin de la chaîne sans avoir à balayer toute la liste.

Un bloc contient le hash du bloc précédent, son propre hash, un timestamp fourni par un appel système linux et diverses informations.

Le calcul et l’affichage des hash sont effectués par des routines du programme sha256_64.s écrites en assembleur. J’avais écrit ce programme pour une autre utilisation.

Les blocs sont crées sur le tas et ne peuvent pas être sauvegardés dans cet exemple. Le minage d’un bloc consiste à calculer un hash avec des zéros en tête. Plus on veut de zéros et plus c’est long à miner. Ici la routine se limite à vérifier la présence des 8 premiers zéros mais déjà le minage à 5 zéros dure un certain temps !! (constante DIFFICULTE à adapter dans le fichier constantesARM64.inc).

Le programme portefeuille.s contient les routines pour créer les portefeuilles, créer les clés publiques et privées, calculer le solde et envoyer des fonds à un autre portefeuille. Remarque : les clés publiques et privées ne sont pas sauvegardées sur un fichier externe !!

Les montants des soldes et virements sont exprimés par des floats de 64 bits (doubles). Leur affichage est effectué par une routine (dans utilFloat.s) différente de grisu et beaucoup plus simple. Merci au site  https://blog.benoitblanchon.fr/lightweight-float-to-string/ pour la présentation de cette solution. Bien sûr l'affichage peut être amélioré pour enlever le E0 derrière les montants !!!

La monnaie s'appelle dans cet exemple : toto !!!!

La génération des clés, la signature d’une transaction, et sa vérification nécessitent l’utilisation de la librairie openssl qu’il faudra donc télécharger et installer sur le raspberry pi. (voir les options du linker dans le makefile ).

Dans le programme transaction.s nous trouvons les routines de création et de gestion des transactions. La routine traiterTransaction est un peu complexe à comprendre mais vous pouvez vous reporter à l’exemple en Java du site cité plus haut.

Voici un exemple d’exécution de ce programme :

 

Début programme.

Init librairie SSL

Init sorties UTXO

création blockchain

création portefeuille 1

création portefeuille 2

création portefeuille depart

création transaction départ

Calcul signature TX départ

Création tx sortie départ

Ajout TX dans liste et hashmap

Création bloc 0

Ajout TX origine au bloc 0

Ajout bloc 0 à la blockchain

creation bloc 1

Solde A

Solde du portefeuille = +100E0 totos

Virement 1

Le solde est OK

Ajout transaction de virement 1

Virement 2

Le solde est OK

Ajout transaction de virement 2

Solde A

Solde du portefeuille = +70,5E0 totos

Solde B

Solde du portefeuille = +29,5E0 totos

Ajout bloc 1 à la blockchain

creation bloc 2

Virement 3

Le solde est OK

Ajout transaction de virement 2

Ajout bloc 2

SOLDE A

Solde du portefeuille = +65,25E0 totos

SOLDE B

Solde du portefeuille = +34,75E0 totos

Verification de la blockchain

La blockchain est valide.

Fin normale du programme.

 

Chapitre 92 : assembleur 32 bits : nouvelle gestion du tas

 

Bon, j’ai fait une énorme erreur dans cette découverte de l’assembleur. En effet j’ai utilisé l’appel système Linux BRK pour gérer l’allocation de place sur le tas lorsque j’avais besoin d’allouer de la place dynamiquement. Or en relisant la documentation de cet appel, je me suis aperçu que cette fonction était faite pour allouer de la place supplémentaire à un processus !!!

Donc j’ai repris l’étude de cette fonctionnalité pour ne plus utiliser BRK. La première idée est de déclarer une zone banalisée de plusieurs milliers d’octets et de gérer cet espace à l’aide d’un pointeur. C’est ce que j’ai fait dans le programme resTas32. Pour être tranquille, il suffit de définir la zone banalisée avec une taille suffisante pour les besoins d’un programme.

L’inconvénient de cette solution est qu’il faut définir cette zone et dupliquer le code pour gérer le tas dans chaque programme.

Une autre idée est d’utiliser l’espace après la fin de la section bss. J’ai testé l’écriture d‘une donnée dans cette partie de la mémoire. Cela fonctionne mais ce n’est pas très propre car cela peut entraîner une interférence si le programme appelle des fonctions de librairies externes car la place utilisée n’est pas référencée.

Enfin une autre solution que j’ai adoptée, c’est de déclarer une zone tas lors de l’édition du lien. Cette zone mémoire sera réservée en fin de la section bss. Pour cela il faut créer un script ld qui sera appelé par le linker :

Voici son contenu :

SECTIONS

{

PROVIDE(__executable_start = 0x0010000);

. = 0x00010000 + SIZEOF_HEADERS;

.interp : { *(.interp) }

.note.ABI-tag : { *(.note.ABI-tag) }

.hash : { *(.hash) }

.dynsym : { *(.dynsym) }

.dynstr : { *(.dynstr) }

.version : { *(.version) }

.version_d : { *(.version_d) }

.version_r : { *(.version_r) }

.rel.dyn : { *(.rel.dyn) }

.rela.dyn : { *(.rela.dyn) }

.rel.plt : { *(.rel.plt) }

.rela.plt : { *(.rela.plt) }

.init : { KEEP (*(.init)) }

.plt : { *(.plt) }

.text : { *(.text .text.*) }

.fini : { KEEP (*(.fini)) }

PROVIDE(__etext = .);

PROVIDE(_etext = .);

PROVIDE(etext = .);

.rodata : { *(.rodata .rodata.*) }

__exidx_start = .;

.ARM.exidx : { *(.ARM.exidx*) }

__exidx_end = .;

. = ALIGN (CONSTANT (MAXPAGESIZE)) - ((CONSTANT (MAXPAGESIZE) - .) & (CONSTANT (MAXPAGESIZE) - 1));

. = DATA_SEGMENT_ALIGN (CONSTANT (MAXPAGESIZE), CONSTANT (COMMONPAGESIZE));

.tdata : { *(.tdata .tdata.*) }

.tbss : { *(.tbss .tbss.*) }

.preinit_array :

{

PROVIDE_HIDDEN (__preinit_array_start = .);

KEEP (*(.preinit_array))

PROVIDE_HIDDEN (__preinit_array_end = .);

}

.init_array :

{

PROVIDE_HIDDEN (__init_array_start = .);

KEEP (*(.init_array*))

PROVIDE_HIDDEN (__init_array_end = .);

}

.fini_array :

{

PROVIDE_HIDDEN (__fini_array_start = .);

KEEP (*(.fini_array*))

PROVIDE_HIDDEN (__fini_array_end = .);

}

.dynamic : { *(.dynamic) }

.got : { *(.got.plt) *(.got) }

.data :

{

__data_start = 0x20000;

*(.data .data.*)

}

_edata = .;

PROVIDE(edata = .);

__bss_start = .;

__bss_start__ = .;

.bss :

{

*(.bss .bss.*)

. = ALIGN(. != 0 ? 32 / 8 : 1);

}

__bss_end__ = .;

_bss_end__ = .;

.heap (NOLOAD):

{

TAILLETAS = DEFINED(TAILLETAS) ? TAILLETAS : 0x20000 ;

. = ALIGN(8);

heap_begin = .;

. = . + TAILLETAS;

. = ALIGN(8);

heap_end = .;

}

. = ALIGN(4);

__end = .;

_end = .;

PROVIDE(end = .);

}

 

Vous remarquerez que j’utilise une instruction pour définir la taille du tas par défaut si celle çi n’est pas définie par un programme utilisateur. Attention dans le programme utilisateur il faudra aussi indiquer que le symbole TAILLETAS est global.

Le script est appelé par le linker avec l’option -T ~/scripts/linkerldarm.ld.

Voir son utilisation dans le programme : verifTas32.s

Dans ce programme, nous faisons appel à des routines regroupées dans le fichier routinesARM2021.s. Nous trouvons une routine pour réserver la place sur le tas, une routine pour libérer la place et une routine d’insertion d’une chaîne de caractères dans une autre chaîne.

La routine pour libérer la place doit être utilisée à bon escient. En effet ici, il n’est possible de libérer de la place que dans l’ordre inverse de la réservation si nous voulons réutiliser la place.

Il ne reste plus qu'à adapter cette solution pour le 64 bits.

Chapitre 91: assembleur ARM 64 bits : tests de différents tris fusion

 

J’avais besoin d’un tri stable et qui reste assez rapide car le tri par insertion est stable mais pas très performant. J’ai donc recherché d’autres tris stables et j’ai donc testé plusieurs exemples de tri fusion.

Le premier algorithme est issu du site rosetta code et je l’ai intégré dans un programme qui génère une table de nombres aléatoires, qui effectue les mesures de performance comme vues au chapitre 87, ce qui permet la comparaison de plusieurs tris.

Dans le programme testMergeTri64.s, nous trouvons la génération de la table, sa copie, l’appel aux mesures et l’appel à chaque tri. Le premier tri est un tri shell qui servira de comparaison. Le deuxième est le tri de rosetta code.

Voici les résultats pour trier 1000 valeurs numériques :

Tri shell

instructions: 178676 Cycles: 195663 temps en µs: 365573 temps1: 358906

tri merge

instructions: 2074928 Cycles: 2150297 temps en µs: 3740209 temps1: 3738177

Ce dernier tri n’est donc pas du tout performant. Je recherche donc d’autres algorithme dont celui de Robert Sedgewick en langage C que j’adapte à l’assembleur :

Nouveau tri merge :

instructions: 257280 Cycles: 313895 temps en µs: 612135 temps1: 609896

ce qui est mieux !! mais attention ce tri utilise une table annexe ce qui peut poser un problème de place.

J’améliore ce tri en effectuant les opérations de manière itérative :

instructions: 214244 Cycles: 253779 temps en µs: 456458 temps1: 451771

Puis il me vient l’idée d’effectuer le premier passage qui compare 2 valeurs successives sans utiliser le stockage dans la table intermédiaire puisque dans ce cas il suffit de stocker les 2 valeurs à intervertir dans seulement 2 registres :

instructions: 179335 Cycles: 230524 temps en µs: 405052 temps1: 401042

Voyons pour 100000 valeurs

tri shell :

instructions: 37658720 Cycles: 42019684 temps en µs: 73245522 temps1: 73231616

tri merge 1

instructions: 20051919690 Cycles: 20112824889 temps en µs: 30899260563 temps1: 30899177076

C’est énorme

tri merge

instructions: 40135342 Cycles: 46668064 temps en µs: 83594376 temps1: 83597240

tri merge itératif :

instructions: 35420192 Cycles: 44364228 temps en µs: 77672919 temps1: 77622968

autre tri merge itératif :

instructions: 31226666 Cycles: 41760383 temps en µs: 72490157 temps1: 72477969

La différence est nette pour ce dernier tri.

Avec ces derniers tests itératifs, il est possible d’utiliser la pile pour stocker la table intermédiaire.

Maintenant il faut vérifier la stabilité de ces tris (sauf le shell qui n’est pas stable). Pour cela dans le programme testMergeTri64Multi.s je crée une structure avec 2 zones dont une est alphanumérique pour tester le tri sur zone alpha.

J’adapte les tris pour effectuer les comparaisons suivant le choix alpha ou numérique.

L’affichage du début de la table triée pour chaque tri montre la même séquence pour les 3 tris fusion et un écart pour le tri shell. Ce qui semble être bon.

J’ai refait un test sur un programme légèrement modifié : au lieu de générer des valeurs numériques aléatoires, je stocke directement le compteur. Ensuite en triant sur les chaînes, il suffit de vérifier que l’ordre des valeurs numériques est croissant pour les chaînes identiques.

Évidemment les temps sont supérieurs à ceux du premier programme ce qui est normal puisque la comparaison s’effectue sur des chaînes de plusieurs caractères.

Chapitre 90 : assembleur ARM 32 bits : affichage des nombres en virgule flottante : algorithme grisu et grisu 2

 

Suite à l’écriture de la routine d’affichage pour l’assembleur 64 bits, je me suis penché à nouveau sur la routine pour le 32 bits que j’avais écrit au chapitre 11 au tout début de ma découverte de l’assembleur ARM. Bon c’est pas très joli joli : la routine est fausse et les résultats ne sont pas très bons. Je suis donc repartit du document pdf de Florian Loitsch (voir : https://www.cs.tufts.edu/~nr/cs257/archive/florian-loitsch/printf.pdf ) et de la transposition en 64 bits que j’ai faite au chapitre 88 pour essayer de réécrire ces algorithmes pour le 32 bits.

Dans le programme convertFloat32.s, j’ai donc transposé l’algorithme grisu. Cela pose quelques difficultés car les nombres en virgule flottante traités sont en double précision et donc nécessitent une zone de 64 bits pour stocker la mantisse et les opérations doivent donc s’effectuer avec 2 registres . L’exposant lui peut être stocké sur 32 bits. De plus en 32 bits, le nombre de registres est limité (13) et donc il faut jongler avec pour arriver à tout calculer.

Dans ce premier programme, je reprends la trame de l’algorithme : conversion du nombre contenu dans le registre d0, normalisation, calcul du coefficient K pour accéder à la table des puissances de 10.

A ce propos, en découvrant sur github, cette méthode écrite pour d’autres langages (C,c++, java), j’ai constaté une différence entre les valeurs de ma table et celles publiées pour les mêmes puissance de 10. Je pense que mes valeurs sont calculées avec une moindre précision que les valeurs publiées.

La multiplication de 2 nombres codés suivant la structure proposée m’a posé quelques difficultés surtout dans le report des retenues.

J’ai gardé le découpage du résultat en 3 zones comme proposé mais l’affichage n’est pas satisfaisant : en utilisant la routine de conversion habituelle y a affichage de caractères blancs avant les chiffres du résultat.

Le résultat affiché est juste jusqu’à 17 chiffres et les valeurs suivantes sont fausses.

Dans le deuxième programme convertFloat32G2V2.s, je programme l’algorithme grisu 2 avec une table réduite par pas de 8 et une table reconstituée à partir d’une trouvée sur Internet.

Les principales difficultés sont de bien gérer les déplacements gauche et droite de bits sur 2 registres 32 bits. Dans la sous routine genererChiffres, pour pouvoir effectuer les calculs sans avoir à sauvegarder des valeurs en mémoire, je stocke certains registres dans les registres s0,s1,s2,et s3 . On gagne pas grand-chose car pour une routine utilisable par d’autres programmes et pour éviter tout problème, il faut sauvegarder quand même ces registres en début de routine et les restaurer en fin.

Pour le formatage, du résultat final, j’ai fait assez simple soit l’exposant est à zéro et j’affiche tous les chiffres disponibles et si l’exposant est différent de zéro, j’affiche le résultat sous la forme nombreEexposant. Il est donc possible d’améliorer cet affichage pour produire d’autres formats.

La routine donne des résultats satisfaisant avec toujours au maximum 17 chiffres significatifs. Reste à savoir si elle est toujours exacte !!!!

Chapitre 89 : Assembleur ARM 64 : routine calcul inverse racine carrée rapide pour des nombres en virgule flottante

 

En recherchant des algorithmes pour le chapitre précédent, je suis tombé sur une routine pour calculer la racine carrée inverse d’un nombre.Elle va nous permettre de tester la conversion de la routine grisu2 précédente en module.

Pour cela j’ai supprimé tout ce qui était inutile dans le programme grisu2NV2_64.s et je l’ai renommé routConvFloat64.s. J’ai ensuite compilé ce programme pour créer un objet.

Ensuite dans le programme calculinvRac, j’ai écrit la routine de calcul telle qu’elle est exposée dans Wikipedia et je l’ai compilé puis linké avec l’objet précédent.

Voici le résultat pour le nombre donnée en exemple dans Wikipedia :

2.529810967007374 (la valeur exacte est 2,52982)

et pour 4 :

0.4999978544248724 (la valeur exacte est 0,5

Il n’est donc plus nécessaire de faire appel à l’instruction printf du C pour afficher les nombres en virgule flottante.

C’est tout pour aujourd’hui !!!