# Arithmetic Coding for Images

This topic is 4913 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, I'm working on a custom lossless image for my game using an arithmetic coder. Here is the code that I have so far:
Uint16 m_nCode;					// The present input code value
Uint16 m_nLow;					// Start of the current code range
Uint16 m_nHigh;					// End of the current code range
Uint32 m_nUnderflowBits;		// Number of underflow bits pending

#define BUFFER_SIZE 256
Uint8 buffer[BUFFER_SIZE + 2];	// This is the i/o buffer
Uint8 *m_pCurrentByte;			// Pointer to current byte

Sint32 input_bytes_left;
Sint32 input_bits_left;
Bool m_bPastEof;

Uint16 HiVal[256];
Uint16 LoVal[256];
Uint16 m_nScale;

// When decoding, this routine is called to figure out which symbol
// is presently waiting to be decoded.
Uint16 get_current_count (void)
{
Uint32 range;
Uint16 count;

range = (Uint32)(m_nHigh - m_nLow) + 1;
count = (Uint16)((((Uint32)(m_nCode - m_nLow) + 1) * m_nScale-1) / range);

return count;
}

// This routine reads bits in from a file.  This routine is set up to
// allow for two dummy bytes to be read in after the end of file is
// reached.  This is because we have to keep feeding bits into the
// pipeline to be decoded so that the old stuff that is 16 bits upstream
// can be pushed out.
Uint16 input_bit (CFile *stream)
{
if (input_bits_left == 0)
{
m_pCurrentByte++;
input_bytes_left--;
input_bits_left = 8;

if (input_bytes_left == 0)
{

if (input_bytes_left == 0)
{
if (m_bPastEof)
{
exit(-1);
}

else
{
m_bPastEof = 1;

// Read two past, since two bits need to be shifted out
// of high and low to complete word
input_bytes_left = 2;
}
}

m_pCurrentByte = buffer;
}
}

input_bits_left--;

// Return the lowest bit
return ((*m_pCurrentByte >> input_bits_left) & 1);
}

/*
* Just figuring out what the present symbol is doesn't remove
* it from the input bit stream.  After the character has been
* decoded, this routine has to be called to remove it from the
* input stream.
*/
void remove_symbol_from_stream (CFile *stream, Uint16 low_count, Uint16 high_count)
{
Uint32 nRange;

nRange = (m_nHigh - m_nLow) + 1;
m_nHigh = m_nLow + (Uint16)((nRange * high_count) / m_nScale - 1);
m_nLow = m_nLow + (Uint16)((nRange * low_count) / m_nScale);

while (True)
{
// The most significant bits match, so shift them out
if ((m_nHigh & 0x8000) == (m_nLow & 0x8000))
{
}

// If underflow is threatining, shift out the 2nd most significant
else if ((m_nLow & 0x4000) && !(m_nHigh & 0x4000))
{
// Flip second most significant of code
m_nCode ^= 0x4000;

// Clear 2 upper bits of low
m_nLow &= 0x3fff;

// Change second most significant of high to 1
m_nHigh |= 0x4000;
}
else
{
return;
}

m_nLow <<= 1;
m_nHigh <<= 1;
m_nCode <<= 1;

// Bring in a new high bit
m_nHigh |= 1;

// Bring in a new input bit
m_nCode += input_bit(stream);
}
}

{
short int count = get_current_count();

// Find the range the value is in
for (Uint8 i = 0; i < 256; i++)
{
if ( count >= LoVal && count < HiVal)
{
remove_symbol_from_stream(pFile, LoVal, HiVal);
return i;
}
}

return 0;
}

// Create the minimum and maximum probability tables for each color value
void CreateTables (void)
{
m_nScale = 0;

for (Sint32 i = 0; i < 256; i++)
{
LoVal = m_nScale;

// Because of filtering, low values are common, and so are
// high values which represent negative. Give them a higher
// probability.
if (i <= 10 || i >= 245)
{
HiVal = m_nScale+10;
m_nScale += 10;
}

else if (i <= 20 || i >= 235)
{
HiVal = m_nScale+5;
m_nScale += 5;
}

else
{
HiVal = m_nScale+1;
m_nScale += 1;
}
}
}

//////////////////////////////////////////////////////////////////////////
// Loads image from given file into pBuffer.
//////////////////////////////////////////////////////////////////////////
Bool LoadIgf (Uint8 **pBuffer, CFile *pFile, Sint32 &nWidth, Sint32 &nHeight)
{
CreateTables();

m_nCode = 0;

for (int i = 0; i < 16; i++)
{
m_nCode <<= 1;
m_nCode += input_bit(pFile);
}

m_nLow = 0;
m_nHigh = 0xffff;

input_bits_left = 0;
input_bytes_left = 1;
m_bPastEof = False;

*pBuffer = new Uint8[nWidth*nHeight*3];
Uint8 *pColor = *pBuffer;

for (int y = 0; y < nHeight; y++)
{
// First pixel in each row is not filtered
pColor++;
pColor++;
pColor++;

// Read rest of row, filtering as we go
for (int x = 1; x < nWidth; x++)
{
*pColor = (Uint8)(((Uint)*(pColor-3) + ReadNextVal(pFile)) & 0xff);
pColor++;
*pColor = (Uint8)(((Uint)*(pColor-3) + ReadNextVal(pFile)) & 0xff);
pColor++;
*pColor = (Uint8)(((Uint)*(pColor-3) + ReadNextVal(pFile)) & 0xff);
pColor++;
}
}

return True;
}

