CRC is an FPGA PITA

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

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 b=
yte and perform the logic at a byte level.  Heck, some of the calculators d=
on't even allow hex data input, treating everything as an ascii character. =
=20

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 c=
ontrols other than selecting CRC32 and inputting the data as binary, lsb fi=
rst I could get an output that agreed with my result before the final bit i=
nversion used in CRC32. =20

Wow!  If I knew more about web page design maybe I would build a page that =
makes this a bit easier. =20

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 lo=
op where they calculate the result bitwise, the input byte is xor'ed with t=
he CRC register all at once mucking the data for comparison purposes. =20

Anyone else have similar problems?=20

BTW, with the standard bit order CRC32, polynomial 0x04C11DB7, the inverted=
 output of an input "ABCD1234" (lsb first) would be 16#E928FF7E.  Anyone ca=
re to confirm that?=20

--=20

Rick C.

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

"gnuarm.del...@gmail.com" <gnuarm.deletethisbit@gmail.com> writes:

> Anyone else have similar problems? 

I've only used this one on FPGA designs: https://www.easics.com/crctool/

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

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

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.

On Sunday, December 13, 2020 at 3:06:28 PM UTC-5, Anssi Saari wrote:
> "gnuarm.del...@gmail.com" <gnuarm.del...@gmail.com> writes:=20
>=20
> > Anyone else have similar problems?
> I've only used this one on FPGA designs: https://www.easics.com/crctool/=
=20
>=20
> It generates a VHDL or Verilog implementation. Selectable polynomial=20
> with some common ones predefined, selectable input data width.

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

> > BTW, with the standard bit order CRC32, polynomial 0x04C11DB7, the inve=
rted output of an input "ABCD1234" (lsb first) would be 16#E928FF7E. Anyone=
 care to confirm that?
> 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 same=
=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.

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

Thanks

--=20

Rick C.

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

On 13/12/2020 21:06, Anssi Saari wrote:
> "gnuarm.del...@gmail.com" <gnuarm.deletethisbit@gmail.com> writes:
> 
>> Anyone else have similar problems? 
> 
> I've only used this one on FPGA designs: https://www.easics.com/crctool/
> 
> It generates a VHDL or Verilog implementation. Selectable polynomial
> with some common ones predefined, selectable input data width.
> 
>> 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? 
> 
> 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.
> 

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

On 2020-12-14 David Brown wrote in comp.arch.fpga:
> On 13/12/2020 21:06, Anssi Saari wrote:
>> "gnuarm.del...@gmail.com" <gnuarm.deletethisbit@gmail.com> writes:
>> 
>>> Anyone else have similar problems? 
>> 
>> I've only used this one on FPGA designs: https://www.easics.com/crctool/
>> 
>> It generates a VHDL or Verilog implementation. Selectable polynomial
>> with some common ones predefined, selectable input data width.
>> 
>>> 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? 
>> 
>> 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.
>> 
>
> 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).

Yes there is no single "CRC32", there are many. This page gives a
nice overview:
https://reveng.sourceforge.io/crc-catalogue/17plus.htm#crc.cat-bits.32


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

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


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

/pub/lunch

On Monday, December 14, 2020 at 2:59:02 AM UTC-5, David Brown wrote:
> 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/crctool=
/=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 inv=
erted output of an input "ABCD1234" (lsb first) would be 16#E928FF7E. Anyon=
e 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 same=
=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
> >
> 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 is=
=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 length=
=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 questionable=
=20
> quality. The key trick is to ignore the mathematical background for how=
=20
> it works - polynomial division rings sound scary, but the implementation=
=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 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. =20

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

That was the hard part, finding that one web site.=20
https://leventozturk.com/engineering/crc/=20

--=20

Rick C.

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

On Monday, December 14, 2020 at 9:26:06 AM UTC-5, Stef wrote:
> On 2020-12-14 David Brown wrote in comp.arch.fpga:=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/crctoo=
l/=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 in=
verted output of an input "ABCD1234" (lsb first) would be 16#E928FF7E. Anyo=
ne 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 sam=
e=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
> >=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).
> Yes there is no single "CRC32", there are many. This page gives a=20
> nice overview:=20
> https://reveng.sourceforge.io/crc-catalogue/17plus.htm#crc.cat-bits.32
> > 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.)
> I just did a bitwise software solution because I did not want to waste=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

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

--=20

Rick C.

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

On 14/12/2020 22:02, gnuarm.del...@gmail.com wrote:
> On Monday, December 14, 2020 at 2:59:02 AM UTC-5, David Brown wrote:
>> On 13/12/2020 21:06, Anssi Saari wrote:
>>> "gnuarm.del...@gmail.com" <gnuarm.del...@gmail.com> writes:
>>> 
>>>> Anyone else have similar problems?
>>> 
>>> I've only used this one on FPGA designs:
>>> https://www.easics.com/crctool/
>>> 
>>> It generates a VHDL or Verilog implementation. Selectable
>>> polynomial with some common ones predefined, selectable input
>>> data width.
>>> 
>>>> 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?
>>> 
>>> 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.
>>> 
>> 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.)
> 
> 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.

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, we
> had one error in the code which I found by inspection... eventually.
> That was only perhaps a quarter of the work though.  The vast
> majority was trying to understand what all the references were doing
> since they often don't actually explain 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 think this is
> because they are software people who are only thinking of CRC
> calculations on files of characters.
> 
> 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 each stage of the computation.
> 
> That was the hard part, finding that one web site. 
> https://leventozturk.com/engineering/crc/
> 

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.

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

Disco oil bussing will create a throbbing naugahide pipeline running
straight to the tropics from the rug producing regions and devalue the dollar!

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.


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