Introduction

«The people of Krikkit have never thought to themselves [as if they were] alone in the Universe. They are surrounded by a huge Dust Cloud, you see, their single sun with its single world, and they are right out on the utmost eastern edge of the Galaxy. Because of the Dust Cloud there has never been anything to see in the sky. At night it is totally blank, During the day there is the sun, but you can't look directly at that so they don't. They are hardly aware of the sky. It's as if they had a blind spot which extended 180 degrees from horizon to horizon.

You see, the reason why they have never thought We are alone in the Universe is that until tonight they don't know about the Universe. Until tonight.»

Douglas Adams - Life, the Universe and Everything 

Principe du jeu

    Le Krikkit War (que nous appelerons par la suite Corewar) est une guerre virtuelle où s'affrontent des programmes (qui peuvent être assimilés à des robots, pour ceux qui voudraient faire le lien avec l'oeuvre de Douglas Adams). Cette guerre se déroule dans une zone de mémoire ou des processus naissent, évoluent, meurent. Le but d'un processus est d'être le dernier en vie. Pour cela, il va devoir faire tout ce qu'il peut pour éliminer les processus adverses, tout en signalant qu'il est en vie. Tout processus ne signalant pas qu'il est en vie est considéré comme mort. Ces processus représentent en fait des processeurs virtuels qui lisent et exécutent le code situé dans la mémoire. Ils exécutent une instruction particulière pour signaler aux joueurs qu'ils sont en vie. Au cours d'une partie, les processeurs pourront donc etre détruits, se multiplier (leur nombre est variable au cours d'une partie et est théoriquement illimité) et manipuler la mémoire pour arriver à leurs fins. C'est la guerre et tous les coups sont permis.




