Chapitre 80 : assembleur ARM64 : gestion de tables, tri, recherche dichotomique

Au chapitre 71, nous avons commencé à voir les instructions de base pour lire et écrire les données dans un tableau. Dans ce nouveau chapitre, nous allons voir d’autres fonctions pour utiliser un tableau. Le tableau est décrit dans une structure qui ne contient que la clé et une valeur toutes les deux sur 4 octets. Bien sûr, on peut adapter ces 2 zones à d’autres valeurs mais il faudra modifier les instructions ldr et str en conséquence.

Dans ce programme triTable.s, je commence à respecter les normes préconisées pour l’utilisation des registres : x0 à x7 pour les paramètres x8 à x18 pour les données intermédiaires et les autres pour les données à conserver.

Dans le code nous commençons par charger une table de 90 postes avec une clé aléatoire dans la plage 1,50 et une valeur contenant le N0 d’enregistrement.la routine insertionTable se contente de charger la clé et la valeur à l’indice de la table donné par le nombre de poste déjà stockés (si 3 postes stockés, le nouveau stockage s’effectue à l’indice 3 : les 3 premiers étant stockés aux indices 0, 1 et 2) et retourne dans x0 le nouveau nombre de postes. Nous gardons une marge de 10 postes pour pouvoir effectuer des insertions de postes. Comme les zones à charger ont une longueur de 4 octets, il faut faire attention aux instructions en mettant bien les registres de type w et pas les registres de type x. Bien sûr pour les zones de 8 octets, il faudra utiliser les registres en x.

Ensuite nous affichons toute la table en effectuant une boucle puis nous effectuons une recherche sequentielle dans la table et nous affichons le résultat.

Ensuite nous plaçons la routine de tri. C’est un tri Shell issu d’un programme en java proposé par Robert Sedgewick dans son livre sur les algorithmes. C’est un tri moins performant que le tri rapide mais il est plus facile à programmer et il comporte moins de situations défavorables.

Nous affichons à nouveau la table pour vérifier le bon fonctionnement du tri sur les clés et sur les valeurs.

Puis nous effectuons une recherche dichotomique sur la table triée et nous terminons par une routine d’insertion qui respecte l’ordre de tri des clés.

Dans le programme hashTable.s nous utilisons une fonction de hachage pour calculer l’indice de poste où stocker un enregistrement. Nous allons utiliser une chaine de caractères comme clé. Pour simplifier et examiner les cas de collision, nous utiliserons une table avec 10 postes seulement.

L’insertion s’effectue en appelant la fonction de hachage d’une chaine de caractère et qui va retourner un nombre compris entre 0 et 9 qui va servir d’indice pour accèder à un poste de la table. Si une clé est déjà stockée dans ce poste, nous cherchons le premier poste vide supérieur pour y inserer les nouvelles valeurs. Si l’indice dépasse le nombre maxi de postes de la table, la recherche continue au poste 0. Pour être sûr que la recherche d’un poste vide soit toujours fructueuse, il faut que la table ne contienne qu’un % du nombre total de poste. (voir la théorie pour avoir le % le plus correct possible).

Vous remarquerez que c’est l’occasion d’utiliser l’instruction particulière csinc qui suivant le résultat de la comparaison prend la valeur d’un registre ou l’incrément d’un autre (ou du même). Ici dès que l’on atteint le maximum de poste s, on remet l’indice à zéro avec le registre spécial xzr : astucieux non ?

La fonction de recherche consiste à calculer le N° de poste avec la même fonction de hachage. Puis si le poste est vide on retourne non trouvé, si le poste est rempli, on teste si les 2 chaines servant de clé sont identiques et sinon on balaye la table jusqu à trouver la bonne clé ou un poste vide.

Cette solution permet de trouver très rapidement des valeurs dans une table à la condition que la fonction de hachage donne des valeurs bien différentes et que la table ait un taux moyen de remplissage.

Exemple du résultat d’affichage de la table du programme :

Affichagetable

N° : 0  clé : 4264681 valeur : 110

N° : 1  clé : 4264675 valeur : 50

N° : 2  clé : 0 valeur : 0

N° : 3  clé : 0 valeur : 0

N° : 4  clé : 0 valeur : 0

N° : 5  clé : 4264686 valeur : 60

N° : 6  clé : 4264688 valeur : 70

N° : 7  clé : 0 valeur : 0

N° : 8  clé : 0 valeur : 0

N° : 9  clé : 0 valeur : 0

