Most space efficient way to store 5x7 dot matrix image data? [using ATtiny]

[Holmes34]

So I'm working on a small (tiny) robot which will include a 5x7 single colour dot matrix. I will be controlling the dot matrix using an ATtiny microcontroller, and with two shift registers (1 for cathode, 1 for anode). I want to store around 8 separate images to display on the dot matrix.

I am trying to push the size limits of the microcontroller memory.

I initially though I could store each column of 7 pixels as part of a byte, which would lead to 1 array of 5bytes. I would shift these bytes into the 8bit shift register and discard either the leading or trailing bit:

Code: [Select]

IMAGE[] = {
    0,
    62,
    42,
    62,
    0
}
However this seems to be far from optimised with respect to memory size. Certainly discarding the extra bit feels wasteful as it accounts for 1/8th of total bits in the image memory. Obviously this is partly due to the awkward matrix size, so I probably can't do a whole lot with those wasted bits.

Are there any good programmatic ways of reducing the memory burden of these types of matrices?

I've thought a little about using a starting byte for each image to indicate any symmetry present in the image, which would allow some parts of some images to be omitted, but I'm unsure if this would help or harm the overall program+image memory size, as it would take some significant functions to sort and transform the reduced representations.

Any advice or suggestions would be much appreciated!

[mikeselectricstuff]

If you only have 8 images, that's 40 bytes using 1 byte per column. To get any advantage, the code to store more efficiently would need to be less than 5 bytes long ( or 15 bytes if you have RGB images).
You might be able to make use of the extra bit, e.g. as an end of digit marker so you don't have to count the 5 columns, which may save a few bytes of code.
 

[nctnico]

C supports structs in which the elements can use an arbitrary number of bits:
See: https://www.tutorialspoint.com/cprogramming/c_bit_fields.htm

Code: [Select]

struct {
   unsigned int widthValidated : 1;
   unsigned int heightValidated : 1;
} status;


[mikeselectricstuff]

C supports structs in which the elements can use an arbitrary number of bits:
See: https://www.tutorialspoint.com/cprogramming/c_bit_fields.htm

Code: [Select]

struct {
   unsigned int widthValidated : 1;
   unsigned int heightValidated : 1;
} status;


I suspect the chances of this being implemented efficiently enough to save space overall are minimal, but it's easy  enough to try.

[dannyf]

Depends on your design requirement. If you want speed, 5 bytes would be the best.

If you are short for space, compress the image first.

[dgtl]

For larger amounts of image data, some simpler compression would help to save space, even just some derivate of RLE or PackBits. To be useful, the decompression code should be smaller than the space savings gained, so for so little amount of image data (40B), any encoding would not make sense. Usually you want each image to start on a byte boundary and then some kind of index pointing to the beginning of each image, this will eat away any small gains.
So unless you need to encode the whole alphabet, you can't go considerably smaller so that it would be worth.

[alank2]

Be aware that normal structures will take up precious SRAM and be stored in FLASH.  If you use the pgmspace.h include and PROGMEM along with eeprom_read_byte or related functions you can avoid the SRAM waste.

[sleemanj]

As with others, I think there's no point trying to avoid losing that 1 bit per column, the complexity in doing so is going to easily outweigh any advantage.

Another poster has reminded you about using PROGMEM, but I would also add, don't forget you also probably have some eeprom you can use for data storage if you like, like PROGMEM and pgm_read_[whatever] you can use EEMEM and eeprom_read_[whatever] - of course you have to program the eeprom, the compilation process will produce an .eep file (or is it .ee, something like that) with the appropriate initialisation data which you can pass into avrdude to do so.


 

[stj]

i would just use 5 bytes,
the 8th bit could be used to indicate display duration or be used to change the display brightness etc and the loss of those 5bytes is going to be far less than the extra space needed for clever decompression or display code.

[Holmes34]

Thank you all for your suggestions and explanations!

As I suspected there isn't much I can do with the extra bit except possibly finding a use for it like stj mentions.

Thanks to dgtl and blueskull for the pointer to RLE, its something I haven't heard about before, however I don't think my 5x7 images have sufficient "runs" to make good use of it. I will definitely keep it in mind for the future!

I also will take the advice of sleemanj and alank2, and use EEPROM as I don't need to actively change these images after they're written into memory, just read.

