CN104410424B - The fast and lossless compression method of embedded device internal storage data - Google Patents

Abstract

The invention discloses a fast lossless compression method for embedded device memory data in the technical field of data processing, which mainly solves the problem of low compression speed of memory pages in the existing compression method. Its main feature is to design two compression formats suitable for memory page data: one is to record the character repetition length, offset distance and new character length in the first byte, and record the remaining new character length, The new character and the remaining offset distance; the second is that the first byte records the compression format flag, the offset distance and the new character length, and records the remaining new character length, new character, and character repetition length sequentially from the second byte and the remaining offset distance. Compared with the current LZO lossless compression method, the present invention improves the compression and decompression speed of memory page data, and obtains a better compression rate, thereby improving the memory data storage capacity and utilization rate of embedded devices, and can be used for storage Restricted embedded devices.

Description

Fast Lossless Compression Method for Embedded Device Memory Data

technical field

The invention belongs to the technical field of data processing, and relates to a data compression method for embedded device memory data. The invention adopts a new data compression format according to the characteristics of memory data during data compression to improve the compression speed, and can be used in embedded devices with limited storage. in the device.

Background technique

Memory is one of the important parts of the computer, it is a bridge to communicate with the CPU. All programs in a computer run in memory. The performance of the memory has a great impact on the computer, and in embedded portable devices with limited volume and storage capacity, the impact of the memory on the device performance and user experience is particularly prominent. In recent years, with the development of the mobile Internet, embedded portable devices such as mobile phones and tablet computers have become a necessary communication tool for people. Therefore, compressing the memory data, increasing the memory storage capacity and utilization rate will greatly improve the overall performance of the device. With the development of society and the increasing amount of information, people have put forward higher requirements for the system performance of embedded devices, such as higher speed, lower energy consumption, smaller volume, and more information can be accessed wait. In order to meet the various performance requirements above, various improved methods have been proposed. Compared with high-cost hardware technology breakthroughs, one of the faster and more effective methods is lossless data compression technology. If lossless data compression technology is used in embedded devices, more data can be accessed in the same hardware storage space, memory utilization can be improved, costs can be reduced, and device performance and user experience can be improved. In view of the various advantages of the above-mentioned technologies, it is necessary to study lossless data compression technology to use this simple and cheap technology to improve the performance of embedded systems.

Lempel and Ziv proposed a high-efficiency lossless compression technology in 1977, that is, the LZ77 lossless data compression algorithm. The main principle of the compression algorithm is to use shorter tags to represent the repeated strings that have appeared before, and the tag format is repeated. Length and offset distance, such as abcdekabcdeha, can be coded into abcdek(5,6)ha, so that on the whole, shorter information replaces longer information, thereby achieving the effect of compression. In 1982, James Storer and Thomas Szymanski improved the algorithm on the basis of LZ77 and proposed the LZSS algorithm, which improved the compression efficiency. Later, Lempel-Ziv-Oberhumer improved the algorithm on the basis of LZSS and proposed the LZO algorithm, which greatly improved the compression coding speed. The LZO algorithm is a lossless data compression algorithm based on a dictionary, which has the characteristics of fast compression speed and instantaneity. The algorithm designs five data compression formats according to different repetition lengths and offset distances. The encoding end selects a certain compression format for encoding according to the matching pair, that is, the repetition length and the offset distance. The decoding end uses the first word of the compression format The section size distinguishes these five different formats, and the maximum offset distance can reach 48K. The disadvantage of this method is that since the memory "paging mechanism" was proposed, the default size of the memory page is set to 4096 bytes, that is, 4KB. Although in principle the memory page size of a computer is configurable, most operating systems still use the default 4KB page in implementation. In order to facilitate memory data management, the memory data should be compressed page by page, and the initial design purpose of LZO is to compress data with variable length. When compressing memory data, it can only achieve a very low compression rate and cannot effectively improve memory utilization. rate, and the compression and decompression speeds are very slow. Therefore, for memory data, the current LZO compression method and compression format cannot be applied.

Contents of the invention

