TWI505091B - Adaptive compression data storing method for non-volatile memories and system using the same - Google Patents

Description

Adaptive compressed data storage method for non-volatile memory And a system using the method

The present invention relates to an adaptive compressed data storage method and a system using the same. In particular, it relates to an adaptive compressed data storage method for non-volatile memory, such as flash memory, and a system using the same.

Non-volatile memory, such as NAND flash memory solid-state drives, has recently become an attractive solution for consumer electronics and desktop systems due to the shrinking size of NAND-type memory cells combined with multi-layered storage technology. . However, as the density of flash memory storage units increases, their performance and reliability may deteriorate significantly. For example, a single-layer storage flash memory fabricated in a 34nm process allows 100,000 program/erase cycles per block, while a multi-layer memory flash memory that is also fabricated in a 34nm process supports only 5,000 blocks per block. Programming/erasing cycle. The performance of multi-layer storage flash memory is also several times slower than that of single-layer storage flash memory. However, as the semiconductor process shrinks further, these problems are expected to become more serious. One way to get rid of these problems is to use hardware to speed up compression.

Because the life of a solid-state hard disk using flash memory is strongly dependent on the amount of data written to the solid-state hard disk, reducing the amount of data written to the actual amount of data on the solid-state hard disk can be an effective way to improve the life of the solid-state hard disk. solution. In addition, if the compression operation can be operated with a hardware acceleration unit, this can improve the performance of the solid state hard disk because a small amount of data entities are transferred to the uncompressed read and write during the I/O operation. The idea of using data compression for data storage is not new, but has been extensively studied. For example, many existing file systems support software-based data compression to expand the effective capacity of storage devices. While software-based compression can effectively improve the life of solid state drives, they incur significant compression/decompression overhead costs. Therefore, the performance of the overall solid state hard disk is significantly deteriorated. Therefore, software-based data compression is often used when storage is one of the most important goals of the design.

Data compression refers to reducing the space required to store data or reducing the time required to send data. The size of the data is reduced by removing excess information. The purpose of data compression is to express the source of information in digital form. The fewer the number of bits, the better, and the minimum requirements for reconstructing the original information. Data compression can be lossless only if it is feasible to accurately reconstruct the original data from the compressed version. This lossless technique is used when the source material is so important that people cannot lose any detail. Examples of such source materials are medical images, texts and images saved for legal reasons, and some computers. Execute files, etc. Because these algorithms irreversibly delete portions of the data, another family of compression algorithms is called "loss", and only the approximation of the original data can be reconstructed. Approximate reconstruction may be desirable because it can lead to more efficient compression. However, this usually requires a good balance between visual quality and computational complexity. Because of the operation of the human visual and auditory systems, materials such as multimedia images, video and audio can be easily compressed by lossy compression techniques. Loss algorithm achieves more compression performance than lossless algorithm. But lossy compression is limited to audio, images, and video, and some of the losses are acceptable. It is meaningless to talk about the advantages and disadvantages of "no loss" or "lossy" compression technology, because each has its use surface, lossless compression technology may be longer than some cases, and loss Compression technology is superior to other situations.

Some of today's lossless compression techniques are mostly based on dictionary or probability and entropy. In other words, they all attempt to achieve compression using the same characters/strings that appear in the material. Based on dictionary-based compression techniques, the Lempel-Ziv scheme is divided into two families: the scheme derived from LZ77 (LZ77, LZSS, LZH and LZB) and the scheme derived from LZ78 (LZ78, LZW and LZFG).

A good example of compression techniques on hardware implementation, presented by Sungjin Lee et al. in a paper titled "Using Hardware Accelerated Compression to Improve the Performance and Longevity of Solid State Drives," the paper was published in November 2011. The Institute of Electrical and Electronics Engineers, Consumer Electronics, Vol. 57, No. 4. Please see Figure 1, one The solid state hard disk architecture 1 includes a direct memory access controller 10, a plurality of flash memory bus controllers 20, and a compression/decompression module 30. The direct memory access controller 20 receives commands from a host (not shown) and transmits data to and from a dynamic random access memory within the host. Each flash memory bus controller 20 performs a number of flash memory operations, including read, write and erase operations, and moves data into and out of the flash memory chip.

