How is a 41KB char array filling up 256KB of program memory?

Question

I have an array of 41,400 elements of type char, which I am trying to put in program memory on a Mega2560. It should have 256KB of flash memory, but when I try to compile my sketch, it says the size of the array is too large. Each char is one byte, so this array should be 41,400 bytes. I'm at a loss as to how this can be too big.

I have also tried using an array of byte variables (should be the same thing) with no success. This is the only variable going into program memory.

Here is the relevant line:

const char Array[] PROGMEM = {0,19,21,25,27,27,27,29,24, ... };

I have included avr/pgmspace.h

Thanks in advance for any help.

Answer 1

The limitation here is the data type of the index of the array. That is int, and on an 8-bit system an int can hold a value in the range -32768 to 32767.

That means the biggest index number an array can have is 32767.

That limit cannot be changed. You're stuck with it.

However, there are some tricks you can use to expand it. One is to use a larger data type than char and pack your data into it. For instance, using unsigned int as your data type will give you a maximum of 32767 16-bit values. Each one can hold two bytes. That gives you a total capacity of 65534 bytes.

Using unsigned long (32 bits) would double that again.

It is then up to you to work out how to get to the individual bytes. Using the pgm_read_byte_*() function you may not see any difference. After all the start address is just an address regardless of type. Of course, you have to watch out for any differences in endianness when you have packed your initial data into the array...

Answer 2

You cannot have more than 32767 elements in one array. The reason is explained nicely by Majenko.

Solution for your problem is very simple, because you need only 41400 elements:

class MyArray
{
  static char array1[30000] = {...};
  static char array2[11400] = {...}; // rest

  public:
    char get(long index)
    {
      return index > 30000 ? array2[index - 30000] : array1[index];
    }

    char operator[] (long index)
    {
      return get(index);
    }
};

So you can use two arrays and depending of the index choose which one to use. I think it is faster than using array of ints, because you need to have division (by two, so it can be only shift right by one) and than again shifting to get the char. Also it is easier to use because for ints you need first to pack values (two values in one int).

This is just example code, fit it to your needs.