The purpose of the present invention is to overcome the deficiencies of the above-mentioned prior art, and propose a fast and lossless compression method for embedded device memory data, so as to compress and decompress memory data more quickly, thereby effectively improving memory storage capacity and utilization rate.

The technical solution for realizing the present invention is: according to the data characteristics of the memory page, design a kind of compression format suitable for the memory page, carry out compression coding for the memory page data, and concrete steps comprise as follows:

(1) Read a memory page of the memory data in the embedded device, that is, read the memory page page by page according to the page size of 4KB;

(2) Judging whether the data of the read page is new data, if the read data is not recorded in the dictionary, it is judged as new data, and the new data position is recorded in the dictionary, and the memory page data continues to be read until it does not appear up to new data;

The dictionary is a hash table structure directly accessed according to a key value, which is calculated by a hash function;

(3) For the read data recorded in the dictionary, according to the character repetition length and offset distance, that is, the distance between the current position of the character and the record position in the hash table, select different compression formats for encoding:

For the memory page data whose character repetition length is less than 8 and whose offset distance is less than or equal to 2KB, the first byte records the character repetition length L, the offset distance D and the new character length S; start from the second byte to record the remaining The new character length M, the new character C and the remaining offset distance N;

For the memory page data that does not satisfy the character repetition length less than 8, and the offset distance is less than or equal to 2KB, the first byte records the compression format flag T, the offset distance D and the new character length S; start from the second byte to record sequentially The remaining new character length M, new character C, character repetition length L and remaining offset distance N;

(4) Determine whether the encoding position is the end of the currently read-in memory page, if so, output the compressed data and the length of the data, and record the end mark, and execute step (5), otherwise, return to step (2) and continue reading new data;

(5) Judging whether the current page is the last memory page of the memory data packet, if so, the encoding ends, otherwise, return to step (1) to read the next memory page.

Because the compression format adopted by the present invention is simple, the compression and decompression speed of memory page data is improved, better compression rate is obtained, and the memory data storage capacity and utilization rate of embedded devices can be greatly improved.

The test results show that: compared with the current LZO lossless compression method, the present invention increases the compression time by 14.52%, the decompression time by 98.84%, and the compression rate by 1.1%.

Description of drawings

Fig. 1 is a compression flowchart of the present invention;

Fig. 2 is a diagram of the compression format in the present invention.

detailed description

Below in conjunction with figure, the present invention is described in further detail:

With reference to Fig. 1, the realization steps of the present invention are as follows:

Step 1: Read a memory page from the memory data packet of the embedded device, that is, read the memory page page by page according to the page size of 4KB.

Step 2: Read four characters from the read memory page, and perform the first hash operation, that is, calculate the key value through the first hash function, which is the first in the current LZO lossless compression method a hash function.

Step 3: Determine whether the position of the character is legal according to the key value in step 2. If it is legal, go to step 4. If not, update the hash table. The hash table is a data structure directly accessed according to the key value, and then return step2.

The legality mentioned means that every position stored in the hash table can only be accessed according to a key value.

Step 4: Judging whether the character in the current location of the hash table is the same as the read character, if they are the same, go to step 7, if not, go to step 5.

The current storage location of the hash table refers to a location stored in the hash table directly accessed according to the key value in step 2.

Step 5: Use the key value obtained in step 2 to perform the second hash operation, that is, calculate the second key value through the second hash function, which is the first in the current LZO lossless compression method Two hash functions; then judge whether the character position is legal according to the second key value, if it is legal, go to step 6, if not, update the hash table, and return to step 2.

Step 6: Determine whether the character in the address stored in the hash table is the same as the read character, if it is the same, go to step 7, if not, determine that the read character is a new character C, update the hash table, and return to step 2.

The address stored in the hash table refers to an address stored in the hash table directly accessed according to the second key value in step 5.

Step 7: Calculate the new character length S, the character repetition length L and the offset distance D, that is, the distance between the current position of the character and the record position in the hash table.

The calculation method is the same as that in the current LZO lossless compression method.

