Data compaction method for an intermediate object code program executable in an onboard system provided with data processing resources and corresponding onboard system with multiple applications

• US 6,952,820 B1
• Filed: 11/04/1999
• Issued: 10/04/2005
• Est. Priority Date: 11/06/1998
• Status: Expired due to Term

• Current Assignee: CP8 Technologies (Thales SA)
• Original Assignee: Institut National de Recherche en informatique et en Automatique, Bull CP8 (Schlumberger NV)
• Inventors: Goire, Christian, Consel, Charles, Schultz, Ulrik Pagh, Muller, Gilles, Clausen, Lars
• Primary Examiner(s): Ingberg, Todd
• Assistant Examiner(s): Nahar, Qamrun
• Application Number:
  US09/582,939
• Time in Patent Office: 2,161 Days
• Field of Search: 717/151, 717/152, 717/159, 717/147, 717/146, 712/245
• US Class Current: 717/151
• CPC Class Codes: G06F 8/4436 Exlining; Procedural abstraction
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836

Abstract

The invention concerns a data compaction method and system for an intermediate program. The method consists in searching the program (1000) for identical sequences (Si) and counting Ni number of occurrences of each sequence (Si), a comparison test (1001) to find the superiority of a function f(Ni) to a reference value enables to generate (1003) a specific instruction of a specific code (Ci) with which the sequence (Si) is associated, replacing (1004) each occurrence in the sequence (Si) by the specific code (Ci) in the intermediate program to create a compacted intermediate program (FCC) with which an executing file (FEX) is associated. The invention is applicable to multiple application portable objects such as microprocessor cards, onboard systems of the like.

Claims

1. A method of compacting an intermediate program comprising a sequence of standard instructions, used in an on-board system, said on-board system being provided with a memory and a program language interpreter capable of turning the intermediate program into instructions of an object code that can be run by a microprocessor through said interpreter, said method comprising the steps of:

a) searching through said intermediate program for identical sequences of successive standard instructions,

b) subjecting said identical sequences of successive instructions to a comparison test to find a function, based on at least the number of occurrences of these sequences in said intermediate program, that is higher than a reference value,

 

and, if the test returns a positive response, for each identical sequence of successive standard instructions which satisfies said test step,

c) generating a new specific instruction by defining a specific operating code and associating said specific operating code with the sequence of successive standard instructions which satisfied said test,

d) replacing each occurrence of each sequence of standard successive instructions in said intermediate program with said specific operating code associated with it to obtain a compacted intermediate program, consisting of a series of standard instructions and specific operating codes, and

e) storing in said memory an execution table which enables a reciprocal link to be established between each specific operating code inserted and the sequence of successive standard instructions associated with said specific operating code,

 

thereby enabling the memory space occupied by said compacted intermediate program to be optimized by storing only one occurrence of said identical sequences of successive standard instructions in said memory.

2. A method as claimed in claim 1, wherein said function is also a function of the size of each identical sequence of successive instructions.

3. A method as claimed in claim 1, wherein in order to compress a plurality of intermediate programs, said method also comprises the steps of:

storing said execution table relating to at least one compacted intermediate program,

and, for every additional intermediate program subjected to a compaction process;

reading said stored execution table, and

running the compaction process for every additional program, taking account of the specific codes and instructions stored in said execution table.

4. A method of running a compacted program comprising a succession of standard instructions and specific operating codes stored in a memory of an on-board system,

said compacted program being obtained by applying a method of compacting an intermediate program comprising a sequence of standard instructions, used in said on-board system, said on-board system being provided with a memory and a program language interpreter capable of turning the intermediate program into instructions of an object code that can be run by a microprocessor through said interpreter;

said method comprising the steps of;

a) searching through said intermediate program for identical sequences of successive standard instructions;

b) subjecting said identical sequences of successive instructions to a comparison test to find a function, based on at least the number of occurrences of these sequences in said intermediate program, that is higher than a reference value;

and, if the test returns a positive response, for each identical sequence of successive standard instructions which satisfies said test step;

c) generating a new specific instruction by defining a specific operating code and associating said specific operating code with the sequence of successive standard instructions which satisfied said test;

