CRC is an FPGA PITA...

[gnuarm.del...@gmail.com]

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?

--

Rick C.

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

 

[Anssi Saari]

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

 

[gnuarm.del...@gmail.com]

On Sunday, December 13, 2020 at 3:06:28 PM UTC-5, 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.

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 code I ended up with is only three assignments and uses two clock enables to allow calculating the bits and then shifting out the result.

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.

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 bother with the initial register state... or the register at all (which makes it more general) or the final inversion. I think we have our code working, but I may give this a try in the test bench for a reference.

Thanks

--

Rick C.

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

 

[David Brown]

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

 

[Stef]

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

 

[gnuarm.del...@gmail.com]

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

--

Rick C.

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

 

[gnuarm.del...@gmail.com]

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

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.

--

Rick C.

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

 

[David Brown]

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/

 

[Stef]

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!

 

[Mike Perkins]

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

 

[gnuarm.del...@gmail.com]

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.

--

Rick C.

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

 

[gnuarm.del...@gmail.com]

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

 

[Stef]

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.

 

[gnuarm.del...@gmail.com]

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.

--

Rick C.

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

 

[David Brown]

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.

 

[Stef]

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

 

[gnuarm.del...@gmail.com]

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

 

[Kevin Neilson]

The resources on CRCs are terrible and they explain things poorly. I\'ve had the opposite problem--the last one I did had to compute a CRC with 512 bits 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 GF(2)) by a 512x32 binary matrix. I compute these generator matrices in Matlab: each row of the matrix is a shifted and reduced version of the generator poly. But the textbooks never seem to cover this stuff. The permutations 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 questions:

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 multiplication of the poly by x, and a subtraction, which is an XOR. Also, Horner\'s Method is being used, which isn\'t always clear.)
2. How is XOR a subtraction? (In a characteristic-2 field, addition and subtraction are the same.)
3. Why are we doing a modulo? (The point is to make the codeword, which is 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 field 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 have a good checksum, but the CRC will show the error if the minimum Hamming distance of the CRC code is >=4.)


On Monday, December 14, 2020 at 2:02:23 PM UTC-7, 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. 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/

--

Rick C.

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

 

[Kevin Neilson]

The resources on CRCs are terrible and they explain things poorly. I\'ve had the opposite problem--the last one I did had to compute a CRC with 512 bits 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 GF(2)) by a 512x32 binary matrix. I compute these generator matrices in Matlab: each row of the matrix is a shifted and reduced version of the generator poly. But the textbooks never seem to cover this stuff. The permutations 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 questions:

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 multiplication of the poly by x, and a subtraction, which is an XOR. Also, Horner\'s Method is being used, which isn\'t always clear.)
2. How is XOR a subtraction? (In a characteristic-2 field, addition and subtraction are the same.)
3. Why are we doing a modulo? (The point is to make the codeword, which is 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 field 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 have a good checksum, but the CRC will show the error if the minimum Hamming distance of the CRC code is >=4.)


On Monday, December 14, 2020 at 2:02:23 PM UTC-7, 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. 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/

--

Rick C.

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

 

[Kevin Neilson]

The resources on CRCs are terrible and they explain things poorly. I\'ve had the opposite problem--the last one I did had to compute a CRC with 512 bits 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 GF(2)) by a 512x32 binary matrix. I compute these generator matrices in Matlab: each row of the matrix is a shifted and reduced version of the generator poly. But the textbooks never seem to cover this stuff. The permutations 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 questions:

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 multiplication of the poly by x, and a subtraction, which is an XOR. Also, Horner\'s Method is being used, which isn\'t always clear.)
2. How is XOR a subtraction? (In a characteristic-2 field, addition and subtraction are the same.)
3. Why are we doing a modulo? (The point is to make the codeword, which is 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 field 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 have a good checksum, but the CRC will show the error if the minimum Hamming distance of the CRC code is >=4.)


On Monday, December 14, 2020 at 2:02:23 PM UTC-7, 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. 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/

--

Rick C.

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