FR2888012A1

FR2888012A1 - Executable code compression method for e.g. microprocessor with reduced instruction set computer architecture, involves forming addressing table permitting to locate compressed word lines in compressed word line block

Info

Publication number: FR2888012A1
Application number: FR0507028A
Authority: FR
Inventors: Didier Fuin
Original assignee: STMicroelectronics SA
Current assignee: STMicroelectronics SA
Priority date: 2005-07-01
Filing date: 2005-07-01
Publication date: 2007-01-05
Anticipated expiration: 2025-07-01
Also published as: FR2888012B1

Abstract

The method involves collecting compressed words of one of executable code lines in a compressed word line. An addressing table (13) permitting to locate compressed word lines in a compressed word line block (12), is formed. The table has an entry per group of a predefined number of compressed word lines. Each entry specifies a position of a first compressed word line in the block and respective lengths of compressed word lines of the group except a last compressed word line. The last line`s length is found by the position of the first compressed word line of a compressed word line group. Independent claims are also included for the following: (1) a method for decompression of code executable by a microprocessor and stored in a program memory zone in compressed form (2) a microprocessor comprising a unit for decompression of code executable by a microprocessor and stored in a program memory zone in compressed form.

Description

PROCEDES ET DISPOSITIFS DE COMPRESSION ET DEMETHODS AND DEVICES FOR COMPRESSION AND

DECOMPRESSION DE CODE EXECUTABLE PAR UN MICROPROCESSEUR A ARCHITECTURE RISC. DECOMPRESSION OF CODE EXECUTABLE BY MICROPROCESSOR WITH ARCHITECTURE RISC.

La présente invention concerne le domaine de la compression de code exécutable par un microprocesseur. The present invention relates to the field of code compression executable by a microprocessor.

Elle s'applique notamment, mais non exclusivement, au code exécutable par les microprocesseurs à jeu d'instructions réduit RISC (Reduced Instruction Set Computer), par opposition aux microprocesseurs à architecture CISC (Complex Instruction Set Computer). It applies in particular, but not exclusively, to executable code by microprocessors Reduced Instruction Set Computer (RISC) reduced instruction set, as opposed to CISC microprocessors (Complex Instruction Set Computer).

Par rapport aux microprocesseurs à architecture CISC, les microprocesseurs RISC présentent l'avantage de posséder une architecture simplifiée, ce qui permet d'obtenir des vitesses d'exécution notablement supérieures, et de mettre en oeuvre des compilateurs de code notablement plus simples que les microprocesseurs à jeu d'instructions complexe. En contrepartie, les programmes écrits pour les microprocesseurs à architecture RISC sont notablement plus volumineux, typiquement de 20 à 50 %. Il en résulte une augmentation du temps de chargement du programme en vue de son exécution, des ressources mémoire nécessaires pour stocker le programme, ainsi que de la bande passante nécessaire si le programme doit être transmis par un réseau. Compared to CISC-based microprocessors, RISC microprocessors have the advantage of having a simplified architecture, which allows for significantly higher execution speeds, and to implement significantly simpler code compilers than microprocessors. to complex instruction set. In return, the programs written for RISC architecture microprocessors are significantly larger, typically 20 to 50%. This results in an increase in the loading time of the program for its execution, the memory resources needed to store the program, as well as the bandwidth required if the program is to be transmitted by a network.

Pour apporter une solution à ce problème, le brevet US 5 764 994 propose d'appliquer au code exécutable par de tels microprocesseurs des procédés de compression tels que Lempel-Ziv, basés sur la détection de répétitions de motifs, le code compressé étant ensuite décompressé à la volée au moment de son exécution par le microprocesseur. Toutefois, un tel code est difficile à compresser en raison du fait de la présence dans les instructions de code exécutable RISC de champs redondants qui ne contiennent pas d'information, mais réduisent l'efficacité du modèle de données construit durant la compression. En outre, les instructions de code exécutable RISC présentent différents formats, et utilisent de nombreux registres et des valeurs littérales, qui rendent difficile la détection de motifs répétés dans le code. To solve this problem, US Pat. No. 5,764,994 proposes to apply to the code executable by such microprocessors compression methods such as Lempel-Ziv, based on the detection of pattern repeats, the compressed code being then decompressed. on the fly at the time of its execution by the microprocessor. However, such code is difficult to compress due to the fact that RISC executable code instructions contain redundant fields that do not contain information, but reduce the efficiency of the data model built during compression. In addition, the RISC executable code statements have different formats, and use many registers and literal values, which make it difficult to detect repeated patterns in the code.

Les brevets US 6 618 506 et US 6 199 126 prévoient de décomposer le programme exécutable à compresser en deux sous-ensembles comprenant 2888012 -2- respectivement le champ de code d'opération et le champ opérande de chaque instruction, puis d'effectuer une analyse statistique de chaque sous-ensemble afin d'évaluer des fréquences d'apparition de symboles. Ensuite, on attribue à chaque symbole un code dont la taille est plus petite pour les symboles ayant une fréquence d'apparition élevée dans le sous-ensemble, et on constitue une table de correspondance entre les symboles et les codes attribués aux symboles. Chaque code comprend un préfixe associé soit à un index soit à la valeur du symbole selon la valeur du préfixe. Dans le cas où le préfixe est suivi d'un index, le préfixe désigne un groupe de symboles dans la table de correspondance et l'index précise la position du symbole correspondant dans le groupe. Enfin, chaque champ des instructions du code exécutable est remplacé par le code correspondant tel que spécifié dans la table de correspondance pour obtenir le programme sous forme compressée. US Pat. Nos. 6,618,506 and 6,199,126 provide for decomposing the executable program to be compressed into two subsets comprising respectively the operation code field and the operand field of each instruction, and then performing a statistical analysis of each subset to evaluate symbol occurrence frequencies. Next, each symbol is assigned a code whose size is smaller for the symbols having a high occurrence frequency in the subset, and a correspondence table is established between the symbols and the codes assigned to the symbols. Each code includes a prefix associated with either an index or the value of the symbol according to the value of the prefix. In the case where the prefix is followed by an index, the prefix designates a group of symbols in the correspondence table and the index specifies the position of the corresponding symbol in the group. Finally, each field of the executable code instructions is replaced by the corresponding code as specified in the correspondence table to obtain the program in compressed form.

Pour optimiser la place mémoire occupée par le programme compressé, les codes de longueur variable sont mémorisés les uns à la suite des autres sans être alignés sur des mots mémoire. Pour pouvoir être décompressé à la volée à partir d'une adresse d'instruction requise par le microprocesseur, le programme est compressé par blocs de 64 octets (16 instructions de 32 bits), et une table d'index est générée pour pouvoir accéder directement à chaque bloc compressé. To optimize the memory space occupied by the compressed program, the variable length codes are stored one after the other without being aligned with memory words. To be decompressed on the fly from an instruction address required by the microprocessor, the program is compressed in blocks of 64 bytes (16 32-bit instructions), and an index table is generated for direct access. to each compressed block.

Il s'avère que cette solution n'est pas non plus optimum en terme d'occupation de la mémoire. En effet, il est nécessaire que chaque bloc d'instructions compressé soit aligné sur les mots mémoire de l'espace d'adressage, ce qui laisse à la fin de chaque bloc, des emplacements inoccupés d'autant plus importants que les blocs choisis sont grands ou d'autant plus nombreux que les blocs sont choisi petits. En outre, la table d'index est relativement volumineuse puisqu'elle occupe 32 bits (4 octets) par bloc de 64 octets, ce qui pénalise d'une manière importante l'efficacité de la compression. It turns out that this solution is also not optimal in terms of memory occupancy. Indeed, it is necessary that each compressed block of instructions is aligned with the memory words of the address space, leaving at the end of each block, unoccupied locations all the more important that the blocks chosen are larger or more so than the blocks are chosen small. In addition, the index table is relatively large since it occupies 32 bits (4 bytes) per block of 64 bytes, which significantly penalizes the efficiency of the compression.

En outre, cette solution dégrade les performances en termes de vitesse d'exécution du programme. Cette dégradation provient du fait que les instructions compressées sont de taille variable et donc qu'il n'est pas possible de décompresser une instruction d'un bloc avant d'avoir déterminé la longueur de l'instruction compressée précédente. Cette solution ne permet donc pas d'effectuer certaines opérations de décompression en parallèle. In addition, this solution degrades the performance in terms of speed of execution of the program. This degradation is due to the fact that the compressed instructions are of variable size and therefore it is not possible to decompress an instruction of a block before having determined the length of the preceding compressed instruction. This solution therefore makes it impossible to perform certain decompression operations in parallel.

La présente invention a pour but de supprimer ces inconvénients. Cet objectif 2888012 -3- est atteint par la prévision d'un procédé de compression de code exécutable par un microprocesseur, comprenant des étapes de: décomposition du code exécutable en mots, division du code exécutable en lignes d'un nombre prédéfini d'instructions, compression de chaque mot de chaque ligne de code exécutable code exécutable sous la forme d'un mot compressé de longueur variable, les mots compressés d'une ligne de code exécutable étant rassemblés dans une ligne de mots compressés, et constitution d'une table d'adressage permettant de localiser chacune des lignes de mots compressés dans un bloc de lignes de mots compressés. The present invention aims to eliminate these disadvantages. This objective is achieved by the provision of a method for compressing code executable by a microprocessor, comprising steps of: decomposing the executable code into words, division of the executable code into lines of a predefined number of instructions compressing each word of each line of executable code executable code into a variable length compressed word, the compressed words of an executable code line being gathered in a compressed word line, and forming a table addressing method for locating each of the compressed word lines in a block of compressed word lines.

Selon l'invention, la table d'adressage comprend une entrée par groupe d'un nombre prédéfini de lignes de mots compressés, chaque entrée spécifiant la position d'une première ligne de mots compressés dans le bloc, et les longueurs respectives des lignes de mots compressés du groupe, sauf une dernière ligne de mots compressés du groupe, dont la longueur est déterminée à l'aide de la position d'une première ligne de mots compressés d'un groupe suivant de lignes de mots compressés. According to the invention, the addressing table comprises a group entry of a predefined number of compressed word lines, each entry specifying the position of a first line of compressed words in the block, and the respective lengths of the rows of words. compressed words of the group, except for a last line of compressed words of the group, the length of which is determined using the position of a first line of compressed words of a next group of compressed word lines.

Selon un mode de réalisation de l'invention, chaque mot du code exécutable est compressé en une partie de longueur fixe prédéfinie et une partie de longueur variable dont la longueur est définie par la partie de longueur fixe, toutes les parties de longueur fixe et toutes les parties de longueur variable étant regroupées respectivement dans un bloc de parties de longueur fixe et dans le bloc de mots compressés de longueur variable, chaque ligne de code exécutable étant compressée en une ligne de parties de longueur fixe et la ligne de mots compressés de longueur variable. According to an embodiment of the invention, each word of the executable code is compressed into a predefined fixed length portion and a variable length portion whose length is defined by the fixed length portion, all fixed length portions and all fixed length portions. the variable length portions being respectively grouped in a block of fixed length parts and in the variable length word block, each line of executable code being compressed into a line of fixed length parts and the compressed word line of length variable.

Avantageusement, chacun des mots du code exécutable à compresser correspond à une instruction. Advantageously, each of the words of the executable code to be compressed corresponds to an instruction.

Alternativement, le code exécutable est scindé en plusieurs parties contenant chacune un mot respectif de chaque instruction du code exécutable à compresser, le procédé étant appliqué séparément à chacune des parties de code exécutable, pour obtenir pour chaque mot d'instruction du code exécutable une partie de longueur fixe qui est insérée dans le bloc de parties de longueur fixe et une partie de longueur variable qui est insérée dans le bloc de parties de longueur variable. Alternatively, the executable code is divided into several parts each containing a respective word of each instruction of the executable code to be compressed, the method being applied separately to each of the executable code parts, to obtain for each instruction word executable code a part of fixed length which is inserted into the block of fixed length parts and a variable length part which is inserted into the block of variable length parts.

Selon un mode de réalisation de l'invention, l'étape de compression comprend des étapes consistant à : constituer un histogramme donnant pour chaque mot distinct du code exécutable un nombre d'occurrences de ce mot dans le code exécutable, et extraire au moins une partie des mots de l'histogramme dans une table de décompression, dans laquelle les mots sont répartis en sous-tables rassemblant des mots ayant des nombres d'occurrences voisins dans l'histogramme, chaque sous-table étant associée à une longueur prédéfmie, la partie de longueur fixe de chaque mot du code exécutable référençant une sous-table de la table de décompression, et la partie de longueur variable donnant une position dans la sous-table de décompression du mot du code According to one embodiment of the invention, the compression step comprises the steps of: constituting a histogram giving for each word distinct from the executable code a number of occurrences of this word in the executable code, and extracting at least one part of the words of the histogram in a decompression table, in which the words are subdivided into sub-tables gathering words having numbers of neighboring occurrences in the histogram, each sub-table being associated with a predefined length; fixed length portion of each executable code word referencing a sub-table of the decompression table, and the variable length portion giving a position in the code word decompression sub-table

exécutable.executable.

Avantageusement, les mots du code exécutable associés dans l'histogramme à un nombre d'occurrences inférieur à un seuil prédéterminé ne sont pas insérés dans la table de décompression, chaque mot de code exécutable non inséré dans la table de décompression étant compressé à l'aide d'une partie de longueur fixe spécifiant que le mot de code exécutable ne figure pas dans la table de décompression, et une partie de longueur variable contenant au moins une partie du mot de code exécutable. Advantageously, the words of the executable code associated in the histogram with a number of occurrences lower than a predetermined threshold are not inserted in the decompression table, each executable code word not inserted in the decompression table being compressed at the same time. using a fixed-length portion specifying that the executable code word does not appear in the decompression table, and a variable-length portion containing at least a portion of the executable code word.

Selon un mode de réalisation de l'invention, si deux mots de code exécutable identiques apparaissent consécutivement dans le code exécutable à compresser, le second mot de code exécutable est compressé sans partie de longueur variable, à l'aide d'une partie de longueur fixe spécifiant que le mot de code exécutable est le même que le mot précédent. According to one embodiment of the invention, if two identical executable code words consecutively appear in the executable code to be compressed, the second executable code word is compressed without a variable length part, using a length part fixed specifying that the executable code word is the same as the previous word.

Selon un mode de réalisation de l'invention, la partie de longueur fixe de chaque mot compressé spécifie selon sa valeur: soit un numéro de soustable de la table de décompression, soit que le mot du code exécutable correspondant est le second mot de deux mots consécutifs identiques du code exécutable, soit que la partie de longueur variable du mot compressé contient au moins une partie du mot de code exécutable correspondant. According to one embodiment of the invention, the fixed length portion of each compressed word specifies according to its value: either a subtable number of the decompression table, or that the word of the executable code corresponding to the second word of two words identical consecutive executable code, or that the variable length portion of the compressed word contains at least a portion of the corresponding executable code word.

2888012 5 Selon un mode de réalisation de l'invention, une valeur prédéfinie de la partie de longueur fixe d'un mot compressé spécifie un point d'arrêt à introduire dans le code exécutable lors d'une phase de test du programme. According to one embodiment of the invention, a predefined value of the fixed length portion of a compressed word specifies a breakpoint to be introduced into the executable code during a test phase of the program.

Selon un mode de réalisation de l'invention, la division en sous-tables de la table de décompression est choisie de manière à obtenir une taille de l'ensemble des parties de longueur variable du code compressé la plus petite possible. According to one embodiment of the invention, the division into sub-tables of the decompression table is chosen so as to obtain a size of all the parts of variable length of the compressed code as small as possible.

Selon un mode de réalisation de l'invention, le code exécutable est scindé en plusieurs parties contenant chacune un mot respectif de chaque instruction du code exécutable à compresser, le procédé étant appliqué séparément à chacune des parties de code exécutable, pour obtenir une table de décompression pour chaque partie du code exécutable. According to one embodiment of the invention, the executable code is divided into several parts each containing a respective word of each instruction of the executable code to be compressed, the method being applied separately to each of the executable code parts, to obtain a table of decompression for each part of the executable code.

L'invention concerne également un procédé de décompression de code exécutable par un microprocesseur, stocké dans une zone mémoire programme sous forme compressée, le procédé de décompression comprenant des étapes consistant à : déterminer une adresse de lecture d'une table d'adressage en fonction d'une adresse d'instruction à exécuter, la table d'adressage permettant de localiser des lignes de mots compressés dans un bloc de lignes de mots compressés, lire à l'adresse de lecture dans la table d'adressage des informations d'adressage dans le bloc de lignes de mots compressés, déterminer en fonction des informations d'adressage lues une adresse de lecture dans le bloc de lignes de mots compressés, lire le bloc de lignes de mots compressés à l'adresse de lecture déterminée, et décompresser au moins une ligne de mots compressés lue pour obtenir des 30 instructions exécutables. The invention also relates to a method for decompressing executable code by a microprocessor, stored in a program memory zone in compressed form, the decompression method comprising the steps of: determining a read address of an address table based on of an instruction address to be executed, the address table for locating compressed word lines in a block of compressed word lines, read at the read address in the address addressing information table in the compressed word line block, determining according to the read address information read a read address in the block of compressed word lines, read the block of compressed word lines at the determined read address, and decompress at minus one compressed word line read to obtain executable instructions.

2888012 6 Selon un mode de réalisation de l'invention, chaque mot du code exécutable est compressé sous la forme d'une partie de longueur fixe prédéfinie et d'une partie de longueur variable dont la longueur est définie par la partie de longueur fixe, toutes les parties de longueur fixe et toutes les parties de longueur variable des mots de code exécutable étant regroupés respectivement dans un bloc de parties de longueur fixe et dans le bloc de mots compressés de longueur variable, chaque ligne de code exécutable étant compressée en une ligne de parties de longueur fixe et la ligne de mots compressés de longueur variable, le procédé comprenant en outre des étapes de: détermination d'une adresse de lecture d'une ligne de parties de longueur fixe en fonction de l'adresse d'instruction à exécuter, lecture de la ligne de parties de longueur fixe à l'adresse déterminée, et 15 décompression des lignes de parties de longueur fixe et variable lues pour obtenir une ligne d'instructions exécutables. According to one embodiment of the invention, each word of the executable code is compressed in the form of a predefined fixed length portion and a variable length portion whose length is defined by the fixed length portion, all of the fixed length portions and all variable length portions of the executable code words being respectively grouped in a block of fixed length portions and in the variable length compressed word block, each line of executable code being compressed in one line fixed length portions and the compressed variable length word line, the method further comprising steps of: determining a read address of a line of fixed length portions based on the instruction address to execute, read the line of fixed length parts at the determined address, and decompress the lines of fixed and variable length portions read to obtain a e line of executable instructions.

Selon un mode de réalisation de l'invention, la partie de longueur fixe de chaque instruction compressée référence une sous-table d'une table de décompression rassemblant au moins une partie des mots du code exécutable, la partie de longueur variable donnant la position dans la sous-table du mot de code exécutable, la décompression d'une partie de longueur fixe et d'une partie de longueur variable correspondante comprenant des étapes de: détermination de la longueur de la partie de longueur variable en fonction de la valeur de la partie de longueur fixe correspondante, lire la partie de longueur variable correspondante compte tenu de la longueur déterminée de la partie de longueur variable, et si la partie de longueur fixe référence une sous-table de la table de décompression, lire le mot de code exécutable dans la sous-table de la table de décompression référencée par la partie de longueur fixe lue, à une position défraie par la partie de longueur variable lue. According to one embodiment of the invention, the fixed length portion of each compressed instruction references a sub-table of a decompression table gathering at least a part of the words of the executable code, the variable length part giving the position in the sub-table of the executable code word, the decompression of a fixed length portion and a corresponding variable length portion comprising steps of: determining the length of the variable length portion according to the value of the corresponding fixed length part, read the corresponding variable length part taking into account the determined length of the variable length part, and if the fixed length part references a sub-table of the decompression table, read the executable code word in the sub-table of the decompression table referenced by the fixed length portion read, at a deferred position by the variable length portion read.

Selon un mode de réalisation de l'invention: si la partie de longueur fixe indique que le mot de code exécutable correspondant est un second mot de deux mots identiques apparaissant consécutivement dans le code exécutable, la partie de longueur fixe est 2888012 -7- décompressée par le mot de code exécutable précédemment décompressé; si la partie de longueur fixe spécifie que le mot de code exécutable correspondant ne figure pas dans la table de décompression, le procédé comprend en outre des étapes d'extraction d'au moins une partie du mot de code exécutable de la partie de longueur variable correspondant à la partie de longueur fixe; si la partie de longueur fixe spécifie un point d'arrêt, un point d'arrêt est inséré dans le code exécutable décompressé. According to one embodiment of the invention: if the fixed-length portion indicates that the corresponding executable code word is a second word of two identical words appearing consecutively in the executable code, the fixed-length portion is uncompressed 2888012 -7- by the executable codeword previously uncompressed; if the fixed length portion specifies that the corresponding executable codeword is not present in the decompression table, the method further includes steps of extracting at least a portion of the executable code word from the variable length portion corresponding to the fixed length portion; if the fixed-length portion specifies a breakpoint, a breakpoint is inserted into the uncompressed executable code.

Avantageusement, chacun des mots de code exécutable décompressé correspond à une instruction. Advantageously, each of the decompressed executable code words corresponds to an instruction.

Alternativement, le code exécutable est scindé en plusieurs parties contenant chacune un mot respectif de chaque instruction du code exécutable à compresser, chaque partie du code exécutable ayant été compressée séparément et étant associée à une table de décompression respective rassemblant des mots de code exécutable de la partie du code exécutable. Alternatively, the executable code is divided into several parts, each containing a respective word of each instruction of the executable code to be compressed, each part of the executable code having been compressed separately and being associated with a respective decompression table gathering executable code words from the executable code. part of the executable code.

L'invention concerne également une unité de décompression de code 20 exécutable par un microprocesseur, stocké dans une zone mémoire programme sous forme compressée, l'unité de décompression étant connectée au microprocesseur et comprenant: des moyens pour recevoir du microprocesseur des requêtes d'instructions de code exécutable comportant une adresse d'instruction à exécuter, des moyens pour déterminer une adresse de lecture d'une table d'adressage en fonction de l'adresse d'instruction à exécuter, la table d'adressage permettant de localiser des lignes de mots compressés dans un bloc de lignes de mots compressés stocké dans la mémoire programme, de moyens pour lire à l'adresse de lecture dans la table d'adressage des informations d'adressage dans le bloc de lignes de mots compressés, des moyens pour déterminer en fonction des informations d'adressage lues une adresse de lecture dans le bloc de lignes de mots compressés et une longueur d'une ligne de mots compressés dans la mémoire programme, correspondant à l'adresse d'instruction fournie par le microprocesseur, des moyens pour lire la ligne de mots compressés à l'adresse de lecture déterminée, et des moyens pour décompresser la ligne de mots compressés lue pour obtenir des instructions exécutables. The invention also relates to a code decompression unit 20 executable by a microprocessor, stored in a program memory zone in compressed form, the decompression unit being connected to the microprocessor and comprising: means for receiving requests for instructions from the microprocessor executable code comprising an instruction address to be executed, means for determining a read address of an address table according to the instruction address to be executed, the addressing table for locating compressed words in a block of compressed word lines stored in the program memory, means for reading at the read address in the addressing table addressing information in the block of compressed word lines, means for determining according to the addressing information read a read address in the block of compressed word lines and a length of a word line co stored in the program memory, corresponding to the instruction address provided by the microprocessor, means for reading the line of compressed words at the determined reading address, and means for decompressing the compressed word line read to obtain executable instructions.

Selon un mode de réalisation de l'invention, l'unité de décompression comprend en outre: une mémoire cache pour stocker un nombre prédéfini d'instructions 15 décompressées, et des moyens pour lire la mémoire cache à la suite de la réception d'une requête d'instructions émise par le microprocesseur, et pour transmettre en réponse les instructions correspondantes si celles-ci se trouvent dans la mémoire cache. According to an embodiment of the invention, the decompression unit further comprises: a cache memory for storing a predefined number of decompressed instructions, and means for reading the cache memory as a result of receiving a instruction request issued by the microprocessor, and to transmit in response the corresponding instructions if they are in the cache memory.

Selon un mode de réalisation de l'invention, chaque mot du code exécutable est compressé sous la forme d'une partie de longueur fixe prédéfinie et d'une partie de longueur variable dont la longueur est définie par la partie de longueur fixe, toutes les parties de longueur fixe et toutes les parties de longueur variable des mots de code exécutable étant regroupés respectivement dans un bloc de parties de longueur fixe et dans le bloc de mots compressés de longueur variable, chaque ligne de code exécutable étant compressée en une ligne de parties de longueur fixe et la ligne de mots compressés de longueur variable, l'unité de décompression comprenant en outre: des moyens pour déterminer la position dans la mémoire programme de la ligne de parties de longueur fixe contenant les mots de code compressé correspondant à l'adresse d'instruction fournie par le microprocesseur, des moyens pour lire le bloc de parties de longueur fixe à l'adresse de lecture déterminés, des moyens pour décompresser les parties de longueur fixe et variable lues pour obtenir une instruction exécutable, et des moyens pour transmettre au microprocesseur l'instruction décompressée. According to an embodiment of the invention, each word of the executable code is compressed in the form of a predefined fixed length portion and a variable length portion whose length is defined by the fixed length portion, all fixed-length portions and all variable-length portions of the executable code words being respectively grouped in a block of fixed-length portions and in the variable-length compressed word block, each line of executable code being compressed into a line of parts of fixed length and the line of compressed words of variable length, the decompression unit further comprising: means for determining the position in the program memory of the line of fixed length portions containing the compressed code words corresponding to the instruction address provided by the microprocessor, means for reading the block of fixed length portions at the determined read address, means for decompressing the fixed and variable length portions read to obtain an executable instruction, and means for transmitting to the microprocessor the decompressed instruction.

Selon un mode de réalisation de l'invention, l'unité de décompression comprend en outre des moyens pour mémoriser des adresses de début du bloc de parties de longueur fixe et du bloc de parties de longueur variable du code compressé, et une adresse de début de la table d'adressage. According to an embodiment of the invention, the decompression unit further comprises means for storing start addresses of the block of fixed length portions and the block of variable length parts of the compressed code, and a start address. of the addressing table.

Selon un mode de réalisation de l'invention, au moins certaines parties de longueur fixe référencent une sous-table d'une table de décompression rassemblant au moins une partie des mots du code exécutable, la partie de longueur variable donnant la position dans la sous-table du mot de code exécutable, l'unité de décompression comprenant en outre: des moyens de stockage d'une table de décompression, des moyens pour déterminer la position du mot de code exécutable à lire dans la table de décompression à partir de la partie de longueur fixe et de la partie de longueur variable, si la partie de longueur fixe référence une sous-table de la table de décompression, et des moyens pour lire le mot de code exécutable à la position déterminée dans la sous-table. According to one embodiment of the invention, at least some fixed length parts reference a sub-table of a decompression table gathering at least a part of the words of the executable code, the variable length part giving the position in the sub-table. executable code word table, the decompression unit further comprising: storage means of a decompression table, means for determining the position of the executable code word to be read in the decompression table from the fixed length portion and variable length portion, if the fixed length portion references a sub-table of the decompression table, and means for reading the executable code word at the determined position in the sub-table.

Selon un mode de réalisation de l'invention, l'unité de décompression comprend en outre des moyens pour transmettre au microprocesseur un mot de code exécutable précédemment décompressé si la partie de longueur fixe indique que le mot de code exécutable correspondant est un second mot de deux mots identiques apparaissant consécutivement dans le code exécutable. According to one embodiment of the invention, the decompression unit further comprises means for transmitting to the microprocessor a previously decompressed executable code word if the fixed length portion indicates that the corresponding executable code word is a second word of two identical words appearing consecutively in the executable code.

Selon un mode de réalisation de l'invention, l'unité de décompression comprend en outre des moyens pour transmettre au microprocesseur la partie de longueur variable lue si la partie de longueur fixe spécifie que le mot de code exécutable correspondant ne figure pas dans la table de décompression. According to an embodiment of the invention, the decompression unit further comprises means for transmitting to the microprocessor the portion of variable length read if the fixed length portion specifies that the corresponding executable code word is not included in the table. decompression.

Selon un mode de réalisation de l'invention, l'unité de décompression comprend en outre des moyens pour transmettre au microprocesseur un point d'arrêt d'exécution de programme, si la partie de longueur fixe le spécifie. According to an embodiment of the invention, the decompression unit further comprises means for transmitting to the microprocessor a program execution stop point, if the fixed length part specifies it.

Selon un mode de réalisation de l'invention, chacun des mots de code exécutable décompressé correspond à une instruction. According to one embodiment of the invention, each of the executable code words decompressed corresponds to an instruction.

2888012 - 10- Selon un mode de réalisation de l'invention, le code exécutable est scindé en plusieurs parties contenant chacune un mot respectif de chaque instruction du code exécutable à compresser, chaque partie du code exécutable ayant été compressée séparément et étant associée à une table de décompression respective rassemblant des mots de code exécutable de la partie du code exécutable. According to one embodiment of the invention, the executable code is divided into several parts, each containing a respective word of each instruction of the executable code to be compressed, each part of the executable code having been compressed separately and being associated with a code. respective decompression table gathering executable code words from the part of the executable code.

L'invention concerne également un microprocesseur comportant une unité de décompression telle que définie ci-avant. The invention also relates to a microprocessor comprising a decompression unit as defined above.

Un mode de réalisation préféré de l'invention sera décrit ci-après, à titre d'exemple non limitatif, avec référence aux dessins annexés dans lesquels: La figure 1 représente schématiquement un système de 15 compression de code source binaire, selon l'invention; La figure 2 montre la structure d'une table d'adressage selon l'invention obtenue durant la compression; La figure 3 montre plus en détail sous la forme d'un organigramme une séquence de traitements de compression 20 exécutée par le système représenté sur la figure 1; La figure 4 montre la structure d'une table de décompression obtenue durant la compression effectuée conformément à la séquence de traitements illustrée sur la figure 3; La figure 5 montre plus en détail sous la forme d'un 25 organigramme une étape du traitement de compression illustré sur la figure 3; La figure 6 illustre sous la forme d'un organigramme un procédé de décompression selon l'invention; La figure 7 représente schématiquement l'architecture d'un 30 calculateur comportant une unité de décompression selon l'invention; 2888012 -11- La figure 8 représente schématiquement l'architecture de l'unité de décompression montrée sur la figure 7; La figure 9 montre la structure d'une page mémoire de programme compressé, selon l'invention; La figure 10 montre la structure d'une table de gestion de mémoire cache de l'unité de décompression représentée sur la figure 8. A preferred embodiment of the invention will be described hereinafter, by way of non-limiting example, with reference to the accompanying drawings in which: Figure 1 schematically shows a binary source code compression system, according to the invention ; Figure 2 shows the structure of an address table according to the invention obtained during compression; Fig. 3 shows in more detail in the form of a flowchart a sequence of compression processes executed by the system shown in Fig. 1; Fig. 4 shows the structure of a decompression table obtained during compression performed according to the processing sequence shown in Fig. 3; Fig. 5 shows in more detail as a flowchart a step of the compression process illustrated in Fig. 3; Figure 6 illustrates in the form of a flowchart a decompression method according to the invention; FIG. 7 schematically represents the architecture of a computer comprising a decompression unit according to the invention; Figure 8 schematically shows the architecture of the decompression unit shown in Figure 7; FIG. 9 shows the structure of a compressed program memory page, according to the invention; Fig. 10 shows the structure of a cache management table of the decompression unit shown in Fig. 8.

Sur la figure 1, le système de compression 1 selon l'invention est conçu pour traiter du code source binaire 2, c'est-à-dire exécutable par un microprocesseur, pour produire du code compressé, en utilisant un algorithme de compression du type "à longueur variable", basé sur la fréquence d'apparition des différents mots dans le code à compresser, des codes courts étant attribués aux mots à compresser les plus fréquents, et des codes plus longs aux mots à compresser les plus rares. L'algorithme choisi est par exemple issu de la méthode de Huffman. In FIG. 1, the compression system 1 according to the invention is designed to process binary source code 2, that is to say executable by a microprocessor, to produce compressed code, by using a compression algorithm of the type "variable length", based on the frequency of occurrence of different words in the code to compress, short codes are assigned to the most common words to compress, and longer codes to the words to compress the rarest. The chosen algorithm is for example derived from the Huffman method.

Le code source à compresser est traité par lignes DL de 32 ou 64 instructions, chaque ligne DL conduisant à l'obtention d'une ligne de mots compressés de longueurs variables VCL, une table d'adressage 13 étant constituée pour pouvoir accéder directement à au moins certains mots compressés, sans avoir à lire et décompresser tous les mots compressés précédents. The source code to be compressed is processed by DL lines of 32 or 64 instructions, each line DL leading to obtaining a line of compressed words of varying lengths VCL, an addressing table 13 being constituted in order to directly access the less some compressed words, without having to read and uncompress any previous compressed words.

Selon l'invention, la table d'adressage 13 est structurée de la manière illustrée sur la figure 2 en mots d'adressage référençant un groupe j de plusieurs lignes de parties variables, par exemple 4: VCLi(0), VCLL(l), VCLL(2) et VCL,(3). Chaque mot d'adressage mémorisé dans la table d'adressage 13 comprend la position Pi(0) en nombre de bits dans la partie variable 12 du début d'une première ligne VCLi(0), et les longueurs LL(0), LL(l), Li(2) en nombre de bits, des première, seconde et troisième lignes VCLL(0), VCLi(1) et VCLL(2). According to the invention, the addressing table 13 is structured in the manner illustrated in FIG. 2 into addressing words referencing a group j of several lines of variable parts, for example 4: VCLi (0), VCLL (l) , VCLL (2) and VCL, (3). Each address word stored in the addressing table 13 comprises the position Pi (0) in number of bits in the variable part 12 of the beginning of a first line VCLi (0), and the lengths LL (0), LL (l), Li (2) in number of bits, first, second and third lines VCLL (0), VCLi (1) and VCLL (2).

Les positions respectives PO), PP(2), Pi(3) en nombre de bits des seconde, troisième et quatrième lignes VCLi(1) VCLL(2) et VCLL(3) sont obtenues en additionnant la position Pi et la longueur Li de la partie fixe de la ligne précédente: Pi(k) = PP(k-1) + L;(k-1), pour k = 1 à 3 (1) 2888012 12- La longueur Li(3) de la quatrième ligne VCLL(3) est déduite de la position de la première ligne Pi+1(0) spécifiée dans le mot d'adressage référençant le groupe j+l des quatre lignes suivantes, et de la position P,(3) du quatrième groupe: L43) = PP+1(0) Pi(3) (2) 5 Chaque mot j de la table d'adressage 13 comporte par exemple 64 bits répartis dans les différents champs de la manière suivante: Bits 63 à 33: P ) Bits 32 à 22: Li (0) Bits 21 à 11: 4(1) Bits 10 à 0: Li(2) La table d' adressage 13 permet ainsi d'accéder directement à une ligne VCL de parties variables d'instructions compressées. Par comparaison avec les tables d'adressage décrites dans le brevet US 6 199 126, la table d'adressage selon l'invention permet d'adresser quatre lignes de 32 ou 64 instructions de 32 bits à l'aide de mots de 64 bits, ce qui augmente dans une relativement faible mesure la taille du code compressé. The respective positions PO), PP (2), Pi (3) in number of bits of the second, third and fourth lines VCLi (1) VCLL (2) and VCLL (3) are obtained by adding the position Pi and the length Li of the fixed part of the previous line: Pi (k) = PP (k-1) + L; (k-1), for k = 1 to 3 (1) 2888012 12- The length Li (3) of the fourth VCLL line (3) is deduced from the position of the first line Pi + 1 (0) specified in the addressing word referencing the group j + 1 of the following four lines, and the position P, (3) of the fourth group : L43) = PP + 1 (0) Pi (3) (2) Each word j of the addressing table 13 comprises for example 64 bits distributed in the different fields as follows: Bits 63 to 33: P) Bits 32 to 22: Li (0) Bits 21 to 11: 4 (1) Bits 10 to 0: Li (2) Addressing table 13 thus provides direct access to a VCL line of variable parts of compressed instructions . In comparison with the addressing tables described in US Pat. No. 6,199,126, the addressing table according to the invention makes it possible to address four lines of 32 or 64 32-bit instructions using 64-bit words. which increases in a relatively small measure the size of the compressed code.

Avantageusement, chaque mot du code exécutable compressé est décomposé sous la forme d'une partie de longueur fixe et d'une partie de longueur variable. Ensuite, toutes les parties de longueur fixe sont regroupées dans un bloc 11 d'instructions compressées de longueur fixe, et toutes les parties de longueur variable sont regroupées dans un bloc 12 de parties compressées de longueur variable, la table d'adressage 13 permettant d'accéder à au moins certains mots compressés rassemblés dans le bloc 12 de parties compressées de longueur variable, sans avoir à lire et décompresser toutes les parties précédentes dans le bloc. Advantageously, each word of the compressed executable code is decomposed into a fixed length portion and a variable length portion. Then, all the fixed length parts are grouped together in a block 11 of compressed instructions of fixed length, and all the variable length parts are grouped in a block 12 of compressed parts of variable length, the addressing table 13 allowing accessing at least some compressed words collected in block 12 of compressed lengthwise portions, without having to read and uncompress all previous parts in the block.

Lorsque le code source à compresser est traité par lignes DL de 32 ou 64 instructions, chaque ligne DL conduit donc à l'obtention d'une ligne de parties fixes FCL et d'une ligne de parties variables VCL. When the source code to be compressed is processed by DL lines of 32 or 64 instructions, each line DL thus leads to obtaining a line of fixed parts FCL and a line of variable parts VCL.

De cette manière, la position en mémoire de la partie fixe d'une instruction peut être déterminée directement en fonction de l'adresse de l'instruction dans le code exécutable, ce qui permet à la décompression de traiter en parallèle les parties de longueur fixe et variable. In this way, the memory position of the fixed part of an instruction can be determined directly according to the address of the instruction in the executable code, which allows the decompression to process the fixed length parts in parallel. and variable.

2888012 -13- L'algorithme de compression choisi est par exemple conforme à celui illustré sur la figure 3. A la première étape 31 de cet algorithme, le système 1 lit le code source binaire pour constituer un histogramme donnant pour chaque mot distinct du code source un nombre d'occurrences dans le code source de ce mot. Cet histogramme est constitué d'une table ordonnée par nombre d'occurrences décroissant. For example, the compression algorithm chosen is in accordance with that illustrated in FIG. 3. In the first step 31 of this algorithm, the system 1 reads the binary source code to form a histogram giving for each distinct word of the code source a number of occurrences in the source code of that word. This histogram consists of a table ordered by decreasing number of occurrences.

A l'étape suivante 32, le système construit une table de décompression 10 extraite de l'histogramme en rassemblant tous les mots distincts associés dans l'histogramme à un nombre d'occurrences supérieur à un seuil prédéfini. L'ordre des mots dans la table de décompression correspond à celui des mots dans l'histogramme. La table de décompression est ensuite divisée en sous-tables rassemblant des mots ayant des nombres d'occurrences voisins, c'est-à- dire dont la position dans la sous-table sera codée par un même nombre de bits. In the next step 32, the system constructs a decompression table 10 extracted from the histogram by gathering all the distinct words associated in the histogram with a number of occurrences greater than a predefined threshold. The order of the words in the decompression table corresponds to that of the words in the histogram. The decompression table is then divided into sub-tables gathering words having numbers of neighboring occurrences, that is, whose position in the sub-table will be encoded by the same number of bits.

A l'étape suivante 33, le code binaire source 2 est lu une nouvelle fois, pour compresser chaque mot du code binaire sous la forme d'une partie de longueur fixe, constante pour tous les mots du code exécutable à compresser, et d'une partie de longueur variable d'un mot à l'autre. Deux cas se présentent selon que le mot à compresser se trouve ou non dans la table de compression. In the next step 33, the source binary code 2 is read again, to compress each word of the binary code in the form of a fixed length part, constant for all the words of the executable code to be compressed, and of a part of variable length from one word to another. There are two cases depending on whether or not the word to compress is in the compression table.

Si le mot à compresser se trouve dans la table de compression 10, on applique le principe de compression illustré par la figure 4 qui montre la table de décompression 10 divisée en sous-tables 21 référencées chacune par un code BC respectif. Selon ce principe, la partie fixe du mot 25 résultant de la compression contient le code BC de sous-table de la table de décompression 10 dans laquelle se trouve le mot 22 à l'état décompressé, et la partie variable indique la position VLI de ce mot dans la sous-table. Dans l'exemple de la figure 4, le code BC de sous-table est codé sur 4 bits, de manière à pouvoir référencer jusqu'à 16 sous- tables.En pratique, certaines valeurs du code BC devront être réservées à d'autres usages comme le codage des mots du code source ne se trouvant pas dans la table de compression 10. If the word to compress is in the compression table 10, we apply the compression principle illustrated in Figure 4 which shows the decompression table 10 divided into sub-tables 21 each referenced by a respective BC code. According to this principle, the fixed part of the word 25 resulting from the compression contains the code BC of sub-table of the decompression table 10 in which the word 22 is in the decompressed state, and the variable part indicates the position VLI of this word in the sub-table. In the example of FIG. 4, the sub-table code BC is coded on 4 bits, so that up to 16 sub-tables can be referenced. In practice, some values of the BC code will have to be reserved for others. uses as the coding of the words of the source code not found in the compression table 10.

Si le mot à compresser ne se trouve pas dans la table de compression 10, la partie fixe du mot résultant de la compression contient un numéro BC non attribué à une sous-table 21, réservé à cet effet, et la partie variable contient le mot à compresser. If the word to be compressed is not in the compression table 10, the fixed part of the word resulting from the compression contains a number BC not assigned to a sub-table 21, reserved for this purpose, and the variable part contains the word to compress.

2888012 - 14- Si l'on peut réserver deux valeurs du code BC au codage des mots à compresser ne se trouvant pas clans la table de compression, on peut gagner un bit dans le codage du mot en considérant qu'un bit du code BC détermine un bit du mot à compresser. Par exemple le bit de poids faible du code BC est égal au bit de poids fort du mot à compresser. 2888012 - 14- If two values of the BC code can be reserved for the encoding of the words to be compressed not found in the compression table, one bit can be gained in the coding of the word by considering that one bit of the BC code determines a bit of the word to be compressed. For example, the least significant bit of the code BC is equal to the most significant bit of the word to be compressed.

Avantageusement, on réserve une valeur du code BC pour spécifier que le mot à compresser est le même que le mot précédent. De cette manière, si le code source à compresser comprend deux mots successifs identiques, le second mot est codé sans partie variable, sous la forme d'une seule partie fixe incluant le code BC réservé, spécifiant que le mot du code source est le même que le mot précédent. Advantageously, a value of the code BC is reserved to specify that the word to be compressed is the same as the preceding word. In this way, if the source code to be compressed comprises two identical successive words, the second word is coded without variable part, in the form of a single fixed part including the reserved code BC, specifying that the word of the source code is the same than the previous word.

Avantageusement, la division de la table de décompression 10 en soustables 21 est effectuée de manière à minimiser la taille du code compressé et en particulier la taille de la partie variable 12 du code compressé, sachant que la taille la partie fixe 11 du code compressé dépend du nombre d'instructions figurant dans le code source à compresser et de la longueur (en nombre de bits) choisie pour le code BC. Advantageously, the division of the decompression table 10 into subtables 21 is performed so as to minimize the size of the compressed code and in particular the size of the variable part 12 of the compressed code, given that the size of the fixed part 11 of the compressed code depends the number of instructions in the source code to be compressed and the length (in number of bits) chosen for the BC code.

Le code BC présente les fonctions suivantes: soit il spécifie un numéro de sous-table, soit il introduit un mot du code non compressé, soit il spécifie que le mot qu'il code est identique au mot précédent. On peut en outre prévoir de réserver une valeur du code BC pour introduire des points d'arrêts dans le code source binaire lors d'une phase de test du programme. The BC code has the following functions: either it specifies a sub-table number, it introduces a word of the uncompressed code, or it specifies that the word that it codes is identical to the previous word. It is furthermore possible to reserve a value of the code BC for introducing breakpoints in the binary source code during a test phase of the program.

La fonction du code BC en fonction de sa valeur est avantageusement définie dans une table 15 indexée en fonction de la valeur de BC, spécifiant soit la longueur L en nombre de bits de la partie variable VLI lorsque BC spécifie un numéro de sous-table 21, soit la longueur du mot non compressé lorsque BC introduit un mot non compressé, soit que le mot introduit par le code BC est identique au mot précédent, soit que la valeur de BC correspondante est un point d'arrêt. The function of the code BC according to its value is advantageously defined in a table 15 indexed according to the value of BC, specifying either the length L in number of bits of the variable part VLI when BC specifies a sub-table number 21 the length of the uncompressed word when BC introduces an uncompressed word, or the word introduced by the code BC is identical to the previous word, or the corresponding value of BC is a breakpoint.

La taille T de la partie variable 12 du code compressé est obtenue par la formule suivante: -15-N 1 Hi+1 T= EVi E Oi +(M HN) Vlitteral (3) i=0 j=Hi dans laquelle: N est le nombre de sous-tables 21 dans la table de décompression 10, Vi (0 i < N) est le nombre de bits choisis pour le codage de la position d'un mot dans la sous-table de décompression i (est directement lié au nombre de mots rassemblés dans la sous-table i), Hi est la position dans la table de décompression i (ou dans l'histogramme) du premier mot de la sous-table i, O; est le nombre d'occurrences du jième mot de la table de décompression (ou de l'histogramme), tel que fourni dans l'histogramme 9, M est le nombre de mots dans l'histogramme, HN est la taille en nombre de mots de la table de décompression, ou la position du premier mot dans l'histogramme qui ne figure pas dans la table de décompression, et Viitterai étant la longueur de codage d'un mot du code à compresser ne se trouvant pas dans la table de décompression. The size T of the variable part 12 of the compressed code is obtained by the following formula: ## EQU1 ## where: N is the number of sub-tables 21 in the decompression table 10, Vi (0 i <N) is the number of bits chosen for the coding of the position of a word in the decompression sub-table i (is directly related to the number of words collected in the sub-table i), Hi is the position in the decompression table i (or in the histogram) of the first word of the sub-table i, O; is the number of occurrences of the jth word of the decompression table (or histogram), as provided in the histogram 9, M is the number of words in the histogram, HN is the size in number of words of the decompression table, or the position of the first word in the histogram that is not in the decompression table, and Viitterai being the coding length of a codeword to be compressed that is not in the decompression table .

HN peut être calculé à l'aide de la formule suivante: N 1 V HN = 2 i=0 Si S est la taille maximum réservée à la table de décompression 10, HN S S. Si S est la taille maximum réservée à la table de décompression 10, HN 5 S. Si on peut réserver deux valeurs du code BC au codage des mots à compresser ne se trouvant pas dans la table de compression, la formule (3) devient: N 2 Hi+1 T = E Vi É 10i + (M HN) ' (Vlitteral -1) (5) i=0 De même, si on peut réserver une valeur du code BC pour spécifier que le mot à compresser est le même que le mot précédent, la formule (3) devient: N 2 Hi+1 T = V1 É OÉ + (M HN) V htteral (6) i=0 j=Hi (4) - 16- L'histogramme est modifié car deux mots consécutifs identiques ne comptent que pour un pour le nombre d'occurrences de ce mot. Ce qui conduit à considérer un nouvel histogramme et un nombre d'occurrences O'i. HN can be calculated using the following formula: N 1 V HN = 2 i = 0 If S is the maximum size reserved for the decompression table 10, HN S S. If S is the maximum size reserved for the table decompression 10, HN 5 S. If two values of the code BC can be reserved for the coding of the words to be compressed that are not in the compression table, the formula (3) becomes: N 2 Hi + 1 T = E Vi 10i + (M HN) '(Vlitteral -1) (5) i = 0 Similarly, if one can reserve a value of the code BC to specify that the word to be compressed is the same as the preceding word, the formula (3) becomes: N 2 Hi + 1 T = V1 E O E + (M HN) V htteral (6) i = 0 j = Hi (4) - 16- The histogram is modified because two identical consecutive words count only for one for the number of occurrences of this word. This leads to consider a new histogram and a number of occurrences O'i.

En combinant les deux conditions précédentes (réservation de deux valeurs du code BC au codage des mots à compresser ne se trouvant pas dans la table de compression et d'une valeur du code BC pour spécifier que le mot à compresser est le même que le mot précédent), la formule (1) devient: N 3 Hi+1 T = Vi E O + (M - HN) . (Vlitteral -1) i=0 j=Hi A l'aide des formules (3), (5), (6) et (7), on calcule T appliqué au code à compresser pour toutes les partitions possibles de la table de décompression en soustables, c'est-à-dire pour toutes les valeurs possibles de H;, en imposant que V. V;+i, c'est-à-dire que la taille de la sous-table i est inférieure ou égale à celle de la sous-table i+l. La partition choisie de la table de décompression en sous-tables est celle qui permet d'obtenir une taille T de partie variable minimum. On détermine ainsi les composantes V; du modèle de compression. By combining the two preceding conditions (reservation of two values of the code BC to the coding of the words to be compressed not found in the compression table and of a value of the code BC to specify that the word to be compressed is the same as the word previous), the formula (1) becomes: N 3 Hi + 1 T = Vi EO + (M - HN). (Vlitteral -1) i = 0 j = Hi Using formulas (3), (5), (6) and (7), one calculates T applied to the code to be compressed for all the possible partitions of the table of decompression into subtables, that is to say for all the possible values of H ;, by imposing that V. V; + i, that is to say that the size of sub-table i is less than or equal to to that of the sub-table i + l. The chosen partition of the decompression table into sub-tables is that which makes it possible to obtain a size T of minimum variable part. The components V are thus determined; the compression model.

La procédure de compression 33 des mots du code à compresser est illustrée sur la figure 5. A la première étape 331 de cette procédure, on lit le mot suivant du code à compresser. Si ce mot est identique au mot précédent (étape 332), on écrit à l'étape 333 le code BC correspondant dans le code compressé, puis on retourne à l'étape 331 de lecture du mot à compresser suivant. The compression procedure 33 of the words of the code to be compressed is illustrated in FIG. 5. In the first step 331 of this procedure, the next word of the code to be compressed is read. If this word is identical to the previous word (step 332), the corresponding BC code is written in step 333 in the compressed code, then the step 331 of the next word to be compressed is returned to step 333.

Si le mot à compresser n'est pas identique au précédent, on détermine à l'étape 334 si le mot à compresser figure dans la table de décompression 10. Si tel est le cas, on insère à l'étape 335 le code BC correspondant à la sous-table 21 où se trouve le mot à compresser dans le code compressé. Ensuite, on insère dans le code compressé la position du mot à compresser dans la sous-table 21 (étape 336), et on retourne à l'étape 331. If the word to be compressed is not identical to the previous one, it is determined in step 334 whether the word to be compressed is included in the decompression table 10. If this is the case, the corresponding code BC is inserted in step 335. at the sub-table 21 where is the word to be compressed in the compressed code. Next, the position of the word to be compressed in the sub-table 21 (step 336) is inserted into the compressed code, and step 331 is returned.

Si le mot à compresser ne figure pas dans la table de décompression 10, on 35 insère dans le code compressé le code BC correspondant (étape 337), puis le (7) 2888012 - 17- mot à compresser ou une partie de celui-ci si le code BC choisi spécifie les bits du mot à compressé non insérés (étape 338). If the word to be compressed does not appear in the decompression table 10, the corresponding code BC (step 337) is inserted into the compressed code, then the word (7) 2888012 to be compressed or part thereof. if the chosen BC code specifies the bits of the word to be compressed not inserted (step 338).

Avantageusement, on prévoit de scinder chaque instruction du code source binaire à compresser en plusieurs mots de manière à faire apparaître davantage de répétitions dans les mots à compresser. On constitue alors autant de tables de décompression qu'il y a de mots dans chaque instruction. Ainsi par exemple, dans le cas d'un code binaire exécutable par un microprocesseur à architecture RISC constitué d'instructions codées sur 32 bits, chaque instruction est scindée en deux mots, à savoir un mot de poids fort et un mot de poids faible, par exemple de tailles égales à 16 bits. Ces mots sont avantageusement traités séparément pour constituer deux histogrammes respectifs, un pour les mots de poids faible et un pour les mots de poids fort. Chacun de ces histogrammes conduit à l'obtention de deux tables de décompression et la compression du code source à compresser fournit deux parties fixes et deux parties variables pour chaque instruction du code exécutable. Advantageously, it is planned to split each instruction of the binary source code to be compressed into several words so as to reveal more repetitions in the words to be compressed. We then create as many decompression tables as there are words in each instruction. For example, in the case of a binary code executable by a RISC architecture microprocessor consisting of 32-bit coded instructions, each instruction is divided into two words, namely a most significant word and a low word, for example, sizes equal to 16 bits. These words are advantageously treated separately to constitute two respective histograms, one for the low-weight words and one for the high-weight words. Each of these histograms leads to obtaining two decompression tables and compression of the source code to be compressed provides two fixed parts and two variable parts for each instruction of the executable code.

La figure 6 illustre le procédé de décompression correspondant au procédé de compression décrit ci-avant en référence à la figure 3. FIG. 6 illustrates the decompression method corresponding to the compression method described above with reference to FIG.

A la première étape 41 de ce procédé, on calcule une adresse j de lecture de la table d'adressage 13 à partir de l'adresse AD d'une première instruction à exécuter. Cette étape consiste tout d'abord à déterminer l'adresse m de la ligne d'instructions DL(m) dans laquelle se trouve l'instruction à partir de laquelle le traitement de décompression doit être effectué. Ce calcul est effectué à l'aide de la formule suivante: m = (AD ADs) / DLS (8) dans laquelle ADs est l'adresse de début du programme compressé et DLS est la taille d'une ligne d'instructions. In the first step 41 of this method, a reading address of the address table 13 is calculated from the address AD of a first instruction to be executed. This step consists first of all in determining the address m of the instruction line DL (m) in which the instruction from which the decompression processing is to be performed is located. This calculation is done using the following formula: m = (AD ADs) / DLS (8) where ADs is the start address of the compressed program and DLS is the size of a statement line.

La ligne j de 64 bits à lire dans la table d'adressage est obtenue en divisant m par le nombre de lignes DL référencées par ligne j de la table d'adressage, soit 4 dans l'exemple décrit précédemment. The 64-bit line to be read in the addressing table is obtained by dividing m by the number of DL lines referenced by row j of the addressing table, ie 4 in the example described above.

A l'étape suivante 42, on lit la ligne j identifiée dans la table d'adressage 13, puis on détermine la position de la ligne d'instructions VCL(m) dans la partie variable 12 du code compressé, et le nombre de mots à lire pour obtenir tout le code compressé de la ligne d'instruction de longueur variable (étape 43). La position P(m) de la ligne m à lire dans la partie variable 12 est obtenue de la 2888012 -18- manière suivante: P(m) = PP(0), (9) sik=mmodulo 4=0, sinon, si k = 1, 2 ou 3, P(m) = Pj(k-1) + L;(k--1). (10) Une fois que l'on a identifié dans quelle ligne m appartient la partie variable de l'instruction à lire, on détermine le nombre F de mots (de 32 bits) à lire dans la partie variable en fonction du numéro de ligne m, à l'aide de la formule suivante: F(m) = 1 + (Li(k) 1)/32 (11) A l'étape suivante 45, on lit la partie fixe FCL(m) de la ligne de code compressé DL(m). Sachant que la partie fixe d'une instruction compressée est codée sur 8 bits (si les codes BC sont définis sur 4 bits et si chaque instruction est décomposée en deux mots de 16 bits codés séparément), la position PF en octets de la ligne de code dans la partie fixe compressée 11 est donnée par la valeur de m. La longueur de la partie fixe FCL(m) est de 32 ou 64 octets selon la longueur d'une ligne. In the next step 42, the line j identified in the addressing table 13 is read, then the position of the instruction line VCL (m) in the variable part 12 of the compressed code is determined, and the number of words to read to get all the compressed code of the variable length instruction line (step 43). The position P (m) of the line m to be read in the variable part 12 is obtained from the following way: P (m) = PP (0), (9) sik = mmodulo 4 = 0, otherwise, if k = 1, 2 or 3, P (m) = Pj (k-1) + L; (k - 1). (10) Once it has been identified in which line m belongs the variable part of the instruction to be read, the number F of words (32 bits) to be read in the variable part is determined according to the line number m, using the following formula: F (m) = 1 + (Li (k) 1) / 32 (11) In the following step 45, the fixed part FCL (m) of the line compressed code DL (m). Knowing that the fixed part of a compressed instruction is coded on 8 bits (if the BC codes are defined on 4 bits and each instruction is broken down into two 16-bit words coded separately), the PF position in bytes of the line of code in the compressed fixed part 11 is given by the value of m. The length of the fixed part FCL (m) is 32 or 64 bytes depending on the length of a line.

A l'étape suivante 46, on lit la partie variable VCL(m) de la ligne de code compressée, déterminée à l'étape 44. Bien entendu, les étapes 44 et 45 d'une part et d'autre part 42, 43 et 46, peuvent être effectuées dans n'importe quel ordre ou en parallèle. In the following step 46, the variable part VCL (m) of the compressed code line determined in step 44 is read. Of course, steps 44 and 45 on the one hand and on the other hand 42, 43 and 46, can be performed in any order or in parallel.

Enfin, à la dernière étape 47, on décompresse la ligne de code compressée, à l'aide des tables de décompression pour obtenir une ligne de code exécutable 2'. A cet effet, on lit chaque code BC de la ligne de longueur fixe FCL(m), on détermine la fonction du code BC en accédant au champ BCOP<BC> dans la table 15, si la fonction du code BC spécifiée dans la table 15 indique que l'instruction correspondante est la même que l'instruction précédente, on duplique l'instruction précédemment décompressée, dans le code décompressé 2'. Si la fonction du code BC spécifiée dans la table 15 est d'introduire une partie variable non compressée de 15 ou 16 bits, on lit respectivement les 15 ou 16 bits suivants dans la partie variable VCL(m) et on les écrit dans le code décompressé 2'. Si longueur de la partie variable est de 15 bits, le bit de poids fort (16ième bit) est égal au bit de poids faible du code BC. Si la fonction du 2888012 - 19- code BC est de référencer une sous-table de la table de décompression 10, on détermine la l'adresse de la sous-table 21 correspondante dans la table de décompression, et la longueur VLI de la partie variable à lire dans la ligne de parties variable VCL(m), tel que spécifiée dans la table 15. On lit les VLI bits suivants dans la partie variable VCL(m) pour obtenir une position à lire dans la table de décompression 10 à partir de l'adresse de la sous-table 21 correspondant au code BC. Enfin, on lit le mot 22 se trouvant à la position ainsi déterminée dans la sous-table de décompression 21, le mot lu étant inscrit dans le code décompressé 2'. Finally, in the last step 47, the compressed code line is decompressed, using the decompression tables to obtain a line of executable code 2 '. For this purpose, each code BC of the fixed length line FCL (m) is read, the function of the code BC is determined by accessing the BCOP <BC> field in the table 15, if the function of the code BC specified in the table 15 indicates that the corresponding instruction is the same as the previous instruction, it duplicates the previously decompressed instruction in the decompressed code 2 '. If the function of the code BC specified in the table 15 is to introduce an uncompressed variable part of 15 or 16 bits, the following 15 or 16 bits are respectively read in the variable part VCL (m) and written in the code uncompressed 2 '. If the length of the variable part is 15 bits, the most significant bit (16th bit) is equal to the least significant bit of the code BC. If the function of the BC code is to reference a sub-table of the decompression table 10, the address of the corresponding sub-table 21 in the decompression table is determined, and the length VLI of the part variable to be read in the line of variable parts VCL (m), as specified in table 15. The following VLI bits are read in the variable part VCL (m) to obtain a position to read in the decompression table 10 from the address of the sub-table 21 corresponding to the BC code. Finally, the word 22 is read at the position thus determined in the decompression sub-table 21, the word read being written in the decompressed code 2 '.

Le procédé de décompression qui vient d'être décrit est adapté pour être effectué à la volée au moment de l'exécution d'un programme par un microprocesseur ou microcontrôleur. La figure 7 représente schématiquement un exemple d'architecture d'un circuit intégré comprenant un tel microprocesseur. Sur cette figure, le microprocesseur comprend une unité centrale CPU couplée directement à une unité d'accès DM à la mémoire de données, et à une unité d'accès à la mémoire programme PMX conçue pour accélérer la lecture des instructions à exécuter dans une mémoire programme PM à accès rapide ou éventuellement dans d'autres mémoires, accessibles par l'intermédiaire d'un bus périphérique PB auquel sont connectés une unité de gestion des interruptions ITC et des organes périphériques P#1, P#2, ..., P#N tels que des mémoires. Le circuit intégré comprend en outre un commutateur de bus PBS établissant une liaison entre le microprocesseur, et en particulier l'unité d'accès DM à la mémoire de données, et l'unité d'accès PMX à la mémoire programme et un bus système SB d'accès à des mémoires externes et à des interfaces externes. The decompression method that has just been described is adapted to be performed on the fly at the time of execution of a program by a microprocessor or microcontroller. FIG. 7 schematically represents an exemplary architecture of an integrated circuit comprising such a microprocessor. In this figure, the microprocessor comprises a CPU CPU directly coupled to a DM access unit to the data memory, and a PMX program memory access unit designed to accelerate the reading of the instructions to be executed in a memory PM program with quick access or possibly in other memories, accessible via a PB peripheral bus to which are connected an ITC interrupt management unit and peripheral devices P # 1, P # 2, ..., P # N such as memories. The integrated circuit further comprises a PBS bus switch establishing a link between the microprocessor, and in particular the DM access unit to the data memory, and the PMX access unit to the program memory and a system bus. SB access to external memories and external interfaces.

Selon l'invention, le microprocesseur comprend une unité de décompression DecU pour décompresser à la volée du code exécutable stocké dans la mémoire programme sous une forme compressée obtenue grâce au procédé de compression décrit ci-avant. A cet effet, l'unité de décompression est interposée entre l'unité d'accès à la mémoire programme PMX d'une part et d'autre part, la mémoire programme PM, le commutateur de bus PBS et le bus périphérique PB. Un exemple d'architecture de l'unité de décompression est représenté sur la figure 8. Sur cette figure, l'unité de décompression DecU comprend un circuit de contrôle de port esclave SPC chargé des communications avec le bus périphérique PB et de l'initialisation de l'unité de décompression DecU, un moteur de décompression DE chargé du traitement de décompression - 20 -proprement- dit, et un circuit de contrôle de mémoire cache DCC. According to the invention, the microprocessor comprises a DecU decompression unit for decompressing on the fly executable code stored in the program memory in a compressed form obtained by means of the compression method described above. For this purpose, the decompression unit is interposed between the PMX program memory access unit on the one hand and the program memory PM, the PBS bus switch and the peripheral bus PB on the other hand. An example architecture of the decompression unit is shown in FIG. 8. In this figure, the decompression unit DecU comprises a slave port control circuit SPC responsible for communications with the peripheral bus PB and initialization. of the DecU decompression unit, an decompression engine DE in charge of decompression processing - properly speaking - and a DCC cache control circuit.

Le moteur de décompression DE comprend des registres CRL, CRH destinés à recevoir la table 15 pour donnant la fonction du code BC pour chacune des valeurs de ce code. Le moteur de décompression comprend en outre une unité de traitement DP rassemblant dans des registres DTF les tables de décompression 10. Si les instructions de code sont scindées en deux mots, on prévoit deux tables 15 stockées dans quatre registres CRL[0], CRL[1], CRH[0], CRH[l] et deux tables de décompression stockées respectivement dans deux registres DTFO et DTF 1. Plus généralement, on prévoit deux registres CRL, CRH et un registre DTF pour chaque mot compressé séparément des instructions du code exécutable. L'unité de traitement DP présente avantageusement une architecture pipeline, c'est-à-dire permettant d'effectuer en parallèle plusieurs opérations normalement effectuées en série. The decompression engine DE includes registers CRL, CRH for receiving the table for giving the function of the code BC for each of the values of this code. The decompression engine further comprises a processing unit DP gathering in the DTF registers the decompression tables 10. If the code instructions are split into two words, two tables 15 are stored in four registers CRL [0], CRL [ 1], CRH [0], CRH [l] and two decompression tables stored respectively in two DTFO and DTF registers 1. More generally, two registers CRL, CRH and a DTF register are provided for each word compressed separately from the instructions of the code. executable. The DP processing unit advantageously has a pipeline architecture, that is to say to perform in parallel several operations normally performed in series.

Le circuit de contrôle de mémoire cache DCC comprend: une interface MIF de bus maître conçue pour être connectée au commutateur de bus PBS, une mémoire tampon d'entrée PFB connectée à l'interface MIF, un ensemble de registres 18 prévus pour recevoir des adresses permettant d'accéder aux différentes parties du code compressé stockées dans les mémoires programme, à savoir les parties fixes 11 et variables 12 du code compressé et les tables d'adressage 13, un registre DCTR de contrôle de l'unité de décompression, une zone mémoire de travail WA comportant une mémoire cache CM, et une table Tags de gestion de la mémoire cache CM contenant les adresses des dernières instructions décompressées stockées dans la mémoire cache CM. The DCC cache control circuit comprises: a master bus MIF interface adapted to be connected to the PBS bus switch, a PFB input buffer connected to the MIF interface, a set of registers 18 provided to receive addresses allowing access to the different parts of the compressed code stored in the program memories, namely the fixed parts 11 and variables 12 of the compressed code and the address tables 13, a control DCTR register of the decompression unit, a zone WA working memory having a cache memory CM, and a CM cache management tag table containing the addresses of the last decompressed instructions stored in the cache memory CM.

Le circuit SPC comprend un port d'adresse d'entrée AD, et des ports d'entrée et de sortie de données DIN et DOUT connectés au bus périphérique PB, notamment pour recevoir du CPU par l'intermédiaire du commutateur de bus PBS, les données à charger dans les différents registres décrits ci-avant de l'unité de décompression pour effectuer le traitement de décompression. Il est également chargé d'effectuer les tests de bon fonctionnement de l'unité de décompression DecU et en particulier de tester le contenu des registres. The circuit SPC comprises an input address port AD, and input and output ports of data DIN and DOUT connected to the peripheral bus PB, in particular to receive from the CPU via the PBS bus switch, the data to be loaded into the different registers described above of the decompression unit to perform the decompression treatment. It is also responsible for performing the functional tests of the DecU decompression unit and in particular for testing the contents of the registers.

2888012 -21- Avantageusement, le code compressé est réparti dans la mémoire programme dans des pages de code compressé, chaque page rassemblant une partie fixe 11 et une partie variable 12 de code compressé, et une table d'adressage 13. L'ensemble de registres 18 est alors prévu pour recevoir pour chaque page de code compressé, un ensemble d'adresses comprenant des adresses de début et de fin de page de code compressé DPSTA et DPEND, une adresse MTSTA de début de table d'adressage 13, et une adresse VASTA de début de partie variable 12 du code compressé, la partie fixe 11 du code compressé étant par exemple rangée à partir de l'adresse de début DPSTA, comme illustré sur la figure 9. Advantageously, the compressed code is distributed in the program memory in compressed code pages, each page comprising a fixed part 11 and a variable part 12 of compressed code, and an address table 13. The set registers 18 is then provided to receive for each compressed code page, a set of addresses comprising compressed code DPSTA and DPEND start and end address addresses, an address table start address MTSTA 13, and a VASTA start address variable 12 of the compressed code, the fixed portion 11 of the compressed code being for example stored from the start address DPSTA, as shown in Figure 9.

Tel que représenté sur la figure 10, la table Tags permet d'adresser 8 lignes DL d'instructions décompressées. Chaque ligne i de cette table qui correspond à une ligne i de la mémoire cache CM, contient l'adresse AD_DL[i] de la ligne décompressée dans le plan d'adressage du CPU, associée à un bit global de validité GL[i], et un ensemble de bits de validité VB[i], à raison d'un bit de validité par groupe de 4 instructions décompressées dans la ligne DL[i] de la mémoire cache CM. As shown in FIG. 10, the Tags table makes it possible to address 8 DL lines of uncompressed instructions. Each line i of this table which corresponds to a line i of the cache memory CM, contains the address AD_DL [i] of the uncompressed line in the address plan of the CPU, associated with a global bit of validity GL [i] , and a set of validity bits VB [i], with one validity bit per group of 4 instructions decompressed in the line DL [i] of the cache memory CM.

Le circuit de contrôle de mémoire cache DCC est prévu pour se connecter directement à l'unité d'accès à la mémoire programme PMX et à la mémoire programme rapide PM. Ainsi, le circuit DCC comprend une entrée d'adresse connectée à une sortie d'adresse AD de l'unité PMX pour recevoir de celleci une adresse de début d'instructions à décompresser provenant du CPU, et une sortie de données connectée à une entrée DIN de l'unité PMX par laquelle le circuit DCC transmet en réponse les instructions décompressées correspondantes. Le circuit DCC comprend également une sortie d'adresse et une entrée de données connectées respectivement à une entrée AD d'adresse et une sortie DOUT de données de la mémoire programme rapide PM, pour recevoir une ligne d'instructions compressées à partir de l'adresse fournie. Lorsque l'adresse reçue de l'unité PMX ne se trouve pas dans la mémoire programme rapide, le circuit de contrôle DCC accède à la mémoire programme externe par l'intermédiaire de l'interface MIF comportant un port de sortie d'adresse et un port d'entrée de données connectés au commutateur de bus PBS. The DCC cache control circuit is provided to connect directly to the PMX program memory access unit and the PM fast program memory. Thus, the DCC circuit includes an address input connected to an address output AD of the PMX unit for receiving therefrom an instruction start address to be decompressed from the CPU, and a data output connected to an input DIN of the PMX unit by which the DCC circuit transmits in response the corresponding decompressed instructions. The DCC circuit also includes an address output and a data input respectively connected to an AD address input and a DOUT data output of the PM fast program memory, to receive a compressed instruction line from the address provided. When the address received from the PMX unit is not in the Quick Program Memory, the DCC control circuit accesses the external program memory via the MIF interface having an address output port and a data input port connected to the PBS bus switch.

Chaque adresse reçue en tant que de requête d'instruction du CPU par l'intermédiaire de l'unité PMX porte sur un groupe de quatre instructions successives. A la réception d'une telle requête, le circuit de contrôle DCC 2888012 -22- recherche si l'adresse du groupe d'instructions requis figure dans les champs AD_DL[i] de la table Tags. Le circuit de contrôle DCC considère que les instructions requises sont décompressées dans la mémoire cache CM si l'adresse requise se trouve dans la table Tags et si le bit global de validité GL[i] correspondant est levé, et si ce bit n'est pas levé, si le bit de validité VB[i][j] correspondant au groupe j d'instructions requis est levé. Si le groupe d'instructions requis figure dans la mémoire cache, le circuit de contrôle DCC lit le groupe d'instructions requis dans le champ correspondant i de la mémoire cache, les transmets à l'unité PMX. Il est alors disponible pour recevoir une nouvelle requête du CPU. Each address received as an instruction request from the CPU via the PMX relates to a group of four successive instructions. Upon receipt of such a request, the control circuit DCC 2888012 -22- checks whether the address of the group of instructions required is in the fields AD_DL [i] of the table Tags. The control circuit DCC considers that the required instructions are decompressed in the cache memory CM if the required address is in the table Tags and if the global bit of validity GL [i] corresponding is raised, and if this bit is not not raised, if the validity bit VB [i] [j] corresponding to the group j of required instructions is raised. If the required instruction group is in the cache memory, the control circuit DCC reads the required instruction group in the corresponding field i of the cache memory, transmits them to the PMX unit. It is then available to receive a new request from the CPU.

Dans le cas où le groupe d'instructions requis n'est pas décompressé dans la mémoire cache, l'unité de contrôle DCC détermine si le groupe d'instructions requis appartient ou non au champ d'adresses du code compressé, c'est-à-dire si l'adresse du groupe d'instructions requis est compris entre les adresses DPSTA[i] et DPEND[i] de la page de code à laquelle appartient l'adresse du groupe d'instructions requis. Si ce n'est pas le cas, l'unité de contrôle accède à la mémoire programme PM ou à une mémoire externe via le port maître, à l'adresse du groupe d'instructions requis et transmet les instructions lues à l'unité PMX. In the case where the required instruction group is not decompressed in the cache memory, the control unit DCC determines whether or not the required instruction group belongs to the address field of the compressed code, that is, that is, if the address of the required instruction group is between the DPSTA [i] and DPEND [i] addresses of the code page to which the address of the required instruction group belongs. If this is not the case, the control unit accesses the PM program memory or external memory via the master port at the address of the required instruction group and transmits the read instructions to the PMX unit. .

Si le groupe d'instructions requis appartient au champ d'adresses du code compressé, l'unité de contrôle DCC détermine une ligne i de la table Tags et de la mémoire cache CM qu'elle peut utiliser pour y insérer la nouvelle ligne de code décompressé qu'elle va générer. La ligne i sélectionnée est par exemple celle qui a été lue le plus anciennement. Ensuite, l'unité de contrôle DCC exécute la procédure de décompression telle que décrite ci-avant en référence à la figure 6. En particulier, aux étapes 45 et 46, l'unité de contrôle DCC fournit les parties fixes FCL(m) et variables VCL(m) lues, au moteur de décompression DE, par exemple par l'intermédiaire d'une mémoire tampon FIFO (First In First Out) . Tant que la FIFO n'est pas vide, le moteur de décompression DE exécute l'étape 47 de décompression proprement dite. A cet effet, il lit les parties fixe et variable de la première ligne introduite dans la FIFO, lit les codes BC de la partie fixe, successivement ou deux par deux si les instructions compressées ont été scindées en deux mots, et décompresse chaque instruction. Les instructions décompressées sont fournies à l'unité de contrôle DCC qui les charge dans la ligne i de la mémoire cache CM sélectionnée préalablement, et met à jour la table Tags, et en particulier les bits de validité VB[i] correspondant à la ligne de 2888012 - 23 - la mémoire cache, à chaque fois qu'un groupe de quatre instructions décompressées est écrit dans la mémoire cache. Lorsqu'une ligne entière d'instructions décompressées est inscrite dans la mémoire cache, l'unité de contrôle met à jour le bit de validité global GV[i] correspondant à la ligne. If the required instruction group belongs to the address field of the compressed code, the DCC control unit determines a line i of the Tags table and the CM cache that it can use to insert the new line of code. uncompressed that it will generate. The selected line i is for example the one that was read the oldest. Then, the control unit DCC performs the decompression procedure as described above with reference to FIG. 6. In particular, in steps 45 and 46, the control unit DCC provides the fixed portions FCL (m) and VCL variables (m) read to the decompression engine DE, for example via a FIFO buffer (First In First Out). As long as the FIFO is not empty, the decompression engine DE executes the decompression step 47 itself. For this purpose, it reads the fixed and variable parts of the first line introduced in the FIFO, reads the BC codes of the fixed part, successively or two by two if the compressed instructions have been split into two words, and decompresses each instruction. The decompressed instructions are supplied to the DCC control unit which loads them into line i of the previously selected CM cache, and updates the Tags table, and in particular the validity bits VB [i] corresponding to the line the cache memory, whenever a group of four decompressed instructions is written to the cache memory. When an entire line of decompressed instructions is written in the cache memory, the control unit updates the global validity bit GV [i] corresponding to the line.

Parallèlement, dès que le bit de validité VB[i] du groupe d'instructions correspondant à l'adresse reçue en tant que requête d'instructions du CPU est levé, l'unité de contrôle transmet le groupe d'instructions correspondant situé dans la mémoire cache CM à l'unité PMX pour qu'il soit fourni au CPU, et se met en attente d'une nouvelle requête d'instructions provenant du CPU. At the same time, as soon as the validity bit VB [i] of the instruction group corresponding to the address received as instruction request of the CPU is raised, the control unit transmits the corresponding group of instructions located in the CM cache memory to the PMX unit to be supplied to the CPU, and waits for a new request for instructions from the CPU.

Parallèlement, on peut prévoir également d'utiliser une autre mémoire cache pour mémoriser les mots lus dans la table d'adressage 13. At the same time, it is also possible to use another cache memory for storing the words read in the addressing table 13.

Grâce à ces dispositions, si le CPU demande des instructions figurant dans la mémoire cache CM, il n'est pas nécessaire d'effectuer le traitement de décompression. De nombreux cycles de traitement sont ainsi économisés, et le bus système est laissé libre pour d'autres tâches. With these provisions, if the CPU requests instructions from the CM cache memory, it is not necessary to perform decompression processing. Many processing cycles are saved, and the system bus is left free for other tasks.

Il résulte également de la description qui précède que les algorithmes de compression et de décompression selon l'invention permettent d'obtenir une grande flexibilité, en terme de possibilité d'effectuer différentes opérations de décompression en parallèle, tout en offrant un taux élevé de compression. Ainsi, l'invention permet d'obtenir un taux de compression typiquement compris entre 30 et 45%, sans augmenter le nombre de cycles d'exécution du code de plus de 5%, lorsque l'on utilise une mémoire cache pour mémoriser les instructions décompressées. It also results from the foregoing description that the compression and decompression algorithms according to the invention make it possible to obtain great flexibility, in terms of the possibility of performing different decompression operations in parallel, while offering a high rate of compression. . Thus, the invention makes it possible to obtain a compression ratio typically between 30 and 45%, without increasing the number of code execution cycles by more than 5%, when using a cache memory to memorize the instructions. decompressed.

Claims

-24-CLAIMS

A method of compressing executable code (2) by a microprocessor, comprising steps of: decomposing the executable code into words, dividing the executable code into lines (DL) of a predefined number of instructions, compressing each word of each line of executable code executable code in the form of a compressed word of variable length, the compressed words of an executable line of code being collected in a compressed word (VCL) line, and constitution of a table of addressing (13) for locating each of the compressed word lines (VCL) in a block (12) of compressed word lines, characterized in that the addressing table (13) comprises an entry per group of a predefined number compressed word lines (VC40), VCLL (1), VCLi (2), VC43)), each entry (j) specifying the position (PP (0)) of a first line (VCL i (0)) of compressed words in the block (12), and the respective lengths (4 (0), 41), 142)) of the compressed words of the group, except a last line (VCLJ (3)) of compressed words of the group, the length of which is determined using the position (Pi + 1 (0)) of a first line of compressed words d a next group (j + 1) of compressed word lines.

The compression method according to claim 1, wherein each executable code word is compressed into a predefined fixed length portion (BC) and a variable length portion (VLI) whose length is defined by the fixed length portion, all the fixed length portions and all the variable length portions being grouped respectively in a block (11) of fixed length portions and in the block (12) of variable length compressed words, each executable code line being compressed into one line (FCL) of fixed length parts and the line (VCL) of compressed words of variable length.

The compression method of claim 1 or 2, wherein each of the executable code words to be compressed corresponds to an instruction.

4. A method of compression according to claim 1 or 2, in which the executable code is divided into several parts each containing a respective word of each instruction of the executable code to be compressed, the method being applied separately to each of the executable code parts. to obtain for each instruction word of the executable code a fixed length portion (BC) which is inserted into the block (11) of fixed length portions and a variable length portion which is inserted into the block (12) of parts of variable length.

5. A compression method according to one of claims 2 to 4, wherein the compression step (33) comprises the steps of: constituting (31) a histogram (9) giving for each word distinct from the executable code (2) ) a number of occurrences of this word in the executable code, and extracting (32) at least a portion of the words of the histogram in a decompression table (10), in which the words are divided into sub-tables (21). ) gathering words (22) having numbers of neighboring occurrences in the histogram, each sub-table being associated with a predefined length, the fixed length portion (BC) of each executable code word referencing a sub-table of the decompression table, and the variable length portion (VLI) giving a position in the decompression sub-table of the executable code word.

The compression method according to claim 5, wherein the words of the executable code (2) associated in the histogram (9) with a number of occurrences less than a predetermined threshold are not inserted in the decompression table (10). ), each executable code word not inserted in the decompression table being compressed using a fixed length portion (BC) specifying that the executable codeword is not present in the decompression table, and a portion of variable length containing at least a portion of the executable code word.

A compression method according to claim 5 or 6, wherein if two identical executable codewords occur consecutively in the executable code (2) to be compressed, the second executable codeword is compressed without a variable length part, to the using a fixed length part (BC) specifying that the executable codeword is the same as the preceding word.

2888012 -26-

The compression method according to one of claims 5 to 7, wherein the fixed length portion (BC) of each compressed word specifies according to its value: either a sub-table number (21) of the decompression table. (10), that the corresponding executable code word is the second word of two identical consecutive words of the executable code, or that the variable length portion of the compressed word contains at least a part of the corresponding executable code word.

A compression method according to claim 8, wherein a predefined value of the fixed length portion (BC) of a compressed word specifies a breakpoint to be introduced into the executable code during a program test phase. .

The compression method according to one of claims 5 to 9, wherein the division into sub-tables (21) of the decompression table (10) is chosen so as to obtain a size of the set (12) of the parts of variable length of the compressed code as small as possible.

11. A method of compression according to one of claims 5 to 10, wherein the executable code is divided into several parts each containing a respective word of each instruction of the executable code to be compressed, the method being applied separately to each of the code parts. executable, to obtain a decompression table (10) for each part of the executable code.

A method for decompressing executable code (2) by a microprocessor, stored in a compressed program memory area, the decompression method comprising the steps of: determining a read address of an address table (13) according to an instruction address to be executed, the addressing table (13) for locating lines (VCL) of compressed words in a block (12) of compressed word lines, read at the read address in the address addressing information table in the compressed word line block, determining, based on the read address information read a read address in the block of compressed word lines, 2888012 -27- read the block of compressed word lines at the determined reading address, and decompressing at least one compressed word line read to obtain executable instructions, characterized in that the addressing table (13) comprises an input per group of a predefined number of compressed word lines (VCLi (0), VCLL (1), VCLi (2), VCLL (3)), each entry (j) specifying the position (Pi (0)) of a first line ( VCLL (0)) compressed words in the block (12), and the respective lengths (L40), LL (1), Lj (2)) of the compressed word lines of the group, except a last line (VCL, (3) )) compressed words of the group, the length of which is determined using the position (PJ + 1 (0)) of a first line of compressed words of a group (j + 1) according to lines of words compressed.

13. The decompression method as claimed in claim 12, in which each word of the executable code (2) is compressed in the form of a part (BC) of predefined fixed length and a part (VLI) of variable length whose length is defined by the fixed length portion, all the fixed length portions and all variable length portions of the executable code words being respectively grouped in a block (11) of fixed length portions and in the word block (12) compressed variable length, each line of executable code being compressed into a line (FCL) of fixed length portions and the line (VCL) of compressed words of variable length, the method further comprising steps of: determining an address for reading a line (FCL) of fixed length portions according to the instruction address to be executed, reading the line (FCL) of fixed length portions at the determined address, and decompressing the lines ( F CL, VCL) of fixed and variable length portions read to obtain a line (DL) of executable instructions. 30

The decompression method according to claim 13, wherein the fixed length portion (BC) of each compressed instruction references a subtable (21) of a decompression table (10) gathering at least a portion of the words of the code. executable, the variable length portion giving the position in the sub-table of the executable code word, the decompression of a fixed length portion and a corresponding variable length portion comprising steps of: determining the length of the variable length portion in accordance with the value of the corresponding fixed length portion, reading the corresponding variable length portion taking into account the determined length of the variable length portion, and if the fixed length portion references a sub-table of the decompression table, read the executable code word in the sub-table of the decompression table referenced by the fixed length part read, to a posit ion defined by the part of variable length read.

15. The decompression method according to claim 14, wherein: if the fixed length portion (BC) indicates that the corresponding executable code word is a second word of two identical words occurring consecutively in the executable code (2), the fixed length portion (BC) is decompressed by the previously decompressed executable code word; if the fixed length portion (BC) specifies that the corresponding executable code word is not present in the decompression table (10), the method further comprises steps of extracting at least a portion of the executable code word the variable length portion corresponding to the fixed length portion; if the fixed-length portion (BC) specifies a breakpoint, a breakpoint is inserted into the uncompressed executable code.

16. The decompression method according to one of claims 12 to 15, wherein each of the decompressed executable codewords corresponds to an instruction.

17. The method of decompression according to one of claims 14 to 15, wherein the executable code is divided into several parts each containing a respective word of each instruction of the executable code to be compressed, each part of the executable code having been compressed separately and being associated with a respective decompression table (10) gathering executable code words from the portion of the executable code.

18. Executable code decompression unit (2) by a microprocessor (CPU), stored in a program memory zone in compressed form, the decompression unit being connected to the microprocessor and comprising: means for receiving the microprocessor executable code instruction requests comprising an instruction address to be executed, means for determining a read address of an address table (13) according to the instruction address to be executed, the addressing (13) for locating lines (VCL) of compressed words in a block (12) of compressed word lines stored in the program memory, means for reading at the read address in the address table of addressing information in the block of compressed word lines, means for determining, as a function of the addressing information read, a read address in the block of compressed word lines and a length of a line ( VCL) compressed words in the program memory, corresponding to the instruction address provided by the microprocessor, means for reading the compressed word line at the determined read address, and means for decompressing the compressed word line. read to obtain executable instructions, characterized in that the addressing table (13) comprises a group entry of a predefined number of compressed word lines (VCL, (0), VCLL (1), VCLi (2) , VCLi (3)), each input (j) specifying the position (P, (0)) of a first line (VCL, (0)) of compressed words in the block (12), and the respective lengths (4) (0), 41), 42)) compressed word lines of the group, except a last line (VCLL (3)) of compressed words of the group, whose length is determined using the position (P; + , (0)) of a first line of compressed words of a group (j + 1) following compressed word lines.

19. The decompression unit of claim 18, further comprising: a cache memory (CM) for storing a predefined number of decompressed instructions; means for reading the cache memory following receipt of a request for instructions issued by the microprocessor (CPU), and to transmit in response the corresponding instructions if they are in the cache memory.

The decompression unit according to claim 18 or 19, wherein each word of the executable code (2) is compressed as a predefined fixed length portion (BC) and a VLI portion (VLI). variable length whose length is defined by the fixed length portion, all the fixed length portions and all variable length portions of the executable code words being respectively grouped in a block (11) of fixed length portions and in the block (12) compressed words of variable length, each line of executable code being compressed into a line (FCL) of fixed length portions and the line (VCL) of compressed words of variable length, the decompression unit further comprising: means for determining the position in the program memory of the line (FCL) of fixed length portions containing the compressed code words corresponding to the instruction address provided by the microprocessor (CPU), means ns for reading the block of fixed length portions at the determined read address, means for decompressing the fixed and variable length portions read to obtain an executable instruction, and means for transmitting the decompressed instruction to the microprocessor.

The decompression unit of claim 20, further comprising means for storing start addresses of the block (11) of fixed length portions and the block (12) of variable length portions of the compressed code, and an address of beginning of the addressing table.

22. A decompression unit according to claim 20 or 21, wherein at least some fixed length portions refer to a sub-table (21) of a decompression table (10) gathering at least a part of the words of the executable code. variable length portion giving the position in the sub-table of the executable code word, the decompression unit further comprising: storing means (DTFO, DTF1) of a decompression table, means for determining the position of the executable codeword to be read in the decompression table from the fixed length portion (BC) and the variable length portion, if the fixed length portion references a subtable of the decompression table, and means to read the executable codeword at position -31-determined in the sub-table.

The decompression unit of claim 22, further comprising means for transmitting to the microprocessor (CPU) a previously decompressed executable code word if the fixed length portion (BC) indicates that the corresponding executable codeword is a second word two identical words appearing consecutively in the executable code (2).

The decompression unit of claim 22 or 23, further comprising means for transmitting to the microprocessor (CPU) the variable length portion read if the fixed length portion (BC) specifies that the corresponding executable code word is not present. in the decompression table (10).

25. The decompression unit according to one of claims 22 to 24, further comprising means for transmitting to the microprocessor (CPU) a program execution stop point, if the fixed length portion (BC) specifies it.

26. Decompression unit according to one of claims 18 to 25, wherein each of the decompressed executable code words corresponds to an instruction.

The decompression unit according to one of claims 22 to 25, wherein the executable code is divided into several parts each containing a respective word of each instruction of the executable code to be compressed, each part of the executable code having been compressed separately and being associated with a respective decompression table (10) gathering executable code words from the portion of the executable code.

28. Microprocessor comprising a decompression unit (DecU) according to any one of claims 18 to 27.