1

I have a hardware CRC32 peripheral on a MCU that I would like to use to speed up string search. Normally this is done with one of the rolling hash functions described here https://en.wikipedia.org/wiki/Rolling_hash#cite_note-3. I'm hoping this is possible using CRC32.

I found this answer to a similar question https://stackoverflow.com/a/22356300/1615960 but realized that it would only work starting with the current CRC and working backwards, reversing the CRC one character at a time. What I need to do is trim the CRC using the nth most recent char. For example:

  • Search "helloworld" for "owo".
  • CRC32 of "hel" = X
  • Remove "h" from X = CRC32 of "el" = Y
  • Add "l" to Y = CRC32 of "ell" = Z
  • And so on.... until matching CRC32 of "owo" is found.

My hunch is that this is not possible with CRC32, I'm hoping someone can prove me wrong.

Thanks!

MFlamer
  • 2,340
  • 2
  • 18
  • 25

1 Answers1

2

Yes, it's possible. However I don't see how to use a hardware CRC-32 to help with that. It would be faster to simply recompute the CRC on every triplet of bytes.

Mark Adler
  • 101,978
  • 13
  • 118
  • 158