Patent Description:
In general, to overcome this transmission problem, delta coding is known in the prior art, as exemplified, for example, by <CIT>) which discloses a compression encoding technique that divides a series of data values into groups, and for each group a minimum number of bits is determined that is sufficiently large to encode each of the data values without a loss in data, based on a property of the data values that is common within the group.

As described herein, the bandwidth consumed by video/graphics images (or other bit streams) can be reduced by implementing delta color compression to represent colors of pixels in a block based on a color of a reference pixel and delta values that represent differences between the colors of the other pixels and the color of the reference pixel. A compressor subdivides the pixels in each block into groups. The compressor determines a minimum number of bits, B_i, that are needed to represent the delta values of the pixels in group i and the compressor determines a minimum number of bits (M) that represents the smallest value of the number of bits that represents the delta values in the groups of the block. The compressor also determines a number of bits (B) that are required to indicate the difference between the minimum number of bits and a maximum number of bits that represents the largest value of the number of bits needed to represent the delta values in the groups of the block. The values of M and B are included in a block header that is transmitted from the compressor to a decompressor in association with the resulting compressed pixel data. The values of M and B can be encoded separately for inclusion in the block header or a combination of the values of M and B can be encoded using an encoding that represents all possible combinations for M and B. The compressor also generates group headers that include values of the difference between B_i and M (B_i - M) that, in combination with M, indicate the number of bits that represent the delta values in the corresponding group. The compressor can compress the delta values for pixels in each group using the number of bits indicated by the corresponding group header and the decompressor can use the information in the block header and the group headers to decompress the compressed information. Some embodiments of the compressor apply the compression algorithm to different group configurations and select the best group configuration that produces the highest level of compression. The compressor includes information in the block header that indicates the selected group configuration.

Delta values inside each group can be zero, positive, or negative numbers. As such, one sign bit is required for each delta value in a group. Some embodiments of the compressor further reduce the number of bits used to represent the pixels in the blocks based on characteristics of the delta values in the groups. For example, the bit representative of the sign of each delta value can be dropped if all the delta values in a group are either positive (including zero) or negative (including zero). The compressor can include bits in the group headers to indicate whether the group is all positive, all negative, or mixed so that the decompressor will know how to decompress the delta values. Some embodiments of the compressor use one bit for one configuration (e.g., all-positive) and two bits for the other two configurations (e.g., all-negative and mixed) as long as the selected <NUM>-bit code and <NUM>-bit code start with different bit values so that the decompressor can distinguish between the codes. Another possibility is to combine sign bits of all groups together and assign one code to all sign bits instead of using different one-bit and two-bit codes for different groups. A net gain in compression is produced if the number of bits saved by eliminating one bit for each delta value is more than the number of bits added to represent signs of the groups. The number of bits used to represent the delta values in a group can also be reduced if a maximum absolute delta value for a pixel in the group is equal to a power-of-two, as discussed herein. In some variations, a bypass bit is included in each block header to enable or disable these features. The bypass bit can be dropped if all the delta values in a block are zero, i.e., all the pixels in the block have the same color value.

<FIG> is a block diagram of a processing system <NUM> according to some embodiments. The processing system <NUM> includes a processing device <NUM> that is connected to one or more external memories such as a dynamic random access memory (DRAM) <NUM>. The processing device <NUM> includes a plurality of compute units <NUM>, <NUM>, <NUM>, <NUM> (collectively referred to as the "compute units <NUM>-<NUM>") such as CPUs or GPUs. For example, the processing device <NUM> may be a system-on-a-chip (SOC) such as an accelerated processing unit (APU) or accelerated processing device (APD) that is formed on a substrate. Each of the compute units <NUM>-<NUM> includes a plurality of processor cores that can concurrently process different instructions. The compute units <NUM>-<NUM> also include one or more resources that are shared by the processor cores, such as caches, arithmetic logic units, floating-point units, branch prediction logic, memory or bus interfaces, and the like.