The compression/decompression module 30 is implemented between the direct memory access controller 10 and the flash memory bus controller 20. The primary function of the compression/decompression module 30 is to perform compression or decompression of data transmitted from the direct memory access controller 10 or the flash memory bus controller 20 individually. The compression/decompression module 30 uses the LZRW3 algorithm and belongs to the evolution of the LZ77. It has four hardware sub-modules: a shift register 21, a dictionary table 22, a compression logic circuit 23, and a compression buffer 24. The shift register 21 is temporarily stored for compressing the material to be tested, and the dictionary table 22 contains the repeat pattern previously seen. The compression logic circuit 23 refers to the dictionary table 22, and converts the data in the shift register 21 into symbols. The compressed data, a series of symbols, is stored in compression buffer 24 and eventually moved into a flash memory chip.

The compression/decompression module 30 takes the data from a direct memory access buffer 11 in the direct memory access controller 10 until the shift register 21 is completely filled, and the direct memory access buffer 11 Keep all the data sent from the host. The compression logic circuit 23 uses the first 3 bytes of the data in the shift register 21 to create a hash value which is used as the dictionary table 22. Dictionary index. The compression logic circuit 23 then checks the data entry indicated by the dictionary index. If the first 3 bytes of the corresponding material registration are equivalent to those in the shift register 21, it is assumed that a matching pattern is found in the dictionary table 22. When the compression logic circuit 23 finds a matching data registration, it compares the remaining byte groups in the shift register 21 with the byte groups in the data registration, and finds the data between the shift register 21 and the data login. The public part. This public part is called a piece of data. The compression logic circuit 23 creates a symbol by combining the dictionary index with the length of the data segment and a compression flag having a value of "1". The compression flag indicates whether the symbol represents compressed data or uncompressed data. The created symbol is then written to the compression buffer 24. Finally, the entire data segment is discarded by the shift register 21, and the new data is transferred from the direct memory access buffer 11 to the shift register 21.

If a matching pattern is not found from the dictionary table 22, a symbol is created only for the first byte of the material. A 9-bit symbol is created by adding a 1-bit compression flag (which is a value of 0) to the first byte of the shift register 21. After the created symbol is written into the compression buffer 24, a new byte from the direct memory access buffer 11 is attached to the tail of the shift register 21, discarding the shift register 21. The first tuple. It should be noted that when a matching pattern does not exist in the dictionary table 22, the old pattern in the data entry indicated by the hash value is replaced by the new pattern in the shift register 21 to support the newly discovered pattern.

The data written to the solid state drive by the solid state hard disk architecture 1 is described in FIG. Figure 2 shows consecutive pages in a solid state drive. These are slashed The page indicates that the storage unit in all pages has been written with the stored data. For those pages that are partially filled with slashes, the blanks contain no data and are technically filled with "0". The ratio of the slash area to the blank area is the ratio of the data portion to the data portion not included in the storage unit of the page. Not all materials can be compressed due to their characteristics. Figure 2 is an example for illustration. From Fig. 2, it is apparent that the physical page addresses P11 to P14 store an uncompressed material. The physical page addresses P15 and P16 store a compressed data. The physical page addresses P17 and P18 store another compressed material. In fact, the blanks in the page are not only a waste of storage space, but also a reason to reduce the life of the solid state hard disk. All of the compression algorithms and the modules that apply the compression algorithm have similar disadvantages as the previous case. Therefore, there is a need for a method that can utilize a page blank area and a system to which the method is applied.

This paragraph of text extracts and compiles certain features of the present invention. Other features will be revealed in subsequent paragraphs. The intention is to cover various modifications and similar arrangements in the spirit and scope of the appended claims.

The present invention provides a solution to the problem that compressed data storage space cannot be utilized. Further, the service life of non-volatile memory can be extended.

