FIELD OF THE INVENTION

[0001] The invention relates to electronic computing and communication and, more particularly, to a method and apparatus for unpacking a variable number of data bits.

BACKGROUND

[0002] To transfer and store electronic computing data more efficiently, such data is often compressed into sizes smaller than their original sizes. Compressed data used in data transmission and storage typically includes variable-sized data units concatenated together. Fast conversion of this compressed data (e.g., unpacking of data bits) to an uncompressed, fixed-size data unit may be problematic, however.

[0003] For example, input data units may include 5 to 69 bits each, where the first 5 bits constitute a header which describes a format of a payload, and the next 0 bits to a maximum of 64 bits constitute the payload. Output data units may include unpacked, fixed-size data units of 64 bits each. Since variable- sized data units are concatenated together in the input data units, there is a sequential dependency between each of the input data units. That is, the first variable-sized data unit must be converted and size- determined before the second variable- sized data unit can be converted, the second variable-sized data unit must be converted and size-determined before the third variable-sized data unit can be converted, and so on.

[0004] In a particular example, three data units of 64 bits each, and of a total of 192 bits, in an uncompressed format, may include 27 bits in a compressed format and concatenated in the form of 5-bit, 11-bit, and 11-bit variable-sized data units, respectively. Uncompressing these three variable- sized data units with computing circuitry may be difficult since recognizing the bit boundaries of the variable-sized data units may require numerous, time-consuming tasks, e.g., first decoding the size of the first variable-sized data unit, then decoding the size of the second variable-sized data unit from the decoded size of the first variable-sized data unit, and so on.

Further, each data unit conversion may require several clock cycles, thereby requiring many clock cycles to unpack the compressed data and making it unsuitable for highspeed electronic computation and communication.

[0005] Accordingly, there exists a need in the art to overcome the deficiencies and limitations described hereinabove.

SUMMARY

[0006] In a first aspect of the invention, a structure includes an input port operable to receive one or more input data units including a plurality of packed bits of data, each of the one or more input data units including a header and a payload, the header including a predetermined number of bits and identifying a format of the payload and a length of the payload, and the payload including a variable number of bits. The structure further includes a circuit operable to identify and unpack the one or more input data units based on the header and the payload of each of the one or more input data units. The structure further includes an output port operable to transmit one or more output data units including the unpacked one or more input data units, once per clock cycle.

[0007] In another aspect of the invention, a structure for unpacking a variable number of data bits, includes an input port operable to receive one or more input data units including a plurality of packed bits of data, each of the one or more input data units including a header and a payload, the header including a predetermined number of bits and identifying a format of the payload and a length of the payload, and the payload including a variable number of bits. The structure further includes a first stage pipeline register operable to rotate the plurality of packed bits of the one or more input data units, and a second stage pipeline register operable to determine the length of the payload of each of the rotated one or more input data units based on the header of each of the rotated one or more input data units. The structure further includes a decode and decompress unit operable to unpack the one or more input data units based on the determined length of the payload of each of the one or more input data units, and an output port operable to transmit one or more output data units including the unpacked one or more input data units, once per clock cycle.

[0008] In yet another aspect of the invention, a method of unpacking a variable number of data bits, includes receiving one or more input data units including a plurality of packed bits of data, each of the one or more input data units including a header and a payload, the header including a predetermined number of bits and identifying a format of the payload and a length of the payload, and the payload including a variable number of bits. The method further includes identifying and unpacking the one or more input data units based on the header and the payload of each of the one or more input data units, and transmitting one or more output data units including the unpacked one or more input data units, once per clock cycle.

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS

[0009] The present invention is described in the detailed description which follows, in reference to the noted plurality of drawings by way of non-limiting examples of exemplary embodiments of the present invention.

[0010] FIG. 1 shows an exemplary pipelined compression and decompression circuit for unpacking a variable number of data bits in accordance with aspects of the present invention;

[0011] FIG. 2 shows another exemplary pipelined compression and decompression circuit for unpacking a variable number of data bits in accordance with aspects of the present invention; and

[0012] FIG. 3 shows an exemplary cycle-by-cycle diagram of a 192-bit buffer in FIG. 2 and contents in the 192-bit buffer in accordance with aspects of the present invention.

DETAILED DESCRIPTION

[0013] The invention relates to electronic computing and communication and, more particularly, to a method and apparatus for unpacking a variable number of data bits. In embodiments, the present invention includes pipelined compression and decompression circuits used in communication and storage of data. More

specifically, in aspects of the invention, the compression and decompression circuits unpack variable bits of compressed data in a pipelined fashion and to output one uncompressed data unit per clock cycle. Advantageously, by performing the various tasks for unpacking the variable bits of compressed data in parallel, the unpacking of the variable bits of compressed data occurs more efficiently and in every one clock cycle. [0014] FIG. 1 shows an exemplary pipelined compression and decompression circuit 10 for unpacking a variable number of data bits in accordance with aspects of the present invention. In embodiments, the compression and decompression circuit 10 includes an input port 15 and an output port 20, which are 64 bits wide, although other dimensions are contemplated by the invention. The compression and decompression circuit 10 further includes a plurality of registers, combinational logic, and state machines for decoding and decompressing compressed input data received through the input port 15 and initially stored in an input register 25. Input data units can be 5 to 69 bits long each (e.g., variable-sized), where the first 5 bits constitute a header which describes a format of a payload, and the next 0 bits to a maximum of 64 bits constitute the payload. Output data units may include unpacked, fixed-size data units of 64 bits each. The input data units may be further concatenated in an input bit stream with no gaps in between, and represented as C(0), C(l), ..., C(i-l), C(i), C(i+1), ..., C(last), where C(i) is the i-th variable-sized data unit. Since the input port 15 is 64 bits wide, a plurality of the input data units may arrive at the input port 15 in a same cycle, such as the input data units C(i+2) and C(i+3) stored in the input register 25. Since the input data units are not integral multiples of 64 bits, the input data units may arrive at the input port 15 at different clock cycles.

[0015] In embodiments, the compression and decompression circuit 10 can include a two-stage pipeline including a holding register 30 (e.g., a holding register A) and a register 35 (e.g., a register B), and a length lookahead unit 40 (e.g., a header size lookahead function), to enable pipelined operation. More specifically, the holding register 30 may be a circular queue or buffer of the input data units, and may be 132 bits wide, e.g., include bits A[0: 131]. A head register 45 (e.g., a head register A) includes a pointer which points to a first occupied bit location in the holding register 30. A tail register 50 (e.g., a tail register A) includes a pointer which points to a first free bit location or position in the holding register 30. When the head register 45 points to a same location or position as the tail register 50, the holding register 30 is empty. The pointer values of the head and tail registers 45 and 50 may be sent to other components of the compression and decompression circuit 10 as discussed herein. A clock 55 may control operation of the holding register 30, the head register 45, and the tail register 50 at a predetermined clock rate. For example, as shown in FIG. 1, the holding register 30 may include the input data units C(i-l), C(i), and C(i+1), the head register 45 may point to a first occupied bit location of the input data unit C(i-l), and the tail register 50 may point to a first free bit location after the input data unit C(i+1).

[0016] In accordance with further aspects of the invention, the holding register 30 can rotate input and output values to align the variable- sized input data units in desirable bit positions for subsequent use by subsequent pipeline stages. More specifically, in embodiments, a rotator function A.append(value, nbits) of the holding register 30 may append an input value (e.g., "value") into the holding register 30 starting from the position of the tail register 50 (e.g., "tail") until the position of the tail register 50 added by a number of bits (e.g., "nbits") of the input value (e.g., the input value is appended into bits A[tail:tail+nbits]). For example, a rotator function A.append(input C(i+2) and C(i+3), 64), where an input value includes the input data bits C(i+2) and C(i+3) and a number of bits is 64, may append the input data bits C(i+2) and C(i+3) into the holding register 30 starting from the position of the tail register 50 that is after the input data bit C(i+1) in the holding register 30. The rotator function of the holding register 30 may further update the position of the tail register 50 based on the following equation: tail = (tail + nbits) mod sizeof (A) (1), where tail is the position of the tail register 50, nbits is the number of bits of the input value, and sizeof(A) is a bit size of the register A or the holding register 30.