The processing device <NUM> includes data storage units <NUM>, <NUM> for storing instructions or data that may be used by the compute units <NUM>-<NUM> or other entities in the processing device <NUM>. Some embodiments of the data storage units <NUM>, <NUM> are implemented with DRAM. A memory controller (MC) <NUM> is used to coordinate the flow of data between the processing device <NUM> and the DRAM <NUM> over a memory interface <NUM>. The memory controller <NUM> includes logic used to control reading information from the DRAM <NUM> and writing information to the DRAM <NUM>. The compute units <NUM>-<NUM> are able to communicate with each other, with the data storage units <NUM>, <NUM>, with the memory controller <NUM>, or with other entities in the processing system <NUM> using a bus <NUM>. For example, the compute units <NUM>-<NUM> typically include a physical layer interface or bus interface for asserting signals onto the bus <NUM> and receiving signals from the bus <NUM> that are addressed to the corresponding compute unit <NUM>-<NUM>. Some embodiments of the processing device <NUM> also include one or more bridges such as a northbridge or a southbridge for facilitating communication between entities in the processing device <NUM>.

The processing device <NUM> implements an operating system (OS) or one or more applications <NUM> that generate workloads in the processing device <NUM>. Although a single instance of the OS/applications <NUM> is shown in <FIG>, some embodiments of the processing device <NUM> implement multiple instantiations of the operating system or one or more of the applications. For example, virtual machines executing on the compute units <NUM>-<NUM> are able to execute separate instances of the operating system or one or more of the applications.

Some embodiments of the processing device <NUM> perform graphics processing to render scenes represented by a <NUM>-D model to generate images for display on a screen <NUM>. For example, one or more of the compute units <NUM>-<NUM> can access information representative of the <NUM>-D model stored on the DRAM <NUM> via the bus <NUM> and the interface <NUM>. The compute units <NUM>-<NUM> then use the accessed information to render a portion of the scene to generate an image for display on the screen <NUM>. The compute units <NUM>-<NUM> transmit information representative of the rendered images to the screen <NUM> via the bus <NUM>. Information is conveyed between the entities in the processing system <NUM> as streams of bits. As discussed herein, the volume of traffic generated by the compute units <NUM>-<NUM>, the DRAM <NUM>, the data storage unit <NUM>, the data storage unit <NUM>, the screen <NUM>, or other entities in the processing system <NUM> can severely tax the bandwidth available in the memory interface <NUM>, the bus <NUM>, or other interconnections in the processing system <NUM>, particularly for graphics applications that generate bitstreams representative of video or graphic information.

Delta color compression and bit packing are used to compress bitstreams that are representative of video or graphic information, such as the colors of pixels that represent images for display on the screen <NUM>. Some embodiments of the compute units <NUM>-<NUM> (or other entities in the processing system <NUM> that generate streams of bits) implement compressors (not shown in <FIG>) to perform the delta color compression and bit packing. The compressors are implemented as hardware, firmware, software, or a combination thereof that can be executed on the corresponding compute units <NUM>-<NUM>. The compressors can be implemented as stand-alone entities that receive information from the compute units <NUM>-<NUM> or other entities. Some embodiments of the compressors compute delta values for pixels in blocks that make up a frame. For example, each block can include an <NUM> x <NUM> set of pixels, e.g., <NUM> pixels, that represent a square portion of the image. Each delta value represents a difference between a color of a corresponding pixel and a reference color of a reference pixel selected from the plurality of pixels. The compressor can subdivide the pixels in the block into a groups such as eight <NUM> x <NUM> groups of pixels or eight <NUM> x <NUM> groups of pixels. The compressor can then generate a compressed bitstream that represents the delta values using a smaller number of bits than the uncompressed bitstream. For example, as discussed herein, the compressor can generate a compressed bitstream that includes a block header associated with the block of pixels, group headers associated with the subdivided groups of pixels, and encoded delta values. The delta values for each group are encoded using different numbers of bits, as indicated by information included in the block header and the corresponding group header. Decompressors (not shown in <FIG>) can decompress the compressed bitstream to recover the bits in the uncompressed bitstream, as discussed herein.