In accordance with an aspect of the present invention, an adaptive compressed data storage method for non-volatile memory is disclosed. The method comprises the steps of: A. receiving a first data, wherein the size of the first data is not greater than a size of a page in a non-volatile memory, and the continuously received first data forms a raw material, the original data Need to be stored in the non-volatile memory; B. If The size of the first data is greater than a predetermined size, and the first data is divided into at least two basic units, wherein at least one basic unit is equal to the predetermined size; C. compressing the basic unit or the first data; D. connecting and padding the compression The basic unit or the first data to form a second data, so that the second data has a size that is an integer multiple of the predetermined size; E. stores the second data in a buffer; F. if the second data The number is 1 and the original data is not completely received. Steps A through E are repeated; G. searching for at least two second data, the second data being combined to have the size of one page in the buffer; H. Combining the at least two second data in the buffer as a third data, or if the original data has been completely received, padding the second data or the second data that is connected and padded in the buffer is a third data, wherein the third data has the same size as a page; I. programming the third data to a specific page in the non-volatile memory; and J. if the original data is not completely received, performing steps A. 0 is used as an element of pad filling.

According to the concept of the present invention, the adaptive compressed data storage method further includes a step I1 after the step I: I1. updating a mapping table, where the mapping table stores a physical page address of the specific page and one of the original materials. The mapping of logical addresses. The adaptive compressed data storage method further includes a step H1 between the step H and the step I: H1. If the buffer is full or substantially full, and no combination of the second data has the same page size, the pad is filled. The second data having the largest of all the second data in the buffer is the third data, and the third data is programmed to a specific page of the non-volatile memory, wherein 0 is used as an element of the pad charge. Or further comprising a step H2 in the step H and the step I: H2. If the buffer is full or substantially full, and no combination of the second data has the same page size, the second data with the longest temporary storage time in all the second data in the buffer is The third data is programmed to the third page of the non-volatile memory, wherein 0 is used as the element of the pad charge.

In accordance with the present invention, a lossless compression algorithm is used in step C to compress the first data or the base unit. The lossless compression algorithm is LZ77, LZSS, LZH, LZB, LZ78, LZW or LZFG. The non-volatile memory is a NAND flash memory or a solid state hard disk. A basic unit is compressed to form a compressed basic unit, or at least two basic units are compressed to form a compressed basic unit.

According to another aspect of the present invention, an adaptive compressed data storage system for non-volatile memory includes: a host interface unit for communicating with a host and receiving first data from the host, The size of the first data is not larger than the size of one page of the non-volatile memory, wherein the first data continuously received forms an original data, and the original data needs to be stored in the non-volatile memory; a data compressor, electricity Connecting to the host interface unit, if the size of the first data is greater than a predetermined size, dividing each first data into at least two basic units and compressing the basic unit, wherein at least one basic unit is equal to the predetermined size; a charging unit electrically connected to the data compressor for connecting and padding the compressed basic unit to form a second data, and if the original data has been completely received, the pad is filled with the second data or connected and padded The second data is a third data; a buffer is electrically connected to the pad The charging unit and the non-volatile memory are configured to temporarily store the second data, replace a stored second data when it is full or substantially full, and program the third data into one of the non-volatile memories a specific page; and a combining unit electrically connected to the buffer for combining at least two second data in the buffer as a third data. If the original data size is not greater than the predetermined size, the first data will not be split but compressed and padded to the size of one page and programmed into the non-volatile memory. The second material has a size that is an integer multiple of the predetermined size. The size of the third material is the same as one page. 0 is used as an element of pad filling.

According to the concept of the present invention, the adaptive compressed data storage system further includes a mapping table unit electrically connected to the buffer for storing and updating a mapping table having a physical page address of the specific page and the original A mapping link of a logical address of the data. If the buffer is full or substantially full, and no combination of the second data has the same page size, the pad charging unit further pads a second data into the third data, and the padded second data is The largest of all the second data in the buffer. If the buffer is full or substantially full, and no combination of the second data has the same page size, the pad charging unit further pads a second data into the third data, and the padded second data is The second time of all the second data in the buffer is the longest.

1‧‧‧ Solid State Drive Architecture

10‧‧‧Direct Memory Access Controller

11‧‧‧Direct memory access buffer

20‧‧‧Flash memory bus controller

21‧‧‧Shift register

22‧‧‧ dictionary table

23‧‧‧Compressed logic circuit

24‧‧‧Compressed buffer

30‧‧‧Compression/Decompression Module

100‧‧‧Adaptive Compressed Data Storage System

101‧‧‧Host interface unit

102‧‧‧Data Compressor

103‧‧‧ pads unit

104‧‧‧buffer

