Patent Description:
Digital computer systems perform data compression to realize a more efficient use of finite storage space. The computer system typically includes a hardware component referred to as a compression accelerator, which accepts work requests or data requests from the host system to compress or decompress one or more blocks of the requested data. When designing an accelerator to perform compression, there is a tradeoff between the size of the input data that is to be compressed compared to the possible compression ratio and the latency that results from compressing the data.

Compression accelerators often utilize a "DEFLATE" algorithm, which is a lossless compression scheme that combines the Lempel-Ziv (e.g., LZ77) compression algorithm with a Huffman encoding algorithm to perform the compression. The computed output from the Huffman algorithm can be viewed as a variable-length code table for encoding a source symbol (such as a character in a file). The Huffman algorithm derives this table from the estimated probability or frequency of occurrence (weight) for each possible value of the source symbol.

To maximize the compression ratio achieved using the DEFLATE algorithm, symbols are encoded into the variable-length code table according to their frequency of occurrence. In other words, the most frequent symbols are encoded with the fewest bits, while relatively less common symbols are encoded with relatively more bits. This results in a direct reduction in the required storage space for the compressed data stream. Because the symbols are encoded based on their relatively frequencies, the occurrence counts for each symbol must be sorted. Sorting the symbol counts (frequencies) during this process is expensive in terms of area (the number of latches and width comparators required), power, and timing/wiring considerations.

"<NPL>discloses the operation of GZIP compression to take up a smaller number of bytes than the uncompressed data. The Deflate algorithm achieves a good compression ratio by using a combination of several techniques, LZ77, Huffman encoding and Run Length Encoding.

According to aspects of the invention there are provided an accelerator, a method, and a system as defined in the attached claims.

The specifics of the exclusive rights described herein are distinctly claimed in the claims at the conclusion of the specification. The foregoing and other features and advantages of the embodiments of the invention defined in the claims are apparent from the following detailed description taken in conjunction with the accompanying drawings in which:.

The diagrams depicted herein are illustrative. There can be many variations to the diagram or the operations described therein without departing from the invention. For instance, the actions can be performed in a differing order or actions can be added, deleted or modified. Also, the term "coupled" and variations thereof describes having a communications path between two elements and does not imply a direct connection between the elements with no intervening elements/connections between them. All of these variations are considered a part of the specification.

In the accompanying figures and following detailed description of the disclosed embodiments, the various elements illustrated in the figures are provided with two or three digit reference numbers. With minor exceptions, the leftmost digit(s) of each reference number correspond to the figure in which its element is first illustrated.

The invention is defined exclusively by the appended set of claims. Various connections and positional relationships (e.g., over, below, adjacent, etc.) are set forth between elements in the following description and in the drawings. These connections and/or positional relationships, unless specified otherwise, can be direct or indirect, and the present invention is not intended to be limiting in this respect. Accordingly, a coupling of entities can refer to either a direct or an indirect coupling, and a positional relationship between entities can be a direct or indirect positional relationship. Moreover, the various tasks and process steps described herein can be incorporated into a more comprehensive procedure or process having additional steps or functionality not described in detail herein.

Additionally, the term "exemplary" is used herein to mean "serving as an example, instance or illustration. " Any embodiment or design described herein as "exemplary" is not necessarily to be construed as preferred or advantageous over other embodiments or designs. The terms "at least one" and "one or more" may be understood to include any integer number greater than or equal to one, i.e., one, two, three, four, etc. The terms "a plurality" may be understood to include any integer number greater than or equal to two, i.e., two, three, four, five, etc. The term "connection" may include both an indirect "connection" and a direct "connection.

For the sake of brevity, conventional techniques related to making and using aspects of the invention may or may not be described in detail herein. In particular, various aspects of computing systems and specific computer programs to implement the various technical features described herein are well known. Accordingly, in the interest of brevity, many conventional implementation details are only mentioned briefly herein or are omitted entirely without providing the well-known system and/or process details.

Turning now to an overview of technologies that are more specifically relevant to aspects of the invention, the reduction in data-representation size produced by an applied data compression algorithm is typically referred to as the compression ratio (C/R). The compression ratio can be defined as the ratio between the uncompressed size and compressed size. Thus, as the compression ratio increases, a more efficient use of the computer system's storage space is achieved, thereby improving the overall performance of the computer system.

The DEFLATE data compression algorithm is a commonly used method for compressing data. When compressing data, there are two main parts to the DEFLATE algorithm: (<NUM>) LZ77 compression to identify duplicate strings and (<NUM>) a Huffman encoding of this information.

The LZ77 compression phase attempts to find duplicate strings in a previously encoded source operand. When a match is found, instead of outputting the literal characters of the duplicate string, the LZ77 compression phase instead outputs the "distance" from the duplicate string to the original (matching) string in the prior data set history, along with the matching "length" of the data. For example, suppose the input operand contains the following symbols: ABBACBABBAABBABBA. This operand could be encoded as follows:
literal byte A; literal byte B; literal byte B; literal byte A; literal byte C; literal byte B; distance <NUM>, length <NUM> (this encodes "ABBA"); distance <NUM>, length <NUM> (this encodes "ABBAABBA").

