CN108702160A - Method, apparatus and system for compression and decompression data - Google Patents
Method, apparatus and system for compression and decompression data Download PDFInfo
- Publication number
- CN108702160A CN108702160A CN201780015262.7A CN201780015262A CN108702160A CN 108702160 A CN108702160 A CN 108702160A CN 201780015262 A CN201780015262 A CN 201780015262A CN 108702160 A CN108702160 A CN 108702160A
- Authority
- CN
- China
- Prior art keywords
- data
- value
- block
- unpressed
- data value
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 238000007906 compression Methods 0.000 title claims abstract description 142
- 230000006835 compression Effects 0.000 title claims abstract description 142
- 230000006837 decompression Effects 0.000 title claims abstract description 134
- 238000000034 method Methods 0.000 title claims abstract description 117
- 230000015654 memory Effects 0.000 claims abstract description 61
- 239000003638 chemical reducing agent Substances 0.000 claims abstract description 48
- 238000004891 communication Methods 0.000 claims abstract description 34
- 238000013144 data compression Methods 0.000 claims description 100
- 238000003860 storage Methods 0.000 claims description 77
- 238000001514 detection method Methods 0.000 claims description 58
- 238000004590 computer program Methods 0.000 claims description 12
- 239000000872 buffer Substances 0.000 claims description 10
- 238000012360 testing method Methods 0.000 claims description 9
- 235000013399 edible fruits Nutrition 0.000 claims description 5
- 238000003825 pressing Methods 0.000 claims description 4
- 239000000203 mixture Substances 0.000 claims description 2
- 230000004044 response Effects 0.000 claims description 2
- 238000002156 mixing Methods 0.000 abstract description 19
- 230000005540 biological transmission Effects 0.000 abstract description 15
- 238000010586 diagram Methods 0.000 description 34
- 238000012545 processing Methods 0.000 description 22
- 230000008569 process Effects 0.000 description 19
- 238000013461 design Methods 0.000 description 8
- 238000005516 engineering process Methods 0.000 description 4
- 238000000605 extraction Methods 0.000 description 4
- 238000012546 transfer Methods 0.000 description 4
- 230000008901 benefit Effects 0.000 description 3
- 238000006073 displacement reaction Methods 0.000 description 3
- 230000006870 function Effects 0.000 description 3
- 238000007689 inspection Methods 0.000 description 3
- 230000008859 change Effects 0.000 description 2
- 230000003247 decreasing effect Effects 0.000 description 2
- 238000000151 deposition Methods 0.000 description 2
- 230000007246 mechanism Effects 0.000 description 2
- 230000008929 regeneration Effects 0.000 description 2
- 238000011069 regeneration method Methods 0.000 description 2
- 239000007787 solid Substances 0.000 description 2
- 238000006467 substitution reaction Methods 0.000 description 2
- 239000008187 granular material Substances 0.000 description 1
- 230000006872 improvement Effects 0.000 description 1
- 230000014759 maintenance of location Effects 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000008450 motivation Effects 0.000 description 1
- 238000005457 optimization Methods 0.000 description 1
- 238000006116 polymerization reaction Methods 0.000 description 1
- 238000012797 qualification Methods 0.000 description 1
- 230000009467 reduction Effects 0.000 description 1
- 238000005070 sampling Methods 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M7/46—Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind
- H03M7/48—Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind alternating with other codes during the code conversion process, e.g. run-length coding being performed only as long as sufficientlylong runs of digits of the same kind are present
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
- G06F12/0806—Multiuser, multiprocessor or multiprocessing cache systems
- G06F12/0811—Multiuser, multiprocessor or multiprocessing cache systems with multilevel cache hierarchies
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
- G06F3/0608—Saving storage space on storage systems
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
- G06F3/0638—Organizing or formatting or addressing of data
- G06F3/064—Management of blocks
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
- G06F3/0655—Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
- G06F3/0659—Command handling arrangements, e.g. command buffers, queues, command scheduling
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0668—Interfaces specially adapted for storage systems adopting a particular infrastructure
- G06F3/0671—In-line storage system
- G06F3/0673—Single storage device
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
- H04N19/102—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or selection affected or controlled by the adaptive coding
- H04N19/13—Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/90—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals
- H04N19/91—Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
- G06F2212/40—Specific encoding of data in memory or cache
- G06F2212/401—Compressed data
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
- G06F3/0655—Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
- G06F3/0656—Data buffering arrangements
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Human Computer Interaction (AREA)
- Multimedia (AREA)
- Signal Processing (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Abstract
Method, apparatus and system make compressor reducer and decompressor extension be coded and decoded for data in cache/memories/data transmission sub-system to computer system or in communication network.Example variable-length compressor reducer be extended to can compressed data value block, and described compressed piece include compressed value and unpressed value mixing, wherein the metadata of unique particular meaning code word (UUIC) form indicates unpressed value.Example variable-length decompressor is extended to the compressed data block that can decompress the mixing including compressed data value and unpressed data value.The compressor reducer and decompressor are extended to the compression and decompression for the common compression situation for supporting to be used in combination with variable-length compression, compressibility in cache/memories/data transmission sub-system to improve computer system or in communication network.
Description
Technical field
Present disclosure generally relates to data compression and decompression fields, such as in the buffer/store of computer system
Data compression and decompression in device subsystem and/or data transmission sub-system or in data communication system.
Background technology
Data compression is a kind of more mature technology for reducing size of data.It is applied to be stored in department of computer science
Data in the memory sub-system of system are to increase storage capacity.When between different sub-systems of the data in computer system
When transmission, or usually when carrying out the transmission between two points in the data communication system including communication network, number
It is also used according to compression.
Data compression needs two basic operations:1) compression (also referred to as encoding), compression is to make unpressed data
For input, and by will be uncompressed with corresponding code word (also referred to as coding, character code or code in the literature) replacement data value
Data be converted to compressed data;And 2) decompression (also referred to as decode), decompression be using compressed data as
It inputs and unpressed by being converted to the compressed data with corresponding data value replacement code word.Data compression can be with
It is lossless formula or damages formula, this depends on whether that the actual data value after decompression and the raw value before compression are complete
Exactly the same (lossless formula), or depend on whether that the data value after decompression is different from raw value and original value can not obtain
(damaging formula).It can implement compression and decompression with the combination of software or hardware or software and hardware, it is corresponding to realize
Method, apparatus and system.
Fig. 1 depicts the example of computer system 100.Computer system 100 includes using communication device such as Internet
Network is connected to one or several processing lists of storage hierarchy (memory hierarchy, memory hierarchy) 110
First P1 ... Pn.Each processing unit includes processor (or core), and each processing unit can be CPU (central processings
Unit), GPU (graphics processing unit) or be typically execute calculate block.On the other hand, storage hierarchy 110 is constituted
The storage subsystem of computer system 100, and including can be with one or several ranks (level, level, grade) L1-L3
Carry out the buffer memory 120 and memory 130 (also known as primary memory) of tissue.Memory 130 may be also connected to secondary
Grade storage device (for example, hard disk drive, solid state drive or flash memory).Memory 130 can be organized into several ranks, example
Such as, fast, primary memory (for example, DDR) and flash memory.Buffer memory 120 in instant example includes three ranks, wherein L1
It is dedicated cache with L2, because each processing unit P1-Pn is connected to specified L1/L2 cachings, and L3 is in all processing
It is shared between unit P1-Pn.With different number processing unit and normally with processing unit and memory subsystem
In the case of various combination between system, alternative example, which may be implemented to have, does not have cache level more, less or even
It is other and with or without the different cache hierarchies of special or shared specified caching, realize various storage levels
Not, everything is all easy to implement by technical staff.
It can be in different ways by data compression applications in computer system.Fig. 2 depicts computer system such as Fig. 1
System 100 example 200, wherein data are compressed in the memory such as main memory of this computer system.
This means that by corresponding squeeze operation as described above, data are compressed before being stored in memory, and data exist
It is decompressed when leaving memory.
In the alternate example 300 of computer system shown in Fig. 3, the L3 that data compression can be applied to caching system is slow
It deposits.It similar to previous example, needs to be compressed before data are stored in caching, and needs to leave caching in data
(for example, go thereto data be it is unpressed other caching ranks (L2) or memory 330) before unzip it.It is substituting
In example, data can be stored in a compressed format in any rank of cache hierarchy.
Only it can also be compressed when being transmitted between data different sub-systems in computer systems.
In the alternate example 400 of computer system shown in Fig. 4, when using corresponding communication device L3 caching with memory 430 it
Between transmission data when, data are compressed.Similar to previous example, need the presence of compression reconciliation in the end of communication device
Compression before transmitting the data to compress data, and is to solve data when receiving data at the other end
Compression.
In the alternate example 500 of computer system, data compression can be applied to the group of subsystem as depicted in figures 5
In conjunction.In this example, when data are stored in memory 530 and when data are in memory 530 and caching level knot
When being transmitted between structure 520, data are compressed.In this way, when data are moved to memory 530 from cache hierarchy 520,
It can only need to compress it before L3 caching transfers in data.Alternatively, leaving memory 530 goes to caching level knot
The compressed data of structure 520 can only need to connect memory 530 with cache hierarchy 520 being received
It is decompressed when the other end of communication device.About the combination that will be compressed applied to the different sub-systems in computer system, appoint
What example is all feasible, and can be realized by those skilled in the art.
Carry out data transmission between two arbitrary points that can also be in communication network.Fig. 6 is depicted including between 2 points
Communication network 605 data communication system 600 example, wherein data are transmitted by transmitter 610 and are connect by receiver 620
It receives.In such example, these points can be the source node and purpose of two intermediate nodes or communication link in network
The combination of ground node or these situations.Data compression can be applied to data as example system 700 as depicted in figure 7
Communication system.Applied compression is needed before data are launched by transmitter 710 on communication network 705, and in data quilt
Receiver 720 is needed after receiving using decompression.
Realize that data compression there are a variety of different algorithms.Family in data compression algorithm is statistics compression algorithm, the system
Meter compression algorithm is data dependence and can provide compression efficiency close to entropy, because the statistics compression algorithm is based on number
Variable-length (also referred to as variable-width) code is distributed according to the statistical property of value:Short code word is used for the data value to frequently occurring
It is encoded, and longer code word encodes the data value less frequently occurred.Huffman coding is known statistics
Compression algorithm.
It is canonical Huffman coding for accelerating the known modification of the huffman coding of decompression.Based on this, code word has
Serial No. attribute, it means that the code word of equal length is continuous integer.
The example of the compression and decompression mechanism based on canonical Huffman is proposed in the prior art.This compression reconciliation
Compression mechanism can be used in example above-mentioned to realize the compression and decompression based on Huffman.
Fig. 9, which is shown, implements the huffman coding such as compressor reducer 900 from the prior art of canonical Huffman coding
Example.By unpressed piece as inputting, described unpressed piece is burst of data value and is included in entire sheet the compressor reducer
Be typically expressed as in disclosure v1, v2 ..., one or more data values of vn.Unit 910 --- it can be storage unit
Or the extractor for extracting data value from unpressed piece --- provide data value to variable length coding unit 920.It can
It includes code table (CT) 922 and code word (CW) selector 928 to become length encoding unit 920.CT 922 is to may be embodied as look-up table
(LUT) or the table of Computer Cache memory (with any arbitrary correlation), and include one or more entries;Each
Entry includes the value 923 that can be compressed using code word, CW 925 and code word size (cL) 927.By statistics compression algorithm institute
The various code word sets used are variable-lengths, so having the width (code word of fixed size when saving it in each entry
925) when in CT 922, it is necessary to these code word sets mend with zero and fill out.Code word size 927 keeps the reality of variable length code
Border length (for example, as unit of position).CW selectors 928 are identified actual CW using cL and give up zero for mending and filling out.So
The value of coding is linked to the rest part of compressed value afterwards, forms compressed piece together.Depict in fig. 25 in accordance with
The exemplary process diagram of the compression method of previously described compression step.
The example of decompressor 1000 in the prior art is shown in Figure 10.Canonical Huffman decompression can be divided into two
A step:Codeword detection and value retrieval (retrieve is obtained, restores, fetched).Each in these steps passes through following
One of unit is implemented:(1) codeword detection unit (CDU) 1020 and (2) value retrieval unit (VRU) 1030.CDU's 1020
Purpose is to find effective code word in compressed sequence (that is, sequence of the code word of compressed data value).CDU1020 packets
Include one group of comparator 1022 and priority encoder 1024.Each comparator 1022a, 1022b, 1022c will each potential positions
Sequence (bit-sequence, bit sequence) is compared with known code word, and the known code word is specific length in this example
(when code generates) the canonical Huffman code word (FCW) distributed for the first time.In substituting and implementing, it can also use and finally distribute
Canonical Huffman code word, but in this case, the definite comparison done will be different.Above-mentioned bit sequence to be compared can be with
It is stored in storage unit 1010 (such as being embodied as FIFO or trigger) and determines the quantity and bit sequence of comparator
In most wide person maximum width, the largest amount of bit sequence to be compared depends on the effective Huffman determined when code generates
The maximum length (mCL) of code word.However, the selected implementation depending on this decompressor is (for example, with software or with hard
Part), the maximum length can be restricted to particular value in design, compiling, configuration or run time.By the defeated of comparator 1022
Go out and be inserted into the priority encoder such as structure 1024, the length which exports the matched code word (is being schemed
It is known as " matched length " in 10).Based on this, extracted from the bit sequence for being stored in storage unit 1010 detected effective
Code word (matched code word);By bit sequence displacement and position as many defined by " matched length ", and by vacant portion
Divide load at the subsequent bit of compressed sequence so that CDU 1020 can determine next effective code word.
On the other hand, value retrieval unit (VRU) 1030 includes that offset table 1034, subtractor unit 1036 and decompression are searched
Table (DeLUT) 1038.It must be from the also determination in previous step to determine using " matched length " from previous step
The deviant (being stored in offset table 1034) that (1036) are subtracted in the arithmetic value of the matched code word, to obtain DeLUT 1038
Address, wherein can obtain and be attached to from DeLUT and be stored in decompression corresponding to the raw value of the code word detected
Remaining decompressed value in contracting block 1040.Repeat decompressor operation, until be stored in a compressed format inputted through pressure
All values in the sequence (in Fig. 10 be known as compressed piece) of contracting be restored to unpressed data value v1, v2 ..., vn.
Figure 26 depicts the exemplary process diagram of the decompression method in accordance with previously described decompression step.
Said compressor and decompressor can utilize variable-length canonical Huffman coding quickly and efficiently to compress number
According to block, and decompress the data block using the coding compression of variable-length canonical Huffman.However, they are unable to compression and decompression
The data block of mixing including compressed and unpressed value, this is when the computer that will count compression applied to examples detailed above
Common situations when system or communication network.The present inventors have realized that being deposited in the technical field of data compression and decompression
In improved space.
Invention content
The object of the present invention is to provide the improvement in data compression and decompression technical field.
Present disclosure substantially discloses cache subsystem and/or the storage worked as and will compressed applied to such as computer system
When in device subsystem and/or data transmission sub-system and/or in data communication system, passed through for compressed data value block and decompression
The method, apparatus and system of the data value block of compression.There are various methods using the variable length code based on entropy in the subsystem
Effectively compressed data in system, and a kind of such mode is by using huffman coding.Current compressor reducer can be used
In carrying out compressed data value block using huffman coding, while current decompressor can be used for decompression huffman coding pressure
The data block of contracting.However, when applying the compression based on entropy in the system, some data are incompressible or selected
To be not compressed;For example, they only occur primary, therefore them are compressed than keeping them uncompressed to need more metadata;
Or without being directed to certain encoding of a data values, because during they do not appear in statistical information collection, but appeared in pressure
During contracting.Therefore, compressor reducer shortage allows them to create compressed data value and unpressed in same
The important feature of the mixing of data value;And when being mixed in block, the decompressor cannot distinguish between compressed
Data and unpressed data.Disclosed method, apparatus and system enhance profit using following new features in this disclosure
With the existing compressor reducer and decompressor of variable length code:It is normal when applying in computer system or communication network that will compress
In the case of seeing, compression data block includes the mixing of compressed data and unpressed data;And when in this system
When including the mixing of compressed data and unpressed data, compressed data block is decompressed.In addition, the side proposed
Method, equipment and system even further enhance the compressor reducer and decompressor by following manner, and the mode is i.e. by them
With other aggressive compressor reducers and decompressor point for the common compression situation in the computer system and communication network
It does not combine.
The first aspect of the present invention is a kind of data compression device, for that will include the uncompressed of one or more data values
The compressed data block of data block boil down to, which includes:
Compressor reducer is configured as the corresponding variable length codeword of data value boil down to of unpressed data block;
Detector, be configured as detecting unpressed data are in the block cannot be by the data value of the compressor compresses;With
And
Compressed data block generator is configured as by combined generating compressed data blocks by following:
Compressed data value, the compressed data value are in the block by the compression with unpressed data
The form of the corresponding variable length codeword of data value of device compression;
Unpressed data value, the unpressed data value be in unpressed data it is in the block it is detected not
It can be by the form of the data value of the compressor compresses;And
Metadata, the metadata indicate unpressed data value, and wherein metadata is unique particular meaning code word.
Advantageously, unique particular meaning code word is the code generated together with the variable length codeword of compressor reducer when code is generated
Word.
More specifically, unique particular meaning code word can be generated when code is generated by following manner:The mode is
The frequency of occurrences for not being presented on all data values in value-frequency meter is calculated or estimated when code generates, wherein they with
The frequency of occurrences that the total number of the data value of appearance is compared will influence the width of unique particular meaning code word.Therefore, by using
The frequency of occurrences of data value, by distinguishing the unpressed data value in compressed data block with unique particular meaning code word
With compressed data value, it is more than art methods that can improve compression efficiency.When code generates not by value-frequency with
The data value of track device capture is more, then is correspondingly kept unpressed data value compared with the data value total number of appearance and gets over
More, the unique particular meaning code word being used to indicate in the compressed data unpressed data value in the block of generation is narrower.Separately
On the one hand, the appearance number frequency of unpressed data value is lower, and the compressed data being used to indicate in generation are in the block not
Unique particular meaning code word of the data value of compression is wider.
The second aspect of the present invention is data decompression device, includes one by compressed data block decompression for being
Or the decompressed data block of multiple data values, the data decompression device include:
Decompressor is configured as the variable length codeword decompression of compressed data block being condensed to corresponding decompressed
Data value;And
Decompressed data block generator, is configured as:
Detection is in compressed data metadata in the block, and the metadata is unique particular meaning code word, and instruction includes
In compressed data unpressed data value in the block;And
Based on the metadata detected, decompressed data block is generated by following manner:The mode combines
Self solve the decompressed data value of compressor reducer and the unpressed data value from compressed data block so that generated
The order of the data value of decompressed data block is with the data value before the data compression for generating compressed data block
The order occurred in unpressed data block is identical.
The third aspect of the present invention is for that will include the unpressed data block boil down to warp of one or more data values
The data compression method of the data block of compression, the data compression method include:
By the corresponding variable length codeword of data value boil down to of unpressed data block;
Detecting that unpressed data are in the block cannot be by the data value of the compressor compresses;And
By being combined to generate compressed data block by following:
Compressed data value, the compressed data value are in the block by compressor reducer pressure with unpressed data
The form of the corresponding variable length codeword of data value of contracting;
Unpressed data value, the unpressed data value be in unpressed data it is in the block it is detected not
It can be by the form of the data value of the compressor compresses;And
Metadata, the metadata indicate unpressed data value, and wherein metadata is unique particular meaning code word.
The fourth aspect of the present invention is uncompressing data, includes one by compressed data block decompression for being
Or the decompressed data block of multiple data values, the uncompressing data include:
The variable length codeword decompression of compressed data block is condensed to corresponding decompressed data value;
Detection is in compressed data metadata in the block, and the metadata is unique particular meaning code word, and instruction includes
In compressed data unpressed data value in the block;And
Based on the metadata detected, decompressed data block is generated by following manner:The mode combines
Self solve the decompressed data value of compressor reducer and the unpressed data value from compressed data block so that generated
The order of the data value of decompressed data block is with the data value before the data compression for generating compressed data block
The order occurred in unpressed data block is identical.
The fifth aspect of the present invention is system, including one or more memories, according to the data pressure of first aspect above
Contracting equipment and data decompression device according to second aspect above.
The sixth aspect of the present invention is computer program product, including code command, and the code command is by processing equipment
Cause the execution according to the method for the third aspect above when load and execution.
The seventh aspect of the present invention is computer program product, including code command, and the code command is by processing equipment
Cause the execution according to the method for fourth aspect above when load and execution.
According to disclosure in detail below, accompanying independent claim and attached drawing, its other party of disclosure embodiment
Face, target, feature and advantage will become apparent from.Usually, unless expressly stated otherwise, all arts otherwise used in claim
Radix is explained according to the ordinary meaning in its technical field.
Unless otherwise expressly provided, otherwise for " one (a)/mono- (an)/[Element, equipment, component, device, step etc.
Equal ]" with reference at least one reality that will be read as to being opened property to the element, equipment, component, device, step etc.
The reference of example.Unless explicitly claimed, otherwise any method disclosed herein the step of not necessarily in strict accordance with disclosed suitable
Sequence executes.
Description of the drawings
The embodiment of the example of background technology and present invention aspect is described with reference to the following drawings:
Fig. 1 instantiates the block diagram of the computer system including n processing core, and each processing core is all connected to three grades
Other cache hierarchy and main memory.
Fig. 2 instantiates the block diagram of Fig. 1, and wherein main memory preserves the data of compressed form.
Fig. 3 instantiates the block diagram of Fig. 1, and wherein L3 cachings preserve the data of compressed form.Other caching ranks also may be used
By store it is compressed in the form of data.
Fig. 4 instantiates the block diagram of Fig. 1, and wherein data are compressed within a communication device, such as when in memory and cache layer
When being transmitted between secondary structure.
Fig. 5 instantiates the block diagram of Fig. 1, wherein compression can be applied to main memory and memory is connected to caching level
The link of structure.In general, compression can be applied to similar cache hierarchy, transmitting device (for example, memory is connected to
The link of cache subsystem) and main memory part any combinations.
Fig. 6 instantiates the block diagram of the data transfer links of two points in connection communication network.These points can be network
In two intermediate nodes or the source node and destination node of communication link or the combination of these situations.
Fig. 7 instantiates the block diagram of the data transfer links of Fig. 6, wherein the data being transmitted are compressed forms, so
They may need to be compressed in the transmitter and be decompressed in the receiver.
Fig. 8 instantiates unpressed data value block in left side, and instantiates to use on right side and utilized huffman coding
The same block of the compressed form of the variable length code of generation.Unpressed piece of all data values are all by corresponding Hough
Graceful code word replaces.
Fig. 9 instantiates the compressor reducer for compressing (or coding) block as illustrated in Figure 8 using huffman coding.
Figure 10 instantiates the decompressor of the block for decoding (or decompression) operating specification huffman coding compression.
Figure 11 instantiates unpressed piece in left side, and right side by alternative way instantiate it is compressed in the form of
Same block, including:Bitmask, the bitmask indicate which value is uncompressed by compression and which value;And variable length code
(that is, the bit sequence encoded by variable length code), according to design that is relevant but being not claimed currently, the variable-length
Coding includes the mixing of compressed value and unpressed value.
Figure 12 instantiates unpressed piece in left side, and instantiates compressed shape on right side with the second alternative way
The same block of formula, includes the mixing of compressed value and unpressed value, wherein being equipped with before each unpressed value unique
Variable-length (for example, Huffman) code word, unique variable length codeword correspond only to all unpressed values.
Figure 13 instantiates unpressed piece in left side, and instantiates compressed shape on right side with third alternative way
The same block of formula includes the mixing of compressed value and unpressed value, wherein will be each by initial data value sequence in block
Unpressed value replaces with unique variable-length (for example, Huffman) code word, which corresponds only to own
Unpressed value, while practical unpressed value is stored in the end of block (that is, what is finally preserved is uncompressed to occur order on the contrary
Value be the appearance of original order first in block by data value unpressed value).
Figure 14 is instantiated according to correlation but the data compression device of design that is not claimed currently, the data compression device
It is the compressor reducer based on Fig. 9, but is changed by following manner and be extended to the block that can compress Figure 11:The mode is examined
Compressible and incompressible piece of data value is surveyed, and generates the mask being placed in before the bit sequence of variable length code, to refer to
Show and be included in the compressed unpressed value in the block, the bit sequence of the variable length code includes compressed value and not
The value of compression.
Figure 15 is instantiated according to correlation but the data decompression device of design that is not claimed currently, the data decompression
Equipment is the decompressor based on Figure 10, but is changed and be extended to and can decompress compressed piece of Figure 11, this is compressed
Block include the mask before being placed in the bit sequence of variable length code to indicate unpressed value.
Figure 16 instantiates data compression device, which is the compressor reducer based on Fig. 9, but passes through following manner
It is changed and is extended to the block that can compress Figure 12:The mode detects compressible and incompressible piece of data value, and
Using corresponding only to unpressed value and be attached at the unique code word before each unpressed value to variable length code
Unpressed piece of data value in bit sequence is encoded, and the bit sequence of the variable length code includes compressed value and do not press
The value of contracting.
Figure 17 a instantiate data decompression device, which is the decompressor based on Figure 10, but is repaiied
Can be decompressed by changing and being extended to by compressed piece of Figure 12, this compressed piece includes compressed value and unpressed value,
It is equipped with the unique code word for corresponding only to unpressed value before wherein each unpressed value.
Figure 17 b show the alternative realization of the data decompression device of Figure 17 a.
Figure 18 instantiates data compression device, which is the compressor reducer based on Fig. 9, but passes through following sides
Formula is changed and is extended to the block that can compress Figure 13:The mode detects compressible and incompressible piece of data value,
The unpressed block number in the bit sequence of variable length code is replaced using the unique code word for corresponding only to all unpressed values
According to value, and by actual unpressed value, by the end for occurring order on the contrary and being placed on compressed piece, (value finally occurred is extremely
The value of first appearance), the bit sequence of the variable length code includes compressed value and unpressed value.
Figure 19 shows data decompression device, which is the decompressor based on Figure 10, but is repaiied
Can be decompressed by changing and being extended to by compressed piece of Figure 13, this compressed piece includes the mixed of compressed value and uncompressed value
It closes, wherein each unpressed value is replaced by the unique code word for corresponding only to all unpressed values, while unpressed value
The end for being stored in block by occurring order on the contrary.
Figure 20 shows empty unpressed piece in left side, is only to include the block of data values of zero, and show on right side
The same block of variable length code compression is utilized using the compressor reducer of Fig. 9, it is assumed that each zero be by it is minimum may width (1
Position) code word replace.
Figure 21 shows empty unpressed piece in left side, is only to include the block of data values of zero, and show on right side
Use the same block of 1 coding compression.
Figure 22 shows unpressed piece in left side, identical as the block in Figure 11, Figure 12 and Figure 13, and right side with
4th alternative way is shown including following same blocks in compressed form:One indicator, the indicator refer to
Show whether compressed piece be empty;And the bit sequence of variable length code, the bit sequence of the variable length code includes through pressure
The mixing of the value of contracting and uncompressed value corresponds only to all unpressed values only wherein being equipped with before each unpressed value
One variable-length (for example, Huffman) code word.
Figure 23 instantiates unpressed piece of (packet of unpressed piece of (compressed sky block) and Figure 22 can compressing Figure 21
Include compressed piece of the mixing of compressed value and unpressed value) data compression device, which includes
The data compression device of Figure 16 and empty block detection unit, the sky block detection unit check whether all pieces of data values are all zero.
In this case, it is compressed using such as 1 coding in Figure 21;Otherwise, it is compressed as in Figure 22.
Figure 24 a instantiate that can to decompress Figure 21 (compressed sky block) and Figure 22 (including compressed and unpressed
Compressed piece of the mixing of value) compressed piece of data decompression device, which includes Figure 17 a
Data decompression device and added logic (in the bottom of Figure 24), the added logic can by check first of block whether be
Zero comes whether detection block is compressed to sky block.In this case, decompressed piece of all data values are all assigned value 0.
Figure 24 b instantiate the alternative example of the data decompression device of Figure 24 a, can decompress the compressed of Figure 21
Block (compressed sky block) and compressed piece of Figure 22 (including compressed value and the mixing of unpressed value is compressed
Block), which includes the data decompression device and added logic (in the bottom of Figure 24) of Figure 17 a, this is additionally patrolled
Collecting can be by checking whether first of block be whether zero be compressed to sky block come detection block.In this case, decompressed
All data values of block be all reset to value 0.
Figure 25 instantiates the exemplary stream for the compression method using variable length code (for example, Huffman) compression blocks
Cheng Tu.
Figure 26 is instantiated for decompressing compressed piece compressed using variable length code (for example, canonical Huffman)
Decompression method exemplary process diagram.
Figure 27 instantiates the block on the compression method of Figure 25 and that Figure 11 can be compressed by following manner of structure
New method exemplary process diagram, the mode i.e. detect compressible and incompressible piece of data value and generation is placed in packet
The mask before the bit sequence of the variable length code of compressed value and unpressed value is included, is included in instruction described through pressure
The unpressed value in the block of contracting.
Figure 28, which is instantiated, builds compressed piece of new side that is on the method for Figure 26 and can decompressing Figure 11
The exemplary process diagram of method, this compressed piece including the mask before being placed in the bit sequence of variable length code to indicate not press
The value of contracting.
Figure 29 instantiate structure on the compression method of Figure 25 with can be compressed by following manner Figure 12 block it is new
The exemplary process diagram of method, the mode detects compressible and incompressible piece of data value, and use corresponds only to
Unpressed value and unique code word before being attached at each unpressed value is not to pressing in the bit sequence of variable length code
The block data value of contracting is encoded, and the bit sequence of the variable length code includes compressed value and unpressed value.
Figure 30 instantiates compressed piece of new method can decompressing Figure 12 of the structure on the method for Figure 26
Exemplary process diagram, this compressed piece includes compressed value and unpressed value, wherein before each unpressed value
It is equipped with the unique code word for corresponding only to unpressed value.
Figure 31 instantiate structure on the compression method of Figure 25 with can be compressed by following manner Figure 13 block it is new
The exemplary process diagram of method, the mode detects compressible and incompressible piece of data value, and utilizes and correspond only to
The unique code word of all unpressed values encodes unpressed piece of data value in the bit sequence of variable length code, with
And by the end for occurring order on the contrary and being placed on compressed piece, (value finally occurred is to first by actual unpressed value
The value of appearance), the bit sequence of the variable length code includes compressed value and unpressed value.
Figure 32 instantiates structure on the method for Figure 26 can decompress compressed piece of the new method of Figure 13
Exemplary process diagram, this compressed piece includes the compressed mixing being worth with unpressed value, wherein each unpressed value
Unique code word by corresponding only to all unpressed values is replaced, while unpressed value is stored in block by occurring order on the contrary
End.
Figure 33 instantiates the exemplary process diagram of new method, and new method structure is on the compression method of Figure 29 so as to also
It checks whether all pieces of data values are zero, and correspondingly sets empty block indicator to " 1 ", use such as Figure 21 in this case
In 1 coding block is compressed;Otherwise, block is compressed as in Figure 22, zero-bit indicator is set as 0.
Figure 34 instantiates the exemplary process diagram of new method, and new method structure is on the method for Figure 30 can pass through
Whether first of inspection block comes whether detection block is compressed to sky block equal to 1.In this case, decompressed block is all
Data value is all assigned value 0;Otherwise, block is decompressed by method illustrated by Figure 30.
Specific implementation mode
Present disclosure is disclosed when compression is applied to the cache subsystem and/or memory sub-system in computer system
And/or when data transmission sub-system and/or communication network, for compressing one or more data value blocks and decompressing one or more
The method, apparatus and system of a compressed data value block.Disclosed method, apparatus and system extension and optimization baseline compression
Method, apparatus and system and decompression method, equipment and system, so as to suitable for common number the system of above application
According to compression situation and also there is better compressibility.
Data block includes one or more data values and can be arbitrary size.In department of computer science as depicted in fig. 1
In the embodiment of system, data value block can be alternatively referred to as:1) cache lines, caching group or caching sector, when data block is protected
When there are in the cache hierarchy in such computer system;2) cache lines, storage page or memory sectors, work as data
It is transmitted in the memory that block is saved in such computer system or in the communication device in such computer system
When.On the other hand, in the embodiment of the transmitting link road in communication network as depicted in figure 6, data block can also claim
For data packet, microplate, payload, header etc..
Variable-length compression based on entropy, such as huffman compression can be shown such as Fig. 2, Fig. 3, Fig. 4, Fig. 5 are discribed
It is answered in cache/memories/data transmission sub-system of example computer system or the situation of example communication link as depicted in figure 7
For the data value block as shown in the left sides Fig. 8.Described piece includes 8 data values, however it can be foregoing arbitrarily large
Small (section 0069).The example of the example collection of operating specification Huffman code word and huffman compression device such as Fig. 9 of the prior art
Embodiment, compression (or coding) described all data values in the block, forms on the right side of Fig. 8 discribed compressed piece.This
Outside, the compressed data value block of example variable-length for being depicted in the right side of Fig. 8 can be by the canonical Huffman of the prior art
The example embodiment of decompressor such as Figure 10 decompresses.
It requires to exist to be directed to using all possible data values of the one or more blocks of huffman coding compression and possibly be present at
The Huffman code word of all data values transmitted in computer system or in a network.It is reduced by decreasing value granularity possible
The quantity of data value is to handle a kind of mode of this problem.For example, being needed using 1 byte data value to be compressed with huffman coding
Up to 256 Huffman code words.However, when using finer grain value, compression efficiency reduces, because the code word generated is not
It is significantly more more dense than the data value of replacement.It improves compression efficiency and needs huffman compression coarse grain data value.The shortcomings of doing so
It must be that all probable values that possible access generate code word in advance to be, this mode make resource needed for storage huffman coding and
Metadata increases to the size forbidden.When compression is applied to cache/memories subsystem, transmission subsystem and communication network,
The current collection of data value used in being based only upon generate code word and when new value occurs (for example, when they are introduced into, create,
Access or transmission when) based on this it is new value regeneration coding alternative solution because due to sampling and code regeneration at and apply
Expense to those skilled in the art nor feasible solution.Particularly when compression is applied to caching and storage
When device subsystem, also mean must to storage it is all before compress data values unzip it and use it is newly encoded right
It carries out weight contracting, potentially introduces significant expense to system.
For the problem allow compress coarse granule value without keeping a large amount of first numbers using variable length huffman code
According to and need not to regenerate the feasible solution of the huffman coding be typically to allow to keep some data values uncompressed.
Keeping another unpressed motivation of some data values is, when (frequency of occurrences is small) several times occurs in data value, compared to holding
They are not compressed, and more metadata is needed to compress them, finally generate more area overheads and more time overheads
(due to compression and decompression).Value-frequency meter can be used for tracking most frequent value and their frequency of occurrences.
When data value block includes unpressed value, may keep uncompressed.The present inventor has contemplated two kinds can
The solution of energy, to allow the mixing of the compressed and unpressed data value in data block, it is assumed that the sequence of data value
It remains unchanged, as in the sequence in the block of original, uncompressed.In addition, the third of the present inventor's design is alternatively used
Solution to allow the permutatation to the original series of data value, and need not exceed by preceding when forming compressed piece
Any additional metadata except any metadata used in two kinds of solutions.
The example of the compressed data block according to the first solution is depicted on the right side of Figure 11, and to the left
Show the identical block of uncompressed form.Compressed data block include variable length huffman code bit sequence and
The metadata of bitmask (C- status masks) form occurred before the variable length huffman code.The variable-length is compiled
The bit sequence of code includes compressed and unpressed value.The mask include with the quantity for the data value for including in block as many
Position.The corresponding data value of each locator qualification in the mask is to be compressed (masked bits are such as 1) again without being compressed
(masked bits are such as 0).The position of masked bits is used to position the variable of (or counting) compressed and unpressed value in mask
Analog value in length sequences.
The block diagram for described compressed piece of the sample data compression device 1400 that can form Figure 11 is depicted in Figure 14.
The sample data compression device includes:The compressor reducer of 1420 form of variable length coding unit;Compress 1430 form of indicating unit
Detector;Compressive state register 1440 for storing C- status masks;And form compressed data block generator
Other logics 1440,1450 and 1460.As in the compressor reducer embodiment of Fig. 9, data compression device will be uncompressed
Data block 1410 as input, the unpressed data block be data value stream and include one or more data value v1,
V2 ..., vn, and the unpressed data block can from storage element 1405 obtain or from the number for coming from unpressed piece
It is obtained according to the extractor of value.However, the data value of unpressed data block 1410 is not provided only to variable length coding unit
1420, it is additionally provided to compression indicating unit 1430 and selector 1450.Variable length coding unit 1420 is similar to the pressure of Fig. 9
The variable length coding unit 920 of contracting device 900, the difference is that code table (CT) 1422 further includes effective in each table clause
Position (v) 1424.Value 1423, code word (CW) 1425 and the code length (cL) 1427 of each CT entries are similar to the compressor reducer 900 of Fig. 9
Value 923, CW 925 and cL 927.The positions v 1424 indicate the entry whether include value for being stored effective CW.
Indicating unit 1430 is compressed by by each incoming data value (candidate for compression) and matched entry
Value 1423 is compared (comparator 1434a) and whether there is the incoming data value in CT 1422 to check, and passes through inspection
The significance bit 1424 of (comparator 1434b) entry checks whether it is effective.If two comparisons are true (by unit 1438
Instruction), then there is effective code word for the candidate value for compression;Otherwise, which will save as uncompressed.It is indicated by compression
Unit or detector 1430 generate as testing result 1439 (for example, be 1 for using the value that the code word in CT is compressed,
The appropriate position in the C- status masks in compressive state register 1440 is marked on for the information 0) for unpressed value
It sets, simultaneous selection device 1450 makes selection appropriate also according to the information.
Therefore, compressed data block generator 1440-1460 is configured as:By pressing data value in unpressed data
The order occurred in block 1410 increases the compressed data value of 1425 form of variable length codeword (CW) or unpressed data
Value v1-vn, iteratively to build the bit sequence 1455 (that is, the bit sequence generated by variable length code) of variable length code,
It is above-mentioned to the compressed data value of variable length codeword form or increasing depending on detector 1430 for unpressed data value
Testing result 1439, while update accordingly in compressive state register 1440) in the compressive state of corresponding position cover
Code C- status masks.
(mean to have attempted to compress all block values) when block, which compresses, to be completed, from compressive state register 1440
It obtains C- status masks and is attached to the variable length including compressed value and unpressed value using connection unit 1460
It spends before the bit sequence 1455 of coding.The connection the result is that compressed piece 1490.Therefore, compressed data block generates
Device 1440-1460 is configured as:When all data values of unpressed data block 1410 have all been handled, pass through connector
1460 connection compression status mask C-state masks) and the bit sequence 1455 of variable length code generate compressed data
Block 1490.
Described compressed piece of the sample data decompression apparatus 1500 that can decompress Figure 11 is depicted in Figure 15
Block diagram.Decompressor 1000 of the data decompression device 1500 based on Figure 10 is built, and includes:Storage element 1505 is protected
(size of storage element 1510 is at least unpressed value length and maximum codeword length to the compressed data block of nonresident portion 1510
In the maximum);Codeword detection unit 1520 (similar to the codeword detection unit 1020 of the decompressor 1000 of Figure 10);Value inspection
Cable elements 1530 (similar to the value retrieval unit 1030 of the decompressor 1000 of Figure 10);And form decompressed data block
The additional logic 1540-1570 of generator.Therefore, codeword detection unit 1520 and value retrieval unit 1530 form decompression
Device.
Decompressed data block generator includes:Register 1550, for storing compressive state mask, C- states are covered
Code, the compressive state mask such as obtained from the extention of compressed data block 1510;Selector 1540 and 1570;And storage
Memory cell 1560.Decompressed data block generator reads C- status masks in each value decompression step, to determine to pass through
The current value of the data block 1510 of compression is compressed or unpressed, to determine correct data path.If C-
Status mask position is 1 (that is, current value is compressed), then the amount that will be shifted by selector 1540 is selected as of code word
The length matched, which is the output of codeword detection unit 1520, and (passing through selector 1570) will be attached to it
The value of remaining decompressed value is selected as the decoded value exported by value retrieval unit 1530.On the other hand, if C- states
Masked bits are 0 (that is, the value is unpressed), then selector 1540 will select the length of unpressed value, which has solid
Value granularity that measured length and being typically based on uses determines (being 32 for example, if symbol granularity is 4 bytes).From depositing
Storage unit 1505 reads unpressed value, and is selected using C- status masks position as control signal by selector 1570
It selects.Decompression continues, until all values of compressed data block 1510 are processed (that is, depending on C- status masks position
Unzip it or read), and form the decompressed data block 1590 of data value v1 ... vn.
Therefore, decompressed data block generator 1540-1570 is configured as:It detects in compressed data block 1510
Metadata (that is, C- status masks), wherein the metadata indicate include in compressed data block unpressed number
According to value, and based on the metadata detected, by self solving the decompressed data value of compressor reducer 1520,1530 in the future and coming
It is combined to generate decompressed data block 1590 from the unpressed data value of compressed data block 1510 so that generate
Order and the data value of data value v1 ... Vn of decompressed data block 1590 (such as scheme generating compressed data block
14 block 1490) data compression before the order that occurs in the unpressed data block (block 1410 of such as Figure 14) it is identical.
More specifically, therefore decompressed data block generator 1540-1570 is configured as from compressed data block
1510 obtain the compression of the position of instruction compressed data value and unpressed data value in compressed data block 1510
Status mask C- status masks.Decompressed data block generator 1540-1570 is additionally configured to generate by following manner
Decompressed data block 1590:The mode is i.e. for each data value in compressed data block 1510, based on compression
The place value of corresponding position in status mask C- status masks, control selections device 1570 selection from decompressor 1520,
1530 decompressed data value or the unpressed data value from compressed data block.
The exemplary process diagram for instantiating the compression method of the compression method structure based on Figure 25 in figure 27, can press
The block of contract drawing 11.As in the data compression device of Figure 14, the compression method by CT search block data value and
Whether they are associated with effective code word, to detect compressible and incompressible piece of data value, and the information coding are being protected
It is stored in the C- status masks before encoded value (that is, bit sequence of variable length code).
On the other hand, Figure 28 instantiates the exemplary flow of the decompression method of the structure of the decompression method based on Figure 26
Figure, can decompress compressed piece of Figure 11, this compressed piece includes unpressed value and compressed value and covering
The mixing of code, the mask positioned at compressed piece beginning, indicate which value is unpressed and which value is not uncompressed
's.The decompression method checks corresponding C- state entries in each decompression step.If it is 0, it is being extracted
The current value of contracting is actually unpressed, and can be from bit sequence (or the one portion for preserving compressed and unpressed value
Point) storage element in directly read the current value.The minimal size of storage element by maximum variable length codewords (mCL) length
The maximum between degree and the length (unc_val_length) of unpressed value limits;However, being still maximum variable length
The length of code word still determines the largest amount compared.As shown in the left hand path of Figure 28, displacement current bit sequence is read with abandoning
The shift amount (" length ") of the value taken is the length of unpressed value, and it is assigned to variable " length ".Otherwise, this is through pressure
The decompression of the value of contracting follows another path in Figure 28, and the length of matched code word is distributed to " length " substitutedly.
Although using the first example solution of fixed size mask before the compressed data value block of variable-length
It is of course possible to have its benefit, but it may have the disadvantage that the solution may be decreased compression efficiency.This be as
This, because it always increases the position of fixed quantity.If need not actually be covered in compression blocks without there is unpressed value
Code.So if the quantity of unpressed value is smaller, the mask of fixed size will inevitably increase area overhead.
Compressed piece of the alternative example of Figure 11 is depicted in Figure 12.In this example, if substitution ground is unique special
Different meaning code word be placed in each unpressed value before (that is, realizing compressed and unpressed data value in data block
Mixing second of solution, it is assumed that the sequence of data value remains unchanged, as original, uncompressed it is in the block), then may be used
To avoid mask completely.It is thus possible to improve compression efficiency.It is all in value-frequency meter by calculating or estimating not appearing in
The frequency of occurrences of these values, the unique code word can when code is generated with remaining variable length code (for example, huffman coding
(such as code word of 1625 form of code word (CW) in the code table (CT) 1622 of the variable length coding unit 1620 in Figure 16)) one
It rises and generates.For example, when one or more values evict from not by this value-frequency meter capture or from this table with for other more frequently
Value create space when, this can be calculated by increment additional counters.Those skilled in the art may be implemented to this its
He possible solution.Compared with the embodiment using fixed size mask before, with the frequency of occurrences of also use value
This alternative way distinguish unpressed value and compressed value in compressed piece and can cause in compression efficiency side
The more effective solution in face:The value that value-frequency tracker does not capture is more, then the total phase of unpressed value and the value occurred
Than more, the unique code word for being attached to unpressed value is narrower.On the other hand, the frequency that unpressed value occurs is smaller, attachment
Unique code word to each unpressed value is wider.Therefore, when code generates, all data in value-frequency meter are not appeared in
The frequency of occurrences of the value compared with the sum of the data value of appearance will influence the width of unique code word.It is attached to all unpressed values
The unique code word be referred to as from now on " unique unpressed identifier code word " (UUIC).
The sample data compression device 1600 for the compressed data block that can form Figure 12 is depicted in Figure 16
Block diagram.It includes:Unit 1605, the unit can be the reservoir such as used by above-mentioned data compression device embodiment or pass
In the extractor for the data value for coming from unpressed data block 1610;The compressor reducer of 1620 form of variable length coding unit;Pressure
The detector of 1630 form of contracting indicating unit;And it is made of UUIC attaching units 1640 and other logics 1650 compressed
Data block generator.Variable length coding unit 1420 of the unit 1620 and 1630 similar to the data compression device 1400 of Figure 14
With compression indicating unit 1430.The data compression device 1600 functions as follows.Data are extracted from unpressed data block 1610
Value, and checked whether and it can be compressed using variable length coding unit 1620 by compression indicating unit 1630.Such as
Fruit is not (that is, the data value will be saved with uncompressed form), then before UUIC being attached at the data value by unit 1640
Otherwise face encodes data value using unit 1620.Unit 1640 also includes storage element (for clarity not in Figure 16
In show), wherein the storage unit keep UUIC.When generating new UUIC (for example, when generating new huffman coding),
Update the storage element.By making correct choosing by compressing the selector 1650 that the testing result 1639 of indicating unit 1630 controls
It selects, and the correctly selection made further is attached to remaining warp that will be formed in the end of compressed data block 1690
The data value of compression.As above it has explained, compared with the data compression device 1400 in Figure 14, data compression device 1600 can be with
Improve compression efficiency.Data compression device 1600 is more than that the second advantage of data compression device 1400 can be dispensed with connector
1460.Therefore, it will need not be used to metadata being attached to compressed data block (referring to the C- status masks in Figure 14)
Individual hardware, and therefore data compression device 1600 can carry in terms of the hardware cost of reduction and increased compression speed
For further improving.
Therefore, compressed data block generator 1640-1650 is configurable to generate above-mentioned metadata as unique special
Meaning code word UUIC indicates detected following data values, in the data value, that is, unpressed data block 1610 cannot
The data value compressed by the compressor reducer 1620.In addition, compressed data block generator 1640-1650 is configured as generating
Unique particular meaning code word UUIC is attached to each unpressed data value when compressed data block 1690.
In addition, such as from clear above finding out, compressed data block generator 1640-1650 is configured as by following
Mode generates compressed data block 1690:The mode is by occurring in unpressed data block 1610 by data value
Order increases the compressed data value of variable length codeword form or the unpressed number for being attached with unique particular meaning code word
According to value, iteratively to build the bit sequence of variable length code, the above-mentioned compressed data value to variable length codeword form
Or it is attached with the testing result 1639 of the unpressed data value of unique particular meaning code word increased depending on detector 1630.
The sample data decompression apparatus for the compressed data block that can decompress Figure 12 is depicted in Figure 17 a
1700 block diagram.Data decompression device 1700 includes:Storage element 1705, storage unit point compressed data block 1710
(the maximum in the total length and maximum codeword length of the UUIC that the part size is at least attached to unpressed value);Code word
Detection unit 1720 (similar to the codeword detection unit 1020 of the decompressor 1000 of Figure 10);It is (similar to be worth retrieval unit 1730
In the value retrieval unit 1030 of the decompressor 1000 of Figure 10);UUIC detection units 1740;Shift amount computing unit 1770;It moves
Bit location 1750;Comparator unit 1760 and selector 1780.Codeword detection unit 1720 and value retrieval unit 1730 therefore shape
At decompressor, while unit 1740-1780 forms decompressed data block generator.
In the decompression of each data value, UUIC detection units 1740 will be with from the bit sequence being stored in unit 1705
One or more seat sequences of the be possible to width of first beginning are as input.Each width can be 1,2
Position, 3 etc., up to be equal to maximum UUIC width maximum width, similar to mCL it is such, can be in design, compiling, configuration
Or when operation depending on the realization (for example, with software or with hardware) of selected this data decompression device by the width
It is limited to particular value, such as Duan Luo [0015]Described in.Codeword detection unit 1720 using identical seat sequence or they
Superset.UUIC detection units 1740 attempt by using comparator 1744a, 1744b, 1744c etc. by one of these bit sequences with
Simultaneously use priority encoder 1748 generates " length of matched UUIC " to detect unpressed data value for candidate UUIC matchings.
Although the huffman coding version for each generating and using only exists the UUIC of a specific length, its length is not pre- prophet
Road;Therefore, it is necessary to more each seat sequences in equality comparator 1744a, 1744b, 1744c.However, only one compares
To be effective.Keep remaining invalid (for clarity by using the corresponding invalid signals being also updated when generating newly encoded
It is not shown in Figure 17 a).
Using comparator 1760, indicate whether to detect UUIC by " length of matched UUIC " that unit 1740 exports.
The output of the comparator is " UUIC detections mark "." length of matched UUIC " is used for:A) shift amount computing unit 1770,
In, (using adder 1774) is added into the length for the unpressed value being stored in storage element (for example, trigger) 1776
Degree is (that is, regular length and be typically based on during code generates the value granularity that uses to determine, for example, if symbol granularity is 4 words
Section, then be 32);And b) shift unit 1750, wherein (being carried from bit sequence " with the matched UUIC of unpressed value together "
Be derived from unit 1710) in remove UUIC so that only retain unpressed data value." UUIC detections mark " is used as going to selector
1772 and 1780 control signal 1762.The selector 1772 of shift amount computing unit 1770 determines the position sequence being stored in 1710
The shift amount of row so that matched part (code word for being followed by the unpressed data value of UUIC or being detected by unit 1720)
It is removed, and empty part is filled up by the next position of compressed sequence.On the other hand, selector 1780 is unpressed
It is selected between data value and the decoded value exported by value retrieval unit 1730.Selected value is with remaining through decompression
The data value of contracting links together.Continue to decompress, until all data values of compressed data block 1710 are all decompressed
And form the decompressed data block 1790 of data value v1 ... vn.
Therefore, decompressed data block generator 1740-1780, which is configured as detecting, is included in compressed data block
Unique particular meaning code word UUIC in 1710, and generate output control signal 1762.Decompressed data block generator
1740-1780 is additionally configured to remove from the associated unpressed data value for being attached with unique particular meaning code word and be examined
The unique particular meaning code word measured.
In addition, decompressed data block generator 1740-1780 be configured as generating by following manner it is decompressed
Data block 1790:The mode is for each data value in compressed data block 1710, based on control signal 1762
Control selections device 1780 selects decompressed data value from decompressor 1720,1730 or by that removes detected
The unpressed data value of the unique particular meaning code word arrived.
The block diagram of the alternative embodiments of the sample data decompression apparatus of Figure 17 a is depicted in Figure 17 b.In the number
According to comparator 1760 in decompression apparatus, is omitted, because UUIC detection units 1740 use comparator 1744a-c and or door
1748 rather than the priority encoder 1748 of Figure 17 a realize.As a result, UUIC detection units 1740 directly generate UUIC detections
Mark, rather than " length of matched UUIC ".Substitution ground, " length of matched UUIC " are for example touched by storage element 1776a
Device output is sent out, which is updated when generating new huffman coding every time so that it is unpressed corresponding to being attached to
The correct length of the UUIC of value.Remaining element and logic are similar to the unit and logic in the data decompression device of Figure 17 a.It should
Other alternative realizations of data decompression device embodiment can be realized by those skilled in the art.
The compression method of block that the compression method based on Figure 25 is built and that Figure 12 can be compressed is instantiated in Figure 29
Exemplary process diagram.The compression method carrys out the compressible of detection block using detection method identical with the compression method of Figure 27
With incompressible data value.However, it is also as described in the data compression device in Figure 16, by unpressed
The unpressed data value for the block that UUIC comes in the bit sequence of coding Variable length coding, the variable length code are attached before value
Bit sequence include compressed value and unpressed value.
Compressed piece of solution that instantiate the structure of the method based on Figure 26 in fig. 30 and that Figure 12 can be decompressed
The exemplary process diagram of compression method, this compressed piece includes compressed value and unpressed value, wherein not pressed each
It is equipped with UUIC before the value of contracting.With the seat sequence of first position alignment of the bit sequence being stored in storage element, with
One code word (FCW) is numerically compared, and is also compared with the unique code word (UUIC) for being attached to unpressed value.If
Described the latter compares generation matching, then unpressed value can be directly read from storage element, while read for abandoning
The shift amount (" length ") of the current bit sequence of value is the length that UUIC length adds unpressed value.Otherwise, this is compressed
The decompression of value follows another path in Figure 30, and the length of matched code word is assigned to " length ".Storage element
Minimal size is limited by the maximum in following the two, and one of both described is maximum variable length codewords (mCL)
Length, the other of both described is the length (unc_val_length) and UUIC length (UUIC_ of unpressed value
Length polymerization length).
Matching code word, (conventional code word as obtained by codeword detection unit 1020 (or 1720) is detected by UUIC
The UUIC of the gained of unit 1740) after, the compressed position sequence that is maintained in storage element 1010 (Figure 10) or 1710 (Figure 17)
The shift amount of row has arbitrary size.Arbitrary shift amount generally increases the complexity of shift unit realization.In addition, due to UUIC long
The sum of fixed size length of degree and unpressed value (after UUIC detections), maximum shift amount may be larger.Reduce displacement
Cost and possibly accelerate decompression a kind of method be that during compression, unpressed value is moved to compressed piece
End, and preserve them by the order opposite with the order occurred in the block of original, uncompressed.Figure 13 is instantiated with described new
Compressed piece of another embodiment of method compression is (that is, when forming compressed piece by rearranging data value
Original series realize the third solution of the mixing of compressed and unpressed data value in data block).In Figure 13
Right side, unpressed value 500 has been shifted to compressed piece of end;In order to the reconstructed value when decompressing block
Original order encodes them now for being attached at the UUIC of unpressed value front before.Therefore, UUIC replaces former
Value 500 in initial value order so that when it is detected by UUIC detection units, unpressed value can be obtained in the end of block.
The sample data compression device 1800 for the compressed data block that can form Figure 13 is depicted in Figure 18
Block diagram.It includes:Unit 1805, the unit can be the reservoir such as used by above-mentioned data compression device embodiment or pass
In the extractor for the data value for coming from unpressed data block 1810;The compressor reducer of 1820 form of variable length coding unit;Pressure
The detector of 1830 form of contracting indicating unit;And by UUIC storage elements 1840, selector 1850, be used for unpressed data
The compressed data block generator of storage element 1860 and connection unit 1870 composition of value.Unit 1820 and 1830 is distinguished
Variable length coding unit similar to above-mentioned data compression device 1400 and 1600 and compression indicating unit.However, working as data
When value is identified as incompressible by compression indicating unit 1830, the UUIC read from UUIC storages 1840 is selected by selector 1850
And it is attached to the bit sequence of variable length code.Unpressed data value is kept instead to be stored in for unpressed value
In storage element 1860.During compression, the storage element is by time occurred in unpressed data block 1810 with data value
The opposite order of sequence keeps unpressed data value.For example, the unpressed data value of first appearance (32, it is assumed that value grain
Degree is 4 bytes) it is saved in the rearmost position (right-most position in Figure 18) of storage element 1860.Storage element 1860 is write
Enabled (WE) is connected to the output of compression indicating unit 1830.When having been processed by all data values, unpressed data value
Sequence (if it include effective unpressed data value) be attached to variable length code bit sequence end and
Compressed data block 1890 is formed together.
Therefore, just as the compressed data block generator 1640-1650 described above with reference to Figure 16, in figure 18
Compressed data block generator 1840-1870 be configurable to generate the metadata as unique particular meaning code word
UUIC indicates the data value that cannot be compressed by compressor reducer 1820 in the unpressed data block 1810 detected.In addition, through pressure
The data block generator 1840-1870 of contracting is configured as:For in unpressed data block 1810 it is all it is detected not
The data value that can be compressed by compressor reducer 1820, by data value in unpressed data in the compressed data block 1890 of generation
The order occurred in block 1810 includes unique particular meaning code word rather than the data value that detects accordingly.Compressed data
Module generator 1840-1870 is additionally configured to:It cannot be by compressor reducer by detected in unpressed data block 1810
The data value of 1820 compressions is by opposite compared with the order that detected data value occurs in unpressed data block 1810
Order be attached at the end (i.e. tail end or front end) of the compressed data block 1890 generated.
In addition, can be clearly seen from above, compressed data block generator 1840-1870 is configured as through following sides
Formula generates compressed data block 1890):The mode is by occurring in unpressed data block 1810 by data value
Order increases the compressed data value of each of the variable length codeword form from compressor reducer 1820, variable iteratively to build
The bit sequence of length coding.Whenever detector 1830 detects cannot be pressed by compressor reducer 1820 in unpressed data block 1810
When the data value of contracting, unique particular meaning code word UUIC is added to the bit sequence of variable length code, and will be detected
Data value is stored in storage element 1860.Detected data value goes out by with data value in unpressed data block 1810
Existing order is stored in compared to opposite order in storage element 1860.When the institute for having been processed by unpressed data block 1810
When having data value, by making connector 1870 by the bit sequence of variable length code and the data preserved in storage element 1860
Value connection, to generate compressed data block 1890.
The example that compressed piece of the data decompression device 1900 that can decompress Figure 13 is depicted in Figure 19 is real
Apply the block diagram of mode.Data decompression device 1900 includes:Storage element 1905, storage unit point compressed data block (storage
The size of memory cell 1905 is at least the maximum in the total length and maximum codeword length of UUIC);Codeword detection unit 1920
(similar to the codeword detection unit 1020 of the decompressor 1000 of Figure 10);It is worth retrieval unit 1930 and (is similar to the decompression of Figure 10
The value retrieval unit 1030 of contracting device 1000);UUIC detection units 1940 (are similar to the data decompression device 1700 of Figure 17 a
UUIC detection units 1740);Unpressed value extraction unit 1960 and added logic.Added logic includes comparator unit
1970, arithmetical unit 1980 and selector 1950 and 1985.Therefore codeword detection unit 1920 and value retrieval unit 1930 are formed
Decompressor, while unit 1940-1985 forms decompressed data block generator.
Unpressed value extraction unit 1960 include selector unit 1968 and storage element 1964, the storage element press with
The order (block end to block starts) that the order of unpressed data value placement is opposite keeps the data compression device institute by Figure 18
The compression blocks obtained, it is opposite in the order of the end of data block and the order of appearance.Based on currently detected unpressed value
Sequence number, unpressed value extraction unit 1960 selects corresponding unpressed data value from storage element 1964, and passes through choosing
It selects device 1985 and sends it to remaining decompressed data value, above-mentioned unpressed value sequence number is by arithmetical unit 1980
(for example, incrementer) is directed to each non-zero (being verified by the comparator unit 1970) " matching exported from UUIC detection units 1940
UUIC length " measures gained.In this way, no longer unpressed data value is read from storage element 1910, such as the data decompression of Figure 17
As the 1500 of contracting equipment 1700 or Figure 15, while the maximum shift amount of compressed bit sequence is reduced to UUIC length and maximum
The maximum in code word size.If there is no unpressed data value in the end of compressed data block, will not select not
The output of the value extraction unit 1960 of compression, because UUIC will not be detected.
Therefore, decompressed data block generator 1940-1985, which is configured as detecting, is included in compressed data block
Unique particular meaning code word UUIC in 1910, and generate output control signal 1962.Decompressed data block generator
1940-1985 is additionally configured to generate decompressed data block 1990 by following manner:The mode is i.e. for compressed
Data block 1910 each data value and based on control signal 1962, control selections device 1985 exists by compressed data value
Decompressed data value of the order selection from decompressor 1920,1930 occurred in compressed data block 1910, or
Person is by order selection opposite compared with the order that unpressed data value occurs in compressed data block 1910 from warp
The unpressed data value of the data block 1910 of compression.In addition, decompressed data block generator 1940-1985 is configured as
At least part of copy for storing compressed data block 1910 in reverse order in storage element 1964, wherein compressed
The tail end of data block be stored in the beginning of storage element 1964.Decompressed data block generator 1940-1985 also by with
It is set to:Whenever detecting that unique particular meaning code word UUIC is included in compressed data block 1910, make unpressed number
According to value 1980 increment of counter, and using unpressed data value counter 1980 as direction depositing in storage element 1964
The pointer that storage space is set, to provide unpressed data value to selector 1985.
The compression method of block that the compression method based on Figure 25 is built and that Figure 13 can be compressed is instantiated in Figure 31
Exemplary process diagram.The compression method carrys out the compressible of detection block using detection method identical with the compression method of Figure 27
Data value and incompressible data value.However, its using UUIC by raw value time ordered pair include compressed value and
The unpressed data value of block in the bit sequence of the variable length code of unpressed value is encoded, and will be practical uncompressed
Value compressed piece of end is placed on opposite appearance order (value that the last one value occurred occurs to first).
Figure 32 instantiates the exemplary process diagram of the decompression method of the structure of the decompression method based on Figure 26, can solve
Compress Figure 13 includes compressed piece of the mixing of compressed value and unpressed value, in this is compressed piece, each
Unpressed value is replaced by raw value order by UUIC, and actual unpressed value is preserved by opposite appearance order
In the end of block.This method is similar to the decompression method of Figure 30, matches UUIC by trial to detect unpressed value.It is different
Place is, when detecting UUIC, from compressed piece of end being stored in the second storage element (" compression " array)
Directly read unpressed value.Then the unpressed value read is abandoned from the second storage element described in this (or makes array
Index delta).In addition, UUIC length is assigned to " length ", it is somebody's turn to do the shifting that " length " is previously stored the bit sequence in storage element
Position amount.Otherwise, the decompression of compressed value follows another path in Figure 32, and the length of matched code word is assigned to
" length ".Therewith unlike the first two embodiment, the minimal size of storage element is by maximum variable length codewords (mCL)
The maximum between length and UUIC length limits.
When data compression applications in the cache/memories subsystem or transfer network sub system of computer system or are answered
With in a communication network when, another situation usually occurred is the data value block filled with identical common data value.Most commonly
Situation be identical common data value be value 0, therefore this piece is referred to as sky block.The variable-length as huffman coding
Coding is limited to maximum compression ratio, because code word can only replacement data value under the best circumstances.It is retouched on the left of Figure 20
In unpressed piece of the embodiment of another 8 data values painted, each value is value 0, is using huffman coding simultaneously
And assumed value 0 is so frequent so that in the case of being encoded with 1, compressed piece includes 8 (each values 1),
It is discribed on the right side of Figure 20.Another alternative for compressing this piece is that entire value block is replaced with one, for example, as schemed
Discribed position 1 in 21.However, in the compression scenario, if fruit block includes the value in addition to 0, then it will be by above-mentioned data
One of compression device compresses.However, it is necessary to be encoded to additional information so that can will be compressed by data decompression device
Described piece of form is distinguished with empty compression blocks.Exemplary method is placed before the bit sequence of other variable length codes
Position, such as position 0, to indicate that it is non-empty block.Those skilled in the art can also find other methods.
The frame for described compressed piece of the sample data compression device that can form Figure 21 and Figure 22 is depicted in Figure 23
Figure.Its data compression device 1600 based on Figure 16, however disclosed all above-mentioned data compression devices in that patent, such as
Equipment 1400,1600 and 1800 can be used as basis by those skilled in the art.Compared with the data compression device 1600 of Figure 16,
New unit in the data compression device 2300 of Figure 23 is sky block detection unit 2360 (in the left side of Figure 23), in multiple comparisons
Whether more all block data values are equal to identical common data value 0 in device 2364a, 2364b etc..It, will be empty if it is true
Block indicating bit (that is, by being exported with door 2368) is set as " 1 ", and correspondingly control selections device 2370 to allow sky block indicating bit structure
At compressed data block 2390.Otherwise, empty block indicating bit is arranged to " 0 ", and correspondingly control selections device 2370 to allow
Empty block indicating positions forms compressed data block 2390 together before the rest part of the bit sequence of variable length code,
As it is above-mentioned for different embodiment descriptions as.Those skilled in the art can change empty block detection unit 2360, with
Compression includes the other kinds of unpressed data block for the identical common data value for not being value 0.
More generally useful, data compression device (such as 2300) may include any data compression device as described above
1400,1600 or 1800, and common value detection unit (such as unit 2360) is also comprised, it is configured to work as unpressed data
It is detected when all data values of block (such as 2310) common block data value (such as value 0) having the same.Such data
Compression device is configured as:When detecting all data values of unpressed data block common block data value all having the same
When, it only includes indicating the particular meaning data value of detected common block data value without including above-mentioned compressed number to generate
According to the compressed data block (such as 2390) of the combination of value, unpressed data value and metadata, data compression device on the contrary
It is configured as:When not detecting all data values of unpressed data block common block data value having the same, generate
Include the compressed data block of the value different from particular meaning data value, after the value different from particular meaning data value
It is followed by the combination of above-mentioned compressed data value, unpressed data value and metadata.
The data of the compressed data block as described in Figure 21 and Figure 22 is discribed can be decompressed by being instantiated in Figure 24 a
The block diagram of the example embodiment of decompression apparatus 2400, and data decompression of the data decompression device based on Figure 17 a
Equipment 1700 is built.However, all above-mentioned data decompression devices disclosed in this disclosure, such as equipment 1500,
1700 and 1900, basis can be used as by those skilled in the art.With the 1710 storage unit lease making pressure of wherein storage element of Figure 17 a
The data decompression device 1700 of the data block 1710 of contracting is compared, and in the new data decompression apparatus 2400 of Figure 24 a, storage is single
Member includes:Subelement 2418 is stored, which only keeps first of compressed data block 2410;And storage
Unit 2414, the storing sub-units preserve the compressed data block in part as in the previous 2410.In the data decompression device
And only at the beginning of decompressing compressed piece, check whether bit preamble (being stored in storage subelement 2418) is non-zero
(or " 1 ").Pass through multiple multiplexers 2495 if it is all values in true, decompressed block 2490 (on the right side of Figure 24)
Apportioning cost 0;Otherwise (if the bit preamble of compressed data block 2410 is " 0 "), follows the data decompression such as Figure 17 a
Remaining step described in contracting equipment 1700 decompresses the data block.
More generally useful, data decompression device (such as 2400) may include any data decompression device as described above
1500,1700 or 1900, and particular meaning data value detector (such as 2450) is also comprised, it is configured in compressed number
According to particular meaning data value is detected at the beginning of block (such as 2410), which indicates that common block data value is (all
Such as value 0), this data decompression device is configured as when detecting particular meaning data value by being filled out with common block data value
Fill decompressed data block to generate the decompressed data block (such as 2490), on the contrary data decompression device by with
It is set to when particular meaning data value is not detected as decompressed for generating described in any of above embodiment
Data block.
The alternative block diagram of the embodiment of the data decompression device is depicted in Figure 24 b, wherein if it find that
Compressed piece of bit preamble is non-zero, then decompressed data value block is reset to 0, it is assumed that decompressed block is in conduct
It is reconstructed in the storage element of flip-flop array.Other alternative realizations of the data decompression device can be by people in the art
Member realizes.When any other value it is very universal appear in identical data value block when, the data decompression may be implemented
The alternative embodiments of equipment.
Figure 33 instantiates the exemplary process diagram of the compression method of the structure of the compression method based on Figure 29, and the compression side
Method also checks for whether all pieces of data values are zero so that it compresses institute as depicted in figure 21 with more efficient way
State block (being known as empty block);Otherwise, it is compressed as depicted in figure 22.This is completed by following manner:Institute
It states mode and checks whether all values are equal to value 0 and correspondingly set empty block indicator to " 1 " (empty block refers to compressing the when of starting
Show that symbol constitutes compressed piece in itself);Otherwise, it sets " 0 " empty block indicator to, and uses the compression side for including Figure 29
Compression blocks are carried out in the alternative path of method, but empty block indicator is placed on to compressed piece of beginning.In the compression method
Alternative embodiments in, can be using including general while the alternative path compression of compression method of Figure 29 is each worth
Each value is compared with value 0.If they are equal to value 0, by block boil down to Null blocks.Other implementations of the compression method
Mode can attempt the other values that either statically or dynamically compression ratio 0 more generally useful occurs.
Figure 34 instantiates the exemplary process diagram of the decompression method of the structure of the decompression method based on Figure 30, and it is logical
Cross and check whether first of block be equal to " 1 ", can detection block whether be compressed to sky block.In this case, decompressed
Block all data values all be assigned value be 0;Otherwise, it is solved using the alternative path including method illustrated by Figure 30
Compression blocks.The other embodiment of the decompression method can either statically or dynamically include ratio 0 more generally useful occur its
He is worth.
In all the above embodiments of data compression device and/or data decompression device, those skilled in the art
Delay cell such as trigger can be inserted so that the compression of the data value of a block or/and one compressed piece of value
Decompression can pipeline as multiple stages, be gulped down with reducing clock period time and increasing processing (compression or/and decompress)
The amount of spitting.
Furthermore, it is possible to by those skilled in the art and according to technology commonly known per se, by the number for compressing multiple pieces simultaneously
According to being worth and/or decompress multiple compressed piece of data values, come make data compression device disclosed in present disclosure and/or
The alternative embodiments parallelization of data decompression device.In this case it is necessary to correspondingly by those skilled in the art
Change decompressor design.
Corresponding data compression device 1400,1600,1800,2300 in Figure 14,16,18 and 23 can be for example with hardware
It realizes, for example, being embodied as digital circuit in integrated circuits, special equipment (such as Memory Controller), programmable processing
Equipment (such as central processing unit (CPU) or digital signal processor (DSP), field programmable gate array (FPGA) etc..At this
The function of corresponding data compression method described in disclosure can be for example by appropriately configured corresponding data compression device
1400, it 1600,1800,2300 executes, or as the corresponding computer program product including code command, which works as
When by general purpose processing device such as CPU or DSP load and executing, cause the execution of correlation method.
Corresponding data decompression apparatus 1500,1700,1900,2400 in Figure 15,17,19,24a and 24b can example
Such as with hardware realization, for example, be embodied as digital circuit in integrated circuits, special equipment (such as Memory Controller), can
Programmed process equipment (such as central processing unit (CPU) or digital signal processor (DSP), field programmable gate array
(FPGA) etc..The function of the corresponding data decompression method described in this disclosure can be for example by appropriately configured corresponding
Data decompression device 1500,1700,1900,2400 executes, or as the corresponding computer program production including code command
Product, the code command are loaded when by general purpose processing device such as CPU or DSP (such as any processing unit P1 ... Pn of Fig. 1-5)
When with executing, cause the execution of correlation method.
Example embodiment disclosed herein proposes the method for following data block compression and decompressions, equipment and is
System, so that more compactly storage or transmission information, the data block compression and decompression are:Computer system caching/deposit
In reservoir subsystem or for the cache/memories subsystem data block compression and decompression, in the number of computer system
According in transmission subsystem or for the data transmission sub-system data block compression and decompression or in a communication network
Or the data block compression and decompression for the communication network.
Figure 35 instantiates general-purpose system 3500 according to the present invention.The system includes one or more memories 3510, number
According to compression device 3520 (such as, for example, any data compression device 1400,1600,1800,2300) and data decompression device
3530 (such as, for example, any data decompression device 1500,1700,1900,2400).Advantageously, system 3500 is computer
System (any computer system 100-500 of such as Fig. 1-5), and one or more of memories 3510 are one or more
A buffer memory (such as, any buffer memory L1-L3 of Fig. 1-5), one or more random access memory (are such as schemed
Any memory 130-530 of 1-5) or one or more auxiliary memories.Alternatively, system 3500 is data communication system
System (such as, the communication network 600 of Fig. 6-7,700), wherein one or more of memories 3510 can be communicated with data
The associated data buffer of transmitting node and receiving node (such as, the transmitter 610,710 of Fig. 6-7 and reception in system
Device 620,720).
Although using example embodiment describe the present invention for the use of, they are not limited to disclosed embodiment party
Formula, and they cover the alternative embodiments that can be realized by those skilled in the art.
It should be noted that define alternative inventive aspect in the clause of following number, be specifically directed to Figure 11,
14 to shown in 15 and needle description thereof related but the design that is not claimed at present.
I. a kind of data compression device, for that will include the unpressed data block boil down to warp of one or more data values
The data block of compression, the data compression device include:
Compressor reducer, the compressor reducer are configured as the corresponding variable-length of data value boil down to of unpressed data block
Code word;
Detector, the detector be configured as detecting unpressed data are in the block cannot be by the compressor compresses
Data value;And
Compressed data block generator, the compressed data block generator are configured as by will be following combined
Generate compressed data block:
Compressed data value, the compressed data value are in the block by compressor reducer pressure with unpressed data
The form of the corresponding variable length codeword of data value of contracting;
Unpressed data value, the unpressed data value be in unpressed data it is in the block it is detected not
It can be by the form of the data value of compressor compresses;And
Metadata, the metadata indicate unpressed data value.
II. the data compression device according to clause I, wherein compressed data block generator includes at least one
Selector, which is response to the testing result of detector, and is configured as by combining one
Variable length codeword, detected data value and metadata in a or multiple steps generate compressed data block.
III. the data compression device according to any one of aforementioned clause, wherein the detector be configured as by
Cannot be detected as by the data value of the compressor compresses in unpressed data block it is following in it is one or more:
The data value being not present in the code table of compressor reducer,
It is present in code table but lacks in the code table of compressor reducer the data value of code word,
It is present in code table, there is code word in code table but be indicated as invalid data value in the code table of compressor reducer.
IV. the data compression device according to the aforementioned clause of any one,
Wherein, compressed data block generator includes compressive state register, for storing compressive state mask form
The metadata, to indicate the position of compressed data compressed data value and unpressed data value in the block;With
And
Wherein, be configured as will be from the compressive state mask packet of compressive state register for compressed data block generator
It includes in the data block of generation.
V. the data compression device according to clause IV, compressed data block generator include connector, wherein warp
The data block generator of compression is configured as:
Increase the compressed of variable length codeword form by the order occurred in unpressed data block by data value
Data value or unpressed data value, iteratively to build the bit sequence of variable length code, while updating accordingly and pressing
In the compressive state mask of corresponding position, the above-mentioned compressed data value to variable length codeword form in contracting status register
Or the testing result of unpressed data value increased depending on detector;And
When all data values of unpressed data block are processed, compression status mask is linked by connector
Compressed data block is generated with the bit sequence of variable length code.
VI. the data compression device according to the aforementioned clause of any one further includes common value detection unit, the common value
Detection unit is configured as detecting all data values common block data value when having the same of unpressed data block,
Wherein, data compression device is configured as:When detect unpressed data block all data values have it is identical
Common block data value when, generate only include the detected common block data value of instruction particular meaning data value without including
The compressed data block of the combination of above-mentioned compressed data value, unpressed data value and metadata;And
Wherein, data compression device is configured as:When not detecting that all data values of unpressed data block have
When identical common block data value, generation includes the value different from the particular meaning data value and in this and the particular meaning
The warp of the combination of above-mentioned compressed data value, unpressed data value and metadata is followed by after the different value of data value
The data block of compression.
VII. a kind of data decompression device includes one or more data by compressed data block decompression for being
The decompressed data block of value, the data decompression device include:
Decompressor, the decompressor are configured as the variable length codeword of compressed data block decompression being condensed to pair
The decompressed data value answered;And
Decompressed data block generator, the decompressed data block generator are configured as:
In compressed data metadata in the block, it is in the block that the metadata instruction is included in compressed data for detection
Unpressed data value;And
Based on detected metadata, the decompressed data block is generated by following manner:The mode is
Decompressed data value of the combination from decompressor and the unpressed data value from compressed data block so that institute
The order of the data value of the decompressed data block generated is with the data value in the data pressure for generating compressed data block
The order occurred in unpressed data block before contracting is identical.
VIII. the data decompression device according to clause VII, wherein decompressed data block generator by with
It is set to:
The metadata of compressive state mask form is obtained from the compressed data block, which refers to
Show the position of compressed data compressed data value and unpressed data value in the block;And
Decompressed data block is generated by following manner:The mode is i.e. in the block each for compressed data
Data value, based on the place value of the corresponding position in compressive state mask, control selections device selects the warp from decompressor
The data value of decompression or unpressed data value from compressed data block.
IX. the data decompression device according to any one of clause VII-VIII further includes particular meaning data value
Detector, the particular meaning data value detector are configured as the detection instruction common block at the beginning of compressed data block
The particular meaning data value of data value,
Wherein, data decompression device is configured as:When detecting particular meaning data value, by with common block data
Value fills decompressed data block to generate the decompressed data block;And
Wherein, data decompression device is configured as:When not detecting particular meaning data value, such as clause VII-
Decompressed data block is generated described in any one of VIII.
X. a kind of data compression method, for that will include the unpressed data block boil down to warp of one or more data values
The data block of compression, the data compression method include:
By the corresponding variable length codeword of data value boil down to of unpressed data block;
Detecting that unpressed data are in the block cannot be by the data value of the compressor compresses;And
By combined generating compressed data blocks by following:
Compressed data value, the compressed data value are in the block by compressor reducer pressure with unpressed data
The form of the corresponding variable length codeword of data value of contracting;
Unpressed data value, the unpressed data value be in unpressed data it is in the block it is detected not
It can be by the form of the data value of the compressor compresses;And
Metadata, the metadata indicate unpressed data value.
The data compression method may include any functional character according to the data compression device of clause I-VI.
XI. a kind of uncompressing data includes one or more data by compressed data block decompression for being
The decompressed data block of value, the uncompressing data include:
The variable length codeword decompression of compressed data block is condensed to corresponding decompressed data value;
In compressed data metadata in the block, it is in the block that the metadata instruction is included in compressed data for detection
Unpressed data value;And
Based on the metadata detected, decompressed data block is generated by following manner:The mode combines
Self solve the decompressed data value of compressor reducer and the unpressed data value from compressed data block so that the warp of generation
The order of the data value of the data block of decompression and the data value before the data compression for generating compressed data block
The order occurred in unpressed data block is identical.
The uncompressing data may include any functional character according to the data compression device of clause VII-IX.
XII. a kind of system, the system comprises one or more memories, according to described in any one of clause I-VI
Data compression device and the data decompression device according to any one of clause VII-IX.
XIII. the system according to clause XII, wherein the system is computer system, and wherein, one
Or multiple memories carry out the freely following group constituted:
Buffer memory,
Random access memory, and
Auxilary unit.
XIV. the system according to clause XII, wherein system is data communication system, and wherein, it is one or
Multiple memories are data buffers.
XV. a kind of computer program product, the computer program product include code command, the code command when by
Processing equipment loads and causes when executing the execution of the method according to clause X.
XVI. a kind of computer program product, the computer program product include code command, and the code command is worked as
Cause the execution of the method according to clause XI when being loaded and executed by processing equipment.
Claims (34)
1. a kind of data compression device (1600;1800;2300), being used for will be including one or more data value (v1-vn) not
The data block (1610 of compression;1810;2310) the compressed data block of boil down to (1690;1890;2390), the data compression
Equipment includes:
Compressor reducer (1620;1820;2320), the compressor reducer is configured as compressing the data value of the unpressed data block
For corresponding variable length codeword (1625;1825;2325);
Detector (1630;1830;2330), the detector be configured as detecting the unpressed data are in the block cannot be by
The data value of the compressor compresses;And
Compressed data block generator (1640-1650;1840-1870;2340-2370), the compressed data block life
It grows up to be a useful person and is configured as by being combined to generate the compressed data block by following:
Compressed data value, the compressed data value are in the block by the compression with the unpressed data
The form of the corresponding variable length codeword of data value of device compression;
Unpressed data value, the unpressed data value be in the unpressed data it is in the block it is detected not
It can be by the form of the data value of the compressor compresses;And
Metadata (UUIC), the metadata indicate the unpressed data value, wherein the metadata is unique special
Meaning code word (UUIC).
2. data compression device (1600 according to claim 1;1800;2300), wherein unique particular meaning code
Word (UUIC) is when code generates and the compressor reducer (1620;1820;2320) the variable length codeword (1625;1825;
2325) code word generated together.
3. data compression device (1600 according to claim 2;1800;2300), wherein unique particular meaning code
Word (UUIC) is generated by following manner:The mode calculates when code generates or estimates not being presented on value-frequency meter
In all data values the frequency of occurrences, their frequency of occurrences compared with the total number of the data value of appearance influence described in only
The width of one particular meaning code word (UUIC).
4. data compression device (1600 according to any one of claim 1-3;1800;2300), wherein described through pressure
Data block generator (the 1640-1650 of contracting;1840-1870;2340-2370) it is configured as:
When generating the compressed data block (1690;1890;2390) when, unique particular meaning code word (UUIC) is attached
It is connected to each unpressed data value.
5. data compression device (1600) according to claim 4, wherein the compressed data block generator
(1640-1650) is configured as generating the compressed data block (1690) by following manner:The mode is i.e. by pressing
The order that data value occurs in the unpressed data block (1610) increases the compressed of the variable length codeword form
Data value or be attached with the unpressed data value of unique particular meaning code word, iteratively to build the position of variable length code
Sequence, above-mentioned compressed data value to variable length codeword form or is attached with the unpressed of unique particular meaning code word
The testing result (1639) of data value increased depending on the detector (1630).
6. data compression device (1800) according to any one of claim 1-3, wherein the compressed data block
Generator (1840-1870) is configured as:
For in the unpressed data block (1810) it is all it is detected cannot be by the data of the compressor compresses
Value, by unique particular meaning code word rather than corresponding detected data value presses the data value described uncompressed
Data block (1610) in occur order be included in the compressed data block (1890) generated;And
By detected in the unpressed data block (1810) cannot be pressed by the data value of the compressor compresses with
The order that detected data value occurs in the unpressed data block (1810) is attached at institute compared to opposite order
The end of the compressed data block (1890) generated.
7. data compression device (1800) according to claim 6, the compressed data block generator (1840-
1870) include storage element (1860) and connector (1870), wherein the compressed data block generator is configured as leading to
Cross following generation compressed data blocks (1890):
Increased from the compressor reducer by the order occurred in the unpressed data block (1810) by data value
(1820) the compressed data value of each of variable length codeword form iteratively builds the bit sequence of variable length code;
Whenever the detector (1830) detect in the unpressed data block (1810) cannot be by the compressor reducer
(1820) when the data value compressed, unique particular meaning code word (UUIC) is added to the position sequence of the variable length code
Arrange and simultaneously detected data value be stored in the storage element (1860), wherein detected data value press with it is described
The order that data value occurs in the unpressed data block (1810) is stored in the storage element compared to opposite order
(1860) in;And
When all data values of the unpressed data block (1810) are processed, even by the connector (1870)
The data value tied the bit sequence of the variable length code and preserved in the storage element (1860), it is described through pressure to generate
The data block (1890) of contracting.
8. the data compression device (2300) according to any one preceding claims, further includes common value detection unit
(2360), the common value detection unit be configured as detecting the unpressed data block (2310) all data values when
Common block data value having the same,
Wherein, the data compression device is configured as:When all data for detecting the unpressed data block (2310)
When value all has the identical common block data value, it only includes that detected the special of common block data value of instruction contains to generate
Adopted data value is described compressed without the combination including above-mentioned compressed data value, unpressed data value and metadata
Data block (2390);And
Wherein, the data compression device is configured as:When not detecting all of the unpressed data block (2310)
When data value all has the identical common block data value, generation include the value different from the particular meaning data value and
Be followed by after the value different from the particular meaning data value above-mentioned compressed data value, unpressed data value and
The compressed data block (2390) of the combination of metadata.
9. the data compression device (1600 according to any one preceding claims;1800;2300), wherein described through pressure
Data block generator (the 1640-1650 of contracting;1840-1870;2340-2370) include at least one selector (1650;1850-
1870;2350), at least one selector is to the detector (1630;1830;2330) testing result (1639;
1839;2339) for response and be configured as by combine one or more steps in the variable length codeword, institute
The data value that detects and the metadata generate compressed data block (1690;1890;2390).
10. the data compression device (1600 according to any one preceding claims;1800;2300), wherein the detection
Device (1630;1830;2330) be configured as by the unpressed data are in the block cannot be by the data of the compressor compresses
Value be detected as it is following in it is one or more:
It is not present in the compressor reducer (1620;1820;2320) code table (1622;1822;2322) data value in,
It is present in the code table but lacks code word (1625 in the code table of the compressor reducer;1825;2325) data
Value,
It is present in the code table, there is code word (1625 in the code table;1825;2325) but in the institute of the compressor reducer
It states and is indicated as invalid (1624 in code table;1824;2324) data value.
11. a kind of data decompression device (1700;1900;2400) it, is used for compressed data block (1710;1910;
2410) decompression be condensed to include one or more data values (v1-vn) decompressed data block (1790;1990;2490), institute
Stating data decompression device includes:
Decompressor (1720-1730;1920-1930;2420-2430), be configured as will be described compressed for the decompressor
Data block variable length codeword (1625;1825;2325) decompression is condensed to corresponding decompressed data value;And
Decompressed data block generator (1740-1780;1940-1985;2440-2487), the decompressed data
Module generator is configured as:
The metadata (UUIC) in the compressed data block (1710) is detected, the metadata is unique particular meaning code
Word (UUIC), instruction are included in the compressed data unpressed data value in the block;And
Based on detected metadata, the decompressed data block is generated by following manner:The mode combines
Decompressed data value from the decompressor and the unpressed data value from the compressed data block, make
The order and the data value for obtaining the data value of the decompressed data block generated are generating the compressed data block
Data compression before in unpressed data block (1610;1810;2310) order occurred in is identical.
12. data decompression device (1700) according to claim 11, wherein the decompressed data block generates
Device (1740-1780) is configured as:
Detection is included in unique particular meaning code word (UUIC) in the compressed data block (1710) and generates result control
Signal (1762) processed;
It is removed from the associated unpressed data value for being attached with detected unique particular meaning code word described unique
Particular meaning code word;And
The decompressed data block (1790) is generated by following manner:The mode is directed to the compressed data
Each data value in block (1710) comes from the decompression based on control signal (1762) the control selections device (1780) selection
The decompressed data value of contracting device (1720,1730) has been that removes detected unique particular meaning code words not
The data value of compression.
13. data decompression device (1900) according to claim 11, wherein the decompressed data block generates
Device (1940-1985) is configured as:
Detection is included in unique particular meaning code word (UUIC) in the compressed data block (1910) and generates knot
Fruit controls signal (1962);And
The decompressed data block (1990) is generated by following manner:The mode is directed to the compressed data
Each data value in block (1910) and it is based on the control signal (1962), control selections device (1985) is by compressed number
Warp of the order selection from the decompressor (1920,1930) occurred in the compressed data block (1910) according to value
The data value of decompression, or by the order phase occurred in the compressed data block (1910) with unpressed data value
Than the opposite unpressed data value of the order selection from the compressed data block (1910).
14. data decompression device (1900) according to claim 13, wherein the decompressed data block generates
Device (1940-1985) is configured as:
At least part of copy of the compressed data block (1910) is stored in storage element in the reverse order
(1964) in, the tail end of the compressed data block is stored in the beginning of the storage element;
Whenever detecting that unique particular meaning code word (UUIC) is included in the compressed data block (1910), make not press
Data value counter (1980) increment of contracting;And
Using the unpressed data value counter (1980) as the storage location being directed toward in the storage element (1964)
Pointer, provide unpressed data value to the selector (1985).
15. the data decompression device (2400) according to any one of claim 11-14, further includes particular meaning data
It is worth detector (2450), the particular meaning data value detector is configured as opening in compressed data block (2410)
The particular meaning data value of detection instruction common block data value at head,
Wherein, the data decompression device is configured as:When detecting the particular meaning data value, by with the public affairs
Block data value fills decompressed data block (2490) to generate the decompressed data block altogether;And
Wherein, the data decompression device is configured as:When not detecting the particular meaning data value, according to right
It is required that the generation decompressed data block described in any one of 11-14.
16. a kind of data compression method, for that will include the unpressed data block of one or more data values (v1-vn)
(1610;1810;2310) the compressed data block of boil down to (1690;1890;2390), the data compression method includes:
By the corresponding variable length codeword of the data value boil down to of the unpressed data block (1625;1825;2325);
Detecting that the unpressed data are in the block cannot compressed data value;And
By being combined to generate the compressed data block by following:
Compressed data value, the compressed data value are in the block by the compression with the unpressed data
The form of the corresponding variable length codeword of data value of device compression;
Unpressed data value, the unpressed data value be in the unpressed data it is in the block it is detected not
It can be by the form of the data value of the compressor compresses;And
Metadata (UUIC), the metadata indicate the unpressed data value, wherein the metadata is unique special
Meaning code word (UUIC).
17. data compression method according to claim 16, wherein make unique particular meaning code word (UUIC) in code
When generation with the variable length codeword (1625;1825;2325) it generates together.
18. data compression method according to claim 17, wherein generate unique particular meaning by following manner
Code word (UUIC):The mode is that all data values not being presented in value-frequency meter are calculated or estimated when code generates
The frequency of occurrences, their frequency of occurrences compared with the total number of the data value of appearance influence unique particular meaning code word
(UUIC) width.
19. according to the data compression method described in any one of claim 16-18, further include:
When generating the compressed data block (1690;1890;2390) when, unique particular meaning code word (UUIC) is attached
It is connected to each unpressed data value.
20. data compression method according to claim 19, further includes:
The compressed data block (1690) is generated by following manner:The mode by data value described i.e. by not pressed
The order occurred in the data block (1610) of contracting increases the compressed data value of the variable length codeword form or is attached with
The unpressed data value of unique particular meaning code word, it is above-mentioned to variable iteratively to build the bit sequence of variable length code
The compressed data value of length codewords form or the increasing for unpressed data value for being attached with unique particular meaning code word take
Certainly in the testing result of detecting step (1639).
21. according to the data compression method described in any one of claim 16-18, further include:
For in the unpressed data block (1810) it is all it is detected cannot be by the data of the compressor compresses
Value, by unique particular meaning code word rather than corresponding detected data value presses the data value described uncompressed
Data block (1610) in occur order be included in the compressed data block (1890) generated;And
By detected in the unpressed data block (1810) cannot be pressed by the data value of the compressor compresses with
The order that detected data value occurs in the unpressed data block (1810) is attached at institute compared to opposite order
The end of the compressed data block (1890) generated.
22. data compression method according to claim 21 further includes generating the compressed data block by following
(1890):
Increase its variable length codeword form by the order occurred in the unpressed data block (1810) by data value
Each of compressed data value, iteratively build variable length code bit sequence;
Whenever detect in the unpressed data block (1810) cannot compressed data value when, will be described unique special
Meaning code word (UUIC) is added to the bit sequence of the variable length code and preserves detected data value, wherein being detected
The data value arrived is by opposite order compared with the order that the data value occurs in the unpressed data block (1810)
It preserves;And
When all data values of the unpressed data block (1810) are processed, compiled by linking the variable-length
The bit sequence of code and the data value preserved, to generate the compressed data block (1890).
Further include the detection unpressed data 23. according to the data compression method described in any one of claim 16-22
All data values common block data value when having the same of block (2310),
Wherein, when detecting that all data values of the unpressed data block (2310) all have the identical public block number
When according to value, generate only include the detected common block data value of instruction particular meaning data value without including above-mentioned through pressure
The compressed data block (2390) of the combination of the data value of contracting, unpressed data value and metadata;And
Wherein, when do not detect the unpressed data block (2310) all data values have the identical common block
When data value, generation includes the value different from the particular meaning data value and different with the particular meaning data value at this
The compressed data block of the combination of above-mentioned compressed data value, unpressed data value and metadata is followed by after value
(2390)。
24. according to the data compression method described in any one of claim 16-23, wherein by the unpressed data block
In cannot compressed data value be detected as it is following in it is one or more:
It is not present in code table (1622;1822;2322) data value in,
It is present in the code table but lacks code word (1625 in the code table;1825;2325) data value,
It is present in the code table, there is code word (1625 in the code table;1825;2325) but in the code table referred to
It is shown as invalid (1424;1624;1824;2324) data value.
25. a kind of uncompressing data is used for compressed data block (1710;1910;2410) decompression is condensed to include one
The decompressed data block (1790 of a or multiple data values (v1-vn);1990;2490), the uncompressing data packet
It includes:
By the variable length codeword (1625 of the compressed data block;1825;2325) decompression is condensed to corresponding decompressed
Data value;
In the compressed data metadata in the block (UUIC), the metadata is unique particular meaning code word for detection
(UUIC), instruction is included in the compressed data unpressed data value in the block;And
Based on detected metadata, the decompressed data block is generated by following manner:The mode combines
Decompressed data value from decompressor and the unpressed data value from the compressed data block so that institute
The order of the data value of the decompressed data block generated is with the data value in the number for generating the compressed data block
According to before compression in the unpressed data block of unpressed data block (1610;1810;2310) order occurred in is identical.
26. uncompressing data according to claim 25, further includes:
Detection is included in unique particular meaning code word (UUIC) in the compressed data block (1710) and generates knot
Fruit controls signal (1762);
It is removed from the associated unpressed data value for being attached with detected unique particular meaning code word described unique
Particular meaning code word;And
The decompressed data block (1790) is generated by following manner:The mode is directed to the compressed data
Each data value in block (1710) is simultaneously based on the control signal (1762), selects decompressed data value or is moved for it
In addition to the unpressed data value of detected unique particular meaning code word.
27. uncompressing data according to claim 25, further includes:
Detection is included in unique particular meaning code word (UUIC) in the compressed data block (1910) and generates knot
Fruit controls signal (1962);And
The decompressed data block (1990) is generated by following manner:The mode is directed to the compressed data
Each data value in block (1910) and it is based on the control signal (1962), by compressed data value described compressed
Data block (1910) in the order that occurs select decompressed data value, or by with unpressed data value in the warp
The order occurred in the data block (1910) of compression comes from the compressed data block (1910) compared to opposite order selection
The unpressed data value.
28. uncompressing data according to claim 27, further includes:
At least part of copy of the compressed data block (1910) is stored in storage element in the reverse order
(1964) in, the tail end of the compressed data block is stored in the beginning of the storage element;
Whenever detecting that unique particular meaning code word (UUIC) is included in the compressed data block (1910), make
Unpressed data value counter (1980) increment;And
Using the unpressed data value counter (1980) as the storage location being directed toward in the storage element (1964)
Pointer, provide unpressed data value to selection step.
29. according to the uncompressing data described in any one of claim 25-28, further include:
The particular meaning data value of detection instruction common block data value at the beginning of the compressed data block (2410),
Wherein, when detecting the particular meaning data value, by filling decompressed number with the common block data value
The decompressed data block is generated according to block (2490);And
Wherein, when not detecting the particular meaning data value, according to the generation described in any one of claim 25-28
The decompressed data block.
30. a kind of system (3500), including:One or more memories (3510);According to any one of claim 1-10 institutes
The data compression device (3520 stated;1600;1800;2300);And the data according to any one of claim 11-15
Decompression apparatus (3530;1700;1900;2400).
31. system (3500) according to claim 30, wherein the system is computer system (100;200;300;
400;500), and wherein, one or more of memories (3510) carry out the group of freely following compositions:
Buffer memory (L1-L3),
Random access memory (130;230;330;430;530), and
Secondary storage device.
32. system (1900) according to claim 30, wherein the system is data communication system (600;700), and
And wherein, one or more of memories (3510) are data buffers.
33. a kind of computer program product, the computer program product includes code command, and the code command is by handling
Equipment loads and causes the execution of the method according to any one of claim 16-24 when executing.
34. a kind of computer program product, the computer program product includes code command, and the code command is by handling
Equipment loads and causes the execution of the method according to any one of claim 25-29 when executing.
Applications Claiming Priority (5)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| SE1650119-9 | 2016-01-29 | ||
| SE1650119 | 2016-01-29 | ||
| SE1650767-5 | 2016-06-01 | ||
| SE1650767A SE540178C2 (en) | 2016-01-29 | 2016-06-01 | Methods, devices and systems for compressing and decompressing data |
| PCT/SE2017/050074 WO2017131578A1 (en) | 2016-01-29 | 2017-01-27 | Methods, devices and systems for compressing and decompressing data |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN108702160A true CN108702160A (en) | 2018-10-23 |
| CN108702160B CN108702160B (en) | 2022-05-17 |
Family
ID=59398468
Family Applications (2)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201780015262.7A Active CN108702160B (en) | 2016-01-29 | 2017-01-27 | Method, apparatus and system for compressing and decompressing data |
| CN201780015236.4A Active CN108886367B (en) | 2016-01-29 | 2017-01-30 | Method, apparatus and system for compressing and decompressing data |
Family Applications After (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201780015236.4A Active CN108886367B (en) | 2016-01-29 | 2017-01-30 | Method, apparatus and system for compressing and decompressing data |
Country Status (2)
| Country | Link |
|---|---|
| CN (2) | CN108702160B (en) |
| WO (2) | WO2017131578A1 (en) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111985636A (en) * | 2019-05-21 | 2020-11-24 | 辉达公司 | Data Structure Compression Technology for Artificial Neural Network |
| CN113228653A (en) * | 2018-12-21 | 2021-08-06 | 零点科技公司 | Method, apparatus and system for efficient compression and decompression for higher throughput |
| CN113517893A (en) * | 2020-04-10 | 2021-10-19 | 苹果公司 | Enabling mask compression of data on a communication bus |
| WO2024149300A1 (en) * | 2023-01-12 | 2024-07-18 | 华为技术有限公司 | Data compression method, apparatus and system, data decompression method, apparatus and system, and medium |
Families Citing this family (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2016186563A1 (en) | 2015-05-21 | 2016-11-24 | Zeropoint Technologies Ab | Methods, devices and systems for hybrid data compression and decompression |
| SE540178C2 (en) | 2016-01-29 | 2018-04-24 | Zeropoint Tech Ab | Methods, devices and systems for compressing and decompressing data |
| RU2729509C1 (en) * | 2019-12-23 | 2020-08-07 | федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский ядерный университет МИФИ" (НИЯУ МИФИ) | Device for unpacking data |
| US11362672B2 (en) * | 2020-05-08 | 2022-06-14 | Qualcomm Incorporated | Inline decompression |
| CN111814009B (en) * | 2020-06-28 | 2022-03-01 | 四川长虹电器股份有限公司 | Mode matching method based on search engine retrieval information |
| SE544557C2 (en) * | 2020-12-01 | 2022-07-12 | Zeropoint Tech Ab | Systems, methods and devices for exploiting value similarity in computer memories |
| JP7305609B2 (en) * | 2020-12-16 | 2023-07-10 | 株式会社日立製作所 | A device that processes received data |
Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20060139188A1 (en) * | 2004-12-28 | 2006-06-29 | Casio Electronics Manufacturing Co., Ltd. | Data compression/decompression device and data compression/decompression method |
| CN101715132A (en) * | 2008-09-30 | 2010-05-26 | 雅马哈株式会社 | Lossless compression-encoding device |
| US20100195724A1 (en) * | 2007-10-18 | 2010-08-05 | Fujitsu Limited | Video compression encoding/decompression device, video compression encoding/decompression program and video generation/output device |
| CN103563255A (en) * | 2011-04-11 | 2014-02-05 | 马维尔国际贸易有限公司 | Method for compression and real-time decompression of executable code |
| CN103891150A (en) * | 2011-10-01 | 2014-06-25 | 英特尔公司 | Compression format for high bandwidth dictionary compression |
Family Cites Families (14)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5784631A (en) * | 1992-06-30 | 1998-07-21 | Discovision Associates | Huffman decoder |
| CN1157653C (en) * | 1994-04-22 | 2004-07-14 | 索尼公司 | Device and method for transmitting data, and device and method for recording data |
| US6272453B1 (en) * | 1998-01-05 | 2001-08-07 | Trw Inc. | Concurrent legacy and native code execution techniques |
| US6492991B1 (en) * | 1998-08-28 | 2002-12-10 | Ati International Srl | Method and apparatus for controlling compressed Z information in a video graphics system |
| US6653954B2 (en) * | 2001-11-07 | 2003-11-25 | International Business Machines Corporation | System and method for efficient data compression |
| US7043077B2 (en) * | 2001-11-07 | 2006-05-09 | International Business Machines Corporation | System and method for efficient compression of raster image data |
| JP3870171B2 (en) * | 2003-03-11 | 2007-01-17 | キヤノン株式会社 | ENCODING METHOD, ENCODING DEVICE, COMPUTER PROGRAM, AND COMPUTER-READABLE STORAGE MEDIUM |
| US7202872B2 (en) * | 2003-10-29 | 2007-04-10 | Via Technologies, Inc. | Apparatus for compressing data in a bit stream or bit pattern |
| CN1599258B (en) * | 2004-06-25 | 2010-05-12 | 浙江大学 | A Coding Method Applicable to Infrared Control Signals in Various Formats |
| JP2009005091A (en) * | 2007-06-21 | 2009-01-08 | Canon Inc | Image forming apparatus, control method of the same, program and storage medium |
| US9088296B2 (en) * | 2011-12-29 | 2015-07-21 | Microsoft Technology Licensing, Llc | Variable length coding and decoding using counters |
| US8497788B1 (en) * | 2012-04-25 | 2013-07-30 | Pure Storage Inc. | Efficient techniques for aligned fixed-length compression |
| JP6021498B2 (en) * | 2012-08-01 | 2016-11-09 | 任天堂株式会社 | Data compression apparatus, data compression program, data compression system, data compression method, data decompression apparatus, data compression / decompression system, and data structure of compressed data |
| CN105264779B (en) * | 2013-01-22 | 2019-06-07 | 阿尔特拉公司 | Data compression and decompression using SIMD instruction |
-
2017
- 2017-01-27 WO PCT/SE2017/050074 patent/WO2017131578A1/en active Application Filing
- 2017-01-27 CN CN201780015262.7A patent/CN108702160B/en active Active
- 2017-01-30 CN CN201780015236.4A patent/CN108886367B/en active Active
- 2017-01-30 WO PCT/SE2017/050078 patent/WO2017131579A1/en active Application Filing
Patent Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20060139188A1 (en) * | 2004-12-28 | 2006-06-29 | Casio Electronics Manufacturing Co., Ltd. | Data compression/decompression device and data compression/decompression method |
| US20100195724A1 (en) * | 2007-10-18 | 2010-08-05 | Fujitsu Limited | Video compression encoding/decompression device, video compression encoding/decompression program and video generation/output device |
| CN101715132A (en) * | 2008-09-30 | 2010-05-26 | 雅马哈株式会社 | Lossless compression-encoding device |
| CN103563255A (en) * | 2011-04-11 | 2014-02-05 | 马维尔国际贸易有限公司 | Method for compression and real-time decompression of executable code |
| CN103891150A (en) * | 2011-10-01 | 2014-06-25 | 英特尔公司 | Compression format for high bandwidth dictionary compression |
Cited By (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN113228653A (en) * | 2018-12-21 | 2021-08-06 | 零点科技公司 | Method, apparatus and system for efficient compression and decompression for higher throughput |
| CN113228653B (en) * | 2018-12-21 | 2024-03-15 | 零点科技公司 | Methods, apparatus and systems for efficient compression and decompression for higher throughput |
| CN111985636A (en) * | 2019-05-21 | 2020-11-24 | 辉达公司 | Data Structure Compression Technology for Artificial Neural Network |
| CN113517893A (en) * | 2020-04-10 | 2021-10-19 | 苹果公司 | Enabling mask compression of data on a communication bus |
| US11303478B2 (en) | 2020-04-10 | 2022-04-12 | Apple Inc. | Data-enable mask compression on a communication bus |
| CN113517893B (en) * | 2020-04-10 | 2022-09-06 | 苹果公司 | Enabling mask compression of data on a communication bus |
| WO2024149300A1 (en) * | 2023-01-12 | 2024-07-18 | 华为技术有限公司 | Data compression method, apparatus and system, data decompression method, apparatus and system, and medium |
Also Published As
| Publication number | Publication date |
|---|---|
| WO2017131579A1 (en) | 2017-08-03 |
| WO2017131578A1 (en) | 2017-08-03 |
| CN108886367B (en) | 2022-01-11 |
| CN108886367A (en) | 2018-11-23 |
| CN108702160B (en) | 2022-05-17 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN108702160A (en) | Method, apparatus and system for compression and decompression data | |
| EP3304746B1 (en) | Methods, devices and systems for hybrid data compression and decompression | |
| US10846218B2 (en) | Methods, devices and systems for compressing and decompressing data | |
| EP3298695B1 (en) | Methods, devices and systems for semantic-value data compression and decompression | |
| US10771090B2 (en) | Data processing unit having hardware-based range encoding and decoding | |
| US11188338B2 (en) | Context value retrieval prior to or parallel with expansion of previous symbol for context-decoding in range decoder | |
| US10922026B2 (en) | Data processing unit having hardware-based range encoding and decoding | |
| JPH09121168A (en) | Compressor, compressing method, expander and context serving device | |
| CN112968706B (en) | Data compression method, FPGA chip and FPGA online upgrading method | |
| CN114697672A (en) | A neural network quantization compression method and system based on run-length all-zero coding | |
| Burtscher et al. | pFPC: A parallel compressor for floating-point data | |
| EP4066121A1 (en) | Pattern-based cache block compression | |
| CN108259515A (en) | A kind of lossless source compression method suitable for transmission link under Bandwidth-Constrained | |
| Munasa et al. | Single Dictionary based Cache Compression and Decompression Algorithm | |
| JPH03209923A (en) | Data compressing system | |
| Morales-Sandoval et al. | On the design and implementation of an FPGA-based lossless data compressor | |
| CN114697673A (en) | A neural network quantization compression method and system based on inter-stream data shuffling | |
| Twelves et al. | JPEG2000 Arithmetic Encoding on the StarCore SC140 | |
| Deepa et al. | Microprocessor cache compressor design using P-Match algorithm | |
| Albonesi et al. | Portable and Transparent Message Compression in MPI Libraries to Improve the Performance and Scalability of Parallel Applications |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |