# US 2014/0156790 A1 · Bitstream processing using coalesced buffers and delayed matching and enhanced memory writes > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0156790 A1 - Document ID: US20140156790A1 - Status: Published application - Kind: A1 - Application number: 13/994,129 - Filed: 2011-12-23 - Published: 2014-06-05 - Earliest claimed: 2011-12-23 - Assignees: Intel Corporation - Inventors: Vinodh Gopal; Jim D. Guilford; Gilbert M. Wolrich; Wajdi K. Feghail; Deniz Karakoyunlu; Erdinc Ozturk; Martin Dixon; Kahraman Akdemir - Web page: https://patentgrep.com/patent/US20140156790A1 ## CPC - H04L 65/70: Media network packetisation - H03M 7/3086: {employing a sliding window, e.g. LZ77} - H03M 7/30: Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction - H04L 65/65: Network streaming protocols, e.g. real-time transport protocol [RTP] or real-time control protocol [RTCP] - H04L 69/04: Protocols for data compression, e.g. ROHC - H04L 69/22: Parsing or analysis of headers - H04W 28/06: Optimizing {the usage of the radio link}, e.g. header compression, information sizing {, discarding information (system modifying transmission characteristic according to link quality by modifying frame length H04L1/0007; dynamic adaptation of the packet size for flow control or congestion control H04L47/365)} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - 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) - H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72) ## Abstract Methods and apparatus for processing bitstreams and byte streams. According to one aspect, bitstream data is compressed using coalesced string match tokens with delayed matching. A matcher is employed to perform search string match operations using a shortened maximum string length search criteria, resulting in generation of a token stream having data and literal data. A distance match operation is performed on sequentially adjacent tokens to determine if they contain the same distance data. If they do, the len values of the tokens are added through use of a coalesce buffer. Upon detection of a distance non-match, a final coalesced length of a matching string is calculated and output along with the prior matching distance as a coalesced token. Also disclosed is a scheme for writing variable-length tokens into a bitstream under which token data is input into a bit accumulator and written to memory (or cache to be subsequently written to memory) as each token is processed in a manner that eliminates branch mispredict operations associated with detecting whether the bit accumulator is full or close to full. ## Claims ### Claim 1 A method, comprising: receiving an original token stream comprising a plurality of original tokens generated by a sliding-window string match search scheme, the original tokens including tokens comprising original len and distance data; and processing the original token stream to generate a coalesced token stream in which a portion of the original tokens are replaced with coalesced tokens including coalesced len and distance data. ### Claim 2 (depends on 1) The method of claim 1, further comprising limiting a coalesced len value to a maximum len that may be encoded in a coalesced token. ### Claim 3 (depends on 1) The method of claim 1, further comprising employing the method to generate a compressed byte stream or document in accordance with the DEFLATE compression standard. ### Claim 4 (depends on 1) The method of claim 1, wherein the original token stream includes a plurality of tokens encoded as literals, and the coalesced token includes the same tokens encoded as literals. ### Claim 5 (depends on 1) The method of claim 1, further comprising processing the coalesced token stream with an entropy coder to generate compressed data. ### Claim 6 (depends on 1) The method of claim 1, further comprising: receiving a first original token having data comprising a first len and a first distance; receiving a second original token immediately following the first original token having data comprising a second len and a second distance; comparing the first and second distances for a match; and in response to a match, temporally storing coalesced token data in a coalesce buffer comprising a len derived from adding the first and second lens and a distance equal to the first distance; receiving a third original token immediately following the second original token having data comprising a third len and a third distance; comparing the first and third distances for a match; and in response to the first and third distances not matching, generating a coalesced token from the coalesced token data in the coalesce buffer and adding the coalesced token to the coalesced token data stream. ### Claim 7 (depends on 6) The method of claim 6, further comprising: determining that first and third distances match; and in response to a match, temporally storing coalesced token data in the coalesce buffer comprising a len derived from adding the first, second, and third lens and a distance equal to the first distance. ### Claim 8 A method, comprising: performing string match detection on data in a bitstream using a sliding window-based search scheme including a maximum matched string length that is searched and outputting a token stream comprising a plurality of tokens, each encoded as len and distance data or literal data; processing the token stream to generate a coalesced token stream in which a portion of the tokens are replaced with coalesced tokens including coalesced len and distance data; and processing the coalesced token stream with an entropy encoder to generate compressed data comprising a plurality of variable-length tokens. ### Claim 9 (depends on 8) The method of claim 8, wherein the entropy encoder is a Huffman coder and the compressed data is compliant with the DEFLATE compression standard. ### Claim 10 (depends on 8) The method of claim 8, further comprising writing the variable-length tokens to memory by inputting token data corresponding to the tokens into a bit accumulator and writing data in the bit accumulator to memory without employing any conditional branch operations to check if the bit accumulator is full or close to full throughout processing of the compressed data. ### Claim 11 A method, comprising: writing variable-length tokens received in an input token stream to a bit stream stored in a plurality of memory segments having a memory segment size by performing a cyclical set of operations for each token that is received, including, inputting data bits of the token into a bit-accumulator register at a location defined by a bit accumulator pointer; and writing a portion of data in the bit accumulator into one of a memory segment or a cache to be subsequently written to the memory segment. ### Claim 12 (depends on 11) The method of claim 11, wherein the cyclical set of operations further include updating the location of the bit accumulator pointer based on a prior location of the pointer, the length of the token, and the memory segment size. ### Claim 13 (depends on 11) The method of claim 11, wherein the cyclical set of operations further include performing a memory address advance calculation to determine a memory address of the memory segment to which the portion of data in the bit accumulator is written. ### Claim 14 (depends on 11) The method of claim 11, further comprising writing the portion of the data in the bit accumulator to a cacheable buffer. ### Claim 15 A method, comprising: writing variable-length tokens received in an input token stream to a bit stream stored in memory by inputting token data corresponding to the tokens into a bit accumulator and writing data in the bit accumulator to memory without employing any conditional branch operations to check if the accumulator is full or close to full throughout processing of the bit stream. ### Claim 16 (depends on 15) The method of claim 15, further comprising, for a cycle performed to process each variable-length token, inputting token data into the bit accumulator and writing out at least a portion of the contents of the bit accumulator to one of memory or a cache. ### Claim 17 (depends on 15) The method of claim 15, wherein during each cycle the at least a portion of the contents of the bit accumulator are written to a cacheable buffer. ### Claim 18 A tangible machine readable medium having instructions stored thereon configured to be executed on a machine to cause the machine to perform operations, comprising: receiving an original token stream comprising a plurality of original tokens generated by a sliding-window string match search scheme, the original tokens including tokens comprising original len and distance data; and processing the original token stream to generate a coalesced token stream in which a portion of the original tokens are replaced with coalesced tokens including coalesced len and distance data. ### Claim 19 (depends on 18) The machine readable medium of claim 18, wherein execution of the instructions perform further operations comprising, receiving a first original token having data comprising a first len and a first distance; receiving a second original token immediately following the first original token having data comprising a second len and a second distance; comparing the first and second distances for a match; and in response to a match, temporally storing coalesced token data in a coalesce buffer comprising a len derived from adding the first and second lens and a distance equal to the first distance; receiving a third original token immediately following the second original token having data comprising a third len and a third distance; comparing the first and third distances for a match; and in response to the first and third distances not matching, generating a coalesced token from the coalesced token data in the coalesce buffer and adding the coalesced token to the coalesced token data stream. ### Claim 20 (depends on 18) The machine readable medium of claim 18, wherein the coalesced token stream comprises a token stream in accordance with the DEFLATE compression standard.