Method and apparatus for improved compression and decompression

• US 6,618,506 B1
• Filed: 09/23/1997
• Issued: 09/09/2003
• Est. Priority Date: 09/23/1997
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Montoye, Robert Kevin, Auerbach, Daniel Jonathan, Kemp, Timothy Michael, Palmer, John Davis
• Primary Examiner(s): Chen, Wenpeng
• Application Number:
  US08/936,201
• Time in Patent Office: 2,177 Days
• Field of Search: 382/232, 382/239, 382/245-247, 341/51, 341/67, 348/404-407, 348/419, 358/261.2, 358/430, 395/381, 395/800.24, 712/210, 712/225, 717/151, 717/157
• US Class Current: 382/232
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction

Abstract

A method and apparatus for compression and decompression of information, such as groups of computer program instructions, encodes (compresses) information comprising a plurality of units by receiving the information to be encoded, splitting the information into a plurality of subsets, each subset comprising a plurality of symbols, each symbol comprising at least a portion of a unit of information, and assigning a codeword to each symbol, for each subset. Preferably, the assignment is performed by determining the frequency of occurrence of each symbol, for each subset, and assigning a codeword to each symbol, based on the frequency of occurrence of each symbol, for each subset. In order to decode (decompress) encoded information, the information comprising a plurality of codewords, each codeword is decoded to form a symbol, each symbol is grouped into one of a plurality of subsets and the plurality of subsets is merged to form decoded information.

Claims

1. A method of compressing a computer program of executable instructions, comprising the steps of:

splitting each instruction of a plurality of the instructions of the program into a first symbol and a second symbol, the first symbol assigned to first subset and the second symbol assigned to a second subset, wherein each instruction of the plurality consists of one opcode and one or more operands, the first symbol comprising the opcode and the second symbol comprising the one or more operands;

assigning a first codeword to the first symbol representing a compressed form of the first symbol and assigning a second codeword to the second symbol representing a compressed form of the second symbol;

generating a first codeword-symbol assignment table for the first subset of symbols and a second codeword-symbol assignment table for the second subset of symbols; and

storing the codewords of the first subset as a first image representing a first compressed split instruction and the code words of the second subset as a second image representing a second compressed split instruction, the first and second compressed split instructions representing a compressed form of the computer program.

2. The method of claim 1, further comprising the step of:

determining a frequency of occurrence of each symbol, for each subset.

3. The method of claim 2, wherein the assigning step comprises the step of:

assigning a codeword to each symbol, based on the frequency of occurrence of each symbol, for each subset.

4. The method of claim 3, wherein each codeword comprises:

an index indicating a location in a codeword-symbol assignment table; and

a prefix indicating a length of the index.

5. The method of claim 4, wherein the generating step comprises the step of:

generating a plurality of symbol groups for each codeword-symbol assignment table.

6. The method of claim 3, wherein each codeword comprises:

an index indicating a location in one of a plurality of codeword-symbol assignment tables; and

a prefix indicating a length of the index.

7. A method of decompressing a computer program of executable instructions, the program having been compressed by splitting each instruction of a plurality of the instructions of the program into a first symbol and a second symbol, wherein each instruction of the plurality consists of one opcode and one or more operands, the first symbol comprising the opcode and the second symbol comprising the one or more operands, the first symbol assigned to first subset and the second symbol assigned to a second subset, assigning a first codeword to the first symbol representing a compressed form of the first symbol and assigning a second codeword to the second symbol representing a compressed form of the second symbol, generating a first codeword-symbol assignment table for the first subset of symbols and a second codeword-symbol assignment table for the second subset of symbols, storing the codewords of the first subset as a first image representing a first compressed split instruction and the code words of the second subset as a second image representing a second compressed split instruction, the first and second compressed split instructions representing a compressed form of the program, the method of decompressing, comprising the steps of:

accessing the first compressed split instruction;

reading a codeword in the first compressed split instruction and looking up a first symbol in the first codeword-symbol assignment table;

outputting the first symbol as a formed symbol of the first subset;

accessing the second compressed split instruction;

reading a codeword in the second compressed split instruction and looking up a second symbol in the second codeword-symbol assignment table;

outputting the second symbol as a formed symbol of the second subset; and

merging the first symbol of the first subset with the second symbol of the second subset to form a decoded instruction.

8. The method of claim 7, wherein each codeword comprises:

