Method and system for compressing program code and interpreting compressed program code

• US 6,907,598 B2
• Filed: 06/05/2002
• Issued: 06/14/2005
• Est. Priority Date: 06/05/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Fraser, Christopher Warwick
• Primary Examiner(s): Das, Chameli C.
• Application Number:
  US10/164,032
• Publication Number:
  US 20030229709A1
• Time in Patent Office: 1,105 Days
• Field of Search: 717/127, 717/131, 717/136, 717/139, 717/140, 717/107, 382/232, 382/233, 718/1, 712/208, 712/245
• US Class Current: 717/127
• CPC Class Codes: G06F 9/3017 Runtime instruction translation, e.g. macros
• CPC Class Codes: G06F 9/45504 Abstract machines for programme code execution, e.g. Java virtual machine [JVM], interpreters, emulators

Abstract

A computer system and method for compressing an instruction stream and executing the compressed instruction stream without decompression. The invention utilizes a new pointer instruction, i.e., an “Echo” instruction that is used to replace repeated instructions or sequences of instructions, also referred to as phrases. Replacing subsequent, repeated phrases with the Echo instruction reduces the size of the instruction stream, i.e., compresses the instruction stream. The Echo instruction generally identifies at least one literal instruction appearing before the Echo instruction and further identifies the number of instructions appearing before the Echo instruction to be repeated. No additional delimiters are necessary, e.g., no End Echo instructions are required. Omitting the End Echo instruction allows for overlapping phrases without the need for two Echo instructions. Reducing the number of instructions used significantly increases compression.

Claims

1. A computer system for executing a compressed stream of instructions, the stream of instructions stored in a program store, the instruction stream having literal instructions and one or more Echo instructions for repeating one or more literal instructions, each Echo instruction relating to one or more literal instructions located in the program store, the system comprising:

an execution module that executes literal instructions in the instruction stream;

an evaluation module that determines whether an instruction is a literal instruction or an Echo instruction;

an Echo module for executing the one or more Echo instructions; and

wherein at least one Echo instruction comprises;

a first parameter that identifies the first instruction to be repeated; and

a second parameter that identifies the last instruction to be repeated.

2. A computer system as defined in claim 1 wherein the system further comprises a program counter used to identify instructions within the program store and wherein the Echo module further comprises:

a program counter control module, the program counter control module controlling the value of the program counter, wherein the value of the program counter identifies the next instruction to be executed by the computer system; and

a count module for maintaining a count of instructions to be repeated during execution of the one or more Echo instructions, the count module using the second parameter of the Echo instruction to maintain the count.

3. A computer system as defined in claim 2 wherein the program control module further stores the present value of the program counter upon execution of an Echo instruction and modifies the value of the program counter to identify a previous instruction in the program store.

4. A computer system as defined in claim 3 wherein the program control module restores the stored value of the program counter upon completion of the Echo instruction.

5. A computer system as defined in claim 4 wherein:

the first parameter is a displacement value, the displacement value indicating a number of addressable units between the Echo instruction and a first instruction in the phrase; and

the second parameter is a count value related to the number of instructions in the phrase.

6. A computer system as defined in claim 5 wherein, upon execution of one of the Echo commands, the displacement value is subtracted from the program counter by the program counter control module, and wherein the count value is used by the count module to indicate a number of instructions to be repeated.

7. A computer system as defined in claim 6 further comprising:

memory;

a receive module for receiving the compressed stream of instructions and storing the compressed stream of instructions in memory; and

an access module for accessing the stored compressed stream of instructions.

8. A computer system as defined in claim 7 wherein the system has a restricted amount of memory and wherein the execution of the compressed instruction stream does not decompress the compressed instruction stream.

9. A computer system as defined in claim 1 wherein the compressed instruction stream is executed without decompression.

10. A computer system as defined in claim 1 wherein the instruction stream is a byte-code.

11. A method of executing a compressed instruction stream, the compressed instruction stream having one or more literal instructions and one or more Echo instructions, the method comprising:

evaluating one of the instructions in the instruction stream to determine whether the instruction is one of the literal instructions or one of the Echo instructions, wherein each Echo instruction identifies at least one literal instruction appearing before the Echo instruction to be repeated, and wherein the Echo instruction further identifies the number of instructions appearing before the Echo instruction to be executed;