Dans le programme suivant hashlistTable, nous utilisons une autre solution. En cas de collision, nous utilisons des listes chainées pour stocker tous les enregistrements qui donnent la même valeur de poste. Ainsi même si la table a un fort taux de remplissage, la recherche d’une clé ne s’effectue que sur quelques nœuds de chaque liste chainée.

L’affichage suivant montre que pour le poste N°5 nous avons un pointeur vers une autre valeur.

Affichagetable

N° : 0  clé : 4264773 valeur : 110  suivant : 0

N° : 1  clé : 4264767 valeur : 50  suivant : 0

N° : 2  clé : 0 valeur : 0  suivant : 0

N° : 3  clé : 0 valeur : 0  suivant : 0

N° : 4  clé : 0 valeur : 0  suivant : 0

N° : 5  clé : 4264778 valeur : 60  suivant : 638988288

N° : 5  clé : 4264780 valeur : 70  suivant : 0

N° : 6  clé : 0 valeur : 0  suivant : 0

N° : 7  clé : 0 valeur : 0  suivant : 0

N° : 8  clé : 0 valeur : 0  suivant : 0

N° : 9  clé : 0 valeur : 0  suivant : 0

Vous remarquerez que la programmation de ces algorithmes en assembleur n’est pas très compliquée (et j’espère que je n’ai pas fait trop d’erreurs !!) et est assez compacte.

Chapitre 79 : Assembleur Arm 64 : lecture d’une page d’un site Web.

Au chapitre 56, nous avons vu l’utilisation des sockets en 32 bits pour accéder à une page sur Internet. A l’aide des tests des fonctions système du chapitre précédent, nous allons voir la même utilisation en 64 bits.

Dans le programme rechMeteo64.s, nous lançons un thread pour exécuter la commande Linux ping pour récupérer l’adresse IP du site de méteoFrance. En effet, dans le container 64 bits de la version Buster que j’utilise, la commande Linux host n’existe pas, j’ai donc du utiliser la commande ping pour récupérer l’adresse.

Comme nous l’avons vu au chapitre précedent l’execution de la commande au travers de execve, ne retourne pas dans le programme appelant. Il nous faut donc dupliquer la sortie Sysout vers un fichier tampon à l’aide des appels system pipe (code 59) et dup3(code 24). Ce qui nous permet de récuperer l’adresse IP dans un buffer et de la convertir pour créer la socket.

Comme en 32 bits, dans la routine envoiRequeteP80 nous ouvrons la socket (code 198) créons la connexion avec le site (code 203) envoyons la requête de lecture (code 206) après avoir calculé sa longueur puis lu la réponse avec le code 207. La lecture s’effectue dans une boucle pour récuperer tout le contenu de la page.

Vous remarquerez que l'utilisation des instructions cinc et csel permettent de résoudre le remplacement des instructions conditionnelles du type incne ou moveq.
 

Le reste du programme concerne l’analyse et l’extraction des données qui nous intéressent.

Attention, ce programme ne concerne que les pages des sites accessibles en http. Pour les sites accessibles en https, il faudra utiliser la librairie openSSL comme je l’avais fait en 32 bits.

Chapitre 78 : assembleur ARM 64 bits : lancement d'un thread. Exécution d'une commande Unix

Je repars du programme assembleur 32 bits vu au chapitre 20 pour l’adapter à l’assembleur 64 bits. (source du programme).

Après les modifications des registres, des accès à la pile il ne reste plus qu’à trouver les codes des appels système en en 64 bits. Hélas l’appel fork ne semble pas exister en 64 bits et donc je modifie le programme pour utiliser l’appel clone.

Ces modifications refusant de fonctionner, j’effectue des recherches sur internet pour trouver la source de mon erreur. En fait, les paramètres de la fonction clone sont identiques à la fonction fork du 32 bits et donc ne correspondent pas à la première description que j’avais trouvée. En effet la documentation des appels système en 64 bits n’est pas très disponible.

J’adapte aussi les appels système pour les fonctions sleep et wait4 sans problème. Par contre je ne trouve pas de fonction pause en 64 bits.

Après recherche sur internet je trouve une solution en utilisant les appels système rt_sigprocmask et rt_sigsuspend.

Tout fonctionne parfaitement après quelques tests !!

Puis, j’ai réécrit un programme pour tester l’exécution d’une commande Linux en utilisant l’appel system execve. Pour cela je me suis contenté de lancer la commande ls –l mais vous trouverez en commentaire la chaine de caractères pour lancer une commande ping.

Ici la seule difficulté est de passer correctement les paramètres à l’appel systeme qui est un peu différent de l’appel 32 bits.

 Comme en 32 bits, vous remarquerez que l’exécution correcte de la commande interrompt le programme appelant.