I have decided on the attached images (ignore the last two "frames"), and as can be seen I have 2 pairs of images that are simply reflections of each other. I am going to try and organise my code to replace 1 of each pair, and just load the appropriate shift register (column or row) "backwards", but I'll have to see if I can do this is 10 bytes or less of code as has been mentioned in this thread.

Thanks for all the help!

[newbrain]

I have decided on the attached images (ignore the last two "frames"), and as can be seen I have 2 pairs of images that are simply reflections of each other.

There's some simple optimization that can save you some storage bytes.
They only work because of the properties of the images you selected.

The first is very simple, and will just save you 6 bytes of storage, at no additional code cost:
if the images are stored as a contiguous array, using offset constants to address the start of each one, you can overlap the common bytes of each one with the one following.
So, the 1st will overlap the 2nd by one byte, and so on until the 6th overlapping the 7th.
Nothing to do for the 7th and the 8th  .

Edit: Added an image (worth a thousand words six bytes). In red the start and in blue the end of each pattern.

The other optimization can save you 12 bytes of storage, but at the cost of some more code, so you have to evaluate if that's worth the effort:
all the images with the exception of the 2nd and 3rd ones have horizontal symmetry.
If the 5 bytes are read in loop, then you could count up from 0 to 2 and then back to 0 and pare the the 2nd half (last two bytes, actually) of each symmetrical image.
But the code to differentiate the symmetric images from the non symmetric ones might end up costing more, even if you encode the information in the spare bit.

[zapta]

IMAGE[] = {
    0,
    62,
    42,
    62,
    0
}

Make sure that the consts you define don't consume RAM space, just ROM/Flash space. IIRC, with gcc-avr, some consts are also replicated in RAM to simplify the addressing.

[Holmes34]

IMAGE[] = {
    0,
    62,
    42,
    62,
    0
}

Make sure that the consts you define don't consume RAM space, just ROM/Flash space. IIRC, with gcc-avr, some consts are also replicated in RAM to simplify the addressing.

Thanks for the tip, I'll make sure to double check in case this happens.

[mariush]

With those particular bitmaps you have something interesting:

First two pixels and last two pixels are always white, so you can use only 8 bits to define the first two rows and the last two rows. 
Think of it like spliting those images in three sections, top middle and bottom. 
You'll have this for the top

00100
01110
and since you can ignore the first two bits, you end up with 10001110

and you have this at the bottom

01110
00100

and since you can ignore the last two bits because they're always 0, you end up with 01110001 which is exactly the first byte in reverse but if you look again, it's also the "negative" of the first byte.
So basically for the first three shapes the first two and last two rows can be generated using just one byte constant. For the 4th to last shapes, depending on form you'd have to do a XOR or something with another byte to get the desired 8 bits.

Now you're left with the middle three rows ... easiest way would be to just use 2 bytes (16 bits) for each digit, but we could further analyze the pictures, let's write for the first 5 pictures the bits in a row (15 bits) and I'm going to add a 0 to pad everything to 16 bits

1101110001110110
1110111000111010
1011100011101110
1000111011111110
1111111011100010

You may notice a pattern in the bits .. let's arrange them a bit and let's allow the last bit to be any value because we'll ignore it anyway.

11011100 01110110 =
11101110 00111011 = 128 + b1 shifted to right 1 digit   , b2 shifted to right
10111000 11101110 = 128 + b1 shifted to left by 1 digits , b2 shifted to left 1 digit +2
10001110 11111110 = 128 + (b1 -192) shifted one digit to right  , b2 + 9 shifted to the left 1 digit
11111110 11100010 = 128  + (b1 + 32) shifted one digit to right , b2 shifted one digit to left - 9

and for shapes 6 and 7 you can figure things out just as well.

So it's up to you to figure out how many bytes of code those shift add substract instructions would add up versus just storing 2 bytes for each of the three middle rows.

[stj]

if im reading this right, your not using a static display, it has to be continuously strobed.
so you need the image in decompressed form in flash or ram anyway for the display servicing routine.

[zapta]

if im reading this right, your not using a static display, it has to be continuously strobed.
so you need the image in decompressed form in flash or ram anyway for the display servicing routine.

Potentially it can be decompressed on the fly as part of the scanning.

[obiwanjacobi]

I would use PROG_MEM and just store them as simple as possible.
You should be able to read directly from flash memory and output each byte to the display directly. Should only need 1 or 2 RAM bytes...