upon determining that the evaluated instruction is one of the literal instructions, executing the literal instruction; and

upon determining that the instruction is one of the Echo instructions, executing the number of previous instructions.

12. A method as defined in claim 11 wherein the instruction stream is a byte-code.

13. A method as defined in claim 11 wherein the Echo instructions comprise at least two parameters:

a displacement value parameter associated with the first instruction to be executed, the displacement value indicating a number of intermediate addressable units between the Echo instruction and a first instruction in a repeated phrase of instructions; and

a count value parameter identifying the number of instructions in the repeated phrase.

14. A method as defined in claim 13 wherein the act of executing one or more previously executed literal instructions further comprises:

saving an original program counter value;

modifying the program counter based on the displacement value; and

performing one or more literal instructions identified by the modified program counter.

15. A method as defined in claim 14 further comprising:

upon executing one or more instructions identified by the modified program counter, restoring the previous program counter value and any previous length counter value; and

executing the instruction immediately following the Echo instruction.

16. A method as defined in claim 14 further comprising:

upon executing one or more instructions identified by the modified program counter, restoring the original program counter value; and

executing the instruction immediately following the Echo instruction.

17. A method as defined in claim 16 wherein the modification of the program counter comprises subtracting the displacement value from the original program counter value to establish a remainder and setting the program counter to the remainder.

18. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 17.

19. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 14.

20. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 11.

21. A computer-readable medium having stored thereon a data structure, the data structure comprising:

a compressed instruction stream of instructions executable by a computer system, the instruction stream comprising;

one or more literal instructions;

one or more Echo instructions, wherein the Echo instruction identifies at least one literal instruction appearing before the Echo instruction, and wherein the Echo instruction further identifies the number of instructions appearing before the Echo instruction to be executed; and

encoding to differentiate Echo instructions from literal instructions.

22. A data structure as defined in claim 21 wherein the instruction stream may be executed without decompression.

23. A data structure as defined in claim 22 wherein the Echo instruction comprises:

an opcode region indicating the type of operation;

a displacement region indicating the location of a repeatable phrase; and

a length region indicating the length of the repeatable phrase.

24. A data structure as defined in claim 23 wherein the Echo instruction further comprises an offset region indicating an offset value, the offset value relating to a number of instructions to skip during interpretation of the Echo instruction.

25. A method of compressing an instruction stream of literal instructions, the method comprising:

sequentially evaluating the instruction stream of instructions;

determining that one or more phrases are repeated; and

replacing at least one instance of the one or more repeated phrases with an Echo instruction to build a compressed instruction stream, the compressed instruction stream being directly interpretable without decompression.

26. A method as defined in claim 25 further comprising encoding the instruction stream to provide means of differentiation between the literal instructions and the Echo instructions.

27. A method as defined in claim 26 further comprising:

upon determining that a phrase is repeated, determining a displacement value relating to the distance between the first occurrence of the phrase and the second occurrence of the phrase;

determining a length value relating to the number of instructions in the repeated phrase; and

encoding the displacement and length values into the Echo instruction, wherein the Echo instruction replaces the second occurrence of the phrase.

28. A method as defined in claim 27 further comprising:

upon determining that a phrase is repeated, determining whether the phrase is replaceable based on predetermined criteria; and

wherein the phrase is replaced if determined that the phrase is replaceable.

29. A method as defined in claim 28 wherein the predetermined criteria relates to branch instructions, wherein the phrase is not replaceable if the phrase includes a branch instruction.

30. A method as defined in claim 28 wherein the predetermined criteria relates to conditional branch instructions, wherein the phrase is not replaceable if the phrase includes a conditional branch instruction.

31. A method as defined in claim 28 wherein the predetermined criteria relates to jump instructions, wherein the phrase is not replaceable if the phrase includes a jump instruction.

32. A method as defined in claim 28 wherein the predetermined criteria relates to labels, wherein the phrase is not replaceable if the phrase includes a label.

33. A method as defined in claim 28 wherein the predetermined criteria relates to labels, wherein the phrase is replaceable if the phrase includes a label, the Echo instruction replacing the phrase including the label further comprising an offset value.

34. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 28.

35. A method as defined in claim 27 wherein the Echo instruction relates to another Echo instruction.

36. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 25.