As can be seen, the more duplicate strings that can be found in the input operand data, the more the output can be compressed. There are two ways the input operand history can be checked for matching strings: an inline history, and via a circular history buffer. For inline histories, the LZ77 compressor simply looks at prior input from the source operand. For a circular history buffer, input data is copied (either actually copied or conceptually copied) to a circular history buffer, and then data in this buffer is searched for matches. In either case, the DEFLATE standard allows looking back up to 32KB for matching strings.

The Huffman encoding phase is based on the probability and distribution of the symbols generated by the LZ77 compressor. The idea behind Huffman encoding is that symbols can be encoded with variable bit lengths such that frequent symbols are encoded with few bits and rare symbols with many bits. In this manner a further compression of the data obtained from the LZ77 compressor is possible.

For this encoding process, the DEFLATE standard supports three types of compressed data blocks: literal copy blocks, a Fixed Huffman Table (FHT), and a Dynamic Huffman Table (DHT). An FHT block is static, while a DHT block consists of a highly compressed version of a Huffman tree, followed by the symbols, encoded using that tree, representing the compressed data.

Example Huffman trees are illustrated in <FIG>. As depicted in <FIG>, a Huffman tree can be highly asymmetrical, with the majority of the nodes (also referred to as leaves) occurring along a single branch of the tree. Alternatively, a Huffman tree can be compressed as shown with respect to <FIG>, with leaves distributed throughout the available branches. In either case, a Huffman tree is constructed such that the depth of the leaves (nodes) are determined by the frequency of the symbols corresponding to each leaf. In other words, the depth of a leaf is determined by its symbol frequency.

Table <NUM> illustrates an exemplary DHT corresponding to the Huffman tree depicted in <FIG>. The DHT shown in Table <NUM> is constructed such that symbols having relatively higher counts/frequencies are encoded using relatively shorter code lengths.

As shown in Table <NUM>, the "A" and "E" symbols have the lowest frequency, occurring only <NUM> times each. The "D" symbol has the next highest frequency and occurs <NUM> times in the dataset. The "C" symbol occurs <NUM> times in the dataset, and the "B" symbol occurs most frequently, with <NUM> occurrences. As further shown in Table <NUM>, the "A" symbol is encoded as the binary number "<NUM>," the "B" symbol as "<NUM>," the "C" symbol as "<NUM>," the "D" symbol as "<NUM>," and the "E" symbol as "<NUM>.

Encoding the most frequent symbols (e.g., "B" in the above example) with the fewest bits results in a direct reduction in the required storage space for the compressed data stream. For example, the "B" symbol, which occurs <NUM> times, can be represented as a single "<NUM>" bit for each occurrence. Consequently, only <NUM> bits (<NUM> bytes) are required to store every occurrence of the "B" symbol. "E," a less frequent symbol, can be represented as a longer binary code such as "<NUM>. " As a result, the <NUM> occurrences of the "E" symbol require <NUM> bits (<NUM> bytes) of storage. Continuing with this example, the symbols depicted in Table <NUM> can be encoded using <NUM> total bytes. This same data, without the use of a DHT, requires <NUM> bytes of storage.

To increase the speed of DEFLATE compression, this Huffman tree generation process can be implemented in hardware. The LZ77 algorithm in DEFLATE uses <NUM> literals (ASCII values 0x00-xFF), <NUM> length symbols, and <NUM> distance symbols for compression. The length and distance symbols represent the distances and lengths of matching strings in a data stream (data history). Since length is always followed by distance, one DHT can be built to encode the literals, an End-of-Block symbol, and the length symbols. This requires a total <NUM> alphabets of symbols. A second DHT can be built for the distance symbols. This requires a total <NUM> alphabets of symbols.

One challenge associated with the Huffman tree generation process is the difficulty in actually populating each DHT leaf with the correct symbol. For each leaf, the symbol having the next highest frequency is needed. In other words, the frequency of each symbol must be determined, stored, and sorted. This sorting process can be expensive in terms of area (the number of latches and width comparators required), power, and timing/wiring considerations.

To illustrate this point, consider an LZ77 compression on <NUM>N bytes of data. To fully (uniquely) encode all <NUM> alphabet symbols into the first DHT of a Huffman encoder (i.e., the DHT encoding the literals, End-of-Block, and the length symbols) would require N-bit counters. For example, LZ77 compression on <NUM> MB of data, using all <NUM> symbols, would require <NUM>-bit counters. In another example, LZ77 compression on <NUM> MB of data, using all <NUM> symbols, would require <NUM>-bit counters.

