Chapitre 12 :Utilisation données locales sur la pile et exemple de tri

Nous avons utilisé la pile pour passer des paramètres dans des routines et nous allons voir l’utilisation de la pile pour stocker des données locales, cela permettant d’appeler une routine dans elle-même (appel récursif). Nous allons utiliser le générateur de nombres aléatoires du chapitre précédent légèrement modifié pour générer 100 nombres que nous stockerons dans une table puis nous trierons cette table en utilisant une routine de tri rapide.

Voyons le source du programme :

Nous commençons par générer 100 nombres aléatoires que nous plaçons dans une table. Le générateur calcule un nombre aléatoire comme précédemment mais nous prenons les chiffres à gauche en fonction de la plage à la place des chiffres à droite (ce qui devrait produire des nombres plus aléatoires).

Pour mesurer le temps du tri, nous allons effectuer un call system pour positionner le temps avant le tri et nous effectuerons la même opération après le tri et nous calculerons la différence. Sur mon raspberry, l’appel system TIME (code 0x0D ) n’est pas implémenté et j’ai donc utilisé l’appel GETTIMEOFDAY (code 0x4E).

Nous appelons ensuite la routine de tri et nous terminons par une vérification que la table est bien triée. Nous balayons la table en comparant 2 postes successifs et nous signalons une erreur si le premier est plus grand que le second.

Dans la routine de tri, nous nous contentons de sauvegarder les registres qui vont être utilisés et nous appelons la sous routine tri. Dans celle-ci après la sauvegarde habituelle des 2 registres fp et lr sur la pile, nous réservons sur la pile 16 octets par l’instruction sub sp,#16 (rappel ; les adresses de la pile décroissent). Et nous positionnons le registre fp (frame pointer) à l’adresse de la pile. Cela nous permet de manipuler les données de la zone réservée facilement.

Le tri rapide utilise un algorithme de partitionnement de la table à trier en 2 sous tables qui seront-elles mêmes partitionner en deux en utilisant un appel récursif de la même sous routine. Avant chaque appel, les pointeurs gauche, droite et courant et l’adresse de la table sont sauvegardé sur la pile dans la zone réservée. Le registre fp permet d’utiliser ces adresses sans difficulté.

Le début de la table est affiché avant et après le tri pour vérification ainsi que le temps mis pour le tri. Ce tri est efficace puisque sur mon raspberry il trie 1000000 de nombres en 1,5 secondes. Attention, ce tri peut utiliser une grande partie de la pile si les données sont mal réparties (voir la théorie sur ce type de tri).

Exercice : Adapter le tri pour trier dans l’ordre décroissant

                Écrire d’autres routines de tri et comparer le temps d’exécution.

                   Modifier le tri pour trier des chaines de caractères.

Chapitre 11 : Calcul en virgule flottante et nombres pseudo aléatoires

Pour effectuer des calculs en virgule flottante en utilisant les instructions assembleur, le programme ci après va consister à générer des nombres pseudo aléatoires et à calculer la moyenne, l’écart type et le khi afin de vérifier la validité du générateur.

Je dois vous avouer que ce générateur est très simple et donc que les nombres générées ne sont pas très aléatoires (voir la théorie sur la génération de ces nombres et les livres de Knuth).

Le programme vous semble aussi très long mais j’ai voulu afficher les résultats en écrivant une routine d’affichage des nombres en virgule flottante simple précision et c’est assez compliqué (et certainement cette routine peut être améliorée).

ATTENTION remarque du 10/09/2020 : la routine d'affichage est fausse pour de grands exposants (certainement > 32). Une nouvelle routine pour les nombres en double précision est en cours de test et sera publiée dans le chapitre 90. Le chapitre 88 donne une routine qui semble plus exacte à ce jour pour l'assembleur 64 bits.

  

Lors de la première compilation de ce programme, le compilateur signale que les instructions en virgule flottante ne sont pas autorisées sur le processeur de mon Raspberry. Alors que la documentation précise bien que c’est possible et donc après recherche, j’ai découvert qu’il fallait ajouter la directive suivante

-mcpu=arm1176jzf-s -mfpu=vfp -mfloat-abi=hard

dans le script d’assemblage. Donc j’ai écrit un nouveau script de compilation et j’ai aussi modifié le link pour qu’il s’exécute par gcc car le programme fait aussi appel à la fonction printf du C.

Voyons le source du programme :

