Les membres ayant 30 points peuvent parler sur les canaux annonces, projets et hs du chat.
La shoutbox n'est pas chargée par défaut pour des raisons de performances. Cliquez pour charger.

Forum Casio - Projets de programmation


Index du Forum » Projets de programmation » Extraction automatique des instructions du CPU SH4
Drakalex007 Hors ligne Membre Points: 688 Défis: 0 Message

Extraction automatique des instructions du CPU SH4

Posté le 12/11/2023 18:40

Partie 1 - Extraction

Je suis actuellement en train de bosser sur la création d'un émulateur pour casio monochrome 35+/75, et je réfléchissais en parallèle à une façon d'extraire automatiquement les instructions de la doc. En effet, il y a des centaines d'instructions, et bien que j'aie implémenté les 27 premières manuellement pour comprendre leur fonctionnement, cela commençait à devenir long et redondant. Je pense avoir désormais compris la base nécessaire pour mettre en place une technique qui le fait à ma place.

Je vais expliquer ici comment je m'y suis pris, sachant que tout le code javascript est disponible dans le repo du projet dans le dossier "script".

La toute première étape consiste à extraire les informations de la doc officielle du CPU SH4 dans un format qui peut être lu par un algorithme. Il existe des bibliothèques qui permettent de lire des PDFs via du code, mais la toute première chose que j'ai tenté de faire est un bête copié/collé (ctrl+a, ctrl+c, ctrl+v) de tout le pdf dans un fichier texte. Les seuls critères étant que les mots devaient apparaître dans l'ordre dans lequel ils apparaissent dans le pdf, c'est-à-dire de gauche à droite puis de haut en bas (ce qui n'est pas garanti avec ce genre de copié/collé bourrin). Heureusement, le document semble bien formaté (enfin presque, on verra pourquoi après), et je peux donc me servir de cette base pour en extraire les informations, il s'agit du fichier raw_instructions.txt.

Ensuite, il faut analyser le pdf et essayer de trouver un pattern qui permettrait d'extraire toutes les instructions. Il y a un gros bloc au début qui contient toutes les instructions à la suite ainsi que leur code, ça avait l'air prometteur, mais leur implémentation ne se situe que bien plus tard dans le document, et pas dans le même ordre, donc il fallait trouver autre chose :



Il y a un deuxième endroit où ces instructions apparaissent, c'est juste avant leur implémentation vers la fin du document, mais elles sont séparées en plusieurs groupes. Pour chaque groupe, il y a d'abord un tableau contenant les informations sur les instructions, toutes à la suite, et un peu plus tard leur implémentation, cette fois-ci dans le même ordre que le tableau ! Ce genre de pattern (tableau + implémentations) est répété plusieurs fois à la suite pour couvrir toutes les instructions. Ce sera le départ de mon algorithme !



Le principe va être de charger le fichier texte en tant que chaîne de caractères, et d'effectuer plein d'opérations dessus (découpage, recherche, trim) pour en isoler certaines parties et en extraire des informations. Le code de cette partie est situé dans le fichier extract_instructions.js.
La première étape est donc d'isoler chacun de ces groupes d'instructions (appelés instruction set dans mon code). Il s'agit de la fonction extractNextInstructionSet() dans mon code. Pour cela, je calcule la position du mot-clé "T Bit" qui représente la fin du header du tableau et donc le début de la toute première instruction (voir image ci-dessus). De façon similaire, je calcule la position de "Format Operation" qui représente le début du prochain tableau, et donc la fin de ce groupe d'instructions

Cela nous donne un tableau de plusieurs chaînes de caractères, contenant chacune un groupe d'instruction avec leur définition et leur implémentation. Pour chacune de ces chaînes, deux algorithmes sont nécessaires :

- extractInstructions() : Tout d'abord, je dois déterminer le nombre d'instructions présentes dans ce groupe. Pour cela, je vais utiliser des expressions régulières (Regexp), un outil très puissant pour chercher des patterns très spécifiques dans des chaînes de caractères. Et ici, on a un pattern qui saute aux yeux, le code de chaque instruction est toujours composé de 16 caractères avec des lettres minuscules ou des 0 ou 1. Le cas de figure parfait pour du regex ! Voici le regex qui permet d'isoler ces instructions :