To store the counts associated with each of these <NUM> symbols, a sort block can be used to store <NUM> "symbol, count" pairs. In a hardware implementation, these pairs are stored in latches. Continuing from the previous example, to store <NUM> symbols having <NUM>-bit counters requires <NUM>,<NUM> latches (sometimes referred to as flipflops). While this latch requirement is already area-intensive, the number of latches required increases by N for each additional bit required by the counters. For example, storing <NUM> symbols using <NUM>-bit counters (for a <NUM> MB data stream) requires <NUM>,<NUM> latches. Similarly, storing <NUM> symbols using <NUM>-bit counters (for a <NUM> MB data stream) requires <NUM>,<NUM> latches.

Turning now to an overview of the aspects of the inventive teachings, one or more embodiments address the above-described shortcomings of the prior art by providing new accelerator hardware and software implementations for reducing the latch count required for symbol sorting when generating dynamic Huffman tables. The latch count is reduced by mapping the X-bit symbol frequencies received from the LZ77 compressor (sometimes referred to as the "LZ count") to a Y-bit float-like representation that requires less than X bits (i.e., X is greater than Y) prior to sorting. The following process is explicitly demonstrated with respect to a <NUM>-bit counter, however, it is understood that a low count mapping can be adapted to work for any N-bit counter. The <NUM>-bit counter is merely selected for ease of discussion.

In some embodiments of the invention, a <NUM>-bit counter (for <NUM> MB of data) can be mapped to a <NUM>-bit value. To accomplish this, the <NUM>-bit value is mapped to a <NUM>-bit exponent (also referred to as a shift field) and a <NUM>-bit mantissa (also referred to as the most significant digits).

The <NUM>-bit exponent represents the position of first "<NUM>" in the <NUM>-bit counter (this bit is referred to as the shift bit). Mathematically, the <NUM>-bit exponent is the amount of shift needed to get the original value. For example, the first (most significant) "<NUM>" in the <NUM>-bit value "<NUM><NUM><NUM>" occurs at the <NUM>th digit (read from the right). The <NUM>th digit can be encoded as the <NUM>-bit binary number "<NUM>.

Once this shift is known, the "<NUM>" bits to the left of the shift bit can be discarded without losing any information. Note that a <NUM>-bit exponent is needed to store every possible location of the shift bit in a <NUM>-bit counter (<NUM> binary digits are needed to uniquely encode the <NUM> shift possibilities). While shown as a <NUM>-bit exponent, the number of bits can be more, or less, depending on the underlying counter that is being mapped. For example, a <NUM>-bit counter requires a <NUM>-bit exponent for an exhaustive mapping of the shift bit.

The <NUM>-bit mantissa contains the five most significant bits of non-zero data present in <NUM>-bit counter. In some embodiments of the invention, the <NUM>-bit mantissa includes the shift bit, while in other embodiments the shift bit is skipped. For example, the <NUM>-bit mantissa generated from the previous example, "<NUM><NUM><NUM>," is "<NUM><NUM>" (when including the shift bit and the next four digits) and "<NUM>" (when skipping the shift bit and including the next five digits).

In either case, these <NUM>-bit values are then combined to provide a <NUM>-bit many-to-one mapping of the <NUM>-bit counter. A "many-to-one" mapping refers to any mapping where two or more input values will map to the same output value. Continuing with the previous example, multiple <NUM>-bit counters will map to the same <NUM>-bit value.

While both approaches are possible and within the contemplated scope of the invention, the second approach leverages one extra bit of data (the shift bit is not re-used). Consequently, the second approach can reduce the number of many-to-one mappings which would be generated using the first approach. Continuing from the previous <NUM>-bit example, the first approach (shift bit is the first digit of mantissa) results in a <NUM>-<NUM> mapping, while the second approach (ignore the shift bit) results in a <NUM>-<NUM> mapping. To illustrate, for LZ counts having a value of "1_ _ _ _XXXXX" (where "_" denotes bit values that are the same in all the LZ counts and "X" indicates different bit values), all <NUM> of these numbers would be mapped to <NUM> number (i.e., a <NUM>:<NUM> mapping). Alternatively, for LZ counts having a value of "1_ _ _ _ _XXXX," only <NUM> of these numbers would be mapped to <NUM> number (i.e., a <NUM>:<NUM> mapping).

To illustrate this point further, consider the <NUM>-bit mappings of the <NUM>-bit representations of the numbers <NUM> and <NUM>, "<NUM><NUM>" and "<NUM><NUM>," respectively (leading zeros have been discarded). Reusing the shift bit (here, the <NUM>th digit from the right, having a binary value of "<NUM>") results in same <NUM>-bit numbers: "<NUM>,<NUM>" and "<NUM>,<NUM>. " Ignoring the shift bit in the mantissa, however, results in the unique <NUM>-bit numbers "<NUM>,<NUM>" and "<NUM>,<NUM>.

