Brute-force CRC polynomial finder

I wrote the brute-force CRC polynomial finder program. It takes six minutes to try all
CRC polynomials of order three through sixteen over two buffers of 1024 ROM words, on my Athlon XP 1900+ system.

It appears that the Spice-series calculator selftest uses either a CRC-10 (x^10 + x^9 + x^5 + x^4 + x + 1), or the reverse of that (x^10 + x^9 + x^6 + x^5 + x + 1). The direction of a CRC polynomial has always been confusing to me, because some books and web pages show them shifting one way, and some another, and the whole GF(2) polynomial division concept still seems tricky. I’ve seen some references that claim that the reverse of a CRC polynomial is effectively as good as the normal one, but nothing authoritative. Any CRC experts out there care to look at my crc.c program and tell me which polynomial it really is?

CRC-10 would have been my first guess, since they are computing it over 10-bit words, so I suppose I could have saved time and just tried it. Though I’m not sure I would have thought to try the reverse polynomial.

I’ve verified that it works for the HP-32E, HP-33C, and HP-37E, as well as the non-bank-switched banks of the HP-34C, HP-38E, and HP-38C. I’ll need to hack my program a bit to handle the bank switched ones, because the bank-switch instruction actually does toggle the bank even when it is fetched by the self-test instruction. That’s why the bank-switch instruction is always present in identical locations in both banks, and there are always an even number of them so that the self-test instruction completes with the original bank selected.

Anyhow, I’ll put the CRC verification code in the next release of Nonpareil, although I don’t yet know how the self-test instruction indicates a failure, so I won’t actually get it hooked in. But I can have it put up a warning dialog at startup if the ROM CRCs are bad.

In case anyone wants to see it, here is the brute-force polynomial finder program: gencrc.c. I suppose it might be useful for reverse-engineering proprietary protocols.

Googling for information on CRCs turned up an interesting recent paper (PDF format): Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks. It turns out that some of the old standbys aren’t really all that great.

Update: I added a function to munge the ROM images for bank switching, and now I can verify that the HP-34C, HP-38E, and HP-38C ROMs also all have the same CRC. I still need to dump the ROMs of the HP-31E and HP-33E; when I tried before I ran into technical difficulties.

This entry was posted in Calculators, Nonpareil. Bookmark the permalink.

Leave a Reply