FR2888013A1 - Microprocessor e.g. reduced instruction set computer microprocessor, executable binary source code compression method for integrated circuit, involves storing positions of certain variable length compressed instructions in addressing table - Google Patents

Abstract

The method involves decomposing a code, executable by a microprocessor, into words, and compressing each word of the code. Each word has a part of predefined fixed length and a part of variable length whose length is defined by the former part. All the fixed and variable length parts of the respective words are regrouped into a block (11) of fixed length compressed instructions and into a block (12) of variable length compressed instructions. The respective positions of certain instructions of the block (12) are stored in an addressing table (13). 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 unit for decompression of code executable by a microprocessor and stored in a program memory zone in compressed form (3) a microprocessor comprising a decompression unit.

Description

2888013 1

  METHODS AND DEVICES FOR COMPRESSION AND

  DECOMPRESSION OF CODE EXECUTABLE BY MICROPROCESSOR WITH ARCHITECTURE RISC.

  The present invention relates to the field of code compression executable by a microprocessor.

  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).

  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.

  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.

  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.

  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.

  It turns out that this solution degrades 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.

  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.

  The present invention aims to eliminate these disadvantages. This object is achieved by providing a microprocessor executable code compression method, comprising the steps of splitting the executable code into words, and compressing each executable code word.

  According to the invention, each compressed executable code word comprises a predefined fixed length portion and a variable length portion whose length is defined by the fixed length portion, the method further comprising a step of grouping all the portions of fixed length and all variable length portions of the words respectively in a block of fixed length portions and in a block of variable length portions, the respective positions of at least some variable length portions in the variable length portion block being stored in an address table.

  According to one embodiment of the invention, the executable code is divided into lines of a predefined number of instructions, each line of executable code being compressed into a line of fixed length portions contained in the block of fixed length portions. and a line of variable length portions in the variable length portion block, each of the variable length portion lines being located in the variable length portion block using the addressing table.

  Advantageously, the addressing table comprises a group entry of a predefined number of lines of variable length portions, each entry specifying the position of a first line of variable length portions in the set of variable length portions of the variable length portion. compressed code, and the respective lengths of the lines of variable length portions of the group, except for a last line of variable length portions of the group, the length of which is determined using the position of a first line of length portions variable of a group of lines of parts of variable length next.

  Preferably, each word of the executable code to be compressed corresponds to an instruction.

  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 for each word An executable code is a fixed length portion that is inserted into the block of fixed length portions and a variable length portion that is inserted into the variable length portion block.

  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, the 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 executable code word decompression sub-table.

  According to one embodiment of the invention, 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 using a fixed length portion specifying that the executable code word is not in the decompression table, and a variable length portion containing at least a portion of the executable code word.

  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.

  According to one embodiment of the invention, the fixed length portion of each compressed word specifies according to its value: either a sub-table number of the decompression table, or that the corresponding executable code word is the second word of two identical consecutive words of the executable code, or the variable length portion of the compressed word contains at least a portion of the corresponding executable codeword.

  According to one embodiment of the invention, a predefined value of the fixed length part 5 of a compressed word specifies a breakpoint to be introduced into the executable code during a test phase of the program.

  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 the set of variable length parts of the smallest possible compressed code.

  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.

  The invention also relates to a method for decompressing executable code by a microprocessor, stored in a program memory zone 20 in compressed form, the method comprising the steps of: receiving from the microprocessor executable code instruction requests including a instruction to be executed, determining a read address of an address table as a function of the instruction address to be executed, reading at the read address in the address table of the word addressing information compressed according to the instruction to be executed, determine according to the address information read a read address of the program memory, read the program memory at the read address, and decompress the words read and transmit them to the microprocessor.

  According to 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 the variable length portions of the executable codewords being respectively grouped into a block of fixed length portions and a block of variable length portions, at least some variable length portions being located in the block of portions variable length using an address table, the decompression method further comprising the steps of: determining a read address in the block of fixed length portions according to the address of the instruction to execute, read the blocks of fixed and variable length portions at the determined read addresses, and decompress the fixed and variable length portions read to obtain a e executable instruction which is transmitted to the microprocessor.

  According to one embodiment of the invention, the compressed code is organized in lines of fixed length portions and in lines of variable length portions, each line of fixed length portions and the line of associated variable length portions corresponding to a fixed length portion. respective line of a predefined number of executable code instructions, each of the variable length portion lines being located in the program memory area using the address table, the method comprising steps of: a line of fixed length parts and a line of variable length parts, localized using the information read from the addressing table, and decompression of the lines of fixed and variable length portions read to obtain a line of executable instructions.

  According to one embodiment of the invention, the addressing table comprises a group entry of a predefined number of lines of variable length portions, each entry specifying the position of a first line of variable length portions in the first row. set of variable length parts of the compressed code, and the respective lengths of the rows of variable length portions of the group, except for a last line of variable length portions of the group, the length of which is determined using the position of d a first line of variable length portions of a group of lines of subsequent variable length portions.

  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 position defined by the variable length portion read.

  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 decompressed by the word of executable code 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; and if the fixed-length portion specifies a breakpoint, a breakpoint is inserted into the uncompressed executable code.

  Advantageously, each of the decompressed executable code words corresponds to an instruction.

  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.

  The invention also relates to a code decompression unit executable by a microprocessor, stored in a compressed program memory zone, the decompression unit being connected to the microprocessor, the decompression unit comprising: means for receiving from the microprocessor executable code instruction requests including an instruction address to be executed; means for determining a read address of an address table based on the instruction address to be executed; addressing for locating in the program memory some stored compressed words, means for reading at the read address in the addressing table of the compressed word addressing information corresponding to the instruction to be executed, means for determining according to the addressing information read a read address of the program memory, means for reading compressed words in the program memory at the read address, means for decompressing the read compressed words to obtain an executable instruction, and means for transmitting the executable instruction to the microprocessor. According to the invention, each word of the executable code is compressed in the form of a predefined fixed length portion and a variable length portion, the length of which is defined by the fixed length portion, all length portions. fixed and all the variable length portions of the executable codewords being grouped together in a program memory area respectively in a block of fixed length portions and in a block of variable length portions, at least some variable length portions being located in the block of variable length portions using an address table, the decompression unit further comprising: means for determining a read address in a block of fixed length portions according to the address of the instruction to be executed, means for reading the block of fixed length portions at the determined read address, and means for decompressing the fixed length and variable length portions. read to get an executable statement.

  According to an embodiment of the invention, the decompression unit 2888013 further comprises means for storing start addresses of the block of fixed length portions and the block of variable length portions of the compressed code.

  According to one embodiment of the invention, the compressed code is organized in lines of fixed length portions and in lines of variable length portions, each line of fixed length portions and the line of associated variable length portions corresponding to a fixed length portion. respective line of a predefined number of executable code instructions, each of the variable length portion lines being located in the program memory area by means of an address table stored in an area of the program memory, decompression unit further comprising means for storing a start address of the addressing table.

  According to one embodiment of the invention, the addressing table comprises a group entry of a predefined number of lines of variable length portions, each entry specifying the position of a first line of variable length portions in the first row. set of variable length parts of the compressed code, and the respective lengths of the rows of variable length portions of the group, except for a last line of variable length portions of the group, the length of which is determined using the position of d a first line of variable length portions of a group of lines of subsequent variable length portions, the decompression unit further comprising: means for receiving from the microprocessor executable code instruction requests including an address of instruction, means for reading the addressing table based on the executable code instruction address provided by the microprocessor, means for determining the using the address table 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 determining using the addressing table the position and length in the program memory of the line of variable length portions containing the compressed code words corresponding to the instruction address provided by the microprocessor, and means for decompressing and memorizing all the instructions executable code corresponding to the line of fixed length portions read and the line of variable length portions read.

  According to an embodiment of the invention, the decompression unit further comprises: a cache memory 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, and to transmit in response the corresponding instructions if they are in the cache memory.

  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.

  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.

  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.

  According to one embodiment of the invention, the decompression unit 2888013 further comprises means for transmitting to the microprocessor a program execution stopping point, if the fixed length part specifies it.

  According to one embodiment of the invention, each of the decompressed executable codewords 5 corresponds to an instruction.

  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 respective decompression table. gathering executable code words from the executable code portion.

  The invention also relates to a microprocessor comprising a decompression unit as defined above.

  A preferred embodiment of the invention will be described below, by way of nonlimiting 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 as a flowchart a sequence of compression processes performed 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; FIG. 6 illustrates in the form of a flowchart a decompression method according to the invention; FIG. 7 schematically represents the architecture of a calculator 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.

  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. The compression algorithm is chosen so that each word of the executable code is compressed as a fixed length portion and a variable length portion. This algorithm is of the "variable length" type, based on the frequency of occurrence of the different words in the code to be compressed, short codes being assigned to the most frequent words to compress, and longer codes to the words to compress the words. more rare. The chosen algorithm is for example derived from the Huffman method.

  Then, all the fixed length portions are grouped together in a fixed length compressed instruction block 11, and all the variable length parts are grouped into a variable length compressed instruction block 12, an addressing table 13 being configured to access the compressed instructions in the variable length compressed instruction block 12 without having to read and uncompress all previous instructions in the block.

  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 in parallel the parts of fixed and variable length.

  Advantageously, 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 fixed parts FCL and a line of variable parts VCL. In this context, 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: VCLL (0), VCLi (1), VCLL (2) and VCLL (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 VCLL (0), and the lengths Li (0), LL (1), Li (2) in number of bits, first, second and third lines VCLi (0), VCLi (1) and VCLi (2).

  The respective positions PO), PP (2), Pi (3) in number of bits of the second, third and fourth lines VCLi (1) VCLi (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) = P, (k-1) + Li (k-1), for k = 1 to 3 (1) The length L43) of the fourth line VCLL (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 from the position Pi (3) of the fourth group: Li (3) = Pi + 1 (0) Pi (3) (2) Each word j of the addressing table 13 comprises, for example, 64 bits distributed in the various fields as follows: bits 63 to 33: P; (0) bits 32 at 22: Li (0) Bits 21 to 11: L (1) Bits 10 to 0: Li (2) The addressing table 13 thus allows 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.

  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.

  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.

  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.

  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, certain values of the code BC will have to be reserved for other uses such as the coding of the words of the source code not found in the compression table 10.

  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.

  2888013 -15- If two values of the BC code can be reserved for the encoding of the words to be compressed that are not 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.

  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.

  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 length of the variable part 12 of the compressed code, given that the length of the fixed part 11 of the compressed code depends on the number of instructions in the source code to be compressed and the length (in number of bits) chosen for the BC code.

  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.

  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.

  The size T of the variable part 12 of the compressed code is obtained by the following formula: ## EQU1 ## ## EQU1 ## Vlitteral (3) i = 0 j = Hi 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 subword -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 number of words in 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 code word to be compressed. not in the decompression table.

  HN can be calculated using the following formula: N 1 HN = 12Vi (4) i = 0 If S is the maximum size reserved for the decompression table 10, HN S. If two values of the BC code can be reserved at the coding of the words to be compressed not found in the compression table, the formula (3) becomes: N 2 Hi + 1 T = Vi E Io; + (M HN) É (Vlitteral -1) (5) i = 0 j = Hi Similarly, if we can reserve a value of the code BC to specify that the word to compress is the same as the previous word, the formula ( 3) becomes: N 2 Hi + 1 T = E Vi E Oj + (M-HN) V Eteral (6) i = 0 j = Hi 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.

  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. IO '+ (M HN)' (Vlitterai -1) (7) i = 0 j = Hi Using formulas (3), (5), (6) and (7), T is calculated as applied to the code to compress for all the possible partitions of the decompression table into sub-tables, that is to say for all the possible values of Hi, by imposing that Vi V; +1, that is to say that the size of the sub-table i is less than or equal 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 V components are thus determined; the compression model.

  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.

  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.

  If the word to be compressed does not appear in the decompression table 10, the corresponding code BC (step 337) is inserted in the compressed code, then the word to be compressed or part of it if the chosen code BC specifies the bits. of the word to compressed not inserted (step 338).

  Advantageously, it is planned to split each instruction of the binary source code to be compressed in 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, lengths 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.

  FIG. 6 illustrates the decompression method corresponding to the compression method described above with reference to FIG.

  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 performed using the following formula: m = (AD ADs) / DLS (8) where ADs is the start address of the compressed program and DLS is the length of an instruction line.

  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.

  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 as follows: if k = m modulo 4 = 0, 2888013 - 19 -P (m) = PP (0), (9) otherwise, if k = 1, 2 or 3, P (m) = Pi (k 1) + LJ (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 + (LL (k) 1) / 32 At the next step 45, read the fixed part FCL (m) of the compressed code line 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.

  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.

  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 code BC is to reference a sub-table of the decompression table 10, the address of the corresponding sub-table 21 in the decomposition table 2888013 - 20 - 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 '.

  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.

  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. the decompression unit DecU, a decompression engine DE in charge of the actual decompression processing, and a DCC cache control circuit.

  2888013 -21 - The decompression engine DE includes registers CRL, CRI intended to receive the table 1.5 to give 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.

  The DCC cache control circuit comprises: a master bus MIF interface adapted to be connected to the PB bus switch S, a PFB input buffer memory connected to the MIF interface, a set of registers 18 provided to receive addresses making it possible to access 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 WA working memory area 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.

  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.

  Advantageously, the compressed code is distributed in the program memory in compressed code pages, each page comprising a fixed portion and a variable portion 12 of compressed code, and an address table 13. The set of 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.

  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.

  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.

  Each address received as an instruction request from the CPU via the PMX relates to a group of four successive instructions. Upon receiving such a request, the DCC control circuit checks whether the address of the required instruction group is in the AD DL fields [i] of the Tags table. The control circuit DCC considers that the required instructions are decompressed in the cache memory CM if the required address is in the Tags table and if the corresponding global bit of validity GL [i] is raised, and if bit is 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.

  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. .

  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 cache, whenever a group of four decompressed instructions is written to the cache. When an entire line 2888013 - 24 of decompressed instructions is entered in the cache memory, the control unit updates the global validity bit GV [i] corresponding to the line.

  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.

  At the same time, it is also possible to use another cache memory for storing the words read in the addressing table 13.

  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.

  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 (31)

- 25 - CLAIMS   A method of executable code compression (2) by a microprocessor, comprising the steps of breaking down the executable code into words, and compressing each executable codeword, characterized in that each executable executable codeword comprises a portion (BC ) of predefined fixed length and a variable length portion (VLI) whose length is defined by the fixed length portion, the method further comprising a step of grouping all the fixed length portions and all variable length portions of the fixed length portion; words respectively in a block (11) of fixed length portions and in a block (12) of variable length portions, the respective positions of at least some variable length portions in the variable length portion block being stored in a addressing table (13).   A compression method according to claim 1, wherein the executable code is divided into lines (DL) of a predefined number of instructions, each line of executable code being compressed into a line (FCL) of portions (BC) of fixed length in the block (11) of fixed length portions, and a line (VCL) of variable length portions in the block (12) of variable length portions, each of the variable length portion lines being localized in the block (12) of variable length portions using the addressing table (13).   The compression method according to claim 2, wherein the addressing table (13) comprises a group entry of a predefined number of lines of variable length portions (VC40), VCL; (1), VCLL (2). ), VCLL (3)), each input (j) specifying the position (Pj (0)) of a first line (VC40)) of variable length parts in all of the variable length portions (12) of the code compressed, and the respective lengths (4 (0), 42)) of lines of variable length portions of the group, except a last line (VCL, (3)) of variable length portions of the group, the length of which is determined at using the position (Pi +, (0)) of a first line of variable length portions of a group (j + 1) of lines of following variable length portions.   4. A compression method according to one of claims 1 to 3, wherein each of the executable code words to be compressed corresponds to a 26 - instruction.   5. A compression method according to one of claims 1 to 3, 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, for obtaining for each instruction word of the executable code a fixed length portion (BC) which is inserted in the block (11) of fixed length portions and a variable length portion which is inserted in the block (12) of parts of variable length.   The compression method according to one of claims 1 to 5, wherein the compressing 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 code executable, and   extracting (32) at least a portion of the words of the histogram in a decompression table (10), wherein the words are subtached (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 code decompression sub-table of the executable code.   The compression method according to claim 6, wherein the words of the executable code (2) associated in the histogram (9) with a number of occurrences lower 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 6 or 7, wherein if two identical executable codewords occur consecutively in the executable code (2) to be compressed, the second executable code word is compressed without a variable length part, to the using a fixed-length part (BC) of 2888013 -27- specifying that the executable codeword is the same as the preceding word.   The compression method according to one of claims 6 to 8, 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) either the corresponding executable code word is the second word of two identical consecutive words of the executable code, or the variable length portion of the compressed word contains at least a portion of the corresponding executable code word.   A compression method according to claim 9, 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 test phase of the program. .   11. A method of compression according to one of claims 6 to 10, 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 parts of variable length of the compressed code as small as possible.   12. A compression method according to one of claims 6 to 11, 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 of decompressing executable code (2) by a microprocessor (CPU), stored in a compressed program memory area, the method comprising the steps of: receiving from the microprocessor executable code instruction requests including a instruction address to be executed, determine a read address of an address table (13) according to the instruction address to be executed, read at the read address in the information addressing table 2888013 For addressing the compressed words corresponding to the instruction to be executed, determining, as a function of the addressing information read, a reading address of the program memory, reading the program memory at the reading address, and decompressing the words read and transmit them to the microprocessor, characterized in that each word of the executable code (2) is compressed in the form of a predefined fixed length part (BC) and a part (VLI) of e variable length whose length is defined by the fixed length portion, all the fixed length portions and all variable length portions of the executable codewords being respectively grouped in a block (11) of fixed length portions and in a block (12) of variable length portions, at least some variable length portions being localized in the block (12) of variable length portions using an address table (13), the decompression method comprising furthermore, the steps of: determining a read address in the block of fixed length portions as a function of the address of the instruction to be executed, reading the blocks of fixed and variable length portions at the determined reading addresses, and decompressing the fixed and variable length portions read to obtain an executable instruction which is transmitted to the microprocessor.   The decompression method according to claim 13, wherein the compressed code is organized in lines (FCL) of fixed length portions and in lines (VCL) of variable length portions, each line of fixed length portions and the line of variable length. associated variable length portions corresponding to a respective line (DL) of a predefined number of executable code instructions, each of the variable length portion lines being located in the program memory area using the addressing table (13), the method comprising steps of: reading a line of fixed length portions and a line of variable length portions, localized using the information read from the addressing table, and decompressing the lines of fixed and variable length parts read to obtain a line of executable instructions.   The decompression method according to claim 14, wherein the addressing table (13) comprises a group entry of a predefined number of lines of variable length portions (VCL, (0), VCLL (1), VCLL (2), 2888013 - 29 - VCLi (3)), each input (j) specifying the position (Pj (0)) of a first line (VCLL (0)) of parts of variable length in all the parts (12) of variable length of the compressed code, and the respective lengths (4 (0), 4 (2)) of the lines of variable length portions of the group, except a last line (VCL, (3)) of length portions variable of the group, the length of which is determined using the position (Pi + 1 (0)) of a first line of variable length parts of a group 0 + 1) of lines of parts of variable length following .   16. A method of decompression according to one of claims 13 to 15, wherein the fixed length portion of each compressed instruction references a sub-table (21) of a decompression table (10) gathering at least a part of the words executable code, 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 as a function of 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 refers to a variable length portion; -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, to a positio n defined by the variable length portion read.   The decompression method according to claim 16, 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 part fixed length (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; and if the fixed length portion (BC) specifies a breakpoint, a stop point is inserted into the uncompressed executable code.   18. The decompression method according to one of claims 13 to 17, wherein each of the decompressed executable codewords corresponds to an instruction.   The decompression method according to one of claims 16 to 17, 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.   20. 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, the decompression unit comprising: means for receiving microprocessor of executable code instruction requests including 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; an address table (13) for locating in the program memory certain stored compressed words, means for reading at the read address in the addressing table of the compressed word addressing information corresponding to the instruction to be executed means for determining, based on the read address information read a read address of the program memory, means for reading compressed words in the program memory e at the read address, means for decompressing the read compressed words to obtain an executable instruction, and means for transmitting to the microprocessor the executable instruction, characterized in that each word of the executable code (2) is compressed under the shape of a predefined fixed length portion (BC) and a variable length portion (VLI), the length of which is defined by the fixed length portion, 2888013 -31-all the fixed length portions and all the fixed length portions; variable length portions of the executable codewords being grouped in a program memory area respectively in a block (11) of fixed length portions and in a block (12) of variable length portions, at least some portions of variable length being located in the block (12) of variable length portions by means of an address table (13), the decompression unit further comprising: means for determining a read address in block d e parts of fixed length according to the address of the instruction to be executed, means for reading the block of fixed length portions to the determined reading address, and means for decompressing the fixed and variable length portions read to get an executable statement.   21. The decompression unit of claim 20, further comprising means for storing start addresses of the block of fixed length portions and the block of variable length portions of the compressed code.   A decompression unit according to claim 20 or 21, wherein the compressed code is arranged in rows (FCL) of fixed length portions and in lines (VCL) of variable length portions, each line of fixed length portions and the an associated variable length portion line corresponding to a respective line (DL) of a predefined number of executable code instructions, each of the variable length portion lines being located in the program memory area using a table addressing unit (13) stored in an area of the program memory, the decompression unit further comprising means for storing a start address of the addressing table.   The decompression unit of claim 22, wherein the addressing table (13) comprises a group entry of a predefined number of lines of variable length portions (VCLj (0), VCLj (1), VCLi ( 2), VCLi (3)), each input (j) specifying the position (P, (0)) of a first line (VCLL (0)) of variable length parts in all the parts (12) of variable length of the compressed code, and the respective lengths (4 (0), LL (1), Li (2)) of the lines of variable length portions of the group, except for a last line VCL, (3) of parts of variable length of the group, the length of which is determined using the position (PP +, (0)) of a first line of parts of 2888013 - 32 variable length of a group (j + 1) of lines of parts of length next variable, the decompression unit further comprising: means for receiving from the microprocessor (CPU) executable code instruction requests including an instruction address; s to read the addressing table according to the executable code instruction address provided by the microprocessor (CPU), means for determining with the help of the addressing table 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 for determining using the address table the position and the length in line program memory (VCL) of variable length portions containing the compressed code words corresponding to the instruction address provided by the microprocessor (CPU), and means for decompressing and storing all executable code instructions corresponding to the line (FCL) of fixed length portions read and to the line (VCL) of parts of variable length read.   24. The decompression unit according to one of claims 20 to 23, further comprising: a cache memory (CM) for storing a predefined number of decompressed instructions; means for reading the cache memory as a result of the reception of an instruction request issued by the microprocessor (CPU), and to transmit in response the corresponding instructions if they are in the cache memory.   25. Decompression unit according to one of claims 20 to 24, wherein at least some fixed length parts reference a subtable (21) of a decompression table (10) gathering at least a portion of the executable code words, the variable length portion giving the position in the sub-table of the executable codeword, the decompression unit further comprising: storing means (DTFO, DTF1) 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 (BC) and the variable length portion, if the fixed length portion references a sub-table of the decompression, and means for reading the executable code word at the determined position in the sub-table.   The decompression unit of claim 25, 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 25 or 26, 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 codeword is not present. in the decompression table (10).   28. The decompression unit according to one of claims 25 to 27, further comprising means for transmitting to the microprocessor (CPU) a program execution stop point, if the fixed length portion (BC) specifies it.   29. The decompression unit according to one of claims 20 to 28, wherein each of the decompressed executable code words corresponds to an instruction.   30. decompression unit according to one of claims 25 to 28, 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.   31. Microprocessor comprising a decompression unit (DecU) according to any one of claims 20 to 30.