Method of compressing data and device for performing the same

• US 9,280,287 B2
• Filed: 12/20/2013
• Issued: 03/08/2016
• Est. Priority Date: 01/02/2013
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Kong, Jun Jin, Seo, Man Keun, Kim, Dae Wook, Son, Hong Rak
• Primary Examiner(s): Sun, Michael
• Application Number:
  US14/135,628
• Publication Number:
  US 20140189279A1
• Time in Patent Office: 809 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: H03M 7/6082 Selection strategies

Abstract

A data compression method includes receiving an input data stream including a previous data block and a current data block, and executing a first comparison of a part of the previous data block with part of a previous reference data block, and a second comparison of the current data block with a current reference data block, where the first and second comparisons are executed in parallel. The method further includes selectively, based on results of the first and second comparisons, outputting the current data block or compressing an extended data block, where the extended data block includes the part of the previous data block and the current data block.

Claims

1. A data compression method comprising:

receiving an input data stream including a previous data block and a current data block;

adjusting each delay of the current data block using a corresponding one of delay circuits and generating a first delayed data block and a second delayed data block;

executing a first comparison of only a part of the previous data block with only a part of a previous reference data block, and a second comparison of all of the first delayed data block with all of a current reference data block, wherein the first and second comparisons are executed in parallel; and

selectively, based on results of the first and second comparisons, outputting the second delayed data block or compressing an extended data block, wherein the extended data block includes the part of the previous data block and the second delayed data block,

wherein a size of the current data block is greater than a size of the part of the previous data block, and

wherein a size of the current reference data block is greater than a size of the part of the previous reference data block.

2. The data compression method of claim 1, wherein a first memory region, in which the current reference data block is stored, and a second memory region, in which the previous reference data block is stored, are respectively implemented in different memories which are allocated using an interleaving method and are independently accessible.

3. The data compression method of claim 1, wherein a ratio of a size of the extended data block to a size of the current data block is a mixed decimal.

4. The data compression method of claim 1, further comprising reading in parallel the part of the previous reference data block and the current reference data block from a buffer memory.

5. A data compression method comprising:

receiving an input data stream including a previous data block and a current data block;

adjusting each delay of the current data block using a corresponding one of delay circuits and generating a first delayed data block and a second delayed data block;

reading only a part of a previous reference data block from a memory, and in parallel reading a current reference data block from the memory;

comparing only a part of the previous data block with only the part of the previous reference data block, and in parallel comparing the first delayed data block with the current reference data block;

compressing an extended data block when the part of the previous data block matches the part of the previous reference data block, and the first delayed data block matches the current reference data block, wherein the extended data block includes the part of the previous data block and the second delayed data block,

wherein a size of the current data block is greater than a size of the part of the previous data block, and

wherein a size of the current reference data block is greater than a size of the part of the previous reference data block.

6. The data compression method of claim 5, further comprising selectively compressing or not compressing the current data block when at least one of the part of the previous data block does not match the part of the previous reference data block, and the current data block does not match the current reference data block.

7. The data compression method of claim 5, wherein the memory is a buffer memory including a first memory region in which the current reference data block is stored, and a second memory region in which the previous reference data block is stored, and the first and second regions are respectively implemented in different memories which are allocated using an interleaving method and are independently accessible.

8. The data compression method of claim 5, wherein a ratio of a size of the extended data block to a size of the current data block is a mixed decimal.

9. A data compression circuit comprising:

a buffer memory including a first memory region, a second memory region, and a third memory region;

a buffer memory controller configured to output only a part of a previous reference data block stored in the first memory region and a current reference data block stored in the second memory region in response to an address output from a hash key generation circuit;

an input data register configured to receive an input data stream, adjust each delay of a current data block included in the input data stream using a corresponding one of delay circuits and generate a first delayed data block and a second delayed data block;

a comparison circuit configured to determine whether only a part of a previous data block matches only the part of the previous reference data block and whether the first delayed data block matches the current reference data block, and to generate control information according to a determination result; and

a compressed-data generation circuit configured to selectively output, based on the control information, the second delayed data block or compressed data, wherein the compressed data is generated by compressing an extended data block which includes only the part of the previous data block and the second delayed data block,

wherein a size of the current data block is greater than a size of the part of the previous data block, and

wherein a size of the current reference data block is greater than a size of the part of the previous reference data block.

10. The data compression circuit of claim 9, wherein the first memory region, the second memory region, and the third memory region are respectively implemented in different memories, which are allocated using an interleaving method and are independently accessible.

11. The data compression circuit of claim 9, wherein the buffer memory controller reads in parallel the part of the previous reference data block from the first memory region and the current reference data block from the second memory region, and then writes the current data block to the third memory region.

12. The data compression circuit of claim 9, wherein the buffer memory controller comprises:

