read a multidimensional array as an integer only for comparison

Status
Not open for further replies.

snowsh

Well-known member
I posted this question earlier on Stack overflow https://stackoverflow.com/questions...ional-array-as-an-integer-only-for-comparison



UPDATE: Considerations: this is on an embedded platform, I am memory limited and not wanting to have to use any extra Libs to perfom things like hashing..

I am running a program that uses a multi dimensional array.

Code:
uint8_t array[8][32]

This array is constantly updating, I need to run a comparison to determine if in the last 3 steps, there is a repetition.

It occoured to me that the array is just memory, so rather than iterate through the array, and create a comparison temp array (memory and processor wasted) why not approach this almost like making a hash of the array. I dont need any unique crypto so why not just read the memory location of the whole array as an integer?

Thoughts? How would I go about addressing the array to read in an integer which I could store in another simple array for my much easier comparison

Code:
unsigned long arrayTemp[3]
 
As others said, for comparing large chunks of memory, use memcmp(). No, it doesn't require copying to a temporary array. Nor does it take much memory.

Casting arrays of bytes to longs is a legitimate way to speed up comparisons. No need to move to another array.
 
Last edited:
As others said, for comparing large chunks of memory, use memcmp(). No, it doesn't require copying to a temporary array.

Casting arrays of bytes to longs is a legitimate way to speed up comparisons.

ok, so lookng closer at memcmp(), is it as simple as this?

Code:
int compare;

arrayTemp[i] = (byte) array;

i++;

if(i>1) i=0;

compare = memcmp(arrayTemp[0] , arrayTemp[1] , sizeof(arrayTemp[0]));

if(compare == 0)
{
   // do somthing
}

somthing like that?
 
Not sure what you are trying to do, perhaps below. Frank's idea is also good (may be more efficient).


Code:
uint8_t array[8][32];
uint8_t prev_array[8][32];

if (memcmp(array, prev_array, sizeof(array)) == 0)
   do something

memcpy(prev_array, array, sizeof(array));

General advice - don't optimize until you are sure it is needed.
 
What are you trying to compare the [8] byte long data or the [32] long data, ie an array[8] of 32 byte entities or an array[32] of 8 byte entities?
The latter is really easy.
 
Not sure what you are trying to do, perhaps below. Frank's idea is also good (may be more efficient).


Code:
uint8_t array[8][32];
uint8_t prev_array[8][32];

if (memcmp(array, prev_array, sizeof(array)) == 0)
   do something

memcpy(prev_array, array, sizeof(array));

General advice - don't optimize until you are sure it is needed.

ok, I am running a game of life program and trying to detect when it gets stuck. I already have it resetting fine when it run out of moves, that was trivial. The issue is it can get stuck in a repeating loop of maybe 2 or 3 repetitions. I need to detect when that happens and trigger a reset.

My idea was to make a holding array to store the last 3 "grids" of the game and run a comparison to the overall array without having to do any loops - that is going to kill the process and take way too long. Much simpler I thought to simply treat the multidimensional array grid[8][32] as a single value based on its pure memory...

using your suggestion and info from https://www.cplusplus.com/reference/cstring/memcmp/ I am at this:

Code:
uint8_t gridTempCompare[3] = {0};

uint8_t compareCounter;

int compare;

uint8_t grid[8][32] = {{0}};     // game state. 0 is dead cell, >1 is live cell

// the game code updates grid on every loop. values could be from 0 to 60 as I have made some changes to the original game of life routine.

void compareArray()
{
  memcpy(gridTempCompare[compareCounter], grid, sizeof(grid)); 
  
  compareCounter++;
  
  if(compareCounter>2) compareCounter=0;   // only need to store 3 records
  
  compare = memcmp(grid, gridTempCompare[compareCounter], sizeof(grid)); // once I get this bit working I can determine how best to reference the array in arg 2.
  
  Serial.print(compare);
  
  if(compare == 0)
  {
     // do somthing
  }
}