Constructing the many-to-one mapping in this manner (shift, mantissa) results in a loss of the exact count (or frequency) for each symbol but preserves the relative frequency distribution of the symbols. For example, consider symbols "A," "B," "C," and "D" having frequency counts in a <NUM> MB data stream of <NUM>, <NUM>, <NUM>, <NUM>, respectively. <NUM>-bit counters can fully encode the exact "symbol, count" pair for all <NUM> symbols in the sort block. The <NUM>-bit mapping (<NUM>-bit shift, <NUM>-bit mantissa) will lose the exact count values for these symbols, but will preserve the relative frequencies (i.e., D count >= C count >= B count >= A count).

Because the relative symbol frequencies are preserved, the latch count can be reduced without impacting the DHT tree quality. In other words, the present disclosure allows for Huffman trees to be populated without knowing the exact frequencies of the symbols. Moreover, because the deflate algorithm does not allow DHT trees to be more than <NUM> levels deep (i.e. the encode length should be <NUM> bits or less), allowing many-to-one mappings for high-frequency symbols does not introduce errors into the DHT tree.

Reducing the number of latches for a given sort block frees valuable wafer area, reduces power consumption, and simplifies the timing/wiring of the accelerator hardware. Continuing with the previous example, mapping a <NUM>-bit counter to a <NUM>-bit value prior to the sorting block reduces the number of required latches from <NUM>,<NUM> latches (<NUM> * <NUM>) to <NUM>,<NUM> latches (<NUM> * <NUM>). Moreover, the use of <NUM>-bit values simplifies the later sorting step, as <NUM>-bit comparators can replace the conventional <NUM>-bit comparators. This results in further area savings.

In some embodiments of the invention, the widths of the exponent (shift) and mantissa are fixed (e.g., <NUM>-bits each, as previously discussed). In some embodiments of the invention, the widths of the exponent (shift) and mantissa can be dynamically adjusted. The widths can be adjusted, for example, depending on the LZ-count range.

To illustrate, consider "K" bits implemented to represent the LZ count in "shift, mantissa" format (i.e., "K" was <NUM> in the previous examples using a <NUM>-bit exponent and a <NUM>-bit mantissa). Depending on upper bound of LZ count, "i" bits can be assigned to the shift bit and "K-i" bits can be assigned to the mantissa. This results in a finite improvement in sorting accuracy for the same, fixed hardware cost.

Table <NUM> illustrates exemplary dynamic widths based on various LZ-count ranges. As shown in Table <NUM>, the many-to-one mapping can be decreased as the LZ count range increases by dynamically allocating extra bits to the mantissa. While Table <NUM> illustrates shifting a single bit from the shift field to the mantissa, other dynamic adjustments are possible.

In some embodiments of the invention, the width of the shift field is made as small as possible, based on the LZ Count Range, to free extra bits for the mantissa. The width of the shift field can be decreased until the point where the loss of a bit will result in some shift bit locations no longer being uniquely assignable.

With reference now to <FIG>, a computer system <NUM> is illustrated in accordance with a non-limiting embodiment of the present disclosure. The computer system <NUM> can be based on the z/Architecture, for example, offered by International Business Machines Corporation (IBM). This architecture, however, is but one example of the computer system <NUM> and is not intended to suggest any limitation as to the scope of use or functionality of embodiments described herein. Other system configurations are possible. Regardless, computer system <NUM> is capable of being implemented and/or performing any of the functionality set forth hereinabove.

Computer system <NUM> is operational with numerous other general purpose or special purpose computing system environments or configurations. Examples of well-known computing systems, environments, and/or configurations that may be suitable for use with computer system <NUM> include, but are not limited to, personal computer systems, server computer systems, thin clients, thick clients, cellular telephones, handheld or laptop devices, multiprocessor systems, microprocessor-based systems, set top boxes, programmable consumer electronics, network PCs, minicomputer systems, mainframe computer systems, and distributed cloud computing environments that include any of the above systems or devices, and the like.

Computer system <NUM> may be described in the general context of computer system-executable instructions, such as program modules, being executed by the computer system <NUM>. Generally, program modules may include routines, programs, objects, components, logic, data structures, and so on that perform particular tasks or implement particular abstract data types. Computer system <NUM> may be practiced in distributed cloud computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer system storage media including memory storage devices.

As shown in <FIG>, computer system <NUM> is depicted in the form of a general-purpose computing device, also referred to as a processing device. The components of computer system <NUM> may include, but are not limited to, one or more processors or processing unit(s) <NUM>, a deflate accelerator <NUM>, a system memory <NUM>, and a bus <NUM> that couples various system components including system memory <NUM> to processing unit <NUM>.

The deflate accelerator <NUM> can be implemented as hardware or as both hardware and software and can include functionality and modules for compressing data using the DEFLATE data compression algorithm according to one or more embodiments. In some embodiments of the invention, the deflate accelerator <NUM> can receive data on an input buffer, process the data using an LZ77 compressor, encode the data using a Huffman encoder, and output the data to an output buffer. An embodiment of the deflate accelerator <NUM> is depicted in <FIG>.