Step 8: Determine whether the character repetition length is less than 8 and whether the offset distance is less than or equal to 2KB, if yes, perform step 9; if not, perform step 10.

Step 9: Encode the characters according to the recording rules of compression format 1.

Referring to Figure 2(a), the steps of encoding in this step according to the recording rules of compression format 1 are as follows:

9.1) The first 3 bits of the first byte record the character repetition length L, and the 4th, 5th, and 6th bits of the first byte record the last 3 bits of the offset distance D, that is, each bit records 1 bit;

9.2) Determine whether the new character length S is greater than 3, if not, record the new character length S in the last 2 bits of the first byte, and record the new character C from the second byte; if so, then record the new character C in the last 2 bits of the first byte Record the bit as 0 as a sign, and subtract 3 from the new character length S to obtain the remaining new character length M, and then judge whether the remaining new character length M is greater than 255, if not, record the remaining new character length M, if so, then Record a byte 0, and subtract 255 from the remaining new character length M until the remaining new character length is less than 255, record the remaining new character length, and then record the new character C;

9.3) After recording the new character, record the remaining offset distance N, which is the first 8 bits of the offset distance D; then enter step 11.

Step 10: Encode characters according to the recording rules of compression format 2.

Referring to Figure 2(b), the steps of encoding in this step according to the recording rules of compression format 2 are as follows:

10.1) The first two digits of the first byte are recorded as 01 as the compression format flag T, that is, the first digit is recorded as 0, the second digit is recorded as 1, and the third, fourth, fifth, and sixth digits of the first byte are recorded The last 4 bits of the offset distance D, that is, each bit records 1 bit.

10.2) Determine whether the new character length S is greater than 3, if not, then record the new character length S in the last 2 bits of the first byte, that is, record 1 bit for each bit, and record the new character from the second byte; if so, Then the last 2 bits of the first byte are recorded as 0 as a sign, and the new character length S is subtracted by 3 to obtain the remaining new character length M, and then judge whether the remaining new character length M is greater than 255, if not, record the remaining new character length Character length M, if so, record a byte 0, and subtract 255 from the remaining new character length M, until the remaining new character length is less than 255, record the remaining new character length, and then record the new character C;

10.3) After recording the new character, judge whether the character repetition length L is greater than 255, if not, record the character repetition length L, if so, record a byte 0, and subtract 255 from the character repetition length L until the character repetition length is less than 255 , record the character repetition length;

10.4) After recording the character repetition length, record the remaining offset distance N, which is the first 8 bits of the offset distance D.

Step 11: Determine whether the encoding position is the same as the end position of the currently read-in memory page. If they are the same, output the encoded data and the length of the data, and record the end mark, and then enter step 12. If not, return to step 2.

The end mark refers to recording three bytes of data, that is, the first byte is recorded as 17, and the second and third bytes are both recorded as 0.

Step 12: Determine whether the current memory page is the last memory page of the memory data packet, that is, whether all the data in the memory data packet of the embedded device has been read, if so, the encoding ends, if not, return to step 1 .

Effect of the present invention is described further below in conjunction with experiment:

This experiment adopts C language to write the compression method proposed by the invention, by comparing the compression effect of the present invention and the current LZO lossless compression method on the memory page data, the advantages of the compression and decompression speed of the method of the present invention are illustrated. LZO is currently the best lossless compression method. The memory data used in this experiment is the 4KB memory page data of a typical mobile device. The data used in the experiment is the memory page data packet, and the data packet size is 453MB. In the VS2010 program development environment, use the present invention and the current LZO lossless compression method to compress memory page data respectively, and the experimental results are shown in Table 1:

Table 1

The time in Table 1 is the compression time and decompression time of all memory pages in the entire compressed package, and the data in the table is the average result of running 1000 times. It can be seen from Table 1 that the compression rate of the present invention is increased by 1.1%, and the compression time and decompression time are respectively increased by 14.52% and 98.84%, thereby improving the data storage capacity and utilization rate of the embedded memory.

Claims (5)