I get the following complie error:

Code:
C:xxxerialMIDI-filesystem_-_02072021\_life.ino:222:40: warning: invalid conversion from 'uint8_t {aka unsigned char}' to 'void*' [-fpermissive]
   memcpy(gridTempCompare[compareCounter], grid, sizeof(grid)); 
                                        ^
In file included from C:xxxxarduino_build_241800\pch\Arduino.h:6:0:
C:xxxArduino\hardware\teensy\avr\cores\teensy4/WProgram.h:94:14: note:   initializing argument 1 of 'void* memcpy(void*, const void*, size_t)'
 extern void *memcpy (void *dst, const void *src, size_t count);
              ^
C:xxxx2072021\_life.ino:228:56: warning: invalid conversion from 'uint8_t {aka unsigned char}' to 'const void*' [-fpermissive]
   compare = memcmp(grid, gridTempCompare[compareCounter], sizeof(grid));
                                                        ^
In file included from c:xxxarduino\hardware\tools\arm\arm-none-eabi\include\stdlib.h:11:0,
                 from C:xxxArduino\hardware\teensy\avr\cores\teensy4/WProgram.h:34,
                 from C:xxxxarduino_build_241800\pch\Arduino.h:6:
c:xxxxarduino\hardware\tools\arm\arm-none-eabi\include\string.h:26:7: note:   initializing argument 2 of 'int memcmp(const void*, const void*, size_t)'
 int   _EXFUN(memcmp,(const _PTR, const _PTR, size_t));
       ^

I have tried many different methods and I always get a complie error. I'm still trying to get my head around &var *var etc......
 
Last edited:
I see now that you are trying to compare an uint8_t array[8][32] with another one.
If it had just been 8byte chunks the following might have been the way to go.

Code:
typedef uint8_t arrayPart[8];

typedef union fred {
    arrayPart B[32];
    unsigned long long BbyAnotherName[32];
}fred ;

fred myData;

// useage
    myData.B[1][3] = 9;
//comparison
    if (myData.BbyAnotherName[3] == myData.BbyAnotherName[6]) {
//        Then do something
    }
 
I see now that you are trying to compare an uint8_t array[8][32] with another one.
If it had just been 8byte chunks the following might have been the way to go.

Code:
typedef uint8_t arrayPart[8];

typedef union fred {
    arrayPart B[32];
    unsigned long long BbyAnotherName[32];
}fred ;

fred myData;

// useage
    myData.B[1][3] = 9;
//comparison
    if (myData.BbyAnotherName[3] == myData.BbyAnotherName[6]) {
//        Then do something
    }

no i need to compare the whole thing - it represents the game which is being displayed on a 8*32 neopixel panel.....
 
ok, so the only way my thing would work was if it became something like:-
Code:
typedef uint8_t arrayPart[8];

typedef union fred {
    arrayPart B[32];
    unsigned long long BbyAnotherName[32];
}fred ;

fred myData, otherData

// useage
    myData.B[1][3] = 9;
//comparison
    if )(myData.BbyAnotherName[1] == otherData.BbyAnotherName[1])  && (myData.BbyAnotherName[2] == otherData.BbyAnotherName[2])) && and so on{
//        Then do something
    }
 
ok, so the only way my thing would work was if it became something like:-
Code:
typedef uint8_t arrayPart[8];

typedef union fred {
    arrayPart B[32];
    unsigned long long BbyAnotherName[32];
}fred ;

fred myData, otherData

// useage
    myData.B[1][3] = 9;
//comparison
    if )(myData.BbyAnotherName[1] == otherData.BbyAnotherName[1])  && (myData.BbyAnotherName[2] == otherData.BbyAnotherName[2])) && and so on{
//        Then do something
    }

