The following sample code represents a practical implementation of the CRC ( Cyclic Redundancy Check) employed in PNG chunks. (See also ISO CRC64ISO. Package for calculating checksums using bit cyclic redundancy checks (CRC) according to the ISO standard. Generator polynomial: x64 +. ISO Information technology — Telecommunications and information exchange between systems — High-level data link control (HDLC) procedures.

Author: | Dailar Kajas |

Country: | Netherlands |

Language: | English (Spanish) |

Genre: | Spiritual |

Published (Last): | 23 March 2004 |

Pages: | 181 |

PDF File Size: | 12.15 Mb |

ePub File Size: | 12.23 Mb |

ISBN: | 393-9-91875-728-3 |

Downloads: | 46302 |

Price: | Free* [*Free Regsitration Required] |

Uploader: | JoJogar |

Unfortunately, the modulo-2 arithmetic used to compute CRCs doesn’t map easily into software. Generally speaking, CRCs are most efficiently calculated in dedicated hardware.

I’m going to complete my 3-part discussion of checksums by showing you how to implement a CRC in C. I’ll start with a naive implementation and gradually improve the efficiency of the code as I go along.

For most software engineers, the overwhelmingly confusing thing about CRCs is their implementation. Knowing that all CRC algorithms are simply long division algorithms in disguise doesn’t help. Modulo-2 binary division doesn’t map particularly well to the instruction sets of off-the-shelf processors. For one thing, generally no registers are available to hold the very long bit sequence that is the numerator.

### On-line CRC calculation and free library

For another, 330 binary division is not the same as ordinary division. So even if your processor has a division instruction, you won’t be able to use it. Before writing even one line of code, let’s first examine the mechanics of modulo-2 binary division.

We’ll use the example in Figure 1 to guide us. The number to be divided is the message augmented with zeros at the end. The number of zero bits added to the message is the same as the width of the checksum what I call c ; in this case four bits were added.

What’s most important to notice at this point is that we never use any of the information in the quotient, either crx or after computing the CRC. So we won’t actually need to track the quotient in our software implementation. Also note here that the result of each XOR with the generator polynomial is a remainder that has zero in its most significant bit.

So we never lose any information when the next message bit is shifted into the remainder. Listing 1 contains a naive software implementation of the CRC computation just described. It simply attempts to implement that algorithm as it was described above for this one particular generator polynomial.

## CRC Series, Part 3: CRC Implementation Code in C/C++

Even though the unnecessary steps have been eliminated, it’s extremely inefficient. Multiple C statements at least the decrement and compare, binary AND, test for zero, and left shift operations must be executed for each bit in the message. Given that this particular message is only eight bits long, that might not seem too costly. But what if the message contains several hundred bytes, as is typically the case in a real-world application?

You don’t want to execute dozens of processor opcodes for each byte of input data. Before we crrc making this more efficient, the first thing to do is to clean this naive routine up a bit.

In particular, let’s start making some assumptions about the applications in which is will most likely be used. First, let’s assume that our CRCs are always going to be 8-,iao bit numbers.

## Cyclic redundancy check

In other words, that the remainder can be manipulated easily in software. That means that the generator polynomials will be 9, 17, or 33 bits wide, respectively. At first it seems we may be stuck with unnatural sizes and will need special register combinations, but remember these two facts:. Since we already have the information in the uppermost bit and we don’t need it for the XOR, the polynomial can also be stored in an 8-,rcc bit register. We can simply discard the most significant bit.

The register size that we use will always be equal to the width of 33309 CRC we’re calculating. As long as we’re cleaning up the code, we should also recognize that most CRCs are computed over fairly long messages. The entire message can usually be treated as an array of unsigned data bytes. The CRC algorithm should then be iterated over all of the data bytes, as well as the bits within those bytes.

### Checksum (Java Card API, Classic Edition)

The result of making these two crcc is the code shown in Listing 2. This implementation of the CRC calculation is still just as inefficient as the previous one. However, it is far more portable and can be used to compute a number of different CRCs of various widths. The most common way to improve the efficiency of the CRC calculation is to throw memory at the problem. For a given input remainder and generator polynomial, the output remainder will always be the isp.

If you don’t believe me, just reread that sentence as “for a given dividend and divisor, the remainder will always be the same. So it’s possible to precompute the output io for each of the possible 33309 input remainders and store the results in a lookup table. That lookup table can then be used to speed up the CRC calculations for a given message. The speedup is realized because the message can now 3390 processed byte by byte, rather than bit by bit.

The code to precompute the output remainders for each possible input byte is shown in Listing 3. The computed remainder for each possible byte-wide dividend is stored in the array crcTable[]. In practice, the crcInit function could either be called ccrc the target’s initialization sequence thus placing crcTable[] in RAM or it could be run ahead of time on your development workstation with the results stored in the target device’s ROM.

You’ll also need a function to compute the CRC of a crd message that is somehow able to make use of the values stored in that table. Without going into all of the mathematical details vrc why this works, suffice it to say that the previously complicated modulo-2 division can now be implemented as a series of lookups and XORs.

In modulo-2 arithmetic, XOR is both addition and subtraction. A function that uses the lookup table contents to compute a CRC more efficiently is shown in Listing 4. The amount of processing to be done for each ido is substantially reduced. As you can see from the code in Listing 4, a number of fundamental operations left and right shifts, XORs, lookups, and so on still must be performed for each byte even with this lookup table approach.

The results of this experiment were as follows:. So, at least on cc processor family, switching to the lookup table approach results in a more than five-fold performance improvement. That’s a pretty substantial gain considering that both implementations were written in C. A bit more could probably be done izo improve the execution speed of this algorithm if an engineer with a good understanding of the target processor were assigned to hand-code or tune the assembly code.

My somewhat-educated guess is that another two-fold performance improvement might be possible. Actually achieving that is, as they say in textbooks, left as an exercise for the curious reader. Now that we’ve got our basic CRC implementation nailed down, I want to talk about the various types of CRCs that you can compute with it.

As I mentioned last month, several mathematically well understood and internationally standardized CRC generator polynomials exist and you should probably choose one of those, rather than isk inventing something weaker.

In addition to the generator polynomial, each of the accepted CRC standards also includes certain other parameters that describe how it should be computed. Table 1 contains the parameters for three of the most popular CRC standards.

Two of these parameters are the “initial remainder” and the “final XOR value”. The purpose vrc these two c-bit constants is similar to the final bit inversion step added to the sum-of-bytes checksum algorithm. Each of these parameters helps eliminate one very special, though perhaps not uncommon, class of ordinarily undetectable difference.

In effect, they bulletproof an already strong checksum algorithm. To see what I mean, consider a message that vrc with some number of zero bits. The remainder will never crcc anything other than zero until the first one in the message is shifted into it. That’s a dangerous izo, since packets beginning with one or more zeros may be completely legitimate and a dropped or added zero would not be noticed by the CRC. In some applications, even a packet of all zeros may be legitimate!

The simple way to eliminate this weakness is to start with a nonzero remainder. The parameter called initial remainder tells you what value to use for a particular CRC standard. And only rcc small change is required to the crcSlow and crcFast functions:. The final XOR value exists for a similar reason.

To implement this capability, simply change the value that’s returned by crcSlow and crcFast as follows:. If the final XOR value consists of all ones as it does in the CRC standardthis extra step will have the same effect as complementing the final remainder. However, implementing it this way allows any possible value to be used in your specific application. In addition to these two simple parameters, two others exist that impact the actual computation.

These are the binary values “reflect data” and “reflect remainder”. The reason this is sometimes done is that a good number of the hardware CRC implementations operate on the “reflected” bit ordering of bytes that is common with some UARTs. Two cc modifications of the code are required to prepare for these capabilities.

What I’ve generally done is to implement one function and two macros. This code is shown in Listing 5. The function is responsible for reflecting a given bit pattern. The macros isp call that function in a certain way. By inserting the macro calls at the two points that reflection may need to be done, it iao easier to turn reflection on and off. To turn either kind of reflection off, simply redefine the appropriate macro as X.

That way, the unreflected data byte or remainder will be used in the computation, with jso overhead cost. Tested, full-featured implementations of both crcSlow and crcFast are available for download. These implementations include the reflection capabilities just described and can be used to implement any parameterized CRC formula.

Simply change the constants and macros as necessary. To test your implementation of a particular standard, simply invoke your CRC computation on that message and check the result:. If checksum has the correct value after this call, then you know your implementation is correct.

This is a handy way to ensure compatibility between two cc devices with different CRC implementations or implementors. Lso are a few holes that I’ve hoped for many years that the author would fill with a fourth edition, but all in all it’s the best coverage of a complex topic that I’ve seen. Many thanks to Ross for sharing his expertise with others and making several of my networking projects possible.