105‧‧‧ combination unit

106‧‧‧ mapping table unit

110‧‧‧Non-volatile memory

200‧‧‧Host

Figure 1 is a block diagram of a solid state drive architecture.

Figure 2 shows consecutive pages in the solid state drive.

Figure 3 is a block diagram of an embodiment of an adaptive compressed data storage system in accordance with the present invention.

Figure 4 illustrates the storage of data in an adaptive compressed data storage system of an embodiment.

FIG. 5 is a flow chart of an embodiment of an adaptive compressed data storage method according to the embodiment.

Figure 6 illustrates the storage of data in an adaptive compressed data storage system of another embodiment.

The invention will be more specifically described by reference to the following examples.

Referring to Figure 3, there is illustrated an adaptive compressed data storage system 100 for non-volatile memory in accordance with the present invention. Non-volatile memory, such as NAND flash memory, including single-layer storage flash memory, multi-layer storage flash memory, and three-layer storage flash memory, are suitable for use in the present invention. In addition, modular non-volatile memory such as solid state drives, memory cards and flash drives can also be used. However, non-volatile memory (or modules) must be programmed in "pages". Non-volatile memory that can be accessed randomly, such as electrically erasable programmable read-only memory, is not suitable. For convenience of explanation, a non-volatile memory 110 used in the embodiment is a NAND flash memory chip. There are many different types of NAND flash memory chips on the market that can be used regardless of their memory capacity and page size. Here, the present invention focuses on the interaction between pages in the non-volatile memory 110. As is known, a common page size ranges from 512B to 4KB (only the data area is calculated, and the memory capacity in the spare area is not included). For a better understanding of the invention, the page size is 2 KB.

The adaptive compressed data storage system 100 includes a plurality of parts: a host interface unit 101, a data compressor 102, a pad charging unit 103, a buffer 104, a combining unit 105, and a mapping table unit 106. The host interface unit 101 can communicate with a host 200 and receive first data from the host 200. The host computer 200 is a central processing unit of a personal computer. It writes data into the non-volatile memory 110 and reads the data stored therein. In practice, the host 200 can also be a standalone electronic device that requests data storage, such as a notebook computer. The host interface unit 101 can be designed to have an interface suitable for the host 200. In this embodiment, the interface can conform to an internal integrated circuit (I2C) specification. The size of each of the first data from the host 200 is not greater than the size of one page (2 KB) in the non-volatile memory 110. The first data received continuously forms a raw material that needs to be stored in the non-volatile memory. The original data, such as an image file, may not be an integer multiple of 2KB. Short source data may have a data length of 500B, and storage needs to occupy one page of capacity. Large original data may have a data length of more than 10 MB, and after being divided into several pages, the last piece of data is shorter than 2 KB. The two kinds of original assets mentioned above The materials are all suitable for the adaptive compressed data storage system 100. In the present embodiment, an original material having 6 KB (the size of 3 pages) is used for explanation. Other sources of material having different data lengths will be described in other embodiments. In this case, the first data with 3 original materials is received, as shown in Figure 4. The size of each first material is 2KB. The first data of the original data can be obtained after the original data is received and divided, and the first data is followed by the other until the original data is received. This manner is also possible, depending on the design of the host interface unit 101, and is not The invention is limited. This embodiment applies the latter.

The data compressor 102 is electrically connected to the host interface unit 101. It divides each first data into 4 basic units. Each basic unit has the same size. As shown in FIG. 4, the first data received first has basic units D1-1, D1-2, D1-3, and D1-4. The first received data has basic units D2-1, D2-2, D2-3 and D2-4. The last received first data has basic units D3-1, D3-2, D3-3 and D3-4. It is obvious that all the basic units are 512B. 512B is set to a predetermined size. The predetermined size is variable based on the different page sizes and the number of basic units in a page. According to the present invention, the number of basic units in the first material is not limited to four, and it may be smaller than 4 or smaller than 4, but if the size of the first material is larger than the predetermined size, at least two are required. In this way, at least one basic unit can be equal to the predetermined size. However, this embodiment describes an ideal situation. If the length of the original data or the last part of the original data (the last data of the last data is counted) is less than one page, only one basic unit in the first data will be no larger than the predetermined size and the other basic units are the same. At the predetermined size. The data compressor 102 can compress the base unit. There are many algorithms for data compression that can be used. According to the present concept, the lossless compression algorithm is preferably used to compress the basic unit. The LZ77 algorithm is used in this embodiment. In practice, a lossless compression algorithm such as LZSS, LZH, LZB, LZ78, LZW or LZFG can also be used.