<FIG> is a block diagram of a portion <NUM> of a processing system according to some embodiments. The portion <NUM> includes a compressor <NUM> and a decompressor <NUM> that are implemented in hardware, firmware, software, or a combination thereof. Some embodiments of the compressor <NUM> and the decompressor <NUM> are implemented at different locations in the processing system <NUM> shown in <FIG>. For example, the compressor <NUM> can be implemented as part of one of the compute units <NUM>-<NUM> (or configured to receive bits from the compute units <NUM>-<NUM>) and the decompressor <NUM> can be implemented as part of the DRAM <NUM> or the screen <NUM> (or configured to provide bits to the DRAM <NUM> or the screen <NUM>). The compressor <NUM> receives an uncompressed bitstream <NUM>, which represents colors of pixels in frame in some cases. The compressor <NUM> compresses the uncompressed bitstream <NUM> according to some embodiments of the delta color compression and bit packing techniques described herein to generate a compressed bitstream <NUM> that is provided to the decompressor <NUM>. The decompressor <NUM> decompresses the compressed bitstream <NUM> to recover an uncompressed bitstream <NUM>, which includes the same bits as the uncompressed bitstream <NUM> or different bits depending upon whether the compression is lossless or lossy and whether errors occurred in transmission of the compressed bitstream <NUM>.

<FIG> is a flow diagram of a method <NUM> for performing delta color compression and bit packing according to some embodiments. The method <NUM> is implemented in some embodiments of the compressor <NUM> shown in <FIG>. The method <NUM> is applied to a block of pixels such as an <NUM> x <NUM> block, which preserves memory addressability by using a block size of <NUM> bytes. Memory addressability can also be preserved in other cases by choosing other sizes of blocks of pixels so that they are aligned to a particular number of bytes such as <NUM> bytes. Some embodiments of the method <NUM> can be performed iteratively or multiple instances of the method <NUM> can be performed concurrently or in parallel (e.g., on multiple processor cores implemented in the compute units <NUM>-<NUM> shown in <FIG>) to perform delta color compression and bit packing on multiple blocks such as the blocks of pixels that represent an image for display on a screen. Decompression of bitstreams that are compressed according to the method <NUM> is performed by some embodiments of the decompressor <NUM> shown in <FIG>, as discussed herein.

At block <NUM>, the compressor chooses a reference pixel from among the pixels in the block and determines a color value for the reference pixel. For example, the color value for the reference pixel can be represented by values of eight bits if an <NUM>-bit color depth (or color gamut) is used to represent the colors of the pixels. In some variations, the compressor chooses more than one pixel as a potential reference pixel and then selects one pixel from the potential reference pixels to use as a reference. Information identifying the potential reference pixels is included in a corresponding block header. The compressor then defines delta values that represent a difference between the color value of the reference pixel and color values of the other pixels in the block. The delta values for the pixels can be positive or negative depending on the relative values of the color of the reference pixel and the color of the pixel. The number of pixels that is sufficient to represent the delta values depends on the range of possible delta values of the pixels in the block. For example, if the pixels are represented by an <NUM>-bit color depth, the delta values of the pixels are in the range -<NUM> to +<NUM>. Eight bits are sufficient to represent the absolute value of the delta values, which ranges from <NUM> to <NUM>, and one additional bit is needed to represent the sign of the delta values. In some embodiments, the sign of the delta values is represented by converting negative numbers to even numbers and positive numbers to odd numbers. For example, a series of delta values {<NUM>, <NUM>, -<NUM>, <NUM>, -<NUM>, <NUM>, -<NUM>} can be converted to a series {<NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>} that encodes the positive and negative delta values as even and odd positive values, respectively. For another example, the values <NUM> to <NUM>n-<NUM> -<NUM> can be used to represent the positive delta values and the values <NUM>n-<NUM> to <NUM>n-<NUM> can be used to represent the negative delta values. Other encodings of the positive and negative delta values into all-positive numbers can also be used.

At block <NUM>, the compressor subdivides the block into groups of pixels. For example, in some variations the compressor subdivides the block into eight groups of pixels arranged in <NUM> x <NUM> configurations or eight groups of pixels arranged in <NUM> x <NUM> configurations. In some variations, the values of the pixels in the pixel groups are converted into all-positive numbers, as discussed herein.

