*****************************************************
****                                             ****
****   Faxdecod.c                                ****
****                                             ****
*****************************************************

/***************************************************************************

   Faxdecoder : Usage faxdecoder uncompressed.fax

   This program compresses a fax using a model based on an order 16 model.
   Context is as follows : C = Context bits, P = bit being predicted

	  			   x
				xxxxxx
				xxxxxx
				xxxP

   Variable names beginning with capital letters are arithmetic coding
   variables used by the arithmetic coding routines.

			-------------------------------

   Copyright Raymond P. Wilson 1989.

   This program is a shareware program. If you use it then credit must be
   given to the author (me). If you find this program useful please send
   whatever you think it is worth ($25 is suggested) to :

			Raymond P. Wilson
			38 Paremata St
			Atawhai
			Nelson
			New Zealand

 **************************************************************************/
 
#include 
#include 
#include 
#include "coderdef.i"	    /* My faxcoder definitions etc... */
#include "arithdec.i" /* Arithmetic decoding functions and defs ... */

/*************************************************************************

   Function   : Initialise_model
   Parameters : None
   Returns    : Nothing

   Initialise_model sets up all the structures and initialisation
 required by the fax coder. 

 ************************************************************************/

void initialise_model()
{
   int i;

   /* Initialise context bits and saved context arrays */
  
   for (i = 0;i < CONTEXT_WINDOW_BPL;i++)
      saved[i] = 0;

   /* Initialise context information array */
  
   for (i = 0;i < NUM_CONTEXTS;i++)
   {
      contexts[i].zero_count = 1;
      contexts[i].sum = 2;   /* No explicit count of ones is kept */      
   }			     /* as this is implicit in the sum	  */
}

/************************************************************************
 
   Function   : Decompress
   Parameters : None
   Returns    : Nothing
   
   Decompress decompresses a fax file read in from std input.
   
 ***********************************************************************/
 
void decompress()
{
   register codevalue	S_low=0, S_high=0;
 		    /* Arithmetic decoder vars high and low of range */
   register int 
      context,      /* Context at predicted bit */
      bitnum,       /* Bit being compressed on current line */
      S_bitstogo,   /* Arithmetic decoder var - used in inputting bits */
      H = half,     /* Arithmetic decoder var - contains constant half */
      last,         /* Shifting three bit field of last three bits read in */
      bitsleft = 8, /* Mask for getting bit out of byte */
      byte = 0;     /* Byte read in from  */

   startinputingbits();
   startdecoding();

   for (line = 0;line < NUM_LINES;line++)
   {
      last = 0;   /* Clear shifting temporary storage for incoming bits */

    /* Start iterating over bits in line - start in from edge of 'sheet'
       to give white space at edge for context */

      for (bitnum = CONTEXT_SIDE_BITS;
           bitnum < (CONTEXT_SIDE_BITS + BITS_PER_LINE);bitnum++)
      {

   /* Work out context that precedes bit being predicted */

         context = saved[bitnum] | (last >> 3);

    /* Store that part of the context that will be used on the next line */ 
 
         saved[bitnum] = (context & CONTEXT_MASK) << 6;
    
    /* Decode the bit currently being decompressed and update the model */
    /* Call arithmetic_decode_target to get position in range */
        
         if (arithmetic_decode_target(contexts[context].sum) 
               < contexts[context].zero_count)
         {  
            /* Decode a zero bit */
            arithmetic_decode_zero(contexts[context].zero_count,
                                   contexts[context].sum);
                                   
            contexts[context].zero_count++; /* Increment zero bit count */
            write_decoded0;                 /* Output a decoded zero */

       /* Add a zero bit to shifting storage and add this to previously
          stored context from two bits back */
           
            saved[bitnum-2] |= (last = (last << 1) & 0x38);            
         }
         else
         {
            /* 'Decode' a one bit */
            arithmetic_decode_one(contexts[context].zero_count,
                                  contexts[context].sum);
                                  
            write_decoded1; /* Write out a decoded ont bit */

       /* Add a zero bit to shifting storage and add this to previously
          stored context from two bits back */
 
            saved[bitnum-2] |= (last = ((last << 1) | 0x8) & 0x38);
         }                                                         

       /* Increment sum count and check to see if counts need halving */
       
         if ((++contexts[context].sum) == HALVE_LIMIT)  
         {
            contexts[context].zero_count = (contexts[context].zero_count >> 2) + 1;
            contexts[context].sum = (contexts[context].sum >> 2) + 2;
         }
      }
   }
}

