title: Making the best of a bad "checksum" algorithm
body: <p>I'm working on an existing driver that controls an 8-bit MCU over a serial port.  There are many different flavors of firmware for the MCU but they all share a common method of trying to ensure link integrity.  This method is not very robust and I am looking for ideas about how the driver could modify its behavior to get the most out of it.</p>
  
  <p>Commands are gcode with a line number and a checksum:</p>
  
  <pre><code>N3 T0*57
  N4 G92 E0*67
  N5 G28*22
  N6 G1 F1500.0*82
  N7 G1 X2.0 Y2.0 F3000.0*85
  N8 G1 X3.0 Y3.0*33
  </code></pre>
  
  <p>The line number must be sequential (but can be reset with <code>M110</code>).  If the checksum doesn't match or the line number is out of sequence the firmware will reply <code>Resend: nnn</code> where <code>nnn</code> is the last successful <code>N</code> plus 1.  The "checksum" is extremely primitive:</p>
  
  <pre><code>        // Calc checksum.
          byte checksum = 0;
          byte count = 0;
          while(instruction[count] != '*')
                  checksum = checksum^instruction[count++];
  </code></pre>
  
  <p>The main problem is that the primary error mechanism is <em>dropped bytes</em> due to interrupts being held off leading to overflows in the 1-byte MCU FIFO.  The actual serial bus is a few cm between an FTDI (or similar) USB serial bridge and the MCU, so bit errors are unlikely.  I've never observed a bit error in a reply from the firmware.</p>
  
  <p>As you can see, the algorithm above would detect one dropped byte, but if you dropped two of the same byte (anywhere!) the result would still match.  Thus <code>F3000.0</code> (feedrate 3000mm/min) could be transmuted to <code>F30.0</code> and still match.  Plus, the character set is very small so certain bits are never going to be involved.</p>
  
  <p>Is there anything the driver can do to make a given line more robust?</p>
  
  <ul>
  <li>Add or drop trailing (or even leading) zeroes</li>
  <li>Add or drop spaces</li>
  <li>Re-order words (<code>X1 Y1</code> is the same as <code>Y1 X1</code>)</li>
  <li>Add or drop spaces</li>
  <li>Make "insignificant" modifications to values within some tolerance (eg <code>F2999.9</code> instead of <code>F3000</code>)</li>
  <li>Reset the line number to get some specific <code>N</code> for a given line</li>
  <li>Break a single command into multiple equivalent commands (eg <code>G1 X2</code> becomes <code>G1 X1</code> <code>G1 X2</code> assuming X=0 initially)</li>
  <li>Eliminate (or add) superfluous words (eg <code>T0</code> is meaningless for most commands, and if you send <code>F3000</code> once it is implied in the future so it can be optionally sent or not)</li>
  </ul>
  
  <p>If I believe that the firmware drops bytes in groups then the most important thing could be to avoid back-to-back duplicates like <code>00</code> which would (if dropped together) be invisible.</p>