const matches = input_str.match(/[01imnd]{16}/gm) // Match tokens like 0100nnnnmmmm1100, 1010dddddddddddd or 0000000000001011

Ici, le regex est /[01imnd]{16}/, qui signifie "cherche une chaîne de 16 caractères de long contenant uniquement des caractères dans cet ensemble : {0, 1, i, m, n, d}". gm sont deux attributs qui veulent dire (g)lobal - cherche TOUTES les occurrences, (m)ultiline - cherche sur plusieurs lignes.

Cela me permet d'isoler chacune des instructions en découpant la chaîne à l'emplacement de ces codes.
Puis pour extraire la famille de l'instruction, j'utilise le regex suivant :

const name = str.match(/[A-Z.01268\/]{2,}/)[0] // Match tokens like JSR, LDRS, MOV.L, DIV0S, CMP/EQ

Je peux aussi isoler la description de l'instruction, elle se trouve simplement entre la famille et le code.
Cette fonction retourne un tableau d’éléments de la sorte:

{
    code: '0000nnnnmmmm1110',
    desc: '@(R0,Rm),Rn',
    family: 'MOV.L'
},
{
    code: '1110nnnniiiiiiii',
    desc: '#imm,Rn',
    family: 'MOV'
},
...


- extractImplementations() : La fonction précédente retourne un tableau contenant pour chaque instruction sa famille, sa description et son code. Maintenant, il faut relier ces instructions à leur implémentations.
Le nom de fonction de chaque instruction n'est indiqué nulle part autre que lors de l'implémentation, donc il n'est pas possible de faire une simple recherche pour isoler la fonction correspondante à une instruction. Heureusement, les implémentations sont toutes dans le même ordre que celui du tableau, donc il suffit juste de les lire une par une et de les associer à l'instruction correspondante, dans l'ordre. J'ai remarqué que toutes les implémentations se situent dans une section qui commence par "Operations:", donc je peux déjà couper la chaîne jusqu'à cet endroit pour simplifier les choses.
Ensuite, il faut savoir que le regex permet de créer des groupes de recherche, et ainsi retourner plusieurs matchs correspondants à plusieurs groupes. Ma toute première tentative était de créer un regex qui isole ces quatre groupes :

FUNCTION_NAME (OPERANDS) /* DESCRIPTION /* { IMPLEMENTATION }

Cela marchait presque bien, mais j'avais des difficultés à détecter la fin du groupe "IMPLEMENTATION", car je me basais sur le caractère "}", mais dans le cas d'un bloc imbriqué (un if { } par exemple) cela coupait la fonction trop tôt. Du coup j'ai modifié un peu les choses pour seulement détecter les 3 premiers groupes. Et ensuite j'utilise un petit algorithme javascript (findLastFunctionBracket()) qui démarre de la fin du dernier groupe (donc juste avant l'implémentation) et calcule la position de l'accolade fermante de la fonction.
Voici le regex, celui-ci est un peu satanique je n'expliquerai pas les détails

const matches = input_str.matchAll(/\n {0,1}([A-Znm_012468]{2,}) {0,1}(\([^)]*\))[^\/]*(\/*.*\/)/gm)
// Utilisation:
for (let [_, name, operands, desc] of matches) {

Cet algorithme permet donc d'extraire le nom de la fonction, ses arguments, sa description (redondante) et surtout tout le code de son implémentation ! Je peux combiner ces infos avec celles précédentes (la famille et le code de l'instruction) de façon à créer un objet complet et utile informatif sur chacune des instructions :

{
    "code": "0011nnnnmmmm1100",
    "desc": "Rm,Rn",
    "family": "ADD",
    "name": "ADD",
    "operands": "(long m, long n)",
    "implementation": "ADD(long m, long n) /* ADD Rm,Rn */\r\n{\r\n R[n] += R[m];\r\n PC += 2;\r\n}"
},

