# US 10,120,581 B2 · Generating compressed data streams with lookback pre-fetch instructions for pre-fetching decompressed data from a lookback buffer > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,120,581 B2 - Document ID: US10120581B2 - Status: Granted - Kind: B2 - Application number: 15/085,399 - Filed: 2016-03-30 - Published: 2017-10-05 - Granted: 2018-11-06 - Earliest claimed: 2016-03-30 - Assignees: QUALCOMM Incorporated - Applicants: QUALCOMM Incorporated - Inventors: Richard Senior; Amin Ansari; Vito Remo Bica; Jinxia Bai - Web page: https://patentgrep.com/patent/US10120581B2 ## CPC - G06F 3/061: {Improving I/O performance} - G06F 3/064: {Management of blocks} - G06F 3/0656: {Data buffering arrangements} - G06F 3/0673: {Single storage device} - H03M 7/3086: {employing a sliding window, e.g. LZ77} - H03M 7/6017: {Methods or arrangements to increase the throughput} - H03M 7/6029: {Pipelining} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C) ## Abstract Aspects for generating compressed data streams with lookback pre-fetch instructions are disclosed. A data compression system is provided and configured to receive and compress an uncompressed data stream as part of a lookback-based compression scheme. The data compression system determines if a current data block was previously compressed. If so, the data compression system is configured to insert a lookback instruction corresponding to the current data block into the compressed data stream. Each lookback instruction includes a lookback buffer index that points to an entry in a lookback buffer where decompressed data corresponding to the data block will be stored during a separate decompression scheme. Once the data blocks have been compressed, the data compression system is configured to move a lookback buffer index of each lookback instruction in the compressed data stream into a lookback pre-fetch instruction located earlier than the corresponding lookback instruction in the compressed data stream. ## Claims ### Claim 1 A data compression system, comprising: a data stream input circuit configured to receive an uncompressed data stream comprising a plurality of data blocks; and a compression engine configured to: generate a compressed data stream from the uncompressed data stream by being configured to: determine if a current data block of the plurality of data blocks in the uncompressed data stream was previously compressed by the compression engine; and responsive to determining that the current data block of the plurality of data blocks was previously compressed by the compression engine, insert a lookback instruction corresponding to the current data block into the compressed data stream, wherein the lookback instruction comprises a lookback buffer index that points to an entry in a lookback buffer that stores data to be provided during decompression of the lookback instruction; and move the lookback buffer index corresponding to each lookback instruction in the compressed data stream to a corresponding lookback pre-fetch instruction in the compressed data stream that is scheduled to be accessed before a corresponding lookback instruction during decompression by being configured to: create a corresponding lookback pre-fetch instruction for each corresponding lookback buffer index in the compressed data stream; and move each corresponding lookback buffer index to the corresponding lookback pre-fetch instruction in the compressed data stream. ### Claim 2 (depends on 1) The data compression system of claim 1, wherein the compression engine is further configured to move the lookback buffer index by being configured to move a lookback buffer index of a first lookback instruction into a lookback pre-fetch instruction in the compressed data stream that is scheduled to be accessed during decompression before a first instruction in the compressed data stream. ### Claim 3 (depends on 2) The data compression system of claim 2, wherein the compression engine is further configured to move the lookback buffer index by being configured to move the lookback buffer index of each lookback instruction in the compressed data stream other than the first lookback instruction into a lookback pre-fetch instruction in the compressed data stream that is scheduled to be accessed with a closest previous lookback instruction during decompression. ### Claim 4 (depends on 3) The data compression system of claim 3, wherein the compression engine is further configured to add a dummy lookback pre-fetch instruction to a last lookback instruction in the compressed data stream. ### Claim 5 (depends on 1) The data compression system of claim 1, wherein the compression engine is further configured to move the lookback buffer index corresponding to each lookback instruction by being configured to: determine a maximum number of lookback instructions in the compressed data stream within an instruction window, wherein the instruction window is sized to encompass a certain number of instructions in the compressed data stream; and move each lookback buffer index of a first plurality of lookback instructions in the compressed data stream to corresponding lookback pre-fetch instructions in the compressed data stream that are scheduled to be accessed during decompression before a first instruction in the compressed data stream, wherein a number of the first plurality of lookback instructions equals the maximum number of lookback instructions. ### Claim 6 (depends on 5) The data compression system of claim 5, wherein the compression engine is further configured to move the lookback buffer index by being configured to: move the lookback buffer index corresponding to each lookback instruction that is not one of the first plurality of lookback instructions into a lookback pre-fetch instruction in the compressed data stream that is scheduled to be accessed with a previous lookback instruction during decompression, wherein the previous lookback instruction is the lookback instruction that is the maximum number of lookback instructions prior to a current lookback instruction. ### Claim 7 (depends on 6) The data compression system of claim 6, wherein the compression engine is further configured to add a dummy lookback pre-fetch instruction to each lookback instruction of a last plurality of lookback instructions in the compressed data stream, wherein a number of the last plurality of lookback instructions equals the maximum number of lookback instructions. ### Claim 8 (depends on 1) The data compression system of claim 1, wherein the compression engine is configured to generate the compressed data stream by being further configured to: determine if the current data block of the plurality of data blocks corresponds to a dictionary instruction; and responsive to determining that the current data block of the plurality of data blocks corresponds to a dictionary instruction, encode the current data block into a dictionary instruction in the compressed data stream. ### Claim 9 (depends on 1) The data compression system of claim 1, wherein the compression engine is configured to generate the compressed data stream by being further configured to: determine if the current data block of the plurality of data blocks corresponds to a raw data instruction; and responsive to determining that the current data block of the plurality of data blocks corresponds to a raw data instruction, encode the current data block into a raw data instruction in the compressed data stream. ### Claim 10 (depends on 1) The data compression system of claim 1 integrated into an integrated circuit (IC). ### Claim 11 (depends on 1) The data compression system of claim 1 integrated into a device selected from the group consisting of: a set top box; an entertainment unit; a navigation device; a communications device; a fixed location data unit; a mobile location data unit; a mobile phone; a cellular phone; a smart phone; a tablet; a phablet; a computer; a portable computer; a desktop computer; a personal digital assistant (PDA); a monitor; a computer monitor; a television; a tuner; a radio; a satellite radio; a music player; a digital music player; a portable music player; a digital video player; a video player; a digital video disc (DVD) player; a portable digital video player; and an automobile. ### Claim 12 A method for generating a compressed data stream with lookback pre-fetch instructions, comprising: receiving an uncompressed data stream comprising a plurality of data blocks; generating a compressed data stream from the uncompressed data stream, wherein generating comprises: determining if a current data block of the plurality of data blocks in the uncompressed data stream was previously compressed by a compression engine; and responsive to determining that the current data block of the plurality of data blocks was previously compressed by the compression engine, inserting a lookback instruction corresponding to the current data block into the compressed data stream, wherein the lookback instruction comprises a lookback buffer index that points to an entry in a lookback buffer that stores data to be provided during decompression of the lookback instruction; and moving the lookback buffer index corresponding to each lookback instruction in the compressed data stream to a corresponding lookback pre-fetch instruction in the compressed data stream that is scheduled to be accessed before a corresponding lookback instruction during decompression, wherein moving the lookback buffer index comprises: creating a corresponding lookback pre-fetch instruction for each corresponding lookback buffer index in the compressed data stream; and moving each corresponding lookback buffer index to the corresponding lookback pre-fetch instruction in the compressed data stream. ### Claim 13 (depends on 12) The method of claim 12, wherein moving the lookback buffer index corresponding to each lookback instruction further comprises moving a lookback buffer index of a first lookback instruction into a lookback pre-fetch instruction in the compressed data stream that is scheduled to be accessed during decompression before a first instruction in the compressed data stream. ### Claim 14 (depends on 13) The method of claim 13, wherein moving the lookback buffer index corresponding to each lookback instruction further comprises moving the lookback buffer index of each lookback instruction in the compressed data stream other than the first lookback instruction into a lookback pre-fetch instruction in the compressed data stream that is scheduled to be accessed with a closest previous lookback instruction during decompression. ### Claim 15 (depends on 14) The method of claim 14, further comprising adding a dummy lookback pre-fetch instruction to a last lookback instruction in the compressed data stream. ### Claim 16 (depends on 12) The method of claim 12, wherein moving the lookback buffer index corresponding to each lookback instruction comprises: determining a maximum number of lookback instructions in the compressed data stream within an instruction window, wherein the instruction window is sized to encompass a certain number of instructions in the compressed data stream; and moving each lookback buffer index of a first plurality of lookback instructions in the compressed data stream to corresponding lookback pre-fetch instructions in the compressed data stream that are scheduled to be accessed during decompression before a first instruction in the compressed data stream, wherein a number of the first plurality of lookback instructions equals the maximum number of lookback instructions. ### Claim 17 (depends on 16) The method of claim 16, wherein moving the lookback buffer index corresponding to each lookback instruction further comprises: moving the lookback buffer index corresponding to each lookback instruction that is not one of the first plurality of lookback instructions into a lookback pre-fetch instruction in the compressed data stream that is scheduled to be accessed with a previous lookback instruction during decompression, wherein the previous lookback instruction is the lookback instruction that is the maximum number of lookback instructions prior to a current lookback instruction. ### Claim 18 (depends on 17) The method of claim 17, further comprising adding a dummy lookback pre-fetch instruction to each lookback instruction of a last plurality of lookback instructions in the compressed data stream, wherein a number of the last plurality of lookback instructions equals the maximum number of lookback instructions. ### Claim 19 A data compression system, comprising: a means for receiving an uncompressed data stream comprising a plurality of data blocks; a means for generating a compressed data stream from the uncompressed data stream, comprising; a means for determining if a current data block of the plurality of data blocks in the uncompressed data stream was previously compressed by the means for generating the compressed data stream; and responsive to determining that the current data block of the plurality of data blocks was previously compressed by the means for generating the compressed data stream, a means for inserting a lookback instruction corresponding to the current data block into the compressed data stream, wherein the lookback instruction comprises a lookback buffer index that points to an entry in a lookback buffer that stores data to be provided during decompression of the lookback instruction; and a means for moving the lookback buffer index corresponding to each lookback instruction in the compressed data stream to a corresponding lookback pre-fetch instruction in the compressed data stream that is scheduled to be accessed before a corresponding lookback instruction during decompression, wherein the means for moving the lookback buffer index comprises: a means for creating a corresponding lookback pre-fetch instruction for each corresponding lookback buffer index in the compressed data stream; and a means for moving each corresponding lookback buffer index to the corresponding lookback pre-fetch instruction in the compressed data stream. ### Claim 20 A processing system, comprising: a processor; a data decompression system configured to decompress a compressed data stream; a lookback buffer comprised of lower level memory that is placed separately from the data decompression system; and a data compression system, comprising: a data stream input circuit configured to receive an uncompressed data stream comprising a plurality of data blocks; and a compression engine configured to: generate the compressed data stream from the uncompressed data stream by being configured to; determine if a current data block of the plurality of data blocks in the uncompressed data stream was previously compressed by the compression engine; and responsive to determining that the current data block of the plurality of data blocks was previously compressed by the compression engine, insert a lookback instruction corresponding to the current data block into the compressed data stream, wherein the lookback instruction comprises a lookback buffer index that points to an entry in the lookback buffer that stores data to be provided during decompression of the lookback instruction; and move the lookback buffer index corresponding to each lookback instruction in the compressed data stream to a corresponding lookback pre-fetch instruction in the compressed data stream that is scheduled to be accessed before a corresponding lookback instruction during decompression by being configured to: create a corresponding lookback pre-fetch instruction for each corresponding lookback buffer index in the compressed data stream; and move each corresponding lookback buffer index to the corresponding lookback pre-fetch instruction in the compressed data stream. ### Claim 21 (depends on 20) The processing system of claim 20, wherein the data decompression system comprises a lookback pre-fetch buffer configured to store data pre-fetched for corresponding lookback instructions during decompression. ### Claim 22 (depends on 21) The processing system of claim 21, wherein the data decompression system further comprises a lookback output buffer configured to: store a plurality of recently decompressed data blocks; and responsive to a lookback pre-fetch instruction requesting a decompressed data block from a lookback buffer index, wherein a lookback pre-fetch buffer position of a most recently stored data block in the lookback pre-fetch buffer minus a lookback pre-fetch buffer position of a data block requested by the lookback pre-fetch instruction is less than a number of entries in the lookback output buffer, provide the decompressed data block from the lookback output buffer. ### Claim 23 (depends on 20) The processing system of claim 20, wherein the compression engine is further configured to move the lookback buffer index by being configured to move a lookback buffer index of a first lookback instruction into a lookback pre-fetch instruction in the compressed data stream that is scheduled to be accessed during decompression before a first instruction in the compressed data stream. ### Claim 24 (depends on 23) The processing system of claim 23, wherein the compression engine is further configured to move the lookback buffer index by being configured to move the lookback buffer index of each lookback instruction in the compressed data stream other than the first lookback instruction into a lookback pre-fetch instruction in the compressed data stream that is scheduled to be accessed with a closest previous lookback instruction during decompression. ### Claim 25 (depends on 24) The processing system of claim 24, wherein the compression engine is further configured to add a dummy lookback pre-fetch instruction to a last lookback instruction in the compressed data stream. ### Claim 26 (depends on 20) The processing system of claim 20, wherein the compression engine is further configured to move the lookback buffer index by being configured to: determine a maximum number of lookback instructions in the compressed data stream within an instruction window, wherein the instruction window is sized to encompass a certain number of instructions in the compressed data stream; and move each lookback buffer index of a first plurality of lookback instructions in the compressed data stream to corresponding lookback pre-fetch instructions in the compressed data stream that are scheduled to be accessed during decompression before a first instruction in the compressed data stream, wherein a number of the first plurality of lookback instructions equals the maximum number of lookback instructions. ### Claim 27 (depends on 26) The processing system of claim 26, wherein the compression engine is further configured to move the lookback buffer index by being configured to: move the lookback buffer index corresponding to each lookback instruction that is not one of the first plurality of lookback instructions into a lookback pre-fetch instruction in the compressed data stream that is scheduled to be accessed with a previous lookback instruction during decompression, wherein the previous lookback instruction is the lookback instruction that is the maximum number of lookback instructions prior to a current lookback instruction. ### Claim 28 (depends on 27) The processing system of claim 27, wherein the compression engine is further configured to add a dummy lookback pre-fetch instruction to each lookback instruction of a last plurality of lookback instructions in the compressed data stream, wherein a number of the last plurality of lookback instructions equals the maximum number of lookback instructions.