1
$\begingroup$

I tried to find information about how features of a CRC polynomials influence computation speed of implementations.

It is obvious that (depending from the CPU architecture the algorithm runs on) algorithms can be optimized for special CRC widths.

However, even when comparing CRC polynomials of the same width there still seems to exist differences in computation speed:

  1. I read a statement that low polynomial weights would increase computation speed.
  2. Also Prof. Koopman wrote on his 6sub8 CRC page: "Consider only polynomials with bits set in the bottom 8 bits (in addition to the topmost bit). This can help speed up computation and reduce lookup table sizes for CRC calculations in application programs."

I can see why pre-calculated CRC tables can be more compact using a sub8 polynomial. But I could not wrap my mind around the speed related statements. All implementations I had a look at (various C implementation of bit-wise and table-based algorithms) seem not to benefit from low-weight or sub8 polynomials. Maybe I missed the point or there are environments (like other algorithms, hardware implementations, special CPU architectures) that would benefit.

My question: Given a certain CRC width, in which way and under which circumstances does a low polynomial weight and/or a sub8 polynomial speed-up the computation of a CRC?

Improve this question
$\endgroup$
5
  • $\begingroup$ Can I ask how it can help reducing table size? You can build table for such polynomial, I guess that it will be as dense as any other one. $\endgroup$
    – Bulat
    Commented Mar 12, 2019 at 12:24
  • $\begingroup$ I tried it with a 32 bit sub8 polynomial. Each table entry only uses the lower 16 bit which reduces memory consumption by 50%. $\endgroup$
    – Silicomancer
    Commented Mar 12, 2019 at 12:41
  • $\begingroup$ This sounds like two separate questions. I think it might be better to ask them as two separate questions: how does a low weight speed up computation; and how does a sub8 polynomial speed up computation? $\endgroup$
    – D.W. ♦
    Commented Mar 28, 2019 at 22:30
  • $\begingroup$ I am not sure about this. They may be connected. Because sub-width polynomials tend to have a low weight as well. Anyway nobody seems to care or being able to answer yet :( $\endgroup$
    – Silicomancer
    Commented Mar 29, 2019 at 7:50
  • $\begingroup$ I'd be surprised that you can obtain a measurable speedup with different polynomials on a general-purpose CPU. And table lookup might be slower than direct computation. $\endgroup$
    – user16034
    Commented Dec 20, 2022 at 10:07

1 Answer 1

Reset to default
2
$\begingroup$

The speed issue would depend on the hardware / processor. For CRC, what is needed is carryless multiply (CLMUL), and I assume most processors that have carryless multiplies, which date back to 2008 for X86 processors (pclmulqdq using xmm registers) the multiply time is fixed. For a typical hardware implementation, since the multiply is carryless, there's no propagation delay related to carry operations and all the XOR operations occur in parallel.

For standard multiplies (with carry), old processor multiply times were affected by the weight of the multiplier, but multiply times on processors since around 2010 or a bit before have fixed multiply times (for X86, it's 3 clocks). I'm not aware of a carryless multiply that isn't fixed in time, but it could exist on some processor I'm not aware of.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.