How to handle a data packet while calculating CRC.

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
Hi,  

I'm trying to process a Ethernet type package. Suppose if i have detected S
FD and now have a  <1600Byte  data.

I'm extracting different package element(ds_addr,src_addr,etc) concatenatin
g them in a long shift register and at same time passing it to a fifo to bu
ffer and calculating crc32 which will take some clock cycles(xoring and shi
fting). Now if calculated CRC matched what is received, pass data to nxt st
age else rst fifo.
  

Is there a better technique for it?

Thank-You in advance.

Re: How to handle a data packet while calculating CRC.
On 2018-03-12 12:02, yogesh tripathi wrote:
Quoted text here. Click to load it

Hi

Calculate CRC on-the-fly together with incoming data.

Adam

Re: How to handle a data packet while calculating CRC.

Quoted text here. Click to load it
ed SFD and now have a  <1600Byte  data.
Quoted text here. Click to load it
ating them in a long shift register and at same time passing it to a fifo t
o buffer and calculating crc32 which will take some clock cycles(xoring and
 shifting). Now if calculated CRC matched what is received, pass data to nx
t stage else rst fifo.
Quoted text here. Click to load it

Hi Adam,

 "Calculate CRC on-the-fly together with incoming data." , can you elaborat
e it a bit more.
I'm getting a 8bit data in one clock cycle from the decoder. Now for crc i  
need serial shift register.  

Re: How to handle a data packet while calculating CRC.
Implement this transition function as your 8-bit data is coming in on each  
cyle:
https://en.wikipedia.org/wiki/Cyclic_redundancy_check#CRC-32_algorithm

Or you could have a 2x clock for the inner loop to fit the table access, or
 compute everything one byte per clock cycle by pipelining the accesses suc
h as:
crc32_now = crc32_prev[23:0] XOR output_from_sram_one_cycle_delay
lookup_sram_index_next = crc32_now[7:0] XOR data_from_packet
crc32_prev = crc32_now

Then make sure you handle the reset conditions on packet start, end of pack
et, etc.

On Tuesday, March 13, 2018 at 12:05:15 AM UTC-4, yogesh tripathi wrote:

Quoted text here. Click to load it
cted SFD and now have a  <1600Byte  data.
Quoted text here. Click to load it
enating them in a long shift register and at same time passing it to a fifo
 to buffer and calculating crc32 which will take some clock cycles(xoring a
nd shifting). Now if calculated CRC matched what is received, pass data to  
nxt stage else rst fifo.
Quoted text here. Click to load it
ate it a bit more.
Quoted text here. Click to load it
i need serial shift register.


Re: How to handle a data packet while calculating CRC.
On Mon, 12 Mar 2018 21:05:09 -0700 (PDT), yogesh tripathi  
Quoted text here. Click to load it
for crc i =
Quoted text here. Click to load it
You have some options:
1. Use a precalculated table (rainbow table) for CRC. With 8 bit the  
size of the table is usually acceptable.
2. Use the 8x clock for the CRC calculating shift register (not  
recommended here).
3. Use a pipelined CRC calculation: The calc module is 8 times in  
parallel and you get the final result with eight clocks latency.

Bart

Re: How to handle a data packet while calculating CRC.
Quoted text here. Click to load it

Table methods are very likely NOT the correct solution for FPGA
implementations.  Those methods are tuned for SW solutions.

CRCs in hardware are actually quite easy / low resources.  Shifting
through the 8 bits in one clock cycle will probably work just fine.
There's online websites that have "CRC" calculators which can  
do some of this work for you. But I find just coding up the  
algorithm in verilog / VHDL to be more compact and clear.

If that doesn't work - i.e. you're not hitting you're desired clock
frequencies -  then Bart's suggestion of pipelining the calc is valid.
That can be a little trickier, but still doable.  I don't think you'll
need to go this far, unless you're trying to hit some high clock rates.

Regards,

Mark



Re: How to handle a data packet while calculating CRC.
On Tue, 13 Mar 2018 19:28:17 -0000 (UTC), snipped-for-privacy@sonic.net (gtwrek)  
wrote:
Quoted text here. Click to load it

