Fast JPEG huffman encoding and decoding

Abstract

Huffman encoding, particularly from a packed data format, is simplified by using two different table formats depending on code length. Huffman tables are also reduced in size thereby. Decoding is performed in reduced time by testing for the length of valid Huffman codes in a compressed data stream and using an offset corresponding to a test criterion yielding a particular test result to provide a direct index into Huffman table symbol values while greatly reducing the size of look-up tables used for such a purpose.

1. A method of Huffman encoding symbols comprising steps of
 defining a seed value for the first occurrence of a code of a given length in a table,  
 storing a length of a code word,  
 storing said length and said code word in a first format when a number of bits of said number  length and said code word are less than or equal to a predetermined number of bits, and  
 storing an index to said seed value, an offset and said code word in a second format when said number  length and said image data  code word comprise a number of bits greater than said predetermined number of bits.  
 
     
     
       2. A method as recited in  claim 1 , wherein said symbols are JPEG R/S bytes. 
     
     
       3. A method recited in  claim 1  wherein said code words are  represents compressed image data. 
     
     
       4. A method as recited in  claim 3 , wherein said image compressed data is JPEG compressed image data. 
     
     
       5. A method of Huffman decoding compressed data including the steps of
 testing bits of a data stream with each of a plurality of test criteria to determine a length of a valid Huffman code,  
 combining one of a plurality of offsets corresponding to said length with said valid Huffman code to form an index, and  
 accessing a symbol value in a Huffman table using said index.  
 
     
     
       6. A method as recited in  claim 5 , including the further step of
 computing said test criteria and said plurality of offsets from Huffman table data.  
 
     
     
       7. A method recited in  claim 5  wherein said compressed  data are  stream is compressed image data. 
     
     
       8. A method as recited in  claim 7 , wherein said compressed image data is compressed JPEG image data.