5

I have just gone through all my code. At max I use 60 bytes. I have done everything in order to minimize its usage - I even store booleans as bits, not bytes! What could be happening here?

The only thing that comes to my mind are extremely large arrays, like this:

const uint8_t SBoxes[8][4][16] PROGMEM;

However, these are stored in the program memory as you can see. How can I check they are really there and my memory usage? My code is too large to post it here.

EDIT:

IDE tells me (even though I believe it's very inaccurate):

Sketch uses 7,898 bytes (24%) of program storage space. Maximum is 32,256 bytes. Global variables use 1,023 bytes (49%) of dynamic memory, leaving 1,025 bytes for local variables. Maximum is 2,048 bytes.

All my literal strings use F() and there are not many of them.

EDIT2:

Code on pastebin. Just for a quick glance, it is really large.

EDIT3:

My Serial prints

ready
some numbers (that's ok I ask it to print out an array)
ENready
again numburs
Enready
...

I ask it to print ready at the very beginning of my program. I ask it to println End of encr near the end of my setup funciton, but as you see it never finishes the printing.

It always behaves like that when I run out of SRAM.

  • What does the IDE say how much space was used? – Avamander Feb 10 '16 at 19:03
  • Please post the data declarations. Check that all literal strings use F(). – Mikael Patel Feb 10 '16 at 19:06
  • I updated my question. Please, see the EDIT. – SlowerPhoton Feb 10 '16 at 19:10
  • What does avr-nm -Crtd --size-sort your_elf_file tell you? Look at symbols of type D, B and V. – Edgar Bonet Feb 10 '16 at 19:23
  • On what kind of file should I call it? All I have are .ino files. And it doesn't take my project file as an argument. It tells me it 'is not an ordinary file'. – SlowerPhoton Feb 10 '16 at 19:30
6

When you are asking yourself what is eating so much RAM, the first step is to look at the symbol table in the ELF file. If you use a makefile, you probably know where to find the ELF file. If you are using the Arduino IDE, go to File / Preferences, check “Show verbose output during compilation”, compile and look at the output: you will see the temporary directory where the compiler puts your ELF file.

Now run the command avr-nm -Crtd --size-sort your_elf_file and look for symbols of type 'D' (data), 'V' (vtable) and 'B' (BSS), in either upper or lower case. On a Unix-style OS you would pipe through grep -i ' [dbv] '. Running this on your program gives:

00000068 B tx_buffer
00000068 B rx_buffer
00000034 B Serial
00000021 B lcd
00000016 V vtable for HardwareSerial
00000008 V vtable for LiquidCrystal
00000004 B timer0_overflow_count
00000004 B timer0_millis
00000002 D __malloc_margin
00000002 D __malloc_heap_start
00000002 D __malloc_heap_end
00000002 B __flp
00000002 B __brkval
00000001 b timer0_fract
00000001 D encr
00000001 B debug
00000001 B EEPROM

Obviously, this cannot account for the 1,023 bytes of static RAM your program is using. What this command misses is the literal arrays and strings. These can be seen with the command avr-objdump -j .data -s your_elf_file. The literal strings are quite obvious in the output, the literal arrays less so. Running this on your program gives a long listing starting with

Contents of section .data:
800100 00000005 2000010e 040d0102 0f0b0803  .... ...........
800110 0a060c05 09000700 0f07040e 020d010a  ................

Now, on the source code we see:

const uint8_t SBoxes[8][4][16] PROGMEM = {
{{14,  4,  13,  1,   2, 15,  11,  8,   3, 10,   6, 12,   5,  9,   0,  7},
 { 0, 15,   7,  4,  14,  2,  13,  1,  10,  6,  12, 11,   9,  5,   3,  8},
 { 4,  1,  14,  8,  13,  6,   2, 11,  15, 12,   9,  7,   3, 10,   5,  0},
 {15, 12,   8,  2,   4,  9,   1,  7,   5, 11,   3, 14,  10,  0,   6, 13} },
 ...

If you translate this to hexadecimal, you get 0e 04 0d 01 02 0f..., which appears also by the end of the first line of previous listing. So there is your culprit: all the big PROGMEM arrays. The compiler does not honor the PROGMEM attribute on local variables.

My first thought was to make the arrays global, and this does solve the problem. However, as pointed out by Mikael Patel in a comment, the documentation on PROGMEM states that “variables must be either globally defined, OR defined with the static keyword, in order to work with PROGMEM.” Then, making the arrays static const PROGMEM is a cleaner solution.

  • 1
    It can't. It doesn't make sense to. – Nick Gammon Feb 10 '16 at 19:49
  • 1
    I tested simply defining them as "static" where they stand and data size drops to 311 bytes. – Mikael Patel Feb 10 '16 at 19:54
  • I tried to take them out of the functions to make them global. To make sure the library works I called the input rigth above the arrays. As you can see the IDE says something different (Sketch uses 7,788 bytes (24%) of program storage space. Maximum is 32,256 bytes. Global variables use 399 bytes (19%) of dynamic memory, leaving 1,649 bytes for local variables. Maximum is 2,048 bytes.). But it is still out of SRAM - the program loops its Serial the same way as before. – SlowerPhoton Feb 10 '16 at 19:57
  • 1
    There is actually a line in the Arduino PROGMEM documentation about this "Please note that variables must be either globally defined, OR defined with the static keyword, in order to work with PROGMEM." arduino.cc/en/Reference/PROGMEM – Mikael Patel Feb 10 '16 at 20:01
  • But it is still out of SRAM - the program loops its Serial the same way as before. - let's not jump to conclusions now. What do you mean "loops its Serial" exactly? – Nick Gammon Feb 10 '16 at 20:10
4

To elaborate on Edgar Bonet's answer and my comment under it, you cannot usefully put PROGMEM variables as local variables because local (non-static) variables have to be allocated on the stack.

void lookUpInSBox(size_t which, byte *address, byte* binaryOutcome, size_t addressFrom){

   ...

    const uint8_t SBoxes[8][4][16] PROGMEM = {

                             /*S1*/

   { {14,  4,  13,  1,   2, 15,  11,  8,   3, 10,   6, 12,   5,  9,   0,  7},
     { 0, 15,   7,  4,  14,  2,  13,  1,  10,  6,  12, 11,   9,  5,   3,  8},
     { 4,  1,  14,  8,  13,  6,   2, 11,  15, 12,   9,  7,   3, 10,   5,  0},
     {15, 12,   8,  2,   4,  9,   1,  7,   5, 11,   3, 14,  10,  0,   6, 13}    },

You could make them global. But if you prefer not to do that, put static in front of them. Doing that on your code reduced it to 247 bytes.

Global variables use 247 bytes (12%) of dynamic memory, leaving 1,801 bytes for local variables. Maximum is 2,048 bytes.

You expect a bit more than the 60 you counted. The serial buffers take a bit (128 bytes).

See Putting constant data into program memory (PROGMEM) for more information. On a tiny sketch I found the following 346 bytes already in use:

  • 34 bytes for the HardwareSerial instance (Serial)
  • 64 bytes for the Serial transmit buffer
  • 64 bytes for the Serial receive buffer
  • 4 bytes for the Serial transmit buffer head and tail pointers
  • 4 bytes for the Serial receive buffer head and tail pointers
  • 9 bytes for keeping track of millis / micros
  • 4 bytes for memory allocation (__malloc_heap_start, __malloc_margin)
  • 128 bytes for the heap safety margin
  • 6 bytes for a few nested function calls (main -> setup -> getFreeMemory)
  • 16 bytes for the compiler vtable for HardwareSerial
  • 4 bytes for variables __brkval and __flp (used in memdebug)
  • 2 bytes pushed onto the stack in main (to save registers)
  • 2 bytes pushed onto the stack in setup (to save registers)
  • 4 bytes pushed onto the stack in getFreeMemory (to save registers)
  • 1 byte because the stack pointer starts at 0x8FF rather than 0x900

The sketch on my page used dynamic memory allocation so it used a bit more than yours does (for keeping track of it).


Once it starts printing gibberish or looping (that means it prints something and starts again from the beginning of the program) I know I have run out of SRAM

I'm a bit puzzled by all the new/delete you are doing. Why do that? For example:

byte *E;
E = new byte[48/8];  
for(size_t i = 0; i < 48; i++){
    insertBit( E, i, bitValue( R, E_BIT[i]-1 ) );
}

// XOR Kn and  E(Rn-1)
byte KxorE[48/8]; 
for (size_t i = 0; i < 48; i++){
    insertBit( KxorE, i, bitValue( K, i ) ^ bitValue( E, i ) );
}
delete[] E;

Massive amounts of dynamic memory allocation may fragment memory. Can't you rewrite to not do that? You can pass arrays by reference, it just seems weird (and slow) to do all that allocation.

  • You mean like const uint8_t SBoxes[8][4][16] PROGMEM? I have tried it and although the IDE lowered the numbers of memory usage, the program still loops its Serial input - it is still out of SRAM :( Even if I add your additional bytes to my numbers we get nowhere near 2000. – SlowerPhoton Feb 10 '16 at 20:07
  • I don't understand that. Therefore it is not out of SRAM, unless you dynamically allocate memory a lot. See my comment under Edgar Bonet's answer. – Nick Gammon Feb 10 '16 at 20:13
  • See my amended answer about dynamic allocation. – Nick Gammon Feb 10 '16 at 20:32
  • I need both of the E and KxorE arrays. What I can do is not to delete them, but not much more. Originally I was worried about the SRAM so I deleted everything I could. Of course I am going to optimalize its speed, but only when it runs. But thank you for that tip, I didn't know memory allocation would be that slow. – SlowerPhoton Feb 10 '16 at 20:37
  • 1
    If you redesign to not use dynamic memory, at least you know that once you have enough memory at the start, you won't use any more of it. – Nick Gammon Feb 10 '16 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.