[0017] In embodiments, another rotator function A.peek(nbits) of the holding register 30 may read a number of bits (e.g., "nbits") as an output value from the holding register 30 starting from the position of the head register 45 until the position of the head register 45 added by the number of bits (e.g., the output value is read from bits A[head:head+nbits]). For example, a rotator function A.peek(74), where a number of bits read from the holding register 30 is 74, may read the input data bits C(i-l) and C(i) from the holding register 30 starting from the position of the head register 45 until the position of the head register 45 added by the number of bits. The rotator function A.peek(nbits) implies a rotator logic which rotates the output value down from the position of the head register 45 to zero or a first bit location in the register 35.

[0018] In accordance with further aspects of the invention, the register 35 can be 74 bits wide, e.g., include bits B[0:73], since a largest possible input data unit size is 69 bits for a payload plus a header of a first input data unit plus 5 bits for a header of a second input data unit. The register 35 may receive the output value (e.g., of the function A.peek(nbits)) from the holding register 30, and align the output value in the register 35 starting from the first bit location. For example, the register 35 may receive the input data bits C(i-l) and C(i) from the holding register 30, and align the input data bits C(i-l) and C(i) starting from the first bit location in the register 35. A function B.current_chunk_len() operates on the register 35 (e.g., the register B) and may determine a length of a current input data unit, including a header of the current input data unit, in the register 35 based on the header (e.g., first 5 bits) of the current input data unit. For example, the function B.current_chunk_len() may determine a length of the input data unit C(i-l) in the register 35, including a header of the input data unit C(i-l), e.g. first 5 bits of C(i-l). That is, the function B.current_chunk_len() is used to find a boundary between the current input data unit (e.g., the input data unit C(i-l)) and a next input data unit (e.g., the input data unit C(i)) in the register 35.

[0019] In embodiments, the pipelined compression and decompression circuit 10 can further include a valid bits determination unit 60, a head delay unit 65, a tail delay unit 70, a valid bits delay unit 75, and a comparator 80. The valid bits determination unit 60 may receive the positions of the head register 45 and the tail register 50, and based on these positions, a function A.validbits() of the valid bits determination unit 60 may determine a number of occupied bits (e.g. valid bits) in the holding register 30. The determination of the number of valid bits "validbits" in the holding register 30 may be based on the following equation: validbits = tail - head(modl 32) (2).

[0020] In accordance with further aspects of the invention, the number of valid bits is determined so that the pipelined compression and decompression circuit 10 can determine whether the decompression operation is complete (e.g., whether the holding register 30 is empty), and thus, whether the length lookahead unit 40 should further perform its functions as described herein. The head delay unit 65, the tail delay unit 70, and the valid bits delay unit 75 can receive and delay by one clock cycle the position of the head register 45, the position of the tail register 50, and the number of valid bits in the holding register 30, respectively. The delayed position of the head register 45, the delayed position of the tail register 50, and the delayed number of valid bits in the holding register 30 may be represented as "dlyHead", "dlyTail", and "dlyVbits", respectively. The clock 55 may control operation of the register 35, the head delay unit 65, the tail delay unit 70, and the valid bits delay unit 75 at a predetermined clock rate.

[0021] In embodiments, the comparator 80 may receive the delayed positions of the head register 45 and the tail register 50 from the head delay unit 65 and the tail delay unit 70, respectively. The comparator 80 may determine whether the delayed positions of the head register 45 and the tail register 50 are equal to each other, which indicates whether the holding register 30 is empty. When the delayed positions of the head register 45 and the tail register 50 are not equal to each other (e.g., the holding register 30 is not empty), the comparator 80 sends an asserted valid signal to a decode and decompress unit 85. Otherwise, the comparator 80 sends a non-asserted valid signal to the decode and decompress unit 85.