[newbrain]

I would use PROG_MEM and just store them as simple as possible.
You should be able to read directly from flash memory and output each byte to the display directly. Should only need 1 or 2 RAM bytes...

Definitely this.
I'm quite sure that any "smart" solution in storage will be outweighed by the size of the code needed to decompress it, as we're talking about a very small dataset.
That is the reason I've proposed something with 0 additional code cost, valid of course only for the data at hand.

[Someone]

I would use PROG_MEM and just store them as simple as possible.
You should be able to read directly from flash memory and output each byte to the display directly. Should only need 1 or 2 RAM bytes...

PROGMEM isn't entirely simple:
http://www.atmel.com/webdoc/AVRLibcReferenceManual/pgmspace_1pgmspace_data.html
Some other compilers abstract it away and you don't need to think about it, pushing constants to flash as appropriate. There is a loss of speed accessing data from program space so having the compiler push all it can into ram/registers isn't a bad thing.

[obiwanjacobi]

I would use PROG_MEM and just store them as simple as possible.
You should be able to read directly from flash memory and output each byte to the display directly. Should only need 1 or 2 RAM bytes...

PROGMEM isn't entirely simple:
http://www.atmel.com/webdoc/AVRLibcReferenceManual/pgmspace_1pgmspace_data.html
Some other compilers abstract it away and you don't need to think about it, pushing constants to flash as appropriate. There is a loss of speed accessing data from program space so having the compiler push all it can into ram/registers isn't a bad thing.

If its fast enough for the display, then there is no problem. Simply test it. Otherwise take the pain...

Here is my take on a PROG_MEM array, but its not for the faint-hearted... 

[Bruce Abbott]

I am trying to push the size limits of the microcontroller memory.

Then you should be coding in assembly language.

[Holmes34]

There's some simple optimization that can save you some storage bytes.
They only work because of the properties of the images you selected.

The first is very simple, and will just save you 6 bytes of storage, at no additional code cost:
if the images are stored as a contiguous array, using offset constants to address the start of each one, you can overlap the common bytes of each one with the one following.
So, the 1st will overlap the 2nd by one byte, and so on until the 6th overlapping the 7th.
Nothing to do for the 7th and the 8th  .

Edit: Added an image (worth a thousand words six bytes). In red the start and in blue the end of each pattern.

The other optimization can save you 12 bytes of storage, but at the cost of some more code, so you have to evaluate if that's worth the effort:
all the images with the exception of the 2nd and 3rd ones have horizontal symmetry.
If the 5 bytes are read in loop, then you could count up from 0 to 2 and then back to 0 and pare the the 2nd half (last two bytes, actually) of each symmetrical image.
But the code to differentiate the symmetric images from the non symmetric ones might end up costing more, even if you encode the information in the spare bit.

That's genius! It just goes to show I wasn't exactly thinking outside of the box the black lines.

The contiguous array should definitely save me those extra bytes! I also noticed that if I move Image 1 to share both of its edges and leave Image 2 at the start I'll be able to share/save another byte. 7 FREE BYTES!

Your mention of looping made me realise that I will be repeating the same byte in many cases with these images. One possible way to take advantage of this is to use the extra bit in each byte signify whether the byte should be passed to the shift register once or twice. I'm not sure if there is an efficient way of doing this, and unfortunately this method seems to clash with the contiguous array, as I can't take advantage of doubled-bytes in many images whilst still having a consistent loop from column 0-4 in each image.

Hopefully double-bytes can save me 4 bytes (from Image 6,7, and 2 from 8 ), so I'll have to see how big the code modification to interpret the extra bit will be. It should just be a simple conditional so I think it will be worth.

Thanks for the fruitful ideas!

With those particular bitmaps you have something interesting:

First two pixels and last two pixels are always white, so you can use only 8 bits to define the first two rows and the last two rows. 
Think of it like spliting those images in three sections, top middle and bottom. 
You'll have this for the top

00100
01110
and since you can ignore the first two bits, you end up with 10001110

and you have this at the bottom

01110
00100

and since you can ignore the last two bits because they're always 0, you end up with 01110001 which is exactly the first byte in reverse but if you look again, it's also the "negative" of the first byte.
So basically for the first three shapes the first two and last two rows can be generated using just one byte constant. For the 4th to last shapes, depending on form you'd have to do a XOR or something with another byte to get the desired 8 bits.

Wow this post was super interesting! I'm going to look into these binary operations more as I confess I am generally baffled often by binary. Your explanation was great though! Thanks!

[Holmes34]

I would use PROG_MEM and just store them as simple as possible.
You should be able to read directly from flash memory and output each byte to the display directly. Should only need 1 or 2 RAM bytes...

PROGMEM isn't entirely simple:
http://www.atmel.com/webdoc/AVRLibcReferenceManual/pgmspace_1pgmspace_data.html
Some other compilers abstract it away and you don't need to think about it, pushing constants to flash as appropriate. There is a loss of speed accessing data from program space so having the compiler push all it can into ram/registers isn't a bad thing.

If its fast enough for the display, then there is no problem. Simply test it. Otherwise take the pain...

Here is my take on a PROG_MEM array, but its not for the faint-hearted... 

I'll aim for 50Hz refresh rate (crappy old tv refresh rate), so each frame needs to be once every 20ms, each column needs to be read and sent in max 4ms. I can't find a specific read time for EEPROM in the ATtiny13 datasheet, but write speeds are as low as 1.8ms, it's probable that read speeds are similar if not better. Therefore I'd assume I'll be cutting it close. (especially if I'm using a conditional check on the byte as per my last post in this thread).

All my parts have arrived in the post so I'll hook everything up, finish up the code and see what happens. Will post results in a week or so.

Thanks for everyone's advice!

[mikeselectricstuff]

I would use PROG_MEM and just store them as simple as possible.
You should be able to read directly from flash memory and output each byte to the display directly. Should only need 1 or 2 RAM bytes...

PROGMEM isn't entirely simple:
http://www.atmel.com/webdoc/AVRLibcReferenceManual/pgmspace_1pgmspace_data.html
Some other compilers abstract it away and you don't need to think about it, pushing constants to flash as appropriate. There is a loss of speed accessing data from program space so having the compiler push all it can into ram/registers isn't a bad thing.

If its fast enough for the display, then there is no problem. Simply test it. Otherwise take the pain...

Here is my take on a PROG_MEM array, but its not for the faint-hearted... 

I'll aim for 50Hz refresh rate (crappy old tv refresh rate), so each frame needs to be once every 20ms, each column needs to be read and sent in max 4ms. I can't find a specific read time for EEPROM in the ATtiny13 datasheet, but write speeds are as low as 1.8ms, it's probable that read speeds are similar if not better. Therefore I'd assume I'll be cutting it close. (especially if I'm using a conditional check on the byte as per my last post in this thread).

All my parts have arrived in the post so I'll hook everything up, finish up the code and see what happens. Will post results in a week or so.

Thanks for everyone's advice!

EEPROM read speeds are only a few cycles- nowhere near as slow as writes

[obiwanjacobi]

I would use PROG_MEM and just store them as simple as possible.
You should be able to read directly from flash memory and output each byte to the display directly. Should only need 1 or 2 RAM bytes...

PROGMEM isn't entirely simple:
http://www.atmel.com/webdoc/AVRLibcReferenceManual/pgmspace_1pgmspace_data.html
Some other compilers abstract it away and you don't need to think about it, pushing constants to flash as appropriate. There is a loss of speed accessing data from program space so having the compiler push all it can into ram/registers isn't a bad thing.

If its fast enough for the display, then there is no problem. Simply test it. Otherwise take the pain...

Here is my take on a PROG_MEM array, but its not for the faint-hearted... 

I'll aim for 50Hz refresh rate (crappy old tv refresh rate), so each frame needs to be once every 20ms, each column needs to be read and sent in max 4ms. I can't find a specific read time for EEPROM in the ATtiny13 datasheet, but write speeds are as low as 1.8ms, it's probable that read speeds are similar if not better. Therefore I'd assume I'll be cutting it close. (especially if I'm using a conditional check on the byte as per my last post in this thread).

All my parts have arrived in the post so I'll hook everything up, finish up the code and see what happens. Will post results in a week or so.

Thanks for everyone's advice!

EEPROM read speeds are only a few cycles- nowhere near as slow as writes

Just to be clear: PROG_MEM puts data into flash, not EEPROM. Of course, EEPROM is also a nice place to stuff that stuff in. Takes a little extra effort programming, but works.