Go Down

Topic: Can I save any SRAM memory in my program? (Read 657 times) previous topic - next topic

pan19ss

May 26, 2019, 05:51 am Last Edit: May 26, 2019, 05:58 am by pan19ss
Title says it all.. My following program is doing SHA256 hashing recursively (i.e. hashes the output of a hash etc.). The main idea is that it produces 2n series of hashes (n is denoted "SIGMA" in my program) and it needs n SHA256 strings. It works fine up to n=10 but it uses 70% SRAM, if I increase it to n=11 then the program does not output correct values (probably because it uses too much SRAM). For n=12 it displays warning about memory and does not run at all.

My main approach to save memory is to keep the initial parameters to PROGMEM (lines 16-23) and convert them to byte arrays and back to char arrays in the program (the hash function needs a string as input). However I cannot find any way to save more memory. My device is Uno (and I specifically want to run my program on this particular device only).

Any suggestions? Library used: https://github.com/rweather/arduinolibs/tree/master/libraries/Crypto

Program with n=10:
Code: [Select]
#include <Crypto.h>
#include <SHA256.h>
#include <string.h>

#define HASH_SIZE 32
#define BLOCK_SIZE 64
#define OUTPUT_MAX 32
#include <limits.h> //for infinity

const unsigned int SIGMA = 10;

char hex[256];
SHA256 hash;
byte bytearray_buffer[32];

const static char* const initpebbles[] PROGMEM = {
"ef92dd53c32ceaba5db5f0a2d697cfb29b4ff250e289a5711840d40504792cda", "72d1dc06087553c571f52f057d401f9b55cce4e6b4daf531e1dfb7a6d1677989",
"39444ff9e95ed61191a477b6925215d5f3fa3e6996905e2c6b1be60d3a54673b", "b2451c6bffdd03bacd10991d59d1230909638401dc1a925de19e23caafa81824",
"2b9ce5954a44bd6e8e2fa01ddba0cf4432f5d72073c5651410e3c504cb870c27", "5acc1b260b286d203376ec75f11a97e644daad765d8b96a235e6d6e6e1f4048b",
"da205ac2f1d5a4b2029af45c6e6cbba6a21245f5b7cf6896bccd8197ab36545c", "9fabcd1fbee85dd1cb27053846ce08cf2e554351206e2a652f227c1a9d7bd13b",
"857958d158f08f168d0dad7d1bcbd5911dd2059bb5d30ec994bd9ed8fe888a93", "a665a45920422f9d417e4867efdc4fb8a04a1f3fff1fa07e998e86f7f7a27ae3"

};

char *btoh(char *dest, uint8_t *src, int len) {
  char *d = dest;
  while( len-- ) sprintf(d, "%02x", (unsigned char)*src++), d += 2;
  return dest;
}


char* h(char* input) {   

uint8_t result[32];
hash.reset();
hash.update(input, strlen(input));
hash.finalize(result, sizeof(result));

  return(btoh(hex, result, 32));
}

void hexCharacterStringToBytes(byte *byteArray, char *hexString)
{
  bool oddLength = strlen(hexString) & 1;

  byte currentByte = 0;
  byte byteIndex = 0;

  for (byte charIndex = 0; charIndex < strlen(hexString); charIndex++)
  {
    bool oddCharIndex = charIndex & 1;

    if (oddLength)
    {
      // If the length is odd
      if (oddCharIndex)
      {
        // odd characters go in high nibble
        currentByte = nibble(hexString[charIndex]) << 4;
      }
      else
      {
        // Even characters go into low nibble
        currentByte |= nibble(hexString[charIndex]);
        byteArray[byteIndex++] = currentByte;
        currentByte = 0;
      }
    }
    else
    {
      // If the length is even
      if (!oddCharIndex)
      {
        // Odd characters go into the high nibble
        currentByte = nibble(hexString[charIndex]) << 4;
      }
      else
      {
        // Odd characters go into low nibble
        currentByte |= nibble(hexString[charIndex]);
        byteArray[byteIndex++] = currentByte;
        currentByte = 0;
      }
    }
  }
}

byte nibble(char c)
{
  if (c >= '0' && c <= '9')
    return c - '0';

  if (c >= 'a' && c <= 'f')
    return c - 'a' + 10;

  if (c >= 'A' && c <= 'F')
    return c - 'A' + 10;

  return 0;  // Not a valid hexadecimal character
}

