Subject: [rddp] CRC32C Calculation "Burden"

From: Caitlin Bestler <[email-masked]>
Date: Tue, 6 May 2003 20:33:47 -0500

RFC 3385 section 8.2 gives a parallel implementation of
CRC-32c. It takes as input the next 32 bits of data and the
current 32 bit CRC. The result is a new 32 bit CRC.

The algorithm presented is based on the fact that each bit
of the resulting CRC is an XOR of a subset of the input
bits (the original CRC and new data).

If you examine the formulas, though, you will realize that
the reverse is also true. Each input bit effects a subset of
the result.

Further the contribution of any set of input bits is an xor
of the contribution of each of those bits. More precisely:

    contributionOf [x^y] = contributionOf[x] ^ 
                           contributionOf[y].
    
These could be rolled into a large table, resulting in a
very short calculation:

    newCRC = contributionOfCRC[oldCRC] ^ 
             contributionOfData[newData].
    
Of course that's 2 tables with 2**32 entries. Probably a bit
too large. Working 16 bits at a time:

    newCRC.high = contributionOfCRChigh[oldCRC.high] ^
                  contributionOfCRClow[oldCRC.low] ^
                  contributionOfDataHigh[newData.high] ^
                  contributionOfDataLow[newData.low];
                  
That produces one indexed lookup and one XOR operation per
byte. Any size can be pre-factored. The Linux code for SCTP
uses 256 entry tables.  Smaller tables result in more
operations, but increase the ability to keep the lookup
table cached.

If you go down to calculating the effect bit-by-bit the
"tables" become in-line constants. This minimizes random
access to code space for constant tables, but increases the
number of calculations. Of course many processors can
perform numerous calculations for each non-cached memory
fetch, so the tradeoff is complex.

The optimum balance is dependent on the memory
architecture. In particular, whether fetches from constant
tables in code-space can execute in parallel with fetches
of the new data byte. The CRC itself would remain in a
register or at least cached.

But whatever combination is selected, there are at most a
few simple operations per 32 bits, and no additional memory
touches to uncached data space are required.

Given those two factors, I cannot see how a CRC32C
calculation can possibly be considered an unreasonable
burden for software implementations.

Note, the referenced Linux implementation can be found at:
http://www.linuxhq.com/kernel/v2.5/33/net/sctp/crc32c.c

Caitlin Bestler
http://asomi.com/CaitlinBestler/
_______________________________________________
rddp mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/rddp

---

From: "John A. Thodiyil" <[email-masked]>
Date: Wed, 7 May 2003 14:07:53 -0700

The Gallois field approach to CRC32 calculation is
very fast, not withstanding my suggestion to making
CRC optional, just incase its enabled.

-John

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]On Behalf Of
Caitlin Bestler
Sent: Tuesday, May 06, 2003 6:34 PM
To: [email-masked]
Subject: [rddp] CRC32C Calculation "Burden"

    

                  

Caitlin Bestler