0
\$\begingroup\$

I have an EEPROM I want to store CRC32 hashes on between 0x0000 and 0x008C. In this range I need a way that I can erase one of the hashes and overwrite its bytes to a default number. By doing this I can iterate through them later searching for a free space which was initialized to my "free space value" to store a new one at that position.

For instance if the memory looks like:

0A0A0A0A
0B0B0B0B
0C0C0C0C
0D0D0D0D

and I erase the third index by overwriting it with my place holder

0A0A0A0A
0B0B0B0B
????????
0D0D0D0D

I can then iterate 4 bytes at a time searching for a free space denoted by the place holder and then write my new hash to that location marked as free.

With that being said with a CRC32 hash, which value is the safest to use as a free place marker, 00000000, FFFFFFFF, or a specific other value.

Thanks.

\$\endgroup\$
8
  • \$\begingroup\$ Related: electronics.stackexchange.com/questions/60342/… \$\endgroup\$
    – jippie
    Commented Feb 28, 2016 at 19:58
  • \$\begingroup\$ Note that you cannot erase single bytes with most EEPROMs; entire pages must be rewritten at once. \$\endgroup\$
    – Ignacio Vazquez-Abrams
    Commented Feb 28, 2016 at 19:59
  • \$\begingroup\$ @IgnacioVazquez-Abrams Maybe I used the wrong word, I meant overwrite, which I am pretty sure you can write over an existing byte at address 0xXXXX, or at least these code samples I have found seem to do just that. \$\endgroup\$
    – randy newfield
    Commented Feb 28, 2016 at 20:22
  • \$\begingroup\$ You can only overwrite if no bits are set in the new value versus the old, otherwise an erase is required first. And even if the block-oriented erase is abstracted away by the hardware, it's still there. \$\endgroup\$
    – Ignacio Vazquez-Abrams
    Commented Feb 28, 2016 at 20:29
  • \$\begingroup\$ Minor nitpick here but CRC32 is not a hash, it's a checksum. This has of course no relevance to your question, but it can be useful to know the correct terms when searching for things. \$\endgroup\$
    – pipe
    Commented Feb 28, 2016 at 20:55

3 Answers 3

Reset to default
2
\$\begingroup\$

By default, unprogrammed EEPROM bytes are usually 0xFF. Setting them to that value will make sure that they don't need to be erased during the next write cycle, both saving time and increasing life expectancy of the cells themselves.

\$\endgroup\$
2
\$\begingroup\$

To overwrite an EEPROM cell (byte) without having to erase it beforehand requires that you change its bits from 1 to 0 (you cannot flip 0 to 1). So, the only "flag value" that is safe is an all zero 32-bit value. Well, but an all zero 32-bit CRC32 is a perfectly valid CRC32! You have a couple of ways of solving this issue, and the following 2 have been used successfully before:

a) Don't allow your CRC32 algorithm to generate an all zero value - you have to map the all zero value to some other value - this increases (a little) the possibility of having a false pass, and

b) For the memory blocks you are computing the CRC32, add an extra byte, so you make this extra byte a programmed value that makes your CRC32 not zero. This incurs in an extra byte in your block that sometimes is not possible.

Yet another option is to have an array of bits (on top of your CRC32 table) that represents the blocks that are free (a 1 represents free, a 0 represents a used block). You only need 1 bit per block, so the overhead is not that big.

\$\endgroup\$
3
  • \$\begingroup\$ These are good suggestions thanks. The bitmap of all the indexes of the table makes sense and is doable, but could you expand a bit about a) and b)? In particular how to use the extra byte to map an all zero crc to a new value? Would the byte be used as some sort of marker to show that the value is truly all zeros or not? \$\endgroup\$
    – randy newfield
    Commented Feb 28, 2016 at 21:41
  • \$\begingroup\$ @randynewfield, the idea of the extra byte is to force the final CRC32 computation to not be zero. It's a computed value that you append to your original data to change the final CRC32. For example, if you have N bytes and its CRC32 is zero, when you append the byte 0x00 to your original data, the block now with N+1 bytes will have a CRC32 of 0xD202EF8D. \$\endgroup\$
    – guga
    Commented Feb 29, 2016 at 19:59
  • \$\begingroup\$ *** Note that if you're using the standard CRC32 you can use the LSB of the computed CRC32 as the N+1 byte and that will guarantee that the CRC32 of the N+1 bytes will not be zero *** \$\endgroup\$
    – guga
    Commented Feb 29, 2016 at 20:32
0
\$\begingroup\$

With that being said with a CRC32 hash, which value is the safest to use as a free place marker, 00000000, FFFFFFFF, or a specific other value.

None of them. Every CRC32 hash value is equally likely to appear.

Depending on what you're doing with the hashes, one option may be to store only the bottom 31 bits of the hash, and use the remaining bit as a flag to indicate whether the location has been used.

\$\endgroup\$
3
  • \$\begingroup\$ They are being used in a loopup table where each hash will point to an address elsewhere on the chip so I can seek to the data faster. This idea about using the top 1 bit as a flag may be what I end up doing. \$\endgroup\$
    – randy newfield
    Commented Feb 28, 2016 at 20:19
  • \$\begingroup\$ Chances of a CRC hitting the default value are 1 in 4.3 billion. Worth the risk? \$\endgroup\$
    – Bruce Abbott
    Commented Feb 28, 2016 at 20:22
  • \$\begingroup\$ @BruceAbbott That is a good question which I will have to think about. I will only have a maximum of 300 entries in the lookup and each hash will be generated from a string ranging from 10-64 characters so the odds would be slim, but still a chance. \$\endgroup\$
    – randy newfield
    Commented Feb 28, 2016 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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