void array_to_string(byte array[], unsigned int len, char buffer[])
{
    for (unsigned int i = 0; i < len; i++)
    {
        byte nib1 = (array[i] >> 4) & 0x0F;
        byte nib2 = (array[i] >> 0) & 0x0F;
        buffer[i*2+0] = nib1  < 0xA ? '0' + nib1  : 'a' + nib1  - 0xA;
        buffer[i*2+1] = nib2  < 0xA ? '0' + nib2  : 'a' + nib2  - 0xA;
    }
    buffer[len*2] = '\0';
}


//Pebble code


//Stop function
void stop()
{
 while(1);
}

typedef struct Pebble{
  int StartIncr;
  int DestIncr;
  int position;
  int destination;
  byte value[32];
};

void FindValue(struct Pebble pebble_List[])
{
  for (int i = 1; i < SIGMA; i++)
  {
        if (pebble_List[i].position == pebble_List[0].position) {
            for (int j=0; j < 32; j++) {
              bytearray_buffer[j] = pebble_List[i].value[j];
                  }

  }
}
}

int struct_cmp_by_destin(const void *a, const void *b)
{
    struct Pebble *ia = (struct Pebble *)a;
    struct Pebble *ib = (struct Pebble *)b;
    return (ia->destination - ib->destination);
}


unsigned int Pow2(byte ex)
{
   return 1 << ex;
}

int x2i(char *s)
{
 int x = 0;
 for(;;) {
   char c = *s;
   if (c >= '0' && c <= '9') {
      x *= 16;
      x += c - '0';
   }
   else if (c >= 'A' && c <= 'F') {
      x *= 16;
      x += (c - 'A') + 10;
   }
   else break;
   s++;
 }
 return x;
}

void setup()
{
  Serial.begin(115200);

  Pebble pebblelist[SIGMA];
  for (int i = 0; i < SIGMA; i++) {
    pebblelist[i].StartIncr = 3*Pow2(i+1);
    pebblelist[i].DestIncr = Pow2(i+2) ;
    pebblelist[i].position = Pow2(i+1);
    pebblelist[i].destination = Pow2(i+1);
  }

 
  for (int i = 0; i < SIGMA; i++) {
    char* ptr = (char *) pgm_read_word (&initpebbles [i]);
   
    hexCharacterStringToBytes(pebblelist[i].value, ptr);
  }

  unsigned int currentposition = 0;
 
 
  char temp[64]  = "";
  char* hashoutput;
  byte temp2;
  while(1) {
  Serial.print("Hash ");
  Serial.println(currentposition);

  //1
  if (currentposition >= Pow2(SIGMA) ) { stop();}
  else {currentposition++ ;};
  //2
  for (int i = 0; i < SIGMA; i++) {
    if (pebblelist[i].position != pebblelist[i].destination) {
      pebblelist[i].position = pebblelist[i].position -2;
      array_to_string(pebblelist[i].value, 32, temp);
      hashoutput = h( h( temp ) );
      hexCharacterStringToBytes(pebblelist[i].value, hashoutput);
      };
  }
  char* output;
  //3
  if (currentposition % 2 == 1 ) {
    array_to_string(pebblelist[0].value, 32, temp);
    output =  h( temp );

    }
  else {
     
    array_to_string(pebblelist[0].value,32,output);
    pebblelist[0].position = pebblelist[0].position + pebblelist[0].StartIncr;
    pebblelist[0].destination = pebblelist[0].destination + pebblelist[0].DestIncr;
    if (pebblelist[0].destination > Pow2(SIGMA) ) {
        pebblelist[0].destination = INT_MAX;
        pebblelist[0].position = INT_MAX;
      }
    else {
        FindValue(pebblelist);

        for (int i=0; i < 32; i++) {
          pebblelist[0].value[i] = bytearray_buffer[i];
        }
 
      };
    qsort(pebblelist, sizeof(pebblelist)/sizeof(pebblelist[0]), sizeof(pebblelist[0]), struct_cmp_by_destin);
    };
  Serial.println(output);

  }
 
}



void loop()
{



}




pan19ss

Program with n=12 (does not run and displays warning about memory):
Code: [Select]
#include <Crypto.h>
#include <SHA256.h>
#include <string.h>

#define HASH_SIZE 32
#define BLOCK_SIZE 64
#define OUTPUT_MAX 32
#include <limits.h> //for infinity

const unsigned int SIGMA = 12;

char hex[256];
SHA256 hash;
byte bytearray_buffer[32];

