*****************************************************
**** ****
**** 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!
|