/*
* The output bit routine just has to set a bit in the current byte
* shows that the current byte is filled up, it is time to go to the
* next character in the buffer.  If the next character is past the
* end of the buffer, it is time to flush the buffer.
*/
void output_bit (CFile *stream, int bit)
{
// Write the bit if it's a 1 to the next bit position
if (bit)
{
}

// Increase the bit position

// We filled this byte
{
m_pCurrentByte++;

// Buffer is full, so write it
if (m_pCurrentByte == (buffer + BUFFER_SIZE))
{
stream->Write(buffer, BUFFER_SIZE);
m_pCurrentByte = buffer;
}

// Initialize next byte to 0
*m_pCurrentByte = 0;
}
}

// This routine uses a low count, a high count, and a range,
// instead of the more conventional probability ranges.  The encoding
// process takes two steps.  First, the values of high and low are
// updated to take into account the range restriction created by the
// new symbol.  Then, as many bits as possible are shifted out to
// the output stream.  Finally, high and low are stable again and
// the routine returns.
void encode(CFile *stream, Uint16 low_count, Uint16 high_count)
{
Uint32 range;

// Add one because high is one under
range = (m_nHigh-m_nLow) + 1;

// Make high one under so it continues forever
m_nHigh = m_nLow + (Uint16)((range * high_count) / m_nScale - 1);

m_nLow = m_nLow + (Uint16)((range * low_count) / m_nScale);

// Output common bits between high and low
while (True)
{
// The most significant digit matches, output it
if ((m_nHigh & 0x8000) == (m_nLow & 0x8000))
{
output_bit(stream, m_nHigh & 0x8000);

while (m_nUnderflowBits > 0)
{
output_bit(stream, (~m_nHigh) & 0x8000);
m_nUnderflowBits--;
}
}

// Test if the numbers are in danger of underflow.
// The significant bits don't match, and low is approaching high, ex:
// high = 10000000 low = 01111111
else if ((m_nLow & 0x4000) && !(m_nHigh & 0x4000))
{
m_nUnderflowBits += 1;

// Clear 2 upper bits of low
m_nLow &= 0x3fff;

// Change second most significant of high to 1
m_nHigh |= 0x4000;
}

else
{
return;
}

m_nLow <<= 1;
m_nHigh <<= 1;

// Insert a new one (high continues forever)
m_nHigh |= 1;
}
}

/*
* 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.
*/
void flush_arithmetic_encoder (CFile *stream)
{
output_bit(stream, m_nLow & 0x4000);
m_nUnderflowBits++;
while (m_nUnderflowBits-- > 0)
output_bit(stream, (~m_nLow) & 0x4000);
}

void flush_output_bitstream (CFile *stream)
{
stream->Write(buffer, (m_pCurrentByte - buffer) + 1);
m_pCurrentByte = buffer;
}

// Write the given image buffer to file
Bool SaveIgf (Uint8 *pBuffer, CFile *pFile, Sint32 &nWidth, Sint32 &nHeight)
{
m_nLow = 0;
m_nHigh = 0xffff;
m_nUnderflowBits = 0;
m_pCurrentByte = buffer;
*m_pCurrentByte = 0;

CreateTables();

pFile->WriteWord(nWidth);
pFile->WriteWord(nHeight);

Uint8 val;

for (int y = 0; y < nHeight; y++)
{
// Write the first pixel plainly, because there is no pixel to the left
// to filter from

val = *pBuffer;
encode_symbol(pFile, LoVal[val], HiVal[val]);
pBuffer++;
val = *pBuffer;
encode_symbol(pFile, LoVal[val], HiVal[val]);
pBuffer++;
val = *pBuffer;
encode_symbol(pFile, LoVal[val], HiVal[val]);
pBuffer++;

// Write rest of row
for (int x = 1; x < nWidth; x++)
{
// Filter each channel as its written (subtract value from prior pixel)

// Write the red channel
val = ((Sint)*pBuffer - (Sint)*(pBuffer-3)) & 0xff;
encode(pFile, LoVal[val], HiVal[val]);
pBuffer++;

// Write the blue channel
val = ((Sint)*pBuffer - (Sint)*(pBuffer-3)) & 0xff;
encode(pFile, LoVal[val], HiVal[val]);
pBuffer++;

// Write the green channel
val = ((Sint)*pBuffer - (Sint)*(pBuffer-3)) & 0xff;
encode(pFile, LoVal[val], HiVal[val]);
pBuffer++;
}
}

flush_arithmetic_encoder(pFile);
flush_output_bitstream(pFile);

return True;
}


As you can probably see, I'm filtering each row by subtracting each pixel channel color from the previous pixel's corresponding color, which gives me a value around -10 to 10 that is translated to about 245-255 and 0-10. I then pass the values to a coder, and set the probabilities higher for the usual filtered values. However the program always reaches the exit() call and closes. If I set the probabilities equally (x for the low, x+1 for the high, 256 for the scale) I obviously don't get any compression, but the program doesn't reach the exit line. I have found that although the equal probabilities don't cause the program to close, the images has a strong greenish tinge. This is not from the filtering, as I have tested the filtering without the coding and the coding without the filtering. Any ideas on why this code is acting up is appreciated. I am using the arithmetic coding method from http://dogma.net/markn/articles/arith/part1.htm . Thanks! Jon

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 10
• 11
• 13
• 9
• 11
• ### Forum Statistics

• Total Topics
634090
• Total Posts
3015433
×