OutputCode()

This routine is complicated by the fact that it has to handle quite a few different situations in the output data. In general, this routine puts out two numbers every time it is called. The first number is the number of bits used in the output word to follow. The second number is the actual amplitude of the output, encoded using a variable-length word, as in the JPEG algorithm.

The number of bits parameter that is output first can range anywhere from zero to ten. To encode this number using standard binary arithmetic would take four bits for every number. To achieve a minor amount of savings, this routine uses a simple prefix code to output the number of bits, which will result in a small net savings.

  void OutputCode( BIT_FILE *output_file, int code )
  {
   int top_of_range;
   int abs_code;
   int bit_count;

   if ( code == 0 ) {
    OutputRunLength++;
    return;
   }
   if ( OutputRunLength != 0 ) {
     while ( OutputRunLength > 0 ) {
      OutputBits( output_file, 0, 2 );
      if ( OutputRunLength <= 16 ) {
       OutputBits( output_file, OutputRunLength - 1, 4 );
       OutputRunLength = 0;
      } else {
       OutputBits( output_file, 15, 4 );
       OutputRunLength -= 16;
      }
    }
   }
   if ( code < 0 )
    abs_code = -code;
   else
     abs_code = code;
    top_of_range = 1;
    bit_count = 1;
    while ( abs_code > top_of_range ) {
     bit_count++;
     top_of_range = ( ( top_of_range + 1 ) * 2 ) - 1;
    }
    if ( bit_count < 3 )
     OutputBits( output_file, bit_count + 1, 3 ) ;
    else
     OutputBits( output_file, bit_count + 5, 4 );
    if ( code > 0 )
     OutputBits( output_file, code, bit_count );
    else
     OutputBits( output_file, code + top_of_range, bit_count );
  }

Figure 11.13  The coding for number of bits.

As if this prefix code didn’t complicate things enough, OutputCode() has an additional thing to worry about; run-length encoding. Since it doesn’t make sense to have a number of bits equal to zero, that value is actually used to encode a run of zeros. The number of consecutive zeros is encoded as a four-bit number immediately following a bit count of zero. Note that the four-bit number encodes runs of length 1 to 16, not 0 to 15 as might be first suspected. This is done since there is no reason to waste a code on a run length of zero.

To properly encode runs of zeros, OutputCode() tracks the current run length. Anytime OutputCode() is called to send out a value of zero, the routine actually just increments the run-length counter, then returns.

The routine will finally be able to output the length of a run when one of two things happens. First, the run length can actually reach sixteen. This is the longest run we can encode, which means it will flush the counter with a run output. The other situation is when OutputCode() is called to send a non-zero code, and the run-length counter is greater than zero. This means a run has just concluded, and it is time to output if.

The final complication in this routine is the encoding of normal numbers. As was shown in the earlier figure, these have an unusual format, with each code encoding a range of negative numbers, then a range of positive numbers, with a gap in between.

OutputCode() first determines how many bits are going to be needed to encode the code by sitting in a loop checking to see if the output code falls in the appropriate range. When it finds the correct range, it encodes the number, using a different offset for negative and positive numbers.

File Expansion

Once the file-compression algorithm is understood, file expansion is relatively easy to follow. The expansion routine first reads in the quality number from the file and uses it to initialize the matrix data. It then sits in a loop, reading in 8-by-8 DCT blocks. The routine that reads the DCT data also takes it out of the zig-zag sequence, storing it in row normal fashion, then dequantizing it. At that point, it is run through the inverse DCT procedure, which returns a block of pixel data. Once an entire strip of pixel data has been read in, it is written to the uncompressed output file.

Note that the expansion routine uses an array of pointers to redirect the output of the inverse DCT to the PixelStrip array. This array has to be set up before every inverse DCT is called so the data is directed to the correct point in the pixel strip. The pixel strip is a matrix 8 rows deep and 320 columns wide.

void ExpandFile( BIT_FILE *input, FILE *output,
         int argc, char *argv[] )
{
 int row;
 int col;
 int i;
 int input_array[ N ][ N ];
 unsigned char *output_array[ N ];
 int quality;

 quality = (int) InputBits( input, 8 );
 Initialize( quality );
 for ( row = 0 ; row < ROWS; row += N ) {
  for ( col = 0 ; col < COLS ; col += N ) {
   for ( i = 0 ; i < N ; i++ )
    output_array[ i ] = PixelStrip[ i ] + col;
  ReadDCTData( input, input_array );
  InverseDCT( input_array, output_array );
  }
  WritePixelStrip( output, PixelStrip );
 }
}

ReadDCTData()

This routine reads in DCT codes from the InputCode routine, dequantizes them, then stores them in the correct location. The codes read back in have been stored in the zig-zag sequence, so they have to be redirected to their appropriate locations in the 8-by-8 block. This is accomplished with a simple table lookup.

void ReadDCTData( input_file, input_data )
BIT_FILE *input_file;
int input_data[ N ][ N ];
{
 int i;
 int row;
 int col;

 for ( i = 0 ; i < ( N * N ) ; i++ ) {
  row = ZigZag[ i ].row;
  col = ZigZag[ i ].col;
  input_data[ row ][ col ] = InputCode( input_file ) *
             Quantum[ row ][ col ];
 }
}