CRC is an FPGA PITA

I've only used this one on FPGA designs:

It generates a VHDL or Verilog implementation. Selectable polynomial with some common ones predefined, selectable input data width.

Not really. I don't have anything I trust handy for that. From some (software) experimentation years ago when I wanted to generate the same CRC32 as is used in zip, rar and sfv files (and also Python's crc32 function in binascii package) the polynomial used was reversed from that, 0xEDB88320.

Thanks. I don't know how I missed this web page. The code is rather crap, but I assume it must work so could be used as a reference design. The cod e I ended up with is only three assignments and uses two clock enables to a llow calculating the bits and then shifting out the result.

rted output of an input "ABCD1234" (lsb first) would be 16#E928FF7E. Anyone care to confirm that?

Not really reversed exactly, just expressed with the bits reversed. It is calculating the same CRC32 when the day is done. The easics code doesn't b other with the initial register state... or the register at all (which make s it more general) or the final inversion. I think we have our code workin g, but I may give this a try in the test bench for a reference.

Thanks

That's the joy of CRC. With the same bit size and polynomial, you can bit reverse the data coming in, byte reverse the incoming data (if it is handled in larger lumps), bit reverse the generated crc, byte reverse the generated crc, start with a non-zero shift register, and various other options - in any combination. The result is equally strong (though some people argue that starting with a non-zero shift register is better because the crc of an all-zero input then varies by the length of the input).

If you are handling the crc in two different ways (two different implementations), you have to check that it really matches up, and be prepared to fiddle the options a little until you get it right.

But the actual implementation is simple. In software, you usually do this a byte at a time, with a lookup table. In an FPGA, a bitwise CRC is a simple linear feedback register and should be straightforward - I'd expect an experienced FPGA designer will find it less effort to implement it themselves than to use some random web page of questionable quality. The key trick is to ignore the mathematical background for how it works - polynomial division rings sound scary, but the implementation is quite easy. (This means picking your polynomial from the wikipedia page rather than guessing one yourself.)

Yes there is no single "CRC32", there are many. This page gives a nice overview:

I just did a bitwise software solution because I did not want to waste space on a table and speed was not an issue. The above link is nice to check your results. (To check what version of CRC32 you just implemented ;-) ).

erted output of an input "ABCD1234" (lsb first) would be 16#E928FF7E. Anyon e care to confirm that?

Funny that you talk about the number of ways to permute the algorithm and t hen talk about how easy it is to design in an FPGA. Yeah, we had one error in the code which I found by inspection... eventually. That was only perh aps a quarter of the work though. The vast majority was trying to understa nd what all the references were doing since they often don't actually expla in at the bit level detail. Hell, maybe half of them don't even allow hex inputs, must less talk about the bit ordering fed into the algorithm. I th ink this is because they are software people who are only thinking of CRC c alculations on files of characters.

Like I said in the first post, there is little on the Internet to support d ebugging a CRC. I did finally find one site that would allow me to enter d ata in binary which means I could calculate on 1 bit at a time to check eac h stage of the computation.

That was the hard part, finding that one web site.

l/

verted output of an input "ABCD1234" (lsb first) would be 16#E928FF7E. Anyo ne care to confirm that?

Does your implementation actually work on a single bit input? Or is it lik e most that work on bytes, calculating the CRC one bit at a time. I say th is because the C implementations usually XOR the input byte with the CRC re gister before sequentially calculating the next 8 steps of the CRC. This w orks fine because the arithmetic has no carry, but it does give different i ntermediate results in the CRC register and so is not good for comparison w ith a true bit by bit algorithm.

Once you have figured out the permutation, the FPGA design /should/ be fairly straightforward. (Making a design where you can handle all the variations at run-time would be much more effort.)

Basically, a CRC calculator has a shift register (32-bit, for CRC32), and a stream of incoming bits. Each incoming bit is shifted into the CRC register. If the bit shifted out of the register is 1, the CRC register is then xor'ed with the polynomial. That's all. I'd be surprised if you couldn't code the core algorithm in your sleep.

The variations include the starting value for the CRC register, the order bits are taken from incoming bytes (when it is a stream of bytes rather than bits), ordering of the bits from the CRC register before moving it out once it is calculated, and so on. Again, these will be simple to support once you know what variations you are using - /identifying/ the variations can sometimes be difficult.

Yeah, you're right. I do the byte xor before the bitwise steps. So no good for a direct bit-for-bit comparison, sorry.

I recall spending days trying to emulate the USB and ethernet CRCs. The Easics website is great at providing the polynomial but that is only half the story.

What I have done is create all the variations of the starting word, the bit order and any other permutations in a CRC module all in parallel. Then streaming a known good packet and seeing which result was correct and choosing just that output.

I've also breadboarded polynomials in c or c++ but that's tricky in conjuction with the Easic's polynomials.

I see what you are referring to, but thinking there is a "correct" result i s the problem. There is no one correct result. Even the online checkers d on't have a universal one right answer, some of them can be permuted in var ious combinations. In one case I had two agreeing and a third would not pr ovide the same result even when I thought I had all three configured the sa me way.

It would appear the reason for the reverse polynomial specification is that it is desired to generate the CRC using the lsb first which is easier/simp ler to think about in the reversed configuration. This will result in a bi t reversed remainder. Combine that with the options of starting pattern, i nverting the output and treating the input as hex vs. ascii characters and you have a nearly intractable number of combinations. Given all that, it's not really surprising I only ever found one web site I was able to coax in to providing an agreeable result.

like most that work on bytes, calculating the CRC one bit at a time. I say this because the C implementations usually XOR the input byte with the CRC register before sequentially calculating the next 8 steps of the CRC. This works fine because the arithmetic has no carry, but it does give different intermediate results in the CRC register and so is not good for comparison with a true bit by bit algorithm.

d for

That sounds like the universally available C version. I did find a version somewhere that also used the incoming byte one bit at a time, but even the n I haven't compiled a C program in a decade or more. I might write a Fort h program for this, but the need is largely satisfied. If I knew more abou t web page development I would create a web page that provided step by step solutions with all the permutations clearly explained. The one web page t hat I got my "right" answer from had any number of confusing parameters. I 'm lucky to have found one that worked... and that one barely worked with many of the functions simply producing the error message "Input pol is Not hex". How cryptic can you get?

That's what I thought too. But when I looked for it, all I found were table versions. So I just wrote the few lines of code based on some pseude code (I think it was from the CRC wiki). That was faster than trying to find a ready made solution.

It's not that hard ;-) :

ste

it like most that work on bytes, calculating the CRC one bit at a time. I s ay this because the C implementations usually XOR the input byte with the C RC register before sequentially calculating the next 8 steps of the CRC. Th is works fine because the arithmetic has no carry, but it does give differe nt intermediate results in the CRC register and so is not good for comparis on with a true bit by bit algorithm.

good for

at a time, but even then I haven't compiled a C program in a decade or mor e. I might write a Forth program for this, but the need is largely satisfie d. If I knew more about web page development I would create a web page that provided step by step solutions with all the permutations clearly explaine d.

Yeah, like an HTML manual is all it takes...

So does that mean you are using something odd for reading newsgroups? I'm using Google groups which is the oddest, but I'm not willing to invest much time or money to access these few groups I am in. I have no real control over line length other than this...

I could just hit return every few words to make sure the line length is short enough.

Yeah, I'll try doing that.

No, he is using standards-compliant software. It is /you/ who is using something that is broken. Google groups does not automatically follow the Usenet conventions - you need to make an effort to fit in. Some google groups users seem to manage it fine, others don't.

Right. That's because /your/ convenience outweighs the convenience of everyone else in the groups - as long as /you/ don't have to make an extra effort, it doesn't matter if other people do. That of course applies to people who are freely helping /you/ with /your/ problems. Don't you think that sounds a little arrogant?

Thunderbird and news.eternal-september.org don't cost any money, and will probably save you time compared to google groups.

I think you missed a few ";-)" in there, they were intended to not let you take these remarks too seriously. You already explained your google problem before and it was not my intention to go into that again, but I couldn't resist a little tease.

And yes, hitting return now and then could work, it is what I do at least (I'm sure vi (or actually vim) can do it for me, but that is one thing I haven't bothered investigating).

with my slrn+vi combination ;-) ]

something odd for reading newsgroups?

software. It is /you/ who is using

groups does not automatically follow

need to make an effort to fit in. Some

manage it fine, others don't.

is the oddest, but I'm not willing to

to access these few groups I am in.

convenience outweighs the convenience of

long as /you/ don't have to make an

if other people do. That of course

helping /you/ with /your/ problems.

september.org don't cost any money, and

time compared to google groups.

Yes, you are right. I don't care about the line length problem. You can easily deal with the problem in ways that don't involve bitching at people. For example you could read posts using a reader that wraps lines rather than absurdly displaying them as longer than your screen is wide or whatever it is your software does.

I tried Thunderbird. It took the shit and I was not able to resurrect it. But I found Seamonkey which used the same code base and so could import my files. Then after using that for a year it took the shit.

I'm done with software with very little support. If you want to pretend my line lengths are a problem, that's on you for using crap software.

Don't blame it on me.

The resources on CRCs are terrible and they explain things poorly. I've ha d the opposite problem--the last one I did had to compute a CRC with 512 bi ts of input per cycle. In that case you need to do a matrix operation--the 512-bit input vector is summed with the shifted CRC and multiplied (over G F(2)) by a 512x32 binary matrix. I compute these generator matrices in Mat lab: each row of the matrix is a shifted and reduced version of the genera tor poly. But the textbooks never seem to cover this stuff. The permutati ons of Endianness and inversions confuse things further.

For 1-bit-input operations, the matrix reduces to a row vector.

The problem with most resources is they don't answer some of these question s:

1. How is this doing a modulo operation? (The way they draw the diagrams, it's not clear that there are 2 things going on: a shift, which is a mult iplication of the poly by x, and a subtraction, which is an XOR. Also, Hor ner's Method is being used, which isn't always clear.)
2. How is XOR a subtraction? (In a characteristic-2 field, addition and s ubtraction are the same.)
3. Why are we doing a modulo? (The point is to make the codeword, which i s the message plus the CRC, a polynomial which has zeros (roots) at certain locations.)
4. That doesn't look like a polynomial! (It's not--it's the GF(2) binary coefficients of the polynomial written as a hex word. Even though the fiel d being used might not be GF(2), the coefficients of the poly are in GF(2)) .
5. Why not use a regular checksum? (A regular checksum doesn't have good minimum Hamming distance qualities. You can have 2 bit errors and still ha ve a good checksum, but the CRC will show the error if the minimum Hamming distance of the CRC code is >=4.)

ol/

nverted output of an input "ABCD1234" (lsb first) would be 16#E928FF7E. Any one care to confirm that?

me

then talk about how easy it is to design in an FPGA. Yeah, we had one erro r in the code which I found by inspection... eventually. That was only perh aps a quarter of the work though. The vast majority was trying to understan d what all the references were doing since they often don't actually explai n at the bit level detail. Hell, maybe half of them don't even allow hex in puts, must less talk about the bit ordering fed into the algorithm. I think this is because they are software people who are only thinking of CRC calc ulations on files of characters.

debugging a CRC. I did finally find one site that would allow me to enter data in binary which means I could calculate on 1 bit at a time to check ea ch stage of the computation.

There is often a "correct" result that is accepted by peripherals such as an ethernet port. However there are some online packet generators that compute the CRC to compare with and Wireshark can provide the CRC for a packet if the checksum number crunching is not offloaded in peripheral hardware.