const static char* const initpebbles[] PROGMEM = {
"82464a185ea9b44899ecee124da954bf5f8b9422115a5adf2c312a526bc34de4", "ebc7e73f8295ea1b5898aea27392bcd17d874293ed8842cea2b79c1e2e6ece57",
"dc6a34506fdbf68f35252c4b81f185a2da8f04a0410f643ce2aeaa2e38ab938c", "5e78dec916588974386e0d83a813f2d8e4c293fcbb5d4aa840e9df67ea6f1c87",
"88af7c67bbd6e8d1ecba28d9dfd337d423bafc31d39eb4c4c80b4d1838304091", "e92dd47091568e8b4da0b06e75b9b4df165f989933005074cb8e1c68dbf7bfd8",
"cc39cc3b2f10f91509e33a5b84376926660f49c49c40cd706b2341cd0ed35d93", "003d4c5165ec1dd262b2eb637dfb117c174ffb28ec6c440a04ee961d9e1a7f18",
"b4fac0f25aa853d4f71bd993a6992e1dfdbb32eee9b656296b78ad6f507cea5b", "fa2335a6ceedb54cb2a3b26503a9c6bcefa58caaa69ed196be407658e7857d48",
"1a3dd37ba3ba6b43950a26966dcce14ff5b01bdaaa788661d1c2a23e6615f4fb", "a665a45920422f9d417e4867efdc4fb8a04a1f3fff1fa07e998e86f7f7a27ae3"

};

char *btoh(char *dest, uint8_t *src, int len) {
  char *d = dest;
  while( len-- ) sprintf(d, "%02x", (unsigned char)*src++), d += 2;
  return dest;
}


char* h(char* input) {  

uint8_t result[32];
hash.reset();
hash.update(input, strlen(input));
hash.finalize(result, sizeof(result));

  return(btoh(hex, result, 32));
}

void hexCharacterStringToBytes(byte *byteArray, char *hexString)
{
  bool oddLength = strlen(hexString) & 1;

  byte currentByte = 0;
  byte byteIndex = 0;

  for (byte charIndex = 0; charIndex < strlen(hexString); charIndex++)
  {
    bool oddCharIndex = charIndex & 1;

    if (oddLength)
    {
      // If the length is odd
      if (oddCharIndex)
      {
        // odd characters go in high nibble
        currentByte = nibble(hexString[charIndex]) << 4;
      }
      else
      {
        // Even characters go into low nibble
        currentByte |= nibble(hexString[charIndex]);
        byteArray[byteIndex++] = currentByte;
        currentByte = 0;
      }
    }
    else
    {
      // If the length is even
      if (!oddCharIndex)
      {
        // Odd characters go into the high nibble
        currentByte = nibble(hexString[charIndex]) << 4;
      }
      else
      {
        // Odd characters go into low nibble
        currentByte |= nibble(hexString[charIndex]);
        byteArray[byteIndex++] = currentByte;
        currentByte = 0;
      }
    }
  }
}

byte nibble(char c)
{
  if (c >= '0' && c <= '9')
    return c - '0';

  if (c >= 'a' && c <= 'f')
    return c - 'a' + 10;

  if (c >= 'A' && c <= 'F')
    return c - 'A' + 10;

  return 0;  // Not a valid hexadecimal character
}

void array_to_string(byte array[], unsigned int len, char buffer[])
{
    for (unsigned int i = 0; i < len; i++)
    {
        byte nib1 = (array[i] >> 4) & 0x0F;
        byte nib2 = (array[i] >> 0) & 0x0F;
        buffer[i*2+0] = nib1  < 0xA ? '0' + nib1  : 'a' + nib1  - 0xA;
        buffer[i*2+1] = nib2  < 0xA ? '0' + nib2  : 'a' + nib2  - 0xA;
    }
    buffer[len*2] = '\0';
}


//Pebble code


//Stop function
void stop()
{
 while(1);
}

typedef struct Pebble{
  int StartIncr;
  int DestIncr;
  int position;
  int destination;
  byte value[32];
};

void FindValue(struct Pebble pebble_List[])
{
  for (int i = 1; i < SIGMA; i++)
  {
        if (pebble_List[i].position == pebble_List[0].position) {
            for (int j=0; j < 32; j++) {
              bytearray_buffer[j] = pebble_List[i].value[j];
                  }

  }
}
}

int struct_cmp_by_destin(const void *a, const void *b)
{
    struct Pebble *ia = (struct Pebble *)a;
    struct Pebble *ib = (struct Pebble *)b;
    return (ia->destination - ib->destination);
}


unsigned int Pow2(byte ex)
{
   return 1 << ex;
}

int x2i(char *s)
{
 int x = 0;
 for(;;) {
   char c = *s;
   if (c >= '0' && c <= '9') {
      x *= 16;
      x += c - '0';
   }
   else if (c >= 'A' && c <= 'F') {
      x *= 16;
      x += (c - 'A') + 10;
   }
   else break;
   s++;
 }
 return x;
}