The results of the compression are described below. D1-1 and D1-2 are incompressible. The compressed basic units C1-1 and C1-2 are the same as D1-1 and D1-2. The base units D1-3 and D1-4 have a high compression ratio, and thus they are compressed into another compressed base unit C1-3. D2-1 to D2-4 are highly compressible, the basic unit corresponding to the compression of the basic units D2-1 and D2-2 is C2-1, and the basic unit corresponding to the compression of the basic units D2-3 and D2-4 is C2-2. Similarly, D3-1 to D3-4 are also highly compressible, and the basic unit corresponding to the compression of the basic units D3-1 and D3-2 is C3-1, corresponding to the compression of the basic units D3-3 and D3-4. The basic unit is C3-2.

The pad charging unit 103 is electrically connected to the data compressor 102. It can connect and pad the compressed basic unit to form a second material. The second material has a size that is an integer multiple of a predetermined size, for example, 1 KB or 1.5 KB. In the extreme case, the compression ratio is zero. The size of the second material can be the same as the size of one page. Please refer to FIG. 4 again, the compressed basic units C1-1, C1-2 are connected to C1-3 and filled (or attached) with a pad P1 pad. The compressed basic unit C2-1 is connected to C2-2 and charged with a pad P2 pad, and the compressed basic unit C3-1 is connected to C3-2 and charged with a pad P3 pad. 0 is used as an element of pad filling. This means pad charging P1, P2 Both P3 and P3 are composed of 0. In the extreme case described above, the pad charging step is still performed, but no "0" is attached to the base unit for connection and compression. The compressed basic unit is identical to the corresponding received first data. This is called the first pad charge, as shown in Figure 4.

The pad charging unit 103 can pad the second data, and if the original data has been completely received, the second data is connected and padded as a third data. The second data is stored in the buffer 104. As shown in Fig. 4, the second data includes C1-1, C1-2, C1-3, and P1 (hereinafter referred to as the second data 1) and further fills P1-2 with a pad (P1-2 is "0" "). This is called the second pad charge, as shown in Figure 4. The third material has the same page size and can be programmed into a particular page (B23P03) in the non-volatile memory 110. This is the final stage of storing the original material. Since no second material can be combined (detailed later), the second data remaining in the buffer 104 will be padded (or connected and padded) and programmed into one page at a time. If the buffer 104 has more than one second material, they can be connected, padded, and programmed as long as their overall size is less than one page size.

The buffer 104 is electrically connected to the pad charging unit 103 and the non-volatile memory 110, which can temporarily store the second material. If the buffer 104 is full or substantially full, it can replace a stored second data with a new second data. However, this work requires the assistance of the pad charging unit 103. When the buffer 104 is full or substantially full (for example, the remaining space is not full of a predetermined size) and there is no combination of the second data having a page size page, the pad charging unit 103 pads a second data into a third data, The second data that is padded is the buffer 104 all second The largest information. The second material (third material) that is padded will be programmed into the non-volatile memory 110. At this point, another second data will be stored in the buffer 104. For example, if the buffer 104 is set to 4 KB (2 pages size), the second data 1 is still combined with the second data composed of C2-1, C2-2, and P2 (hereinafter referred to as second data 2). Without the size of one page, the larger second data 1 will be replaced by the second data consisting of C3-1, C3-2 and P3 (hereinafter referred to as second data 3). Thus, the second material 2 and the second material 3 can be combined to reach the size page of one page. In this regard, at least two second data are retained in the buffer 104. The new second material may have a different size than the second data compiled, and at least the combination of the second data (which will be detailed later) can continue. The second data that is replaced can also be the longest temporary storage time of all the second data of the buffer 104. Both of the above methods can solve the problem that the buffer is full.

The size of the buffer 104 may be an integer multiple of a predetermined size, which should be four times larger than the predetermined size. The size of the buffer 104 is not limited to the present invention, but is preferably eight times larger than the predetermined size to avoid receiving two first data but the buffer 104 is full. Buffer 104 can include a dynamic random access memory or static random access memory, in addition to some logic circuitry for control. Dynamic random access memory or static random access memory is often used in buffers. Further, the buffer 104 can program the third data into a particular page of the non-volatile memory 110. When the third material is programmed into the non-volatile memory 110, a portion of the original data is stored.

The combining unit 105 is electrically connected to the buffer 104 for combining at least two second materials in the buffer 104 as a third data. Please see figure 4. When processing the second data charged by the pad P2 pad and the second material charged by the pad charging pad, the combining unit 105 finds that the two second materials in the buffer 104 have a size of one page (four times predetermined size) The two second data are combined into a third data and then programmed into the non-volatile memory 110. This combination may be four second materials having a predetermined size, which may also be two second materials, one being three times the predetermined size and the other being just exactly one predetermined size. Of course, if a page contains more than 4 basic units, the combined pattern will change.

It should be noted that if the size of the first material is not greater than the predetermined size and no other second data remains in the buffer 104, the received first data will not be split, but can be compressed and padded to one page. Size and programming into non-volatile memory 110. This condition only occurs when the original data is shorter than the predetermined size or the last first data of the original data is received and the second data is not in the buffer 104.

The mapping table unit 106 is electrically coupled to the buffer 104, which stores and updates a mapping table having a mapping of a physical page address of a particular page to a logical address of the original material. Please refer to Figure 4. If the logical address of the image file (original data) to be stored is at the URL:e:\data\image.jpg, the corresponding physical page address will be B23P03 (block 23, page 3) and B23P02 (block 23). Page 2). More specifically, the first page size of the original data is compressed and stored in the B23P03, while the other parts are stored in the B23P02. One page of information Storage. For devices with other compression algorithms available on the market, there is still a three-page space required because there is no "combination step" to take advantage of unused space on a page. The mapping table unit 106 can be an electrically erasable programmable read only memory or other flash memory chip having a size smaller than the non-volatile memory 110.

