A painless guide to crc error detection algorithms Painless Grammar (Painless Series) · Read more Software Error Detection through Testing and Analysis. A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS INDEX V (9/24/96). Contents: Table of Contents · 1. Preface · ) About the Author &. A Painless Guide to CRC Error Detection Algorithms – gentooinit/crc.

Author: Tetaxe Brakazahn
Country: Benin
Language: English (Spanish)
Genre: Personal Growth
Published (Last): 8 February 2006
Pages: 89
PDF File Size: 14.46 Mb
ePub File Size: 7.49 Mb
ISBN: 557-6-77485-406-8
Downloads: 59601
Price: Free* [*Free Regsitration Required]
Uploader: Kagis

The concept itself seems to be easy—a CRC is just the remainder of a particular type of division. The steps of the algorithm are very simple:. And from that description, the code pretty much follows:.

Although, this is the rare case where it’s easier to write it in assembly that it is in C, since we have access to the carry bit when shifting, which makes it easier to check:. What is not shown in the code above either version is the agumentation step of adding additional 0-bits to the message—that’s left up to the caller of deection routines. Both of these routines give the same result. Other implementations I did based upon the Guide also give the same results.

And they’re consistent with the results of the reference code given in the Guide. So far so good. Okay, so the bits are fed in painlews. That can be compensated for.

The Painless Guide to CRC isn’t quite painless – The Boston Diaries – Captain Napalm

Also, the standard CRC algorithm mandates that the initial value of the remainder is all one bits, not zero bits. And that the final remainder is to be exclusived-or’ed with all ones. Again, easy to do.


It all seems pretty straightforward. And since the zlib library uses the CRC, we can link that in as a baseline to compare results. I didn’t think the code I wrote for reflected CRCs was that unreasonable based upon the information in the Guide, but I guess Giide was wrong for some of them.

The Boston Diaries

Oh, and getting back to the non-reflected code—I didn’t initialize the results properly, nor did I exclusive-or the results. Okay, now I’m horribly confused. But I’m concerned that the routines that require additional zero bits aren’t the same in this case.

There has to be some subtle difference between the two in this case that I don’t see, and isn’t mentioned in the Guide at all.

Another thing I noticed by looking deeply into the abyss that is CRC, is that my first implementation of CRC is flawed —I don’t exclusive-or the results with all ones at the end.

I suspect that the code I based mine detetcion didn’t bother with the exclusive-or when returning the CRC, but instead did that elsewhere in the codebase. It’s not a bug per sebut according to Numerical Recipes in C:.

The result is that there’s a type of corruption that I won’t catch. This code was the basis for the CRC implementation in a few programs at work oops but again, I don’t think it’s an outright show-stopping bug.

At some point, I may go through some of this on paper, one bit at a time, to see what’s going on math-wise with the reflected and non-reflected table implementations with non-0 initial values. The dates are the permanent links to that day’s entries or entry, if there is only one entry. The titles are the permanent links to that entry only. The format for the links are simple: Start with the base link for this site: You can also specify the entire month by leaving off the day portion.


You can even select an arbitrary portion of time. You may also note subtle shading of the links and that’s intentional: It’s an experiment in using color shading to denote the distance a link is from here.

Fo you don’t notice it, don’t worry; it’s not all that important. The steps of the algorithm are very simple: Load the remainder with zero bits.

Augment the message by appending zero bits equal to the size of the remainder to the end of it. While more message bits Shift the remainder left by one bit, reading the next bit of the augmented message into bit position 0 of the remainder.

If a 1 bit popped out of the remainder during the previous step, XOR the result with the polynomial We now have the remainder.

And from that description, the code pretty much follows: So, with that out of the way, the code: It’s not a bug per sebut according to Numerical Recipes in C: Operating System Development Reddit: Theory and Application Reddit: Compilers Obligatory Miscellaneous Comments?

You have my permission to link freely to any entry here. Go ahead, I won’t bite.