Can I save any SRAM memory in my program?

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: arduinolibs/libraries/Crypto at master · rweather/arduinolibs · GitHub

Program with n=10:

#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()
{



}

Program with n=12 (does not run and displays warning about memory):

#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()
{



}

What do you mean by "save sram"?

Use less sram? Or save it to e.g. external eeprom?

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).

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. |500x209 http://www.crossroadsfencing.com/BobuinoRev17/

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.

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. |500x209 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.

[quote author=Coding Badly link=msg=4187296 date=1558851407] 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.

[/quote] 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?

I want to make this work on Uno

Why? Reconsider your requirements. They make no sense.

|500x317

pan19ss:
But I see my memory usage already during compilation.

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

jremington: Why? Reconsider your requirements. They make no sense.

|500x317

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

[quote author=Coding Badly link=msg=4187995 date=1558892105] No, you see "a memory usage". The value is not your memory usage.

[/quote] 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

Consider a less challenging hobby.

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)

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)

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

pan19ss: 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?

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:

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.

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.

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:

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.



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.

Wow david! That was ENORMOUSLY useful! Exactly the improvements I was looking for!
I confirm that it works for sigma=15 flawlessly! At compilation, global variables use 845 bytes of dynamic memory!
I also confirm that it doesn’t work for sigma=16 for some reason and the dynamic memory usage on compilation drops by half for some reason. But still this is great!

pan19ss:
I also confirm that it doesn’t work for sigma=16 for some reason

Have not looked at all the code closely, but the Pow2 function stops the code at sigma=16, because 1 << 16 will not fit in an unsigned integer.

david_2018:
Have not looked at all the code closely, but the Pow2 function stops the code at sigma=16, because 1 << 16 will not fit in an unsigned integer.

Of course great catch!
So since I’m only doing power of two’s, I tried to do bitshifting with long but can’t get it to work…

long Pow2(long ex)
{
  return 1 << ex;
}

and

Pow2(16) returns zero…

(and just confirmed that it works perfectly in C++)

Must be something with the compiler assuming 1 is an integer, if you explicitly give the type it works:

unsigned long Pow2(unsigned long ex) {
  return 1ul << ex;
}

or written another way

uint32_t Pow2(uint32_t ex) {
  return (uint32_t)1 << ex;
}

Appears to work using unsigned long long ( uint64_t ), but the print statements can’t seem to handle 64-bit numbers.

Thanks again david, meanwhile I tried something simpler and it works as well

unsigned long Pow2(int ex)
{
   unsigned long number=2;
   for (int intIndex = 1; intIndex < ex; intIndex++) {
     number = number*2 ;
   }
   return number;
}

although I suppose the bit shifting is much more efficient.

So before moving to sigma=16 I changed the respective parts in the code from unsigned int to unsigned long to test if the code outputs the same values for sigma=15 as before. After trial and error I found that if I change the function

unsigned int struct_cmp_by_destin(const void *a, const void *b)

to

unsigned long struct_cmp_by_destin(const void *a, const void *b)

(which is used by quicksort), then the output values are wrong.
Eg. Hash 17 should be 7118aeefe80cc7cf531acd988590b735e066a2b7f0518c6fe0f9c006954d54b5 but it outputs some other hash value. Following is my updated code. Any idea what can be wrong here?
Thank you very much in advance!

#include <Crypto.h>
#include <SHA256.h>
 
#define HASH_SIZE 32
#define BLOCK_SIZE 64
#define OUTPUT_MAX 32

const unsigned int SIGMA = 15;

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

const char pebble0[] PROGMEM = "bdef24e9651a63598c44e273f808f5cdc3b4154a425541c05c85432fbb018154";
const char pebble1[] PROGMEM = "cda7573d832969f4afd769a257cb66a124af53ff1e510c005096ca3cf2b9a2a8";
const char pebble2[] PROGMEM = "46beb35229cd40e9dcdcf960e713339f0519078b65be13cd17dabe1adeb28354";
const char pebble3[] PROGMEM = "ae85dee37dcef9852a26a41d11e0534ddfd7275ed326c4adc411747e838a7d46";
const char pebble4[] PROGMEM = "4a93eee7c2848bddf2193af5953ad9f185aa052999f2f01d7c698797ecedf8b4";
const char pebble5[] PROGMEM = "35aa135be5c5eed96b158f407c73cc37d95c6ad88cd294f8759ec9a417aa99e1";
const char pebble6[] PROGMEM = "b9859686029f61d729b79e190089ad9211485cf720ca0f26d3578fae6dbf2636";
const char pebble7[] PROGMEM = "418185dfda06277885102410a7bdbcc4891be9ad5b3601e6fd70e83c9dce944f";
const char pebble8[] PROGMEM = "a11f1070ddf0c184796047b346845993ef0dd21ae5905946cbfefafef6352dbb";
const char pebble9[] PROGMEM = "2c0498375e19d748659dcaacb05d82ada9a065d1a052af32b7bb2a3a87406016";
const char pebble10[] PROGMEM = "32381d47548695cec2e499ebef5ecbe5ca2baed472c8f86396817fae5b92e8c4";
const char pebble11[] PROGMEM = "1d6e456784f0b097d5a0cf6499c68f513869cfbd65de40629b448efdc9c84552";
const char pebble12[] PROGMEM = "bed5c8f8cb4d4416fccfb0211fa5895af1a08bd43a92462323749b2998ccead0";
const char pebble13[] PROGMEM = "ec1ab900946965bb5244fb70a4046fc1dc94b1f6f7bac856b67d49e2c3dd1545";
const char pebble14[] PROGMEM = "a665a45920422f9d417e4867efdc4fb8a04a1f3fff1fa07e998e86f7f7a27ae3";

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

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

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{
  unsigned long StartIncr;
  unsigned long DestIncr;
  unsigned long position;
  unsigned long 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];
                  }
  }
}
}

unsigned 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);
} 

uint32_t Pow2(uint32_t ex) {
  return (uint32_t)1 << ex;
}

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]);
    strcpy_P(pebble_buffer, ptr); //added
    hexCharacterStringToBytes(pebblelist[i].value, pebble_buffer);
  }

  unsigned long 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;
        pebblelist[0].destination = Pow2(SIGMA+1);
        pebblelist[0].position = Pow2(SIGMA+1);
      }
    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()
{



}