an index indicating a location in a codeword-symbol assignment table; and

a prefix indicating a length of the index.

9. A computer program product for compressing a computer program of executable instructions, the computer program product, comprising:

program code for splitting each instruction of a plurality of the instructions of the program into a first symbol and a second symbol, the first symbol assigned to first subset and the second symbol assigned to a second subset, wherein each instruction of the plurality consists of one opcode and one or more operands, the first symbol comprising the opcode and the second symbol comprising the one or more operands;

program code for assigning a first codeword to the first symbol representing a compressed form of the first symbol and assigning a second codeword to the second symbol representing a compressed form of the second symbol;

program code for generating a first codeword-symbol assignment table for the first subset of symbols and a second codeword-symbol assignment table for the second subset of symbols;

program code for storing the codewords of the first subset as a first image representing a first compressed split instruction and the code words of the second subset as a second image representing a second compressed split instruction, the first and second compressed split instructions representing a compressed form of the computer program; and

a medium to store said program codes.

10. A computer program product for decompressing a computer program of executable instructions, the program having been compressed by splitting each instruction of a plurality of the instructions of the program into a first symbol and a second symbol, wherein each instruction of the plurality consists of one opcode and one or more operands, the first symbol comprising the opcode and the second symbol comprising the one or more operands, the first symbol assigned to first subset and the second symbol assigned to a second subset, assigning a first codeword to the first symbol representing a compressed form of the first symbol and assigning a second codeword to the second symbol representing a compressed form of the second symbol, generating a first codeword-symbol assignment table for the first subset of symbols and a second codeword-symbol assignment table for the second subset of symbols, storing the codewords of the first subset as a first image representing a first compressed split instruction and the code words of the second subset as a second image representing a second compressed split instruction, the first and second compressed split instructions representing a compressed form of the program, the computer program product, comprising:

program code for accessing the first compressed split instruction;

program code for reading a codeword in the first compressed split instruction and looking up a first symbol in the first codeword-symbol assignment table;

program code for outputting the first symbol as a formed symbol of the first subset;

program code for accessing the second compressed split instruction;

program code for reading a codeword in the second compressed split instruction and looking up a second symbol in the second codeword-symbol assignment table;

program code for outputting the second symbol as a formed symbol of the second subset;

program code for merging the first symbol of the first subset with the second symbol of the second subset to form a decoded instruction; and

a medium to store said program codes.

11. A system for compressing a computer program of executable instructions, the system comprising:

a processor; and

a memory containing program instructions executable by the processor for performing the steps of;

splitting each instruction of a plurality of the instructions of the program into a first symbol and a second symbol, the first symbol assigned to first subset and the second symbol assigned to a second subset, wherein each instruction of the plurality consists of one opcode and one or more operands, the first symbol comprising the opcode and the second symbol comprising the one or more operands;

assigning a first codeword to the first symbol representing a compressed form of the first symbol and assigning a second codeword to the second symbol representing a compressed form of the second symbol;

generating a first codeword-symbol assignment table for the first subset of symbols and a second codeword-symbol assignment table for the second subset of symbols; and

storing the codewords of the first subset as a first image representing a first compressed split instruction and the code words of the second subset as a second image representing a second compressed split instruction, the first and second compressed split instructions representing a compressed form of the computer program.

12. A system for decompressing a computer program of executable instructions, the program having been compressed by splitting each instruction of a plurality of the instructions of the program into a first symbol and a second symbol, wherein each instruction of the plurality consists of one opcode and one or more operands, the first symbol comprising the opcode and the second symbol comprising the one or more operands, the first symbol assigned to first subset and the second symbol assigned to a second subset, assigning a first codeword to the first symbol representing a compressed form of the first symbol and assigning a second codeword to the second symbol representing a compressed form of the second symbol, generating a first codeword-symbol assignment table for the first subset of symbols and a second codeword-symbol assignment table for the second subset of symbols, storing the codewords of the first subset as a first image representing a first compressed split instruction and the code words of the second subset as a second image representing a second compressed split instruction, the first and second compressed split instructions representing a compressed form of the program, the system for decompressing, comprising:

a processor; and

a memory containing program instructions executable by the processor for performing the steps of;

accessing the first compressed split instruction;

reading a codeword in the first compressed split instruction and looking up a first symbol in the first codeword-symbol assignment table;

outputting the first symbol as a formed symbol of the first subset;