[0022] In embodiments, based on the determined length of the current input data unit, the register 35 can send the header of the current input data unit and a payload (e.g., a remaining portion or body) of the current input data unit to the decode and decompress unit 85. When the decode and decompress unit 85 receives the asserted valid signal from the comparator 80, the decode and decompress unit 85 may convert the variable-sized, compressed current input data unit into a fixed-size, uncompressed output data unit of 64 bits which is outputted by the output port 20. For example, based on the determined length of the input data unit C(i-l), the register 35 may send the header of the input data unit C(i-l) and a data unit of the input data unit to the decode and decompress unit 85 which may convert the input data unit C(i-l) for output. When the decode and decompress unit 85 receives the non-asserted valid signal from the comparator 80, the decode and decompress unit 85 does nothing.

[0023] In accordance with further aspects of the invention, the length lookahead unit 40 is a combinatorial logic of 74 inputs that can receive the current input data unit (e.g., the input data unit C(i-l)) and the next input data unit (e.g., the input data unit C(i)) from the register 35. The length lookahead unit 40 may further receive the delayed valid bits (e.g., occupied bits) in the holding register 30 from the valid bits delay unit 75. When the delayed valid bits is greater than or equal to the length of the current input data unit (including the header of the current input data unit) determined based on the header of the current input data unit, the length lookahead unit 40 (e.g., via a lookaheadChunkLength(B) function) may use the length of the current input data unit to find a header of the next input data unit, and use the header of the next input data unit to determine the length of the next input data unit. When the delayed valid bits are not greater than or equal to the length of the current input data unit, the length lookahead unit 40 may determine the length of the next input data unit to be zero.

[0024] In embodiments, the length lookahead unit 40 may send the length of the next input data unit to an adder 90 which in a next clock cycle, may receive the position of the head register 45 and add the position of the head register 45 to the length of the next input data unit. The adder 90 may set this sum value as a new position of the head register 45, to point to a first occupied bit location of a next input data unit (e.g., the input data unit C(i+1)) in the holding register 30. The incrementing of the position of the head register 45 may be determined based on the following equation: head = head + L(modl32) (3), where L is the length of the next input data unit.

[0025] In accordance with further aspects of the invention, in the same next clock cycle, an adder 95 can receive and increment the position of the tail register 50 by 64 bits. The adder 95 may set this incremented value as a new position of the tail register 50, to point to a first free bit location in the holding register 30, e.g., after the input data unit C(i+3) which is to be appended into the holding register 30. The adders 90 and 95 are used to increment the positions of the head register 45 and the tail register 50, respectively, to boundaries of the input data units such that they are subsequently sent to the decode and decompress unit 85 in a proper order.

[0026] In embodiments, each of the functions of the registers 30 and 35, the decode and decompress unit 85, the length lookahead unit 40, the adder 90, and the head register 45 can be performed in parallel and in the same clock cycle, e.g., as represented in pseudocode as "DO IN PARALLEL". Advantageously, a 64-bit, decompressed output data unit is efficiently produced every cycle, instead of after multiple cycles.

[0027] In accordance with further aspects of the invention, the functions of the components in the pipelined compression and decompression circuit 10 may be represented by the following exemplary pseudocode:

DO IN PARALLEL

A.append(input,64) on clock edge // rotate input up to tail;

tail^tail+64(modl32) nextB A.peek(74) // rotate down from head B nextB on clock edge if( dlyHead != dlyTail AND dlyVbits >= B.current_chunk_length() )

Output decompress(B[0..])

else

Output invalid // don't care if( Head != Tail AND dlyVbits >= B.current_chunk_length()) // current means C(i-l)

L lookaheadChunkLength(B)

else

L ^ O

nextHead head+L (mod 132) head nextHead on clock edge

END