/*************************************************************************

                                 Main program.
   
 ************************************************************************/
 
main(argc,argv)
int argc;
char **argv;
{
   initialise_model();
   fprintf(stderr,"Decompressing file, please wait.\n");
   start_time = get_time();              /* Get starting time */
   decompress();			 
   total_time = get_time() - start_time; /* Get total time from difference */  
   fprintf(stderr,"%s: Decompressed fax in %.3f seconds.\n",argv[0],total_time);
   exit(0);
}




*****************************************************
****                                             ****
****   Faxcoder.c                                ****
****                                             ****
*****************************************************

/***************************************************************************

    Faxcoder : Usage faxcoder output

    This program compresses a fax using a model based on an order 16 model.
    Context is as follows : x = Context bits, P = bit being predicted
   
	  			   x
				xxxxxx
				xxxxxx
				xxxP
 
   Variable names beginning with capital letters are arithmetic coding
   variables used by the arithmetic coding routines.

			-------------------------------

   Copyright Raymond P. Wilson 1989.

   This program is a shareware program. If you use it then credit must be
   given to the author (me). If you find this program useful please send
   whatever you think it is worth ($25 is suggested) to :

			Raymond P. Wilson
			38 Paremata St
			Atawhai
			Nelson
			New Zealand

    If you want to use this or parts of this program in a commercial product
 then the authors permission is required.

 **************************************************************************/
 
#include 
#include 
#include 
#include "coderdef.i"	    /* My faxcoder definitions etc... */
#include "arithcod.i"	/* Arithmetic coding functions and defs... */

/*************************************************************************

   Function   : Initialise_model
   Parameters : None
   Returns    : Nothing

   Initialise_model sets up all the structures and initialisation
 required by the fax coder. 

 ************************************************************************/

void initialise_model()
{
   int i;

   /* Initialise context bits and saved context arrays */
  
   for (i = 0;i < CONTEXT_WINDOW_BPL;i++)
      saved[i] = 0;

   /* Initialise context information array */
  
   for (i = 0;i < NUM_CONTEXTS;i++)
   {
      contexts[i].zero_count = 1;
      contexts[i].sum = 2;
   }
}

/************************************************************************

   Function   : Compress
   Parameters : None
   Returns    : Nothing
   
   Compress compresses a fax file read in from std input.
   
 ***********************************************************************/
 
void compress()
{
   register codevalue	S_low=0, S_high=0;
 		    /* Arithmetic coder vars high and low of range */
   register int 
      context,      /* Context at predicted bit */
      bitnum,       /* Bit being compressed on current line */
      S_bitstogo,   /* Arithmetic coder var - used in inputting bits */
      H = half,     /* Arithmetic coder var - contains constant half */
      last,         /* Shifting three bit field of last three bits read in */
      mask = 0,     /* Mask for getting bit out of byte */
      byte = 0;     /* Byte read in from  */
      
   startoutputingbits();
   startencoding();
  
   for (line = 0;line < NUM_LINES;line++)
   {
      last = 0;   /* Clear shifting temporary storage for incoming bits */

    /* Start iterating over bits in line - start in from edge of 'sheet'
       to give white space at edge for context */
       
      for (bitnum = CONTEXT_SIDE_BITS;
           bitnum < (CONTEXT_SIDE_BITS + BITS_PER_LINE);bitnum++)
      {
      
    /* Work out context that precedes bit being predicted */
   
         context = saved[bitnum] | (last >> 3);
                   
    /* Store that part of the context that will be used on to the next line */ 
 
         saved[bitnum] = (context & CONTEXT_MASK) << 6;
    
     /* Get the bit that is to be compressed */
    
         getabit()
         
    /* Code the bit currently being compressed and update the model */
   	
         if (byte & mask)
         {
            arithmetic_encode_one(contexts[context].zero_count,
                                  contexts[context].sum)
                                  
       /* Add a one bit to shifting storage and add this to previously
          stored context from two bits back */
                                        
            saved[bitnum-2] |= (last = ((last << 1) | 0x8) & 0x38);
         }
         else
         {
            arithmetic_encode_zero(contexts[context].zero_count,
                                   contexts[context].sum);

       /* Add a zero bit to shifting storage and add this to previously
          stored context from two bits back */

            saved[bitnum-2] |= (last = (last << 1) & 0x38);
            
            contexts[context].zero_count++; /* Increment zero bit count */
         }

       /* Increment sum count and check to see if counts need halving */
       
         if ((++contexts[context].sum) == HALVE_LIMIT)  
         {
            contexts[context].zero_count = (contexts[context].zero_count >> 2) + 1;
            contexts[context].sum = (contexts[context].sum >> 2) + 2;
         }
      }
   }
   /* Finish up encoding and finishing outputting bits */
   doneencoding();
   doneoutputingbits();
}