accessing the second compressed split instruction;

reading a codeword in the second compressed split instruction and looking up a second symbol in the second codeword-symbol assignment table;

outputting the second symbol as a formed symbol of the second subset; and

merging the first symbol of the first subset with the second symbol of the second subset to form a decoded instruction.

13. A system for decompressing a computer program of executable instructions, the program having been compressed by splitting each instruction of a plurality of the instructions of the program into a first symbol and a second symbol, wherein each instruction of the plurality consists of one opcode and one or more operands, the first symbol comprising the opcode and the second symbol comprising the one or more operands, the first symbol assigned to first subset and the second symbol assigned to a second subset, assigning a first codeword to the first symbol representing a compressed form of the first symbol and assigning a second codeword to the second symbol representing a compressed form of the second symbol, generating a first codeword-symbol assignment table for the first subset of symbols and a second codeword-symbol assignment table for the second subset of symbols, storing the codewords of the first subset as a first image representing a first compressed split instruction and the code words of the second subset as a second image representing a second compressed split instruction, the first and second compressed split instructions representing a compressed form of the program, the system for decompressing, comprising:

accessing logic for accessing the first compressed split instruction;

look up logic coupled to the accessing logic, for reading a codeword in the first compressed split instruction and looking up a first symbol in the first codeword-symbol assignment table;

output logic coupled to the look up logic, for outputting the first symbol as a formed symbol of the first subset;

said accessing logic accessing the second compressed split instruction;

said look up logic reading a codeword in the second compressed split instruction and looking up a second symbol in the second codeword-symbol assignment table;

said output logic outputting the second symbol as a formed symbol of the second subset; and

merging logic coupled to the output logic, for merging the first symbol of the first subset with the second symbol of the second subset to form a decoded instruction.

14. A method of compressing a computer program of executable instructions, comprising the steps of:

splitting each instruction of a plurality of the instructions of the program into a first symbol and a second symbol, the first symbol assigned to first subset and the second symbol assigned to a second subset, wherein each instruction of the plurality consists of one opcode and one or more operands, the first symbol comprising a first half of the instruction including at least part of the opcode and the second symbol comprising the second half of the instruction including at least part of the one or more operands;

assigning a first codeword to the first symbol representing a compressed form of the first symbol and assigning a second codeword to the second symbol representing a compressed form of the second symbol;

generating a first codeword-symbol assignment table for the first subset of symbols and a second codeword-symbol assignment table for the second subset of symbols; and

storing the codewords of the first subset as a first image representing a first compressed split instruction and the code words of the second subset as a second image representing a second compressed split instruction, the first and second compressed split instructions representing a compressed form of the computer program.

15. The method of claim 14, wherein the instruction is a 32-bit instruction.

16. A system for decompressing a computer program of executable instructions, the program having been compressed by splitting each instruction of a plurality of the instructions of the program into a first symbol and a second symbol, wherein each instruction of the plurality consists of one opcode and one or more operands, the first symbol comprising a first half of the instruction including at least part of the opcode and the second symbol comprising the second half of the instruction including at least part of the one or more operands, the first symbol assigned to first subset and the second symbol assigned to a second subset, assigning a first codeword to the first symbol representing a compressed form of the first symbol and assigning a second codeword to the second symbol representing a compressed form of the second symbol, generating a first codeword-symbol assignment table for the first subset of symbols and a second codeword-symbol assignment table for the second subset of symbols, storing the codewords of the first subset as a first image representing a first compressed split instruction and the code words of the second subset as a second image representing a second compressed split instruction, the first and second compressed split instructions representing a compressed form of the program, the system for decompressing, comprising:

accessing logic for accessing the first compressed split instruction;

look up logic coupled to the accessing logic, for reading a codeword in the first compressed split instruction and looking up a first symbol in the first codeword-symbol assignment table;

output logic coupled to the look up logic, for outputting the first symbol as a formed symbol of the first subset;

said accessing logic accessing the second compressed split instruction;

said look up logic reading a codeword in the second compressed split instruction and looking up a second symbol in the second codeword-symbol assignment table;

said output logic outputting the second symbol as a formed symbol of the second subset; and

merging logic coupled to the output logic, for merging the first symbol of the first subset with the second symbol of the second subset to form a decoded instruction.

17. The system of claim 16, wherein the instruction is a 32-bit instruction.