Method and system for segment encoded graphic data compression

• US 5,748,904 A
• Filed: 09/13/1996
• Issued: 05/05/1998
• Est. Priority Date: 09/13/1996
• Status: Expired due to Fees

• Current Assignee: XGI Technology Inc.
• Original Assignee: Silicon Integrated Systems Corporation (Silicon Integrated Systems Corporation Taiwan)
• Inventors: Yao, Jo-Tan, Chen, Chung-Heng, Huang, Hung-Ju
• Primary Examiner(s): Ramirez, Ellis B.
• Application Number:
  US08/713,598
• Time in Patent Office: 599 Days
• Field of Search: 395/200.77, 395/114, 395/116, 395/508, 395/511, 395/519, 395/117, 395/480, 395/497.02, 395/497.04, 345/200, 345/201, 345/113, 345/202, 364/715.02
• US Class Current: 345/544
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: G09G 2340/02 Handling of images in compressed format, e.g. JPEG, MPEG
• CPC Class Codes: G09G 5/39 Control of the bit-mapped memory

Abstract

A method and system for compressing graphic data by dividing the data into segments is disclosed. The size of the divided segment is programmable. A frame buffer partitioned into a compressed frame buffer and an uncompressed frame buffer stores graphic data. Each segment of the graphic data is compressed by three different algorithms that encode the graphic data as a plurality of code-words. Each code-word for the segment is taken from the algorithm that can compress the largest number of pixels in the code-word. A header is used to indicate the number of code-words and the compression method used in each code-word. The total number of bytes obtained from the compression of a segment is compared to a pre-defined limit to determine if the compression of the segment is successful. The successfully compressed data of a segment are written to the compressed frame buffer. A compression status flag buffer is used to identify if a segment is compressed or not. A decompressor decompresses or passes the graphic data to a pixel stream for display according to the compress status flag.

Claims

1. A method of compressing graphic data in a graphic system having a frame buffer partitioned into an uncompressed frame buffer and a compressed frame buffer, comprising the steps of:

a. dividing said graphic data stored in said uncompressed frame buffer into a plurality of uncompressed segments each having a plurality of pixels;

b. preparing a compression status flag buffer having a plurality of status flags being set to zero, each of said status flags indicating the compression status of one of said uncompressed segments;

c. reading and compressing the plurality of pixels of an uncompressed segment pixel by pixel using a plurality of compression methods for forming a compressed segment including a header and a plurality of code-words for said uncompressed segment, said compressed segment being generated by the steps of;

d. formatting said header for the storage of a length code and a plurality of method codes;

e. reading pixels from said uncompressed segment and determining the number of pixels that can be encoded in a code-word for each of said compression methods;

f. selecting and saving the code-word of the compression method that encodes the largest number of pixels into said code-word;

g. identifying the selected compression method with a method code and recording said method code in said header orderly;

h. repeating steps d., e., f. and g. until all pixels of said uncompressed segment have been encoded;

i. and forming said compressed segment by counting the total number of all saved code-words, recording said total number in said length code and appending all saved code-words orderly to said header;

j. determining the total number of bytes in said compressed segment and comparing the total number of bytes with a pre-defined limit;

k. writing said compressed segment to said compressed frame buffer and setting the corresponding status flag to 1 if the total number in step j. is smaller than said limit;

l. and repeating steps c., j. and k. until all uncompressed segments have been processed;

wherein when said graphic data after compression are sent for display, the compression status of each segment is determined by its corresponding status flag, the compressed segment are decompressed if the corresponding status flag is set, and each code-word is decompressed by a decompression method corresponding to the compression method code stored in the header of the compressed segment.

2. A segment encoded graphic data compression system comprising:

a frame buffer being partitioned into a compressed frame buffer and an uncompressed frame buffer, said uncompressed frame buffer having uncompressed graphic data divided into a plurality of segments;

a VGA DRAM controller for controlling the access of data in said frame buffer;

an uncompress/decompress FIFO, said VGA DRAM controller reading an uncompressed data segment from said frame buffer to said FIFO for compression;

a compressor for compressing said uncompressed graphic data segment sent from said FIFO and encoding said uncompressed graphic data segment into a compressed data segment having a compressed data size;

a compressed data processor receiving said compressed data segment and said compressed data size from said compressor, said data processor writing said compressed data segment to said compressed frame buffer through said VGA DRAM controller and setting a corresponding flag in a compression flag buffer to one if said data size is smaller than a pre-defined limit;

a decompressor receiving a compressed or uncompressed data segment from said FIFO and converting the data segment into a pixel stream for display, said compression flag buffer sending a flag corresponding to the data segment to said FIFO to enable the decompression of the data segment if the corresponding flag is zero or pass the data segment through if the corresponding flag is one;

a RAMDAC receiving said pixel stream for display;

a plurality of color registers providing the storage of pixel colors for an uncompressed data segment, said compressor encoding pixel colors of the uncompressed data segment into color indices contained in the corresponding compressed data segment and said decompressor decoding said color indices into pixel colors for display, each of said color indices pointing to a pixel color stored in said color registers for improving the compression ratio of said compressor;

and a segment counter controlling said compression flag buffer and said VGA DRAM controller for coordinating the selection of a data segment and its corresponding flag for the operation of compression or decompression.

3. The segment encoded graphic data compression system according to claim 2, said compressor further comprising:

a plurality of encoders and corresponding local buffers, each of said encoder having a different compression algorithm and receiving pixel data of an uncompressed data segment from said FIFO and compressing the pixel data into a code-word and saving said code-word in its corresponding local buffer;

an algorithm select controller selecting the encoder that encodes the largest number of pixel data into its corresponding code-word;

and a multiplexer controlled by said algorithm select controller for passing the code-word of the selected encoder from its corresponding local buffer to a compress buffer;

wherein each uncompressed data segment is read from said frame buffer to said FIFO and compressed as a compressed data segment stored in said compress buffer, said compressed data segment including a code-word header recording the algorithm of the encoder selected for each code-word and the number of code-words, and all the code-words generated by the selected encoders.

4. The segment encoded graphic data compression system according to claim 3, said decompressor further comprising:

a FIFO-shift-load controller for loading a compressed or uncompressed data segment stored in said FIFO to an input buffer, said input buffer storing the code-word header of the data segment if the data segment is a compressed data segment;

a compressed data decoder controlled by the code-word header stored in said input buffer for decoding a compressed data segment read from said FIFO;

an uncompressed data decoder for passing an uncompressed data segment read from said FIFO;

and a decompression controller for controlling a multiplexer to pass either the ouput of said compressed data decoder or said uncompressed data decoder based on the data of the code-word header stored in said input buffer.