void setup()
{
  Serial.begin(115200);

  Pebble pebblelist[SIGMA];
  for (int i = 0; i < SIGMA; i++) {
    pebblelist[i].StartIncr = 3*Pow2(i+1);
    pebblelist[i].DestIncr = Pow2(i+2) ;
    pebblelist[i].position = Pow2(i+1);
    pebblelist[i].destination = Pow2(i+1);
  }

  
  for (int i = 0; i < SIGMA; i++) {
    char* ptr = (char *) pgm_read_word (&initpebbles [i]);
  
    hexCharacterStringToBytes(pebblelist[i].value, ptr);
  }

  unsigned int currentposition = 0;
  
  
  char temp[64]  = "";
  char* hashoutput;
  byte temp2;
  while(1) {
  Serial.print("Hash ");
  Serial.println(currentposition);

  //1
  if (currentposition >= Pow2(SIGMA) ) { stop();}
  else {currentposition++ ;};
  //2
  for (int i = 0; i < SIGMA; i++) {
    if (pebblelist[i].position != pebblelist[i].destination) {
      pebblelist[i].position = pebblelist[i].position -2;
      array_to_string(pebblelist[i].value, 32, temp);
      hashoutput = h( h( temp ) );
      hexCharacterStringToBytes(pebblelist[i].value, hashoutput);
      };
  }
  char* output;
  //3
  if (currentposition % 2 == 1 ) {
    array_to_string(pebblelist[0].value, 32, temp);
    output =  h( temp );

    }
  else {
      
    array_to_string(pebblelist[0].value,32,output);
    pebblelist[0].position = pebblelist[0].position + pebblelist[0].StartIncr;
    pebblelist[0].destination = pebblelist[0].destination + pebblelist[0].DestIncr;
    if (pebblelist[0].destination > Pow2(SIGMA) ) {
        pebblelist[0].destination = INT_MAX;
        pebblelist[0].position = INT_MAX;
      }
    else {
        FindValue(pebblelist);

        for (int i=0; i < 32; i++) {
          pebblelist[0].value[i] = bytearray_buffer[i];
        }
 
      };
    qsort(pebblelist, sizeof(pebblelist)/sizeof(pebblelist[0]), sizeof(pebblelist[0]), struct_cmp_by_destin);
    };
  Serial.println(output);

  }
  
}



void loop()
{



}

sterretje

What do you mean by "save sram"?

Use less sram? Or save it to e.g. external eeprom?
If you understand an example, use it.
If you don't understand an example, don't use it.

Electronics engineer by trade, software engineer by profession. Trying to get back into electronics after 15 years absence.

pan19ss

