Bug 1776

Summary: improve crc performance for CsmaNetDevice in emulation mode
Product: ns-3 Reporter: Tom Henderson <tomh>
Component: csmaAssignee: Tom Henderson <tomh>
Status: RESOLVED FIXED    
Severity: enhancement CC: piotr.jerzy.jurkiewicz
Priority: P5    
Version: pre-release   
Hardware: PC   
OS: Linux   
Attachments: copyright added for CRC table code

Description Tom Henderson 2013-10-20 09:34:47 UTC 
From Piotr's GSoC project:

https://gist.github.com/piotrjurkiewicz/6655299

Explanation (copy-pasted from Piotr's email to ns-developers):

First, in CsmaNetDevice::Receive() function CheckFcs() is called two times, line after line repeatedly:

702  trailer.CheckFcs (packet);
703  bool crcGood = trailer.CheckFcs (packet);

I assume that it is programmer's mistake. Removing of the additional call brings x1.32 performance improvement*.

Second, implementation of CRC32 algorithm used is EthernetTrailer::DoCalcFcs() is far from the optimal one.

Helpful comparison: http://create.stephan-brumme.com/crc32/

Current implementation in EthernetTrailer uses bitwise "Branch-free" algorithm. However, we do not really need a bitwise algorithm - we can operate on bytes (Ethernet frames are sized in bytes). Thus we can use "Standard Implementation" algorithm.

Replacing of the algorithm brings additional x1.85 performance improvement*. Furthermore, I rename the function calculating CRC to CRC32Calculate() and move it to the ns3 namespace. I do that in order to keep consistence with the existing function CRC8Calculate().

* Performance tests were performed in the following configuration:

[tap0]---[TapBridge-CsmaNetDevice<------->CsmaNetDevice-TapBridge]---[tap1]

using iperf (TCP mode) between two tap interfaces. On 3.8 GHz IvyBridge processor overall performance improved from 197 Mbit/s to 482 Mbit/s.

The patch is available here:
http://gist.github.com/piotrjurkiewicz/6655299
Comment 1 Tom Henderson 2013-10-20 09:38:56 UTC 
I would like to find the correct attribution/copyright for this table code as I suspect it has been copied from somewhere.

Does it derive from BSD?

http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/libkern/crc32.c

Or was it computed from something like this?

http://www.ross.net/crc/download/crc_v3.txt

other similar code:
http://git.lpclinux.com/cgit/apex-1.6.8-lpc313x/tree/src/mach-lpc313x/drv-crc32.c
Comment 2 Piotr Jurkiewicz 2013-10-23 20:47:35 UTC 
I came across this table in many sources. As I remember, I cut out this table from Stephan Brumme's examples, whose site I referenced above.

http://create.stephan-brumme.com/crc32/Crc32.cpp

This is the first sub-table of Crc32Lookup table (line 197).
Comment 3 Tom Henderson 2013-11-03 17:54:56 UTC 
Created attachment 1693 [details]
copyright added for CRC table code

This patch adds the following comment to crc32.cc, preceding the table:

+/*
+ * Note:  CRC tables such as below are found in many projects;
+ * below is the oldest reference (and copyright) to original work 
+ * of this nature that we could find.
+ *
+ * COPYRIGHT (C) 1986 Gary S. Brown.  You may use this program, or
+ * code or tables extracted from it, as desired without restriction.
+ */
Comment 4 Tom Henderson 2013-11-19 12:34:40 UTC 
pushed in changeset 10431:023c52cf0c2c