At block <NUM>, the compressor determines a group minimum number of bits (B_i) that is sufficient to represent the delta values within each group (i). If the positive and negative delta values have been converted to a series of positive numbers, the group minimum number of bits are determined using: <MAT> where M_i is the maximum delta value for a pixel within the group. For example, the delta values in a first group (i=<NUM>) can have delta values that range from <NUM> to <NUM> so that the delta values for the first group can be represented by three bits (B_i=<NUM>), the delta values in a second group (i=<NUM>) can have delta values that range from <NUM> to <NUM> so that the delta values for the second group can be represented by four bits (B_i=<NUM>), and the delta values in a third group (i=<NUM>) can have delta values that range from <NUM> to <NUM> so that the delta values for the third group can be represented by five bits (B_i=<NUM>). In this example, the delta values for the remaining groups are also represented by <NUM>-<NUM> bits.

At block <NUM>, the compressor determines a number of bits (M) that is equal to a smallest number of bits that is sufficient to represent the delta values in any one of the groups of the block. The minimum number of bits (M) is determined by taking the minimum of the group minimum numbers of bits that are sufficient to represent each of the groups in the block according to: <MAT> Thus, if the delta values for the groups can be represented by <NUM>-<NUM> bits, as in the above example, then the minimum number of bits M=<NUM> for the block.

At block <NUM>, the compressor determines a number of bits (B) that is sufficient to represent a difference between M and the largest number of bits that is sufficient to represent the delta values in the block. The largest number of bits is determined by taking the maximum of the group minimum numbers of bits that are sufficient to represent each of the groups in the block. The number of bits (B) can therefore be determined according to: <MAT> Thus, the number of bits B=<NUM> for the groups in the block if the delta values for the groups can be represented by <NUM>-<NUM> bits, as in the above example.

At block <NUM>, the compressor generates a block header that includes bits representative of M and B. Some embodiments of the block header include a first number of bits to represent M and a second number of bits to represent B. For example, four bits in the block header can be used to represent M and four bits in the block header can be used to represent B if the pixels are represented by an <NUM>-bit color depth, in which case as many as nine bits could be required to represent the delta values in the groups. Some embodiments of the block header alternatively include a number of bits to represent all possible combinations of the values of M and B, which reduces the total number of bits included in the block header. For example, the following table illustrates separate encoding of the values of M and B and a combined encoding of the same values of M and B.

At block <NUM>, the compressor generates a group header for each group i. Some embodiments of the group header include one or more bits to represent a value of Bi-M for the corresponding group. Fewer bits are sufficient to represent the quantity Bi-M, relative to the number of bits that would be sufficient to represent the quantity Bi, except in the case M=<NUM>, in which case the same number of bits is used to represent the quantity Bi-M, and the quantity Bi. Consequently, using the quantity Bi-M to represent the number of bits that are sufficient to represent the delta values in each group reduces the overall number of bits that need to be transmitted from the compressor to the decompressor. For example, if the block uses an <NUM>-bit color depth for the pixels, the quantities M and B are each represented by four bits if M and B are encoded separately. The quantity Bi-M can be represented using B bits so that <NUM>*B bits are sufficient to represent quantity Bi-M for all eight groups.

At block <NUM>, the compressor encodes delta values for each group i using Bi bits to represent the delta values. Returning to the example of block <NUM>, the delta values in the first group (i=<NUM>) are encoded using three bits (B_i=<NUM>), the delta values in the second group (i=<NUM>) are encoded using four bits (B_i=<NUM>), and the delta values in the third group (i=<NUM>) are encoded using five bits (B_i=<NUM>).

At block <NUM>, the compressor transmits the block header, the group headers, and the encoded delta values towards the decompressor. For example, compressors associated with the compute units <NUM>-<NUM> transmit the block header, the group headers, and the encoded delta values via the bus <NUM> towards the memory controller <NUM> or the screen <NUM> shown in <FIG>.

At block <NUM>, the decompressor receives a bitstream that includes bits that represent the block header, the group headers, and the encoded delta values. The decompressor can decompress the bitstream to recover the uncompressed bits that represent the delta values using the information in the block header and the group headers. For example, the decompressor reads the value of B from the block header and uses this value to determine the number of bits that represent the quantity Bi-M for all the groups, i.e. the <NUM>*B bits if the block has been subdivided into eight groups. The decompressor also reads the value of M from the block header. For each group, the decompressor reads the value of the quantity Bi-M from the corresponding group header and combines the value Bi-M with the value of M to determine the value of the quantity Bi for the corresponding group. The decompressor uses the value of the quantity Bi to parse the bits that represent the encoded delta values so that the encoded delta values can be decoded correctly. For example, if the quantity Bi=<NUM> for a group, the decompressor determines that each encoded delta value is represented by three bits in the bitstream.

