CN103975533A - High bandwidth decompression of variable length encoded data streams - Google Patents
High bandwidth decompression of variable length encoded data streams Download PDFInfo
- Publication number
- CN103975533A CN103975533A CN201280060474.4A CN201280060474A CN103975533A CN 103975533 A CN103975533 A CN 103975533A CN 201280060474 A CN201280060474 A CN 201280060474A CN 103975533 A CN103975533 A CN 103975533A
- Authority
- CN
- China
- Prior art keywords
- data
- line
- token
- symbol
- byte
- 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
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L69/00—Network arrangements, protocols or services independent of the application payload and not provided for in the other groups of this subclass
- H04L69/04—Protocols for data compression, e.g. ROHC
-
- 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/3084—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method
-
- 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
- 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/60—General implementation details not specific to a particular type of compression
- H03M7/6005—Decoder aspects
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Computer Security & Cryptography (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
- Compression Or Coding Systems Of Tv Signals (AREA)
Abstract
Mechanisms are provided for decoding a variable length encoded data stream. A decoder of a data processing system receives an input line of data. The input line of data is a portion of the variable length encoded data stream. The decoder determines an amount of bit spill over of the input line of data onto a next input line of data. The decoder aligns the input line of data to begin at a symbol boundary based on the determined amount of bit spill over. The decoder tokenizes the aligned input line of data to generate a set of tokens. Each token corresponds to an encoded symbol in the aligned next input line of data. The decoder generates an output word of data based on the set of tokens. The output word of data corresponds to a word of data in the original set of data.
Description
Technical field
The application relates generally to a kind of improved data processing equipment and method and relates more specifically to the mechanism of the high bandwidth decompress(ion) of the data flow for variable length code is provided.
Background technology
Lossless data compression is the class data compression algorithm allowing from the accurate legacy data of data reconstruction of compression.Term " can't harm " with only allowing the data compression technique formation that damages being similar to exchange better compression speed for of rebuilding legacy data and contrasts.In the many dissimilar application that comprises ZIP compressed format, GZIP in the computing system based on Unix operating system compression etc., use lossless data compression.
One class lossless data compression is the 5th, the DEFLATE data compression algorithm of describing in 051, No. 745 United States Patent (USP).DEFLATE data compression algorithm utilizes the combination of Lempel-ZivLZ77 compression algorithm and huffman coding.LZ77 compression is following sliding window compress technique, in this sliding window compress technique, for data area (or window), storage is not yet detected as the literal byte of the string of repetition, and when repeated strings detected in scope (or window) time, the pointer of previously stored literal byte is pointed in storage as an alternative.Pointer is included in length in scope (or window) and distance backward.Then huffman coding is applied to literal byte and the pointer in LZ77 algorithm.Huffman coding is provided for using the ability of variable length code to literal byte and pointer coding.Can in Publication about Document, find the more information about DEFLATE data compression algorithm: Deutsch, " DEFLATECompressed Data Format Specification; " version1.3, Network WorkingGroup RFC1951, May1996.
Summary of the invention
In an exemplary embodiments, provide a kind of method of decoding for the data flow to variable length code in data handling system.The method comprises that wherein Data In-Line is a part for the data flow of variable length code by the decoder reception Data In-Line of data handling system.The method also comprises by decoder specified data input line overflows quantity for symbols to the position on next Data In-Line.In addition, the method comprises that quantity aligned data input line is overflowed to start at character boundary in the position of determining based on from past data input line by decoder.In addition, the method comprises that the Data In-Line of being aimed at by decoder tokenization is to generate token set, and wherein each token is corresponding to the symbol of the variable length code in next input line of aiming at.In addition, the method comprises that by decoder, based on token set generated data output word, wherein data output word is corresponding to the concentrated data word of legacy data.
In other exemplary embodiments, provide a kind of comprise computer can with or the computer program of computer-readable recording medium, computer can with or computer-readable recording medium there is computer-readable program.Computer-readable program makes more than computing equipment execution about various operations and combination in the operation of method exemplary embodiments general introduction in the time being performed on computing equipment.
In another exemplary embodiments, provide a kind of systems/devices.This systems/devices can comprise one or more processor and be coupled to the memory of one or more processor.Memory can comprise instruction, and instruction makes various operations and the combination in one or more operation of more than processor execution summarizing about method exemplary embodiments in the time being carried out by one or more processor.
These and other feature of the present invention and advantage by the following specifically describes of example embodiment of the present invention, described or will become according to the following specifically describes by those of ordinary skill in the art clear.
Brief description of the drawings
By in the time reading by reference to the accompanying drawings by understand best the present invention and preferred implementation and more objects and advantage with reference to the following specifically describes of exemplary embodiments.
Fig. 1 has described the graphic representation of example distribution formula data handling system, can in this distributed data processing system, implement exemplary embodiments aspect;
Fig. 2 is the block diagram of sample data treatment system, can in this data handling system, implement exemplary embodiments aspect;
Fig. 3 is according to the example block diagram of decoder/decompression machine framework of an exemplary embodiments;
Fig. 4 is the exemplary plot that illustrates multiple input lines, these input lines illustrate data a part position from an input line overflowing to another input line;
Fig. 5 illustrates according to the alignment logic of the decoder/decompression machine of an exemplary embodiments in the example block diagram to punctual operation of determining input line;
Fig. 6 is according to the example block diagram of the token device logic flow waterline of an exemplary embodiments;
Fig. 7 is according to the example block diagram of the output maker logic of an exemplary embodiments; And
Fig. 8 is the flow chart of having summarized according to the exemplary operations of the data flow for the treatment of variable length code of an exemplary embodiments.
Embodiment
Exemplary embodiments is provided for the mechanism of the high bandwidth decompress(ion) of the data flow that variable length code is provided.The mechanism of exemplary embodiments compensates the symbol of the variable length code in the data flow of the compression of for example, introducing in the compress technique by utilizing (, variable length huffman code or other variable length code technology).The mechanism of the symbol of this variable length code of the compensation that utilizes exemplary embodiments in coded data stream, can carry out the parallel decompress(ion) to the data block in data flow, and this increases throughput and the speed of separating press operation.As a result of, providing can be to the high speed decompress(ion) mechanism of the data flow operations of variable length code.
Person of ordinary skill in the field knows, the present invention can be implemented as system, method or computer program.Therefore, various aspects of the present invention can specific implementation be following form, that is: hardware implementation mode, implement software mode (comprising firmware, resident software, microcode etc.) completely completely, or the execution mode of hardware and software aspect combination, can be referred to as " circuit ", " module " or " system " here.In addition, in certain embodiments, various aspects of the present invention can also be embodied as the form of the computer program in any one or more computer-readable mediums, comprise the program code that computer can be used in this computer-readable medium.
Can adopt the combination in any of one or more computer-readable mediums.Computer-readable medium can be computer-readable signal media or computer-readable recording medium.Computer-readable recording medium for example may be-but not limited to-electricity, magnetic, optical, electrical magnetic, infrared ray or semi-conductive system, device, device or any above combination.The example more specifically (non exhaustive list) of computer-readable recording medium comprises: have the electrical connection, portable computer diskette, hard disk, random access memory (RAM), read-only memory (ROM), erasable type programmable read only memory (EPROM or flash memory), optical fiber, Portable, compact dish read-only memory (CD-ROM), light storage device, magnetic memory device of one or more wires or the combination of above-mentioned any appropriate.In presents, computer-readable recording medium can be any comprising or stored program tangible medium, and this program can be used or be combined with it by instruction execution system, device or device.
Computer-readable signal media can be included in the data-signal of propagating in base band or as a carrier wave part, has wherein carried computer-readable program code.The combination of electromagnetic signal that the data-signal of this propagation can adopt various ways, comprises---but being not limited to---, light signal or above-mentioned any appropriate.Computer-readable signal media can also be any computer-readable medium beyond computer-readable recording medium, and this computer-readable medium can send, propagates or transmit the program for being used or be combined with it by instruction execution system, device or device.
The computer code comprising on computer-readable medium can be with any suitable medium transmission, comprises that---but being not limited to---is wireless, wired, optical cable, radio frequency (RF) etc., or the combination of above-mentioned any appropriate.
Can write the computer program code for carrying out the present invention's operation with the combination in any of one or more programming languages, described programming language comprises object-oriented programming language-such as JavaTM, SmalltalkTM, C++ etc., also comprises conventional process type programming language-such as " C " language or similar programming language.Program code can fully be carried out, partly on subscriber computer, carries out, carry out or on remote computer or server, carry out completely as an independently software kit execution, part part on subscriber computer on remote computer on subscriber computer.In the situation that relates to remote computer, remote computer can be by the network of any kind---comprise local area network (LAN) (LAN) or wide area network (WAN)-be connected to subscriber computer, or, can be connected to outer computer (for example utilizing ISP to pass through Internet connection).
Below with reference to describing the present invention according to flow chart and/or the block diagram of the method for illustrated embodiments of the invention, device (system) and computer program.Should be appreciated that the combination of each square frame in each square frame of flow chart and/or block diagram and flow chart and/or block diagram, can be realized by computer program instructions.These computer program instructions can offer the processor of all-purpose computer, special-purpose computer or other programmable data processing unit, thereby produce a kind of machine, make these computer program instructions in the time that the processor by computer or other programmable data processing unit is carried out, produced the device of the function/action specifying in the one or more square frames in realization flow figure and/or block diagram.
Also these computer program instructions can be stored in computer-readable medium, these instructions make computer, other programmable data processing unit or other equipment with ad hoc fashion work, thereby the instruction being stored in computer-readable medium just produces the manufacture (article of manufacture) of the instruction of the function/action specifying in the one or more square frames that comprise in realization flow figure and/or block diagram.
Also computer program instructions can be loaded on computer, other programmable data processing unit or miscellaneous equipment, make to carry out sequence of operations step on computer, other programmable data processing unit or miscellaneous equipment, to produce computer implemented process, thereby make the instruction of carrying out on computer or other programmable device that the process of the function/action specifying in the one or more square frames in realization flow figure and/or block diagram is provided.
Flow chart in accompanying drawing and block diagram have shown according to architectural framework in the cards, function and the operation of the system of multiple embodiment of the present invention, method and computer program product.In this, the each square frame in flow chart or block diagram can represent a part for module, program segment or a code, and a part for described module, program segment or code comprises one or more for realizing the executable instruction of logic function of regulation.Also it should be noted that what the function marking in square frame also can be marked to be different from accompanying drawing occurs in sequence in some realization as an alternative.For example, in fact two continuous square frames can be carried out substantially concurrently, and they also can be carried out by contrary order sometimes, and this determines according to related function.Also be noted that, the combination of the square frame in each square frame and block diagram and/or flow chart in block diagram and/or flow chart, can realize by the special hardware based system of the function putting rules into practice or action, or can realize with the combination of specialized hardware and computer instruction.
Therefore, can in many dissimilar data processing circumstances, utilize exemplary embodiments.In order to be provided for describing the concrete unit of exemplary embodiments and the context of function.Below provide Fig. 1 and Fig. 2 as the example context that wherein can implement the aspect of exemplary embodiments.Should understand, Fig. 1 and Fig. 2 are only for example and being not intended as is concluded or imply about any restriction of environment that wherein can implement aspect of the present invention or embodiment.Many amendments of the environment to describing be can carry out and Spirit Essence of the present invention and scope do not departed from.
Fig. 1 has described the graphic representation of example distribution formula data handling system, can in this distributed data processing system, implement exemplary embodiments aspect.Distributed data processing system 100 can comprise the network that can implement therein the computer of the aspect of exemplary embodiments.Distributed data processing system 100 comprises at least one network 102, and network 102 is the media that are used to provide the communication link between various device and the computer linking together in distributed data processing system 100.Networking 102 can comprise connection, such as wired, wireless communication link or optical fiber cable.
In the example of describing, server 104 is connected to network 102 together with memory cell 108 with server 106.In addition, client 110,112 and 114 is also connected to network 102.These clients 110,112 and 114 can be for example personal computer, network computer etc.In the example of describing, server 104 provides data to client 110,112 and 114, such as boot files, operation system image and application.Client 110,112 and 114 is the client of server 104 in the example of describing.Distributed data processing system 100 can comprise unshowned Additional servers, client and miscellaneous equipment.
In the example of describing, distributed data processing system 100 is the internets with network 102, and network 102 representative is used TCP/IP (TCP/IP) protocol suite to collect with the network that intercoms mutually and the whole world of gateway.It is the trunk of the high-speed data communication link between main node or the host computer forming in the thousands of business by route data and message, government, education and other computer system at the center of internet.Certainly, distributed data processing system 100 also may be implemented as and comprises many dissimilar networks, as such as in-house network, local area network (LAN) (LAN), wide area network (WAN) etc.Say as above, Fig. 1 is intended to as example instead of as the architectural limitation for different embodiments of the invention, and therefore the discrete cell shown in Fig. 1 should not be regarded as about the environment that can implement therein exemplary embodiments of the present invention restricted.
Fig. 2 is the block diagram of sample data treatment system, can in this data handling system, implement exemplary embodiments aspect.Data handling system 200 is that enforcement can be positioned at computer wherein for computer usable code or the instruction of the process of exemplary embodiments of the present invention, such as the example of the client 10 in Fig. 1.
In the example of describing, data handling system 200 is used hub architecture, and this hub architecture comprises north bridge and Memory Controller hub (NB/MCH) 202 and south bridge and I/O (I/O) controller hub (SB/ICH) 204.Processing unit 206, main storage 208 and graphic process unit 210 are connected to NB/MCH202.Graphic process unit 210 can be connected to NB/MCH202 by Accelerated Graphics Port (AGP).
In the example of describing, local area network (LAN) (LAN) adapter 212 is connected to SB/ICH204.Audio frequency adapter 216, keyboard and mouse adapter 220, modulator-demodulator 222, read-only memory (ROM) 224, hard drive (HDD) 226, CD-ROM driving 230, USB (USB) port and other communication port 232 and PCI/PCIe equipment 234 are connected to SB/ICH204 by bus 238 and bus 240.PCI/PCIe equipment can for example comprise Ethernet Adaptation Unit, accessory card and the PC card for notebook.PCI uses card bus control unit, and PCIe does not use.ROM224 can be for example flash memory basic input/output (BIOS).
HDD226 and CD-ROM drive 230 to be connected to SB/ICH204 by bus 240.HDD226 and CD-ROM drive 230 can for example use integrated drive electronics (IDE) or serial advanced technology attachment (SATA) interface.Super I/O (SIO) equipment 236 can be connected to SB/ICH204.
Operating system is moved on processing unit 206.Operating system is coordinated the various parts in the data handling system 200 in Fig. 2 and the control of various parts is provided.As client, operating system can be commercially available operating system, such as
oO programing system is (such as Java
tMprograming system) can binding operation system move and provide the Java from carrying out in data handling system 200
tMprogram or application calling operating system.
As server, data handling system 200 can be for example the senior mutual execution of operation
operating system or
operating system
eServer
tM computer system.Data handling system 200 can be symmetric multiprocessor (SMP) system that comprises the multiple processors in processing unit 206.Alternatively, can use single processor system.
Be positioned at memory device (such as HDD226) above and can load for being carried out by processing unit 206 to main storage 208 for the instruction of operating system, OO programing system and application or program.Can use the computer usable program code that can be arranged in memory (as such as main storage 208, ROM224) or for example be positioned at one or more ancillary equipment 226 and 230 to carry out by processing unit 206 for the process of exemplary embodiments of the present invention.
Bus system (such as bus 238 or 240 as shown in Figure 2) can be made up of one or more bus.Certainly, can implement bus system with the communication structure of any type or framework, this communication system or framework provide the data transmission between the different parts or the equipment that are attached to this structure or framework.Communication unit (such as modulator-demodulator 222 or the network adapter 212 of Fig. 2) can comprise one or more equipment for transmission and reception data.Memory can be for example main storage 208, ROM224 or such as the high-speed cache of finding in the NB/MHC202 in Fig. 2.
Those of ordinary skill in the art will understand, and the hardware in Fig. 1 and Fig. 2 can change according to implementation.The hardware of describing the hardware of describing in Fig. 1 and Fig. 2 or in replacement Fig. 1 and Fig. 2, can use other internal hardware or ancillary equipment, such as flash memory, equivalent nonvolatile memory or disc drives etc.The process of exemplary embodiments also can be applied to the multi-processor data process system except previously mentioned smp system and not depart from Spirit Essence of the present invention and scope.
In addition, data handling system 200 can adopt the form of any data handling system in multiple different pieces of information treatment systems, and these data handling systems comprise client computing device, server computing device, flat computer, laptop computer, phone or other communication equipment, personal digital assistant (PDA) etc.In some exemplary example, data handling system 200 can be portable computing equipment, to this portable computing equipment configuration flash memory so that the nonvolatile memory of the data that generate for storage operation system file and/or user to be for example provided.In fact, data handling system 200 can be any known or later exploitation data handling system and without architectural limitation.
Referring again to Fig. 1 and Fig. 2, data processing or computing equipment/system (, such as the server 106 in Fig. 1, can implement this data processing or computing equipment/system for example for the data handling system of Fig. 2 or there is different units configuration and composition but can be implemented as follows the data handling system of the machine-processed another type of the exemplary embodiments that literary composition describes) receive the coded data stream of the part of the data of the compression with variable-length, these parts need to be decoded into the legacy data of coded data stream, thereby make data processing/computing system can process legacy data.Coded data stream can be by one or more other data handling system/computing equipment transmission of being coupled in other data handling system/computing equipment (being for example server 104, client 110,112 and/or 114 etc. in this example) of server 106.Can be via the data flow of one or more network 102 transfer encodings.Certainly, can be similarly and any other scene of utilizing the data flow of wherein variable length code to be received by machine-processed data handling system/computing equipment of implementing exemplary embodiments together with the mechanism of exemplary embodiments.That is to say, the data flow of only having variable length code is received and then operated subsequently by the mechanism of exemplary embodiments as will be described below at data handling system/computing equipment, how to data handling system/computing equipment transmission of variable length coded data stream or just inessential to data handling system/computing equipment transmission of variable length coded data stream under which kind of circumstances.
The data stream encoding of the encryption algorithm that can use any known or later exploitation to variable length code, this encryption algorithm generates variable-length symbol with to original noncoding data encoding.For the object of this description, hypothesis is used to the data stream encoding of DEFLATE algorithm to variable length code, and the data flow of therefore variable length code has DEFLATE form.But, should understand and the invention is not restricted to can use together with the mechanism of exemplary embodiments with other data flow using together with the data flow of DEFLATE format and there is variable length code and do not depart from the Spirit Essence and the scope that illustrate row embodiment.
Conventionally, the data flow of variable length code is not used for itself parallel decoding operation, and the processor of data handling system can not be to the part parallel decoding of data flow.This is because there is no byte alignment marker character and therefore can not determine where a data division starts and finish and where another data division starts and finish from data flow in data flow, for example, data division can be 7 long, another part can be 9 long, another part can be 16 long, etc., and can not determine where these borders are dropped on from data flow.As a result of, can not simply data flow be resolved into then by the chunk of parallel processing, because can complete decomposition in symbol, make thus incorrect decompress(ion) result be generated.As a result of, the general processing of carrying out the data flow of variable length code with decode operation successively, throughput and the speed of the decoding of this data flow that decode operation restriction can be used for realizing variable length code successively.
Exemplary embodiments is provided for considering the variable-length symbol in coded data stream in the time that the data flow of coding (or compression) is carried out decoding or separated press operation.That is to say, exemplary embodiments provide a kind of with parallel mode decoder or the decompression machine mechanism of the data flow operations to variable length code.Fig. 3 is according to the example block diagram of an exemplary embodiments such decoder/decompression machine.In the software that can carry out at hardware, by one or more hardware device or any combination of hardware and/or software, be implemented in the unit shown in Fig. 3.In an exemplary embodiments, the unit of Fig. 3 is implemented in circuit logic and therefore represents an only exemplary embodiments for hardware.In other exemplary embodiments, one or more unit in the unit shown in Fig. 3 may be implemented as such as, carried out by hardware device (processor of hardware implementation) for implementing its software, the firmware etc. of function.In more other exemplary embodiments, some unit in the unit in Fig. 3 may be implemented as the only circuit of hardware, and other unit is implemented as software, the firmware etc. on one or more hardware device, carried out.
As shown in Figure 3, decoder/decompression machine 300 comprises alignment logic 310, token logic 320, token list data structure storage device 325, output maker logic 330 and data flow input line storage device 340.Decoder/decompression machine 300 receives the data flow 350 of variable length code as input.During each processor cycle, decoder/decompression machine 300 receives " input line " of the data flow 350 of variable length code, and this input line is defined in the data word joint number of the input traffic receiving during the processor cycle.Input line has fixed size or byte number M.For 1 the compression ratio of being greater than or equal to of the data flow 350 of variable length code, the byte number M in input line is less than or equal to the byte number N of the output of being sought the decompress(ion) to generate in each processor cycle.In the data flow 350 of variable length code, the regular length character in legacy data is encoded as variable-length symbol.For example, in the time utilizing huffman coding (such as generating under data flow 350 these concrete conditions of variable length code by the DEFLATE compression algorithm with static huffman coding), the each symbol in the symbol of coding can have at minimum huffman code length H
min(for example, 7) are upper to the longest huffman code length H
maxfor example, variable-length between (, 31).
The input data that alignment logic 310 operations of decoder/decompression machine 300 are used for aiming at input line are to start at the character boundary of coding, wherein represent the symbol in coded data stream by variable amount of bits, and symbol is corresponding to one or more byte of the legacy data before coding/compression.For example, utilize huffman coding, use variable length huffman code to the symbolic coding in the data of compression, the pointer of some successive bytes of the legacy data that wherein the literal byte of the symbology legacy data of coding or sensing had previously detected.Due to the changeability of the length of the symbol of the coding in fixed size input line, can misalignment input line to start at character boundary, and the symbol of some codings can cross over multiple input lines, for example, crosses over to next input line from an input line.
As mentioned above, in the context of this description, input line refers to the coded data with fixed word joint number.Every processor cycle receives and processes input line.Term " symbol " refers to that the variable length code in coded data stream represents as used it here about coded data stream, wherein can be to each symbol decoding/decompress(ion) to create the legacy data of one or more byte.For example, can receive input line, this input line comprises 8 bytes (64) and can comprise 5 symbols that length is 17,8,9,21 and 11 (amounting to=66).In this example, the symbol 1 of 17 can be decoded into the legacy data of 13 bytes, and symbol 2 can be decoded into the legacy data of 1 byte, by that analogy.In addition, the total bit in symbol 1-5 is 66 and therefore has the position of 2 to overflow.Therefore, next line must be shifted 2 to aim at it to start at new character boundary.
Fig. 4 is the exemplary plot that illustrates multiple input lines, these input lines illustrate coding symbol position from an input line overflowing to another input line.As shown in Figure 4, symbol 410-424 is corresponding to the coding in the data of compression or the symbol of compression.The Part I that the first input line 430 of multiple bytes of the data of the compression that receives in the processor cycle comprises symbol 410-414 and symbol 416 equally.Symbol 416 overflows in next input line 440, thereby makes the position of call sign 416 be present in input line 430 and input line 440 in the two.This is called as " overflow position ".Therefore, the skew of the beginning of the identifier 418 in input line 440 depends on the figure place of overflowing from input line 430.The minimum number of bits of overflowing is 0, and maximum is overflowed for H
max-1, because the size of the symbol of coding is at most the largest amount H of code
max, and at least one position must be present in input line 430 and overflows to have.
Therefore,, in order to aim at input line 440, must first determine overflowing quantity and must compensate this and overflow from previous input line 430.This is the function being provided by the aligner logic 310 of the decoder/decompression machine 300 in Fig. 3.In order to carry out the parallel processing of these input lines, need to overflow and start to aim at input line at character boundary by compensation position.Once overflow and be aligned by compensating such position, the mechanism of exemplary embodiments can be by parallel mode to the input line operation of aiming at.
What are owing to not knowing in advance that position is overflowed for specific a pair of input line 430 and 440, so the pipelined architecture that the aligner logic 310 of exemplary embodiments is used for speculative decode, wherein all options that overflow are followed by rear selection operation.Speculative decode comprise each line for from 0 to H
maxthe H of-1 all possible skew
maxprocessing is inferred on road.That is to say, the each possible skew of parallel in the time that line is carried out, and result and the decoded result in first front based on decoding selected one of decoded result for one of possible skew.Carry out speculative decode with the mode of pipelining for the each skew in input line to walk abreast.
In order to further illustrate the mode of overflowing and determine corresponding skew for identifying correct position, consider the following sample situation of simplifying.Suppose only to have with biased the moving with y is biased of x and move corresponding two possible skews.Now hypothesis input line can comprise maximum n symbol and computing equipment can every processor period treatment symbol at the most, thereby make some cycles of needs process input line.In the cycle 1, receive input line 1, and consider that biased the moving with the biased in-migration of y of x process the first symbol in input line 1 to find the length of the first symbol in input line for two kinds of drift condition.In next processor cycle, receive input line 2, and similarly consider biased the first symbol of processing line 2 with the biased in-migration of y that moves of x.In the same processor cycle, for the second symbol of two supposition scene process input lines 1.This process continues, and in n cycle, process all possible n symbol of input line 1, and computing equipment is known the length of all possible n symbol in line.The total length of all symbols deducts the Length Indication of input line to the possible position overflow value of next line.For example, if the total length of all symbols is 69 and 71 for two supposition situations, and the length of input line is 64, has two possible positions to overflow guess value (5 and 7).Provide a kind of position of determining for the decoding based on from past data input line to overflow or be offset and select to infer that overflow position or overflow which position of be offset or to be offset be a correct selection mechanism of overflowing or being offset.
Utilize the mechanism of exemplary embodiments, not only consider that two may be offset or overflow position, but as in above example, can any number of parallel possible overflows or is offset.For example, utilize an exemplary embodiments, in the time processing each input line, consider from 0 to H
maxoverflow the possible position of-1.
Fig. 5 illustrates according to the alignment logic 310 of the decoder/decompression machine 300 of an exemplary embodiments in the example block diagram to punctual operation of determining input line.As shown in Figure 5, alignment logic 310 receives the input line 510 of the data of the coding/compression that comprises M byte.The filling logic 520 of alignment logic 310 is filled from the maximum of previous input line and is overflowed figure place to input line 510.Therefore, for example, in the first processor cycle, can receive and store the first input line, and in next processor cycle, can receive the second input line and with the formerly front processor cycle during the first input line combination of receiving is upper overflows figure place to maximum.The input line of filling to parallel pipeline 530-550 input.Each streamline in parallel pipeline 530-550 is carried out the displacement of the input line of filling according to one of possible skew (overflow position) quantity.For example, first-class waterline 530 is carried out 0 bit shift, and second waterline (not shown) can be carried out 1 bit shift, and the 3rd streamline (not shown) can be carried out 2 bit shifts, by that analogy.Therefore, streamline 540 is carried out i bit shift, and final streamline 550 is carried out (H
max-1) bit shift or maximum shift (overflow position).
In each streamline 530-550, next symbol decoding of every grade of 532-536, the 542-546 of streamline and 552-556 storage displacement and the input line of filling and the input line to displacement and filling.Streamline 530-550 has 8*M/H
minpipeline depth, wherein H
minbe the symbol lengths of minimum code, the symbol lengths of this minimum code is 7 in this concrete example of static huffman coding.The size of symbol is based on sign pattern and have width w designated in encryption algorithm and that aligner logic 310 is known (or length).For example, use DEFLATE algorithm and data format, know the length (width) for the particular code in the symbol in the input line being shifted and fill by reading the coding schedule associated with encryption algorithm.For example, coding schedule has entry, and these entries define for specific bit patterns, and what the length of the symbol of next coding will be.For example, be 1010111.. if coding schedule can define ensuing n position, the length of next symbol is x, and if ensuing n position is 111000 ..., the length of next symbol is y, by that analogy.Once the length of next symbol is known, input line can be shifted this figure place, and can again check that ensuing n position is to find the length of next symbol, by that analogy.
Every grade of 532-536,542-546 and 552-556 comprise one or more register and the decoding/decompress(ion) logic that are called as computational logic (CL), this CL is to displacement and next symbol decoding/decompress(ion) of input line 510 of filling and the amount of displacement of renewal accumulative total,, equal to add the width by next symbol of processing as prime 532-536,542-546 and 552-556 from the amount of displacement of the accumulative total of first prime for the amount of displacement of the accumulative total of level 532-536,542-546 and 552-556.This amount of displacement of accumulative total is until run into the end of original M byte input line.That is to say, carry out the upper point that is greater than or equal to unfilled input line length to accumulative total displacement of decoding.This can any grade of appearance in level 532-536,542-546 and the 552-556 of streamline 530-550 according to the width of amount of displacement and symbol.Once amount of displacement of this accumulative total meets or the size that exceedes input line (in the example of describing, input line is 8*M position, wherein M is the byte number of the compression in input line, and 8 represent the figure place of every byte), not continue accumulative total amount of displacement, but transmit input line and current accumulative total amount of displacement from level to level and do not upgrade.For example, if original input line length be 64 and fill that it is upper to 94, carry out that decoding is upper is greater than or equal to the point of 64 to accumulative total displacement.In this case, be necessary to fill in input line to 94 because can for example have in place 63 start and extend until the symbol of position 94, and only can all 94 when known to this symbol decoding.Figure place in original unfilled input line length more than 64 is overflowing or being offset for next input line.
In the end of streamline 530-550, the size (8*M) that deducts input line from the amount of displacement " displacement " of accumulative total is overflowed to obtain to the supposition position of next input line.Therefore, there is the position of supposition overflow value for the each streamline 530-550 inputting to multiplexer 560.Be selected as and will be used for next input line (for example to carry out shifting function to one of supposition position overflow value input of multiplexer 560, the operation of shifting left) actual bit overflow to aim at next input line and character boundary, generate thus the input line 570 of aiming at.
Referring again to the previous example that wherein has two possible position overflow value x or y, multiplexer 560 is used for selecting one of these two values as for aiming at overflowing of next input line.Multiplexer 560 know the skew (or position overflow) of lucky the first input line in the data flow of compression and therefore likely the known offset based on lucky the first input line (being input line 1) select two positions overflow or one of deviant (not for lucky the first input line from the overflowing of previous input line, but it can comprise some known head positions).Once carried out this selection, known overflowing to the actual bit of input line 2 from input line 1 what is.In next processor cycle, this actual bit from input line 1 to input line 2 is overflowed and can be used for selecting to overflow to the actual bit of line 3 from line 2.Overflow from input line 2 to the actual bit of line 3 and then can be used for selecting to overflow to the actual bit of line 4 from line 3, by that analogy.
Look back Fig. 3, provide the input line 570 of aligning as input to token device logic 320.Although being illustrated as from aligner logic 310, token device logic 320 separates, but should understand, the pipeline stages of token device logic 320 can be aimed at the level of streamline in aligner logic 310 and do not departed from Spirit Essence and the scope of exemplary embodiments.Token device logic 320 is the symbol extraction symbol data from the compression the input line of aiming in the mode of pipelining as shown in Figure 6.As shown in Figure 6, token device logic 320 comprises multiple grades of 610-640, and wherein every grade comprises computational logic (CL) and for storing one or more register of result of computational logic.Pipeline depth equals the maximum number (t) of effective token of every input line, and this maximum number has upper limit 8*M/H
minposition.
Extract the symbol data for the symbol at next coding corresponding with one or more byte in legacy data input line of aiming at the computational logic of every grade of 610-640.Symbol data can comprise significance bit, type bit (for example, literal or point to the pointer of previously stored byte sequence/quote), literal (if type bit instruction is literal), distance (if type bit instruction pointer/quote) etc. backward.Computational logic is also determined the expanded character joint number (IB) associated with symbol,, the byte number of the decoding/unpressed data that generate from the symbol the input line of aiming at, and in the streamline of token device logic 320, maintain the expansion total amount of byte (IBt) for input line from level to level 610-640.
In the final stage 640 of token device logic 320 streamlines, use information updating token table 650 from the extraction of symbol to generate thus the token entry in token table 650.As shown in Figure 6, token table 650 comprises one or more entry, and each entry is corresponding to the symbol in input line.Significance bit that each entry in token table 650 is extracted for corresponding token store according to the type of symbol (token), type (for example, literal or pointer/quote), write pointer (wr_ptr) and backward apart from or the actual literal symbol that flies decoding/decompress(ion).For token write pointer (wr_ptr) point to unpressed data flow as upper/lower positions, should be inserted through in this position the byte that token decode is produced.In final stage 640, upgrade the pointer that writes for symbol/token i based on finally writing pointer wr_last, this finally writes pointer corresponding to by until the expansion byte accumulative total till whole expansion bytes that all symbols of the previously end of input line produce and previous symbol/token i-1 in the upper extremely current line of aiming at, i.e. wr_last+IB
i-1.The first token in the input line of aiming at has the pointer of writing wr_ptr, and this writes pointer and be arranged for the wr_last value of previous input line, because it is the first symbol/token in the input line of aligning.Also in final stage 640, upgrade and write last pointer wr_last, thereby this value is stored for using in the time processing the input line of next aligning.Can export to the output maker logic 300 in Fig. 3 the token of storage in token table 650.
Output maker logic 330 obtains the data that the token that generated by token device logic 320 and every processor cycle generate the decoding/decompress(ion) of N byte.In an exemplary embodiments, these N byte comprises the data word of being exported by output maker logic 330, and wherein data word comprises the byte from the decoding/decompress(ion) of legacy data, and this legacy data is the source of the input line of coding.Output maker logic 330 comprises state machine, and this state machine is resolved token and the every processor cycle that and its information that generate by token device logic 320 is stored in the entry of token table 650 and generated N byte.Output maker logic 330 maintains the current word location (out_ctr) in the output stream of decoding/decompress(ion) and is each byte-identifier source token in N byte of current output word (src_token[0:N-1]).For example,, if wr_ptr is (token
x) <=(out_ctr+i) <wr_ptr (token
x+1), be less than or equal to if point to the pointer that writes of the beginning of token X the pointer that writes that current word location and byte index sum and current word location and byte index sum are less than next token X+1, token X is the source for byte i.
The token that output maker logic 330 is processed from multiple input lines simultaneously for example, is processed the token from least two input lines simultaneously.If token set is not consumed (the current output word that all tokens in set are used for producing N byte) completely by current output word, [wr_last (token set1) > (out_ctr+N), delay aligner logic 310 and/token device logic 320.In the time generating output word, output maker logic 330 determines whether output byte is literal, and if be like this, copies literal to output byte.On the other hand, if output byte is the pointer of the byte in the byte sequence identifying before pointing to formerly or quotes, use the distance backward of storage in token table 650 to carry out execute store search operation to fetch byte data from memory and to copy it to output word.If not can be used to generate enough tokens of output word, [wr_last (token set2) < (out_crt+N), storage area output word keep out_ctr, and get and read new token set; Otherwise, out_ctr is increased progressively to N and this operation repetition.
Fig. 7 is according to the example block diagram of the output maker logic of an exemplary embodiments.As shown in Figure 7, (for example receive two token set 710 and 712, from a token set of the each input line in two different input lines) as the input in N multiplexer 720-724, wherein N is the output word joint number in every processor cycle of wishing for certain architectures.Token set 710-712 is that the token table 650 from being generated by token device logic 320 obtains, and therefore comprises the token entry from token table 650 in these entries together with all information of storing.
Each multiplexer 720-724 selects signal src_token[i with the corresponding source token for this byte] associated, wherein i scope is from 0 to N-1.Therefore, each multiplexer is selected signal src_token[i from token Resource selection and source token] corresponding token, this source token is selected signal src_token[i] mark is used for the source token in this specified byte of output word.Multiplexer 720-724 comprises additional logic, this additional logic is for based on exporting corresponding token type (literal or pointer/quote) in token set and token entry corresponding to token that select as the selection signal in another multiplexer 730-734, in token type be literal in the situation that output from the literal data of token table clause as the input to multiplexer 730-734 and at token type output determining apart from field backward based on token table clause be pointer/quote in the situation that, to another multiplexer 740-744 and also to the enable/reading address that reads of RAM750-754 input.
For every processor cycle provides the private memory 750-754 of separation by the each output byte in the output byte of generation or has the part of the shared storage of N read port.The data of the decompressed/decoded that each memory stores in these memories 750-754 is identical, the each memory in memory 750-754 repeats each other.Each memory in N the memory 750-754 corresponding with N byte in output word 760 is organized as N byte word.Alternatively, can use shared storage, this shared storage is organized as N byte word and has N read port, and wherein each read port is served one of N byte in output word 760.Memory 750-754 can share the public inbound port of writing.Total memory capacity is determined by pointer/the quote adducible previous history of token.For example, history is 32KB for DEFALTE specification.If suppose N=16, then this 32KB memory is organized as the 2K memory word of 16 bytes of respectively doing for oneself.Enable and reading address signal according to reading, read the memory word of 16 bytes.The more high-order position of reading address signal is used for reading word (being 11 the 32KB memory) from memory, and more low-order bit (being 4 in the situation that of 16 byte word) is used for selecting one of N byte reading from memory (multiplexer 740-744).
With together with literal output from multiplexer 720-724, be fed to byte from the selection of memory 750-754 as the input to multiplexer 730-734.Based on token type (be literal or pointer/quote), one of these inputs are selected as the output byte for the correspondence position 1 to N at output word of output word 760.For example, if token type is literal type, select the literal data input to multiplexer 730-734.If token type is pointer/quote, select from the byte of multiplexer 740-744 output for being exported by multiplexer 730-734.Therefore, the each multiplexer in multiplexer 730-734 is exported the data byte that the tram in output word comprises in output word 760.Then can provide this output word 760 for processing to other logic in computing equipment, for example, provide to the central processing unit in computing equipment or other functional unit, this central processing unit or other functional unit can software, firmware etc. based on carrying out on computing equipment operate output word 760.The output word of decoding also in the each memory in N memory the definite memory location of current word location in the output stream by decoding/decompress(ion) be stored as N byte word.
Therefore, utilize the mechanism of exemplary embodiments, make the high bandwidth parallel processing of the data flow of variable length code become possibility.Utilize these mechanism, even still can parallel processing individual traffic in the time that individual traffic comprises the symbol of variable-length.Input line is overflowed, again aimed to the mechanism of exemplary embodiments to make them at character boundary and then correspondingly to process line in the mode of parallel pipelining process linearize and corresponding symbol/token carrys out compensate for variable length symbol by determining position since from an input line to another input line.This rolls up throughput and the speed that can be used for processing such data flow by elimination for the requirement of the serialization processing of the data flow of variable length code.
Fig. 8 is the flow chart of having summarized according to the exemplary operations of the data flow for the treatment of variable length code of an exemplary embodiments.The operation of summarizing in can being implemented in Fig. 8 in the decoder/decompression machine of data handling system/computing equipment.This decoder/decompression machine for example can be to integrated as coprocessor, as the part of network or storage adapter, as one or more hardware device in the hardware device separating or these hardware devices and one or more software mechanism of being performed on one or more processor device and the combination of software mechanism in data handling system/computing equipment.
As shown in Figure 8, operation starts from decoder/decompression machine and receives Data In-Line, and this Data In-Line is the part (step 810) to the data flow of the variable length code of the data handling system of implementing therein decoder/decompression machine/computing equipment transmission.Decoder/decompression machine specified data input line is overflowed quantity (step 820) for symbols to the position on next Data In-Line.Quantity aligned data input line (step 830) is overflowed in the position of decoder/decompression machine based on determining.The Data In-Line that decoder/decompression machine tokenization is aimed at is to generate token set, and wherein each token is corresponding to the symbol (step 840) in coded data input line.Decoder/decompression machine is based on token set generated data output word (step 850).Data output word is corresponding in the concentrated data word of legacy data.Export this output word to other unit of data handling system/computing equipment for processing (step 860), and operation stops.
As noted above, should understand exemplary embodiments can adopt devices at full hardware embodiment, full implement software example or comprise the such form of both embodiment of hardware and software unit.In an example embodiment, in the mechanism that includes but not limited to implement in the software of firmware, resident software, microcode etc. or program code exemplary embodiments.
The data handling system that is suitable for storage and/or executive program code will comprise at least one processor that is coupled, either directly or indirectly, to memory cell by system bus.Memory cell can be included in the local storage, mass storage device and the cache memory that between actual executive program code period, use, these cache memories the temporary transient storage of at least some program codes is provided in case reduce must the term of execution fetch the number of times of code from mass storage device.
I/O or I/O equipment (including but not limited to keyboard, display, pointing apparatus etc.) can be directly or are coupled to system by I/O controller between two parties.Network adapter also can be coupled to system and be coupled to other data handling system or remote printer or memory device so that data handling system can become by special or public network between two parties.Modulator-demodulator, cable modem and Ethernet card are only a few types of current available network type of adapter.
Description of the invention is presented for the object of example and description, is still not intended as exhaustive the present invention or makes the present invention be limited to disclosed form.Many modifications and variations will be clear by those of ordinary skill in the art.Select and describe embodiment to principle of the present invention, practical application are described best and make other those of ordinary skill of this area understand the present invention for the various embodiment that have as with the matched various amendments of specific use of imagining.
Claims (25)
1. a method of decoding for the data flow to variable length code in data handling system, comprising:
Decoder by described data handling system receives Data In-Line, and wherein said Data In-Line is a part for the data flow of described variable length code;
Determine that by described decoder described Data In-Line overflows quantity to the position on next Data In-Line;
Institute's rheme by described decoder based on definite is overflowed quantity and described next Data In-Line is aligned to the character boundary that starts from coding, to generate next Data In-Line of aligning;
By next Data In-Line of aiming at described in described decoder token, to generate token set, wherein each token is corresponding to the symbol in next Data In-Line of described aligning; And
By described decoder, based on described token set generated data output word, wherein said data output word is corresponding to the concentrated data word of legacy data.
2. method according to claim 1, wherein determine that described Data In-Line overflows quantity to the position on next Data In-Line and comprises:
Carry out multiple speculative decode operations of described Data In-Line, each speculative decode operation be overflowed one of quantity corresponding to multiple different possibilities position; And
May position overflow each in quantity and may overflow quantity in position for multiple, the result of the described multiple speculative decode operations based on described Data In-Line determines that the position of described Data In-Line overflows quantity.
3. method according to claim 2, its meta overflow quantity at 0 to H
maxin the scope of-1, wherein H
maxthe maximum length of the variable-length symbol in described Data In-Line, and wherein for from 0 to H
maxeach figure place of may overflowing in-1 described scope is carried out speculative decode operation.
4. method according to claim 2, wherein multiple speculative decode operation described in executed in parallel, and the position of wherein determining described Data In-Line overflows that quantity comprises past data line in the data flow based on for described variable length code and quantity is overflowed and select the result of one of described multiple speculative decode operations in definite position.
5. method according to claim 2, wherein determines that position overflows decoded result that quantity comprises described result based on described multiple speculative decode operation and past data line and determine that institute's rheme overflows quantity.
6. method according to claim 1, wherein comprised to generate token set by next Data In-Line of aiming at described in described decoder token: by thering is next input line of aiming at described in multistage token pipeline processes, wherein every grade comprises computational logic, described computational logic extracts the symbol data for the symbol of next coding of next input line of described aligning, the size accumulative total of the described symbol data of determining the previous sum of expansion byte of the expansion byte number associated with the described symbol data extracting and next input line based on for described aligning and extract is used for the expansion total amount of byte of next input line of described aligning.
7. method according to claim 6, the final stage utilization of wherein said token streamline is upgraded token list data structure for the entry of the symbol data of the extraction of next input line extraction from described aligning.
8. method according to claim 7, is wherein included in the token of substantially the same time processing from least two input lines based on described token set generated data output word.
9. method according to claim 7, the symbol data that wherein extracts the symbol that is used for next coding comprises that the type of the symbol of corresponding extraction is designated as literal sign pattern or the data of quoting to literal sign pattern by extraction, indicate literal sign pattern and the data of directive face amount and in response to described type instruction reference type and indicate the data apart from pointer backward in response to described type, and wherein utilize entry to upgrade token list data structure and comprise the symbol data of filling the extraction corresponding with the symbol of extraction that is associated with described token table clause to described entry.
10. method according to claim 1, the data flow of wherein said variable length code comprises the legacy data that uses huffman coding algorithm and be encoded.
11. methods according to claim 1, wherein carry out described method in pipelining mode, so that per clock cycle is processed the Data In-Line from the data flow of described variable length code.
12. methods according to claim 1, wherein comprise at least one operation in following operation based on described token set generated data output word:
In each memory in multiple N memories of output maker logic, storage is from the same section of the data of the decoding of the data flow of described variable length code, and wherein N is that every processor cycle is by the byte number of the data of the decoding being output in described output word; And
For the each byte in described N byte in described data output word, export data byte that the corresponding memory from described multiple N memory reads or the literal from token table clause according to described sign pattern; Or
A part for the data of storage decoding in the single shared storage of described output maker logic, described single shared storage has N read port, and each read port is used for each processor cycle by a byte of the data of the decoding being output at described data output word; And
For the each byte in described N byte in described data output word, export data byte that the corresponding read port from described multiple N read port reads or the literal from token table clause according to described sign pattern.
13. 1 kinds comprise the computer program of computer-readable recording medium, described computer-readable recording medium has the computer-readable program of storage therein, and wherein said computer-readable program makes described data handling system in the time being performed in data handling system:
Receive Data In-Line, wherein said Data In-Line is a part for the data flow of described variable length code;
Determine that described Data In-Line overflows quantity to the position on next Data In-Line;
Institute's rheme based on definite is overflowed quantity and described next Data In-Line is aligned to the character boundary that starts from coding;
Described next Data In-Line that tokenization is aimed at is to generate token set, and wherein each token is corresponding to the symbol in described next Data In-Line of aiming at; And
Based on described token set generated data output word, wherein said data output word is corresponding to the concentrated data word of legacy data.
14. computer programs according to claim 13, wherein said computer-readable program makes described data handling system determine that by following operation described Data In-Line overflows quantity to the position on next Data In-Line:
Carry out multiple speculative decode operations of described Data In-Line, each speculative decode operation be overflowed one of quantity corresponding to multiple different possibilities position; And
May position overflow each in quantity and may overflow quantity in position for multiple, the result of the described multiple speculative decode operations based on described Data In-Line determines that the position of described Data In-Line overflows quantity.
15. computer programs according to claim 14, its meta overflow quantity at 0 to H
maxin the scope of-1, wherein H
maxthe maximum length of the variable-length symbol in described Data In-Line, and wherein for from 0 to H
maxeach figure place of may overflowing in-1 described scope is carried out speculative decode operation.
16. computer programs according to claim 14, wherein multiple speculative decode operation described in executed in parallel, and wherein said computer-readable program makes the described data handling system position definite by the past data line in the data flow based on for described variable length code overflow quantity to select the result of one of described multiple speculative decode operations to determine the quantity of overflowing of described Data In-Line.
17. computer programs according to claim 14, wherein said computer-readable program makes described data handling system determine that by the decoded result of the described result based on described multiple speculative decode operation and past data line position overflows quantity and determine that institute's rheme overflows quantity.
18. computer programs according to claim 13, wherein said computer-readable program makes described data handling system carry out described next Data In-Line that tokenization aims to generate token set by described next input line that has multistage token pipeline processes and aim at, wherein every grade comprises computational logic, described computational logic extracts the symbol data of the symbol of next coding of described next input line for aiming at, the size of the described symbol data of determining the previous sum of expansion byte of the expansion byte number associated with the described symbol data of extraction and described next input line based on for aiming at and extract adds up the expansion total amount of byte of described next input line for aiming at.
19. computer programs according to claim 18, the final stage utilization of wherein said token streamline is upgraded token list data structure for the entry of the symbol data of the extraction of described next input line extraction from aiming at.
20. computer programs according to claim 19, wherein said computer-readable program makes described data handling system process from the token of at least two input lines to come based on described token set generated data output word by the time substantially the same.
21. computer programs according to claim 19, wherein said computer-readable program makes described data handling system, by extracting, the type of the symbol of corresponding extraction is designated as to literal sign pattern or the data of quoting to literal sign pattern, indicate literal sign pattern and the data of directive face amount and in response to described type instruction reference type and indicate the data apart from pointer backward to extract the symbol data for the symbol of next coding in response to described type, and wherein said computer-readable program makes described data handling system utilize described entry renewal token list data structure by fill the symbol data of the extraction corresponding with the symbol of extraction that is associated with described token table clause to entry.
22. computer programs according to claim 13, the data flow of wherein said variable length code comprises the legacy data that uses huffman coding algorithm and be encoded.
23. computer programs according to claim 13, wherein said computer program makes the data wire operation to the data flow from described variable length code in pipelining mode of described data handling system, so that per clock cycle is processed the Data In-Line from the data flow of described variable length code.
24. computer programs according to claim 13, wherein said computer-readable program also makes described data handling system come based on described token set generated data output word by least one operation in following operation:
In each memory in multiple N memories of output maker logic, storage is from the same section of the data of the decoding of the data flow of described variable length code, and wherein N is that every processor cycle is by the byte number of the data of the decoding being output in described output word; And
For the each byte in described N byte in described data output word, export data byte that the corresponding memory from described multiple N memory reads or the literal from token table clause according to described sign pattern; Or
A part for the data of storage decoding in the single shared storage of described output maker logic, described single shared storage has N read port, and each read port is used for each processor cycle by a byte of the data of the decoding being output at described data output word; And
For the each byte in described N byte in described data output word, export data byte that the corresponding read port from described multiple N read port reads or the literal from token table clause according to described sign pattern.
25. 1 kinds of devices, comprising:
Processor; And
Is coupled to the interface of described processor, wherein receives the data flow of variable length code via described interface, and wherein said processor comprises the logic for following operation:
Receive Data In-Line, wherein said Data In-Line is a part for the data flow of described variable length code;
Determine that described Data In-Line overflows quantity to the position on next Data In-Line;
Institute's rheme based on definite is overflowed described next Data In-Line of quantity aligning to start at the character boundary of coding;
Described next Data In-Line that tokenization is aimed at is to generate token set, and wherein each token is corresponding to the symbol in described next Data In-Line of aiming at; And
Based on described token set generated data output word, wherein said data output word is corresponding to the concentrated data word of legacy data.
Applications Claiming Priority (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US13/313,072 | 2011-12-07 | ||
| US13/313,072 US8824569B2 (en) | 2011-12-07 | 2011-12-07 | High bandwidth decompression of variable length encoded data streams |
| PCT/CN2012/084440 WO2013082990A1 (en) | 2011-12-07 | 2012-11-12 | High bandwidth decompression of variable length encoded data streams |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN103975533A true CN103975533A (en) | 2014-08-06 |
| CN103975533B CN103975533B (en) | 2017-11-21 |
Family
ID=48571482
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201280060474.4A Active CN103975533B (en) | 2011-12-07 | 2012-11-12 | The high bandwidth decompression of the data flow of variable length code |
Country Status (6)
| Country | Link |
|---|---|
| US (2) | US8824569B2 (en) |
| JP (1) | JP5878644B2 (en) |
| CN (1) | CN103975533B (en) |
| DE (1) | DE112012004873B4 (en) |
| GB (1) | GB2512762B (en) |
| WO (1) | WO2013082990A1 (en) |
Cited By (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107111623A (en) * | 2014-10-21 | 2017-08-29 | 华为技术有限公司 | Parallel historical search and coding for the compression based on dictionary |
| CN107925419A (en) * | 2015-09-25 | 2018-04-17 | 英特尔公司 | For system, the method and apparatus unziped it using hardware and software |
| CN107925420A (en) * | 2015-09-25 | 2018-04-17 | 英特尔公司 | Isomery for optimized compression ratio compresses framework |
| CN109716659A (en) * | 2016-07-22 | 2019-05-03 | 英特尔公司 | High-performance list stream LZ77 compress technique |
| CN109923516A (en) * | 2014-05-14 | 2019-06-21 | 卡拉公司 | Reinforce computer security, variable word length coding and the decoded technology of variable length code |
| CN109937537A (en) * | 2016-11-18 | 2019-06-25 | 国际商业机器公司 | Coding Variable length symbol is to realize parallel decoding |
| CN112771498A (en) * | 2018-07-05 | 2021-05-07 | 米西克有限公司 | System and method for implementing an intelligent processing computing architecture |
| CN113474999A (en) * | 2019-02-27 | 2021-10-01 | 国际商业机器公司 | Overflowing temporary results to accommodate storage boundaries |
| CN114244373A (en) * | 2022-02-24 | 2022-03-25 | 麒麟软件有限公司 | LZ series compression algorithm coding and decoding speed optimization method |
| CN117220687A (en) * | 2023-03-01 | 2023-12-12 | 山东华科信息技术有限公司 | Data decompression method for distributed energy grid-connected monitoring |
Families Citing this family (19)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| TWI455595B (en) * | 2011-09-29 | 2014-10-01 | Mstar Semiconductor Inc | Boolean entropy decoder and boolean entropy decoding method in video display system |
| US8824569B2 (en) * | 2011-12-07 | 2014-09-02 | International Business Machines Corporation | High bandwidth decompression of variable length encoded data streams |
| US20140006536A1 (en) * | 2012-06-29 | 2014-01-02 | Intel Corporation | Techniques to accelerate lossless compression |
| US9311721B1 (en) | 2013-04-04 | 2016-04-12 | Sandia Corporation | Graphics processing unit-assisted lossless decompression |
| US9374106B2 (en) | 2013-08-28 | 2016-06-21 | International Business Machines Corporation | Efficient context save/restore during hardware decompression of DEFLATE encoded data |
| US8933824B1 (en) | 2013-08-28 | 2015-01-13 | International Business Machines Corporation | Hardware decompression of deflate encoded data with multiple blocks |
| US9086871B2 (en) | 2013-09-26 | 2015-07-21 | International Business Machines Corporation | Reordering the output of recirculated transactions within a pipeline |
| US9800640B2 (en) | 2013-10-02 | 2017-10-24 | International Business Machines Corporation | Differential encoder with look-ahead synchronization |
| US9524169B2 (en) | 2014-09-24 | 2016-12-20 | Intel Corporation | Technologies for efficient LZ77-based data decompression |
| US9946705B2 (en) * | 2015-06-29 | 2018-04-17 | International Business Machines Corporation | Query processing using a dimension table implemented as decompression dictionaries |
| US9819359B1 (en) | 2016-12-11 | 2017-11-14 | Microsoft Technology Licensing, Llc | Multi-symbol, multi-format, parallel symbol decoder for hardware decompression engines |
| US10680644B2 (en) | 2017-09-15 | 2020-06-09 | Groq, Inc. | Decompression of model parameters using functions based upon cumulative count distributions |
| US11119928B2 (en) | 2019-02-27 | 2021-09-14 | International Business Machines Corporation | Instant quiescing of an accelerator |
| TWI729939B (en) * | 2019-03-22 | 2021-06-01 | 美商葛如克公司 | Method and processor for decompression of model parameters using functions based upon cumulative count distributions |
| TWI708196B (en) * | 2019-03-22 | 2020-10-21 | 美商葛如克公司 | Method and processor for decompression of model parameters using functions based upon cumulative count distributions |
| CN112631595B (en) * | 2019-10-09 | 2024-03-01 | 安徽寒武纪信息科技有限公司 | Shuffling method, shuffling device, computer equipment and readable storage medium |
| JP2021129143A (en) | 2020-02-10 | 2021-09-02 | キオクシア株式会社 | Decoding device |
| CN112988673B (en) * | 2021-02-22 | 2023-02-28 | 山东英信计算机技术有限公司 | Method and equipment for processing data overflow in decompression process |
| CN113965207B (en) * | 2021-12-17 | 2022-03-15 | 苏州浪潮智能科技有限公司 | Deflate Huffman coding-based dynamic code table generation device and method |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1154014A (en) * | 1995-10-19 | 1997-07-09 | 三星电子株式会社 | High-speed variable-length decoder |
| US6310563B1 (en) * | 2000-05-12 | 2001-10-30 | International Business Machines Corporation | Method and apparatus for enhanced decompressor parsing |
| US6865668B1 (en) * | 1998-09-15 | 2005-03-08 | Trustees Of Columbia University In The City Of New York | Variable-length, high-speed asynchronous decoder circuit |
| US20080022074A1 (en) * | 2002-06-25 | 2008-01-24 | Madduri Venkateswara R | Instruction Length Decoder |
Family Cites Families (52)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB9405914D0 (en) | 1994-03-24 | 1994-05-11 | Discovision Ass | Video decompression |
| JPS63278468A (en) * | 1987-05-09 | 1988-11-16 | Fujitsu Ltd | Decoding circuit for variable length code data |
| US5146221A (en) | 1989-01-13 | 1992-09-08 | Stac, Inc. | Data compression apparatus and method |
| US5051745A (en) * | 1990-08-21 | 1991-09-24 | Pkware, Inc. | String searcher, and compressor using same |
| US5212742A (en) * | 1991-05-24 | 1993-05-18 | Apple Computer, Inc. | Method and apparatus for encoding/decoding image data |
| US5842033A (en) | 1992-06-30 | 1998-11-24 | Discovision Associates | Padding apparatus for passing an arbitrary number of bits through a buffer in a pipeline system |
| US5440753A (en) * | 1992-11-13 | 1995-08-08 | Motorola, Inc. | Variable length string matcher |
| US5829007A (en) | 1993-06-24 | 1998-10-27 | Discovision Associates | Technique for implementing a swing buffer in a memory array |
| JP3371677B2 (en) * | 1996-04-09 | 2003-01-27 | 富士ゼロックス株式会社 | Variable length decoding device |
| US5909569A (en) | 1997-05-07 | 1999-06-01 | International Business Machines | Terminal emulator data stream differencing system |
| US5890006A (en) * | 1997-12-12 | 1999-03-30 | Advanced Micro Devices, Inc. | Apparatus for extracting instruction specific bytes from an instruction |
| US6061775A (en) * | 1997-12-12 | 2000-05-09 | Advanced Micro Devices, Inc. | Apparatus and method for predicting a first microcode instruction of a cache line and using predecode instruction data to identify instruction boundaries and types |
| US6219457B1 (en) * | 1998-05-26 | 2001-04-17 | Silicon Graphics, Inc. | Method and system for decoding data encoded in a variable length code word |
| US6215424B1 (en) | 1998-12-16 | 2001-04-10 | Thomson Licensing S.A. | System for variable length codeword processing suitable for video and other applications |
| US6822589B1 (en) | 1999-01-29 | 2004-11-23 | Quickshift, Inc. | System and method for performing scalable embedded parallel data decompression |
| US6601104B1 (en) | 1999-03-11 | 2003-07-29 | Realtime Data Llc | System and methods for accelerated data storage and retrieval |
| US8913667B2 (en) * | 1999-11-09 | 2014-12-16 | Broadcom Corporation | Video decoding system having a programmable variable-length decoder |
| JP2001274690A (en) * | 2000-03-28 | 2001-10-05 | Toshiba Corp | Variable length decoder |
| JP2002016501A (en) * | 2000-04-28 | 2002-01-18 | Matsushita Electric Ind Co Ltd | Variable length decoder |
| US6856651B2 (en) * | 2000-07-25 | 2005-02-15 | Peribit Networks, Inc. | System and method for incremental and continuous data compression |
| US6732198B1 (en) * | 2001-07-20 | 2004-05-04 | Lsi Logic Corporation | Methods and apparatus for saving and restoring scatter/gather list processing context in intelligent controllers |
| US7092578B2 (en) * | 2001-10-23 | 2006-08-15 | Agilent Technologies, Inc. | Signaling adaptive-quantization matrices in JPEG using end-of-block codes |
| US7681013B1 (en) * | 2001-12-31 | 2010-03-16 | Apple Inc. | Method for variable length decoding using multiple configurable look-up tables |
| US6944751B2 (en) * | 2002-02-11 | 2005-09-13 | Hewlett-Packard Development Company, L.P. | Register renaming to reduce bypass and increase apparent physical register size |
| US6963613B2 (en) * | 2002-04-01 | 2005-11-08 | Broadcom Corporation | Method of communicating between modules in a decoding system |
| GB0210604D0 (en) | 2002-05-09 | 2002-06-19 | Ibm | Method and arrangement for data compression |
| GB0213687D0 (en) * | 2002-06-14 | 2002-07-24 | Ibm | Multi-byte lempel-ziv 1 (LZ1) decompression |
| US6781529B1 (en) | 2002-10-24 | 2004-08-24 | Apple Computer, Inc. | Methods and apparatuses for variable length encoding |
| US8107885B2 (en) * | 2002-10-30 | 2012-01-31 | Motorola Mobility, Inc. | Method and apparatus for providing a distributed architecture digital wireless communication system |
| US20040120404A1 (en) * | 2002-11-27 | 2004-06-24 | Takayuki Sugahara | Variable length data encoding method, variable length data encoding apparatus, variable length encoded data decoding method, and variable length encoded data decoding apparatus |
| US6867715B2 (en) | 2003-06-25 | 2005-03-15 | Broadcom Corporation | System, method, and apparatus for variable length decoder |
| GB0315152D0 (en) * | 2003-06-28 | 2003-08-06 | Ibm | Data parsing and tokenizing apparatus,method and program |
| GB0323284D0 (en) * | 2003-10-04 | 2003-11-05 | Koninkl Philips Electronics Nv | Method and apparatus for processing image data |
| US7594098B2 (en) | 2005-07-01 | 2009-09-22 | Stmicroelectronics, Sa | Processes and devices for compression and decompression of executable code by a microprocessor with RISC architecture and related system |
| JP2007043595A (en) * | 2005-08-05 | 2007-02-15 | Nec Corp | Variable length code decoding method and device and data decompression device |
| US7180433B1 (en) * | 2005-09-22 | 2007-02-20 | Tandberg Storage Asa | Fast data compression and decompression system and method |
| US7665015B2 (en) * | 2005-11-14 | 2010-02-16 | Sun Microsystems, Inc. | Hardware unit for parsing an XML document |
| WO2007091367A1 (en) * | 2006-02-06 | 2007-08-16 | Matsushita Electric Industrial Co., Ltd. | Image decoding apparatus and image decoding method |
| US8731051B1 (en) * | 2006-02-10 | 2014-05-20 | Nvidia Corporation | Forward and inverse quantization of data for video compression |
| SE531398C2 (en) * | 2007-02-16 | 2009-03-24 | Scalado Ab | Generating a data stream and identifying positions within a data stream |
| JP4398987B2 (en) * | 2007-03-19 | 2010-01-13 | 株式会社東芝 | Multi-decoder device and method |
| US7538695B2 (en) | 2007-06-29 | 2009-05-26 | Rmi Corporation | System and method for deflate processing within a compression engine |
| US7492290B1 (en) | 2007-08-15 | 2009-02-17 | Red Hat, Inc. | Alternative encoding for LZSS output |
| US7900006B2 (en) | 2008-04-30 | 2011-03-01 | Netapp, Inc. | Maintaining checkpoints during backup of live system |
| US7692561B2 (en) * | 2008-07-17 | 2010-04-06 | International Business Machines Corporation | Method and apparatus for data decompression in the presence of memory hierarchies |
| US8244911B2 (en) * | 2008-07-22 | 2012-08-14 | International Business Machines Corporation | Method and apparatus for concurrent and stateful decompression of multiple compressed data streams |
| US7872598B2 (en) * | 2008-12-10 | 2011-01-18 | Intel Corporation | Accelerated decompression |
| US8013762B2 (en) | 2009-11-03 | 2011-09-06 | Seagate Technology Llc | Evaluating alternative encoding solutions during data compression |
| US8325069B2 (en) | 2009-12-22 | 2012-12-04 | Intel Corporation | System, method, and apparatus for a scalable processor architecture for a variety of string processing applications |
| US20110280314A1 (en) | 2010-05-12 | 2011-11-17 | Texas Instruments Incorporated | Slice encoding and decoding processors, circuits, devices, systems and processes |
| US20130103695A1 (en) * | 2011-10-21 | 2013-04-25 | Microsoft Corporation | Machine translation detection in web-scraped parallel corpora |
| US8824569B2 (en) | 2011-12-07 | 2014-09-02 | International Business Machines Corporation | High bandwidth decompression of variable length encoded data streams |
-
2011
- 2011-12-07 US US13/313,072 patent/US8824569B2/en active Active
-
2012
- 2012-07-23 US US13/555,547 patent/US8804852B2/en active Active
- 2012-11-12 GB GB1409981.6A patent/GB2512762B/en active Active
- 2012-11-12 JP JP2014545071A patent/JP5878644B2/en active Active
- 2012-11-12 DE DE112012004873.3T patent/DE112012004873B4/en active Active
- 2012-11-12 CN CN201280060474.4A patent/CN103975533B/en active Active
- 2012-11-12 WO PCT/CN2012/084440 patent/WO2013082990A1/en active Application Filing
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1154014A (en) * | 1995-10-19 | 1997-07-09 | 三星电子株式会社 | High-speed variable-length decoder |
| US6865668B1 (en) * | 1998-09-15 | 2005-03-08 | Trustees Of Columbia University In The City Of New York | Variable-length, high-speed asynchronous decoder circuit |
| US6310563B1 (en) * | 2000-05-12 | 2001-10-30 | International Business Machines Corporation | Method and apparatus for enhanced decompressor parsing |
| US20080022074A1 (en) * | 2002-06-25 | 2008-01-24 | Madduri Venkateswara R | Instruction Length Decoder |
Cited By (14)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109923516A (en) * | 2014-05-14 | 2019-06-21 | 卡拉公司 | Reinforce computer security, variable word length coding and the decoded technology of variable length code |
| CN107111623B (en) * | 2014-10-21 | 2020-04-03 | 华为技术有限公司 | Parallel history search and encoding for dictionary-based compression |
| CN107111623A (en) * | 2014-10-21 | 2017-08-29 | 华为技术有限公司 | Parallel historical search and coding for the compression based on dictionary |
| CN107925419A (en) * | 2015-09-25 | 2018-04-17 | 英特尔公司 | For system, the method and apparatus unziped it using hardware and software |
| CN107925420A (en) * | 2015-09-25 | 2018-04-17 | 英特尔公司 | Isomery for optimized compression ratio compresses framework |
| CN109716659A (en) * | 2016-07-22 | 2019-05-03 | 英特尔公司 | High-performance list stream LZ77 compress technique |
| CN109716659B (en) * | 2016-07-22 | 2024-02-27 | 英特尔公司 | High-performance uniflow LZ77compression technology |
| CN109937537A (en) * | 2016-11-18 | 2019-06-25 | 国际商业机器公司 | Coding Variable length symbol is to realize parallel decoding |
| CN109937537B (en) * | 2016-11-18 | 2023-05-30 | 国际商业机器公司 | Encoding variable length symbols to enable parallel decoding |
| CN112771498A (en) * | 2018-07-05 | 2021-05-07 | 米西克有限公司 | System and method for implementing an intelligent processing computing architecture |
| CN113474999A (en) * | 2019-02-27 | 2021-10-01 | 国际商业机器公司 | Overflowing temporary results to accommodate storage boundaries |
| CN114244373A (en) * | 2022-02-24 | 2022-03-25 | 麒麟软件有限公司 | LZ series compression algorithm coding and decoding speed optimization method |
| CN117220687A (en) * | 2023-03-01 | 2023-12-12 | 山东华科信息技术有限公司 | Data decompression method for distributed energy grid-connected monitoring |
| CN117220687B (en) * | 2023-03-01 | 2024-09-13 | 山东华科信息技术有限公司 | Data decompression method for distributed energy grid-connected monitoring |
Also Published As
| Publication number | Publication date |
|---|---|
| JP5878644B2 (en) | 2016-03-08 |
| DE112012004873B4 (en) | 2024-03-21 |
| DE112012004873T5 (en) | 2014-08-21 |
| GB2512762B (en) | 2019-12-11 |
| GB2512762A (en) | 2014-10-08 |
| GB201409981D0 (en) | 2014-07-16 |
| CN103975533B (en) | 2017-11-21 |
| US8824569B2 (en) | 2014-09-02 |
| US8804852B2 (en) | 2014-08-12 |
| US20130148745A1 (en) | 2013-06-13 |
| WO2013082990A1 (en) | 2013-06-13 |
| US20130147644A1 (en) | 2013-06-13 |
| JP2015505432A (en) | 2015-02-19 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN103975533A (en) | High bandwidth decompression of variable length encoded data streams | |
| JP5895545B2 (en) | Program, compressed file generation method, compression code expansion method, information processing apparatus, and recording medium | |
| WO2014106782A1 (en) | High bandwidth compression to encoded data streams | |
| CN103582883A (en) | Improved encoding and decoding of variable-length data with group formats | |
| US9094039B2 (en) | Efficient deflate decompression | |
| CN101610088A (en) | System and method for encoding data based on compression techniques with security features | |
| JP7425526B2 (en) | Reducing latch counts to save hardware space for dynamic Huffman table generation | |
| CN105740215A (en) | Data communication coding and decoding method | |
| JP2013541295A5 (en) | ||
| US7773005B2 (en) | Method and apparatus for decoding variable length data | |
| US8947272B2 (en) | Decoding encoded data | |
| TW201722088A (en) | Systems, methods, and apparatuses for decompression using hardware and software | |
| US9088297B2 (en) | High throughput decoding of variable length data symbols | |
| US20210203354A1 (en) | Compression and decompression engines and compressed domain processors | |
| US8868584B2 (en) | Compression pattern matching | |
| JP2019536367A (en) | Variable length symbol encoding to allow parallel decoding | |
| US9287893B1 (en) | ASIC block for high bandwidth LZ77 decompression | |
| CN109844750A (en) | Padding state determines | |
| US10678505B2 (en) | Subset encoding method: increasing pattern density for finite automata | |
| US9128758B2 (en) | Encoding densely packed decimals | |
| US10020819B1 (en) | Speculative data decompression | |
| JP2023055683A (en) | Data Encoding Method and Encoder and Data Decoding Method | |
| CN114070470A (en) | Encoding and decoding method and device | |
| CN104518850B (en) | Reference template is synchronized to the method and information processing system of data flow | |
| Liao et al. | SFVInt: Simple, Fast and Generic Variable-Length Integer Decoding using Bit Manipulation Instructions |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |