CRC is an FPGA PITA

On Tuesday, December 15, 2020 at 7:23:13 AM UTC-5, Mike Perkins wrote:
> On 12/12/2020 21:36:11, gnuarm.del...@gmail.com wrote:=20
> > I had a newbie working on a bit wise CRC32 implementation and he=20
> > could not get the results of any of the many online CRC32 generators=20
> > available. So I coded up the same algorithm and tried it myself with=20
> > similar results.=20
> >=20
> > I tried digging around and found little that I could use to either=20
> > evaluate an algorithm or to generate comparison data other than the=20
> > final result. What I needed was something that could produce a=20
> > result for each input bit. Most of the reference designs are for=20
> > sequential languages which are byte oriented. Even if you present=20
> > them with a single bit they treat it as a byte and perform the logic=20
> > at a byte level. Heck, some of the calculators don't even allow hex=20
> > data input, treating everything as an ascii character.=20
> >=20
> > Finally I found this link...=20
> >=20
> > https://leventozturk.com/engineering/crc/=20
> >=20
> > Not very easy to use, much of the controls and labeling is rather=20
> > cryptic. Eventually by stumbling around I found it I didn't touch=20
> > anything on the controls other than selecting CRC32 and inputting the=
=20
> > data as binary, lsb first I could get an output that agreed with my=20
> > result before the final bit inversion used in CRC32.=20
> >=20
> > Wow! If I knew more about web page design maybe I would build a page=20
> > that makes this a bit easier.=20
> >=20
> > The standard example code is C, written to calculate a result one bit=
=20
> > at a time. However it won't work on less than a byte of data. In=20
> > fact, it isn't good for comparing to a true bitwise implementation=20
> > because before the loop where they calculate the result bitwise, the=20
> > input byte is xor'ed with the CRC register all at once mucking the=20
> > data for comparison purposes.=20
> >=20
> > Anyone else have similar problems?=20
> >=20
> > BTW, with the standard bit order CRC32, polynomial 0x04C11DB7, the=20
> > inverted output of an input "ABCD1234" (lsb first) would be=20
> > 16#E928FF7E. Anyone care to confirm that?
> I recall spending days trying to emulate the USB and ethernet CRCs. The=
=20
> Easics website is great at providing the polynomial but that is only=20
> half the story.=20
>=20
> What I have done is create all the variations of the starting word, the=
=20
> bit order and any other permutations in a CRC module all in parallel.=20
> Then streaming a known good packet and seeing which result was correct=20
> and choosing just that output.=20
>=20
> I've also breadboarded polynomials in c or c++ but that's tricky in=20
> conjuction with the Easic's polynomials.=20

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.=20

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.=20

--=20

Rick C.

-+ Get 1,000 miles of free Supercharging
-+ Tesla referral code - https://ts.la/richard11209

On Monday, December 14, 2020 at 6:52:53 PM UTC-5, Stef wrote:
> On 2020-12-14 gnuarm.del...@gmail.com wrote in comp.arch.fpga: 
> > On Monday, December 14, 2020 at 9:26:06 AM UTC-5, Stef wrote:
> [...]
> >> 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 ;-) ). 
> > 
> > Does your implementation actually work on a single bit input? Or is it 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.
> Yeah, you're right. I do the byte xor before the bitwise steps. So no good for 
> a direct bit-for-bit comparison, sorry.

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 then I haven't compiled a C program in a decade or more.  I might write a Forth program for this, but the need is largely satisfied.  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 explained.  The one web page that 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? 

-- 

Rick C.

+- Get 1,000 miles of free Supercharging
+- Tesla referral code - https://ts.la/richard11209

On 2020-12-15 gnuarm.del...@gmail.com wrote in comp.arch.fpga:
> On Monday, December 14, 2020 at 6:52:53 PM UTC-5, Stef wrote:
>> On 2020-12-14 gnuarm.del...@gmail.com wrote in comp.arch.fpga: 
>> > On Monday, December 14, 2020 at 9:26:06 AM UTC-5, Stef wrote:
>> [...]
>> >> 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 ;-) ). 
>> > 
>> > Does your implementation actually work on a single bit input? Or is it 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.
>> Yeah, you're right. I do the byte xor before the bitwise steps. So no good for 
>> a direct bit-for-bit comparison, sorry.
>
> That sounds like the universally available C version.

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.

> I did find a version somewhere that also used the incoming byte one bit at a time, but even then I haven't compiled a C program in a decade or more.  I might write a Forth program for this, but the need is largely satisfied.  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 explained.

It's not that hard ;-) : https://www.w3schools.com/


[your line length remains a pain with my slrn+vi combination ;-) ]
-- 
Stef    (remove caps, dashes and .invalid from e-mail address to reply by mail)

-- I love KATRINKA because she drives a PONTIAC.  We're going away
now.  I fed the cat.

On Tuesday, December 15, 2020 at 4:06:07 PM UTC-5, Stef wrote:
> On 2020-12-15 gnuarm.del...@gmail.com wrote in comp.arch.fpga:=20
> > On Monday, December 14, 2020 at 6:52:53 PM UTC-5, Stef wrote:=20
> >> On 2020-12-14 gnuarm.del...@gmail.com wrote in comp.arch.fpga:=20
> >> > On Monday, December 14, 2020 at 9:26:06 AM UTC-5, Stef wrote:=20
> >> [...]=20
> >> >> I just did a bitwise software solution because I did not want to wa=
ste=20
> >> >> space on a table and speed was not an issue. The above link is nice=
=20
> >> >> to check your results. (To check what version of CRC32 you just=20
> >> >> implemented ;-) ).=20
> >> >=20
> >> > Does your implementation actually work on a single bit input? Or is =
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.=20
> >> Yeah, you're right. I do the byte xor before the bitwise steps. So no =
good for=20
> >> a direct bit-for-bit comparison, sorry.=20
> >=20
> > That sounds like the universally available C version.
> That's what I thought too. But when I looked for it, all I found were=20
> table versions. So I just wrote the few lines of code based on some=20
> pseude code (I think it was from the CRC wiki). That was faster than=20
> trying to find a ready made solution.
> > I did find a version somewhere that also used the incoming byte one bit=
 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.
> It's not that hard ;-) : https://www.w3schools.com/=20

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


> [your line length remains a pain with my slrn+vi combination ;-) ]

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=20
sure the line length is=20
short enough.=20

Yeah, I'll try doing=20
that.

--=20

Rick C.

++ Get 1,000 miles of free Supercharging
++ Tesla referral code - https://ts.la/richard11209

On 16/12/2020 00:27, gnuarm.del...@gmail.com wrote:
> On Tuesday, December 15, 2020 at 4:06:07 PM UTC-5, Stef wrote:

> 
>> [your line length remains a pain with my slrn+vi combination ;-) ]
> 
> So does that mean you are using something odd for reading newsgroups?

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.

> 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.

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.

On 2020-12-15 gnuarm.del...@gmail.com wrote in comp.arch.fpga:
> On Tuesday, December 15, 2020 at 4:06:07 PM UTC-5, Stef wrote:
>> On 2020-12-15 gnuarm.del...@gmail.com wrote in comp.arch.fpga: 
>> > On Monday, December 14, 2020 at 6:52:53 PM UTC-5, Stef wrote: 
>> >> On 2020-12-14 gnuarm.del...@gmail.com wrote in comp.arch.fpga: 
>> >> > On Monday, December 14, 2020 at 9:26:06 AM UTC-5, Stef wrote: 
>> >> [...] 
>> >> >> 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 ;-) ). 
>> >> > 
>> >> > Does your implementation actually work on a single bit input? Or is it 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. 
>> >> Yeah, you're right. I do the byte xor before the bitwise steps. So no good for 
>> >> a direct bit-for-bit comparison, sorry. 
>> > 
>> > That sounds like the universally available C version.
>> 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.
>> > I did find a version somewhere that also used the incoming byte one bit at a time, but even then I haven't compiled a C program in a decade or more. I might write a Forth program for this, but the need is largely satisfied. 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 explained.
>> It's not that hard ;-) : https://www.w3schools.com/ 
>
> Yeah, like an HTML manual is all it takes... 
>
>
>> [your line length remains a pain with my slrn+vi combination ;-) ]
>
> 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.

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).


-- 
Stef    (remove caps, dashes and .invalid from e-mail address to reply by mail)

Nice guys finish last, but we get to sleep in.
		-- Evan Davis

On Wednesday, December 16, 2020 at 2:54:58 AM UTC-5, David Brown wrote:
> On 16/12/2020 00:27, gnuarm.del...@gmail.com wrote: 
> > On Tuesday, December 15, 2020 at 
4:06:07 PM UTC-5, Stef wrote: 
> 
> > 
> >> [your line length remains a pain 
with my slrn+vi combination ;-) ] 
> > 
> > So does that mean you are using 
something odd for reading newsgroups?
> 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.
> > 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.
> 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.

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.  

-- 

Rick C.

--- Get 1,000 miles of free Supercharging
--- Tesla referral code - https://ts.la/richard11209 

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 >=3D4.)


On Monday, December 14, 2020 at 2:02:23 PM UTC-7, gnuarm.del...@gmail.com w=
rote:
> On Monday, December 14, 2020 at 2:59:02 AM UTC-5, David Brown wrote:=20
> > On 13/12/2020 21:06, Anssi Saari wrote:=20
> > > "gnuarm.del...@gmail.com" <gnuarm.del...@gmail.com> writes:=20
> > >=20
> > >> Anyone else have similar problems?=20
> > >=20
> > > I've only used this one on FPGA designs: https://www.easics.com/crcto=
ol/=20
> > >=20
> > > It generates a VHDL or Verilog implementation. Selectable polynomial=
=20
> > > with some common ones predefined, selectable input data width.=20
> > >=20
> > >> BTW, with the standard bit order CRC32, polynomial 0x04C11DB7, the i=
nverted output of an input "ABCD1234" (lsb first) would be 16#E928FF7E. Any=
one care to confirm that?=20
> > >=20
> > > Not really. I don't have anything I trust handy for that. From some=
=20
> > > (software) experimentation years ago when I wanted to generate the sa=
me=20
> > > CRC32 as is used in zip, rar and sfv files (and also Python's crc32=
=20
> > > function in binascii package) the polynomial used was reversed from=
=20
> > > that, 0xEDB88320.=20
> > >=20
> > That's the joy of CRC. With the same bit size and polynomial, you can=
=20
> > bit reverse the data coming in, byte reverse the incoming data (if it i=
s=20
> > handled in larger lumps), bit reverse the generated crc, byte reverse=
=20
> > the generated crc, start with a non-zero shift register, and various=20
> > other options - in any combination. The result is equally strong=20
> > (though some people argue that starting with a non-zero shift register=
=20
> > is better because the crc of an all-zero input then varies by the lengt=
h=20
> > of the input).=20
> >=20
> > If you are handling the crc in two different ways (two different=20
> > implementations), you have to check that it really matches up, and be=
=20
> > prepared to fiddle the options a little until you get it right.=20
> >=20
> > But the actual implementation is simple. In software, you usually do=20
> > this a byte at a time, with a lookup table. In an FPGA, a bitwise CRC=
=20
> > is a simple linear feedback register and should be straightforward - I'=
d=20
> > expect an experienced FPGA designer will find it less effort to=20
> > implement it themselves than to use some random web page of questionabl=
e=20
> > quality. The key trick is to ignore the mathematical background for how=
=20
> > it works - polynomial division rings sound scary, but the implementatio=
n=20
> > is quite easy. (This means picking your polynomial from the wikipedia=
=20
> > page rather than guessing one yourself.)
> Funny that you talk about the number of ways to permute the algorithm and=
 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.=20
>=20
> Like I said in the first post, there is little on the Internet to support=
 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.=20
>=20
> That was the hard part, finding that one web site.=20
> https://leventozturk.com/engineering/crc/=20
>=20
> --=20
>=20
> Rick C.=20
>=20
> + Get 1,000 miles of free Supercharging=20
> + Tesla referral code - https://ts.la/richard11209

On 15/12/2020 15:44:55, gnuarm.del...@gmail.com wrote:
> On Tuesday, December 15, 2020 at 7:23:13 AM UTC-5, Mike Perkins
> wrote:
>> On 12/12/2020 21:36:11, gnuarm.del...@gmail.com wrote:
>>> I had a newbie working on a bit wise CRC32 implementation and he 
>>> could not get the results of any of the many online CRC32
>>> generators available. So I coded up the same algorithm and tried
>>> it myself with similar results.
>>> 
>>> I tried digging around and found little that I could use to
>>> either evaluate an algorithm or to generate comparison data other
>>> than the final result. What I needed was something that could
>>> produce a result for each input bit. Most of the reference
>>> designs are for sequential languages which are byte oriented.
>>> Even if you present them with a single bit they treat it as a
>>> byte and perform the logic at a byte level. Heck, some of the
>>> calculators don't even allow hex data input, treating everything
>>> as an ascii character.
>>> 
>>> Finally I found this link...
>>> 
>>> https://leventozturk.com/engineering/crc/
>>> 
>>> Not very easy to use, much of the controls and labeling is
>>> rather cryptic. Eventually by stumbling around I found it I
>>> didn't touch anything on the controls other than selecting CRC32
>>> and inputting the data as binary, lsb first I could get an output
>>> that agreed with my result before the final bit inversion used in
>>> CRC32.
>>> 
>>> Wow! If I knew more about web page design maybe I would build a
>>> page that makes this a bit easier.
>>> 
>>> The standard example code is C, written to calculate a result one
>>> bit at a time. However it won't work on less than a byte of data.
>>> In fact, it isn't good for comparing to a true bitwise
>>> implementation because before the loop where they calculate the
>>> result bitwise, the input byte is xor'ed with the CRC register
>>> all at once mucking the data for comparison purposes.
>>> 
>>> Anyone else have similar problems?
>>> 
>>> BTW, with the standard bit order CRC32, polynomial 0x04C11DB7,
>>> the inverted output of an input "ABCD1234" (lsb first) would be 
>>> 16#E928FF7E. Anyone care to confirm that?
>> 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 is the problem.  There is no one correct result.  Even the
> online checkers don't have a universal one right answer, some of them
> can be permuted in various combinations.  In one case I had two
> agreeing and a third would not provide the same result even when I
> thought I had all three configured the same 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/simpler to think about in the reversed configuration.  This
> will result in a bit reversed remainder.  Combine that with the
> options of starting pattern, inverting 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 into  providing an
> agreeable result.

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.


-- 
Mike Perkins
Video Solutions Ltd
www.videosolutions.ltd.uk