Method and apparatus for compressing and decompressing data

• US 7,728,742 B2
• Filed: 06/30/2009
• Issued: 06/01/2010
• Est. Priority Date: 09/30/2008
• Status: Expired due to Fees

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Gonion, Jeffry E.
• Primary Examiner(s): JEAN PIERRE, PEGUY
• Application Number:
  US12/495,568
• Publication Number:
  US 20100079313A1
• Time in Patent Office: 336 Days
• Field of Search: 341/50, 341/51, 341/55, 341/67, 341/65, 341/60, 370/389, 370/413
• US Class Current: 341/60
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Abstract

The described embodiments include a system for performing data compression. The system includes a compression mechanism with N channels, and an internal decompression mechanism in the compression mechanism that accepts N channels of fixed-length packets. The compression mechanism is configured to receive an input bit stream that includes a set of data words. In response to receiving a request from the internal decompression mechanism identifying at least one of the channels for which a fixed-length packet is to be appended to the output stream, the system fills a fixed-length packet for the identified channel with compressed data words; appends the fixed-length packet to the output stream; and forwards a copy of the fixed-length packet to the internal decompression mechanism. The internal decompression mechanism decompresses fixed-length packets for each of the channels to determine a next fixed-length packet to be appended to the output stream.

Claims

1. An apparatus for performing data compression, comprising:

a compression mechanism including N channels; and

an internal decompression mechanism in the compression mechanism,

wherein the internal decompression mechanism accepts N channels of fixed-length packets;

wherein the compression mechanism is configured to;

receive an input bit stream including a set of data words; and

in response to receiving a request from the internal decompression mechanism identifying at least one of the channels for which a fixed-length packet is to be appended to the output stream;

fill a fixed-length packet for the identified channel with compressed data words;

append the fixed-length packet to the output stream; and

forward a copy of the fixed-length packet to the internal decompression mechanism.

2. The apparatus of claim 1, wherein when filling the fixed-length packet with compressed data words, until the fixed-length packet is full, the compression mechanism is configured to iteratively:

retrieve data words from the input bit stream;

compress each of the retrieved data words into a variable-length word; and

append the variable-length words in a round-robin pattern into a fixed-length packet for each of the channels.

3. The apparatus of claim 2, wherein when appending the variable-length words in the round-robin pattern into a fixed-length packet for each channel, the compression mechanism is configured to:

store the variable-length words in a fixed-length packet for each channel until a fixed-length packet for the channel is full, then store subsequent variable-length words into a buffer associated with the channel.

4. The apparatus of claim 3, wherein when filling a fixed-length packet for a channel, if variable-length words are available in the buffer associated with the channel, the compression mechanism is configured so that:

if sufficient variable-length words are available in the buffer to fill a fixed-length packet for the channel, the compression mechanism fills the fixed-length packet with the available variable-length words from the buffer, appends the full fixed-length packet to an output stream of fixed-length packets, and forwards a copy of the filled fixed-length packet to the internal decompression mechanism;

otherwise, the compression mechanism uses the variable-length words in the buffer to partially fill the fixed-length packet, and then performs the retrieving, compressing, and storing operations to fill a remainder of the fixed-length packet.

5. The apparatus of claim 1, wherein the internal decompression mechanism is configured to:

receive the fixed-length packet for the identified channel from the compression mechanism; and

in a round-robin pattern, for each channel,

retrieve a variable-length word from a fixed-length packet;

decompress the variable-length word; and

upon determining that there is insufficient data in a fixed-length packet to enable decompressing variable-length words for the channel, send a request to the compression mechanism to cause the compression mechanism to output a fixed-length packet for the channel.

6. The apparatus of claim 1, wherein upon starting compressing a new input bit stream, the internal decompression mechanism is further configured to send requests to the compression mechanism indicating that a fixed-length packet is needed to continue decompression for each of the channels.

7. The apparatus of claim 1, wherein the compression mechanism is further configured to store the output stream in a computer-readable storage device or output the output stream to a network;

wherein a separate remote decompression mechanism subsequently retrieves the output stream from the computer-readable storage device or receives the output stream from the network and decompresses the output stream to recreate the input bit stream.

8. A computer system for performing data compression, comprising:

a processor;

a memory coupled to the processor, wherein the memory stores instructions and data for the processor;

a compression mechanism in the processor, wherein the compression mechanism includes N channels; and

an internal decompression mechanism in the compression mechanism, wherein the internal decompression mechanism accepts N channels of fixed-length packets;

wherein the compression mechanism is configured to;

receive an input bit stream including a set of data words; and

in response to receiving a request from the internal decompression mechanism identifying at least one of the channels for which a fixed-length packet is to be appended to the output stream;

fill a fixed-length packet for the identified channel with compressed data words;

append the fixed-length packet to the output stream; and

forward a copy of the fixed-length packet to the internal decompression mechanism.