[0028] FIG. 2 shows another exemplary pipelined compression and decompression circuit 200 for unpacking a variable number of data bits in accordance with aspects of the present invention. In embodiments, the compression and decompression circuit 200 includes a 64-bit input port 205 and a 74-bit output port 210, although other dimensions are contemplated by the invention. The compression and decompression circuit 200 further includes a plurality of registers, combinational logic, and state machines for decoding and decompressing compressed input data received through the input port 205. Input data units can be 5 to 69 bits long each (e.g., variable-sized), where the first 5 most significant bits constitute a header which describes a format of a payload, and the next 0 bits to a maximum of 64 bits constitute the payload. The input data units may be further concatenated in an input bit stream with no gaps in between. Output data units may include unpacked, fixed-size data units of 74 bits each, which include a 5-bit header of a current payload, the 64-bit payload, and a 5-bit header of a next payload. [0029] In embodiments, the compression and decompression circuit 200 can further include a 192-bit buffer 215, a 0-to-63-bit left shifter 220, a selectable 64-bit or 128- bit left preshifter 225, a read pointer register 230, a length decoder 235, a next read pointer adder 240, a buffer controller 245, a 64-bit multiplexer 250, a 64-bit multiplexer 255, and a decode and decompress unit 260. The 192-bit buffer 215 may receive a 64-bit input data unit from the input port 205, and store the input data unit into any of three 64-bit sections (e.g., including bits [0:63], bits [64:127], and bits [128: 191], respectively) of the 192-bit buffer 215. Data valid bits (e.g., Valid(O), Valid(l), and Valid(2)) are associated with each of the respective 64-bit sections of the 192-bit buffer 215. The read pointer register 230 may include a read pointer which indicates or points to a starting point or bit location of the input data unit in the 192-bit buffer 215, namely, within the first 64-bit section, the bits [0:63], of the 192- bit buffer 215. The 192-bit buffer 215 may send the data in the 192-bit buffer 215 (e.g., including the input data unit) to both the left shifter 220 and the left preshifter 225.

[0030] In accordance with further aspects of the invention, the O-to-63 bit left shifter 220 can left shift the received data of the 192-bit buffer 215 by O-to-63 bits based on the read pointer of the read pointer register 230. For example, the left shifter 220 may left shift the bit pointed by the read pointer by O-to-63 bits such that the bit is at a first bit location (e.g., is the most significant bit) in the left shifter 220. All bits following the bit pointed by the read pointer may also be shifted left by O-to-63 bits. The left shifter 220 may send a header (e.g., first 5 most significant bits) of the shifted input data unit to a length decoder 235 which may determine a length of the input data unit in the 192-bit buffer 215. The length decoder 235 may send the 7-bit length of the input data unit to the adder 240.

[0031] In embodiments, the adder 240 can receive the length of the input data unit in the 192-bit buffer 215 from the length decoder 235, and the 6-bit starting point of the input data unit in the 192-bit buffer 215 (e.g., the read pointer) from the read pointer register 230. The adder 240 may add the length of the input data unit to the starting point of the input data unit to determine an 8-bit next starting point or bit location of a next input data unit in the 192-bit buffer 215 (e.g., a next read pointer). The adder 240 may send the next read pointer to the buffer controller 245. The adder 240 may further send 6 lower order bits of the next read pointer to the read pointer register 230 which may set the current read pointer to the next read pointer when the buffer controller 245 determines the next input data unit is valid, e.g., entirely within one of the three 64-bit sections of the 192-bit buffer 215.

[0032] In accordance with further aspects of the invention, the buffer controller 245 can control operation of the 192-bit buffer 215, the 64-bit or 128-bit left preshifter 225, the 64-bit multiplexer 250, and the 64-bit multiplexer 255 at a predetermined clock rate. More specifically, the 64-bit or 128-bit left preshifter 225 may receive the data in the 192-bit buffer 215. Based on the next read pointer received from the adder 240, the buffer controller 245 may instruct the left preshifter 225 to left shift the received data from the 192-bit buffer 215 by 64 bits or 128 bits. For example, the left preshifter 225 may left shift the received data from the 192-bit buffer 215 by 64 bits or 128 bits such that a first bit location of the next input data is contained within bits [0:63] of the left preshifter 225.

