Reputation: 6610
Saving graphic to EEPROM, compressing graphic by filter repeating 0x00 and 0xFF to save space
As part of firmware, I want to save a graphic or graphics into the EEPROM of a MCU. The space is not much, 1K, however it can save some program space. And yes you can seperate the glyphs of the graphic to save space however it is not easy to manage and you need more code to display it right.
Most of the monochrome GUI graphics do not fill the screen entirely and contain allot of empty space or repeating pixels. The images are already compressed, each bit in a byte represent 8 pixels.
I show the graphics on a tiny display of 128x32 pixels. Display it and erase the parts that are not relevant, works perfectly fine and efficient.
So I came up with the idea to filter those repeats, to compress it a little. With success, a bitmap like this (see below), is 496 bytes and 'compressed' with my method less 401 bytes.
That doesn't sound much however is a 20% decrease in total size, really great when there is only 1K storage available.
Example of byte array:
PROGMEM const uint8_t TEP_DISPLAY [] = { /* 496 bytes */
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x80, 0x00, 0x00, 0x00, 0x00,
0x06, 0x00, 0x80, 0x90, 0x00, 0x3E, 0x01, 0x80, 0x03, 0xC0, 0x01, 0x80, 0x00, 0x47, 0x0F, 0xFE,
0x17, 0x01, 0xC0, 0x90, 0x00, 0x30, 0x00, 0x00, 0x03, 0x60, 0x01, 0x80, 0x01, 0x87, 0x10, 0x02,
0x30, 0x83, 0xE3, 0xFC, 0x00, 0x61, 0xE7, 0x39, 0xB6, 0x6F, 0x0F, 0x00, 0x03, 0x07, 0x36, 0xDA,
0x7F, 0xF0, 0x83, 0xFC, 0x7C, 0x7D, 0xB3, 0x6D, 0xB6, 0x61, 0x9B, 0x1F, 0x03, 0x87, 0x36, 0xDA,
0x30, 0x43, 0xE1, 0xF8, 0x00, 0x61, 0xB3, 0x6D, 0xA7, 0xCF, 0xB3, 0x00, 0x01, 0x80, 0x36, 0xDA,
0x13, 0x81, 0xC0, 0x60, 0x00, 0xC3, 0x66, 0x6D, 0xCC, 0x1B, 0x36, 0x00, 0x01, 0x07, 0x10, 0x02,
0x03, 0x00, 0x80, 0x60, 0x00, 0xFB, 0x66, 0x39, 0x8C, 0x0F, 0x1E, 0x00, 0x02, 0x07, 0x0F, 0xFE,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x06, 0x01, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1C, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x2A, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xA2, 0xD5, 0x54,
0x40, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x14, 0x00, 0x02,
0x00, 0xC0, 0x22, 0x00, 0x08, 0x00, 0x02, 0x20, 0x00, 0x82, 0x48, 0x20, 0x00, 0x08, 0x00, 0x00,
0x40, 0xC0, 0x01, 0xE0, 0x00, 0x01, 0xC0, 0x1E, 0x00, 0x01, 0x50, 0x00, 0xFE, 0x00, 0x0C, 0x02,
0x00, 0xC0, 0x20, 0x10, 0x08, 0x07, 0xC2, 0x01, 0x00, 0x80, 0x00, 0x21, 0x01, 0x08, 0x0E, 0x00,
0x4F, 0xFC, 0x00, 0xFE, 0x00, 0x0F, 0x40, 0x3F, 0xF8, 0x03, 0xF8, 0x03, 0x01, 0x80, 0x0B, 0x02,
0x1C, 0xC2, 0x21, 0x11, 0x08, 0x1C, 0x42, 0x40, 0x04, 0x84, 0x04, 0x21, 0x11, 0x08, 0x69, 0x80,
0x59, 0xE2, 0x01, 0x11, 0x00, 0x18, 0x40, 0x55, 0x54, 0x05, 0x54, 0x03, 0x39, 0x80, 0x3B, 0x02,
0x12, 0xD2, 0x21, 0x11, 0x08, 0x10, 0x42, 0x40, 0x04, 0x84, 0x04, 0x21, 0x7D, 0x08, 0x1E, 0x00,
0x54, 0xCA, 0x01, 0x83, 0x00, 0x10, 0x40, 0x55, 0x54, 0x05, 0x54, 0x03, 0x11, 0x80, 0x3E, 0x02,
0x12, 0x12, 0x21, 0x01, 0x08, 0x11, 0xC2, 0x40, 0x04, 0x84, 0x04, 0x21, 0x11, 0x08, 0x6B, 0x00,
0x51, 0xE2, 0x01, 0x01, 0x00, 0x13, 0xC0, 0x47, 0xC4, 0x04, 0x44, 0x01, 0x11, 0x00, 0x09, 0x82,
0x10, 0x02, 0x21, 0x01, 0x08, 0x71, 0x82, 0x40, 0x04, 0x84, 0x04, 0x23, 0x01, 0x88, 0x0B, 0x00,
0x4F, 0xFC, 0x01, 0xFF, 0x00, 0xF0, 0x00, 0x3F, 0xF8, 0x05, 0x54, 0x01, 0x01, 0x00, 0x0E, 0x02,
0x0F, 0xFC, 0x20, 0xFE, 0x08, 0x60, 0x02, 0x1F, 0xF0, 0x84, 0x04, 0x20, 0xFE, 0x08, 0x0C, 0x00,
0x40, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02
};
Still there is one problem and I think it is a small error in code and I cannot detect it (because spend a couple days on it to think about how to get it some smaller). Maybe there is somebody that can point me into the right direction to solve the problem.
The problem
The problem occurs when there are allot of similarties, more than 255 repetitions of the same, such as many 0xFF repeating lines or 0x00 repeating empty spaces. In my code I take some precautions to avoid a byte overflow however it fails (and now cannot figure out why). What I try to do is when there is an overflow, record it and start allover again with counting. I cannot figure out it is a problem of the read function or just the write function.
This is the layout of storage
At start address:
-----------------
<byte width>
<byte heigth>
<uint16 dataSize>
<data>
<if data=0xFF>
<0xFF>
<repeat count>
</if>
<if data=0x00>
<0x00>
<repeat count>
</if>
<else data>
</data>
Here is my code:
uint16_t TOLEDdisplay::writeToEeprom( uint16_t iAddress )
{
if( width == 0 || height == 0 || cacheSize == 0 )
{ return 0; }
uint8_t iZeros = 0;
uint8_t iFFs = 0;
bool bIsZero = false;
bool bIsFF = false;
bool bZeroOverflow = false;
bool bFFOverflow = false;
uint16_t iBits = 0;
uint8_t* pByteSize = (uint8_t*)&iBits;
uint8_t iZeroCount = 0; // empty stripes , same pixels in a row
uint8_t iFFCount = 0; // filled stripes, same pixels in a row
// Write screen bounds, when read it back with readFromEeprom,
// this bounds must match with the current screen bounds.
EEPROM.write( iAddress++, width );
EEPROM.write( iAddress++, height );
// Reserve two bytes for stream size
uint16_t iSizeAddress = iAddress++;
++iAddress;
// Write the cache content to the EEPROM
uint16_t i = 0;
while( i < cacheSize )
{
iBits = getCacheRawBits( i );
//iBits = displayCache[ i ];
bIsFF = ( iBits == 0xFF );
bIsZero = ( iBits == 0x00 );
if( bIsFF && !bFFOverflow )
{ ++iFFs; }
bFFOverflow = (iFFs == 0xFF);
if( bIsZero && !bZeroOverflow )
{ ++iZeros; }
bZeroOverflow = (iZeros == 0xFF);
if( (!bIsFF && !bIsZero) || bFFOverflow || bZeroOverflow )
{
if( (!bIsFF && iFFs > 0) || bFFOverflow )
{
// Read function knows if there is a 0xFF, amount of 0xFF
// will be follow.
EEPROM.write( iAddress++, 0xFF );
// Write the amount of FF's
EEPROM.write( iAddress++, iFFs );
iFFCount+=iFFs;
// If there is no byte 'overflow' iFFs = 0, otherwise it is 1
iFFs = (uint8_t)bIsFF;
}
if( (!bIsZero && iZeros > 0) || bZeroOverflow )
{
// Read function knows if there is a zero, amount of zeros
// will be follow.
EEPROM.write( iAddress++, 0 );
// Write the amount of zero's
EEPROM.write( iAddress++, iZeros );
iZeroCount+=iZeros;
// If there is no byte 'overflow' iZeros = 0, otherwise it is 1
iZeros = (uint8_t)bIsZero;
}
// Avoid confusion writing a FF or zero
if( !bIsFF && !bIsZero )
{ EEPROM.write( iAddress++, iBits ); }
}
++i;
}
// Calculate stream size
iBits=iAddress-iSizeAddress-1;
// Write size of stream
EEPROM.write( iSizeAddress , *pByteSize++ );
EEPROM.write( iSizeAddress+1, *pByteSize );
Serial.print( "Zeros found: " );
Serial.println( iZeroCount );
Serial.print( "FF found: " );
Serial.println( iFFCount );
Serial.print( "SIZE: " );
Serial.println( iBits );
// return bytes written
return iBits+2;
}
bool TOLEDdisplay::readFromEeprom( uint16_t iAddress )
{
uint8_t bits = 0;
uint16_t i = 0;
uint8_t* pI = (uint8_t*)&i;
uint8_t iZeros = 0;
uint8_t iFFs = 0;
uint8_t iWidth = EEPROM.read( iAddress++ );
uint8_t iHeight = EEPROM.read( iAddress++ );
// Read stream size, read two bytes
*pI = EEPROM.read( iAddress++ );
*pI++;
*pI = EEPROM.read( iAddress++ );
// Clear the screen
clear();
Serial.print( "Size: " );
Serial.println( i );
Serial.print( "Width: " );
Serial.println( iWidth );
Serial.print( "Height: " );
Serial.println( iHeight );
// If an error (no image on EEPROM address) or screen bounds
// doesn't match, skip to continue
if( i == 0 || iWidth != width || iHeight != height )
{
update( true );
return false;
}
uint16_t iCacheAddress = 0;
while( i-- )
{
do {
if( iFFs == 0 && iZeros == 0 )
{
bits = EEPROM.read( iAddress++ );
if( bits == 0xFF )
{
// read amount of FF's minus this one
iFFs = EEPROM.read( iAddress++ )-1;
Serial.print( "iFFs: ");
Serial.println( iFFs );
}
else if( bits == 0x00 )
{
// read amount of zeros minus this one
iZeros = EEPROM.read( iAddress++ )-1;
Serial.print( "iZeros: ");
Serial.println( iZeros );
}
}
else {
if( iFFs > 0 )
{
--iFFs;
bits = 0xFF;
}
else if( iZeros > 0 )
{
--iZeros;
bits = 0x00;
}
}
setCacheRawBits( iCacheAddress, bits );
++iCacheAddress;
}
while( iFFs == 0 && iZeros == 0 );
}
update( true );
return true;
}
Any ideas?
NOTE:
I don't want to use any expensive compression method, 96% of program space is already in use and my method seems to work fine but with some error and I need to know the error, no alternative compression method. It has some compression already, bits in a byte to represent 8 pixels and just want to slim it down a bit (proven however with error at byte overflow).
Upvotes: 0
Views: 340
Answers (2)
Reputation: 6610
After some sleep I redone it with much better results and less code, I overcomplicated such thing too much.
I got impressive results with it and think about to refine it with an examination method to find the best 'compression' by selecting the bytes that repeats the most and record this into the EEPROM 'file'.
Anyway, this is my code, much better comparing to the first one, maybe it can help others. It is very lightweight solution to save some bytes.
For example a blank screen or full filled screen with a resolution of 128x32 pixels results in only 9 bytes, half by half only 17 bytes. The screen I showed in the question before 'compiles' to only 405 bytes, a saving of about 100 bytes.
Here is my renewed code:
uint8_t TOLEDdisplay::getCacheRawBits( uint16_t iAddress )
{
if( iAddress < cacheSize )
{ return displayCache[ iAddress ]; }
return 0x00;
}
bool TOLEDdisplay::setCacheRawBits( uint16_t iAddress, uint8_t iBitByte )
{
if( iAddress < cacheSize )
{
displayCache[ iAddress ]=iBitByte;
return true;
}
return false;
}
uint16_t TOLEDdisplay::writeToEeprom( uint16_t iAddress )
{
if( cacheSize == 0 || width == 0 || height == 0 )
{ return 0; }
uint8_t iBits; // Pixel * 8 = byte
uint8_t iFoundBits; // 'Type' of detected
uint16_t iByteSize = 0; // Total byte size of stream
uint8_t iCount = 0; // Count of repeats found
bool bSame; // Boolean to evaluate repeats
// Write screen bounds, when read it back with readFromEeprom,
// these bounds need to match with current screen bounds.
EEPROM.write( iAddress++, width );
EEPROM.write( iAddress++, height );
// Reserve two bytes for stream size
uint16_t iSizeAddress = iAddress;
iAddress+=2;
// Write the cache content to the EEPROM
uint16_t i = 0;
while( i < cacheSize )
{
// Get a byte with bits
iBits = getCacheRawBits( i );
++i;
// Find repeating lines or empty lines
if( iBits == 0xFF || iBits == 0x00 )
{
iFoundBits = iBits; // Set found bits to detect changes
bSame = true; // Set to true to able to start loop
iCount=1; // Count this found one
// Loop to find duplicates
while( bSame && ( iCount < 0xFF ) && ( i < cacheSize ))
{
iBits = getCacheRawBits( i ); // Get next byte with bits
bSame = (iBits == iFoundBits); // Determine is repeat, the same
iCount+=bSame; // Increment count when same is found
i+=bSame;
}
// Finally write result to EEPROM
EEPROM.write( iAddress++, iFoundBits ); // type
// Write the amount
EEPROM.write( iAddress++, iCount ); // count
// Goto main loop and find next if any
}
else {
// Write found value normally to EEPROM
EEPROM.write( iAddress++, iBits );
}
}
// Final EOF address is one pos back
--iAddress;
// Calculate stream size
iByteSize=iAddress-iSizeAddress;
uint8_t* pByteSize = (uint8_t*)&iByteSize;
// Write size of stream
EEPROM.write( iSizeAddress , *pByteSize++ );
EEPROM.write( iSizeAddress+1, *pByteSize );
// return bytes written including width and height bytes (+2 bytes)
return iByteSize+2;
}
bool TOLEDdisplay::readFromEeprom( uint16_t iAddress )
{
uint8_t iBits;
uint8_t iRepeats;
uint16_t i = 0;
uint8_t* pI = (uint8_t*)&i;
uint8_t iWidth = EEPROM.read( iAddress++ );
uint8_t iHeight = EEPROM.read( iAddress++ );
// Read stream size, read two bytes
*pI = EEPROM.read( iAddress++ );
*pI++;
*pI = EEPROM.read( iAddress++ );
// Clear the screen
clear();
// If an error (no image on EEPROM address) or screen bounds
// doesn't match, skip to continue
if( i == 0 || iWidth != width || iHeight != height )
{
update( true ); // Set screen to blank
return false;
}
uint16_t iCacheAddress = 0;
while( i-- )
{
// Get a byte with bits
iBits = EEPROM.read( iAddress++ );
// Explode repeats if detected
if( iBits == 0xFF || iBits == 0x00 )
{
// read amount of repeats
iRepeats = EEPROM.read( iAddress++ );
// Explode it into cache
while( iRepeats-- )
{ setCacheRawBits( iCacheAddress++, iBits ); }
}
else {
// Put value normally into cache
setCacheRawBits( iCacheAddress++, iBits );
}
}
// Done, update the screen
update( true );
// Return success
return true;
}
Maybe I have to add some EEPROM boundry checks but for now it works fine.
Upvotes: 0
Reputation: 32732
The first time thru the loop, bFFOverflow and bZeroOverflow are accessed without having been initialized.
The main problem, though, is that after you record your 255 0 or 0xFF bytes, you set the count to 1 if there are more. However, this should be zero, since you detect the overflow after you've counted the 255th copy of that byte.
So always set bFFOverflow and bZeroOverflow to 0 writing out the counts.
Upvotes: 2
Related Questions
- Arduino: Lightweight compression algorithm to store data in EEPROM
- Efficient design for multiple pixel operations when decompressing an image
- Save exr/pfm as little endian
- Save exr/pfm to bitmap CImg
- How to save compressed pixels (compressed with my own encoder) back into DICOM image file using Imebra library?
- How to compress an image with JPEG or PNG in C# in-memory?
- Compressing a raw image buffer
- Compressing a bitmap with Run Length Encoding [RLE] using GDI+
- Compress image in .NET
- Saving image without compressing