yeah, this is what I am trying to avoid.... Hence my thinking that taking the whole array[][] as a single block of memory, poping that value into the temp array and doing the comparison on that is the way to go. That way the temp records are just an integer that represents the total bytes of the original array... Am I tripping? These neopixels are getting a bit psycadelic to be fair :D
 
> an integer that represents the total bytes of the original array

You can only approximate this with a hash/crc/checksum.
 
At last, got it to work. I don't know how, it should not, but it seems to.
Check it out.
Code:
// Visual Micro is in vMicro>General>Tutorial Mode
// 

//

typedef uint8_t arrayTypeA[8];
typedef arrayTypeA ArrayTypeB[32];

unsigned long long l;

typedef union tom {
    ArrayTypeB B;
//    unsigned long long BbyAnotherName[32];
}tom ;


tom myData, yourData;

// The setup() function runs once each time the micro-controller starts
void setup()
{

    while (!Serial);
    Serial.print("unsigned long long occupies ");
    Serial.print(sizeof(l));
    Serial.println(" bytes");
    Serial.print("myData occupies ");
    Serial.print(sizeof(myData));
    Serial.println(" bytes");
    Serial.print("yourData occupies ");
    Serial.print(sizeof(yourData));
    Serial.println(" bytes");
    myData.B[1][3] = 9;
    if (myData.B == yourData.B) {
//        Then do something
    }
}

// Add the main program code into the continuous loop() function
void loop()
{


}
 
if (myData.B == yourData.B) {
// Then do something
}

I challenge you to find a case where the if statement is true.
 
well after a tense evening and a fruitfull morning, I decided I had to roll my own. This is what I came up with, it seems to do the job niceley. I can see how on a larger grid this approach would fail, but for my purposes, this does the job. At the end of the day, thats all we need right?

Code:
#define STUCK_COUNTER_MAX 4

int gridTempCompare[STUCK_COUNTER_MAX] = {0};

uint8_ t crcCounter = 0;

#define GRID_HEIGHT 8
#define GRID_WIDTH 32


bool calcGrid(uint8_t ar[GRID_HEIGHT][GRID_WIDTH])
{
  int csSumAr[GRID_HEIGHT] = {0};

  int sum = 0;

  for (int y = 0; y < GRID_HEIGHT; y++)
  {
    for (int x = 0; x < GRID_WIDTH; x++)
    {
      Serial.print(ar[y][x]);
      Serial.print(F(" "));
      csSumAr[y] = csSumAr[y] + (int) (ar[y][x] * x * y);          // attempt to get somthing close to unique
    }
    Serial.print(F(" --- csSum: "));
    Serial.print(csSumAr[y]);
    Serial.print(F(" --- sum: "));
    sum += csSumAr[y];                                                      // now sum all elements. prob not right - we will see
    Serial.println(sum);
  }
  
  gridTempCompare[crcCounter] = sum;
  
  Serial.println(F("------- GRAND SUM:"));
  Serial.print(crcCounter);
  Serial.print(F(": "));
  Serial.println(gridTempCompare[crcCounter]);
  Serial.println(F("-------"));
  
  crcCounter ++;
  if (crcCounter == CRC_COUNTER_MAX) crcCounter = 0;
  
  // better in a for loop, but here for reference. so far I have only experienced stuck loops that last 4 cycles.
  if (gridTempCompare[0] == gridTempCompare[1] || gridTempCompare[0] == gridTempCompare[2] || gridTempCompare[0] == gridTempCompare[3]) 
  {
    return true;
  }
  else
  {
    return false;
  }
}

My first searches a few days ago lead me here: https://forum.arduino.cc/t/conways-game-of-life-code-with-auto-restart/82533 Im glad I have proven comment #2 to be wrong. not that that comment was bad in any way, but (on a slightly off topic slant) it seems that since the arduino forum upgrade last month, allot of user names are now marked System. There are a couple of lurkers there (no names mentioned) that always take the high position to questions that seem to be beneath them (really what is the point - we all had to learn at some point) - their names are now System - maybe they have been banished. Glad that kind of thing does not happen here on PJRC, I do find it to be a much more friendly area - maybe because we have awesome hardware to play with :)

