LOSSLESS DATA COMPRESSION AND REAL-TIME DECOMPRESSION

• US 20100223237A1
• Filed: 11/05/2008
• Published: 09/02/2010
• Est. Priority Date: 11/05/2007
• Status: Abandoned Application

• Current Assignee: University of Florida Research Foundation, Incorporated (State University System of Florida)
• Original Assignee: University of Florida Research Foundation, Incorporated (State University System of Florida)
• Inventors: Basu, Kanad, Wang, Weixun, Mishra, Prabhat, Qin, Xiaoke, Seong, Seok-Won, Murthy, Chetan
• Application Number:
  US12/682,808
• Publication Number:
  US 20100223237A1
• Time in Patent Office: Days
• US Class Current: 707/693
• CPC Class Codes: G06F 9/30156 Special purpose encoding of instructions, e.g. Gray coding
• CPC Class Codes: G06F 9/30174 for non-native instruction set, e.g. Javabyte, legacy code
• CPC Class Codes: G06F 9/30178 of compressed or encrypted instructions
• CPC Class Codes: G06F 9/3822 Parallel decoding, e.g. parallel decode units
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method

Abstract

A method, information processing system, and computer program storage product store data in an information processing system. Uncompressed data is received and the uncompressed data is divided into a series of vectors. A sequence of profitable bitmask patterns is identified for the vectors that maximizes compression efficiency while minimizes decompression penalty. Matching patterns are created using multiple bit masks based on a set of maximum values of the frequency distribution of the vectors. A dictionary is built based upon the set of maximum values in the frequency distribution and a bit mask savings which is a number of bits reduced using each of the multiple bit masks. Each of the vectors is compressed using the dictionary and the matching patterns with having high bit mask savings. The compressed vectors are stored into memory. Also, an efficient placement is developed to enable parallel decompression of the compressed codes.

Claims

1. A method for storing data in an information processing system, the method comprising:

receiving uncompressed data;

dividing the uncompressed data into a series of vectors;

identifying a sequence of profitable bitmask patterns for the vectors that maximizes compression efficiency while minimizes decompression penalty;

creating matching patterns using a plurality of bit masks based on a set of maximum values of a frequency distribution of the vectors;

building a dictionary based upon the set of maximum values in the frequency distribution and a bit mask savings which is a number of bits reduced using each of the plurality of bit masks;

compressing each of the vectors using the dictionary and the matching patterns with having high bit mask savings;

storing the vectors which have been compressed into memory.

2. The method of claim 1, wherein the uncompressed data comprises of instructions including opcodes, operands and immediate values in an information processing system.

3. The method of claim 1, wherein the uncompressed data comprises of data (such as integer value, floating-point value etc.) in an information processing system.

4. The method of claim 1, wherein the series of vectors are n-bit long vectors having equal length, where n is a counting number.

5. The method of claim 1, wherein the uncompressed data represents seismic data.

6. The method of claim 1, wherein the uncompressed data represents electronic test patterns used by test equipment.

7. The method of claim 1, wherein building a dictionary further comprises:

creating a graph comprising a set of nodes corresponding to each vector in the series of vectors, wherein the graph comprises a set of edges, wherein an edge is created between two nodes if the nodes can be matched using at least one bit-mask pattern.

8. The method of claim 7, further comprising:

allocating bit savings to at least one of each node in the set of nodes and each edge in the set of edges; and

determining an overall savings for each node based on the bit savings allocated to the at least one of each node in the set of nodes and each edge in the set of edges.

9. The method of claim 8, further comprising:

selecting at least one node with a maximum savings associated therewith; and

adding the at least one node that has been selected to the dictionary.

10. The method of claim 9, further comprising:

deleting the at least one node that has been selected from the graph.

11. The method of claim 9, further comprising:

setting a node deletion threshold; and

deleting at least one node connected to the at least one node that has been selected if a frequency value associated with the at least one node is less than the given threshold.

12. The method of claim 1, wherein the frequency distribution is determined by:

identifying repeating 32-bit sequences; and

determining a total number of repetitions for the repeating 32-bit sequences that have been determined.

13. The method of claim 1, further comprising:

adjusting branch targets by patching branch targets into new offsets in the vectors that have been compressed.

14. The method of claim 13, further comprising:

padding extra bits at an end portion of code preceding the branch targets to align on a byte boundary.

15. The method of claim 13, further comprising:

storing a minimal mapping table comprising new address for addresses that have failed to be patched.

16. An information processing system for storing data, the information processing system comprising:

a memory;

a processor;

a code compression engine adapted to;

receive uncompressed data;

divide the uncompressed data into a series of vectors;

identify a sequence of profitable bitmask patterns for the vectors that maximizes compression efficiency while minimizes decompression penalty;

create matching patterns using a plurality of bit masks based on a set of maximum values of a frequency distribution of the vectors; and

a dictionary selection engine adapted to;

build a dictionary based upon the set of maximum values in the frequency distribution and a bit mask savings which is a number of bits reduced using each of the plurality of bit masks;

wherein the code compression engine is further adapted to;

compress each of the vectors using the dictionary and the matching patterns with having high bit mask savings;

store the vectors which have been compressed into memory.

17. The information processing system of claim 16, wherein the dictionary selection engine is further adapted to build a dictionary by:

creating a graph comprising a set of nodes corresponding to each vector in the series of vectors, wherein the graph comprises a set of edges, wherein an edge is created between two nodes if the nodes can be matched using at least one bit-mask pattern.

18. The information processing system of claim 17, wherein the dictionary selection engine is further adapted to build a dictionary by:

allocating bit savings to at least one of each node in the set of nodes and each edge in the set of edges; and

determining an overall savings for each node based on the bit savings allocated to the at least one of each node in the set of nodes and each edge in the set of edges.

19. The information processing system of claim 18, wherein the dictionary selection engine is further adapted to build a dictionary by:

selecting at least one node with a maximum savings associated therewith; and

adding the at least one node that has been selected to the dictionary.

20. A method for decompressing compressed data, the method comprising:

receiving a set of bitmask-based compressed data;

generating an instruction-length mask based on the compressed data;

retrieving at least one dictionary entry corresponding to the compressed data, wherein

generating the instruction-length mask is performed substantially parallel to retrieving the at least one dictionary entry; and

performing a logical XOR operating on the instruction-length mask and a dictionary entry corresponding to the compressed data.