In some embodiments of the invention, the deflate accelerator <NUM> can be connected directly to the bus <NUM> (as depicted). In some embodiments of the invention, the deflate accelerator <NUM> is connected to the bus <NUM> between the RAM <NUM>/cache <NUM> and the processing unit <NUM>. In some embodiments of the invention, the deflate accelerator <NUM> is directly connected to the cache <NUM> (e.g., to the L3 cache), rather than to the bus <NUM>. In some embodiments of the invention, the deflate accelerator <NUM> is directly connected to the processing unit <NUM>.

Bus <NUM> represents one or more of any of several types of bus structures, including a memory bus or memory controller, a peripheral bus, an accelerated graphics port, and a processor or local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnects (PCI) bus.

Computer system <NUM> may include a variety of computer system readable media. Such media may be any available media that is accessible by computer system/server <NUM>, and it includes both volatile and non-volatile media, removable and non-removable media.

System memory <NUM> can include an operating system (OS) <NUM>, along with computer system readable media in the form of volatile memory, such as random access memory (RAM) <NUM> and/or cache <NUM>. Computer system <NUM> may further include other removable/non-removable, volatile/non-volatile computer system storage media. By way of example only, storage system <NUM> can be provided for reading from and writing to a non-removable, non-volatile magnetic media (not shown and typically called a "hard drive"). Although not shown, a magnetic disk drive for reading from and writing to a removable, non-volatile magnetic disk (e.g., a "floppy disk"), and an optical disk drive for reading from or writing to a removable, non-volatile optical disk such as a CD-ROM, DVD-ROM or other optical media can be provided. In such instances, each can be connected to bus <NUM> by one or more data media interfaces. As will be further depicted and described below, memory <NUM> may include at least one program product having a set (e.g., at least one) of program modules that are configured to carry out the functions of embodiments of the disclosure.

The OS <NUM> controls the execution of other computer programs and provides scheduling, input-output control, file and data management, memory management, and communication control and related services. The OS <NUM> can also include a library API (not shown in <FIG>). The library API is a software library that includes APIs for performing the data manipulation functions provided by the specialized hardware devices such as, for example, an accelerator (not shown in <FIG>).

The storage system <NUM> can store a basic input output system (BIOS). The BIOS is a set of essential routines that initialize and test hardware at startup, start execution of the OS <NUM>, and support the transfer of data among the hardware devices. When the computer system <NUM> is in operation, one or more of the processing units <NUM> are configured to execute instructions stored within the storage system <NUM>, to communicate data to and from the memory <NUM>, and to generally control operations of the computer system <NUM> pursuant to the instructions.

One or more of the processing unit <NUM> can also access internal millicode (not depicted) and data stored therein. The internal millicode (sometimes referred to as firmware) can be viewed as a data storage area that is separate and different from the main memory <NUM> and can be accessed or controlled independent from the OS. The internal millicode can contain part of the complex architected instructions of the computer system <NUM>. A complex instruction can be defined as a single instruction to the programmer; however, it may also include internally licensed code which breaks one complex instruction into many less complex instructions. The millicode contains algorithms that have been designed and tested specifically for computer system <NUM> and can provide full control over the hardware. In at least one embodiment, the millicode can also be utilized to store one or more compression dictionaries, which can be delivered to the hardware to facilitate data decompression as described in greater detail below.

Program/utility <NUM>, having a set (at least one) of program modules <NUM>, may be stored in memory <NUM> by way of example, and not limitation, as well as the OS <NUM>, one or more application programs, other program modules, and program data. Each of the operating system, one or more application programs, other program modules, and program data or some combination thereof, may include an implementation of a networking environment. Program modules <NUM> generally carry out the functions and/or methodologies of embodiments of the invention as described herein.

Computer system <NUM> may also communicate with one or more external devices <NUM> such as a keyboard, a pointing device, a display <NUM>, etc.; one or more devices that enable a user to interact with computer system/server <NUM>; and/or any devices (e.g., network card, modem, etc.) that enable computer system/server <NUM> to communicate with one or more other computing devices. Such communication can occur via Input/Output (I/O) interfaces <NUM>. Still yet, computer system <NUM> can communicate with one or more networks such as a local area network (LAN), a general wide area network (WAN), and/or a public network (e.g., the Internet) via network adapter <NUM>. As depicted, network adapter <NUM> communicates with the other components of computer system <NUM> via bus <NUM>. It should be understood that although not shown, other hardware and/or software components could be used in conjunction with computer system <NUM>. Examples include, but are not limited to: microcode, device drivers, redundant processing units, external disk drive arrays, RAID systems, tape drives, data archival storage systems, etc..

Various types of compression algorithms can be utilized in the computer system <NUM> such as, for example, an adaptive lossless data compression (ALDC) family of products which utilize a derivative of Lempel-Ziv encoding to compress data. As a general compression technique, the Lempel-Ziv <NUM> (LZ77) algorithm integrates well into systems required to handle many different data types. This algorithm processes a sequence of bytes by keeping a recent history of the bytes processed and pointing to matching sequences within the history. Compression is achieved by replacing matching byte sequences with a copy pointer and length code that together are smaller in size than the replaced byte sequence.