Après avoir effectué ce processus pour toutes les instructions de tous les instruction sets, je peux sauvegarder ces informations sous un format .json (instructions.json) qui contient les memes informations que le fichier original raw.txt, mais dans un format bien plus pratique pour la suite de l'implémentation !

Il y a juste un détail à prendre en compte:

Drakalex007 a écrit :
Heureusement, le document semble bien formaté (enfin presque, on verra pourquoi après)

En fait, ma technique ne marche que pour la moitié du document environ. La seconde moitié des instructions sont liées au DSP (de ce que j'ai compris c'est une unité pour faire des opérations avec des doubles ou fixed-point). Pour une raison quelconque, bien que le format soit exactement le même pour les instructions DSP et non DSP dans le PDF, ma technique de copier/coller tout le document ne fonctionne plus car certains tableaux relatifs aux instructions DSP apparaissent désormais par colonne et non par rangée dans le fichier texte.
Le SDK Casio de base n'utilise jamais ces instructions, cependant gint le fait. Donc je me pencherai sur cette seconde partie plus tard, mon algorithme peut être légèrement réarrangé pour pouvoir gérer ce cas de figure!


Drakalex007 Hors ligne Membre Points: 688 Défis: 0 Message

Citer : Posté le 12/11/2023 18:43 | #


Partie 2 - Implémentation

Maintenant, je vais vouloir créer du code C valide à partir de ces instructions (write_instructions.js). Il y a plusieurs fichiers à générer : un fichier .h contenant les définitions de chaque fonction, un .c contenant leurs implémentations et finalement il faut aussi générer du code C qui permet d'assigner une instruction (désignée par son code 16 bits) à son implémentation.

Commençons par le plus simple : le header. Il s'agit juste de convertir chaque nom de fonction sous le format suivant :

FUNCTION_NAME(cpu_t* cpu, uint16_t instruction);

Un jeu d'enfant avec notre fichier json actuel:

// instruction.h
const header = instructions.map(instruction => `void ${instruction.name}(cpu_t* cpu, uint16_t instruction);\n`).join('')
fs.writeFileSync('generated/instruction.h', header)

Ce qui nous genere le code suivant, disponible dans instruction.h :

void ADD(cpu_t* cpu, uint16_t instruction);
void ADDI(cpu_t* cpu, uint16_t instruction);
void ADDC(cpu_t* cpu, uint16_t instruction);
void ADDV(cpu_t* cpu, uint16_t instruction);
void AND(cpu_t* cpu, uint16_t instruction);
...

Ensuite, pour le "sélecteur d'instruction", c'est un peu plus complexe. Dans chaque code, il y a une partie fixe, qui désigne l'instruction, et une partie variable, qui désigne ses paramètres. Pour convertir un code en instruction, il faut faire un if qui isole la partie fixe de chaque instruction pour la tester avec le code de l'instruction actuellement lue par le CPU. Cette partie est un peu plus brute-force, j'ai tout d'abord isolé 5 patterns uniques dans lesquels les parties fixes pouvaient être disposées, que je peux extraire grâce à des regex :

const reg16 = /[01]{16}/                // 0000000000001011
const reg8  = /[01]{8}[a-z]{8}/         // 00000000nnnnmmmm
const reg4  = /[01]{4}[a-z]{12}/        // 0000nnnnmmmmdddd
const reg48 = /[01]{4}[a-z]{4}[0-1]{8}/ // 0100nnnn00010010
const reg44 = /[01]{4}[a-z]{8}[01]{4}/  // 0110nnnnmmmm1000

Je peux ensuite grouper les instructions par pattern, et pour chaque pattern je genere la condition qui teste la partie fixe du code. Voici un exemple:

// 00000000nnnnmmmm
for (const instruction of filterInstructions(reg8)) {
    str += `\tif (high8 == 0b${instruction.code.slice(0, 8)}) return ${instruction.name};\n`
}

Cela permet de générer la fonction suivante, inclue dans instructions.c et qui retourne un pointeur de fonction :