Après les déclarations habituelles des messages et des zones nécessaires, nous initialisons les registres nécessaires au calcul. En virgule flottante simple précision, nous trouvons de nouveaux registres s0 à s31 et en double précision les registres d0 à d15 ( mais attentions les registres d recouvrent les registres s. Voir le chapitre 13 sur http://thinkingeek.com/arm-assembler-raspberry-pi/). Nous allons effectuer les calculs en simple précision et donc nous utiliserons les registres s. Pour alimenter s3, il suffit de copier le registre r0 par l’instruction vmov s3,r0  puis il faut effectuer une conversion par l’instruction vcvt.f32.s32 s3, s3  (f32 et s32 indique que nous travaillons en simple précision) car les nombres ont une structure très particulière : norme IEEE754.

En simple précision, les nombres font 32 bits : le bit à gauche donne le signe puis les 8 bits suivants représentent l’exposant et les 23 derniers bits la mantisse (pour plus de précisions voir la norme IEEE754)

Après avoir initialisé les 3 registres s2, s3 et s4 (surtout de jamais oublier d’effectuer la conversion). Nous préparons une table qui va compter le nombre de tirage pour un chiffre aléatoire tiré, table nécessaire pour le calcul du KHI.

Puis nous avons une boucle qui va effectuer MAXI tirages en appelant la fonction de génération. Nous passons à cette fonction la valeur PLAGE et nous aurons en retour dans r0 un nombre pseudo aléatoire compris entre 0 et PLAGE. La fonction de génération est simple puisque nous nous contentons de multiplier une graine de départ par un nombre donné et d’y ajouter un autre nombre pour calculer une nouvelle graine. Ensuite nous effectuons une division par la plage demandée et nous retournons le reste comme nombre aléatoire.

 Nous copions ce nombre dans le registre s1, et effectuons sa conversion pour le diviser par le nombre de tirage et l’ajouter dans le registre de totalisation de la moyenne avec les instructions de calcul en virgule flottante (vdiv, fmul, fadd ). Nous calculons aussi l’écart type en virgule flottante. Et pour chaque tirage, nous l’ajoutons aussi dans la table des tirages.

En fin de boucle, nous calculons la moyenne en nombre entier (en fait simplement pour voir la différence avec le calcul en virgule flottante) et nous l’affichons par notre fonction d’affichage, nous terminons le calcul de l’écart type (élévation au carré et calcul de la racine carrée) et nous l’affichons avec la fonction printf du C. Mais cette fonction n’admet que les nombres en double précision passés dans les registres r2 et r3. Il nous faut donc convertir notre résultat par l’instruction vcvt.f64.f32  d5, s3  (noter le f64 et l’utilisation du registre d5) puis alimenter les registres par vmov r2,r3,d5 pour appeler la fonction du C printf. Cette fonction utilise le format %f pour éditer correctement le nombre indiqué dans la chaine szFormat.

Ensuite nous appelons la routine conversionFloatSP pour convertit le contenu du registre r0 en chaine affichable. J’ai écrit cette routine pour ne pas faire appel à des fonctions du C. Comme je ne suis pas encore un expert en assembleur, cette routine n’est certainement pas l’idéal et il reste des points à améliorer (en particulier les zéros inutiles après la virgule. Elle est aussi compliquée car pour calculer le résultat qui dépasse la taille d’un registre, je suis passé par des zones en mémoire pour effectuer les multiplications et divisions nécessaires. Sur Internet, je n’ai pas trouvé d’exemples de routines en assembleur qui effectuent cette conversion et j’ai dû écrire la mienne à partir de la documentation du format IEEE754.

La routine commence par extraire l’exposant et la mantisse du registre r0 et en fonction de l’exposant va effectuer 4  traitements différents : l’exposant est égal à 255 , l’exposant est égal à 0, l’exposant est supérieur à 127 et l’exposant est inférieur à 127. Pour la suite de la routine, je vous suggère d’aller voir directement le code et les commentaires.

Revenons dans le programme principal pour calculer le coefficient khi  qui permet de juger de la pertinence du générateur aléatoire. Nous repartons de la table dans laquelle nous avons enregistré les comptages de chaque tirage  pour calculer le total des carrés de chaque compteur. Ensuite nous effectuons le reste des calculs en virgule flottante pour afficher le résultat avec la fonction printf du C et avec la routine en assembleur.

Voici le résultat sur mon raspberry :

Comme vous le voyez, la moyenne, l’écart type et le khi sont proches de ceux attendus (50 , 25 et 100).

Pour les calculs en virgule flottante, les instructions à utiliser ne sont pas très complexes, il faut surtout veiller à bien mettre les bonnes extensions .f32.s32  et pensez à effectuer les conversions entier vers float.

Et dans ce programme, je n’ai pas fait appel à des données en virgule flottante. Si c’est nécessaire il faut les coder comme ceci :

pi: .float 0E-3141592E-6

et l’utiliser par ldr r1,=pi

                           vldr s1,[r1]         @ s1 contient pi

et dans ce cas il est inutile d’effectuer la conversion par l’instruction vcvt.

Exercice : tester  un générateur diffèrent pour avoir un khi meilleur

                Améliorer la routine de conversion du nombre en simple précision

              Et plus difficile, écrire une routine de conversion pour les nombres en double précision.

               Et aussi une routine pour saisir dans la console des nombres en virgule flottante.

Chapitre 10 : lecture d'un répertoire

Si avec le programme de lecture du chapitre 8, nous essayons de lire un répertoire, nous avons une erreur qui indique que le fichier lu n’est pas un fichier mais un répertoire !! Donc il nous faut trouver un autre appel système qui traite les répertoires. Nous trouvons un READDIR code 89 mais un premier test retourne une erreur -38 : appel non implémenté. Enfin nous trouvons un appel GETDENTS code 8D qui fonctionne. Cet appel donne à l’adresse passée dans le registre r1 une structure qui contient des entrées composées entre autres de l’identification des fichiers et leurs noms. Pour certainement un gain de place, les noms ne sont pas stockés dans une zone de longueur fixe mais dans une zone de longueur variable. Ainsi pour connaitre l’emplacement de début de l’entrée suivante chaque entrée contient le déplacement (offset) qui permet d’aller à l’entrée suivante.

Voyons ce petit programme qui accède à un répertoire, qui affiche le nom de chaque fichier qui compose le répertoire et son type. Voici le lien vers le source du programme lectdir2.s.

Tout d’abord, nous trouvons une série de constantes pour les types des fichiers possibles puis les libellés des messages d’erreurs ou de résultats et la description de la structure utilisée.

Dans la partie code, nous effectuons comme précédemment l’ouverture du répertoire puis la lecture des données dans un buffer avec l’appel GETDENTS. Nous affichons le contenu de ce buffer par notre routine habituelle de vidage pour vérification puis nous entrons dans une boucle qui va afficher le nom du fichier. Ce nom est récupéré grâce à l’instruction : add r0,r2,#Dir_name  r2 contenant l’adresse de début du buffer. Ensuite nous effectuons le calcul de l’adresse de l’entrée suivante car le type du fichier que nous venons d’afficher se trouve au caractère précèdent l’entrée suivante (ouf !!). En fonction de ce type nous affichons le message correspondant. (ici je me suis contenté de n’afficher que les types fichiers et répertoires). Et nous terminons en bouclant.

Remarquez que rien n’indique la fin des entrées stockées dans la structure. Il nous faut donc conserver le nombre d’octets lus dans le registre r6 et à chaque entrée traitée il faut ajouter sa longueur au registre r7 . Ceci permet de comparer les 2 registres et d’arrêter la boucle quand tous les octets sont traités.

Exercice :  compléter le programme avec les autres types de fichiers.

                Afficher toutes les informations de chaque entrée (inode, offset, longueur).

                Éliminer de l’affichage les 2 répertoires Unix . et .. (au fait savez-vous à quoi ils correspondent ?)

Chapitre 9: taille et informations d'un fichier

Avant de lire un fichier et de stocker son contenu dans le buffer, il serait intéressant de connaitre sa taille avant de le lire et d’agir en conséquence (par exemple : afficher un message d’erreur).

Dans la documentation des call system, nous trouvons l’appel newfstat code 6c (les autres fonctions comme stat et fstat ne sont pas implémentées) qui retourne toute une série d’information sur un fichier passé en paramètre. En fait c’est un pointeur qui est retourné dans le registre r0 et ce pointeur donne l’adresse d’une structure qui contient soit les informations soit des adresses vers d’autres données.

Il est possible d’accéder à chaque donnée de la structure en ajoutant son déplacement (offset) au pointeur de la structure  comme ldr r1,[r0,#8]. Mais il est plus parlant d’y accéder par ldr r1,[r0,#Taille] et il nous faut donc décrire la structure en assembleur. L’assembleur as n’est pas très bien conçu (avis personnel !) pour décrire les structures mais il offre quand même un mécanisme pour le faire. Il permet d’associer des noms de zones à un déplacement en indiquant la longueur en octets de chacune d’elles. L’instruction .struct effectue cette association sans réserver de zones en mémoire. Pour l’utilisation il suffira d’ajouter au pointeur de début de structure, le nom adéquat.

Voyons sur l’exemple des infos d’un fichier. La documentation des call system indique que la structure s'appelle stat et donne sa description en langage c

struct stat {

        unsigned int   st_dev;

        unsigned int   st_ino;

        unsigned int   st_mode;

        unsigned int   st_nlink;

        unsigned int   st_uid;

        unsigned int   st_gid;

        unsigned int   st_rdev;

        long           st_size;

        unsigned long  st_atime;

        unsigned long  st_mtime;

        unsigned long  st_ctime;

        unsigned int   st_blksize;

        unsigned int   st_blocks;

        unsigned int   st_flags;

        unsigned int   st_gen;

};

Et bien, nous allons reprendre cette description et la traduire pour l’assembleur en préfixant les zones par Stat et en considérant que chacune occupe 4 octets :

/* structure de type   stat  : infos fichier  */

    .struct  0

Stat_dev_t:                  /* ID of device containing file */

    .struct Stat_dev_t + 4

Stat_ino_t:                   /* inode */

    .struct Stat_ino_t + 4

Stat_mode_t:             /* File type and mode */

    .struct Stat_mode_t + 4          

Stat_nlink_t:                /* Number of hard links */

    .struct Stat_nlink_t + 4            

Stat_uid_t:                    /* User ID of owner */

    .struct Stat_uid_t + 4

Stat_gid_t:                      /* Group ID of owner */

    .struct Stat_gid_t + 4                

Stat_rdev_t:                  /* Device ID (if special file) */

    .struct Stat_rdev_t + 4

Stat_size_t:                   /* Total size, in bytes */

    .struct Stat_size_t + 4              

Stat_blksize_t:             /* Block size for filesystem I/O */

    .struct Stat_blksize_t + 4        

Stat_blkcnt_t:              /* Number of 512B blocks allocated */

    .struct Stat_blkcnt_t + 4         

Stat_Fin:            

Puis nous écrivons le programme qui va ouvrir le fichier, puis appeler la fonction NEWSTAT et nous allons afficher la mémoire correspondant au pointeur de la structure. Puis nous allons afficher la zone Stat_size_t qui devrait contenir la taille.

Voici le source du programme :

Voici le résultat sur le fichier fic1.

Mais il y a un petit problème : la taille affichée ne correspond pas à celle donnée par ls –l. Il y a un décalage entre les infos de la structure et le résultat. Donc je pars à la recherche sur Internet des différentes descriptions de Stats.h en C et je trouve que certaines données sont des short (2octets) et non pas des integer (4 octets) et d’autres comme la taille sont des longs (8 octets) et je complète aussi avec les zones concernant les dates du fichier . Donc je rectifie la structure comme suit :

/* structure de type   stat  : infos fichier  */

    .struct  0

Stat_dev_t:                  /* ID of device containing file */

    .struct Stat_dev_t + 4

Stat_ino_t:                   /* inode */

    .struct Stat_ino_t + 2

Stat_mode_t:             /* File type and mode */

    .struct Stat_mode_t + 2          

Stat_nlink_t:                /* Number of hard links */

    .struct Stat_nlink_t + 2            

Stat_uid_t:                    /* User ID of owner */

    .struct Stat_uid_t + 2

Stat_gid_t:                      /* Group ID of owner */

    .struct Stat_gid_t + 2                

Stat_rdev_t:                  /* Device ID (if special file) */

    .struct Stat_rdev_t + 2

Stat_size_deb:           /* la taille est sur 8 octets si gros fichiers */

                 .struct Stat_size_deb + 4

Stat_size_t:                   /* Total size, in bytes */

    .struct Stat_size_t + 4              

Stat_blksize_t:             /* Block size for filesystem I/O */

    .struct Stat_blksize_t + 4        

Stat_blkcnt_t:              /* Number of 512B blocks allocated */

    .struct Stat_blkcnt_t + 4         

Stat_atime:                   /*   date et heure fichier */

    .struct Stat_atime + 8    

Stat_mtime:                 /*   date et heure modif fichier */

    .struct Stat_atime + 8

Stat_ctime:                   /*   date et heure creation fichier */

    .struct Stat_atime + 8              

Stat_Fin:            

Cette fois ci le programme est correct et je trouve bien la longueur du fichier en hexa dans le registre r1. En conclusion, il nous faudra par la suite, vérifier par des tests la validité des structures.

Remarque : j’ai décrit la structure utilisée en reprenant les noms anglais, mais il est possible de franciser ces noms.

Exercice :  Afficher dans la console d’autres informations du fichier.

                  Et sans doute plus difficile, la date de création du fichier étant codée sur 8 octets, écrire une routine qui l’affiche sous la forme JJ/MM/AAAA  HHh MMm SSs.