The compression algorithm can also include the "DEFLATE" compression format, which uses a combination of the LZ77 algorithm (which removes repetitions from the data) and Huffman coding. The Huffman encoding is entropy encoding that is based on a "Huffman tree". To Huffman encode and decode data, a system must know in advance that the Huffman tree is being used. To accommodate decompression (e.g., an "Inflate" operation), the Huffman tree is written at the header of every compressed block. In one embodiment, two options are provided for Huffman trees in the Deflate standard. One option is a "static" tree, which is a single hard-coded Huffman tree, known to all compressors and decompressors. The advantage of using this static tree is that its description does not have to be written in the header of a compressed block, and is ready for immediate decompression. On the other hand, "dynamic" trees are tailored for the data block at hand and an exact description of the dynamic tree must, therefore, be written to the output.

Huffman encoding may also use a variable-length code table based on entropy to encode source symbols, and as previously mentioned, is defined either as either static or dynamic. In static Huffman coding, each literal or distance is encoded using a fixed table (FHT) that is defined in the RFC. In dynamic Huffman coding, however, special coding tables (DHTs) are constructed to better suit the statistics of the data being compressed. In most cases, using a DHT achieves better compression ratio (e.g., quality) when compared to FHT, at the expense of degrading the compression rate (e.g., performance) and adding design complexity. The fixed and dynamic Huffman encoding methods best reflect the built-in tradeoff between compression rate and ratio. The static Huffman method may achieve a lower compression ratio than is possible using dynamic Huffman coding. This is due to using a fixed encoding table regardless of the content of the input data block. For example, random data and a four-letter DNA sequence would be encoded using the same Huffman table.

In some embodiments of the invention, the computer system <NUM> includes a compression library that can be implemented as a software library used for deflation/inflation and can be an abstraction of a compression algorithm. In at least one embodiment, the compression library allows the computer system <NUM> and/or the deflate accelerator <NUM> to break up input data to be deflated/inflated in arbitrary ways across multiple requests and provides arbitrary sized output buffers to hold the results of the deflate/inflate operation.

<FIG> depicts a block diagram of the deflate accelerator <NUM> shown in <FIG> according to one or more embodiments. The deflate accelerator <NUM> can include, for example, an input buffer <NUM>, an LZ77 compressor <NUM>, a Huffman encoder <NUM> (sometimes referred to as a DEFLATE Huffman encoder), and an output buffer <NUM>. As shown in <FIG>, the input buffer <NUM> can be communicatively coupled to the LZ77 compressor <NUM> and the output from the LZ77 compressor <NUM> can be directly connected to the input of the Huffman encoder <NUM>. In this manner, the DEFLATE accelerator <NUM> is configured to facilitate data compression using the DEFLATE algorithm.

In some embodiments of the invention, uncompressed data is obtained by the deflate accelerator <NUM> on the input buffer <NUM> (sometimes referred to as an input data buffer). In some embodiments of the invention, the deflate accelerator <NUM> performs an LZ77 compression on the data provided to the input buffer <NUM>. In some embodiments of the invention, the compressed data is received by, and encoded by, the Huffman encoder <NUM>. In some embodiments of the invention, the compressed and encoded data can be stored in the output buffer <NUM> (sometimes referred to as an output data buffer).

To initiate data compression, the deflate accelerator <NUM> can receive one or more requests to compress targeted data or a targeted data stream in the input buffer <NUM>. In some embodiments of the invention, a request block (not depicted) can be used to facilitate the request. In some embodiments of the invention, the request block is delivered to a compression interface of the OS <NUM>. For each request, the computer system <NUM> can supply an input buffer (e.g., the input buffer <NUM>) with the data to be processed and an output buffer (e.g., the output buffer <NUM>) where the processed data results are stored.

In some embodiments of the invention, to begin processing a compression request, the deflate accelerator <NUM> reads a request block, and processes the data in the input buffer <NUM> to generate compressed or and/or decompressed data. As described herein, various compression algorithms can be employed including, but not limited to, the DEFLATE compression algorithm and ALDC algorithms. The resulting compressed data can be saved in the output buffer <NUM>.

<FIG> depicts a block diagram of a DHT generator <NUM> of the Huffman encoder <NUM> shown in <FIG> according to one or more embodiments. As illustrated in <FIG>, the DHT generator <NUM> can include a sort module <NUM>, a Huffman tree module <NUM>, tree static random access memory (SRAM) <NUM>, a tree walk module <NUM>, code length SRAM <NUM>, and a encode length module <NUM>. In some embodiments of the invention, the DHT generator <NUM> is a first stage of a Huffman encoder (e.g., the Huffman encoder <NUM> shown in <FIG>).