Chapitre 77 : Assembleur ARM 64 bits : calculs en virgule flottante (instructions Float)

Je commence l’année par découvrir les instructions de calcul en virgule flottante. En 64 bits, ces instructions sont très différentes de l’assembleur 32 bits et à première vue sont plus simples d’utilisation. Pour effectuer des calculs en double précision, nous disposons de 32 registres de 64 bits dont le nom commence par d.

Comme nous n’avons pas de routines assembleur pour afficher des nombres en virgule flottante, il nous faut utiliser l’instruction printf du C en utilisant le formatage « %+09.25f\n ». Comme il y a peu d’exemple sur internet de programmation 64 bits arm en float, il nous faut découvrir comment passer les arguments à la fonction.

Après quelques essais, je trouve que la chaine de formatage doit être passée dans le registre x0 et les valeurs à afficher dans les registres d0 d1 etc. En effet en virgule flottante les registres à utiliser en double précisions sont des registres 64 bits qui commencent par d et nous pouvons utiliser xx registres. Attention : l’appel de la fonction printf détruit le contenu des registres d0 d1 et peut être d’autres (à vérifier). L’utilisation des instructions du langage C necessite aussi l’utilisation de gcc pour effectuer le link. 

Source du programme calculFloat1.s

Donc je commence à alimenter le registre d0 avec une valeur immédiate avec l’instruction fmov d0,2 et tout se passe bien avec plusieurs valeurs lorsqu’une erreur de compilation arrive pour la valeur 50 !!

La recherche dans les 5000 pages de la documentation ARM montre que les valeurs immediates possibles doivent pouvoir être codées sur 8 bits dont un exposant de 3 bits et une mantisse de 4 bits. La figure C2-2 de la page C2-136 donne les valeurs possibles : par exemple 1 2 4 8 16 mais aussi 0,25 ou 0,1796875 mais pas 50.

Bien ! maintenant passons une valeur dans le registre x0 puis dans le registre d0 et comme en 32 bit, il faut effectuer une opération de conversion en float avec l’instruction scvtf d0,d0.

Et enfin nous chargeons une valeur double stockée en mémoire par la simple instruction ldr.

Après affichage, nous la rechargeons dans le registre d0 puis la convertissons en entier non signé avec l’instruction fcvtzu et la transferrons dans le registre x0 en passant par le registre d1 pour varier un peu. L’affichage du registre x0 montre bien la valeur 3. Pour les valeurs signées il faut utiliser fcvtzs.

Nous effectuons quelques opérations de calcul, addition, multiplication, division, minimum, racine carrée et quelques comparaisons qui sont plus simples qu’en 32 bits.

Enfin nous vérifions le stockage d’une valeur en mémoire. Il existe encore plein d’instructions pour manipuler ces nombres (et pour des conversions en simple précision).

J’effectue aussi quelques tests pour voir les conversions 32 bits 64 bits.

Comme exemple je vais reprendre le programme écrit en 32 bits pour analyser la génération de nombres aléatoires. Voir le programme verifAlea.s. Celui çi ne pose pas de problème particulier sauf que la valeur immédiate zéro ne peut pas être mis dans un registre dn avec l’instruction fmov. Mais en utilisant le registre particulier xzr, cela fonctionne.

Vous remarquerez que j’utilise le registre d8 pour les calculs pour éviter la modification d’un registre comme d4 par le premier appel de printf.

Ensuite le programme saisieFloat1.s donne une routine de conversion d’une chaine de caractères (abc,def ou abc.def) en nombre float. La chaine est passés d’abord dans la ligne de commande puis est ensuite saisie en utilisant l’appel système read.

Je voulais utiliser l’instruction de conversion     scvtf d0,x0, n bits   mais le position de la virgule par n bits ne peut pas être la valeur d’un registre. Donc j’ai utilisé une autre technique, je recopie la chaine de caractère en supprimant la virgule ou le point et en conservant leur position. Ensuite je convertit en décimal la chaine résultante et convertit en float le résultat.

Avec la position de la virgule, je calcule la puissance de 10 necessaire pour effectuer la division en float pour trouver le résultat correct. Exemple :

Soit la saisie de 12345,67 qui donne la chaine 1234567 convertit en float pour donner le dividende.

La virgule est en position 5 à partir de la gauche et 2 à partir de la droite . Il faut calculer la puissance 2 de 10 soit 100 qui convertit en float donnera le diviseur.

Il ne reste plus qu’à effectuer la division en float de 1234567 par 100 pour avoir un nombre float résultant correct dans le registre d0.