La Machine Virtuelle

    Le projet Krikkit War se compose de deux parties distinctes :

    • un assembleur
    • une machine virtuelle
    Dans un premier temps, vous avez réalisé l'assembleur. Dans un second, vous allez realiser la machine virtuelle. La question que vous vous posez donc maintenant doit bien entendu être :
    « qu'est-ce que la machine virtuelle, et que doit-elle faire ? »

    La machine virtuelle va simuler l'arène dans laquelle se battront les processus. A chaque processus est alloué un processeur qui va exécuter des instructions. La machine virtuelle est chargée de simuler chaque processeur, leurs cycles d'exécution, leurs lectures et leurs écritures mémoire, leurs départs en couille, les cinq feuilles qu'ils se roulent, tout ça. Chaque processeur essaie d'être le dernier vivant, suivant la règle du dernier des mohicans ("S'il n'en reste qu'un, je serai celui-là"). Et la machine virtuelle, c'est le Grand Arbitre, celui à qui on rend les comptes, celui qui accorde et prend la vie (HellMaster Phibrizzo ?), et aussi Big Brother, car elle surveille tout, tout le monde, et tout le temps.


    Caractéritisques des processeurs : de quoi sont capables nos processus ?

      Voici les caractéristiques techniques de chaque processeur.

      • Le processeur travaille sur des quartets. Le quartet est la plus petite entité comprise par le processeur. Un quartet est un ensemble de 4 bits consécutifs, soit la moitié d'un octet.
      • Le processeur dispose des registres suivants :
        • r0 à r15: 16 registres de calcul de 16 bits chacun.
        • Une pile circulaire de 16 niveaux de 16 bits chacun.
        • PC: le pointeur d'exécution de programme (16 bits).
        • P: un registre de 2 bits (voir plus loin).
        • Z: un registre de 1 bit (voir plus loin).
      • Chaque processeur dispose d'une pile. La pile est circulaire, ce qui signifie qu'après avoir dépilé 16 valeurs, on peut à nouveau redépiler les mêmes valeurs. Si l'on dépile la valeur 1, puis la valeur 0, la prochaine valeur à être dépilée est celle qui se trouve à la 15e position.

      • P est un registre spécial, il n'est pas utilisé pour les calculs, mais influe sur le fonctionnement de presque toutes les instructions. Les registres de calcul font 16 bits, c'est-à-dire 4 quartets numérotés de 0 à 3, le quartet 0 représentant les 4 bits de poids faible. P fait 2 bits et peut donc prendre les valeurs de 0 à 3. D'une maniere générale, les instructions du processeur travaillent uniquement sur les quartets 0 à P des registres (les (P + 1) * 4 bits de poids faible).
      • Z est un autre registre spécial. Il est essentiellement affecté par les instructions de calcul. Après un calcul, Z vaut 1 si le résultat est nul, sinon il prend la valeur 0. Attention : n'oubliez pas que les instructions de calcul travaillent avec les quartets 0 à P, donc Z dépend uniquement du résultat sur ces mêmes quartets 0 à P. Quelques autres instructions modifient Z et cela sera précisé.
      • On utilise le little-endian. Ce concept s'oppose à celui du big-endian. Dans notre cas, il concerne uniquement les accès mémoire et le format des fichiers sur le disque. Ceux-ci auront lieu en little-endian, c'est-à-dire qu'en mémoire les octets de poids faible seront aux adresses faibles. Par exemple, si la mémoire contient la suite de 4 octets 00000000 à l'adresse 0x0 et qu'on écrit la valeur 0x1234 sur 2 octets à l'adresse 0x1, la mémoire contiendra après écriture 0x00341200 à l'adresse 0x0. Si maintenant on lit la valeur sur 1 octet à l'adresse 0x1, on aura 0x34.
      • Les processeurs fonctionnent entièrement en relatif. Cela signifie que la position du programme dans la mémoire n'influe pas sur son comportement. Les accès mémoire et les sauts se font d'une certaine distance en avant ou en arrière par rapport à la position courante (PC).



    Le langage d'assemblage : description du jeu d'instructions

      Voici le jeu d'intructions des processeurs. Les instructions sont de taille variable et elles peuvent prendre des paramètres qui peuvent être :

      • des registres : rx ou ry
      • des expressions constantes: n

      Dans les tables qui suivent, la première colonne représente les mnémoniques des instructions. Une mnémonique est un identifiant qui représente une instruction dans le langage de l'assembleur. Les mnémoniques sont suivis des paramètres à fournir, s'il y en a, séparés par des virgules. Notez que chaque caractère est important et qu'il devra apparaître dans le code. Les mnémoniques qui n'affectent pas Z sont signalées, toutes les autres l'affectent.

      Description des instructions

        Cette description vous est fournie pour que vous puissiez comprendre ce que fait chaque instruction du langage.

      Mnémonique Description
      die die : Tout processeur qui exécute cette instruction est détruit instantanément.
      live n live : Emet un signe de vie pour le joueur n. Le fonctionnement est indépedendant de P et n'affecte pas Z.
      mov rx, ry move : Copie les quartets 0 à P de ry dans rx. Le fonctionnement n'affecte pas Z.
      swp rx, ry swap : Echange les quartets 0 à P de rx et ry. Le fonctionnement n'affecte pas Z.
      not rx, ry not : Calcule la négation logique (complément à 1) des quartets 0 à P de ry et stocke le résultat dans les quartets 0 à P de rx.
      and rx, ry and : Calcule le ET logique bit à bit entre les quartets 0 à P de rx et de ry et stocke le résultat dans les quartets 0 à P de rx.
      or rx, ry or : Calcule le OU logique bit à bit entre les quartets 0 à P de rx et de ry et stocke le résultat dans les quartets 0 à P de rx.
      xor rx, ry xor : Calcule le OU exclusif bit à bit entre les quartets 0 à P de rx et de ry et stocke le résultat dans les quartets 0 à P de rx.
      rol rx, n rotate left : Effectue une rotation vers la gauche de n bits des quartets 0 à P de rx. L'instruction ror qui effectue une rotation à droite n'existe pas car on peut la simuler grace à un rol avec une valeur appropriée de n.
      asr rx, n arithmetic shift right : Effectue un décalage arithmétique à droite de n bits des quartets 0 à P de rx. Ce décalage a pour caractéristique de faire entrer des bits identiques au bit de signe (conservation du signe).
      add rx, ry add : Additionne les quartets 0 à P de ry à ceux de rx et stocke le résultat dans les quartets 0 à P de rx (rx = rx + ry).
      sub rx, ry sub : Soustrait les quartets 0 à P de ry de ceux de rx et stocke le résultat dans les quartets 0 à P de rx (rx = rx - ry).
      rsb rx, ry reverse sub : Soustrait les quartets 0 à P de rx de ceux de ry et stocke le resultat dans les quartets 0 à P de rx (rx = ry - rx).
      neg rx, ry neg : Calcule la négation arithmétique (complement à 2) des quartets 0 à P de ry et stocke le résultat dans les quartets 0 à P de rx.
      inc rx, n inc : Incrémente de n les quartets 0 à P de rx (rx = rx + n).
      dec rx, n dec : Décrémente de n les quartets 0 à P de rx. (rx = rx - n).
      lsl rx, n logical shift left : Effectue un décalage à gauche de n bits des quartets 0 à P de rx. Les bits entrants sont nuls.
      lsr rx, n logical shift right: Effectue un décalage à droite de n bits des quartets 0 à P de rx. Les bits entrants sont nuls.
      lp n load P : Charge les 2 bits de poids faible de n dans P (P = n). Le fonctionnement est indépedendant de P et n'affecte pas Z.
      bnz rx branch if not Z : Effectue un saut relatif de rx modulo IDX_MOD quartets si Z = 0 (PC = PC + (rx % IDX_MOD)). rx est signé et utilise en entier. Le fonctionnement est indépedendant de P et n'affecte pas Z.
      bz rx branch if Z : Effectue un saut relatif de rx modulo IDX_MOD quartets si Z = 1 (PC = PC + (rx % IDX_MOD)). rx est signé et utilisé en entier. Le fonctionnement est indépedendant de P et n'affecte pas Z.
      ld rx, [ry] load : Charge les P + 1 quartets stockés à l'adresse PC + (ry % IDX_MOD) dans les quartets 0 à P de rx. ry est signé et utilisé en entier. Le fonctionnement n'affecte pas Z.
      st [rx], ry store : Stocke les quartets 0 à P de ry dans les P + 1 quartets stockés à l'adresse PC + (rx % IDX_MOD). rx est signé et utilisé en entier. Le fonctionnement n'affecte pas Z.
      lc rx, n load constant : Charge n dans les 2 quartets de poids faible de rx et propage le bit de signe de ces 2 quartets dans les 2 quartets de poids fort de rx. Le fonctionnement est indépedendant de P et n'affecte pas Z.
      ll rx, n load long : Charge n dans le registre rx entier. Le fonctionnement est indépedendant de P et n'affecte pas Z.
      fork fork : Créé un nouveau processeur en tout point identique à celui qui exécute le fork à l'exception du registre Z qui vaudra 0 dans l'un et 1 dans l'autre. Le fonctionnement est indépedendant de P.
      push rx push : Empile rx entier dans la pile du processeur. Le fonctionnement est indépedendant de P et n'affecte pas Z.
      pop rx pop : Dépile une valeur de la pile du processeur et la stocke dans rx. Le fonctionnement est indepedendant de P et n'affecte pas Z.
      jmp rx jmp : Effectue un saut relatif long et inconditionnel de rx quartets (PC = PC + rx). rx est signé et utilisé en entier. Le fonctionnement est indépedendant de P et n'affecte pas Z.
      fl rx, [ry] far load : Charge les P + 1 quartets stockés à l'adresse PC + ry dans les quartets 0 à P de rx. ry est signé et utilisé en entier. Le fonctionnement n'affecte pas Z.
      write rx write : Ecrit sur la sortie standard le caractère contenu dans les 2 quartets de poids faible de rx. Le fonctionnement est indépedendant de P et n'affecte pas Z.
      stat rx, n statistic : Charge dans rx entier la valeur du compteur n. Le fonctionnement est indépedendant de P et n'affecte pas Z.

      Codage et temps des instructions

        Cette table fournit le codage bit à bit des instructions. Les X répresentent des bits non significatifs, c'est-à-dire que leur valeur est quelconque et n'influe pas, donc vous pouvez mettre ce que vous voulez. Les registres sont stockés sur 1 quartet et sont juste representés par leur nom depuis la première colonne. Le registre r0 sera codé par 0x0, r1 par 0x1... et r15 par 0xF. 'n' représente une constante d'un quartet.
        Attention : ces constantes sont stockées dans le code en little-endian.

        La table fournit aussi les temps des instructions. Il y a trois phases pour chaque instruction et le nombre de cycles pour chacune d'elles.

      Mnémonique Offset 0 Offset 1 Offset 2 Offset 3 Offset 4 Offset 5   Décodage Délai Exécution Total
      die X000 0000           2 0 0 2
      live n X000 n           2 39 1 42
      mov rx, ry X001 0000 rx ry       4 0 P + 1 P + 5
      swp rx, ry X001 0001 rx ry       4 0 P + 1 P + 5
      not rx, ry X001 0010 rx ry       4 0 P + 1 P + 5
      and rx, ry X001 0011 rx ry       4 0 P + 1 P + 5
      or rx, ry X001 0100 rx ry       4 0 P + 1 P + 5
      xor rx, ry X001 0101 rx ry       4 0 P + 1 P + 5
      rol rx, n X001 0110 rx n       4 0 P + 1 P + 5
      asr rx, n X001 0111 rx n       4 0 P + 1 P + 5
      add rx, ry X001 1000 rx ry       4 0 P + 1 P + 5
      sub rx, ry X001 1001 rx ry       4 0 P + 1 P + 5
      rsb rx, ry X001 1010 rx ry       4 0 P + 1 P + 5
      neg rx, ry X001 1011 rx ry       4 0 P + 1 P + 5
      inc rx, n X001 1100 rx n       4 0 P + 1 P + 5
      dec rx, n X001 1101 rx n       4 0 P + 1 P + 5
      lsl rx, n X001 1110 rx n       4 0 P + 1 P + 5
      lsr rx, n X001 1111 rx n       4 0 P + 1 P + 5
      lp n X010 n           2 0 1 3
      bnz rx 0011 rx           2 1 1 4
      bz rx 1011 rx           2 1 1 4
      ld rx, [ry] X100 rx ry         3 1 P + 1 P + 5
      st [rx], ry X101 rx ry         3 8 P + 1 P + 12
      lc rx, n 0110 rx n n       4 0 1 5
      ll rx, n 1110 rx n n n n   6 0 1 7
      fork X111 X000           2 81 1 84
      push rx X111 X001 rx         3 2 1 6
      pop rx X111 X010 rx         3 2 1 6
      jmp rx X111 X011 rx         3 20 1 24
      fl rx, [ry] X111 X100 rx ry       4 5 P + 1 P + 10
      write rx X111 X101 rx         3 0 1 4
      stat rx, n X111 X110 rx n       4 5 1 10




    Fonctionnement des parties

      Fonctionnement de la VM

        vm [-help] [-ms n] [-mp n] [-im n] [-cy n] [-nl n] [-cd n] [-t] [file 1 ...[file n]]

        • -help : affiche l'aide du programme. Si cette option est rencontrée, la machine virtuelle ne fera rien d'autre.
        • -ms n : permet d'indiquer la taille de la mémoire (8192 par defaut).
        • -mp n : permet d'indiquer le nombre maximum de processeurs par joueur (2048 par défaut).
        • -im n : permet d'indiquer la constante IDX_MOD (128 par défaut).
        • -cy n : permet d'indiquer CYCLE_TO_DIE du début de partie (1554 par défaut).
        • -nl n : permet d'indiquer la constante NBR_LIVE (700 par defaut).
        • -cd n : permet d'indiquer la constante CYCLE_DELTA (1 par défaut).
        • -t : active le mode trace (celui-ci affiche les instructions quand elles ont été décodées).
        • file n : liste des champions participant a la partie. Si elle est vide, renvoyer un message d'erreur.

        Les fichiers des champions peuvent être des .cor générés par l'assembleur. Les options numériques devront être non-nulles.

      Déroulement d'une partie

        Dans chaque partie, plusieurs champions vont s'affronter. L'espace mémoire va être entièrement initialisé à 0x0 et le code des différents champions va être copié en mémoire. Le première sera à l'adresse 0x0000 et les autres tous les taille mémoire / nombre joueurs quartets plus loin.

        Puis, un numéro de 1 à 15 va être attribué de manière unique (et laissée à votre discrétion) à chacun d'entre eux. Ce numéro va essentiellement servir pour les signes de vie. Au cours de la partie, les champions vont (devoir) émettre des signes de vie. Ceux-ci servent à déterminer le ou les vainqueurs. Comme cela sera expliqué plus loin, du point de vue du fonctionnement, les processeurs n'appartiennent pas aux joueurs, ils évoluent simplement dans la mémoire. Par contre, ils émettent des signaux de vie pour les joueurs, et le vainqueur est le joueur réel (tous les numéros ne sont pas attribués) pour lequel un signal de vie a été émis en dernier (si plusieurs signaux ont eu lieu au même cycle, il y a égalité).

        Enfin, un processeur est créé pour chaque joueur. Il sont initialisés de la manière suivante : PC contient l'adresse à laquelle le code a été copié, r0 contient le numéro du joueur, r1 à r15 valent 0x0000, P vaut 0x0, Z vaut 1 et les 16 niveaux de la pile contiennent 0x0000. L'arène, la zone de mémoire dans laquelle va se dérouler le combat, est initialisée pleine de 0 avant le chargement des différents champions en mémoire.

        La partie est ensuite lancée, les processeurs évoluent et appliquent les stratégies mises en place dans les codes des champions en interférant les uns avec les autres dans la mémoire. La partie se termine quand tous les processeurs sont détruits (ce qui arrive toujours) et le ou les gagnants sont annoncés.

      Fin de la partie

        En fin de partie, la machine virtuelle doit annoncer les vainqueurs. Elle le fera en affichant sur la sortie standard le ou les noms (.name) des éventuels champions gagnants, ainsi que leur numéro dans l'ordre sur la ligne de commande (on peut faire jouer un champion contre lui-même et ils auront le même nom). Aucun format particulier n'est imposé si ce n'est que le message doit rester sur une ligne. Cet affichage est obligatoire et ne dépend pas de l'option verbose.

        Exemples :

        Le champion Jesus42 (3) a gagné.
Les champions Fifi (1), Riri (2) et Loulou (3) sont vainqueurs.
Ces champions sont des larves, pas un seul n'a réussi à faire un live : pas de gagnant.

      Le parallélisme

        Pour ne pas favoriser de joueur en fonction de l'ordre de traitement des processeurs par la machine virtuelle, on va évoluer dans un système entièrement parallèle (comme la réalité). A chaque cycle, toutes les opérations vont être executées comme si elles avaient lieu exactement en même temps. Cela a une influence sur les signaux de vie et les écritures en mémoire. Nous en reparlerons au cas par cas dans les sections suivantes.

      Destruction des processeurs

        Au cours de la partie, les processeurs ne sont pas invulnérables, ils peuvent être détruits de deux façons :

        • en exécutant l'instruction die (un 0x00 est si vite arrivé)
        • en n'exécutant pas de live pendant un délai trop long

        En effet, les signaux de vie ne sont pas uniquement utilisés pour déterminer le gagnant, ils sont aussi indispensables à la survie des processeurs. Il y a un compteur dans la machine virtuelle nomme CYCLE_TO_DIE. Si à un cycle quelconque de la partie un processeur n'a pas exécuté un live quelconque (sauf live 0 bien sûr) depuis CYCLE_TO_DIE cycles ou plus, il est instantanément détruit. Les processeurs doivent donc régulierement exécuter live.

        Mais pour rendre la chose plus intéressante et pour limiter la durée des parties, CYCLE_TO_DIE va décroître au cours du jeu. En fait, plus les processeurs exécutent live, plus CYCLE_TO_DIE décroît. Il existe deux autres compteurs fixés nommés NBR_LIVE et CYCLE_DELTA qui peuvent etre précisés au lancement de la VM. Toutes les NBR_LIVE exécutions d'un live par un processeur quelconque, CYCLE_TO_DIE est décrementé de CYCLE_DELTA.

        Pour respecter le parallélisme, CYCLE_TO_DIE n'évolue pas juste au moment où un live est exécuté, mais à la fin du cycle, une fois que tout les live à faire ou toutes les lectures des compteurs ont eu lieu.

        Il est intéressant de noter que CYCLE_TO_DIE est global à la machine virtuelle, c'est-à-dire que tout live d'un processeur diminue la durée de vie de tout le monde...

        Les live prennent effet à la fin du dernier cycle d'exécution. Ceci a pour conséquence que les évolutions de CYCLE_TO_DIE se font en fin de cycle (sachant que tous les processeurs travaillent en parallèle). Donc toute lecture de cette valeur par stat n'est pas affectée par les live exécutés dans le même cycle. De plus, comme les tests de destruction des processeurs qui n'ont pas fait live depuis trop longtemps sont fait en debut de cycle, avant toute autre action, les die ne peuvent pas tuer les processeurs directement : il faut attendre le cycle suivant. Ces quelques précautions évitent que l'ordre de traitement des processeurs influe sur le déroulement.

      Le fork

        Comme nous venons de le voir, le nombre de processeurs peut décroître, mais il lui est aussi possible d'augmenter. En fait, cela est possible grâce à l'instruction fork. Cette instruction a pour but de dupliquer le processeur. A l'issue de celle-ci (fin du dernier cycle d'exécution), un nouveau processeur va être introduit dans la machine virtuelle entièrement identique - même le PC - à celui qui a exécuté le fork. La seule différence entre les deux est l'état du registre Z qui vaut 0 dans un processeur et 1 dans l'autre, ce qui permet de les différencier. Evidemment, il n'y a pas de notion de père ou de fils. Si le nombre maximal de processeurs est atteint, le fork échoue. C'est-à-dire qu'aucun nouveau processeur n'est crée. Il renvoie 0 dans Z, et ne prend pas moins de temps que s'il réussit.

      Le monde du relatif

        Comme cela a été précisé au début, les processeurs travaillent intégralement en relatif. Cela signifie que tous les accès mémoire et les sauts se font relativement au PC courant (donc à la fin de l'instruction qui fait une lecture, une écriture ou un saut). De plus, pour que cela fonctionne correctement, la mémoire est circulaire, c'est à dire que si elle mesure 1000 quartet, qu'un PC vaut 990 et que le processeur saute de 20 en avant, PC vaudra ensuite 10 et pas 1010.

        Or, comme on peut le constater dans la table instructions, les instructions classiques d'accès à la mémoire ou de saut utilisent dans leur calcul une constante nommée IDX_MOD. Cette valeur qui est précisée au lancement de la VM sert tout simplement à limiter la portée des lectures, écritures ou sauts en mémoire. Pour chacune des intructions classiques, un modulo IDX_MOD va être appliqué à la distance d'accès.

        Il existe cependant des instructions dites longues qui ne tiennent pas compte de cette limite pour la lecture et le saut en mémoire, mais elles sont plus grosses et plus lentes.

      Ecritures simultanées en mémoire

        Le problème est simple : que se passe-t-il lorsque plusieurs processeurs écrivent en mémoire au même endroit au même moment ? Pour respecter le parallélisme, un système de votes a été mis en place. Si un même quartet de la mémoire est affecté plusieurs fois au cours d'un même cycle, il y a un vote indépendant pour chacun des bits du quartet. Si l'on cherche à écrire plus de fois 0 que 1, un 0 est écrit, si l'on cherche à écrire plus de fois 1 que 0, un 1 est écrit, et s'il y a ballotage, la valeur actuelle du bit est conservée. C'est aussi simple que cela.

      Exécution des instructions

        L'exécution de chaque instruction se déroule en trois étapes :

        • La phase de décodage qui consiste à lire la mémoire en avançant le registre PC à raison d'1 quartet par cycle jusqu'à trouver l'instruction à exécuter (la mémoire peut changer pendant cette lecture, mais ce qui a déjà été lu est inviolable).
        • La phase de délai, où le processeur n'a extérieurement l'air de ne rien faire (on dira qu'il fait des calculs en interne, qu'il se prépare ou qu'il boit une tasse de thé).
        • La phase d'execution ou le processeur met à jour les registres affectés par l'instruction. Dans la théorie, pour les calculs ou les accès mémoire (c'est-à-dire partout où l'on a un temps d'exécution dépendant de P), les opérations sont faites cycle à cycle et les quartets sont donc modifiés un par un à raison d'un quartet par cycle (d'où P + 1) en commençant par le poids faible.

        Tous les codes ne sont pas définis par des instructions. Si un processeur tente d'exécuter une instruction inconnue, il peut avoir un comportement quelconque.

        Les quartets autre que ceux de 0 à P ne peuvent être affectés par des instructions qui travaillent en fonction de P. Le bout restant du registre que vous essayez de trafiquer est absent, parti en voyage dans un autre plan, ou s'il a rate sa navette spatiale, un dinosaure en carton pâte est venu monter la garde devant lui. Les quartets au-dessus de P sont sous protection démoniaque, personne ne peut les toucher, meme pas manu. L'affectation de Z dépend du résultat du calcul effectué par l'opération, c'est-à-dire le contenu du registre de destination après affectation du résultat.

        Les instructions asr, inc, dec, lsl et lsr interprètent les constantes en non signé. rol, live, lp, lc, ll et stat interprètent comme elles souhaitent car il n'y a pas de calculs, seules les valeurs comptent. P est toujours utilisé de manière non signée et dans le cas de lc, le bit de signe est propagé, c'est-à-dire le bit de poids le plus fort.

      Ordre des actions au cours d'un cycle

        Voici l'ordre dans lequel ont lieu les principales actions au cours d'un cycle :

        • Test de destruction des processeurs qui n'ont pas émis de signal de vie depuis trop longtemps
        • Exécution du cycle pour chaque processeur (lecture, délai ou exécution sauf pour les accès mémoire, les live et les fork)
        • Lectures en mémoire
        • Ecritures en mémoire en tenant compte des votes
        • Résolution des fork
        • Résolution des live et évolution de CYCLE_TO_DIE
        • Incrément du compteur de cycles

        On remarquera que les lectures ont lieu avant les écritures et que la résolution des live a lieu après lecture des compteurs. Naturellement, le premier cycle qu'exécutera la machine sera le cycle 0, et il sera incrémenté entre deux cycles.

      L'anti jeu

        A cause du système de CYCLE_TO_DIE pour limiter le temps des parties, il est possible d'appliquer une technique d'anti-jeu qui consiste à multiplier le nombre de processeurs de manière exponentielle puis de faire des live. La partie se termine alors très rapidement (CYCLE_TO_DIE passe en dessous de 0) et le joueur qui a appliqué cette méthode est quasiment sûr de gagner.

        Pour empêcher cela et parce que la VM tourne dans un environnement fini, le nombre de processeurs va être limité. Il y a beaucoup de méthodes pour éviter l'anti-jeu, nous avons choisi celle qui semblait la plus simple, la plus efficace et la plus juste.

        Entre processeurs et joueurs, du point de vue de l'exécution, il y a un lien d'appartenance assez faible (le premier processeur a le numéro du joueur dans r0 et chaque processeur peut demander à qui il appartient), les processeurs ne font qu'exécuter la mémoire. Si on change le code dans la mémoire, le processeur qui passe dessus fait ce qu'on veut.

        Par contre, en ce qui concerne les fork, le lien va être beaucoup plus fort. Chacun des joueurs va avoir droit à un nombre limite de processeurs. L'appartenance est héréditaire, c'est-à-dire que lorsqu'un processeur fait un fork, les 2 processeurs résultant appartiendront au même joueur que le processeur qui a fait le fork. Si au cours d'un cycle un ou plusieurs processeurs d'un même joueur termine leur fork et que cela fait dépasser le plafond, le ou les fork en question vont simplement échouer.

        Le vol d'une processeur d'un autre joueur devient alors très intéressant pour empêcher celui-ci de forker...

      L'accès aux compteurs de la machine virtuelle

        Comme la table des instructions l'indique, il existe une instruction stat qui permet de récuperer la valeur d'un compteur. Elle renvoie la valeur dans le registre que l'on lui passe en argument. Les compteurs suivants existent dans la VM :

        Compteur Description
        0 Renvoie la constante NBR_LIVE
        1 Renvoie la constante CYCLE_DELTA
        2 Renvoie la valeur actuelle de CYCLE_TO_DIE
        3 Renvoie la taille de la memoire
        4 Renvoie IDX_MOD
        5 Renvoie les 16 bits de poids faible du compteur de cycle
        6 Renvoie les 16 bits de poids fort du compteur de cycle
        7 Renvoie 42
        8 Renvoie le nombre de joueurs de la partie
        9 Renvoie le numéro du joueur qui possède le processeur qui fait le stat
        10 Renvoie le nombre maximum de processeurs par joueur
        11 Renvoie le nombre de processeurs courant pour le joueur qui possède le processeur qui fait le stat
        autre Indéterminé, peut renvoyer n'importe quoi

        Le premier cycle de la partie est le cycle 0.

    Format des fichiers .cor

      Votre assembleur, à partir d'un fichier source contenant des instructions en langage d'assemblage, devra générer un « binaire », un fichier contenant la traduction de votre code source en langage machine. Ces binaires porteront l'extension .cor. Les données vont y être stockées directement (et pas sous forme de texte). Si on l'édite avec un éditeur de texte, on verra un peu n'importe quoi.

      Le format de fichier est simple :

      • Un "magic number" sur 32 bits (en little endian bien sûr) valant COREWAR_EXEC_MAGIC
      • La taille du code en quartets sur 32 bits (toujours little endian)
      • Une zone de PROG_NAME_LENGTH caractères contenant le nom du programme (complété par des 0)
      • Une zone de PROG_COMMENT_LENGTH caractères contenant un commentaire (idem)
      • Le code du champion (little endian encore), auquel on ajoutera un 0 si le nombre de quartets est impair.
      A titre indicatif (voir le fichier data.h pour les valeurs exactes) :
        #define  COREWAR_EXEC_MAGIC  0x726f6342
        #define  PROG_NAME_LENGTH  64
        #define  PROG_COMMENT_LENGTH  256
      L'assembleur devra reconnaitre des directives ayant le format suivant :
      point directive arguments
      D'où le programme d'exemple :
        .name"zork"
        .comment"just a basic living program"
         lcr1, live-w+1
        :wst[r1], r0
         lcr2, live-j
        live:live0
        :jbzr2
      Pour le programme d'exemple du sujet, le debut du header suivi du code sera donc, octet par octet : 
        42 63 6F 72 0F 00 00 00 7A 6F 72 6B 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
..
61 50 51 06 2C F0 0B 20
      Le fichier doit donc faire 336 octets.

      N'oubliez pas que votre fichier est écrit par un PC, une Alpha ou une Sun. Le type de base de ces machines est l'octet. On adopte la convention qu'utilisent les humains, c'est-à-dire d'écrire d'abord dans le quartet de poids fort de l'octet, puis dans le quartet de poids faible. Donc, si vous avez a écrire les quartets 0x1 puis 0x2, l'octet qui contient ces deux quartets vaudra 0x12.




    Modalités de rendu

    • Le projet Krikkit War est à faire en quadrinome (à quatre personnes donc).
    • Le projet devra etre rendu dans un seul des 4 comptes, dans le répertoire ~/c/rendu/projs/corewar/vm
    • Le projet est à réaliser en C, et devra respecter strictement la norme EPITA.
    • Vous devrez créer un fichier "auteurs" qui contiendra les quatre logins (un par ligne). Ce fichier devra se trouver à la racine du répertoire de rendu, donc dans ~/c/rendu/projs/corewar/vm
    • Les droits sur le répertoire ~/c/rendu/projs de rendu devront être 700. Tous vos fichiers devront être en 600, sauf l'exécutable généré qui conservera les droits par défaut (surtout les droits d'exécution).
    • Vous devrez écrire un Makefile contenant les règles suivantes :
      Une règle clean qui effacera tous les objets et les exécutables.
      Une règle all qui compilera la machine virtuelle.
      La règle par défault sera all. Vous ne pouvez évidemment utiliser aucune fonction de la bibliothèque standard. Utilisez seulement les fonctions : open(), close(), read(), write(), malloc(), free(), realloc() et exit().
    • Le projet est à rendre pour le dimanche 13 Janvier 2002, a 04h42.
    • L'exécutable généré devra obligatoirement s'appeler « kvm ». Tout autre nom entrainera une note de 0, sans négociation possible.
    • Votre programme devra compiler ET fonctionner sur les trois architectures suivantes : alpha, sun, et i386. Ceci sous-entend que votre machine virtuelle doit fonctionner sur toutes les machines disponibles en salle machine, ainsi que sur tous les serveurs ALPHA.
    • Si vous essayez de détourner le sujet, ou de produire un résultat sans que votre code C n'en soit responsable, vous vous verrez attribuer la note de -42, pour tricherie.
    • Réfléchissez avant de poser dans les news plein de questions auxquelles les ACU sadiques seraient ravis de répondre "Maintenant, oui (c)".




    Documentation Complémentaire

      Vous disposez d'un newsgroup dédié au projet :

        epita.cours.c-unix.kriquet-wars


      (oui, le nom du newsgroup est bizarre, mais il est comme ca sur le serveur de news, on ne peut rien y changer, mes plus plates excuses à Douglas Adams. La confusion vient de ce qu'au bocal, il y a des gens qui ne savent pas écrire)


      Une FAQ sera peut-etre mise en place, nous vous indiquerons dans le newsgroup ad-hoc sa création et son emplacement.


      Les responsables du suivi et de la correction de ce projet sont vos acus préférés (oui, la vingtaine de gusses qui vous ont appris à nager pendant la piscine).





    - But what about the End of the Universe? We'll miss the big moment.
    - I've seen it. It's rubbish, said Zaphod, nothing but a gnab gib.
    - A what ?
    - Opposite of a big bang. Come on, let's get zappy.