An adaptive compressed data storage method for non-volatile memory using adaptive compressed data storage system 100 is described in the flow chart of FIG. Please also see Figures 5 and 4. The data compressor 102 receives a first data (including the basic units D1-1 to D1-4, hereinafter referred to as the first material 1) from the host interface unit 101 (S01). After the first data 1, a first data 2 (including the basic units D2-1 to D2-4) and a first data 3 (including the basic units D3-1 to D3-4) will be received in order to be noted. The data 1, the first data 2 and the first data 3 are the same size as the one page of the non-volatile memory 110, as described above. The first data 1 and the first data 2 continuously received form a raw material, and the original data needs to be stored in the non-volatile memory 110. Next, if the size of the first material is larger than the predetermined size, 512B, the data compressor 102 divides the first material 1 into four basic units (S02). In step S02, at least two basic units are required. The data compressor 102 also includes basic units D1-1 to D1-4 (S03). The pad charging unit 103 takes over the basic units D1-1 to D1-4, which connect and pad the compressed basic units D1-1 to D1-4 to form the second material 1 so that the second material 1 has an integral multiple of a predetermined size ( S04). Next, the second material 1 is stored in the buffer 104 (S05). For illustration, the size of the buffer 104 is set to 3 KB.

If the number of second materials is 1 and the original data is not completely received, steps S01 to S05 are repeated (S06). This means that at least two second data should be available for combination by the combining unit 105. After repeating these steps, the first data 2 was obtained, and the second data 2 was also created. In the next step, at least two second data are searched, and the second data can be combined by the combining unit 105 in the buffer 104 to have a size of one page (S07). If this is not feasible because the size of the combined second data 1 and the second data 2 exceeds the page, other second data (second data 3) should be used to perform step S07. Therefore, steps S07, S08, and S09 are skipped and are not executed. When the original data is not completely received, step S01 is performed to obtain the first data 3 and create the second data 3. After step S07, the second material 2 and the second material 3 are found to be combined. The combining unit 105 combines the second material 2 and the second material 3 into a third data in the buffer 104 (S08). It should be noted that the original data is not so long that it is received at this time. However, for storing large raw materials, the combining step continues when the original data is not completely received. At the same time, the number of second materials to be combined is not limited to two, but at least two are required. The third material including the second material 2 and the second material 3 is first programmed into a specific page (B23P02) of the non-volatile memory 110 (S09). Then, if the original material has been completely received, the second material 1 is padded and programmed into another specific page (B23P03) of the non-volatile memory 110. As described above, 0 is used as an element of the pad filling.