[0033] In embodiments, when the next read pointer is pointing at a bit location that is greater than a 127 bit in the 192-bit buffer 215 (e.g., the next input data starts in the third 64-bit section, the bits [128:191], of the 192-bit buffer that includes the least significant bit "lsb"), the 64-bit or 128-bit left preshifter 225 can left shift the data from the 192-bit buffer 215 by 128 bits. When the next read pointer is pointing at a bit location that is less than a 128 ^th bit but greater than a 63 ^rd bit, in the 192-bit buffer 215 (e.g., the next input data starts in the second 64-bit section, the bits [64:127], of the 192-bit buffer), the left preshifter 225 may left shift the data from the 192-bit buffer 215 by 64 bits. When the next read pointer is pointing at a bit location that is less than a 64 ^th bit in the 192-bit buffer 215 (e.g., the next input data starts in the first section, the bits [0:63], of the 192-bit buffer), the left preshifter 225 does not left shift the data from the 192-bit buffer 215. These functions or actions of the left preshifter 225 may be summarized by the following table:

TABLE 1

Next Read Pointer (NRP) Action

127 ^th Bit < NRP Shift Left 128 Bits

63 ^rd Bit < NRP < 128 ^th Bit Shift Left 64 Bits

NRP < 64 ^th Bit No Shift Left

[0034] In accordance with further aspects of the invention, the 64-bit or 128-bit left preshifter 225 can send a first 64 or least significant bits (e.g., bits [64:127]) of the shifted or non-shifted data in the left preshifter 225 to the 64-bit multiplexer 255. The left preshifter 225 may send a second 64 or most significant bits (e.g., bits [0:63]) of the shifted or non-shifted data in the left preshifter 225 to the 64-bit multiplexer 250. The 64-bit multiplexer 255 and the 64-bit multiplexer 250 may further receive the input data unit from the input port 205. Based on the buffer valid bits and the value of the next read pointer, the buffer controller 245 may instruct the 64-bit multiplexers 255 and 250 to output the shifted data from the preshifter 225 or the input data unit from the input port 205, to the 192-bit buffer 215, as discussed herein.

[0035] FIG. 3 shows an exemplary cycle-by-cycle diagram of the 192-bit buffer 215 in FIG. 2 and contents in the 192-bit buffer 215 in accordance with aspects of the present invention. In each cycle, a read pointer (in the read pointer register 230 in FIG. 2) indicates or points to a starting point or bit location of a next, variable-length input data unit in the 192-bit buffer 215, e.g., where a header of the next input data unit begins. C(i) is a first input data unit in a data stream, followed by an input data unit C(i+1), and so on.

[0036] In cycle 1, at the beginning of the sequence, the 192-bit buffer 215 is empty. This is indicated by all three valid bits (e.g., Valid(O), Valid(l), and Valid(2)) of the 192-bit buffer 215 being cleared. The valid bits Valid(O), Valid(l), and Valid(2) indicates whether a first section (e.g., bits [0:63]), a second section (e.g., bits

[64:127]), and a third section (e.g., bits [128:191]), respectively, of the 192-bit buffer 215 includes bits of data. Input data (e.g., the first input data unit C(i)) is written into the 192-bit buffer 215 at the bits [0:63], and the first valid bit Valid(O) is set.

[0037] In cycle 2, the bits [0:63] of the 192-bit buffer 215 have valid data, namely, the first input data unit C(i). The 0-63-bit left shifter 220 in FIG. 2 performs a shift equal to the read pointer value of zero. The length decoder 235 in FIG. 2 determines a length of the first input data unit C(i). The adder 240 in FIG. 2 determines a next read pointer which the buffer controller 245 uses to determine that the first input data unit C(i) is entirely contained within a valid 64-bit section (e.g., the bits [0:63]) of the 192-bit buffer 215. The output of the 0-63-bit left shifter 220 is passed to the decode and decompress unit 260, and the read pointer may advance to the next read pointer. No preshifting occurs since the next read pointer is at a bit location less than a 64th bit in the 192-bit buffer 215. Input data (e.g., the input data unit C(i+1)) is written into 192-bit buffer 215 at the bits [64:127] and the second valid bit Valid(l) is set.

