Electrical computers and digital processing systems: processing – Instruction decoding – Decoding instruction to accommodate plural instruction...
Reexamination Certificate
1999-04-29
2002-01-15
Kim, Kenneth S. (Department: 2783)
Electrical computers and digital processing systems: processing
Instruction decoding
Decoding instruction to accommodate plural instruction...
C712S200000
Reexamination Certificate
active
06339820
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to a method and a device for carrying out at least one function assigned to an instruction code. More particularly, the method, respectively the device, represents a space-efficient and flexible mechanism for implementing a virtual machine in a resource-constrained environment such as a smartcard, particularly a smartcard offering a Java environment, such as a Javacard.
TECHNICAL FIELD AND BACKGROUND OF THE INVENTION
In a system environment with constrained resources such as limited code storage area, usually a ROM, limited application storage area, usually an EEPROM, limited runtime memory, usually a RAM, and limited compute power, i.e, small CPU and low clock cycle rate, the interpretive approach to running applications is well-known. Due to the higher level of abstraction provided by the interpreted code over the machine code, the use of more compact application code is possible, which is an essential requirement in the aforementioned environments. Therefore, the availability of an interpreter is desirable in an embedded system.
OBJECT AND ADVANTAGES OF THE INVENTION
It is an object of the invention according to claim 1 and 8, to provide a method and a device for executing instruction codes, which require less memory. It is another object of the invention according to claim 1 and 8, to provide a method and a device for executing instruction codes which provides for an easier way to amend the instructions codes, respectively functions which are to be carried out.
The above mentioned objects are met by a method according to claim 1 and a device according to claim 8. Regardless of whether the interpreter, also called “virtual machine”, is implemented in software or in hardware, the following two problems are solved:
Firstly, the size of the internal main loop serving for the dispatching respectively executing of the codes, herein called “opcodes”, interpreted in the virtual machine, as well as the size and also number of functions necessary to implement the opcodes is reduced. It is most advantageous to get both to the minimum size because of the aforementioned resource constraints in embedded systems, i.e. a system e.g. on a smartcard.
Secondly, it might be desirable to be able to change and/or enhance the semantics of single opcodes without changing the code of either the main loop or code implementing the other opcodes. The latter is especially important in an area where opcodes can change due to specification changes, error fixes, particularly at the level of single opcodes, or performance improvements requiring the modification/addition of single opcodes.
The approach using a virtual machine which is designed for interpreting or carrying out instructions which are identified by an instruction code whereby the addresses of the functions implementing the opcodes which the virtual machine interprets, as well as parameters to those functions are kept within lookup tables, yields two primary benefits:
First, the main interpreter loop is very small, and due to the parameter table, generic functions can be referred to by the opcode table, thus leading to a very space-efficient representation of the virtual machine code.
Second, by placing these tables into a mutable memory, such as an EEPROM, error-fixing as well as general maintenance of the virtual machine is feasible at the level of single opcodes even after production of the actual hardware.
SUMMARY OF THE INVENTION
The invention uses generic opcode tables in conjunction with parameter tables. The idea is to use two types of lookup tables at the core of the virtual machine implementation. The first table, called also “opcode lookup table”, contains for each opcode the address of a function implementing its semantics. As these functions might be generic, i.e., serve for several opcodes as their implementation, a second, discriminating table, also called “parameter lookup table”, is used. Both tables contain the same number of entries, which is identical to the number of opcodes understood by the respective virtual machine. The tables can also be unified to one single table with the opcodes, the functions and the parameters as entries.
Especially in a scenario, where many functions can be shared between opcodes, this approach is advantageous: Only a minimum number of these generic routines, which hence results in an according minimum requirement of code size, need be employed because of the use of the functionality-discriminating parameter table. For example, it is assumed that such a scenario of function-sharing for opcode implementations is common if a virtual machine originally intended for a non-resource-constrained environment has to be semantically stripped down to run in a resource-constrained environment. Therewith, the reduction of the functionality of the virtual machine eventually leads to a reduction in complexity of many opcodes, in turn leading to the aforementioned opportunity to create generic functions.
Execution of the virtual machine main loop then can proceed as follows:
An opcode to be interpreted is loaded from memory.
The address of the opcode-realizing function is looked up from the opcode lookup table.
A parameter for this function is read from the parameter lookup table. This part of the procedure is optional. Possibly no parameter may be needed. The lookup then returns no parameter or a read parameter can be ignored by the function.
The parameter can be loaded into a unique address, e.g., a variable.
The function for the instruction code is called and executed.
The function returns, and the next opcode is fetched and executed.
This way, the code of the core of the virtual machine does not need modification, even if new opcodes are added, since the table is in that case just extended. Also, if old codes are changed, address and parameter entries can be simply changed at the index corresponding to the respective opcode. If opcodes are to be removed, table entries can be invalidated.
By the invention's concept, the implementation of the virtual machine core and the implementation of each single opcode are separated.
This yields the following advantages: The virtual machine core is extremely small in size. By having the lookup tables reside in immutable memory, e.g. a ROM, an implementation of a virtual machine can be secured against future changes. By having the lookup tables reside in mutable memory, e.g. EEPROM, an implementation of a virtual machine can be changed after delivery of the implementation to the customer.
Although optimizing compilers are known to build memory-efficient jump tables for the alternative implementation of a virtual machine core, i.e., CASE or SWITCH statements, they have four primary disadvantages solved by the proposed concept: First, they still bear an overhead due to the inclusion of the inevitable ‘JMP’ machine code statement, which is necessary, since executable code must be the result of a compiler/linker. Second, they always reside in the immutable area shared with all machine code. Third, it is impossible to only change single cases, i.e., implementations of single opcodes after the code has been produced, i.e., put into ROM or hardware. Fourth, compiler-generated optimizations are highly compiler-dependent and cannot be relied on to be done correctly on all platforms.
The advantage of the proposed solution is that it works on all system architectures the virtual machine is intended to work in, without change. In fact, if the virtual machine core were implemented in hardware, by putting the lookup tables into mutable memory, this approach would permit the enhancement of a hardware-based virtual machine even after production “in the field”, i.e., even after a customer has started to use it. This is an invaluable advantage if resources are scarce, thus not permitting an update of the complete virtual machine if only single opcode's implementations need enhancements.
REFERENCES:
patent: 4703416 (1987-10-01), Crupi et al.
patent: 5784640 (1998-07-01), Asghar et al.
patent: 6058402 (2000-05-01), Fleiken
Baentsch Michael
Buhler Peter
Eirich Thomas
Hoering Frank
Oestreicher Marcus
Herzberg Louis P.
Kim Kenneth S.
LandOfFree
Method and device for carrying out a function assigned to an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and device for carrying out a function assigned to an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for carrying out a function assigned to an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2826556