Sorry for respeak.Of course is the usage of a lookup-table a valid  
design technic for FPGAs.
Maybe not in the range of megabytes, but e.g. for 8 bit input and 8  
bit output it's very acceptable.
One example: a low fidelity DDS usually use a small ROM with a sine  
table...

Bart Fox

Re: How to handle a data packet while calculating CRC.
Quoted text here. Click to load it

Table lookups, in general, are a very valid tool for some hardware
solutions.  Just not for CRCs.  A "brute force" table lookup for an
8-bit input, 8-bit CRC would require 2**16 entries by 8 bits.  So a  
64 KByte table.  Not efficient.  So one looks up many of the  
"Software" table generated techniques to reduce the requirements.  
Problem is those techniques are tuned to optimizes SW, not HW.  

... All to replace something less than a 100 LUT6s, and 8 FFs.  

CRCs in hardware are very efficient just coded brute force.

Regards,

Mark


Re: How to handle a data packet while calculating CRC.
Den fredag den 16. marts 2018 kl. 01.29.54 UTC+1 skrev gtwrek:
Quoted text here. Click to load it

http://www.sunshine2k.de/articles/coding/crc/understanding_crc.html#ch6

doesn't look too bad




Re: How to handle a data packet while calculating CRC.
Quoted text here. Click to load it

My favorite reference is:
http://www.ross.net/crc/download/crc_v3.txt

Hardware engineers should STOP reading after section 8.  That's all you
need to know as a hardware designer.  Everything after section 8 is
dedicated to software optimizations where one doesn't have free access
to any bit - like we do in hardware.

Regards,

Mark


Re: How to handle a data packet while calculating CRC.
On 16/03/18 01:29, gtwrek wrote:
Quoted text here. Click to load it

No, it is 8-bit in (the address), 32-bit out for a 32-bit CRC - 1024 bytes.

Quoted text here. Click to load it

CRC's in hardware, using a shift register, are very efficient if your  
data is coming in a bit at a time.  If you have data in memory or  
arriving in a wider path, table lookup can be very useful.  You can  
choose your sizes to give a balance between speed and size.  For  
example, you could use 4-bit in, 32-bit out tables and run 4 bits at a  
time.  (Such a solution can be pipelined for greater throughput.)


Re: How to handle a data packet while calculating CRC.
Quoted text here. Click to load it

So the "brute force" table is even larger.  

Quoted text here. Click to load it

I don't agree. Those table methods described in all those papers you
find are tuned for software solutions, not hardware.   It's quite easy  
to handle one-bit, or N-bits at a time in hardware.

Code up a simple amount of logic to shift one bit at a time - in whatever
language.

next_crc = shift_crc( current_crc, new_data_bit_in );

The shift_crc function is very simple to implement in verilog/vhdl.

Now for N bits at a time, stick a 'for' loop around that function
call... Done.  The for loop (as always in hardware) describes parallel
hardware, not sequential operation.  And it works to do exactly what is
desired. You get a clear description of what's happening in shockingly
few lines of code.  It reproduces what all those online CRC generators
spit out as a glob of random XOR code....  

If that's not fast enough, then look at pipelining it.  Table methods
are hardly ever the right solution for CRCs in hardware.  

Burning even one block memory for a CRC calculation in hardware just seems
absurdly excessive to me.  But maybe your designs have a lot of spare
block memories, (and few LUTs available).

Regards,

Mark


Re: How to handle a data packet while calculating CRC.
On 16/03/18 15:52, gtwrek wrote:
Quoted text here. Click to load it

No, they are not.

Let's take the simple case of 8-bit CRC, with data coming in 8-bit
lumps.  This is the C code for it:

static const uint8_t crcTable[256] = {
    0x00, 0x8d, 0x97, 0x1a, 0xa3, 0x2e, 0x34, 0xb9,
    // ...
}

uint8_t calcCrc(uint8_t crc, const uint8_t * p, size_t n)
{
    while (n--) {
        crc = crcTable[crc ^ *p++];
    }
    return crc;
}

In hardware terms, that means you take your incoming 8-bit data, xor it
with your 8-bit current crc, then use that as the address for the lookup
in your 256-entry (8-bit address, 8-bit data) table.  The value from the
table is the new crc to use for the next round of 8-bit data.

The table is 256 bytes - 2K bits, if you prefer.  Not 2^16.

I suspect that what you are missing in your understanding here is that
you do not need a table that combines the current crc and the incoming
byte independently - /that/ would need a 2^16 entry table.  You take
advantage of the way the CRC is defined to combine the parts with xor
(using plain logic) first.

If you have a wider CRC and data coming in as 8-bit lumps, you need more
than one 256-entry table and you combine the steps with xor's.  So for a
32-bit CRC, you can use 4 256-entry, 8-bit wide lookup tables.  The four
lookups and the xors between them can easily be pipelined.

You can reduce the depth of the pipelines by having bigger tables - 2^16
entry tables will half the pipeline depth, but is unlikely to be worth
it due to the size of the tables.  You can also use smaller tables and
more steps, but 8-bit lookups often work well.  It is also possible to
take advantage of wider tables if your incoming data is in wider batches.

Quoted text here. Click to load it

I haven't looked at the particular papers here.  One-bit CRC hardware
is, as you say, quite easy to make and it is fine if your data is coming
in 1 bit at a time.  But it is much slower if the data is coming in
parallel bunches as is often the case for high-speed serial lines.  If
you have 1 GBit Ethernet, it is far easier to handle data that is 8-bit
wide at 125 MHz than data that is 1-bit wide at 1 GHz.

Quoted text here. Click to load it


Re: How to handle a data packet while calculating CRC.
Quoted text here. Click to load it

In FPGA, almost all methods are table methods.
But not always the same ones as software.

Re: How to handle a data packet while calculating CRC.
On 20/03/18 16:27, mac wrote:
Quoted text here. Click to load it

(Your quoting is jumbled.  You posted a follow-up to my post, but quoted
from gtwrek's post.  And you failed to give proper attributions.  Please
try to get this right - it is not hard, it is common courtesy, and it
makes newsgroup threads much easier to follow.  Thanks.)


Re: How to handle a data packet while calculating CRC.
Quoted text here. Click to load it

Sometimes email/nntp/forums makes these technical dicussions difficult.
As some background - I've written many CRCs designs in hardware for  
both ASICs, and FPGAs.  Every one of them uses the "plain-vanilla"  
method as described in many of the CRC papers.  The only twist
is, as I've tried to describe, is putting the single-shift
implementation in a for loop, to allow 'N' bits to be calculated in a
single clock cycle.  

This "twist" is shockingly simple to write in HDLs.  The core kernel of
a (generic) CRC - shifting through N-bits at a time is really just about
10 (simple) lines of code.  No online-generators needed - that spit out gobs  
of (unreadable) XOR gates.

The "table" methods we've been discussing, are all solutions aimed at
software.  Software where it's difficult to do (many) parallel XORs of  
any random bits.  But that's something that hardware excels at.  

Taking those software solutions, and retargetting them back at hardware,
is at best case, overcomplicating something very simple.  At worst case  
quite costly.

I've never written a table method for calculating CRCs (because as I've
asserted it's pointless for hardware), but I quite understand the underlying  
concepts and what they are doing.

Some numbers to back things up.
I have a generic crc module that's used all over the place.  I  
synthesized in Vivado various version of a 32-bit CRC.  (The one used in  
the MPEG-2 spec with  POLY=0x4C11DB7)

I targetting something high-speed to make sure the tools are
actually trying to do at least some optimizations.  Targetted 2ns clocks
(500 MHZ) in a Virtex7 device

Test 1:
1 bit at a time:  
CLB LUTs*               |  151  
CLB Registers           |   64  
Worst case timing slack: 0.754ns
  
You'll first note that I use twice as many registers than seems
neccesary.  This is because the way it's been coded it stores both the
"augmented" and "non-augmented" CRC in FFs.  

Test 2:
8 bits at a time:
CLB LUTs*               |  172
CLB Registers           |   64  
Worst case timing slack: 0.270ns

Notice, not much delta in LUT usage.  One thing to note - the baseline
may seem high.  After all for a single bit shift, you only need one XOR
gate per (high POLY bit).  The augmentation adds more complexity too.
But, in the end the overhead "housekeeping", if you will, actually is
probably what's dominating the logic here.  Things like loading the
INIT value, holding the current value when no new data is available,
etc.  Plus a LUT6 is under-utilized to do just 2-bit XOR.

Test 3:
32-bits at a time:
CLB LUTs*               |  259
CLB Registers           |   64
Worst case timing slack: 0.332ns

A few more LUTs.  But paradoxically, the timing's better.  
Decided to go for broke, and really up the DATA WIDTH:

Test 4:
512-bits at a time
CLB LUTs*               | 1734
CLB Registers           |   64
Worst case timing slack: 0.188ns

So even taking a very large datapath, things are fine.

Adding a "software" LUT method at it's very baseline, adds 1 BRAM block
to the solution - 36Kbits - a very large, IMHO resource.  I would argue
that for such a software solution aimed at the "Test 3 above (32-bits at a
time)" solution would likely still consume a signficant amount  
of CLB LUTs - just to handle the "housekeeping" and further logic behind
the software LUT.  I'd also argure that it would very likely run slower  
too, as BRAMs are in general slower than logic.  

Well, don't use a BRAM you might ask - use the CLB logic.  I'd argue
that this solution, to the tools is the same thing as my 10-line
"plain-vanilla", just overly complicated, and unclear, and likely take
the tool longer to achieve the same solution (if at all).

Those software implementations are quite interesting methods, and I
quite like reading up at the clever tricks being performed.  But none
of that is neccesary in hardware where you have free-access to any bit,
and can freely perform many things in parallel.

Regards,

Mark


Re: How to handle a data packet while calculating CRC.
On 13/03/2018 04:05, yogesh tripathi wrote:

Quoted text here. Click to load it

Not necessarily, have a look at:
   http://www.easics.com/webtools/crctool

I've used this, albeit a few years ago and the website has changed since.

If I recall you have to invert and swap the bit order to get the correct  
CRC. I used a simulator to check the permutations until I got it right.

If you have 8bit data you can generate the CRC on the fly at the same rate.


--  
Mike Perkins
Video Solutions Ltd
We've slightly trimmed the long signature. Click to see the full one.
Re: How to handle a data packet while calculating CRC.
On Wednesday, March 14, 2018 at 1:18:40 AM UTC+5:30, Mike Perkins wrote:
Quoted text here. Click to load it

e:
Quoted text here. Click to load it
cted SFD and now have a  <1600Byte  data.
Quoted text here. Click to load it
enating them in a long shift register and at same time passing it to a fifo
 to buffer and calculating crc32 which will take some clock cycles(xoring a
nd shifting). Now if calculated CRC matched what is received, pass data to  
nxt stage else rst fifo.
Quoted text here. Click to load it
borate it a bit more.
Quoted text here. Click to load it
c i need serial shift register.
Quoted text here. Click to load it
  
Quoted text here. Click to load it
e.

Thank-You Mike.
The link gives a provide a HDL package which is basically a Parallel LFSR.  
You know any related text how to generate a custom LFSR for these CRC ,just
 for better understanding.

Re: How to handle a data packet while calculating CRC.
On 15/03/2018 11:28, yogesh tripathi wrote:
Quoted text here. Click to load it

Quoted text here. Click to load it

I looked into this a long while ago and gave up!

A LFSR is a simple concept in it's own right but I didn't have time to  
decipher a Parallel LFSR. I made the choice of using the result rather  
than spend time trying to understand something I would only use once in  
a long while.

I'm sure there are proof and theorems on the 'net somewhere!


--  
Mike Perkins
Video Solutions Ltd
We've slightly trimmed the long signature. Click to see the full one.
Re: How to handle a data packet while calculating CRC.

Quoted text here. Click to load it

So look for CRC implementation able to process 8bits ( byte ) in single  
clock and store data in same time to fifo and to CRC unit.

Hint: Online CRC VHDL generator. There is many.

Best regards



Site Timeline