<FIG> is a block diagram of a block <NUM> of pixels that can be subdivided into groups of pixels in different group configurations according to some embodiments. The block <NUM> includes <NUM> pixels <NUM> (only one indicated by a reference numeral in the interest of clarity) that are arranged in an <NUM> x <NUM> grid. However, other embodiments of the block <NUM> include different numbers of pixels arranged in different patterns. The block <NUM> is subdivided into groups of pixels, e.g., by a compressor such as the compressor <NUM> shown in <FIG>. In a first group configuration, the block <NUM> is subdivided into eight groups <NUM> (only one indicated by a reference numeral in the interest of clarity) that are each arranged in an <NUM> x <NUM> grid configuration. In a second group configuration, the block <NUM> is subdivided into eight groups <NUM> (only one indicated by a reference numeral in the interest of clarity) that are each arranged in a <NUM> x <NUM> grid configuration. Other group configurations can also be used to subdivide the block <NUM> into more or fewer groups.

Some embodiments of the compressor determine a number of bits required to encode delta values for the pixels <NUM> when the block <NUM> is subdivided into different groups according to two or more different group configurations. For example, in the illustrated case of two different group configurations, the block <NUM> can be subdivided into the groups <NUM> according to the first group configuration and the groups <NUM> according to the second configuration. The compressor then executes portions of the method <NUM> shown in <FIG> to estimate the number of bits required to encode the delta values for the pixels <NUM> according to the different group configurations. The compressor then compares the different values of the number of bits and selects the group configuration that results in the smallest number of bits in the compressed bitstream. The selected group configuration is then be used to compress the bitstream, e.g., according to some embodiments of the method <NUM> shown in <FIG>.

<FIG> is a block diagram of a compressed bitstream <NUM> that represents delta values of pixels in a block according to some embodiments. The bitstream <NUM> is generated by some embodiments of the compressor <NUM> to form the compressed bitstream <NUM> shown in <FIG>, e.g., by performing some embodiments of the method <NUM> shown in <FIG>. The bitstream <NUM> shown in <FIG> is generated based on delta values of pixels that are determined based on color values of the pixels that have an <NUM>-bit color depth. However, color depths having larger or smaller numbers of bits can also be used.

The bitstream <NUM> includes a block header <NUM> formed of bits that represent a minimum number of bits (M) that is sufficient to represent the delta values for any group in the block. The block header <NUM> also includes bits that represent a number of bits (B) that is sufficient to represent a difference between M and the largest number of bits that is sufficient to represent the delta values in the block. The values M and B are each represented by four bits so that the block header <NUM> includes at least eight bits for <NUM>-bit pixel depths. However, as discussed herein, a small number of bits can be included in the block header <NUM> to represent all possible combinations of values M and B instead of representing these values separately. Furthermore, as discussed below, some embodiments of the compression algorithm implement features that change the number of bits in the block header <NUM>.

The bitstream <NUM> also includes group headers <NUM>, <NUM> associated with each of the groups of delta values for the block. For example, the group header <NUM> includes bits that represent a value of B<NUM>-M for the group <NUM> and the group header <NUM> includes bits that represent a value of B<NUM>-M for the group <NUM>. As discussed herein, B bits are sufficient to represent values of Bi-M for the groups, so the group headers <NUM>, <NUM> include B bits. However, as discussed below, some embodiments of the compression algorithm implement features that change the number of bits in the group headers <NUM>, <NUM>.

The bitstream <NUM> further includes the encoded delta values for the groups corresponding to the group headers <NUM>, <NUM>. For example, the bitstream <NUM> includes encoded delta values <NUM> for the group <NUM> that is associated with the group header <NUM>. The encoded delta values <NUM> may be represented by Bi bits per encoded delta value. For example, if the eight encoded delta values <NUM> for the group <NUM> are each represented by Bi=<NUM> bits then the encoded delta values <NUM> are represented by <NUM> bits. However, as discussed below, some embodiments of the compression algorithm implement features that change the number of bits that are sufficient to represent the encoded delta values <NUM>.