/*************************************************************************

                                 Main program.
   
 ************************************************************************/
 
main(argc, argv)
int argc;
char **argv;
{
   initialise_model();
   fprintf(stderr,"Compressing file, please wait...\n\n");
   start_time = get_time();             /* Get starting time */
   compress();
   total_time = get_time() - start_time; /* Get total time from difference */
   fprintf(stderr,"%s: compression %4.2f bpc (%4.2f : 1) in %.3f seconds.\n",
                  argv[0], (8 * cmpbytes)/(double)FAX_SIZE,
                  FAX_SIZE/(float)cmpbytes, total_time);
   exit(0);
}



*****************************************************
****                                             ****
****   Coderdef.i                                ****
****                                             ****
*****************************************************


/*********************************************************************

   FAXCOM Copyright Raymond P. Wilson 1989.

   This program is a shareware program. If you use it then credit must be
   given to the author (me). If you find this program useful please send
   ($25 is suggested) or whatever you think it is worth to :

			Raymond P. Wilson
			38 Paremata St
			Atawhai
			Nelson
			New Zealand

If you wish to use this, or parts of this, program in a commercial product then the authors permission is required.

**********************************************************************/
/* This file contains variable and macro definitions common to the
   faxcoder and faxdecoder */

#define NUM_LINES          2376    /* Number of lines in the fax */
#define BYTES_PER_LINE     216     /* Bytes per line in fax */
#define BITS_PER_LINE      (8 * BYTES_PER_LINE)
				   /* Bits on a fax line */
#define FAX_SIZE           (NUM_LINES * BYTES_PER_LINE)
				   /* Size (in bytes) of a fax file */
#define MODEL_ORDER        16      /* Number of bits of context */
#define NUM_CONTEXTS       (1 << MODEL_ORDER)
#define HALVE_LIMIT        16383   /* Halve counts when sum reaches this */

#define CONTEXT_MASK       0x3ff /* This masks out unwanted portions of the
                                    context from the bit immediately above */
                                    
#define CONTEXT_SIDE_BITS  3 /* Number bits to side of fax page to allow
				for context spilling over sides */
                              
#define CONTEXT_WINDOW_BPL (BITS_PER_LINE + 2 * CONTEXT_SIDE_BITS)
			     /* Bits per line for context bits array */

int cmpbytes = 0,   /* Number of compressed bytes outputted */
    line,           /* Line currently on in fax file */
    saved[CONTEXT_WINDOW_BPL];
                    /* Array that holds saved pieces of context */

struct context_type    /* This structure holds the counts for zeros and the */
{		       /* sum of zeros and ones for a context               */
   int zero_count, sum;
} contexts[NUM_CONTEXTS]; /* The array that holds context information */

/* Get a bit from the input file */

#define getabit() 	\
   if ((mask>>=1) ==0)	\
   {			\
      byte=getchar();	\
      mask=0x80;	\
   }

/* Write a zero bit out to the output file */

#define write_decoded0       \
{                            \
   byte <<= 1 ;              \
   bitsleft-- ;              \
   if (bitsleft==0)          \
   {                         \
      putc(byte, stdout) ;   \
      bitsleft = 8 ;         \
   }                         \
}

