cfs_tool.c

基于nucleus实时操作系统的webserver源代码

*       characters in the file are in the counts array, and we know      
*       that there will be a single instance of the EOF symbol.          
*                                                                       
* INPUTS                                                                
*                                                                       
*       scaled_counts           Scaled Number of bytes in file.  
*                                                                       
* OUTPUTS                                                               
*                                                                       
*       None
*                                                                       
************************************************************************/
static VOID CFS_Build_Totals(UINT8 scaled_counts[])
{
    INT i;
    
    CFS_Totals[0] = 0;
    for ( i = 0 ; i < CFS_END_OF_STREAM ; i++ )
        CFS_Totals[i + 1] = (INT16)(CFS_Totals[i] + (INT16)scaled_counts[i]);
    CFS_Totals[CFS_END_OF_STREAM + 1] = (INT16)(CFS_Totals[CFS_END_OF_STREAM] + 1);
}

/************************************************************************
*                                                                       
* FUNCTION                                                              
*                                                                       
*       CFS_Output_Counts                                                    
*                                                                       
* DESCRIPTION                                                           
*                                                                       
*       In order for the compressor to build the same model, I have      
*       to store the symbol counts in the compressed file so the         
*       expander can read them in.  In order to save space, I don't      
*       save all 256 symbols unconditionally. The format used to store   
*       counts looks like this:                                          
*                                                                       
*       start, stop, counts, start, stop, counts, ... 0                  
*                                                                       
*       This means that I store runs of counts, until all the            
*       non-zero counts have been stored.  At this time the list is      
*       terminated by storing a start value of 0.  Note that at least    
*       1 run of counts has to be stored, so even if the first start     
*       value is 0, I read it in. It also means that even in an empty    
*       file that has no counts, I have to pass at least one count.      
*                                                                       
*       In order to efficiently use this format, I have to identify      
*       runs of non-zero counts.  Because of the format used, I don't    
*       want to stop a run because of just one or two zeros in the count 
*       stream. So I have to sit in a loop looking for strings of three  
*       or more zero values in a row.                                    
*                                                                       
*       This is simple in concept, but it ends up being one of the most  
*       complicated routines in the whole program.  A routine that just  
*       writes out 256 values without attempting to optimize would be    
*       much simpler, but would hurt compression quite a bit on small    
*       files.                                                           
*                                                                       
* INPUTS                                                                
*                                                                       
*       output                  Pointer to BIT_FILE structure.   
*                               This structure holds all the     
*                               related to the output file to be 
*                               compressed.                      
*       scaled_counts           Scaled Number of bytes in file.  
*                                                                       
* OUTPUTS                                                               
*                                                                       
*       None
*                                                                       
************************************************************************/
static VOID CFS_Output_Counts(WS_BIT_FILE *output, UINT8 scaled_counts[])
{
    INT first;
    INT last;
    INT next;
    INT i;

    first = 0;
    while ( first < 255 && scaled_counts[ first ] == 0 )
        first++;
    /*
     * Each time I hit the start of the loop, I assume that first is the
     * number for a run of non-zero values.  The rest of the loop is
     * concerned with finding the value for last, which is the end of the
     * run, and the value of next, which is the start of the next run.
     * At the end of the loop, I assign next to first, so it starts in on
     * the next run.
     */
    for ( ; first < 256 ; first = next )
    {
        last = first + 1;
        while(1)
        {
            for ( ; last < 256 ; last++ )
                if ( scaled_counts[ last ] == 0 )
                    break;
                last--;
                for ( next = last + 1; next < 256 ; next++ )
                    if ( scaled_counts[ next ] != 0 )
                        break;
                    if ( next > 255 )
                        break;
                    if ( ( next - last ) > 3 )
                        break;
                    last = next;
        }
        /*
         * Here is where I output first, last, and all the counts in between.
         */
        if ( CFS_Buf_Putc((unsigned int)first, output) != first )
            CFS_Fatal_Error( "Error writing byte counts\n" );
        if ( CFS_Buf_Putc( (unsigned int)last, output ) != last )
            CFS_Fatal_Error( "Error writing byte counts\n" );
        for ( i = first ; i <= last ; i++ ) {
            if ( CFS_Buf_Putc( (unsigned int)scaled_counts[ i ], output ) !=
                (INT) scaled_counts[ i ] )
                CFS_Fatal_Error( "Error writing byte counts\n" );
        }
    }
    if ( CFS_Buf_Putc( 0, output ) != 0 )
        CFS_Fatal_Error( "Error writing byte counts\n" );
}

/************************************************************************
*                                                                       
* FUNCTION                                                              
*                                                                       
*       CFS_Input_Counts                                                     
*                                                                       
* DESCRIPTION                                                           
*                                                                       
*       When expanding, I have to read in the same set of counts.        
*       This is quite a bit easier that the process of writing           
*       them out, since no decision making needs to be done. All         
*       I do is read in first, check to see if I am all done, and        
*       if not, read in last and a string of counts.                     
*                                                                       
* INPUTS                                                                
*                                                                       
*       *input                  Pointer to BIT_FILE structure.   
*                               This structure holds all the     
*                               related to the input file to be  
*                               compressed.                      
*                                                                       
* OUTPUTS                                                               
*                                                                       
*       None
*                                                                       
************************************************************************/
static VOID CFS_Input_Counts(WS_BIT_FILE *input)
{
    INT     first;
    INT     last;
    INT     i;
    INT     c;
    UINT8   scaled_counts[256];
    
    for ( i = 0 ; i < 256 ; i++ )
        scaled_counts[ i ] = 0;
    if ( ( first = CFS_Buf_Getc( input ) ) == EOF )
        CFS_Fatal_Error( "Error reading byte counts\n" );
    if ( ( last = CFS_Buf_Getc( input ) ) == EOF )
        CFS_Fatal_Error( "Error reading byte counts\n" );
    while(1)
    {
        for ( i = first ; i <= last ; i++ )
            if ( ( c = CFS_Buf_Getc( input ) ) == EOF )
                CFS_Fatal_Error( "Error reading byte counts\n" );
            else
                scaled_counts[ i ] = ( UINT8 )c;
            
            if ( ( first = CFS_Buf_Getc( input ) ) == EOF )
                CFS_Fatal_Error( "Error reading byte counts\n" );
            if ( first == 0 )
                break;
            if ( ( last = CFS_Buf_Getc( input ) ) == EOF )
                CFS_Fatal_Error( "Error reading byte counts\n" );
    }
    CFS_Build_Totals( scaled_counts );
}

/*
 * Everything from here down define the arithmetic coder section
 * of the program.
 */

/************************************************************************
*                                                                       
* FUNCTION                                                              
*                                                                       
*       CFS_Init_Arithmetic_Encoder                                    
*                                                                       
* DESCRIPTION                                                           
*                                                                       
*       This routine must be called to initialize the encoding           
*       process. The high register is initialized to all 1s, and         
*       it is assumed that it has an infinite string of 1s to be         
*       shifted into the lower bit positions when needed.                
*                                                                       
* INPUTS                                                                
*                                                                       
*       None                                                            
*                                                                       
* OUTPUTS                                                               
*                                                                       
*       None                                                           
*                                                                       
*************************************************************************/
static VOID CFS_Init_Arithmetic_Encoder(void)
{
    CFS_Low = 0;
    CFS_High = 0xffff;
    CFS_Underflow_Bits = 0;
}

/************************************************************************
*                                                                       
* FUNCTION                                                              
*                                                                       
*       CFS_Flush_Arithmetic_Encoder                                        
*                                                                       
* DESCRIPTION                                                           
*                                                                       
*       At the end of the encoding process, there are still              
*       significant bits left in the high and low registers.             
*       We output two bits, plus as many underflow bits as               
*       are necessary.                                                   
*                                                                       
* INPUTS                                                                
*                                                                       
*       *stream                  Pointer to BIT_FILE structure.   
*                               This structure holds all the     
*                               related to the output file to be 
*                               compressed.                                                             
*                                                                       
* OUTPUTS                                                               
*