CN102404564A - Data compression and decompression using relative and absolute increament values - Google Patents
Data compression and decompression using relative and absolute increament values Download PDFInfo
- Publication number
- CN102404564A CN102404564A CN2011102649569A CN201110264956A CN102404564A CN 102404564 A CN102404564 A CN 102404564A CN 2011102649569 A CN2011102649569 A CN 2011102649569A CN 201110264956 A CN201110264956 A CN 201110264956A CN 102404564 A CN102404564 A CN 102404564A
- Authority
- CN
- China
- Prior art keywords
- data
- value
- packet
- stored
- item
- 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
- 238000013144 data compression Methods 0.000 title claims abstract description 8
- 230000006837 decompression Effects 0.000 title abstract description 8
- 238000000034 method Methods 0.000 claims description 34
- 239000000872 buffer Substances 0.000 claims description 20
- 230000004044 response Effects 0.000 claims description 17
- 238000004590 computer program Methods 0.000 claims description 2
- 238000007906 compression Methods 0.000 description 17
- 230000006835 compression Effects 0.000 description 17
- 230000000875 corresponding effect Effects 0.000 description 12
- 230000008569 process Effects 0.000 description 6
- 230000007246 mechanism Effects 0.000 description 3
- 230000003109 amnesic effect Effects 0.000 description 2
- 230000005540 biological transmission Effects 0.000 description 2
- 238000004364 calculation method Methods 0.000 description 2
- 230000002596 correlated effect Effects 0.000 description 2
- 238000012986 modification Methods 0.000 description 2
- 230000004048 modification Effects 0.000 description 2
- 241001522296 Erithacus rubecula Species 0.000 description 1
- 230000008859 change Effects 0.000 description 1
- 230000001276 controlling effect Effects 0.000 description 1
- 238000010586 diagram Methods 0.000 description 1
- 238000005538 encapsulation Methods 0.000 description 1
- 230000006870 function Effects 0.000 description 1
- 206010027175 memory impairment Diseases 0.000 description 1
- 238000007619 statistical method Methods 0.000 description 1
Images
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- 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
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
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)
- Data Exchanges In Wide-Area Networks (AREA)
- Information Transfer Between Computers (AREA)
- Compression Or Coding Systems Of Tv Signals (AREA)
Abstract
The present invention relates to data compression and decompression using relative and absolute delta values. Data compressor comprises a data input end for receiving data flow; an increament values calculator generating copressed data value, receiving a plurality of data items, accessing a data warehouse to determine whether related data items are stored in the data warehouse, obtaining related data items from the data warehouse and calsulating and outputting increament value from the received data items and the related data items for storing, and calsulating and outputting increament value from the received data items and predetermined values; a data warehouse; and a data warehouse controller controlling the storing of the data items, accessing the data warehouse to determine whether the storing positions are distributed for the data items, if yes, the data items are stored in the positions, if no, the storing positions are distributed, the data stored in the storing positions are removed and recovered, and the data itmes are stored in the distributed storing positions. Also disclsoed is a data decompressor used for compressed data.
Description
Technical Field
The present invention relates to the field of data compression and decompression in data processing.
Background
As the processing power of modern processors increases, the amount of data they can process increases. The transmission of such increased amounts of data between different devices presents its own problems, and various different compression mechanisms have been utilized to address these problems. These compression mechanisms allow data to be compressed into a more compact form before transmission and then decompressed on reception where it is needed.
One method of compressing data is delta compression. It has been found that in a data stream representing an image as it is to be displayed, in general, the difference between two adjacent data items is rather small, and therefore it is more efficient to transmit only the first data item and then transmit a value representing the difference from the previous value, rather than transmitting each data item. If the values are similar, it is clear that less data can be sent in this way.
However, problems can arise when graphics data, such as data with different tiles (tiles) from the screen in any order, is being sent in a stream. By its nature, delta compression is only efficient if the data items for which the deltas are calculated are similar. Thus, in a graphical data stream, deltas should be computed between related data items (e.g., those data contiguous in a data set). These values may not appear in data stream summaries that are close to each other, and therefore, in order to calculate the delta value, a data warehouse is needed to store the previously received data items. There are thousands of data sets that can be accessed in any order, and the required correlation values may not be stored unless a very large amount of previously received data is stored.
Disclosure of Invention
Viewed from a first aspect, the present invention provides a data compressor for receiving a data stream comprising a plurality of data items and for outputting the compressed data stream, said data compressor comprising: a data input for receiving the data stream; a delta value calculator for generating a compressed delta value, the delta value calculator configured to receive the plurality of data items from the data input and to access a data repository for at least some of the received data items to determine whether a related one of the received data items is stored in the data repository, and: responsive to the related data item being stored, retrieving the related data item from the data repository and calculating an incremental value from the received data item and the related data item and outputting the incremental value; and in response to the associated data item not being stored in the data store, calculating an increment value from the received data item and a predetermined value and outputting the increment value; the data repository for storing the plurality of data items received at the data input; the data compressor further comprises: a data warehouse controller for controlling storage of the plurality of data items in the data warehouse, the data warehouse controller being configured to access the data warehouse in response to receiving a data item at the data input and to determine whether a storage location is allocated for the data item, and: if so, storing the data item in the allocated storage location; and if not, allocating a storage location for the data item, reclaiming and discarding any data stored in the allocated storage location, and storing the data item in the allocated storage location.
The present invention recognizes that with certain data streams, there may be data items received in any order, such that adjacent values are not related to each other in a data set or object. Forming a delta value between data items is only suitable for compressing received data streams where two data items are similar to each other and generally occurs as they relate to each other, possibly abutting in the data set. However, if the data stream comprises data items received in an arbitrary order, adjacent data items in the data stream will be irrelevant. In order to be able to form delta values between data items that are related to each other in a data set, a data warehouse is needed to store previously received values, so that when a new value is received, the related value can be retrieved from the data warehouse and the corresponding delta value calculated. However, if the data stream includes many data items received in any order, the data warehouse needs to be large in order to ensure that there are stored correlation values.
If the data warehouse is a quickly accessible data warehouse, such as a cache, it is expensive in terms of area and it is not advantageous to have a very large data warehouse. If a smaller data warehouse and cheaper memory are used, the latency of the system will depend on whether the relevant data items need to be retrieved from memory, and this will mean that the latency of the system is not constant, but depends on the actual data items retrieved, so there cannot be a constant throughput of input data.
The present invention solves this problem by allowing the "delta value" to be calculated from a predetermined value at which no relevant data item is stored. Thus, when a new data item is received, it is determined whether a related data item is stored, and if so, an incremental value is calculated from the related value. If not, however, the delta value is calculated only with respect to a predetermined stored value. The value may be zero (in which case the actual data item is the output) or may be a statistical average calculated over the data items. This allows the delta value to be calculated with the same delay regardless of whether there is a stored correlation value. Thus, there may be a constant throughput of data, and only in certain cases (where no relevant data items are stored) will the data not be compressed, or will the data not be compressed very well.
The data warehouse is a forgetful type of warehouse, and therefore, when a new data item is received, it is determined whether a storage location is allocated thereto. If so, the value is stored in that location, and if not, another storage location is reclaimed, the data is discarded, and the new value is stored there. This is possible because the system is able to process related data items that are not stored, therefore, overwriting the stored values will not generate errors, which may only result in compression of future values not being performed so efficiently.
It should be noted that, in general, the delta value is calculated as the difference between the received data item and its associated value or a predetermined value. This difference may be a simple subtraction or it may be another method of determining the difference between the two values.
In some embodiments, each of the plurality of data items in the data stream is classified as belonging to one of a plurality of data objects, each of the data objects comprising a plurality of data items stored in the data warehouse including an identifier associated therewith identifying the data object, wherein the data warehouse controller is configured to assign the storage location to the data object in the data warehouse.
Embodiments of the present invention are particularly applicable to data streams having several data objects. When there are multiple data objects, data items within the same data object will be related to each other, while those data items in other data objects will generally not be related to each other. Thus, if adjacent data items in the data stream are from different data objects, forming delta values between them will not compress the data. Thus, it is convenient if a data item can be identified as belonging to a data object and the data warehouse assigns a storage location to the data object. Accordingly, relevant values in the data warehouse may be identified from these identifiers, and corresponding deltas calculated. If the data stream has a well-defined format, each of the data items in the data stream will not necessarily have an identifier bit, but can be identified as belonging to a particular data object from a location in the data stream and possibly from a single identifier bit of that data object.
In some embodiments, the data item and the related data item belong to the same data object, such that the data controller is configured to store the data item in the storage location allocated to the same data object and to reclaim and discard the related data item in response to determining that the related data item is stored in the data repository and retrieving the related data item for use in calculating the delta value.
In some embodiments, storage locations are allocated to data objects, so when a data item is received, if a storage location in the data warehouse has already been allocated to the data object, the associated data item will be stored in the data warehouse, and an increment may be calculated from the associated data item, when this has been completed, the received data item may be stored in the allocated storage location, and the stored data item may be reclaimed and discarded. Once the correlation value has possession of the calculated delta, it is no longer needed and, therefore, it is overwritten by the correlated value that will be correlated with the next data item received from the same data object.
In some embodiments, each of the data objects comprises a plurality of data portions, each of the data portions comprising a plurality of adjacent data items in the data stream, the data warehouse controller configured to store a data portion in one of the storage locations allocated to the corresponding data object.
In some embodiments, the data warehouse controller is configured to, in response to receiving a first data item of one of the data portions, determine whether a data portion from the same data object is stored in a storage location of the data warehouse, such that the storage location is assigned to the data object, and: if so, calculating a delta value from at least one data item in the received data portion and at least one associated data item in the stored data portion using the delta value calculator, then reclaiming the stored data portion from the allocated storage location and storing the received data portion in the allocated storage location; and, if not, reclaiming and discarding data from one of the storage locations and assigning the storage location to the data object and storing the data portion in the assigned storage location.
When a new data portion is received, the data warehouse controller checks to see if data portions from the same data object are stored in the data reference, and if so, at least one of the data items in the data portion will be used to form a delta with the corresponding data item in the received data portion, and the received data portion will overwrite the previously stored data portion.
In some embodiments, the data stream includes data portions with adjacent data items, and the data warehouse controller stores the entire data portion in each storage location assigned to the particular data object.
In some embodiments, for at least one of the data items, the related data items comprise data items in the same data portion.
Deltas are calculated from related data items in different data portions but in the same data object. Deltas may also be calculated within the data portion so that data items within the data portion may be related and the delta value between them will be a compressed version thereof.
In some embodiments, for at least one of the data items, the related data item comprises a data item from a corresponding position in a previously received data portion belonging to the same data object.
Related data items may also be corresponding data items from the same data object but from different data parts. In this way, data portions may be linked to one another, and different data items in the data portions may be linked by these incremental values. The data may then be compressed as appropriate and decompressed from the received values.
In some embodiments, the data items belonging to the same data object and identified by the identifier are assigned to the same destination.
While a data object may be a plurality of different data sets provided that include data that are related to each other in some way, in some embodiments it is a data set that is designated to a particular destination.
In some embodiments, the at least one data stream comprises at least one graphics data stream, the data object comprises a list of graphics commands for drawing a map in a graphics display, the data portion comprises one of the graphics commands, and the data item comprises a field within the graphics command.
With embodiments of the present invention, graphics data streams are particularly well suited for compression. The graphical display is formed from a list of tiles, each of which is drawn using a list of graphical commands. Thus, the lists of graphics commands used to draw the maps are related to each other, and incremental values may be formed between the lists of the same maps and between fields within the commands. However, forming delta values between lists of different maps will generally not provide compression of the data. Thus, such a graphics data stream will have many data items that are related to each other and many data items that are not related to each other, and the data items will be arranged in any order. Embodiments of the present invention utilize amnestic data repositories and allow compression with absolute values, which allows for constant throughput of such different data even if no relevant data items are stored.
While the data store may be many things, in some embodiments it includes a data cache. A buffer is a convenient way of storing data that can be accessed quickly and easily. It is expensive in area and therefore of limited size, but the use of an amnesic buffer and allowing data items to be calculated irrespective of whether the correlation values are stored means that buffers of reasonable size can be used and the compressor will still function correctly.
If the cache is a data store, each row of the data store, which is assigned to store a data object, has an identification value for identifying the data object.
In some implementations, the data object includes a list of graphics commands for drawing a hierarchical layer of a map in a graphics screen, wherein the data warehouse controller is configured to determine, in response to receiving a first data item of one of the data portions, whether a data portion from the same data object is stored in a storage location of the data warehouse, and, in response to determining that the same data object is not stored in a storage location of the data warehouse, identifying data objects from the same map but at different hierarchical levels, and calculating, with the delta value calculator, at least one delta value from at least one data item in the received data portion and at least one related data item in the stored data portion, and outputting the delta value with an indication identifying a source of the related data item.
If the data stream includes data for a hierarchical graphical display, the correlation values used to form the deltas may come from different hierarchical layers of the same map. This will result in compression, but decompression will also be allowed, since the previous layer will always be received at the decompressor when the delta value is received.
A second aspect of the present invention provides a data formatter comprising: an input for receiving a value output by the data compressor; formatting circuitry configured to encapsulate the output value into a fixed-size data packet, the data packet having one of a plurality of formats, each of the formats being identified by an identifier bit within the data packet; and an output for outputting the data packet; wherein one of the plurality of formats comprises an extended format for extending a capacity of a data packet by storing a portion of an output value that is too large to be stored in the data packet, the formatting circuit being responsive to receiving the output value that is too large to be stored in the data packet to split the output value between the data packet and at least one further packet having the extended format and outputting the data packet and the at least one extended data packet at the output.
Some data compressors, in particular the data compressor of the first aspect of the invention, are capable of compressing certain data items particularly efficiently, while others are not compressed well and, sometimes, are not compressed at all. When formatting the data to send it further, it is difficult to do so efficiently, since the size of the data representing the data items may be very different. If data packets with different lengths are used, encoding is required to indicate the beginning and end of each data packet. Alternatively, constant length data packets may be used, but this may result in inefficient encapsulation of data due to the variable length of any data transmitted. When transmitting uncompressed data, a packet large enough to accommodate the uncompressed data will have much empty space. The present invention solves this problem by providing a constant data packet length so that no bits need to be used to indicate the length, or start and end, of the packet. The data packets have one of a plurality of formats, which are identified by identifier bits. One of the formats is an extended format, such that if the storage capacity of a data packet is too small to store an output value, a portion of that value may be arranged in one or more extended format packets. In this way, data packets having a size suitable for storing one or more uncompressed data items can be used, and if it is desired to transmit a larger value that is not efficiently compressed, it can still be transmitted with these expanded data packets.
In some embodiments, the received values include at least some data compressed by an incremental compressor to form an incremental value, and the plurality of formats includes: a first format comprising an indication value for indicating whether a subsequent packet comprises a delta value relating to a predetermined value or, alternatively, a delta value comprising data relating to a previously received data item and at least a portion of at least one of said delta values; a second format comprising at least a portion of at least one of the delta values; and the extended format is for storing a portion of the at least one delta value that is too large to store in the second format.
Embodiments of the second aspect of the invention are particularly suitable for formatting data from the compressor of the first aspect of the invention. Thus, the data format packet can process the increment value associated with the other data item as well as the increment value obtained by subtracting the predetermined value. In this way, the compressed data output by the compressor of the first aspect of the invention may be stored in a constant length data packet and may be identified as an increment value associated with another data item or an increment value associated with a predetermined value, and in this way the compressed data may be later identified by the decompressor and may be reproduced.
In some embodiments, the indication value for the first format provides an indication of which previously received data items the delta value was calculated for.
In some embodiments, each of the formats includes an indication bit dedicated to storing the indication value and a bit dedicated to storing at least one data field, each of the received values including data of one of the at least one data field.
The format includes an indicator indicating the specific format and at least one data field that follows. Each data field is for storing at least a portion of an increment value.
In some embodiments, the data formatter is configured to output the data packet in the expanded format immediately before the data packet it expands.
An extended format packet is typically output before the packet it extends. Therefore, a plurality of extension packets can be output, and when another format packet is received, it is understood that the extension packets belong to the packet without any additional information. Thus, no start or end indicator is required.
A third aspect of the invention comprises a data compression system comprising a data compressor according to the first aspect of the invention coupled to a data formatter according to the second aspect of the invention.
A fourth aspect of the present invention provides a data decompressor comprising: an input for receiving a compressed data stream comprising a plurality of data packets of fixed size, each data packet storing a plurality of values, the data packet having one of a plurality of formats, each of the plurality of formats being identified by an identifier bit within the data packet, one of the plurality of formats comprising an extended format for storing a portion of at least one output value that is too large to be stored in the associated data packet; a data deformatter to identify the format of the data packets from the identifier bits and to combine data stored in at least one of the extension packets with data stored in the associated data packet; a data decompressor for decompressing said data.
A fifth aspect of the present invention provides a method of compressing data, comprising the steps of: receiving at a data input a data stream comprising a plurality of data items; accessing a data repository and determining whether data items related to the received data items are stored in the data repository, and: in response to storing the related data item, retrieving the related data item from the data repository and calculating a delta value comprising a difference between the received data item and the related data item and outputting the delta value; in response to the related data item not being stored in the data repository, calculating a delta value comprising a difference between the received data item and a predetermined value and outputting the delta value; accessing the data warehouse to determine whether a storage location is allocated to the received data item, and: if not, assigning a storage location in the data warehouse to the data item, and reclaiming and discarding data stored at the storage location; storing the data item in the allocated storage location.
A sixth aspect of the present invention provides a method of formatting compressed data, comprising: receiving a value output by the data compressor; encapsulating the output value into a fixed-size data packet, the data packet having one of a plurality of formats, each of the formats identified by an identifier bit within the data packet; and outputting the data packet; wherein one of the plurality of formats comprises an extended format for extending a capacity of a data packet by storing a portion of an output value that is too large to be stored in the data packet, the formatting circuit being responsive to receiving the output value that is too large to be stored in the data packet to split the output value between the data packet and at least one further packet having the extended format and outputting the data packet and the at least one extended data packet at the output.
A seventh aspect of the invention provides a method of compressing and formatting compressed data comprising the method of the fifth aspect of the invention followed by the method according to the sixth aspect of the invention.
An eighth aspect of the present invention provides a method of decompressing compressed data, comprising: receiving a compressed data stream comprising a plurality of data packets of fixed size, each data packet storing a plurality of values, the data packet having one of a plurality of formats, each of the plurality of formats being identified by an identifier bit within the data packet, the one of the plurality of formats comprising an extended format for storing a portion of at least one output value that is too large to be stored in the associated data packet; identifying the format of the data packet from the identifier bits; and combining data stored in at least one of the extension packets with data stored in the associated data packet; and decompresses the data.
A ninth aspect of the invention provides a computer program product operable, when run on a data processor, to control the data processor to perform the steps of the method according to the sixth, seventh or eighth aspect of the invention.
Drawings
The invention will be described, by way of example only, with reference to the accompanying drawings and illustrated embodiments, in which:
FIG. 1 illustrates a data compression system according to an embodiment of the present invention;
FIG. 2 illustrates a data decompression system according to an embodiment of the present invention;
FIG. 3 illustrates an amnesic type buffer according to an embodiment of the present invention;
FIG. 4 illustrates graphics commands compressed by an embodiment of the invention;
FIGS. 5 and 6 illustrate examples of formatted compressed data packets according to embodiments of the present invention;
FIG. 7 illustrates a flow diagram showing a method of compressing data according to an embodiment of the invention;
FIG. 8 illustrates a flow chart showing a method of compressing graphics data in a hierarchical graphical image display, in accordance with an embodiment of the present invention;
FIG. 9 illustrates a method of formatting data according to an embodiment of the present invention; and
fig. 10 illustrates a method of decompressing data according to an embodiment of the present invention.
Detailed Description
FIG. 1 illustrates a data compression system 10 according to an embodiment of the present invention. Data stream 5 is received at an input of system 10 and is then sent to a forgetting (forgetful) buffer 20 having a buffer controller 22 that controls storage within buffer 20. When a data item is received, the buffer controller 22 checks whether a value associated with the received data item is stored in the buffer 20, and if so, the value will be output to the delta compressor 30. Cache controller 22 will then check to see if any storage locations within cache 20 have been allocated for that particular data item. If allocated, it will store the data item in the allocated location and, if not, it will allocate a location to the data item and store the data item there, possibly overwriting another data item in the process. Selection of the data items for overlay can be accomplished in a variety of known ways, such as a round robin way.
The data items are sent to the delta compressor 30 and the buffer 20 in parallel. Thus, if data is already stored in the buffer 20, the delta compressor 30 receives the data items and (possibly) the related data items. The delta compressor 30 compresses the received data items by calculating the difference between the received data items and their associated values or the difference between the received item data and a predetermined value stored in the register 32 (if associated data is not stored). Register 32 may store any value. It may store 0, in which case the delta value calculated in respect of that value will actually be an uncompressed received data item, or, more generally, it will store a statistical average of the received data items. Thus, the output will be smaller, and therefore occupy fewer bits, typically by subtracting the average value from the received data item value. The output data is then sent to the data formatter 40.
The data formatter 40 has formatting circuitry 42 which looks at the received compressed data items and encapsulates them into constant size data packets. These data packets have different formats. There is a general command or packet that encodes several large but infrequently changing data fields and that has an indication bit that can be used to indicate whether a subsequent data item is in absolute or relative mode. The indication bit is used to indicate that the next packet includes an increment value relative to a predetermined value stored in the register 32 or that the next packet includes an increment value relative to the associated data item. By default all commands are related to previous commands, but the indication bit in the generic command can be used to re-bias (re-bias) the remaining current command to be related to a predetermined constant value. In this way, the formatter may output differently compressed data items received in constant size data packets. In order to be able to handle different sizes of these differently compressed values, there is also a primitive (native) packet that can encode the entire set of data items and an extension of these primitives, which allows to store additional values, which are not specifically compressed and which require additional space. In this way, the size of the data packet need not be large enough to include the worst case uncompressed data item, but may be the size that would include a general compressed data item, and the extension packet may be used to send the remainder of the value or values. These different formats are described in more detail in fig. 5.
Fig. 2 shows, in schematic form, a decompression system 50 according to an embodiment of the present invention. Constant size data packets 45 are received from the compression system 10 and the deformatter 60 identifies the format of each packet from the identifier within the packet, then combines the expanded packets with the packets to which they belong and reformulates the compressed data items. These are then placed into a decompressor 70 which performs the calculations necessary to generate the data stream 5 originally input into the compression system 10.
While the above decompression system is useful for all types of data streams, it is particularly useful for graphics data, where there are data maps formed as a list of commands for drawing a particular map. Thus, each map has a list of commands for drawing that particular map, and each command is sent as a plurality of contiguous data items with an identifier that identifies the map associated with the plurality of data items.
Fig. 3 shows the forgetting-type buffer 20 of fig. 1 storing such command data in more detail. Each line of the buffer stores graphics commands. There is a data object/list identifier associated with each command in the stream that identifies the map and command list associated with that command, and these identifiers are stored in the buffer as flags associated with the data items. These list identifiers are used to confirm whether the previous data item is already in the cache. In this example, each list or map has a row assigned to it, which is identified by an identifier in a flag (not shown). Thus, when a new command is received from the list, the value is retrieved for appropriate incremental calculations, and the newly received value is then stored in the line of the buffer assigned to that particular list.
In this regard, the rank level may be explicitly stored as part of the flag, or the map location and rank level may be mathematically combined into a single identifier field. Keeping the hierarchical levels separate makes it easier to perform the incrementing between lists for the same map but belonging to different hierarchical levels.
Fig. 4 shows the nature of such a command in more detail, so there may be input fields, a timestamp providing information of which command should be executed first, and different fields identified in the figure as index 1, index 2 and index 3, and these indices are related to different primitive commands, which may be commands for drawing a specific primitive. There is also an identifier that identifies which map the command relates to. Fig. 4 also shows how different fields are combined to form the delta. In this embodiment, deltas are formed between two fields within each command and between corresponding fields of commands from the same map. This is an efficient way to compress data because in each list of commands, the corresponding fields are likely to refer to similar vertex indices (vertex indices), and therefore, the corresponding fields within the command will be similar. Additionally, primitives drawn together may be of similar size and in similar screen coordinates, and therefore, likely end up in the same list. Primitive datasets are also typically optimized by software tools, so primitives submitted together for drawing are likely to have similar vertex indices and global states that change relatively infrequently.
Thus, in the illustrated example, inter-command compression and intra-command compression are used. The increment for index 3 is calculated from index 3 of the relevant command acquired from the buffer 20, and the increment for index 2 is calculated with respect to index 3, and the increment for index 1 is calculated from index 2. At start-up, or if no correlation value is stored, the increment for index 3 will be calculated with respect to the predetermined value stored in register 32 of FIG. 1.
FIG. 5 illustrates an example of some formats of data packets output by the data formatter 30. The data packets have an identifier that identifies which format they are. Thus, in this particular example, there is an extension identifier, a primitive identifier and a generic identifier, the packet being used to establish some infrequently changing global state and to indicate when the following packet is a delta value with respect to a predetermined value.
FIG. 6 shows an example compressed data flow with three data items being output (field A, field B, and field C). Field C has not been compressed well, while fields a and B have been compressed moderately, but not well. If all three values have been compressed well, they will just fit into a single primitive packet 80. However, because this is not the case, the extension packet 82 has been used to accommodate the extra bits of these fields. These extension packets have a common extension packet format and therefore require fewer identifier bits. The extension packet is received first and then the values are combined when the primitive is received.
Thus, the variable length encoding mechanism utilizes a small number of fixed length compressed packets to encode variable length data items of multiple data fields simultaneously. Specifically, in an embodiment of the invention, it uses four types of 32-bit packets to encode up to 198 bits per primitive. The different formats include a generic format that establishes some infrequently changing global state and allows the delta value in the decompressor to be optionally reset to deal with the forgetfulness of the buffer in the compressor, i.e. it can identify whether the delta in the immediately following packet is a relative delta or a delta with respect to an absolute value.
There is also a proprietary format (not shown) that provides high bits of a wide data item with few changes and there is a primitive format that can encode the entire primitive in a single command if the compressed value is small enough.
There is also a primitive extension format for extending the range of all data fields in the primitive format.
Common and proprietary formats are rarely used, and as such they do allow for efficient setup of a very wide range of data items and also allow for arbitrary resetting of delta compression in intermediate streams.
Primitive formats and primitive extension formats provide a novel way to efficiently encode the most frequently changed portions of a data stream. The number of bits allocated to each field in the format is fixed, but not necessarily an equivalent division of the available bits. The exact proportion of bits is determined by statistical analysis of a plurality of test data sets.
During compression, a delta value is calculated and the minimum number of bits required to encode each field is determined. If any field cannot be expressed in a single primitive format, as many bits as possible per field are arranged into an extension format that is then output. The remaining bits in the delta value are right-shifted by the number of bits output and the process is then repeated until all of the remaining bits will fit into the primitive command format that is then output.
Through this process, the variable length delta values for all delta fields are partitioned into zero or more such extended formats prior to a single primitive format. By outputting the most significant bits first, we do not need to encode the sequence end markers for these extended formats, or specify the number of extended formats that make up the fourth command. This saves storage bandwidth and, therefore, power, and allows for very simple hardware in both the compressor and decompressor.
It should be noted that instead of outputting the landmark identifier in a compressed command, the formatter splits the command list into different memory address regions, which avoids the need to decompress the list identifier.
Fig. 7 shows a flow chart illustrating a method of compressing data according to an embodiment of the invention. A data stream is received at a data compressor and each data portion comprising a number of data items is considered in turn. Delta values between different data items within the data portion are calculated and it is determined whether data parts from the same data object are stored in the data warehouse. If so, an incremental value between at least one of the stored data items and a corresponding data item in the received data portion is calculated. The received data portions are then stored in the data warehouse at the location where the data portions for the same data object are currently stored. The storage location has been allocated the data object and, therefore, is correctly allocated to the data portion. Additionally, if the data item of the data object requires a delta value to be calculated from the data portion of the same data object, the newly stored portion will include the required data item.
If a data portion from the same data object is not stored in the data warehouse, a delta value between at least one of the data items in the data portion and the stored constant is calculated. This step allows the data warehouse to not have to store all previously received data items. Calculating the delta value with the stored constants will generally not provide efficient compression of the value, but it does mean that the delta value can always be calculated without storing each received data item. The received data portion is then stored in a storage location in a data warehouse. Since there is no storage location assigned to the particular data object, it overwrites one of the data portions already stored in the data store, and then assigns the storage location to the new data object. When selecting which data portion to overwrite, the cache controller utilizes one of several known routines, such as determining which is the oldest data portion stored in the data warehouse.
It should be noted that although the steps are shown in the flowchart as being performed in this particular order, they may be performed in a different order such that the delta values in the data portions are calculated after the delta values between the data portions or for constants.
FIG. 8 illustrates a flow chart showing a method of compressing data for a hierarchical graphical display. A data portion in the form of a graphics command is received in a data stream for drawing a map portion. An incremental value between at least two of the received data items is calculated and it is determined whether data portions from the same data object and the same data level are stored in the data warehouse. In other words, whether there is another command from the same command list and the same level of the graphic map. If so, an incremental value between the stored data item and a corresponding data item in the received data portion is calculated. If there are no data portions from the same level and stored maps, a determination is made as to whether there are data portions from the same map but from different levels of the level. If so, a delta value is calculated from the stored portion. It has been found that calculating delta values between corresponding data items from the same map but from different hierarchical levels does in general provide good compression, and the probability of finding a previous value with which a delta can be formed increases. However, some indication needs to be output along with the compressed value indicating that it is associated with another hierarchical level. If there is no stored command for the map in the data warehouse at all, a delta value between the received data item and the stored constant is calculated and the received command is stored in a storage location in the data warehouse that is selected by some known method. In the case where a command from a map of the same data hierarchy level appears in the data warehouse, the command is overwritten by the newly received command. In the case where a command from a map of a different data level appears in the data warehouse, a row is assigned to the command if there is space or there are many newly unassigned rows when a delta has been calculated.
As with fig. 7, the steps of the method may be performed in a different order, where appropriate.
Fig. 9 shows a flow chart illustrating a method of formatting compressed data into data packets according to an embodiment of the invention. Compressed data is received and it is determined whether one or more values are delta values for another data item. If not, a general packet is used to indicate to the system that the delta value is formed with respect to a constant and includes the received compressed value, the value and the indication are encapsulated in the general packet, and if there is not enough space in the general packet, they are also encapsulated in a general extension packet. The other delta values associated therewith are then encapsulated into primitives and, if necessary, into extended packets of primitives. These delta values may be delta values associated with other data values, or some of them may be absolute values with respect to constants, in which case an indicator in the general packet would indicate it. The packet is then output as a generic packet, an extension of the generic packet (if extension is required), one or more extensions to the primitive packet (if extension is required), and a primitive packet indicating the end of the command packet associated therewith.
If the values are delta values formed with respect to another data value, a determination is made as to whether these values will fit into the primitive data packet. If so, it is encapsulated into the primitive data packet and output. If not, it is encapsulated into at least one primitive data packet extension, a primitive data packet and one or more extension packets, and then the primitive data packet is output. The output of the primitive packet indicates the end of the data of the command packet. Then, the received further values are considered.
Thus, the general packet provides an indication that the delta value is formed with respect to a constant, and in the absence of such a packet, it is assumed that all of the delta values are delta values with respect to another data value.
Fig. 10 shows a flow chart illustrating a method of decompressing data according to an embodiment of the invention. First, a compressed data stream comprising a plurality of data packets of a fixed size is received. Each packet is analyzed and the format of the packet is identified from the format identifier in the packet, and then it is determined exactly which data items are stored in the data packet. Different portions of the data item may be stored in multiple packets and these combined to form a compressed data item. Then, other increment values or absolute values to which they are related are determined, and then decompressed to generate original book data items.
Various further aspects and features of the present invention are defined in the appended claims. Various modifications may be made to the previous embodiments described herein without departing from the scope of the present invention.
Although illustrative embodiments of the invention have been described herein with reference to the accompanying drawings, it is to be understood that the invention is not limited to those precise embodiments, and that various changes and modifications may be effected therein by one skilled in the art without departing from the scope or spirit of the invention as defined by the appended claims.
Claims (26)
1. A data compressor for receiving a data stream comprising a plurality of data items and for outputting the compressed data stream, the data compressor comprising:
a data input for receiving the data stream;
a delta value calculator for generating a compressed delta value, the delta value calculator configured to receive the plurality of data items from the data input and to access a data repository for at least some of the received data items to determine whether a related one of the received data items is stored in the data repository, and:
responsive to the related data item being stored, retrieving the related data item from the data repository and calculating an incremental value from the received data item and the related data item and outputting the incremental value; and is
In response to the associated data item not being stored in the data store, calculating an increment value from the received data item and a predetermined value and outputting the increment value;
the data repository for storing the plurality of data items received at the data input;
the data compressor further comprises:
a data warehouse controller for controlling storage of the plurality of data items in the data warehouse, the data warehouse controller being configured to access the data warehouse in response to receiving a data item at the data input and to determine whether a storage location is allocated for the data item, and:
if so, storing the data item in the allocated storage location; and is
If not, a storage location is allocated for the data item, any data stored in the allocated storage location is reclaimed and discarded, and the data item is stored in the allocated storage location.
2. The data compressor of claim 1, wherein the plurality of data items in the data stream are each classified as belonging to one of a plurality of data objects, the data objects each comprising a plurality of data items stored in the data warehouse including an identifier associated therewith identifying the data object, wherein
The data warehouse controller is configured to assign the storage locations in the data warehouse to the data objects.
3. The data compressor of claim 2, wherein the data item and the related data item belong to a same data object, such that in response to determining that the related data item is stored in the data warehouse and retrieving the related data item for calculating the delta value, the data controller is configured to store the data item in the storage location allocated to the same data object, and to reclaim and discard the related data item.
4. The data compressor of claim 2, wherein each of the data objects includes a plurality of data portions, each of the data portions including a plurality of adjacent data items in the data stream, the data warehouse controller configured to store one data portion in one of the storage locations allocated to the corresponding data object.
5. A data compressor as claimed in claim 4, wherein for at least one of the data items the related data items comprise data items within the same data portion.
6. A data compressor as claimed in claim 4, wherein for at least one of the data items the related data item comprises a data item from a corresponding position in a previously received data portion belonging to the same data object.
7. The data compressor of claim 6, wherein the data warehouse controller is configured to, in response to receiving a first data item of one of the data portions, determine whether a data portion from the same data object is stored in a storage location of the data warehouse such that the storage location is assigned to the data object, and:
if so, calculating a delta value from at least one data item in the received data portion and at least one associated data item in the stored data portion using the delta value calculator, then reclaiming the stored data portion from the allocated storage location and storing the received data portion in the allocated storage location; and is
If not, data is retrieved and discarded from one of the storage locations, the storage location is assigned to the data object, and the data portion is stored in the assigned storage location.
8. A data compressor as claimed in claim 2, wherein the data items belonging to the same data object and identified by the identifier are designated to the same destination.
9. The data compressor of claim 2, wherein the at least one data stream comprises at least one graphics data stream, the data object comprises a list of graphics commands for drawing a map in a graphics display, the data portion comprises one of the graphics commands, and the data item comprises a field within the graphics command.
10. The data compressor of claim 1, wherein the data warehouse comprises a data buffer.
11. The data compressor of claim 2, wherein the data store comprises a data buffer, and wherein each row of the data buffer comprises a store for storing an identification value for identifying the data object for which the row is allocated to store.
12. The data compressor of claim 11, wherein each of said data objects comprises a plurality of data portions, each said data portion comprising a plurality of adjacent data items in said data stream, said data warehouse controller configured to store a data portion in one of said storage locations allocated to said corresponding data object; and is
For at least one of the data items, the related data item comprises a data item from a corresponding position in a previously received data portion belonging to the same data object; and is
The data object includes a list of graphics commands for drawing a hierarchical layer of a map in a graphics screen, wherein the data warehouse controller is configured to determine, in response to receiving a first data item of one of the data portions, whether a data portion from a same data object is stored in a storage location of the data warehouse, and, in response to determining that the same data object is not stored in a storage location of the data warehouse, identifying data objects from the same map but at different hierarchical levels, and calculating at least one delta value using said delta value calculator said at least one data item in the received data portion and at least one related data item in the stored data portion, and outputting said delta value together with an indication identifying the source of said related data item.
13. A data formatter, comprising:
an input for receiving a value output by the data compressor;
formatting circuitry configured to encapsulate the output value into a fixed-size data packet, the data packet having one of a plurality of formats, each of the formats being identified by an identifier bit within the data packet; and
an output for outputting the data packet; wherein,
one of the plurality of formats includes an extended format for extending a capacity of a data packet by storing a portion of an output value that is too large to be stored in the data packet, the formatting circuit responsive to receiving the output value that is too large to be stored in the data packet to split the output value between the data packet and at least one further packet having the extended format and outputting the data packet and the at least one extended data packet at the output.
14. The data formatter of claim 13, wherein the received values comprise at least some data compressed by an delta compressor to form delta values, and wherein the plurality of formats comprises:
a first format comprising an indication value for indicating whether a subsequent packet comprises a delta value relating to a predetermined value or a delta value comprising data relating to a previously received data item, and at least a portion of at least one of the delta values;
a second format including at least a portion of at least one of the delta values; and is
The extended format is used to store a portion of the at least one delta value that is too large to store in the second format.
15. The data formatter of claim 14, wherein the indication value for the first format provides an indication of which data item the delta value was calculated with respect to previously received.
16. The data formatter of claim 13, wherein each of the formats comprises an indication bit dedicated to storing the indication value and a bit dedicated to storing at least one data field, each of the received values comprising data of one of the at least one data field.
17. The data formatter of claim 13, wherein the data formatter is configured to output data packets having the expanded format immediately prior to the data packets that it expands.
18. A data compression system comprising a data compressor according to claim 1 coupled to a data formatter, said data formatter comprising:
an input for receiving a value output by the data compressor;
formatting circuitry configured to encapsulate the output value into a fixed-size data packet, the data packet having one of a plurality of formats, each of the formats being identified by an identifier bit within the data packet; and
an output for outputting the data packet; wherein,
one of the plurality of formats comprises an extended format for extending a capacity of a data packet by storing a portion of an output value that is too large to be stored in the data packet, the formatting circuit responsive to receiving the output value that is too large to be stored in the data packet to split the output value between the data packet and at least one further packet having the extended format and outputting the data packet and the at least one extended data packet at the output; wherein,
the received values include at least some data compressed by an increment compressor to form an increment value, and the plurality of formats includes:
a first format comprising an indication value for indicating whether a subsequent packet comprises a delta value relating to a predetermined value or a delta value comprising data relating to a previously received data item, and at least a portion of at least one of the delta values;
a second format including at least a portion of at least one of the delta values; and is
The extended format is used to store a portion of the at least one delta value that is too large to store in the second format.
19. A data decompressor, comprising:
an input for receiving a compressed data stream comprising a plurality of data packets of fixed size, each data packet storing a plurality of values, the data packet having one of a plurality of formats, each of the plurality of formats being identified by an identifier bit within the data packet, one of the plurality of formats comprising an extended format for storing a portion of at least one output value that is too large to be stored in the associated data packet;
a data deformatter to identify the format of the data packets from the identifier bits and to combine data stored in at least one of the extension packets with data stored in the associated data packet;
a data decompressor for decompressing said data.
20. The data decompressor according to claim 19, wherein at least some of said data packets comprise data compressed by an increment compressor to form an increment value, and said plurality of formats comprises:
a first format comprising an indication value for indicating whether a subsequent packet comprises a delta value relating to a predetermined value or a delta value comprising data relating to a previously received data item, and at least a portion of at least one of the delta values;
a second format including at least a portion of at least one of the delta values; and is
The extended format is to store a portion of the delta value that is too large to store in the second format; wherein,
each of the formats comprising bits dedicated to storing the indication value and bits dedicated to storing at least one data field;
the data deformatter is configured to extract an increment value from the packets in the first format, the second format, and the extended format, and
the data decompressor is configured to form an original data item from the extracted delta value and the predetermined value.
21. A method of compressing data, comprising the steps of:
receiving at a data input a data stream comprising a plurality of data items;
accessing a data repository and determining whether data items related to the received data items are stored in the data repository, and:
in response to storing the related data item, retrieving the related data item from the data repository and calculating a delta value comprising a difference between the received data item and the related data item and outputting the delta value;
in response to the related data item not being stored in the data repository, calculating a delta value comprising a difference between the received data item and a predetermined value and outputting the delta value;
accessing the data warehouse to determine whether a storage location is allocated to the received data item, and:
if not, assigning a storage location in the data warehouse to the data item, and reclaiming and discarding data stored at the storage location;
storing the data item in the allocated storage location.
22. The method of compressing data of claim 21, wherein each of the plurality of data items in the data stream is classified as belonging to one of a plurality of data objects, each of the data objects including a plurality of data items, each storage location in the data warehouse being assigned to one of the data objects and including an identifier that identifies the data object, such that in response to the related data item being stored in the data warehouse, the data item is stored in the storage location assigned to the related data item, and the related data item is reclaimed and discarded.
23. A method of formatting compressed data, comprising:
receiving a value output by the data compressor;
encapsulating the output value into a fixed-size data packet, the data packet having one of a plurality of formats, each of the formats identified by an identifier bit within the data packet; and
outputting the data packet; wherein,
one of the plurality of formats includes an extended format for extending a capacity of a data packet by storing a portion of an output value that is too large to be stored in the data packet, the formatting circuit responsive to receiving the output value that is too large to be stored in the data packet to split the output value between the data packet and at least one further packet having the extended format and outputting the data packet and the at least one extended data packet at the output.
24. A method of compressing and formatting compressed data, comprising the method of claim 21, followed by a method of formatting compressed data, the method of formatting compressed data comprising:
receiving a value output by the data compressor;
encapsulating the output value into a fixed-size data packet, the data packet having one of a plurality of formats, each of the formats identified by an identifier bit within the data packet; and
outputting the data packet; wherein,
one of the plurality of formats includes an extended format for extending a capacity of a data packet by storing a portion of an output value that is too large to be stored in the data packet, the formatting circuit responsive to receiving the output value that is too large to be stored in the data packet to split the output value between the data packet and at least one further packet having the extended format and outputting the data packet and the at least one extended data packet at the output.
25. A method of decompressing compressed data, comprising:
receiving a compressed data stream comprising a plurality of data packets of fixed size, each data packet storing a plurality of values, the data packet having one of a plurality of formats, each of the plurality of formats being identified by an identifier bit within the data packet, the one of the plurality of formats comprising an extended format for storing a portion of at least one output value that is too large to be stored in the associated data packet;
identifying the format of the data packet from the identifier bits; and is
Combining data stored in at least one of the extension packets with data stored in the associated data packet; and is
The data is decompressed.
26. A computer program product operable, when run on a data processor, to control the data processor to perform the steps of the method of claim 21.
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| GB1014625.6A GB2483282B (en) | 2010-09-03 | 2010-09-03 | Data compression and decompression using relative and absolute delta values |
| GB1014625.6 | 2010-09-03 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN102404564A true CN102404564A (en) | 2012-04-04 |
| CN102404564B CN102404564B (en) | 2016-08-17 |
Family
ID=43013600
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201110264956.9A Active CN102404564B (en) | 2010-09-03 | 2011-09-05 | Utilize the relative and data compression and decompression of absolute increment value |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US8548962B2 (en) |
| JP (1) | JP5781867B2 (en) |
| CN (1) | CN102404564B (en) |
| GB (1) | GB2483282B (en) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107193642A (en) * | 2016-03-14 | 2017-09-22 | 阿里巴巴集团控股有限公司 | Task data compression switching method, suitable compression degree evaluation method and relevant apparatus |
| CN112241013A (en) * | 2019-07-01 | 2021-01-19 | 英飞凌科技股份有限公司 | Extended delta encoding technique for light detection and ranging raw data compression |
| CN113227957A (en) * | 2018-11-29 | 2021-08-06 | 超威半导体公司 | Aggregating commands in a stream based on cache line addresses |
Families Citing this family (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8032714B2 (en) * | 2007-09-28 | 2011-10-04 | Aggregate Knowledge Inc. | Methods and systems for caching data using behavioral event correlations |
| US20120185612A1 (en) * | 2011-01-19 | 2012-07-19 | Exar Corporation | Apparatus and method of delta compression |
| US11336295B2 (en) * | 2011-09-13 | 2022-05-17 | Exagrid Systems, Inc. | Systems and methods for version chain clustering |
| US9146870B2 (en) | 2013-07-24 | 2015-09-29 | Arm Limited | Performance of accesses from multiple processors to a same memory location |
| US10063422B1 (en) * | 2015-12-29 | 2018-08-28 | Amazon Technologies, Inc. | Controlled bandwidth expansion in compressed disaggregated storage systems |
| US10055135B2 (en) * | 2016-08-18 | 2018-08-21 | Intel Corporation | Method and apparatus for compressing a data set using incremental deltas and a variable reference value |
| US10411730B2 (en) * | 2017-04-18 | 2019-09-10 | Delphi Technologies Ip Limited | Data compression system for storing data from an automated vehicle |
| US10419022B2 (en) | 2017-11-30 | 2019-09-17 | International Business Machines Corporation | Run-length base-delta encoding for high-speed compression |
| US11321292B2 (en) | 2020-08-31 | 2022-05-03 | Chicago Mercantile Exchange Inc. | Accumulation-based data object processing |
Citations (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5832490A (en) * | 1996-05-31 | 1998-11-03 | Siemens Medical Systems, Inc. | Lossless data compression technique that also facilitates signal analysis |
| US20030090740A1 (en) * | 2001-11-14 | 2003-05-15 | International Business Machines Corporation | Raster data compression apparatus and method |
| CN1658665A (en) * | 2004-02-17 | 2005-08-24 | 索尼株式会社 | Memory management method, image processing apparatus, and memory management program |
| US20060161963A1 (en) * | 2005-01-17 | 2006-07-20 | Samsung Electronics Co., Ltd. | Display apparatus and control method thereof |
| US20060227250A1 (en) * | 2003-07-18 | 2006-10-12 | Mauro Barbieri | Detecting a content item in a digital video stream |
| US20080129748A1 (en) * | 2003-11-19 | 2008-06-05 | Reuven Bakalash | Parallel graphics rendering system supporting parallelized operation of multiple graphics processing pipelines within diverse system architectures |
| US20100125553A1 (en) * | 2008-11-14 | 2010-05-20 | Data Domain, Inc. | Delta compression after identity deduplication |
Family Cites Families (56)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| FR2683648B1 (en) * | 1991-11-12 | 1996-12-13 | Apple Computer | METHOD FOR CHOOSING OBJECTS IN A MOVING IMAGE SEQUENCE AND CORRESPONDING SUCCESS TEST TRACK |
| TW224553B (en) * | 1993-03-01 | 1994-06-01 | Sony Co Ltd | Method and apparatus for inverse discrete consine transform and coding/decoding of moving picture |
| JP2830750B2 (en) * | 1994-02-24 | 1998-12-02 | 日本電気株式会社 | Image multipoint communication control device, image communication terminal, and image communication system |
| JP3495800B2 (en) * | 1994-12-28 | 2004-02-09 | キヤノン株式会社 | Encoding device and method |
| JPH08307860A (en) * | 1995-04-28 | 1996-11-22 | Toshiba Corp | Scene re-encoding device |
| JPH0993592A (en) * | 1995-07-13 | 1997-04-04 | Matsushita Electric Ind Co Ltd | Image coding device |
| US5793371A (en) * | 1995-08-04 | 1998-08-11 | Sun Microsystems, Inc. | Method and apparatus for geometric compression of three-dimensional graphics data |
| US5724033A (en) * | 1996-08-09 | 1998-03-03 | Digital Equipment Corporation | Method for encoding delta values |
| WO2000068946A1 (en) * | 1999-05-07 | 2000-11-16 | Kabushiki Kaisha Toshiba | Data structure of stream data, and method of recording and reproducing stream data |
| JP2000331421A (en) * | 1999-05-17 | 2000-11-30 | Victor Co Of Japan Ltd | Information recorder and information recording device |
| US6879634B1 (en) * | 1999-05-26 | 2005-04-12 | Bigband Networks Inc. | Method and system for transmitting media streams over a variable bandwidth network |
| JP2001127644A (en) * | 1999-10-29 | 2001-05-11 | Toshiba Corp | Computer-readable recording medium recording transfer data conversion device and program |
| US6678417B1 (en) * | 1999-11-30 | 2004-01-13 | International Business Machines Corporation | Dictionary based video compression |
| US7587467B2 (en) * | 1999-12-02 | 2009-09-08 | Western Digital Technologies, Inc. | Managed peer-to-peer applications, systems and methods for distributed data access and storage |
| US7116717B1 (en) * | 1999-12-15 | 2006-10-03 | Bigband Networks, Inc. | Method and system for scalable representation, storage, transmission and reconstruction of media streams |
| US7061936B2 (en) * | 2000-03-03 | 2006-06-13 | Ntt Docomo, Inc. | Method and apparatus for packet transmission with header compression |
| US6523102B1 (en) * | 2000-04-14 | 2003-02-18 | Interactive Silicon, Inc. | Parallel compression/decompression system and method for implementation of in-memory compressed cache improving storage density and access speed for industry standard memory subsystems and in-line memory modules |
| US6748520B1 (en) * | 2000-05-02 | 2004-06-08 | 3Com Corporation | System and method for compressing and decompressing a binary code image |
| US7471298B1 (en) * | 2000-06-26 | 2008-12-30 | S3 Graphics Co., Ltd. | Fetching pixel data with reduced memory bandwidth requirement |
| US6961927B1 (en) * | 2000-11-27 | 2005-11-01 | Microsoft Corporation | Lossless, context-free compression system and method |
| JP3737705B2 (en) * | 2001-02-20 | 2006-01-25 | インターナショナル・ビジネス・マシーンズ・コーポレーション | Network system, server, client, communication method, and communication program |
| US7042948B2 (en) * | 2001-03-05 | 2006-05-09 | Intervideo, Inc. | Systems and methods for management of data in a ring buffer for error resilient decoding of a video bitstream |
| US6719689B2 (en) * | 2001-04-30 | 2004-04-13 | Medtronic, Inc. | Method and system for compressing and storing data in a medical device having limited storage |
| US7379472B2 (en) * | 2001-09-27 | 2008-05-27 | Broadcom Corporation | Hardware filtering of unsolicited grant service extended headers |
| US7231456B1 (en) * | 2001-10-10 | 2007-06-12 | Cisco Technology, Inc. | 32-bit vendor-extended-type vendor specific attribute |
| US7283265B2 (en) * | 2001-11-14 | 2007-10-16 | Infoprint Solutions Company | Raster data compression apparatus and method |
| AUPR890201A0 (en) * | 2001-11-16 | 2001-12-06 | Silverbrook Research Pty. Ltd. | Methods and systems (npw005) |
| US7130072B2 (en) * | 2002-02-08 | 2006-10-31 | Canon Kabushiki Kaisha | Multifunction system, image processing method, computer program and memory medium |
| US20040005005A1 (en) * | 2002-04-22 | 2004-01-08 | Mcintyre Kristen A. | Method and apparatus to facilitate image difference transmission while maintaining image salience |
| CN100426861C (en) * | 2002-07-01 | 2008-10-15 | 微软公司 | System and method for providing user control over repeating objects embedded in a media stream |
| FR2842683B1 (en) * | 2002-07-22 | 2005-01-14 | Cit Alcatel | MULTIPLEXING DEVICE, MULTIPLEXING DEVICE, AND MULTIPLEXING / DEMULTIPLEXING SYSTEM |
| GB0218961D0 (en) * | 2002-08-15 | 2002-09-25 | Koninkl Philips Electronics Nv | Transmission method and system |
| WO2004029935A1 (en) * | 2002-09-24 | 2004-04-08 | Rad Data Communications | A system and method for low bit-rate compression of combined speech and music |
| US20050047504A1 (en) * | 2003-09-03 | 2005-03-03 | Sung Chih-Ta Star | Data stream encoding method and apparatus for digital video compression |
| US7657533B2 (en) * | 2003-11-26 | 2010-02-02 | Hewlett-Packard Development Company, L.P. | Data management systems, data management system storage devices, articles of manufacture, and data management methods |
| MX2007004142A (en) * | 2004-10-05 | 2008-02-15 | Vectormax Corp | METHOD AND SYSTEM TO DISSEMINATE DATA IN MULTIMEDIA. |
| WO2006063057A2 (en) * | 2004-12-06 | 2006-06-15 | Agilix Labs | Applying multiple compression algorithms in a database system |
| US7921078B2 (en) * | 2005-04-20 | 2011-04-05 | Sony Online Entertainment Llc | System for negotiated differential compression |
| US20090190652A1 (en) * | 2005-10-06 | 2009-07-30 | Yong-Hwa Kim | System and method for controlling transmission of moving image data over network |
| US8718147B2 (en) * | 2006-02-17 | 2014-05-06 | Avocent Huntsville Corporation | Video compression algorithm |
| JP4576350B2 (en) * | 2006-03-24 | 2010-11-04 | 富士通株式会社 | Communication control device and communication control method |
| EP2013974B1 (en) * | 2006-04-07 | 2018-07-11 | Data Storage Group | Data compression and storage techniques |
| CN101094171B (en) * | 2006-06-22 | 2011-02-16 | 华为技术有限公司 | Method and system for implementing interaction of media streams, controller of media gateway, and media gateway |
| US7885988B2 (en) * | 2006-08-24 | 2011-02-08 | Dell Products L.P. | Methods and apparatus for reducing storage size |
| US20080162922A1 (en) * | 2006-12-27 | 2008-07-03 | Swartz Troy A | Fragmenting security encapsulated ethernet frames |
| US8068654B2 (en) * | 2007-02-02 | 2011-11-29 | Siemens Akteingesellschaft | Method and system for detection and registration of 3D objects using incremental parameter learning |
| US8768895B2 (en) * | 2007-04-11 | 2014-07-01 | Emc Corporation | Subsegmenting for efficient storage, resemblance determination, and transmission |
| US8014614B2 (en) * | 2008-04-14 | 2011-09-06 | General Electric Company | Method and system for compressing data |
| US20090290855A1 (en) * | 2008-05-20 | 2009-11-26 | Francois-Xavier Kowalski | Apparatus And Method For Recording Video Data |
| JP2010062792A (en) * | 2008-09-03 | 2010-03-18 | Weigang Xu | Image compression apparatus, image decompression apparatus, image compression program, and image decompression program |
| US8447740B1 (en) * | 2008-11-14 | 2013-05-21 | Emc Corporation | Stream locality delta compression |
| US8412848B2 (en) * | 2009-05-29 | 2013-04-02 | Exagrid Systems, Inc. | Method and apparatus for content-aware and adaptive deduplication |
| CN101674315B (en) * | 2009-10-20 | 2014-12-10 | 中兴通讯股份有限公司 | Method and device for compressing and decompressing timestamp |
| US8396954B2 (en) * | 2010-06-24 | 2013-03-12 | Aryaka Networks, Inc. | Routing and service performance management in an application acceleration environment |
| US8362931B2 (en) * | 2010-11-30 | 2013-01-29 | Microsoft Corporation | Compression and decompression of mass spectrometry data |
| US20120185612A1 (en) * | 2011-01-19 | 2012-07-19 | Exar Corporation | Apparatus and method of delta compression |
-
2010
- 2010-09-03 GB GB1014625.6A patent/GB2483282B/en active Active
-
2011
- 2011-08-15 US US13/137,432 patent/US8548962B2/en active Active
- 2011-09-02 JP JP2011191535A patent/JP5781867B2/en active Active
- 2011-09-05 CN CN201110264956.9A patent/CN102404564B/en active Active
Patent Citations (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5832490A (en) * | 1996-05-31 | 1998-11-03 | Siemens Medical Systems, Inc. | Lossless data compression technique that also facilitates signal analysis |
| US20030090740A1 (en) * | 2001-11-14 | 2003-05-15 | International Business Machines Corporation | Raster data compression apparatus and method |
| US20060227250A1 (en) * | 2003-07-18 | 2006-10-12 | Mauro Barbieri | Detecting a content item in a digital video stream |
| US20080129748A1 (en) * | 2003-11-19 | 2008-06-05 | Reuven Bakalash | Parallel graphics rendering system supporting parallelized operation of multiple graphics processing pipelines within diverse system architectures |
| CN1658665A (en) * | 2004-02-17 | 2005-08-24 | 索尼株式会社 | Memory management method, image processing apparatus, and memory management program |
| US20060161963A1 (en) * | 2005-01-17 | 2006-07-20 | Samsung Electronics Co., Ltd. | Display apparatus and control method thereof |
| US20100125553A1 (en) * | 2008-11-14 | 2010-05-20 | Data Domain, Inc. | Delta compression after identity deduplication |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107193642A (en) * | 2016-03-14 | 2017-09-22 | 阿里巴巴集团控股有限公司 | Task data compression switching method, suitable compression degree evaluation method and relevant apparatus |
| CN113227957A (en) * | 2018-11-29 | 2021-08-06 | 超威半导体公司 | Aggregating commands in a stream based on cache line addresses |
| CN112241013A (en) * | 2019-07-01 | 2021-01-19 | 英飞凌科技股份有限公司 | Extended delta encoding technique for light detection and ranging raw data compression |
Also Published As
| Publication number | Publication date |
|---|---|
| GB2483282A (en) | 2012-03-07 |
| JP5781867B2 (en) | 2015-09-24 |
| US8548962B2 (en) | 2013-10-01 |
| GB201014625D0 (en) | 2010-10-13 |
| US20120059804A1 (en) | 2012-03-08 |
| GB2483282B (en) | 2017-09-13 |
| CN102404564B (en) | 2016-08-17 |
| JP2012074026A (en) | 2012-04-12 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN102404564B (en) | Utilize the relative and data compression and decompression of absolute increment value | |
| US6452602B1 (en) | Method and apparatus for storing compressed data | |
| JP4564718B2 (en) | 3-D computer graphics rendering system | |
| EP1074945B1 (en) | Method and apparatus for controlling compressed Z information in a video graphics system | |
| US6407741B1 (en) | Method and apparatus for controlling compressed Z information in a video graphics system that supports anti-aliasing | |
| US9946462B1 (en) | Address mapping table compression | |
| US8836696B2 (en) | Random accessible lossless parameter data compression for tile based 3D computer graphics systems | |
| US20080062775A1 (en) | Fusion memory device and method | |
| JP2012074026A5 (en) | ||
| US20210158585A1 (en) | Graphics processing systems | |
| CN109075798B (en) | Variable-Size Symbolic Entropy-Based Data Compression | |
| KR20160001701A (en) | Texture Pipeline with Frequency Compression | |
| US8125364B2 (en) | Data compression/decompression method | |
| US20150379682A1 (en) | Vertex attribute data compression with random access using hardware | |
| EP3444952A1 (en) | Data compression apparatus, data decompression apparatus, data compression program, data decompression program, data compression method, and data decompression method | |
| KR20180048938A (en) | Hardware - Accelerated Storage Compression | |
| CN108377394B (en) | Image data reading method of video encoder, computer device and computer-readable storage medium | |
| CN108122189B (en) | Vertex attribute compression and decompression in hardware | |
| KR102589299B1 (en) | Method and apparatus for vertex attribute compression and decompression in hardware | |
| US10803018B2 (en) | Compressed data rearrangement to optimize file compression | |
| US11275505B2 (en) | Storage system | |
| US12374005B2 (en) | Graphics processing | |
| CN116797440A (en) | graphics processing | |
| US9105250B2 (en) | Coverage compaction | |
| US12217463B2 (en) | Adaptable and hierarchical point cloud compression |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant |