Brevet FR2783065A1 — publié le 20000310

"Procédé de compression de code interprétable" Le procédé objet de la présente invention est du domaine des procédés de compression de code informatique. Elle concerne plus particulièrement les applications exécutées dans des cartes à puce et les dispositifs disposant d'un interpréteur de code, tel que machines virtuelles "Java". La technologie actuelle des microcircuits pour cartes à puce ne permet encore que de faibles capacités pour les différentes mémoires du microcircuit, ce qui incite à rechercher la diminution de la taille des applications chargées dans les mémoires de ces cartes à puce. Ces mémoires sont essentiellement de type soit non volatile modifiable (par exemple de type dit "EEPROM", "flash", etc.), soit non volatile non modifiable (par exemple de type dit "ROM"), soit mémoires vives à accès direct (de type dit " RAM"). On est donc en présence d'une limitation de capacité mémoire, ce qui limite également la taille et le nombre des applications réalisables avec les cartes à puce actuelles. La présente invention entend donc remédier à cet inconvénient en proposant un procédé de compression de code interprété mémorisé dans la carte à puce, de manière à réduire sensiblement la taille mémoire occupée par une application donnée. Selon un second objectif de l'invention, le procédé est simple de mise en oeuvre et rapide d'exécution. Il s'applique à des dispositifs de carte à puce existants sans modification. Le procédé selon l'invention est donc un procédé de réduction de taille mémoire occupé par le code d'une application, mémorisé dans un dispositif adapté au sein d'une carte dite "à puce", ladite carte étant dotée d'un interpréteur dit "machine virtuelle", I'application étant interprétée par la machine virtuelle, caractérisé en ce qu'il comporte les étapes suivantes: - lecture du code interprété de l'application, et reconnaissance, dans le code interprété, des séquences dupliquées à l'identique au moins deux fois, - pour au moins un groupe de séquences dupliquées de code interprété, définition d'une portion de code interprété identique à ces séquences dupliquées, appelée "séquence de compression", et mémorisation de cette séquence de compression (SDC), - remplacement d'au moins une séquence dupliquée d'un groupe de séquences dupliquées dans le code interprété original par une séquence d'appel de la séquence de compression (SDC) correspondante. On comprend que l'utilisation de compression de code dans le domaine des applications de carte à puce répond au problème de limitation de capacité mémoire de ces cartes. Par ailleurs, cette disposition repose sur une analyse par séquences d'octets, au contraire des techniques classiques de compression, qui "travaillent" sur des séquences de bits, sans tenir compte de leur signification. La méthode proposée tient compte de ce que les séquences d'octets du code interprété représentent les instructions d'une machine virtuelle. On note également que ce procédé permet effectivement de réduire la taille occupée par une application écrite en code interprété par une machine virtuelle implémentée dans une carte à puce, sans augmentation significative du jeu d'instructions de la machine virtuelle. Selon une mise en oeuvre préférée, la séquence d'appel de la séquence de compression est un octet unique de code interprété réalisant l'appel de la séquence de compression. Cette disposition est favorable à une bonne réduction de taille du code interprété. Selon une mise en oeuvre préférée, la définition de séquence de compression est réalisée pour des groupes de séquences dupliquées de code interprété, vérifiant certains critères. Préférentiellement, les critères appliqués aux séquences dupliquées comportent en particulier les points suivants: - ne pas contenir d'instruction de saut aboutissant en dehors de la séquence de compression (SDC), - ne pas accepter qu'une instruction de saut aboutisse à l'intérieur d'une séquence de compression (SDC), - ne pas contenir de code résultant de l'exécution de code interprété en sous-programme. Ces dispositions permettent de réaliser une implémentation du procédé restreinte aux cas de compression simples. La description et les dessins qui suivent permettront de mieux comprendre les buts et avantages de l'invention. Il est clair que cette description est donnée à titre d'exemple, et n'a pas de caractère limitatif. Dans les dessins: - les figures la et lb représentent schématiquement un code interprété avant (figure la) et après (figure lb) mise en oeuvre du procédé; - la figure 2 représente la table des pointeurs et la zone des séquences de compression dans la mémoire du microcircuit. Dans le cadre de la description donnée ici à titre non limitatif, l'assemblage décrit est celui d'une carte plastique de type " carte à puce " à machine virtuelle, de type connu de l'homme de l'art, dans lesquelles des applications interprétées sont chargées dynamiquement dans la mémoire non volatile modifiable du microcircuit (par exemple de type dit "EEPROM" ou "Flash"). Elle s'applique tout aussi bien aux applications interprétées inscrites en fabrication dans la mémoire non volatile non modifiable du microcircuit (de type ROM). Le procédé réalise la compression du code d'une application interprété destiné à être mémorisé dans une carte dite à puce dotée d'un interpréteur ("machine virtuelle"). Le procédé est alors mis en oeuvre de la manière suivante (par exemple par un système informatique dans lequel le code interprété est mémorisé selon une méthode et avec des dispositifs connus en soi): 1/ Le code interprété de l'application est tout d'abord parcouru, et on procède à une reconnaissance, dans le code interprété, des séquences (de longueur minimale 2 octets), dupliquées à l'identique au moins deux fois. Cette reconnaissance est réalisée selon des algorithmes connus de l'homme de métier et hors du champ de la présente invention. 2/ Pour chaque groupe de séquences dupliquées de code interprété, il est défini une portion de code interprété identique à ces séquences dupliquées, appelée "séquence de compression" (SDC), et on enregistre en mémoire au sein du microcircuit de la carte à puce cette séquence de compression, 3/ En revenant alors au code interprété original, on procède au remplacement de chaque séquence dupliquée dans le code interprété original par une séquence d'appel de la séquence de compression (SDC) correspondante. Tel que représenté sur la figure 1, une implémentation particulière du procédé selon l'invention consiste à désigner une séquence de compression (SDC) par la valeur N de l'index correspondant de la table des pointeurs (figure 2) sur la zone des SDC, et à ajouter les instructions suivantes au jeu d'instructions de la machine virtuelle: "appel court SDC n N", avec N compris entre 0 et 15, N faisant partie de l'octet d'instruction, constitué de 4 bits de code opératoire et de 4 bits représentant N, - "appel long SDC n N", avec N supérieur à 15, et nécessitant un octet d'opérande à la suite de l'octet d'instruction pour contenir N, - "retour de SDC". Cette troisième instruction, de longueur un octet, n'est d'ailleurs pas nécessaire dans le cas o les SDC sont stockées de manière contiguë dans I'espace mémoire réservé aux SDC, ce qui est le cas dans l'implémentation décrite, car la différence entre les valeurs des pointeurs sur deux séquences de compression consécutives SDCN+1 et SDCN fournit alors la longueur de la séquence SDCN, ce qui permet de déterminer le retour de SDCN sans l'aide d'instruction "retour de SDC". Dans cette implémentation, en supposant qu'un code interprété fait appel A fois à une séquence de compression SDCN contenant L octets, la réduction de taille de code interprété est de G octets par rapport au code sans création de séquence de compression, avec: G = A x L (taille mémoire dans le code interprété original) - A (octets d'appels à la SDCN insérés dans le code transformé) - L (longueur de la SDCN dans l'espace mémoire) - 1 (octet de retour de la SDCN) - 2 (octets de la table des pointeurs sur la SDCN), soit G = (A-l) x (L-1)-4 Par exemple, pour une séquence de compression comportant 4 octets et appelée 5 fois, le gain est de 8 octets. Il est évident que si le gain est inférieur à zéro, le code initial n'est pas transformé. Pour obtenir une implémentation simple, des restrictions sont imposées aux séquences de compression (SDC), et en particulier les suivantes: - ne pas contenir d'instruction de saut aboutissant en dehors de la SDC, - ne pas accepter qu'une instruction de saut aboutisse à l'intérieur d'une SDC (c'est-à-dire refuser de transformer en SDC des séquences au milieu desquelles aboutit une instruction de saut), - ne pas contenir de code résultant en l'exécution de code interprété en sous- programme (la récursivité des séquences de compression, c'est-à-dire I'appel d'une SDC dans une SDC, n'est pas supportée). L'appel de code natif reste néanmoins autorisé, - ne pas se terminer entre un code opératoire et son (ses) opérande(s). Une fois le code transformé selon le procédé décrit, ce code est mémorisé dans le microcircuit de la carte à puce à machine virtuelle de façon classique. On comprend que ce procédé présente l'avantage de ne pas augmenter significativement le jeu d'instructions de la machine virtuelle, à chaque création d'une séquence de compression, puisque le procédé n'ajoute que deux ou trois instructions nouvelles à la machine virtuelle. Il est à noter que les SDC se distinguent à la fois des sous-programmes et des macro-instructions. En effet, contrairement aux sous-programmes, I'appel à la SDC et le retour de la SDC n'utilisent pas la pile du microcircuit, et cette pile peut être dans des états différents lors de l'appel à la SDC et lors du retour de la SDC, (ce qui ne serait pas le cas avec un sous-programme classique). Vis-à-vis d'une macro- instruction, lors du traitement par un macro-processeur associé, la macro-instruction est remplacée par la séquence de code qu'elle représente, chaque fois qu'elle apparaît dans le code source initial. La portée de la présente invention ne se limite pas aux détails des formes de réalisation ci-dessus considérés à titre d'exemple, mais s'étend au contraire aux modifications à la portée de l'homme de l'art. li1 REVENDICATIONS 1. Procédé de réduction de taille mémoire occupé par le code d'une application, mémorisé dans un dispositif adapté au sein d'une carte dite "à puce", ladite carte étant dotée d'un interpréteur dit "machine virtuelle", l'application étant interprétée par la machine virtuelle, caractérisé en ce qu'il comporte les étapes suivantes: - lecture du code interprété de l'application, et reconnaissance, dans le code interprété, des séquences dupliquées à l'identique au moins deux fois, - pour au moins un groupe de séquences dupliquées de code interprété, définition d'une portion de code interprété identique à ces séquences dupliquées, appelée "séquence de compression", et mémorisation de cette séquence de compression (SDC), - remplacement d'au moins une séquence dupliquée d'un groupe de séquences dupliquées dans le code interprété original par une séquence d'appel de la séquence de compression (SDC) correspondante. 2. Procédé selon la revendication 1, caractérisé en ce que la séquence d'appel de la séquence de compression est un octet unique de code interprété réalisant l'appel de la séquence de compression. 3. Procédé selon la revendication 2, caractérisé en ce que la définition de séquence de compression est réalisée pour des groupes de séquences dupliquées de code interprété, vérifiant certains critères. 4. Procédé selon la revendication 3, caractérisé en ce que les critères appliqués aux séquences dupliquées comportent en particulier les points suivants: - ne pas contenir d'instruction de saut aboutissant en dehors de la séquence de compression (SDC), - ne pas accepter qu'une instruction de saut aboutisse à l'intérieur d'une séquence de compression (SDC), - ne pas contenir de code résultant en l'exécution de code interprété en sous-programme, - ne pas se terminer entre un code opératoire et son (ses) opérande(s).