lz77.c

来自「Microsoft Visual C++ 6.0环境下的无损压缩测试工程」· C语言 代码 · 共 734 行 · 第 1/2 页

/*****************************************************************************/
/* Name : MatchPeek()
 *
 * Notes: This function is used by the lazy compression scheme to look
 *        for matches farther down the data stream.
 */

struct Match MatchPeek( struct LZ77Info * info, struct LzMode * mode,
                        const UBYTE * input, ULONG length, int distance )
{
    ULONG           tempOffset;
    ULONG           tempMaxOffset;
    struct Match    newMatch;
    UBYTE         * tempBuffer;
    

    /* First, save the current buffer state. */

    tempBuffer = malloc( (BUF_SIZE( mode ) * 2) + mode->m_MaxLength );
    memcpy( tempBuffer, info->buffer, (BUF_SIZE( mode ) * 2) + mode->m_MaxLength );
    tempOffset = info->bufferOffset;
    tempMaxOffset = info->maxOffset;


    /* Now update the buffer as if we had written the next `distance'
     * characters out as literals.
     */

    UpdateMatchTables( info, input + mode->m_MaxLength, distance, mode );
    mode->m_MaxOffset -= distance;


    /* Finally we attempt to find a new match at the new buffer
     * position.
     */

    newMatch = FindMatch( info, input + distance,
                          ( length > mode->m_MaxLength ) ? mode->m_MaxLength 
                          : length,
                          mode );


    /* Reset the buffer to its initial state. */

    mode->m_MaxOffset += distance;
    memcpy( info->buffer, tempBuffer, (BUF_SIZE( mode ) * 2) 
                                      + mode->m_MaxLength );
    info->bufferOffset = tempOffset;
    info->maxOffset = tempMaxOffset;


    /* Return the match that we found at the new buffer position. */

    return( newMatch );
}




/*****************************************************************************/
/* Name : WriteMatch()
 *
 * Notes: This function takes the specified match value and converts it into
 *        one 16-bit word and writes this word to the output stream.  In a
 *        match tag word, the upper four bits denote the length of the run,
 *        and the low twelve bits specify the offset to the first character
 *        in the run.  Therefore, the next 16-bits in the output stream
 *        would look something like this:
 *
 *         L  L  L  L  O  O  O  O  O  O  O  O  O  O  O  O
 *        15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
 */

UBYTE * WriteMatch( struct LZ77Info * info, struct Match * match,
                    UBYTE * output, const UBYTE * input )
{
    /* This is done to make sure that we can't compress data that is
     * beyond the end of the input buffer.  This should probably be
     * taken care of in the actual matching routine, but I'm feeling
     * a little lazy right now. :)
     */

    if ( (input + match->m_Length) > (info->input + info->length) )
    {
        match->m_Length = (info->input + info->length) - input;
    }


    if ( match->m_Length > (MAX_LENGTH + 1) )
    {
        if ( match->m_Length > MAX_ELENGTH )
            match->m_Length = MAX_ELENGTH;

        /* First, write out the offset as normal, but write the string
         * length as zero.  This tells the decompressor that the next
         * byte is (length-MAX_LENGTH).
	 */

        *(output++) = (match->m_Offset >> 8) & 0x000f;
        *(output++) =  match->m_Offset       & 0x00ff;

        *(output++) = match->m_Length - MAX_LENGTH;
    }
    else
    {
        UBYTE   temp;


        if ( match->m_Length > MAX_LENGTH )
            match->m_Length = MAX_LENGTH;


        /* Build the magic offset/length word and write it out to 
	 * the stream! 
	 */

        temp  = (match->m_Length - ADJ) << 4;
        temp |= (match->m_Offset >> 8) & 0x0f;
        *(output++) = temp;
        *(output++) = match->m_Offset & 0x0ff;
    }

    /* Once the offset/length data has been written to the stream, the
     * correct bit in the previous tag word needs to be set to signify
     * that this block is compressed. 
     */

    info->tagPos[0] |= ( 1L << (info->nextBit & 0x07) );


    return( AdvanceTagBit( info, output ) );
}




/******************************************************************************/
/* Name : WriteLiteral()
 *
 * Notes: This function is used to write a literal character (i.e., a non-
 *        match) to the output data stream.
 */

UBYTE * WriteLiteral( struct LZ77Info * info, int literal, UBYTE * output )
{
    *(output++) = literal;
    return( AdvanceTagBit( info, output ) );
}




/*****************************************************************************/
/* Name : DecompressLZ77()
 *
 * Notes: This function performs all decompression of LZ77 data streams
 *        created by the CompressLZ77() function.
 */

ULONG DecompressLZ77( struct LZ77Info * info )
{
    UWORD   tag;        /* Current compression tag bits.    */
    UBYTE * input;      /* Input data bytes (compressed).   */
    UBYTE * output;     /* Output data bytes (decompressed).*/
    UWORD   lcv;        /* Local counter variable.          */
    ULONG   size;       /* Decompressed data size.          */
    ULONG   length;     /* Compressed bytes remaining.      */


    info->hashTable = NULL;


    input  = info->input;
    length = info->length;
    output = info->output;
    size   = 0;

    while ( length > 0 )
    {
        tag = (input[0] << 8) | (input[1]);
        length -= 2;
        input  += 2;


        for ( lcv = 0 ; (lcv < 16) && (length > 0) ; lcv++ )
        {
            if ( 0x8000 & tag )
            {
                WORD    offset;
                UWORD   runSize;


                /* If the current tag bit is set, then the next two bytes
                 * are an offset/length pair. */

                runSize = ((input[0] >> 4) & 0x000f) + ADJ;

                /* Calculate the offset to the string.  The last ``or'' is
                 * needed to sign-extend from 12-bits to 16-bits. 
		 */

                offset  = (*(input++) & 0x000f) << 8;
                offset |= (*(input++) & 0x00ff);
                offset |= 0xf000;
                length -= 2;


                /* If the run-size value written to the stream was a zero,
                 * then the run is actually an extended run.  This means
                 * that the next byte is equal to (runSize - MAX_LENGTH).
                 */

                if ( runSize == ADJ )
                {
                    UBYTE   temp;


                    temp = *(input++);

                    runSize = (UWORD)temp + MAX_LENGTH;
                    length--;
                }


                /* Copy the string from the specified offset into the output
                 * buffer.  DO NOT change this code to use ``memcpy().''  If
                 * you do, it will NOT work correctly.  Trust me, I tried
                 * it that way. :) 
		 */

                size += runSize;
#if 1
                while ( runSize-- )
                {
                    output[0] = output[ offset ];
                    output++;
                }
#else
                /* Take a look at flz.html to see the pros/cons of using this
                 * alternate code segment.
                 */

                output[0] = output[ offset ];
                output[1] = output[ offset + 1 ];
                output[2] = output[ offset + 2 ];

                output += 3;
                runSize -= 3;

                memcpy( output, output + offset, runSize );
                output += runSize;
                runSize = 0;
#endif
            }
            else
            {
                /* If the current tag bit is clear, then the next byte of
                 * data is a literal byte. 
		 */

                *(output++) = *(input++);
                length--;
                size++;
            }


            /* Advance to the next compression tag bit. */

            tag <<= 1;
        }
    }


    assert( size == (output - info->output) );
    return( output - info->output );
}




/*****************************************************************************/
/* Name : InitCompress()
 *
 * Notes:
 *
 */

UBYTE * InitCompress( struct LZ77Info * info, struct LzMode * mode )
{
    if ( info->buffer == NULL )
    {
        /* The first step is to allocate some space for a look-back
         * buffer.  This extra buffer is needed so near-optimal compression
         * can be achieved when the data to be compressed is sent to the
         * compressor in several chunks. 
	 */

        info->buffer = (UBYTE *) malloc( (BUF_SIZE(mode) * 2) 
	                                 + mode->m_MaxLength );
        if ( info->buffer == NULL )
        {
            info->hashTable = NULL;
            return( FALSE );
        }


        /* Allocate and initialize the hash table. */

        info->hashTable = AllocHashTable( mode->m_MaxOffset - 1 );
        if ( info->hashTable == NULL )
        {
            free( info->buffer );
            info->buffer = NULL;
            return( FALSE );
        }


        /* Copy some look-ahead data into the buffer.  This is done so
         * that certain strings can start compressing with the second
         * byte of input.  See header comments for details. 
	 */

        info->bufferOffset = 0;
        UpdateMatchTables( info, info->input, mode->m_MaxLength, mode );
        info->maxOffset = 0;


        /* Initialize the first tag value.  It is important that the output
         * tags be all set for literal bytes.  This way if a decompressor
         * compressor is written to only test for completion between tags,
         * a maximum of 16 extra bytes will be written out. 
	 */

        info->nextBit   = 15;
        info->tagPos    = info->output;
        info->tagPos[0] = 0;
        info->tagPos[1] = 0;
    }


    return( info->output + 2 );
}




/*****************************************************************************/
/* Name : PackFreeLZ77()
 *
 * Notes:
 *
 */

void PackFreeLZ77( struct LZ77Info * info )
{
    if ( info->hashTable != NULL )
    {
        FreeHashTable( info->hashTable );
    }

    if ( info->buffer != NULL )
    {
        free( info->buffer );
    }
}