<FIG> is a flow diagram of a method <NUM> for reducing a number of bits used to represent all-positive delta values or all-negative delta values according to some embodiments. In different variations of the method <NUM>, the number <NUM> is considered positive or negative for the purposes of determining whether the delta values are all-positive or all-negative. The method <NUM> is implemented by some embodiments of the compressor <NUM> shown in <FIG>. A corresponding decompression process is implemented in some embodiments of the decompressor <NUM> shown in <FIG> to decode the compressed bitstream that is generated according to the method <NUM>.

At block <NUM>, the compressor determines whether delta values in a group have all positive values, all negative values, or a mixture of positive values and negative values. The compressor can then add bits to the corresponding group header to indicate all - positive, all-negative, or mixed positive and negative values. Two bits are sufficient to represent the three possible states of the delta values in the group.

At decision block <NUM>, the compressor determines whether the delta values in the group have all-positive values. If so, the compressor drops the sign bits from the delta values in the group at block <NUM>. At block <NUM>, the compressor sets a first sign bit in the corresponding group header to <NUM> to indicate that the delta values in the group have all-positive values. In the illustrated embodiment, the value of a second sign bit in the corresponding group header is set to either <NUM> or <NUM>, or the second sign bit can be left out of the corresponding group header to further reduce the bit count. If the delta values in the group do not have all-positive values, the method flows to decision block <NUM>.

At decision block <NUM>, the compressor determines whether the delta values in the group have all negative values. If so, the compressor drops the sign bits from the delta values in the group at block <NUM>. At block <NUM>, the compressor sets the first and second sign bits in the corresponding group header to <NUM> to indicate that the delta values in the group have all negative values. If the delta values in the group do not have all negative values, the method flows to decision block <NUM>.

At block <NUM>, the compressor sets the first sign bit in the corresponding group header to <NUM> and the second sign bit in the corresponding group header to <NUM> to indicate that the delta values in the group have a mixture of positive and negative values.

The method <NUM> illustrated in <FIG> uses one or two sign bits in each group header to indicate whether the delta values in the corresponding group are all-positive, all -negative, or mixed. However, in some embodiments, the compressor uses a smaller number of bits to represent all possible combinations of the states of the groups in a block. For example, the three possible states of the delta values in eight groups correspond to <NUM>^<NUM>=<NUM> different combinations, which can be represented by <NUM> bits because <NUM>^<NUM> = <NUM>, whereas2^<NUM>=<NUM>. The bits that represent the combinations of the states of the groups and the block may be included in the block header.

<FIG> is a flow diagram of a method <NUM> for encoding delta values in a group that has a maximum delta value equal to a power-of-two according to some embodiments. The method <NUM> is implemented in some embodiments of the compressor <NUM> shown in <FIG>.

At block <NUM>, the compressor reads uncompressed bits representative of the delta values. At block <NUM>, the compressor maps the delta values to all-positive values, as discussed herein. The compressor adds one additional bit to indicate that the sign optimization is being used and one or more additional bits to indicate the sign of the delta value if the delta values are all-negative or if the delta values are a mix of positive and negative values. For example, the compressor can determine values of the additional bits according to some embodiments of the method <NUM> shown in <FIG>.

At decision block <NUM>, the compressor determines whether a maximum absolute delta value for a pixel in the group is equal to a power-of-two (e.g., <NUM>k for k><NUM>). In that case, k+<NUM> bits are required to represent the delta values in the group because the group has been mapped to all-positive values in block <NUM>. If the maximum absolute delta value for pixel in the group is not equal to a power of two, the compressor compresses the uncompressed bits at block <NUM>, e.g., according to some embodiments of the method <NUM> shown in <FIG>. If the maximum absolute delta value for a pixel in the group is equal to a power of two, the compressor encodes each delta value using k bits (instead of using k+<NUM> bits) at block <NUM>.

By encoding the delta values using k bits, delta values that are equal to <NUM>k or <NUM>k-<NUM> would be represented by the same k-bit number. To resolve the degeneracy, at decision block <NUM>, the compressor determines if the delta value is equal to <NUM>k or <NUM>k-<NUM>. If so, the compressor adds (at block <NUM>) a trailing bit and sets the value of the trailing bit to indicate whether the corresponding delta value is equal to <NUM>k-<NUM> or <NUM>k. If the delta value is not equal to <NUM>k or <NUM>k-<NUM>, the compressor bypasses (at block <NUM>) adding the trailing bit.

