0

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.

randy newfield
  • 189
  • 1
  • 3
  • 10
  • Related: http://electronics.stackexchange.com/questions/60342/wear-leveling-on-a-microcontrollers-eeprom – jippie Feb 28 '16 at 19:58
  • Note that you cannot erase single bytes with most EEPROMs; entire pages must be rewritten at once. – Ignacio Vazquez-Abrams Feb 28 '16 at 19:59
  • @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. – randy newfield Feb 28 '16 at 20:22
  • 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. – Ignacio Vazquez-Abrams Feb 28 '16 at 20:29
  • 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. – pipe Feb 28 '16 at 20:55
  • @pipe: In what way is a CRC (or any other checksum) not a hash? It may not be a *cryptographic hash*, which has special properties with respect to finding a reverse mapping, but it still has the property of mapping a large (possibly infinite) set of input values to a smaller (finite) set of output values, which is the general definition of a hash function. – Dave Tweed Feb 29 '16 at 00:59
  • @DaveTweed Simply because it's not designed as a hash function in the meaning used in computer science. It may superficially look like one, and as you have pointed out, it has many if not most of the same properties as one, but it would still be a bad fit when a hash function is needed. Right tool for the job and all that. – pipe Feb 29 '16 at 01:18
  • @pipe: I think you're using too narrow a definition. See [Wikipedia](https://en.wikipedia.org/wiki/Hash_function). – Dave Tweed Feb 29 '16 at 01:31

3 Answers3

2

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.

Ignacio Vazquez-Abrams
  • 48,282
  • 4
  • 73
  • 102
2

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.

guga
  • 146
  • 3
  • 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? – randy newfield Feb 28 '16 at 21:41
  • @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. – guga Feb 29 '16 at 19:59
  • *** 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 *** – guga Feb 29 '16 at 20:32
0

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.

  • 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. – randy newfield Feb 28 '16 at 20:19
  • Chances of a CRC hitting the default value are 1 in 4.3 billion. Worth the risk? – Bruce Abbott Feb 28 '16 at 20:22
  • @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. – randy newfield Feb 28 '16 at 20:27