In fact, steps S01 through S09 should be repeated until the original data is received (S10). After the original data is stored, the mapping table unit 106 updates its A mapping table within (S11). In step S11, a mapping link is stored, which links the physical page addresses (B23P02 and B23P03) for a particular page with the logical address of the original material.

If the size of the buffer 104 is small, for example, 2 KB, the second material 3 cannot coexist with the second material 1 and the second material 2, and according to the present invention, there are two methods to solve the problem. First, a step S08' is added after step S08: if the buffer 104 is full or substantially full and the combination of the second data has a size of one page, the second data in the pad buffer 104 is larger ( The second data 1) is a third data page and the third data is programmed to a particular page in the non-volatile memory 110. Second, a step S08 is added after step S08: if the buffer 104 is full or substantially full and the combination of the second data has a page size, the padding buffer 104 has the longest temporary storage time. The second data (second material 1) is the third data, and the third data is programmed to a specific page in the non-volatile memory 110. Similarly, 0 is used as an element of the pad charge.

In this embodiment, the original material has only three pages in size. In other embodiments, the size of the original material is not an integer multiple of one page. Certain steps in accordance with the present invention are subject to change.

See Figure 6, some elements are used from Figure 4. The differences between the two embodiments are explained below. First, the original data is 5.5 KB, which is less than the original data 512B exemplified in the previous embodiment. Therefore, the first material 3 (including the basic units D3-1 to D3-3) is not full size by one page (requires at least one basic unit equal to the predetermined size). Second, the first data 2 has a high compression ratio. Basic order The elements D2-1 to D2-4 can only be compressed to C2-1 and filled with the pad P2 pad as the second material 2. The first data 1 and the second data 2 did not change.

Therefore, in step S07, the second material 1 and the second material 2 will first be combined and then programmed into B23P02. Since no other first data is received after the first data 3, the second data 3 will be padded with the P4 pad and programmed into the B23P03 in step S09. In this case, step S10 will be skipped and step S11 is performed.

In other embodiments, if the original data is large, when the original data is received, two or more second data are retained, and in step S07, the second data is connected and padded in the buffer 104 to become A third piece of information. Similarly, step S10 will be skipped and step S11 will be executed.

In extreme cases, the original material is too short, so that the size of the original material is not greater than the predetermined size. The first data (only one) will not be split, but will be directly compressed and padded to the size of one page and programmed into the non-volatile memory 110. Only steps S01, S04, S05, S08, S09, and S11 are performed, and the remaining steps are not performed because the requirements of this case are not met.

Although the present invention has been disclosed in the above embodiments, it is not intended to limit the present invention, and any person skilled in the art can make some changes and refinements without departing from the spirit and scope of the present invention. The scope of protection of this creation is subject to the definition of the scope of the patent application attached.

100‧‧‧Adaptive Compressed Data Storage System

101‧‧‧Host interface unit

102‧‧‧Data Compressor

103‧‧‧ pads unit

104‧‧‧buffer

105‧‧‧ combination unit

106‧‧‧ mapping table unit

110‧‧‧Non-volatile memory

200‧‧‧Host

Claims (17)

