Comment by neilv
3 years ago
I used a similar idea the other day, while implementing in Rust the CRC algorithm that a device required, but the vendor didn't document 100% clearly.
Fortunately, I had some device vendor sample code in C (of varying quality and provenance), which I believed was probably correct, but I wasn't 100% certain which (if any) of numerous CRC standard variants it was actually implementing (so I couldn't just use an off-the-shelf Rust library).
So, the fastest/best way to get a perfectly compatible Rust implementation seemed to be:
1. Write idiomatic Rust code to try to mimic the behavior of the C code.
2. Write some C code to generate a text file of exhaustive results from the known-good C implementation, for all possible inputs up to length N.
3. Exhaustively check the Rust implementation against that text file of inputs and outputs.
For future reference there's an excellent tool for discovering the parameters of a CRC model with pairs of inputs and outputs called RevEng [0] (github copy: [1]). Once you have the parameters you can use the CRC crate [2] with a predefined CRC or a custom algorithm (highly unlikely).
[0] https://reveng.sourceforge.io/
[1] https://github.com/berney/reveng
[2] https://crates.io/crates/crc
Going on this "Brute Force" discussion... the CRC Zoo is computing the minimal hamming distances of various CRCs.
https://users.ece.cmu.edu/~koopman/crc/notes.html
I don't know what algorithm they're using, but the idea that you can make a hamming distance calculation over all possible input sets these days is pretty spectacular.
Thanks! And another tool recommended to me: https://crccalc.com/
https://en.wikipedia.org/wiki/Test_oracle
Test oracles are great for porting software.
This sounds like things I heard in Rob Pike's presentation regarding how they wrote the go parser. I am no expert though.