Compression algorithm with embedded meta-data for partial record operation augmented with expansion joints
First Claim
1. A method for compressing data, said method comprising the steps of:
- receiving uncompressed data;
placing a first meta-data marker in the compressed data, the first meta-data marker indicating the beginning of a data record;
compressing a portion of the uncompressed data into the compressed data using a compression engine;
inserting a second meta-data marker in the compressed data, the second meta-data marker indicating the beginning of a decompressible data block; and
inserting a third meta-data marker in the compressed data, the third meta-data marker indicating that a portion of the compressed data is to be ignored.
3 Assignments
0 Petitions
Accused Products
Abstract
A compression system stores meta-data in the compressed record to allow better access and manage merging data. Markers are added to the compression stream to indicate various things. Each compressed record has a marker to indicate the start of the compressed data. These markers have sector number as well as the relocation block numbers embedded in their data. A second marker is used to indicate free space. When compressed data is stored on the disk drive, free space is reserved so that future compression of the same, or modified, data has the ability to expand slightly without causing the data to be written to a different location. Also the compressed data can shrink and the remaining space can be filled in with this free space marker. A third type of marker is the format pattern marker. Compression algorithms generally compress the format pattern very tightly. However, the expectation is that the host will write useful data to the storage device. The compressor is fed typical data in the region of the format pattern, but a marker is set in front of this data to allow the format pattern to be returned rather than the typical data.
196 Citations
13 Claims
-
1. A method for compressing data, said method comprising the steps of:
-
receiving uncompressed data;
placing a first meta-data marker in the compressed data, the first meta-data marker indicating the beginning of a data record;
compressing a portion of the uncompressed data into the compressed data using a compression engine;
inserting a second meta-data marker in the compressed data, the second meta-data marker indicating the beginning of a decompressible data block; and
inserting a third meta-data marker in the compressed data, the third meta-data marker indicating that a portion of the compressed data is to be ignored. - View Dependent Claims (2, 3, 4, 5)
adding an expansion joint meta-data marker in the compressed data.
-
-
3. The method of claim 2 further comprising the steps of:
-
searching in the compressed data for the first meta-data marker;
decompressing the compressed data with a decompression engine;
if the second meta-data marker is found in the compressed data, then resting the decompression engine; and
if the expansion joint meta-data marker is found in the compressed date, then instructing the decompression engine to skip the expansion joint meta-data marker.
-
-
4. The method of claim 2 further comprising the step of:
merging additional data into the compressed data.
-
5. The method of claim 4 wherein the step of merging further comprising the steps of;
-
estimating a location of the additional data in the compressed data;
searching in the compressed data for the second meta-data marker;
merging the additional data with the compressed data;
if the merged data requires more space, then decreasing the expansion joint meta-data marker; and
if the merged data requires less space, then increasing the expansion joint meta-data marker.
-
-
6. A method for compressing data, said method comprising the steps of:
-
receiving uncompressed data;
placing a first meta-data marker in the compressed data, the first meta-data marker indicating the beginning of a data record;
compressing a portion of the uncompressed data into the compressed data using a compression engine;
inserting a second meta-data marker in the compressed data, the second meta-data marker indicating the beginning of a decompressible data block; and
adding an ignore meta-data marker whenever the compression engine outputs a code equal to the first meta-data marker or the second meta-data marker.
-
-
7. A method for compressing data, said method comprising the steps of:
-
receiving uncompressed data;
placing a first meta-data marker in the compressed data, the first meta-data marker indicating the beginning of a data record;
compressing the uncompressed data into the compressed data using a compression engine;
after a predefined amount of the uncompressed data is compressed, inserting a second meta-data marker in the compressed data, the second meta-data marker indicating the beginning of a decompressible data block;
after a predefined amount of the compressed data is created, adding a third meta-data marker in the compressed data, where the third meta-data marker identifies an expansion joint in the compressed data, and adding an ignore meta-data marker whenever the compression engine outputs a code equal to the first meta-data marker, the second meta-data marker or the third meta-data marker. - View Dependent Claims (8)
-
-
9. A storage system comprising:
-
a storage media; and
a controller connected to the storage media, the controller further comprising;
a compression engine;
a dictionary connected to the compression engine;
a meta-data insertion logic arranged to receive compressed data from the compression engine;
a command interpreter for controlling the compression engine and the meta-data insertion logic, the command interpreter instructing the meta-data insertion logic to insert a first meta-data marker in the compressed data, where the first meta-date marker indicates the beginning of a data record;
after a predefined amount of uncompressed data is compressed, the command interpreter instructs the meta-data insertion logic to insert a second meta-data marker in the compressed data, the second meta-data marker indicating the beginning of a decompressible data block;
after a predefined amount of the compressed data is created, the command interpreter instructs the meta-data insertion logic to insert a third meta-data marker, where the third meta-data marker identifies an expansion joint in the compressed data, the command interpreter resetting the dictionary when the first meta-data marker or the second meta-data marker is inserted.- View Dependent Claims (10)
a decompression engine connected to the dictionary;
a mete-data extraction logic connected to the decompression engine, for extracting meta-data from compressed data; and
the command interpreter resetting the dictionary when the meta-data extraction logic extracts the first meta-data marker or the second meta-data marker.
-
-
11. A method for decompressing data, said method comprising the steps of:
-
searching the compressed data for a first meta-data marker, the first meta-data marker indicating the beginning of a data record;
decompressing the compressed data with a decompression engine;
if a second meta-data marker is found in the compressed date, then resting the decompression engine; and
if a third meta-data marker is found in the compressed data, then instructing the decompression engine to skip the third meta-data marker. - View Dependent Claims (12, 13)
estimating B location of the first meta-data marker in the compressed data.
-
-
13. The method of claim 11 further comprising the step of:
if a fourth meta-data marker is found in the compressed data, then instructing the decompression engine to decompress a next code of the compressed data.
Specification