Thanks for all the useful tips - we got there in the end.

If anyone else wants to use this, I simply called it in my main game of life routine:

Code:
if(calcGrid(grid))
    {
      resetGrid();
    }
 
Last edited:
@Jonr was correct in his statement made in msg14 above.
Although the code compiled and ran it did not give a valid answer.
I have included a test program to demonstrate that below.
Although you can assign typedefs, structs and unions to each other you cannot compare them.
I just wish that the compiler followed that and displayed an error rather than going on and producing code without error or warning.
The code below also demonstrates using MEMCPY to do a comparison.
@snowsh, I am glad that you've got something working for your needs.
Code:
// Visual Micro is in vMicro>General Mode
// 

//
#include "Arduino.h"

typedef uint8_t arrayTypeA[8];
typedef arrayTypeA ArrayTypeB[32];

unsigned long long l;
//uint32_t l;

typedef union tom {
    ArrayTypeB B;
    uint8_t buf[sizeof(ArrayTypeB)];
}tom;


tom myData, yourData;

// The setup() function runs once each time the micro-controller starts
void setup()
{
    Serial.begin(9600);
    while (!Serial && (millis() < 4000)) {}

    Serial.print("unsigned long long occupies ");  Serial.print(sizeof(l));         Serial.println(" bytes");
    Serial.print("myData occupies ");              Serial.print(sizeof(myData));    Serial.println(" bytes");
    Serial.print("yourData occupies ");            Serial.print(sizeof(yourData));  Serial.println(" bytes");

//Fill myData with data...and copy to yourData

    for (uint n = 0; n < sizeof(ArrayTypeB); n++) {
        myData.buf[n] = n;
 //       yourData.buf[n] = n;
    }
    yourData = myData;

//now check that they match

    Serial.println("Data should match");
    if (myData.B == yourData.B) 
        Serial.println("Data Match");
    else 
        Serial.println("Data Different");
    int n = memcmp(myData.B, yourData.B, sizeof(myData.B));
    if (n == 0);   Serial.print("Using MEMCMP() Data Shown to Match. n=");
    Serial.println(n);

    //alter myData and see if they still match

    myData.B[1][3] = 9;
    Serial.println("Data should NOT match");
    if (myData.B == yourData.B)
        Serial.println("Data Match");
    else 
        Serial.println("Data Different");

    n = memcmp(myData.B, yourData.B, sizeof(myData.B));
    Serial.print("Using MEMCMP on differing data n= ");  Serial.println(n);

}

// Add the main program code into the continuous loop() function
void loop()
{


}
 
A cryptographic hash function can be used to detect repetitions of previous states without
having to store all the previous state - perhaps only 256 bits per repetition.

The chance of different states leading to the same hash is too small to worry about, if its
a strong crypto hash.

However you do have to compute the hash for each copy of the state.
 
A cryptographic hash function can be used to detect repetitions of previous states without
having to store all the previous state - perhaps only 256 bits per repetition.

The chance of different states leading to the same hash is too small to worry about, if its
a strong crypto hash.

However you do have to compute the hash for each copy of the state.

yes, this is kind of what I am doing but without all the expense of calculating a hash.
 
To be pedantic, the code in #15 is using a hash. Below supposedly performs well for strings (not applicable here). murmur3 might be better for ints.

I used to think it didn't much matter. Then I did some testing of the number of collisions.

Code:
// larson hash

unsigned int
hash(
    const char* s,
    unsigned int seed = 0)
{
    unsigned hash = seed;
    while (*s)
    {
        hash = hash * 101  +  *s++;
    }
    return hash;
}
 
Last edited:
Status
Not open for further replies.
Back
Top