1. A fast lossless compression method for embedded device memory data, comprising the steps: (1) Read a memory page of the memory data in the embedded device, that is, read the memory page page by page according to the page size of 4KB; (2) Judging whether the data of the read page is new data, if the read data is not recorded in the dictionary, it is judged as new data, and the new data position is recorded in the dictionary, and the memory page data continues to be read until it does not appear up to new data; The dictionary is a hash table structure directly accessed according to a key value, which is calculated by a hash function; (3) For the read data recorded in the dictionary, according to the character repetition length and offset distance, that is, the distance between the current position of the character and the record position in the hash table, select different compression formats for encoding: For the memory page data whose character repetition length is less than 8 and whose offset distance is less than or equal to 2KB, the first byte records the character repetition length L, the offset distance D and the new character length S; start from the second byte to record the remaining The new character length M, the new character C and the remaining offset distance N; For the memory page data that does not meet the character repetition length less than 8, and does not meet the offset distance less than or equal to 2KB, its first byte records the compression format flag T, offset distance D and new character length S; start from the second byte Record the remaining new character length M, new character C, character repetition length L and remaining offset distance N in sequence; (4) Determine whether the encoding position is the end of the currently read-in memory page, if so, output the compressed data and the length of the data, and record the end mark, and execute step (5), otherwise, return to step (2) and continue reading new data; (5) Judging whether the current page is the last memory page of the memory data packet, if so, the encoding ends, otherwise, return to step (1) to read the next memory page. 2. the fast lossless compression method of embedded device memory data according to claim 1, is characterized in that: the first byte record character repetition length L described in step (3), offset distance D and new character length S, Record according to the following rules: The first 3 digits of the first byte record character repetition length L, L<8; The 4th, 5th, and 6th bits of the first byte record the last 3 bits of the offset distance D, that is, each bit records 1 bit; Determine whether the new character length S is greater than 3, if not, the last 2 bits of the first byte record the new character length S, that is, each bit records 1 bit, if so, the last 2 bits of the first byte are recorded as 0 as a sign, And subtract 3 from the new character length S to obtain the remaining new character length M. 3. the fast lossless compression method of embedded device memory data according to claim 1, is characterized in that: the described in step (3) starts to record remaining new character length M, new character C successively from second byte and the remaining offset distance N, recorded according to the following rules: Determine whether the remaining new character length M is greater than 255, if not, record the remaining new character length M, if so, record a byte 0, and subtract 255 from the remaining new character length M until the remaining new character length is less than 255 , record the remaining new character length, and then record the new character C; After the new character is recorded, the remaining offset distance N is recorded, and the remaining offset distance N is the first 8 bits of the offset distance D. 4. the fast lossless compression method of embedded device memory data according to claim 1, is characterized in that: the first byte record compression format sign T, offset distance D and new character length S described in step (3), Record according to the following rules: The first two digits of the first byte are recorded as 01 as the compression format flag T, that is, the first digit is recorded as 0, and the second digit is recorded as 1; The 3rd, 4th, 5th, and 6th bits of the first byte record the last 4 bits of the offset distance D, that is, each bit records 1 bit; Determine whether the new character length S is greater than 3, if not, the last 2 bits of the first byte record the new character length S, that is, each bit records 1 bit, if so, the last 2 bits of the first byte are recorded as 0 as a sign, And subtract 3 from the new character length S to obtain the remaining new character length M. 5. the fast lossless compression method of embedded device internal memory data according to claim 1 is characterized in that: the described in step (3) starts to record remaining new character length M, new character C successively from second byte , the character repetition length L and the remaining offset distance N are recorded according to the following rules: Determine whether the remaining new character length M is greater than 255, if not, record the remaining new character length M, if so, record a byte 0, and subtract 255 from the remaining new character length M until the remaining new character length is less than 255 , record the remaining new character length, and then record the new character C; After recording the new character, judge whether the character repetition length L is greater than 255, if not, record the character repetition length L, if so, record a byte 0, and subtract 255 from the character repetition length L until the character repetition length is less than 255, record The character repeat length; After the character repetition length is recorded, the remaining offset distance N is recorded, and the remaining offset distance N is the first 8 bits of the offset distance D.