// Returns a pointer to the function that implements the corresponding instruction
void (*get_instruction_impl(uint16_t instruction))(cpu_t*, uint16_t) {
    uint8_t high = (instruction >> 12) & 0x0F;
    uint8_t high8 = instruction >> 8;
    uint8_t low = instruction & 0x0F;
    uint8_t low8 = instruction & 0xFF;

    if (instruction == 0b0000000000101000) return CLRMAC;
    if (instruction == 0b0000000000011001) return DIV0U;
    if (high8 == 0b11000000) return MOVBSG;
    if (high8 == 0b11000001) return MOVWSG;
    if (high == 0b0111) return ADDI;
    if (high == 0b1110) return MOVI;
    if (high == 0b0100) {
        if (low8 == 0b00010101) return CMPPL;
        if (low8 == 0b00101011) return JMP;
                ...

Finalement, il faut créer l'implémentation de chacune de ces instructions. Pour cela, il va falloir modifier un peu le code de la doc. La doc passe chaque paramètre du code comme argument aux fonctions, cependant le processus qui extrait les variables depuis le code n'est pas inclus. Il faut transformer cette syntaxe :

ADD(long m, long n) /* ADD Rm,Rn */
{
     R[n] += R[m];
     PC += 2;
}

Pour arriver à la syntaxe suivante (qui dépend de la position et de la taille des paramètres de l'instruction) :

// ADD / Rm,Rn - 0011nnnnmmmm1100
void ADD(cpu_t* cpu, uint16_t instruction) {
    long n = (instruction >> 8) & 0xF;
    long m = (instruction >> 4) & 0xF;

    R[n] += R[m];
    PC += 2;
}


Pour cela, j'utilise d'abord un premier algorithme qui va lire le code de l'instruction, et calculer la position de départ et de fin de chaque caractère du code :

0000nnnnmmmm1110 -> [ { char: 'n', start: 4, end: 8 }, { char: 'm', start: 8, end: 12 } ]
1110nnnniiiiiiii -> [ { char: 'n', start: 4, end: 8 }, { char: 'i', start: 8, end: 16 } ]
1101nnnndddddddd -> [ { char: 'n', start: 4, end: 8 }, { char: 'd', start: 8, end: 16 } ]
11000100dddddddd -> [ { char: 'd', start: 8, end: 16 } ]

Grâce à ces informations, un autre algorithme crée la définition de chaque variable en fonction de son type, de sa taille et de sa position:

// Get instruction code + operands
1) 0010nnnnmmmm1101 + (long n, long m)
// Extract variable position and type
2) [
       { char: 'n', start: 4, end: 8, type: 'long' },
       { char: 'm', start: 8, end: 12, type: 'long' }
   ]
// Create variable definition
3) long n = (instruction >> 8) & 0xF;
   long m = (instruction >> 4) & 0xF;

Finalement, l'instruction est combinée de la façon suivante avant d'être ajoutée au fichier :

/* DESCRIPTION */
FUNCTION_NAME(cpu_t* cpu, uint16_t instruction) {
    VARIABLE_DEFINITION
    IMPLEMENTATION
}

Il y a une dernière chose à prendre en compte, la doc utilise des noms de variable simplifiés pour faire ses opérations (PC, PR, MACL, T...). Heureusement, il n'y a pas besoin de s'embêter à remplacer ces noms de variable dans l'algorithme, il suffit simplement de créer les #define appropriés au début du fichier. Par exemple :

#define SSR cpu->ssr
#define SPC cpu->spc
#define DBR cpu->dbr

#define PC cpu->pc
#define PR cpu->pr
...

De plus, j'ai pu convertir les fonctions plus complexes telles que les memory read/write et delay slot toujours en utilisant des define:

#define Read_Byte(addr) mem_read(cpu, addr, 1)
#define Read_Word(addr) mem_read(cpu, addr, 2)
#define Read_Long(addr) mem_read(cpu, addr, 4)

#define Write_Byte(addr, data) mem_write(cpu, addr, data, 1)
#define Write_Word(addr, data) mem_write(cpu, addr, data, 2)
#define Write_Long(addr, data) mem_write(cpu, addr, data, 4)