an address generator configured to generate a first address of the first memory region and a second address of the second memory region using the address; and

a buffer memory access control circuit configured to read in parallel the part of the previous reference data block from the first memory region using the first address and the current reference data block from the second memory region using the second address, and to write the current data block to the third memory region based on a third address of the current data block.

13. The data compression circuit of claim 9, wherein the comparison circuit determines in parallel whether the part of the previous data block matches the part of the previous reference data block and whether the current data block matches the current reference data block.

14. The data compression circuit of claim 9, wherein the comparison circuit comprises:

a register configured to store the part of the previous data block;

a first comparator configured to determine whether the part of the previous data block, which is output from the register, matches the part of the previous reference data block, which is output from the buffer memory controller;

a second comparator configured to determine whether the current data block matches the current reference data block;

a length calculation circuit configured to output match information indicating matching or mismatching and length information indicating a length of matching data based on an output signal of the first comparator and an output signal of the second comparator; and

a distance calculation circuit configured to output distance information based on an address of the part of the previous data block and an address of the current data block,

wherein the control information includes the match information, the length information, and the distance information.

15. The data compression circuit of claim 14, wherein the compressed-data generation circuit comprises:

a selection signal generation circuit configured to generate a selection signal based on the match information;

a code generation circuit configured to generate the compressed data based on the length information and the distance information; and

a selection circuit configured to output the current data block or the compressed data in response to the selection signal.

16. A data processing system comprising:

a data storage device;

a host configured to output a data stream including a previous data block and a current data block; and

a memory controller comprising an input data register configured to receive the current data block, adjust each delay of the current data block using a corresponding one of delay circuits and generate a first delayed data block and a second delayed data block,

wherein the memory controller is configured to determine a matching property of each data block or each extended data block in the data stream from the host, to compress the second delayed data block or the extended data block in the data stream according to a determination result, and to output compressed data to the data storage device, and

wherein the memory controller determines the matching property of the previous data block, and then determines a matching property of the extended data block which includes a part of the previous data block and the second delayed data block,

the memory controller further comprising a comparison circuit configured to determine in parallel whether the part of the previous data block matches a part of a previous reference data block and whether the first delayed data block matches a current reference data block,

wherein a size of the current data block is greater than a size of the part of the previous data block, and

wherein a size of the current reference data block is greater than a size of the part of the previous reference data block.

17. The data processing system of claim 16, wherein the memory controller further comprises:

a buffer memory including a first memory region, a second memory region, and a third memory region;

a buffer memory controller configure to output in parallel the part of the previous reference data block stored in the first memory region and the current reference data block stored in the second memory region in response to an address,

wherein the comparison circuit is further configured to generate control information according to a determination result; and

a compressed-data generation circuit configured to selectively output, based on the control information, the current data block or the compressed data, wherein the compressed data is generated by compressing the extended data block.

18. The data processing system of claim 17, wherein the first memory region, the second memory region, and the third memory region are respectively implemented in different memories respectively having different addresses allocated using an interleaving method.

19. The data processing system of claim 17, wherein the buffer memory controller comprises:

an address generator configured to generate a first address of the first memory region and a second address of the second memory region using the address; and

a buffer memory access control circuit configured to read in parallel the part of the previous reference data block from the first memory region using the first address and the current reference data block from the second memory region using the second address, and to write the current data block to the third memory region based on a third address of the current data block.

20. The data processing system of claim 17, wherein the comparison circuit comprises:

a register configured to store the part of the previous data block;

a first comparator configured to determine whether the part of the previous data block, which is output from the register, matches the part of the previous reference data block, which is output from the buffer memory controller;

a second comparator configured to determine whether the current data block matches the current reference data block;

a length calculation circuit configured to output match information indicating matching or mismatching and length information indicating a length of matching data based on an output signal of the first comparator and an output signal of the second comparator; and

a distance calculation circuit configured to output distance information based on an address of the part of the previous data block and an address of the current data block,

wherein the control information includes the match information, the length information, and the distance information.

21. The data processing system of claim 20, wherein the compressed-data generation circuit comprises:

a selection signal generation circuit configured to generate a selection signal based on the match information;

a code generation circuit configured to generate the compressed data based on the length information and the distance information; and

a selection circuit configured to output the current data block or the compressed data in response to the selection signal.

22. The data processing system of claim 16, wherein a ratio of a size of the extended data block to a size of the current data block is not an integer.

23. The data processing system of claim 16, wherein the data storage device is a flash memory, an embedded multimedia card (eMMC), a universal flash storage (UFS), a universal serial bus (USB) flash drive, or a solid state drive (SSD).

24. The data processing system of claim 16, wherein the data storage device is a hard disk drive.

25. The data processing system of claim 16, wherein the data processing system is a smart phone, a tablet personal computer, mobile internet device, or an e-book.