d) replacing each occurrence of each sequence of standard successive instructions in said intermediate program with said specific operating code associated with it to obtain a compacted intermediate program, consisting of a series of standard instructions and specific operating codes; and

e) storing in said memory an execution table which enables a reciprocal link to be established between each specific operating code inserted and the sequence of successive standard instructions associated with said specific operating code;

thereby enabling the memory space occupied by said compacted intermediate program to be optimized by storing only one occurrence of said identical sequences of successive standard instructions in said memory;

wherein said method for running the compacted program is performed by said microprocessor through said program interpreter for interpreting said standard instructions and said specific instructions, and comprises the steps of;

recognizing in said memory the existence of a stored execution table containing at least one sequence of successive instructions associated with a specific operating code by means of a reciprocal link;

calling up a command, via said program language interpreter, to read the successive standard instructions or specific operating codes of said compacted intermediate program and, in the presence of a specific operating code;

retrieving said sequence of successive instructions associated with said specific operating code from the memory by means of a read instruction and, in the presence of a standard instruction;

commanding the execution of said standard instruction by means of a read instruction.

5. A method as claimed in claim 4, wherein if a sequence of successive instructions associated with a specific operating code is called up, the current value of a program counter is incremented in a stack associated with the specific operating codes and a program pointer points to the first instruction of said sequence of specific instructions, after which, on running an instruction to end the sequence of specific instructions, said program counter is decremented and the execution process continues starting with the next instruction or specific operating code.

6. A method as claimed in claim 5, wherein the stack associated with the specific operating codes and the stack associated with the standard instructions are a single stack.

7. A multi-application on-board system comprising computing resources, a memory and language interpreter capable of turning an intermediate program into instructions which are executable by the computing resources through said language interpreter, wherein said multi-application on-board system also at least comprises:

one table of standard codes constituting said intermediate program stored in a memory to which said language interpreter is able to access to;

at least one compacted intermediate program constituting an application and consisting of a series of specific instruction codes and standard instruction codes, said specific instruction codes corresponding to sequences of successive standard instructions;

an execution table stored in a memory to which said language interpreter is able to access to, and enabling a reciprocal link to be established between an operating specific instruction code and the sequence of successive standard instructions associated with the latter, said at least one compacted intermediate program and said execution table being stored in said memory, thereby enabling the memory space occupied by said compacted intermediate program to be optimized by storing in said programmable memory only one occurrence of said identical sequences of successive instructions.

8. An on-board system as claimed in claim 7, wherein said execution table comprises at least:

a file of successive sequences corresponding to said specific instruction codes;

a table of specific instruction codes and addresses at which said specific instruction codes are embedded in the table of successive sequences.

9. An on-board system as claimed in claim 8, wherein said file of successive sequences corresponding to said specific instruction codes and said table of specific instruction codes are stored in a programmable memory of said on-board system.

10. A compaction system for an intermediate program, said intermediate program consisting of a series of standard instructions which can be executed by a target unit, wherein said system comprises at least:

means for analyzing all the standard executable instructions enabling, by means of a reading process, said intermediate program to distinguish between and establish a list of all the sequences of executable standard instructions contained in said intermediate program;

means for counting the number of occurrences in this intermediate program of each of the sequences of executable standard instructions forming part of said list;

means for allocating to at least one sequence of executable standard instructions a specific code associated with this sequence of executable standard instructions in order to generate a specific instruction;

means for replacing, in said intermediate program, each occurrence of said sequence of executable standard instructions with said specific code associated with this sequence of executable standard instructions, representative of said specific instruction, thereby enabling a compacted program to be generated comprising a succession of executable standard instructions and specific instructions.

11. A compaction system as claimed in claim 10, wherein said means for allocating to at least one sequence of executable standard instructions a specific code associated with said sequence of executable standard instruction in order to generate a specific instructions comprises at least:

means for computing the value of a function based on at least the length of and number of occurrences of said sequence of executable standard instructions, said function being representative of the compression gain for said sequence of executable standard instructions;

means for comparing the value of said function with a threshold value and, if said comparison returns a positive response;

means for writing to a file, with a reciprocal link, a specific code and this sequence of executable standard instructions in order to constitute said specific instruction.