title: Computation of 64 bit CRC polynomial performance
body: <p>I found the following page in the web:
  <a href="https://users.ece.cmu.edu/%7Ekoopman/crc/crc64.html" rel="nofollow noreferrer">https://users.ece.cmu.edu/~koopman/crc/crc64.html</a></p>
  <p>It lists the performance of a handful of 64 bit CRC polynomials. The optimal payload for a hamming distance of 3 is listed as 18446744073709551551 bit. A polynomial providing that HD 3 payload is <code>0xd6c9e91aca649ad4</code> (Koopman notation).</p>
  <p>On the same website there is also some basic &quot;HDLen&quot; C code that can compute the performance of any polynomial (<a href="https://users.ece.cmu.edu/%7Ekoopman/crc/hdlen.html" rel="nofollow noreferrer">https://users.ece.cmu.edu/~koopman/crc/hdlen.html</a>). I checked that code and the HD 3 optimized loop is very simple, similar to this:</p>
  <pre><code>Poly_t accum = cPoly;   
  Length_t len = 0;
  
  while(accum != cTopBitSet)
  {
      accum = (accum &amp; 1) ? (accum &gt;&gt; 1) ^ cPoly) : (accum &gt;&gt; 1);
      len++;  
  }
  </code></pre>
  <p>18446744073709551551 is a huge number. It is almost the full range of a 64 bit integral. Even that simple loop would run centuries on the most powerful CPU core available.</p>
  <p>It also appears to me that this loop can not be parallelized since each iteration depends from the previous iteration.</p>
  <p>It is claimed that payload is optimal amongst all possible 64 bit polynomials which means that all possible 64 bit polynomials would have been checked for their individual HD 3 performance. This task can be parallelized, still the huge number of candidate polynomials seems to be undoable.</p>
  <p>I can't see a way to even compute a single (good) polynomial's (HD 3) performance. Not to mention all possible 64 bit wide polynomials.</p>
  <p>So I wonder: How has the number been found? What kind of code or method (in contrast to the simple HDLen software) was used to find the mentioned optimal HD 3 payload?</p>