The sort module <NUM> receives a symbol frequency counter ("LZ Count," an X-bit counter) for each symbol compressed by the LZ77 compressor <NUM>. The sort module <NUM> then maps the X-bit counter to a compressed many-to-one Y-bit value according to one or more embodiments. In some embodiments of the invention, the Y-bit values are sorted (generating a relative frequency distribution of the symbols, as discussed previously herein).

In some embodiments of the invention, the Y-bit mappings can be decompressed back into X-bit values after sorting, but prior to the Huffman tree module <NUM>. In this manner, the Huffman tree module <NUM> can receive full X-bit values and does not need to be modified. Similarly, any remaining downstream modules, including the Huffman tree module <NUM>, tree SRAM <NUM>, the tree walk module <NUM>, code length SRAM <NUM>, and the encode length module <NUM> do not need to be modified. In other words, the Huffman tree module <NUM>, tree SRAM <NUM>, tree walk module <NUM>, code length SRAM <NUM>, and encode length module <NUM> can be implemented using known DEFLATE compression implementations and are not meant to be limited. While depicted as having separate modules for ease of discussion, it is understood that the DHT generator <NUM> can include more, or fewer modules. For example, the output of the sort module <NUM> can be received and encoded into a DHT by a single Huffman tree module and may or may not include separate tree SRAM and/or code length SRAM.

<FIG> depicts a block diagram of the sort module <NUM> shown in <FIG> according to one or more embodiments. As depicted in <FIG>, the sort module <NUM> (also referred to as a sort block) can include a bit translator. The <NUM>-Bit to <NUM>-Bit Translator <NUM> is depicted for ease of discussion; other X-Bit to Y-Bit translations are possible, as previously discussed herein.

In some embodiments of the invention, the <NUM>-Bit to <NUM>-Bit Translator <NUM> receives a <NUM>-bit counter from an LZ77 compressor (e.g., the LZ77 compressor <NUM> depicted in <FIG>). In some embodiments of the invention, the <NUM>-Bit to <NUM>-Bit Translator <NUM> generates a <NUM>-bit exponent and a <NUM>-bit mantissa based on the <NUM>-bit counter according to the following algorithm:.

In some embodiments of the invention, the <NUM>-Bit to <NUM>-Bit Translator <NUM> receives a <NUM>-bit counter from the LZ77 compressor for each symbol in a data stream (e.g., <NUM><NUM>-bit counters for each of <NUM> symbols in a DHT). In some embodiments of the invention, a <NUM>-bit value is generated for each of the <NUM>-bit counters. These <NUM>-bit values can be passed to a sorting module <NUM>.

In some embodiments of the invention, the sorting module <NUM> completes a value sort of the <NUM><NUM>-bit values. The sorting of the <NUM>-bit values can be accomplished using any suitable method known for DEFLATE accelerators. In some embodiments of the invention, the sorting module <NUM> stores <NUM> "symbol, count" pairs in <NUM>,<NUM> latches and uses a <NUM>-D shear sort for fast execution. For a <NUM>-D shear sort, the <NUM> "symbol, count" pairs can be arranged in a 18x16 matrix populated with <NUM> comparators. The comparators are spaced such that no two comparators are horizontally or vertically adjacent (immediately left, right, up, or down). Instead, each of the comparators is diagonally adjacent to one or more other comparators. Advantageously, <NUM>-bit comparators can be used instead of <NUM>-bit comparators, further increasing the area savings afforded by the <NUM>-bit mappings. In some embodiments of the invention, the sorted <NUM>-bit values can then be used to generate a dynamic Huffman tree.

In some embodiments of the invention, downstream processes (after sorting) require conversion back to <NUM>-bit values. This allows, for example, an easy addition of LZ counts from <NUM> ascending symbols and a comparison of the LZ count of the next symbol. In some embodiments of the invention, a <NUM>-Bit to <NUM>-Bit decompressor <NUM> receives each <NUM>-bit number from the sorting module <NUM> and converts each back to a <NUM>-bit number. A <NUM>-Bit to <NUM>-Bit decompressor is depicted for ease of discussion; other Y-Bit to X-Bit decompressors are possible, as previously discussed herein.

A <NUM>-bit number can be constructed from the <NUM>-bit number according to the following algorithm: Step <NUM>. Generate a <NUM>-bit field with all digits set to "<NUM>. " Step <NUM>. Copy the mantissa from the <NUM>-bit number into the least significant digits of the <NUM>-bit number. Step <NUM>. Shift by the value of the shift bit (or shift bit less one, if the shift bit is ignored in the mantissa) and insert the shift bit if not included in the mantissa. Step <NUM>. Discard five of the leading bits (always "<NUM>" by construction) to convert the <NUM>-bit field to a <NUM>-bit field.