9. The computer system of claim 8, wherein when filling the fixed-length packet with compressed data words, until the fixed-length packet is full, the compression mechanism is configured to iteratively:

retrieve data words from the input bit stream;

compress each of the retrieved data words into a variable-length word; and

append the variable-length words in a round-robin pattern into a fixed-length packet for each of the channels.

10. The computer system of claim 9, wherein when appending the variable-length words in the round-robin pattern into a fixed-length packet for each channel, the compression mechanism is configured to:

store the variable-length words in a fixed-length packet for each channel until a fixed-length packet for the channel is full, then store subsequent variable-length words into a buffer associated with the channel.

11. The computer system of claim 10, wherein when filling a fixed-length packet for a channel, if variable-length words are available in the buffer associated with the channel, the compression mechanism is configured so that:

if sufficient variable-length words are available in the buffer to fill a fixed-length packet for the channel, the compression mechanism fills the fixed-length packet with the available variable-length words from the buffer, appends the full fixed-length packet to an output stream of fixed-length packets, and forwards a copy of the filled fixed-length packet to the internal decompression mechanism;

otherwise, the compression mechanism uses the variable-length words in the buffer to partially fill the fixed-length packet, and then performs the retrieving, compressing, and storing operations to fill a remainder of the fixed-length packet.

12. The computer system of claim 8, wherein the internal decompression mechanism is configured to:

receive the fixed-length packet for the identified channel from the compression mechanism; and

in a round-robin pattern, for each channel,

retrieve a variable-length word from a fixed-length packet;

decompress the variable-length word; and

upon determining that there is insufficient data in a fixed-length packet to enable decompressing variable-length words for the channel, send a request to the compression mechanism to cause the compression mechanism to output a fixed-length packet for the channel.

13. The computer system of claim 8, wherein upon starting compressing a new input bit stream, the internal decompression mechanism is further configured to send requests to the compression mechanism indicating that a fixed-length packet is needed to continue decompression for each of the channels.

14. The computer system of claim 8, wherein the compression mechanism is further configured to store the output stream in a computer-readable storage device or output the output stream to a network;

wherein a separate remote decompression mechanism subsequently retrieves the output stream from the computer-readable storage device or receives the output stream from the network and decompresses the output stream to recreate the input bit stream.

15. A method for performing data compression in a system with a compression mechanism with N channels that includes an internal decompression mechanism, wherein the internal decompression mechanism accepts N channels of fixed-length packets, comprising:

receiving an input bit stream that includes a set of data words; and

in response to receiving a request from the internal decompression mechanism identifying at least one of the channels for which a fixed-length packet is needed to be appended to the output stream;

filling a fixed-length packet for the identified channel with compressed data words;

appending the fixed-length packet to the output stream; and

forwarding a copy of the fixed-length packet to the internal decompression mechanism.

16. The method of claim 15, wherein filling the fixed-length packet for the identified channel involves:

retrieving data words from the input bit stream;

compressing each of the retrieved data words into a variable-length word; and

appending the variable-length words in a round-robin pattern into a fixed-length packet for each of the channels,

until the fixed-length packet is full.

17. The method of claim 16, wherein appending the variable-length words in the round-robin pattern into a fixed-length packet for each channel involves storing the variable-length words in a fixed-length packet for each channel until a fixed-length packet for the channel is full, then storing subsequent variable-length words into a buffer associated with the channel.

18. The method of claim 17, wherein if variable-length words are available in the buffer associated with the channel, filling a fixed-length packet for a channel involves:

if sufficient variable-length words are available in the buffer to fill a fixed-length packet for the channel, filling the fixed-length packet with the available variable-length words from the buffer, appending the full fixed-length packet to an output stream of fixed-length packets, and forwarding a copy of the filled fixed-length packet to the internal decompression mechanism;

otherwise, using the variable-length words in the buffer to partially fill the fixed-length packet, and then performing the retrieving, compressing, and storing operations to fill a remainder of the fixed-length packet.

19. The method of claim 15, wherein the method further comprises:

receiving the fixed-length packet for the identified channel at the internal decompression mechanism; and

in the internal decompression mechanism, for each channel in a round-robin pattern, for each channel

retrieving a variable-length word from a fixed-length packet;

decompressing the variable-length word; and

upon determining that there is insufficient data in a fixed-length packet to enable decompressing variable-length words for the channel, sending a request for a next fixed-length packet for the channel.

20. The method of claim 15, wherein upon starting compressing a new input bit stream, the method further comprises sending requests from the internal decompression mechanism identifying that a fixed-length packet is needed for each of the channels to continue decompression.

21. The method of claim 15, wherein the method further comprises:

storing the output stream in a computer-readable storage device or outputting the output stream to a network;

at a separate remote decompression mechanism, subsequently retrieving the output stream from the computer-readable storage device or receiving the output stream from the network; and

using the separate remote decompression mechanism to decompress the output stream to recreate the input bit stream.