How to search through an array to find a 'matching' byte sequence?

Using Arduino Project Guidance
1

Hello all,

I am currently attempting to find a solution for searching through the EEprom on an Arduino Uno for a matching entry.
My application involves RFID tags for inventory purpose. It is possible that a user swipes identical tags that are the same thing, and when this happens, I would like to delete the item from the EEprom. The RFID tags have Start and Stop bytes (FF, FF), and I'm not sure if this could assist in some sort of algorithm?

Thanks for any help.

2

Do they have a fixed length?

3

Yes, 11 Bytes per RFID Tag.

The form may be something such as:

byte tag[] = {0xFF,0x00,0x01,0x82,0x83, 0xFC, 0x64, 0xD0, 0x82,0x83, 0xFF};

For example

4

At 11 bytes per tag, you can only store 90 tags? Is that OK? I've been playing with FRAM, and it seems to be a lot easier to work with, and it's a lot bigger, and it doesn't have limited write cycles.

Since EEPROM has limited number of write cycles, you pretty much have to start at the beginning every time and brute force your way through the comparison. There's no way to do a bubble sort in EEPROM as it would take too long and you'd wear the EEPROM out in a hurry.

5

I definitely should have considered FRAM... I totally forgot the EEprom on the uno supports only 1K bytes. Also just realized that the EEprom is very sensitive to the number of times it can be written. Thanks for the heads up!

6

cptdondo:
At 11 bytes per tag, you can only store 90 tags? Is that OK? I've been playing with FRAM, and it seems to be a lot easier to work with, and it's a lot bigger, and it doesn't have limited write cycles.

FRAM Write cycles are limited. They're in the millions, but limited.
Also, their Read cycle is destructive, too.

7

Yes, each access is a read/refresh, but from the data sheet: "Even at 2000 accesses per second to the same row, 15 years time will elapse before 10^12 endurance cycles occur", so in my world, that's "practically unlimited." :slight_smile:

8

Bermshot58:
Yes, 11 Bytes per RFID Tag.

The form may be something such as:

byte tag[] = {0xFF,0x00,0x01,0x82,0x83, 0xFC, 0x64, 0xD0, 0x82,0x83, 0xFF};

For example

I think you will find that the first three bytes and the last one is always the same so there is no need to store these. So that only leaves you with 7 bytes per tag. That will go into a long int and then you can use the normal compare ( == ) operation, no need for an array.

9

Grumpy_Mike:
So that only leaves you with 7 bytes per tag. That will go into a long int

That's a good idea. I assume you mean a 'long long int' (64-bit).

10 
byte tag[] = {0xFF, 0x00, 0x01, 0x82, 0x83, 0xFC, 0x64, 0xD0, 0x82, 0x83, 0xFF};

if the list is long you can create a hash of every tag, and store in in the first byte or so (as this is always 0xFF)

uint8_t hash(byte *tag)
{
  uint8_t h = 0;
  for (int i=1; i<9; i++)
  {
    h = h ^ tag[i];  // XOR will work reasonably well
  }
  return h;
}

The hash value stored in byte 0 of the array can have a value between 0..255, so by testing this first for match you will get a quick fail (chance 255 of 256 values will fail).

As the first 2 bytes are always the same you can use a similar trick on int level and store the hash in the first 2 bytes.
Chance on a quick fail will increase to 65535 of 65536 values, so less testing is needed to find the match.