The example compression algorithm illustrated in <FIG> uses a trailing bit to distinguish between two degenerate encoded values of the delta values. However, in some variations, a smaller number of bits can be used to perform the basic encoding (e.g., less than k bits can be used to encode delta values ranging up to a maximum absolute delta value of <NUM>k for k><NUM>. Additional trailing bits are then used to resolve the resulting degeneracies. For example, if the delta values in a block are <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>, the maximum absolute delta value is <NUM> which is <NUM>^<NUM>+<NUM> or k=<NUM>. Three bits are therefore needed to represent each delta value because the maximum absolute delta value is greater than <NUM>^<NUM>=<NUM>. A total of <NUM>*<NUM>=<NUM> bits is therefore needed to represent all delta values. However, if the maximum absolute delta value evaluated in block <NUM> is equal to <NUM>^n+<NUM>, then the delta values equal to <NUM>^n-<NUM>, <NUM>^n, and <NUM>^n+<NUM> are all encoded as the degenerate value of <NUM>^n-<NUM>. Additional trailing bits are added to the delta values to distinguish between the degenerate values of <NUM>^n-<NUM>, <NUM>^n, and <NUM>^n+<NUM>. For example, a trailing bit of "<NUM>" is added to <NUM>^n-<NUM>, two trailing bits of "<NUM>" are added to <NUM>^n, and two trailing bits "<NUM>" are added to <NUM>^n+<NUM>. The input data stream <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> is then compressed to a series of binary values: <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>. The total number of bits in the compressed binary stream is <NUM>+<NUM>+<NUM>+<NUM>+<NUM>+<NUM> = <NUM>, which is a savings of one bit in this example.

Some embodiments of the compressor add a bit to the block header to indicate whether the power-of-two optimization is being used for the corresponding block. For example, this bit can be set (or reset) to indicate that the power-of-two optimization is not being used if the compressor determines that the number of bits is not reduced. Although adding an additional bit reduces the compression rate for the algorithm, in some variations the decompressor needs fewer processing cycles to decompress the bitstream if the additional bit is present to indicate whether the power-of-two optimization is being used, which can reduce the number of clock cycles required by the decompressor.

<FIG> is a flow diagram of a method <NUM> for decoding delta values in a group that has a maximum delta value equal to a power-of-two according to some embodiments. The method <NUM> is implemented in some embodiments of the decompressor <NUM> shown in <FIG>. The decompressor uses the method <NUM> to decompress bitstreams that are compressed according to a corresponding compression algorithm, such as the compression algorithm illustrated in the method <NUM> of <FIG>.

At block <NUM>, the decompressor reads bits that are representative of a delta value for a pixel in a group of a block. The decompressor has previously determined the value of the quantity Bi using information included in the block header and the corresponding group header. Delta values in the group are encoded using Bi bits.

At decision block <NUM>, the decompressor determines whether the bit value indicated by the bits representative of the delta value is equal to a maximum encoded bit value of <NUM>^(Bi)-<NUM>. If not, the decompressor sets the delta value equal to the bit value at block <NUM>. If the decompressor determines that the bit value indicated by the bits representative of the delta value is equal to <NUM>^(Bi)-<NUM>, the method <NUM> flows to decision block <NUM>.

At decision block <NUM>, the decompressor reads in a trailing bit and determines whether the trailing bit is equal to <NUM> or <NUM>. If the trailing bit is equal to <NUM>, the decompressor determines that the delta value is equal to <NUM>^(Bi)-<NUM> at block <NUM>. If the trailing bit is equal to <NUM>, the decompressor determines that the delta value is equal to <NUM>^(Bi) at block <NUM>. The association of the trailing bits to the delta values is arbitrary and the opposite convention may also be used in some embodiments.

<FIG> is a flow diagram of a method <NUM> of determining whether to bypass features of a compression algorithm according to some embodiments. The method <NUM> is implemented in some embodiments of the compressor <NUM> shown in <FIG>. A corresponding decompression process is implemented in some embodiments of the decompressor <NUM> shown in <FIG> to decode the compressed bitstream that is generated according to the method <NUM>.

At block <NUM>, the compressor determines a number of bits that are saved by encoding delta values for the pixels in a block according to one or more optimizations of the compression algorithm implemented by the compressor. For example, the compressor can determine a first number of bits that are sufficient to encode the delta values according to some embodiments of the method <NUM> shown in <FIG>. The compressor can also determine a second number of bits that are sufficient to encode the delta values when additional optimization features are implemented, such as features implemented according to some embodiments of the method <NUM> shown in <FIG>, the method <NUM> shown in <FIG>, or the method <NUM> shown in <FIG>. The number of saved bits is equal to the difference between the first number and the second number.

At block <NUM>, the compressor determines a number of bits that are added to the block header or the group headers to support compression of the encoded delta values according to the one or more optimizations. For example, the compressor can determine a first number of bits that are needed to represent the values in the block header and the group headers to support encoding the delta values according to some embodiments of the method <NUM> shown in <FIG>. The compressor can also determine a second number of bits that are needed to represent the values in the block header and the group headers to support encoding the delta values when additional optimization features are implemented, such as features implemented according to some embodiments of the method <NUM> shown in <FIG>, the method <NUM> shown in <FIG>, or the method <NUM> shown in <FIG>. The number of added bits is equal to the difference between the first number and the second number.

At decision block <NUM>, the compressor determines whether the number of saved bits is greater than the number of added bits. If so, the compressor sets (at block <NUM>) a bypass bit in the block header to FALSE (or some other value) to indicate that the compressor is using the additional features to compress the encoded delta values. If the number of saved bits is less than the number of added bits, the method <NUM> flows to decision block <NUM>.

At decision block <NUM>, the compressor determines whether all of the delta values for the pixels in the block are equal to zero. If not, the compressor sets (at block <NUM>) the bypass bit in the block header to TRUE (or some other value) to indicate that the compressor is bypassing the use of the additional features to compress the encoded delta values. If all the delta values for the pixels in a block are equal to zero, the bypass bit may be dropped from the block header at block <NUM> to further reduce the bit count.

In some embodiments, the apparatus and techniques described above are implemented in a system comprising one or more integrated circuit (IC) devices (also referred to as integrated circuit packages or microchips), such as the processing system described above with reference to <FIG>. Electronic design automation (EDA) and computer aided design (CAD) software tools may be used in the design and fabrication of these IC devices. These design tools typically are represented as one or more software programs. The one or more software programs comprise code executable by a computer system to manipulate the computer system to operate on code representative of circuitry of one or more IC devices so as to perform at least a portion of a process to design or adapt a manufacturing system to fabricate the circuitry. This code can include instructions, data, or a combination of instructions and data. The software instructions representing a design tool or fabrication tool typically are stored in a computer readable storage medium accessible to the computing system. Likewise, the code representative of one or more phases of the design or fabrication of an IC device may be stored in and accessed from the same computer readable storage medium or a different computer readable storage medium.

A computer readable storage medium may include any non-transitory storage medium, or combination of non-transitory storage media, accessible by a computer system during use to provide instructions and/or data to the computer system.

Claim 1:
A method comprising:
determining delta values for a plurality of pixels in a block of pixels, each block comprising a portion of an image frame, wherein each delta value represents a difference between a color of one of the plurality of pixels and a reference color of a reference pixel selected from the plurality of pixels;
subdividing the plurality of pixels into a plurality of groups, each group having the same number of pixels, wherein a minimum number of bits is calculated for each group to represent the delta values for that group;
generating a compressed bitstream (<NUM>) representative of the delta values, wherein the compressed bitstream (<NUM>) comprises:
information identifying the reference color of the reference pixel;
bits representative of a block header that indicates a range of the minimum numbers of bits that are used to represent the delta values in the plurality of groups;
a plurality of group headers, each group header indicating a group minimum number of bits that is sufficient to represent all of the delta values in a corresponding one of the plurality of groups; and
the delta values encoded using the group minimum number of bits for the group that includes the delta values; and
transmitting the compressed bitstream (<NUM>), wherein determining the delta values for the plurality of pixels in the block comprises determining each of the delta values using a predetermined number of bits to represent a color difference and a sign of the delta value, and wherein a total number of bits in the compressed bitstream (<NUM>) is less than a sum, over the plurality of pixels, of the predetermined number of bits used to represent the delta values for the plurality of pixels.