deflateencoder.cpp

Jpeg编解码器的源代码

//
//  Description:
//
//    This function calculates the hash value from a location
//    in the input stream. We create the hash value by
//    extracting a fixed number of the low order bits from each
//    of the next three data values.
//
//  Parameters:
//    index: The index into the lookahead buffer
//
//  Return Value:
//    The hash value
//
inline unsigned int DeflateEncoder::hashValue (unsigned int index)
{
  unsigned int i1 = index & LOOKAHEADMASK ;
  unsigned int i2 = (index + 1) & LOOKAHEADMASK ;
  unsigned int i3 = (index + 2) & LOOKAHEADMASK ;

  unsigned int result = Hash (lookahead_buffer [i1],
                        lookahead_buffer [i2],
                        lookahead_buffer [i3]) ;
  return result ;
}


//
//  Description:
//
//    This function moves a hash entry corresponding to a position
//    in the LZ window to a specified hash chain.
//
//  Parameter:
//    entry: The Hash Entry (index into the LZ window)
//    hashvalue:  The new hashvalue for the entry.
//
inline void DeflateEncoder::moveHashEntry (unsigned int entry, unsigned int hashvalue)
{
  HashEntry *he = &hash_values [entry] ;
  if (he->previous != 0)
    he->previous->next = he->next ;
  if (he->next != 0)
    he->next->previous = he->previous ;

  he->next = hash_table [hashvalue].next ;
  he->previous = &hash_table [hashvalue] ;
  hash_table [hashvalue].next = he ;
  if (he->next != 0)
    he->next->previous = he ;

  return ;
}

//
//  Description:
//
//    This function finds the length encoding for
//    a length or distance table.
//
//  Parameters:
//    function: The function to process the code
//    lengths: lengths [n] = the length of the huffman code for n.
//    count: The number of code lengths
//
void DeflateEncoder::findLengthCodes (DeflateOutputStream &outputstream,
                                      LENGTHFUNCTION function,
                                      DeflateHuffmanEncoder &encoder, 
                                      unsigned int count)
{
  ASSERT (count <= DEFLATEMAXLENGTHCODES) ;

  unsigned int lengths [DEFLATEMAXLENGTHCODES] ;
BILLSELLSPOOP
  for (unsigned int ii = 0 ; ii < count ; ++ ii)
  {
    unsigned int code ; // Not used
    encoder.encode (ii, code, lengths [ii]) ;
  }
ENDBILLSELLSPOOP

BILLSELLSPOOP
  for (unsigned int ii = 0, jj ; ii < count ; ii = jj)
  {
    if (lengths [ii] != 0)
    {
      (this->*function) (outputstream, ii, lengths [ii], 0, 0) ;
      jj = ii + 1 ;
    }
    else
    {

      // Attempt to compact runs of zero length codes.
      // First find the number of consecutive zeros.
      for (jj = ii + 1;
           lengths [jj] == lengths [jj-1]
           && jj < count ;
           ++ jj)
      {
      }

      // We need at least 3 consecutive zeros to compact them.
      switch (jj - ii)
      {
      case 1:
        (this->*function) (outputstream, ii, lengths [ii], 0, 0) ;
        break ;
      case 2:
        (this->*function) (outputstream, ii, lengths [ii], 0, 0) ;
        (this->*function) (outputstream, ii + 1, lengths [ii], 0, 0) ;
        break ;
      default:
        {
          // We have at least three zeros.

          int kk = jj - ii ;
          if (kk > 138)
          {
            kk = 138 ;
            jj = ii + kk ;
          }
          if (kk > 10)
          {
            (this->*function) (outputstream, ii, 18, 7, kk - 11) ;
          }
          else
          {
            (this->*function) (outputstream, ii, 17, 3, kk - 3) ;
          }
        }
        break ;
      }
    }
  }
ENDBILLSELLSPOOP
  return ;
}

//
//  Description:
//
//    This function is passed as a parameter to FindLengthCodes.
//    It is use to find the frequency for each code.
//
//  Parameters:
//
//    code:  The code generated by FindLengthCodes
//
void DeflateEncoder::gatherLengthCounts (DeflateOutputStream &,
                                         unsigned int,
                                         unsigned int code,
                                         unsigned int,
                                         unsigned int)
{
  length_length_table.incrementFrequency (code) ;
  return ;
}

//
//  Description:
//
//    This function is passed as a parameter to FindLengthCodes.
//    It is use to encode and output the code to the output stream.
//
//  Parameters:
//
//    outputstream : The output stream for writing data to
//    code:  The code generated by FindLengthCodes
//    extra:  The number of extra bits of data for the code
//    value:  The extra value
//
void DeflateEncoder::outputLengthCounts (DeflateOutputStream &outputstream,
                                         unsigned int,   // Index - Not used here
                                         unsigned int code,
                                         unsigned int extra,
                                         unsigned int value)
{
  unsigned int huffmancode ;
  unsigned int huffmansize ;
  length_length_table.encode (code, huffmancode, huffmansize) ;

  outputstream.writeBits (huffmancode, huffmansize) ;
  if (extra != 0)
    outputstream.writeBits (value, extra) ;

  return ;
}