[0038] In cycle 3, the bits [0:127] of the 192-bit buffer 215 have valid data. In a fashion identical to cycle 2, the next read pointer is calculated, the buffer controller 245 determines that the input data unit C(i+1) is entirely within valid 64-bit sections (e.g., the bits [0:127]), and the read pointer may advance to the next read pointer. Since next read pointer is at a bit location less than a 128 ^th bit but greater than a 63 ^rd bit in the 192-bit buffer 215, the buffer controller 245 instructs the 64 or 128-bit left preshifter 225 and the multiplexer 250 to perform a 64-bit preshift operation. More specifically, the bits [64:127] in the 192-bit buffer 215 are moved to the bits [0:63], and the valid bit Valid(l) is moved to the valid bit Valid(O). Input data (e.g., an input data unit C(i+2)) is written into the empty bits [64:127] in the 192-bit buffer 215, and the valid bit Valid(l) is set.

[0039] In cycle 4, the bits [0:127] in the 192-bit buffer 215 have valid data. The next read pointer is calculated, and the buffer controller 245 determines that input data unit C(i+2) is not entirely valid, e.g., within valid 64-bit sections (e.g., the bits [0: 127]) of the 192-bit buffer 215. The read pointer cannot be updated and the output of the 0- 63-bit left shifter 220 cannot be used yet. Input data (e.g., an input data unit C(i+3)) is written to the bits [128:191] of the 192-bit buffer 215, and the valid bit Valid(2) is set. [0040] In cycle 5, all of the bits [0:191] of the 192-bit buffer 215 have valid data. The next read pointer is calculated, the buffer controller 245 determines that the input data unit C(i+2) is entirely valid within valid 64-bit sections (e.g., the bits [0:191]), and the read pointer can be advanced to the next read pointer. Since next read pointer is at a bit location greater than a 127 ^th bit in the 192-bit buffer 215, the buffer controller 245 instructs the 64 or 128 -bit left preshifter 225 and the multiplexer 250 to perform a 128-bit preshift operation. More specifically, the bits [128:191] in the 192- bit buffer 215 are moved to the bits [0:63], leaving only the valid bit Valid(O) set. Input data (e.g., an input data unit C(i+4)) is written to the empty bits [64:127] of the 192-bit buffer 215, and the valid bit Valid(l) is set.

[0041] In cycle 6, the bits [0:127] in the 192-bit buffer 215 have valid data. The next read pointer is calculated, the buffer controller 245 determines that chunk C(i+3) is entirely valid within the valid bit section (e.g., the bits [0:63]), and the read pointer can be advanced to the next read pointer. No preshift is performed since the next read pointer is at a bit location less than the 64 ^th bit in the 192-bit buffer 215. Input data (e.g., an input data unit C(i+5)) is written to the bits [128:191] in the 192-bit buffer 215, and the valid bit Valid(2) is set.

[0042] Referring back to FIG. 2, in embodiments, the decode and decompress unit 260 can receive and convert the variable-sized, compressed input data unit from the 0- to-63 bit left shifter 220 into a fixed-size, uncompressed output data unit of 64 bits which is outputted by the output port 210. Each of the components of the

compression and decompression circuit 200 can perform its function(s) in parallel and in the same clock cycle. Advantageously, a 64-bit, decompressed output data unit is efficiently produced every cycle, instead of after multiple cycles. [0043] The method as described above is used in the fabrication of integrated circuit chips. The resulting integrated circuit chips can be distributed by the fabricator in raw wafer form (that is, as a single wafer that has multiple unpackaged chips), as a bare die, or in a packaged form. In the latter case the chip is mounted in a single chip package (such as a plastic carrier, with leads that are affixed to a motherboard or other higher level carrier) or in a multichip package (such as a ceramic carrier that has either or both surface interconnections or buried interconnections). In any case the chip is then integrated with other chips, discrete circuit elements, and/or other signal processing devices as part of either (a) an intermediate product, such as a

motherboard, or (b) an end product. The end product can be any product that includes integrated circuit chips, ranging from toys and other low-end applications to advanced computer products having a display, a keyboard or other input device, and a central processor.

[0044] The descriptions of the various embodiments of the present invention have been presented for purposes of illustration, but are not intended to be exhaustive or limited to the embodiments disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the described embodiments. The terminology used herein was chosen to best explain the principles of the embodiments, the practical application or technical improvement over technologies found in the marketplace, or to enable others of ordinary skill in the art to understand the embodiments disclosed herein.