#define Delay_Slot(pc_next)     \
    uint32_t pc_save = cpu->pc; \
    cpu->pc = pc_next;          \
    run_next_instruction(cpu);  \
    cpu->pc = pc_save;

Tous ces define sont définis dans ce fichier et ajoutés lors de la création du code C.
Pour implémenter toutes les instructions, j'ai aussi dû ajouter les registres suivants (contrairement aux autres, je n'ai pas vraiment vu/approfondi leur utilisation dans le code):

// CPU
struct cpu_t {
    // ...
    uint32_t vbr;  // Vector base register
    uint32_t ssr;  // Saved status register
    uint32_t sgr; // Saved general register
    uint32_t spc; // Saved program counter
    uint32_t dbr; // Debug base register
};

Au final, tout ce travail nous produit le fameux Graal qui est le fichier instructions.c contenant la fidèle reproduction de 157 instructions de la doc ! S'il y a des bugs dans le code, on ne peut plus remettre en question mon implémentation des instructions, ce sera la faute de la doc
Drakalex007 Hors ligne Membre Points: 688 Défis: 0 Message

Citer : Posté le 12/11/2023 18:49 | #


Bonus - Les incohérences de la documentation

Pour finir, j'aimerais faire une petite compilation de toutes les incohérences de la doc auxquelles j'ai dû faire face lors de l'implémentation d'un tel outil très sensible au format et à la régularité des patterns. Il s'agit de la partie la plus compliquée et frustrante d'un tel projet x)

Le seul header qui contient une faute:


La seule implémentation contenant une accolade inversée:

MOVLL(long m, long n) /* MOV.L @Rm,Rn */
} // <---
     R[n] = Read_Long(R[m]);
     PC += 2;
}

(long i) au lieu de (long) i :



Les petits espaces vicieux



Les oublis du type des arguments:

MOVWI(d, n) // <--- should be (int d, int n)
     unsigned int disp;
     disp = (unsigned int)(0x000000FF & d);
     R[n] = (int)Read_Word(PC+4+(disp<<1));
     if ((R[n]&0x8000)==0) R[n] &= 0x0000FFFF;
     else R[n] |= 0xFFFF0000;
     PC += 2;
}

Les oublis de points-virgule:

DMULU(long m, long n) /* DMULU.L Rm,Rn */
{
     ...
     temp2 = RmL*RnH;
     temp3 = RmH*RnH;
     Res2 = 0 // <-----------
     Res1 = temp1 + temp2;

La seule occurrence de la typo "lomg" au lieu de "long":

LDSMMACL(lomg m) // <--------
{
     MACL = Read_Long(R[m]);
     R[m] += 4;
     PC += 2;
}

SYNCO, la seule fonction qui n'a pas de parenthèses après son nom:

SYNCO // <--- missing ()
{
     synchronize_data_operaiton();
     PC += 2;
}

Et j'en passe!
Cela me fait craindre qu'il puisse y avoir ne serait-ce qu'une petite faute (qui ne gênerait pas la compilation) quelque part dans une des implémentations, ce qui pourrait entraîner des crash impromptus de l’émulateur...

Et grâce à ce nouveau panel d'instructions, j'ai pu grandement avancer dans mon émulateur et afficher l’écran initial de trois programmes en plus du Sample Add-in: AsteroFall, Mandelbrot et Jetpack Joyride!








Fun fact d'ailleurs, tous ces programmes ont besoin de moins de 1000 instructions pour afficher l'écran initial.
Sauf Mandelbrot qui en a besoin de 15 millions
Lephenixnoir En ligne Administrateur Points: 24343 Défis: 170 Message

Citer : Posté le 12/11/2023 20:00 | #


Je suis assez surpris que ça marche. Je m'attends à des subtilités, sauf si le proco était généré par HLS et que la doc était le code source (j'en doute). En tous cas je ne l'ai pas vu venir...

Seul inconvénient, ça doit être assez lent sauf si le compilo carry à mort
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Drakalex007 Hors ligne Membre Points: 688 Défis: 0 Message

Citer : Posté le 12/11/2023 20:24 | #