//
//  Description:
//
//    This function initializes the Hash Table.
//
//    This function needs to be called once at the start 
//    of the compression process.
//
void DeflateEncoder::initializeHashTable ()
{
  int ii ;
  memset (hash_values, 0, sizeof (HashEntry) * DEFLATEWINDOWSIZE) ;
  memset (hash_table, 0, sizeof (HashEntry) * (1 << (3 * HASHBITS))) ;

  for (ii = 0 ; ii < DEFLATEWINDOWSIZE ; ++ ii)
    hash_values [ii].index = ii ;

  // Initialize the hash table to allow initial zero runs. Here we are
  // setting up the hash table so that it appears that we have read
  // 258 zero values before the actual compression begins. This way
  // if the first 258 data bytes contains a run of zeros then we already
  // have a code to compress them with.
  hash_table [Hash (0, 0, 0)].next = &hash_values [DEFLATEWINDOWSIZE - 1] ;
  hash_values [DEFLATEWINDOWSIZE - 1].next = &hash_table [0] ;

  for (ii = DEFLATEWINDOWSIZE - 2 ;
       ii > DEFLATEWINDOWSIZE - DEFLATELONGESTLENGTH - 1 ;
       -- ii)
  {
    hash_values [ii + 1].next = &hash_values [ii]  ;
    hash_values [ii].previous = &hash_values [ii + 1] ;
  }
  return ;
}

//
//  Description:
//
//    This function writes a Deflate block header and Huffman table
//    descriptions to the output stream.
//
//  Parameters:
//
//    outputstream : The stream to write the header to
//    lastblock: true => This is the last block in the image
//               false => There are more blocks to come
//
void DeflateEncoder::outputDeflateHeader (DeflateOutputStream &outputstream,
                                          bool lastblock)
{
  length_table.incrementFrequency (DEFLATEENDCODE) ;
  length_table.buildTable (DEFLATEMAXLENGTHCODESIZE) ;
  distance_table.buildTable (DEFLATEMAXDISTANCECODESIZE) ;

  // Determine the count of length/literal and distances that
  // are used.
  unsigned int lengthcount ;
  for (lengthcount = DEFLATEMAXLENGTHCODES ;
       lengthcount > 0 ;
       -- lengthcount)
  {
    unsigned int code ;
    unsigned int size ;
    length_table.encode (lengthcount - 1, code, size) ;
    if (size != 0)
      break ;
  }

  unsigned int distancecount ;
  for (distancecount = DEFLATEMAXDISTANCECODES ;
       distancecount > 0 ;
       -- distancecount)
  {
    unsigned int code ;
    unsigned int size ;
    distance_table.encode (distancecount - 1, code, size) ;
    if (size != 0)
      break ;
  }

  // Gather the Huffman statistics for encoding the
  // lengths then create the Huffman table for doing so.
  length_length_table.reset () ;
  findLengthCodes (outputstream,
                   &DeflateEncoder::gatherLengthCounts,
                   length_table,
                   lengthcount) ;
  findLengthCodes (outputstream,
                   &DeflateEncoder::gatherLengthCounts,
                   distance_table,
                   distancecount) ;
  length_length_table.buildTable (DEFLATEMAXLENGTHLENGTHCODESIZE) ;

  // Count the number of lengths we have to output.
  unsigned int hclen ;
  for (hclen = DEFLATEMAXLENGTHLENGTHCODES ; hclen > 0 ; -- hclen)
  {
    unsigned int code ;
    unsigned int size ;
    length_length_table.encode (DEFLATELENGTHORDER [hclen-1], code, size) ;
    if (size != 0)
      break ;
  }

  // Write the Deflate header to the IDAT bock.
  if (lastblock)
    outputstream.writeBits (1, 1) ;
  else
    outputstream.writeBits (0, 1) ;

  outputstream.writeBits (2, 2) ; // Dynamic Huffman Codes
  outputstream.writeBits (lengthcount - 257, 5) ;
  outputstream.writeBits (distancecount - 1, 5) ;
  outputstream.writeBits (hclen - 4, 4) ;
  // Output the data for the Huffman table that encodes the Huffman tables
  for (unsigned int ii = 0 ; ii < hclen ; ++ ii)
  {
    unsigned int code ;
    unsigned int size ;
    length_length_table.encode (DEFLATELENGTHORDER [ii], code, size) ;
    outputstream.writeBits (size, 3) ;
  }
  // Huffman encode the lengths for the Length/Literal and Distance
  // Huffman tables.
  findLengthCodes (outputstream,
                   &DeflateEncoder::outputLengthCounts,
                   length_table,
                   lengthcount) ;
  findLengthCodes (outputstream,
                   &DeflateEncoder::outputLengthCounts,
                   distance_table,
                   distancecount) ;
  return ;
}

//
//  Description:
//
//    This function writes a ZLIB header to the output stream.
//
//  Parameters:
//
//    outputstream : The stream for writing the header to
//
void DeflateEncoder::outputZLibHeader (DeflateOutputStream &outputstream)
{
  UBYTE1 cmf = 0x78 ;  // 7=>32K Sliding Window, 8=> Deflate Compression
  UBYTE1 flg = compression_level << 6 ;

  UBYTE2 check = (cmf << 8) | flg ;
  flg |= 31 - (check % 31) ;
  outputstream.writeBits (cmf, 8) ;
  outputstream.writeBits (flg, 8) ;
  return ;
}

//
//  Description:
//
//    This function Huffman encodes and outputs the block buffer data.
//
//    The buffer is encoded so that
//
//      0..255  is a literal byte
//      256-514 is a length code of N-256
//
//    Each length code is followed by a distance code.
//
//  Parameters:
//
//    outputstream : The stream to write the compressed data to.
//
void DeflateEncoder::outputBlockData (DeflateOutputStream &outputstream)
{
  unsigned int huffmancode ;
  unsigned int huffmansize ;
  unsigned int code ;
  unsigned int extra ;
  unsigned int value ;
  unsigned int limit = block_buffer_count ;
  for (unsigned int ii = 0 ; ii < limit ; ++ ii)
  {
    if (block_buffer [ii] < 256)
    {
      length_table.encode (block_buffer [ii], huffmancode, huffmansize) ;
      outputstream.writeBits (huffmancode, huffmansize) ;
    }