An adaptive compressed data storage method for non-volatile memory, comprising the steps of: A. receiving a first data, wherein the size of the first data is not greater than a size of a page in a non-volatile memory, The first data continuously received forms an original data, and the original data needs to be stored in the non-volatile memory; B. if the size of the first data is greater than a predetermined size, the first data is divided into at least two basic units, at least a basic unit is equal to the predetermined size; C. compressing the basic unit or the first data; D. connecting and padding the compressed basic unit or the first data to form a second data, so that the second data has The size is an integer multiple of the predetermined size; E. storing the second data in a buffer; F. if the number of the second data is 1 and the original data is not completely received, repeat steps A through E; Searching at least two second data, the second data being combined to have a size of a page in the buffer; H. combining the at least two second data in the buffer as a third data, or if the original The data is completely received, the second data or the second data that is connected and filled in the buffer is a third data, wherein the third data has the same size as a page; Three data to a specific page in the non-volatile memory; and J. If the original material is not completely received, perform step A, where 0 is used as the element of the pad charge. The adaptive compressed data storage method of claim 1, further comprising a step I1 after step I: I1. updating a mapping table, the mapping table storing a physical page address of the specific page and the original A mapping link of a logical address of the data. The adaptive compressed data storage method of claim 1, further comprising a step H1 between the step H and the step I: H1. If the buffer is full or substantially full, and there is no second data Combining the size of the same page, the pad is filled with the second data of all the second data in the buffer as the third data, and the third data is programmed to a specific page of the non-volatile memory, wherein Used as an element for pad filling. The adaptive compressed data storage method of claim 1, further comprising a step H2 between the step H and the step I: H2. If the buffer is full or substantially full, and there is no second data Combining the size of the same page, the second data of the second data stored in the second data in the buffer is the third data, and the third data is programmed to a specific page of the non-volatile memory. , where 0 is used as the element of the pad charge. The adaptive compressed data storage method of claim 1, wherein a lossless compression algorithm is used in step C to compress the first data or the basic unit. For example, the adaptive compressed data storage method described in claim 5, The lossless compression algorithm is LZ77, LZSS, LZH, LZB, LZ78, LZW or LZFG. The adaptive compressed data storage method of claim 1, wherein the non-volatile memory is a NAND flash memory or a solid state hard disk. The adaptive compressed data storage method of claim 1, wherein a basic unit is compressed to form a compressed basic unit, or at least two basic units are compressed to form a compressed basic unit. An adaptive compressed data storage system for non-volatile memory, comprising: a host interface unit for communicating with a host and receiving first data from the host, the size of the first data is no more than one non- a size of a page in the volatile memory, wherein the first data continuously received forms a raw material, the original data needs to be stored in the non-volatile memory; and a data compressor is electrically connected to the host interface unit, if The size of the first data is greater than a predetermined size, and is configured to divide each first data into at least two basic units and compress the basic unit, wherein at least one basic unit is equal to the predetermined size; and a pad charging unit electrically connected to the data compression And a pad for charging the compressed basic unit to form a second data, and if the original data has been completely received, padding the second data or connection and padding the second data to a third data a buffer electrically connected to the pad charging unit and the non-volatile memory for Temporarily storing the second data, replacing a stored second data when it is full or substantially full, and programming the third data to a specific page in the non-volatile memory; and a bonding unit electrically connected to The buffer is configured to combine the at least two second data in the buffer into a third data, wherein if the original data size is not greater than the predetermined size, the first data is not divided but compressed and padded The size of one page is programmed into the non-volatile memory; the second data has a size that is an integer multiple of the predetermined size; the size of the third material is the same as a page; 0 is used as an element of the pad charge. The adaptive compressed data storage system of claim 9, further comprising a mapping table unit electrically connected to the buffer for storing and updating a mapping table having a physical page of a specific page The address is linked to a logical address of the original data. The adaptive compressed data storage system of claim 9, wherein if the buffer is full or substantially full, and no combination of the second data has the same page size, the pad charging unit further fills one The second data is the third data, and the second data that is padded is the largest of all the second data in the buffer. The adaptive compressed data storage system of claim 9, wherein if the buffer is full or substantially full, and no combination of the second data has the same page size, the pad charging unit further fills one The second information is The third data, the second data that is padded is the longest temporary storage time of all the second data in the buffer. The adaptive compressed data storage system of claim 9, wherein a lossless compression algorithm is used to compress the first data or the basic unit. The adaptive compressed data storage system of claim 13, wherein the lossless compression algorithm is LZ77, LZSS, LZH, LZB, LZ78, LZW or LZFG. The adaptive compressed data storage system of claim 9, wherein the non-volatile memory is a NAND flash memory or a solid state hard disk. The adaptive compressed data storage system of claim 9, wherein the buffer comprises a dynamic random access memory or a static random access memory. The adaptive compressed data storage system of claim 9, wherein a basic unit is compressed to form a compressed basic unit, or at least two basic units are compressed to form a compressed basic unit.