J'avoue que je n’étais pas totalement sur de la réussite de cette méthode, mais jusqu'ici les 4 add-ins semblent s’être initialisés a merveille!
De quel genre de subtilités parles-tu?

Par contre je ne vois pas en quoi ce serait plus lent ? Les #define ne devraient absolument rien changer au code généré.
Lephenixnoir En ligne Administrateur Points: 24343 Défis: 170 Message

Citer : Posté le 12/11/2023 20:35 | #


Quelles subtilités ? Oh ben le fait que le pseudo-code fourni par la doc n'est pas une description complète, exacte et exhaustive du comportement du processeur.

Pour les performances, c'est parce que le pseudo-code fourni n'est pas écrit d'une façon très optimale (eg. extensions de signe manuelles au lieu d'utiliser le cast, multiplications multi-précision esquivées, ce genre de choses). Et le décodage que tu fais semble aussi très linéaire, et c'est surtout ça qui joue je pense.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Drakalex007 Hors ligne Membre Points: 688 Défis: 0 Message

Citer : Posté le 12/11/2023 21:08 | #


Ah oui, effectivement!

Lephenixnoir a écrit :
Et le décodage que tu fais semble aussi très linéaire, et c'est surtout ça qui joue je pense.

Tu parles de la ribambelle de if pour choisir l'instruction ?
Ou bien de l'extraction des arguments :

long n = (instruction >> 8) & 0xF;
long m = (instruction >> 4) & 0xF;

Comment serait-il possible d’améliorer le code généré selon toi?
Lephenixnoir En ligne Administrateur Points: 24343 Défis: 170 Message

Citer : Posté le 12/11/2023 21:29 | #


La ribambelle de if. À mon sens il faudrait une table de saut de 256 entrées pour le premier octet, ce qui t'identifie déjà plein d'instructions, et ensuite du if/else dans chaque cas, un truc comme ça.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Yannis300307 Hors ligne Membre Points: 284 Défis: 0 Message

Citer : Posté le 13/11/2023 10:57 | #


Pour avoir les meilleurs performances, est ce que ce ne serait pas mieux de le faire en WebAssembly ?
EDIT : ah et bien il semblerait que c'est déja le cas ...
WOW ! Mais qu'est-ce-que je vois ??!! Une extension VS Code qui permet de simplifier le développement sur calculatrices ??!! C'est ici : Casio Dev Tools. C'est incroyable ! C'est prodigieux !
Fcalva Hors ligne Membre Points: 523 Défis: 9 Message

Citer : Posté le 13/11/2023 11:10 | #


Webasm ? Pourquoi pas directement en LLVM voire asm amd64 vu que c'est une cible pc ?
Et puis aussi moin que je le sache c'est en C pour la portabilité hein.
Pc master race - Apréciateur de Noctua moyen
Caltos : G90+E, FX-92+ (x2)

LienAjouter une imageAjouter une vidéoAjouter un lien vers un profilAjouter du codeCiterAjouter un spoiler(texte affichable/masquable par un clic)Ajouter une barre de progressionItaliqueGrasSoulignéAfficher du texte barréCentréJustifiéPlus petitPlus grandPlus de smileys !
Cliquez pour épingler Cliquez pour détacher Cliquez pour fermer
Alignement de l'image: Redimensionnement de l'image (en pixel):
Afficher la liste des membres
:bow: :cool: :good: :love: ^^
:omg: :fusil: :aie: :argh: :mdr:
:boulet2: :thx: :champ: :whistle: :bounce:
valider
 :)  ;)  :D  :p
 :lol:  8)  :(  :@
 0_0  :oops:  :grr:  :E
 :O  :sry:  :mmm:  :waza:
 :'(  :here:  ^^  >:)

Σ π θ ± α β γ δ Δ σ λ
Veuillez donner la réponse en chiffre
Vous devez activer le Javascript dans votre navigateur pour pouvoir valider ce formulaire.

Si vous n'avez pas volontairement désactivé cette fonctionnalité de votre navigateur, il s'agit probablement d'un bug : contactez l'équipe de Planète Casio.

Planète Casio v4.3 © créé par Neuronix et Muelsaco 2004 - 2024 | Il y a 45 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd