deflateencoder.cpp

Jpeg编解码器的源代码

    else
    {
      unsigned int length = block_buffer [ii] - 256 ;
      ++ ii ;
      unsigned int distance = block_buffer [ii] ;
      LengthToCode (length, code, extra, value) ;
      length_table.encode (code, huffmancode, huffmansize) ;

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

      DistanceToCode (distance, code, extra, value) ;
      distance_table.encode (code, huffmancode, huffmansize) ;

      outputstream.writeBits (huffmancode, huffmansize) ;
      if (extra != 0)
        outputstream.writeBits (value, extra) ;
    }
  }
  length_table.encode (DEFLATEENDCODE, huffmancode, huffmansize) ;
  outputstream.writeBits (huffmancode, huffmansize) ;
  block_buffer_count = 0 ;
  prepareNewBlock () ;
  return ;
}

//
//  Description:
//
//    This function finds the longest match of the lookahead buffer 
//    in the LZ Window.
//
//  Parameters:
//
//    count : The number of characters in the lookahead buffer.
//    bestlength : The longest match
//    bestoffset : The offset of the longest match
//
void DeflateEncoder::longestMatch (unsigned int count, 
                                   unsigned int &bestlength,
                                   unsigned int &bestoffset)
{
  bestlength = 0 ;

  unsigned int hashvalue = hashValue (lookahead_output_position) ;
  if (hash_table [hashvalue].next == 0)
    return ;


  // count and DEFLATELONGESTLENGTH are the limits for the longest match. 
  unsigned int chain ;
  unsigned int matchlimit = (count < DEFLATELONGESTLENGTH ? count : DEFLATELONGESTLENGTH) ;
  HashEntry *current ;
  for (chain = 0 , current = hash_table [hashvalue].next ;
       current != 0 && chain < search_limit ;
       current = current->next, ++ chain)
  {
    unsigned int src = lookahead_output_position ;
    unsigned int dest = current->index ;
    unsigned int len  ;

#if 0
    unsigned int limit = WindowOffsetToPosition (lz_position, current->index) ;
#else
    unsigned int limit = DEFLATEWINDOWSIZE
                - ((DEFLATEWINDOWSIZE + current->index - lz_position)
                    & DEFLATEWINDOWMASK) ;
#endif
    if (limit > matchlimit)
      limit = matchlimit ;

    for (len = 0 ; 
         len < limit ; 
         ++ len, AdvanceWindowPosition (dest), AdvanceLookaheadPosition (src))
    {
      unsigned int lookahead = lookahead_buffer [src] ;
      unsigned int window = lz_window [dest] ;
      if (lookahead != window)
        break ;
    }

    // We only care about matches longer than 3
    if (len >= 3 && len > bestlength)
    {
      bestlength = len ;
      bestoffset = DEFLATEWINDOWSIZE
                - ((DEFLATEWINDOWSIZE + current->index - lz_position)
                    & DEFLATEWINDOWMASK) ;
      if (bestlength == DEFLATELONGESTLENGTH || bestlength == count)
        break ;
    }
  }
  return ;
}

//
//  Description:
//
//    This function performs the initializations required 
//    before creating a new compressed data block.
//
void DeflateEncoder::prepareNewBlock () 
{
  length_table.reset () ; 
  distance_table.reset () ; 
  return ;
}

//
//  Description:
//
//    This function compresses data within the lookahead buffer.
//
//  Parameters:
//
//    outputstream : The stream to write the compressed data to
//    count : The number of bytes in the lookahead buffer
//    endofstream : true => no more data, 
//                  false => More data to be compressed
//
void DeflateEncoder::compressLookaheadData (DeflateOutputStream &outputstream, 
                                            unsigned int count,
                                            bool endofstream)
{
  // Here were are determining the number of characters to leave in the 
  // lookahead buffer. For all but the last pass we stop seaching when
  // the number of characters left is less than the largest possible match
  // for a copy operation. This keeps use from using less than ideal matches. 
  // The remaining characters will get processed on a subsequent call after 
  // the buffer gets refilled.
  unsigned int limit ;
  if (endofstream)
    limit = 3 ;
  else
    limit = DEFLATELONGESTLENGTH ;

  while (count >= limit)
  {
    // See if we can find a match for the input in the
    // LZ window.
    unsigned int length ;
    unsigned int offset ;
    longestMatch (count, length, offset) ;
    if (length == 0)
    {
      // There is no match of at least three. Encode this value a
      // literal value.
      UBYTE1 literal = lookahead_buffer [lookahead_output_position] ;
      unsigned int hashvalue = hashValue (lookahead_output_position) ;
      moveHashEntry (lz_position, hashvalue) ;

      lz_window [lz_position] = literal ;

      block_buffer [block_buffer_count] = literal ;
      ++ block_buffer_count ;

      length_table.incrementFrequency (literal) ;

      AdvanceLookaheadPosition (lookahead_output_position) ;
      AdvanceWindowPosition (lz_position) ;

      -- count ;
    }
    else
    {
      // We have found a match.  First update the hash table and
      // copy the data in the LZ window.
      unsigned int source = WindowOffsetToPosition (lz_position, offset) ;
      for (unsigned int ii = 0 ; ii < length ; ++ ii, AdvanceWindowPosition (source))
      {
        unsigned int hashvalue = hashValue (lookahead_output_position) ;
        moveHashEntry (lz_position, hashvalue) ;

        lz_window [lz_position] = lz_window [source] ;
        AdvanceWindowPosition (lz_position) ;
        AdvanceLookaheadPosition (lookahead_output_position) ;
      }

      block_buffer [block_buffer_count] = 256 + length ;
      ++ block_buffer_count ;
      block_buffer [block_buffer_count] = offset ;
      ++ block_buffer_count ;

      // Gather Huffman Statistics
      unsigned int code ;
      unsigned int extra ;
      unsigned int value ;
      LengthToCode (length, code, extra, value) ;
           length_table.incrementFrequency (code) ;
      DistanceToCode (offset, code, extra, value) ;
           distance_table.incrementFrequency (code) ;

      count -= length ;
    }
    // Since a code can either require 1 or 2 values
    // we need to allow at least one extra space.
    if (block_buffer_count >= block_buffer_size - 1)
    {
      outputDeflateHeader (outputstream, false) ;
      outputBlockData (outputstream) ;
    }
  }

  // During the final call to this function we need to consume all the characters.
  // Since there is a minimum of 3 characters in a copy operation, we could have
  // up to 2 character remaining that have to be transfered as literals.
  if (endofstream)
  {
    ASSERT (count <= 2)
    for ( ; count > 0 ; -- count)
    {
      UBYTE1 literal = lookahead_buffer [lookahead_output_position] ;
      block_buffer [block_buffer_count] = literal ;
      length_table.incrementFrequency (literal) ;
      ++ block_buffer_count ;
      AdvanceLookaheadPosition (lookahead_output_position) ;
    }
    outputDeflateHeader (outputstream, true) ;
    outputBlockData (outputstream) ;
  }
  return ;
}


//
//  Description:
//
//    An application calls this function when it wants to start a Deflate
//    compressed stream.
//
//  Parameters:
//
//    outputstream  : The output stream the encoder writes to.
//
//  Restrictions:
//
//    endCompressedStream must be called before calling this function 
//    again.
// 

void DeflateEncoder::startCompressedStream (DeflateOutputStream &outputstream)
{
  if (compression_in_progress)
    throw DeflateError ("Compression Already Underway") ;

  // Buffer Allocation
  lz_window = new UBYTE1 [DEFLATEWINDOWSIZE] ;
  lookahead_buffer = new UBYTE1 [LOOKAHEADSIZE] ;
  hash_values = new HashEntry [DEFLATEWINDOWSIZE] ;
  hash_table = new HashEntry [HASHTABLESIZE] ;

  // Convert the compression level to the maximum depth hash
  // chains are searched.
  switch (compression_level)
  {
  case FASTESTCOMPRESSION: search_limit = 1 ;        break ;
  case FASTCOMPRESSION:    search_limit = 64 ;       break ;
  case DEFAULTCOMPRESSION: search_limit = 128 ;      break ;
  case MAXIMUMCOMPRESSION: search_limit = UINT_MAX ; break ;
  default: throw DeflateError ("Invalid Compression Level") ;
  }

  // Checksum Initialization
  adler_value = 1 ; 

  // Block Buffer Initialization
  block_buffer = new UBYTE2 [block_buffer_size] ;
  block_buffer_count = 0 ;

  // LZ Window and Lookahead buffer initialization
  memset (lz_window, 0, DEFLATEWINDOWSIZE) ;
  lz_position = 0 ;
  lookahead_input_position = 0 ;
  lookahead_output_position = 0 ;
  initializeHashTable () ;

  // Hash Table Initialization
  prepareNewBlock () ;

  // Output the Deflate Header.
  outputstream.enterBitMode (0) ;
  outputZLibHeader (outputstream) ;

  compression_in_progress = true ;
  return ;
}

//
//  Description:
//
//    Applications call this function to suuply raw data to the 
//    encoder. An application may make any number of calls
//    to this function.
//
//  Parameters:
//
//    outputstream  : The output stream the encoder writes to.
//    outputbuffer  : A pointer to the data to compress
//    outputcount   : The number of bytes in the output buffer.
// 
//  Restrictions:
//
//    This function must be called after startCompressedStream and 
//    before calling endCompressedStream.
//
//    An application should use the same outputstream supplied to
//    startCompressedStream in each call to this function.
//
void DeflateEncoder::compressData (DeflateOutputStream &outputstream, 
                                   const char outputbuffer [], 
                                   unsigned int outputcount) 
{
  // Ensure that the compressor is in a valid state.
  if (! compression_in_progress)
    throw DeflateError ("Compression Not Underway") ;

  // Feed the raw data unto the lookahead buffer.
  for (unsigned int ii = 0 ; ii < outputcount ; ++ ii)
  {
    adler_value = Adler (adler_value, outputbuffer [ii]) ;
    lookahead_buffer [lookahead_input_position] = outputbuffer [ii] ;
    AdvanceLookaheadPosition (lookahead_input_position) ;

    // When the lookahead buffer is full, compress the data.
    if (lookahead_input_position == lookahead_output_position)
        compressLookaheadData (outputstream, LOOKAHEADSIZE, false) ;   
  }
  return ;
}

//
//  Description:
//
//    An application calls this function to inform the encoder that
//    all the data has been transmitted to the encoder.
//
//    Here we flush the lookahead buffer and write the checksum.
//
//  Parameters:
//
//    outputstream : The outputstream the encoder writes to.
//
//  Restrictions:
//
//    This function must follow a call to startCompressedStream.
//
//    An application should use the same outputstream supplied to
//    startCompressedStream.
//
void DeflateEncoder::endCompressedStream (DeflateOutputStream &outputstream) 
{
  if (! compression_in_progress)
    throw DeflateError ("Compression Not Underway") ;

  // Compress anything that remains in the lookahead buffer.
  unsigned int count = LOOKAHEADMASK 
                     & (LOOKAHEADSIZE - lookahead_output_position + lookahead_input_position) ;
  compressLookaheadData (outputstream, count, true) ;   

  // Output the final Adler32 value. We need to byte align this value.
  outputstream.exitBitMode () ;
  outputstream.writeBigEndianLong (adler_value) ;

  // Final cleanup.
  freeBuffers () ;
  compression_in_progress = false ;
  return ;
}






} // End Namespace Colosseum