/* Write a one bit out to the output file */

#define write_decoded1       \
{                            \
   byte = (byte << 1) | 0x1; \
   bitsleft-- ;              \
   if (bitsleft==0)          \
   {                         \
      putc(byte, stdout) ;   \
      bitsleft = 8 ;         \
   }                         \
}

#ifdef UNIX
float start_time,total_time;
/*
 * get_time()
 *
 * return amount of CPU time in seconds used since starting
 */

float get_time()
{
        struct rusage rusage;

	getrusage(RUSAGE_SELF,&rusage);
        return(rusage.ru_utime.tv_sec +
	       rusage.ru_utime.tv_usec/1000000.0 +
	       rusage.ru_stime.tv_sec +
	       rusage.ru_stime.tv_usec/1000000.0) ;
}
#endif



*****************************************************
****                                             ****
****   Arithdec.i                                ****
****                                             ****
*****************************************************


/*************************************************************************

   This program is shareware. If you use it and find it useful please
   send ($25 is suggested) or whatever you think it is worth to :

			 Raymond P. Wilson
			 38 Paremata St.
			 Atawhai
			 Nelson
			 New Zealand

   If you wish to use this program or parts of this program in a
commercial the authors permission is required.

Copyright Raymond P. Wilson 1989

**************************************************************************/

/* arithmetic coding routines */

/* Most of the functions here have been converted to macro definitions
   to speed them up and have been customised for a binary alphabet */

#define codevaluebits 16
typedef long codevalue ;

#define topvalue (((long)1<>= 1 ; 		\
  } 

/*==================================*/

#define arithmetic_decode_zero(hbnd, totl) 				\
{									\
   S_high = S_low  +  (((long)(S_high-S_low)+1) * hbnd)/totl - 1 ;	\
   									\
   for (;;)								\
     { if (S_high=H) 							\
         { S_value -= H ;						\
           S_low -= H ;							\
           S_high -= H ;						\
         }								\
       else								\
       if (S_low>=firstqtr && S_high=H)  							\
         { S_value -= H ; 						\
           S_low -= H ; 						\
           S_high -= H ; 						\
         } 								\
       else 								\
       if (S_low>=firstqtr && S_high0)    \
        { outputbit1 ;            \
          S_bitstofollow--;       \
        }                         \
    }

#define bitplusfollow1            \
    { outputbit1 ;                \
      while (S_bitstofollow>0)    \
        { outputbit0 ;            \
          S_bitstofollow--;       \
        }                         \
    }

#define outputbit0                \
    { S_buffer >>= 1;		  \
      S_bitstogo--;               \
      if (S_bitstogo==0)          \
        { putc(S_buffer, stdout) ;\
          S_bitstogo = 8 ;        \
          cmpbytes++ ;            \
        }                         \
    }

#define outputbit1                \
    { S_buffer = (S_buffer >> 1) | 0x80;            \
      S_bitstogo--;               \
      if (S_bitstogo==0)          \
        { putc(S_buffer, stdout) ;\
          S_bitstogo = 8 ;        \
          cmpbytes++ ;            \
        }                         \
    }

/*==================================*/

#define arithmetic_encode_zero(hbnd, totl)				\
{									\
   S_high = S_low  +  (((long)(S_high-S_low)+1) * hbnd)/totl - 1 ;	\
									\
   for (;;)								\
     { if (S_high=H) 							\
         { bitplusfollow1 ;						\
           S_low -= H ;							\
           S_high -= H ;						\
         }								\
       else								\
       if (S_low>=firstqtr && S_high=H) 							\
         { bitplusfollow1 ;						\
           S_low -= H ;							\
           S_high -= H ;						\
         }								\
       else								\
       if (S_low>=firstqtr && S_high>S_bitstogo, stdout) ;\
    cmpbytes++;				\
  }




Discuss this article in the forums


Date this article was posted to GameDev.net: 7/16/1999
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
Compression Algorithms

© 1999-2011 Gamedev.net. All rights reserved. Terms of Use Privacy Policy
Comments? Questions? Feedback? Click here!