Use less SRAM so my program runs without problems (I'm not sure if I can move any more data to flash memory other than those I have already).

CrossRoads

What's wrong with moving up to a 1284P (16K SRAM)? I offer boards in many footprints,  one of them is similar to an Uno.

http://www.crossroadsfencing.com/BobuinoRev17/

Designing & building electrical circuits for over 25 years.  Screw Shield for Mega/Due/Uno,  Bobuino with ATMega1284P, & other '328P & '1284P creations & offerings at  my website.

Coding Badly


You put a fairly large structure on the stack.  If, instead, you made it global / static then the IDE would be able to report how much memory it consumes.  That would give you a better sense of just how out-of-memory you are.


pan19ss

#6
May 26, 2019, 03:42 pm Last Edit: May 26, 2019, 04:56 pm by pan19ss
What's wrong with moving up to a 1284P (16K SRAM)? I offer boards in many footprints,  one of them is similar to an Uno.

http://www.crossroadsfencing.com/BobuinoRev17/

As I said, I want to specifically make this work on Arduino Uno for various reasons - in other words, adding more memory is a trivial solution to my problem, but I want to make this work on Uno.

You put a fairly large structure on the stack.  If, instead, you made it global / static then the IDE would be able to report how much memory it consumes.  That would give you a better sense of just how out-of-memory you are.

But I see my memory usage already during compilation. For n=10 I am at about 70% SRAM...

What I think it could be an improvement is not to convert byte arrays back to char arrays and feed those into the hash function, but feed byte arrays straight into the hash function instead (thus saving memory and computation). Any idea how I could do this?

jremington

#7
May 26, 2019, 07:01 pm Last Edit: May 26, 2019, 07:12 pm by jremington
Quote
I want to make this work on Uno
Why? Reconsider your requirements. They make no sense.


Coding Badly

But I see my memory usage already during compilation.
No, you see "a memory usage".  The value is not your memory usage.


pan19ss

Why? Reconsider your requirements. They make no sense.


I have set my requirements. The discussion "buy a more powerful arduino" doesn't offer anything to my question...

No, you see "a memory usage".  The value is not your memory usage.


I'm a bit confused here but again I don't see how knowing the exact memory usage would help to solve my problem..

Again, I think a solution would be to just deal with byte arrays exclusively (without converting to char arrays). However I tried to pass byte arrays to the hash function but it doesn't seem to output correct values

jremington


DrAzzy

I just don't think there is enough ram on the Uno for this, quite frankly, no matter what hoops you jump through. You're getting the low memory warning without all the arrays being counted (because they're local variables)

ATtiny core for 841+1634+828 and x313/x4/x5/x61/x7/x8 series Board Manager:
http://drazzy.com/package_drazzy.com_index.json
ATtiny breakouts (some assembled), mosfets and awesome prototyping board in my store http://tindie.com/stores/DrAzzy

pan19ss

I just don't think there is enough ram on the Uno for this, quite frankly, no matter what hoops you jump through. You're getting the low memory warning without all the arrays being counted (because they're local variables)


But wouldn't I save memory if I dealt with byte arrays exclusively, instead of converting back and forth to char arrays?

Coding Badly

I don't see how knowing the exact memory usage would help to solve my problem..
The processor has M available memory.  Your application requires A memory to run correctly.  If A is greater than M you're stuffed.  At this point in time you have no idea what A is.

The change is trivial.  It will take less than a minute.  If you can't be bothered to make a trivial change that will garner something vital then why should anyone on this side of your monitor be bothered spending any time trying to help you?


david_2018

#14
May 27, 2019, 09:41 am Last Edit: May 27, 2019, 12:39 pm by david_2018
You are not implementing PROGMEM correctly, your initpebbles array is only storing the pointers to the character arrays in PROGMEM, not the actual character arrays themselves.

Please see
Progmem - Arduino Reference

and a rather thorough explanation

PROGMEM - Nick Gammon

This is one way of putting the actual character arrays into progmem:

Code: [Select]

const char pebble0[] PROGMEM = "ef92dd53c32ceaba5db5f0a2d697cfb29b4ff250e289a5711840d40504792cda";
const char pebble1[] PROGMEM = "72d1dc06087553c571f52f057d401f9b55cce4e6b4daf531e1dfb7a6d1677989";
const char pebble2[] PROGMEM = "39444ff9e95ed61191a477b6925215d5f3fa3e6996905e2c6b1be60d3a54673b";
const char pebble3[] PROGMEM = "b2451c6bffdd03bacd10991d59d1230909638401dc1a925de19e23caafa81824";
const char pebble4[] PROGMEM = "2b9ce5954a44bd6e8e2fa01ddba0cf4432f5d72073c5651410e3c504cb870c27";
const char pebble5[] PROGMEM = "5acc1b260b286d203376ec75f11a97e644daad765d8b96a235e6d6e6e1f4048b";
const char pebble6[] PROGMEM = "da205ac2f1d5a4b2029af45c6e6cbba6a21245f5b7cf6896bccd8197ab36545c";
const char pebble7[] PROGMEM = "9fabcd1fbee85dd1cb27053846ce08cf2e554351206e2a652f227c1a9d7bd13b";
const char pebble8[] PROGMEM = "857958d158f08f168d0dad7d1bcbd5911dd2059bb5d30ec994bd9ed8fe888a93";
const char pebble9[] PROGMEM = "a665a45920422f9d417e4867efdc4fb8a04a1f3fff1fa07e998e86f7f7a27ae3";

const char* const initpebbles[] PROGMEM = {pebble0,pebble1,pebble2,pebble3,pebble4,pebble5,pebble6,pebble7,pebble8,pebble9};



You will also need to copy the character array to dynamic memory before using it, although you may be able to rewrite the code to use PROGMEM directly, I'm not getting into it that deeply.

Code: [Select]

char pebble_buffer[sizeof(pebble0)]; //temporary buffer to hold copy of character array


//section of your code that uses the character array from PROGMEM

for (int i = 0; i < SIGMA; i++) {
    char* ptr = (char *) pgm_read_word (&initpebbles [i]);
    strcpy_P(pebble_buffer, ptr);              //copy from PROGMEM to dynamic memory
    hexCharacterStringToBytes(pebblelist[i].value, pebble_buffer);
  }



This appears to work for SIGMA of 15, although you will have to test with your data to verify.

Go Up