To illustrate, consider the <NUM>-bit number "<NUM>,<NUM>" generated, for example, from the compression of the number <NUM> as discussed previously herein (mantissa ignoring the shift bit). At step <NUM>, the <NUM>-bit field is set to "<NUM>. <NUM>" (leading zeros truncated). At step <NUM>, the <NUM>-bit field is shifted <NUM> digits (<NUM> is the decimal value of the shift bit "<NUM>") and the shift bit is inserted, resulting in "<NUM>. " At step <NUM>, five of the leading "<NUM>" (the leftmost digits) are dropped, resulting in the <NUM>-bit number "<NUM><NUM><NUM>. " While the previous example is provided in the context of a <NUM>-Bit to <NUM>-Bit decompressor, the same scheme can be used to decompress an LZ Count having any initial bit width (e.g., <NUM> bits, <NUM>, bits, <NUM> bits, etc.).

<FIG> depicts a flow diagram <NUM> illustrating a method for reducing a latch count required for symbol sorting when generating a dynamic Huffman table according to a non-limiting embodiment. As shown at block <NUM>, a plurality of first symbol counts is determined. Each of the first symbol counts can include a first bit width. In some embodiments of the invention, each of the first symbol counts is encoded as a <NUM>-bit number.

At block <NUM>, a plurality of second symbol counts is generated based on a mapping of the plurality of first symbol counts. The second symbol counts can include a second bit width less than the first bit width. In some embodiments of the invention, each of the second symbol counts is encoded as a <NUM>-bit number.

In some embodiments of the invention, generating each of the second symbol counts includes generating a <NUM>-bit shift field and a <NUM>-bit mantissa according to one or more embodiments. In some embodiments of the invention, the <NUM>-bit shift field encodes a position of the most significant non-zero bit of the first symbol (i.e., the shift bit, as discussed previously herein). In some embodiments of the invention, the <NUM>-bit mantissa encodes the most significant non-zero bit and the next four bits of the first symbol (i.e., the shift bit is reused as the first digit in the mantissa). In some embodiments of the invention, the <NUM>-bit mantissa encodes the next five bits of the first symbol following the most significant non-zero bit (i.e., the shift bit is not reused in the mantissa). In some embodiments of the invention, the <NUM>-bit shift field and the <NUM>-bit mantissa are concatenated to form a <NUM>-bit number.

At block <NUM>, the plurality of second symbol counts is sorted by frequency. At block <NUM>, a dynamic Huffman tree is generated based on the sorted plurality of second symbol counts according to one or more embodiments. In some embodiments of the invention, the <NUM>-bit mappings are decompressed back to <NUM>-bit numbers prior to generating the dynamic Huffman tree, as discussed previously herein.

<FIG> depicts a flow diagram <NUM> illustrating a method according to a non-limiting embodiment. As shown at block <NUM>, a data stream comprising a first symbol can be received from an input buffer.

At block <NUM>, a first symbol count having a first bit width can be determined, based on the first symbol. In some embodiments of the invention, the first bit width is <NUM> bits.

At block <NUM>, a <NUM>-bit shift field is generated based on the first symbol count. In some embodiments of the invention, the <NUM>-bit shift field encodes a position of the most significant non-zero bit of the first symbol.

At block <NUM>, a <NUM>-bit mantissa is generated based on the first symbol count. In some embodiments of the invention, the <NUM>-bit mantissa encodes the next five bits of the first symbol following the most significant non-zero bit.

At block <NUM>, a second symbol count having a second bit width is generated by concatenating the <NUM>-bit shift field and the <NUM>-bit mantissa. At block <NUM>, a frequency of the second symbol count is sorted.

The network may include copper transmission cables, optical transmission fibers, wireless transmission, routers, firewalls, switches, gateway computers and/or edge servers.

In some embodiments, electronic circuitry including, for example, programmable logic circuitry, field-programmable gate arrays (FPGA), or programmable logic arrays (PLA) may execute the computer readable program instruction by utilizing state information of the computer readable program instructions to personalize the electronic circuitry, in order to perform aspects of the present invention.

These computer readable program instructions may also be stored in a computer readable storage medium that can direct a computer, a programmable data processing apparatus, and/or other devices to function in a particular manner, such that the computer readable storage medium having instructions stored therein includes an article of manufacture including instructions which implement aspects of the function/act specified in the flowchart and/or block diagram block or blocks.

In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of instructions, which includes one or more executable instructions for implementing the specified logical function(s).

Claim 1:
An accelerator comprising:
an input buffer (<NUM>);
a Lempel-Ziv <NUM>, LZ77, compressor (<NUM>) communicatively coupled to an output of the input buffer;
a Huffman encoder (<NUM>) communicatively coupled to the LZ77 compressor, the Huffman encoder comprising a bit translator (<NUM>) configured to map a first symbol count comprising a first bit width to a second symbol count comprising a second bit width of less than the first bit width, wherein the bit translator is configured to generate a bit shift field to encode a position of the most significant non-zero bit of the first symbol and a bit mantissa, wherein the bit shift field has a number of digits needed to uniquely encode the shift possibilities of the first symbol count; and
an output buffer (<NUM>) communicatively coupled to the Huffman encoder.