Demonstrate calculation of CRC8/MAXIM aka DOW-CRC

maxim_1wire_crc8.c

/*
 * maxim_1wire_crc8.c
 *
 * Demonstrate calculation of CRC8/MAXIM aka DOW-CRC in a way compatible with
 * Maxim 1-wire (Dallas iButton).
 *
 * Original portions copyright (C) June 3, 2016, Andrew Domaszek. All rights reserved.
 * Except as noted, this work is licensed under the Modified BSD License (BSD-new).
 */

/*
 * Most of what I know about CRC I learned from:
 * http://www.ross.net/crc/download/crc_v3.txt
 *
 * The function doCRC8() was originally found at:
 * http://www.microchip.com/forums/FindPost/626520
 * It appears to be derived from Atmel's (now Microchip) application note AVR318.
 * While OWIcrc.c (circa 2004) does not state an explicit license, modern
 * Atmel ANs are published under the Modified BSD License with an additional
 * clause limiting use to Atmel (and now Microchip) products.
 * 
 * The function and table used in mxCRC8() based on crc lookup code found at:
 * Applicaton Note 27
 * "Understanding and Using Cyclic Redundancy Checks with Maxim 1-Wire and iButton Products"
 * https://www.maximintegrated.com/en/app-notes/index.mvp/id/27
 * Maxim makes its 1-wire Application Note software available under the Xfree86 license.
 *
 * The function crc_bits() is originally by T. Scott Dattalo, 2003/01/18.
 * Mr. Dattalo does not appear to publish the original document anymore, but
 * all citations point to:
 * http://www.dattalo.com/technical/software/pic/crc_8bit.c
 * Wayback machine copy:
 * https://web.archive.org/web/20130328201356/http://www.dattalo.com/technical/software/pic/crc_8bit.c
 * No license information is provided, but several derivatives of the math
 * exist with very permissive/public domain style licenses, for example:
 * http://www.ccsinfo.com/forum/viewtopic.php?t=26264 (for PIC microcontroller)
 */

#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>

typedef uint8_t INT8U;
 
//--------------------------------------------------------------------------
/*  Compute the CRC8 value of a data set.
 *  Full Software Method (Atmel/Microchip)
 *
 *  This function will compute the CRC8 or DOW-CRC of inData using seed
 *  as inital value for the CRC.
 *
 *  \param  inData  One byte of data to compute CRC from.
 *
 *  \param  seed    The starting value of the CRC.
 *
 *  \return The CRC8 of inData with seed as initial value.
 *
 *  \note   Setting seed to 0 computes the crc8 of the inData.
 *
 *  \note   Constantly passing the return value of this function
 *          As the seed argument computes the CRC8 value of a
 *          longer string of data.
 */
//--------------------------------------------------------------------------
/*
 * ~~aed.20160603
 * Comments (mine) explain how this is implementing X^{8}+X^{5}+X^{4}+1, the
 * CRC polynomial Maxim specifies in AN27.
 */
INT8U doCRC8(INT8U inData, INT8U seed) __attribute__ ((const));
INT8U doCRC8(INT8U inData, INT8U seed)
{
  INT8U bitsLeft;
  INT8U temp; // in maxim's (8051) assembler example, this is the carry bit. ~~aed.20160603

  for (bitsLeft = 8; bitsLeft > 0; bitsLeft--)
  {
    temp = ((seed ^ inData) & 0x01); // xor LSB from seed and inData (X^{8} factor from the polynomial) ~~aed.20160603
    if (temp == 0)
    {
      seed >>= 1; // SR passes 0 as the polynomial input. All of the input bit dependent xor inputs pass the prior stage forward. ~~aed.20160603
    }
    else
    {
      seed ^= 0x18; // Apply X^{5}+X^{4} factors ~~aed.20160603
      seed >>= 1; // Right shift SR state ~~aed.20160603
      seed |= 0x80; // Apply +1 factor. ~~aed.20160603
    }
    inData >>= 1; // Advance to next input bit. ~~aed.20160603
  }
  return seed;
}

//--------------------------------------------------------------------------
/*  Compute the CRC8 value of a data set.
 *  Lookup table method. (Maxim-derived)
 *
 *  This function will compute the CRC8 or DOW-CRC of inData using seed
 *  as inital value for the CRC.
 *
 *  \param  inData  One byte of data to compute CRC from.
 *
 *  \param  seed    The starting value of the CRC.
 *
 *  \return The CRC8 of inData with seed as initial value.
 *
 *  \note   Setting seed to 0 computes the crc8 of the inData.
 *
 *  \note   Constantly passing the return value of this function
 *          As the seed argument computes the CRC8 value of a
 *          longer string of data.
 */
//--------------------------------------------------------------------------
const /*_rom*/ uint8_t mxCRC8_table[256] = {
  0, 94, 188, 226, 97, 63, 221, 131, 194, 156, 126, 32, 163, 253, 31, 65,
  157, 195, 33, 127, 252, 162, 64, 30, 95, 1, 227, 189, 62, 96, 130, 220,
  35, 125, 159, 193, 66, 28, 254, 160, 225, 191, 93, 3, 128, 222, 60, 98,
  190, 224, 2, 92, 223, 129, 99, 61, 124, 34, 192, 158, 29, 67, 161, 255,
  70, 24, 250, 164, 39, 121, 155, 197, 132, 218, 56, 102, 229, 187, 89, 7,
  219, 133, 103, 57, 186, 228, 6, 88, 25, 71, 165, 251, 120, 38, 196, 154,
  101, 59, 217, 135, 4, 90, 184, 230, 167, 249, 27, 69, 198, 152, 122, 36,
  248, 166, 68, 26, 153, 199, 37, 123, 58, 100, 134, 216, 91, 5, 231, 185,
  140, 210, 48, 110, 237, 179, 81, 15, 78, 16, 242, 172, 47, 113, 147, 205,
  17, 79, 173, 243, 112, 46, 204, 146, 211, 141, 111, 49, 178, 236, 14, 80,
  175, 241, 19, 77, 206, 144, 114, 44, 109, 51, 209, 143, 12, 82, 176, 238,
  50, 108, 142, 208, 83, 13, 239, 177, 240, 174, 76, 18, 145, 207, 45, 115,
  202, 148, 118, 40, 171, 245, 23, 73, 8, 86, 180, 234, 105, 55, 213, 139,
  87, 9, 235, 181, 54, 104, 138, 212, 149, 203, 41, 119, 244, 170, 72, 22,
  233, 183, 85, 11, 136, 214, 52, 106, 43, 117, 151, 201, 74, 20, 246, 168,
  116, 42, 200, 150, 21, 75, 169, 247, 182, 232, 10, 84, 215, 137, 107, 53};
uint8_t mxCRC8(uint8_t inData, uint8_t seed) __attribute__ ((pure));
uint8_t mxCRC8(uint8_t inData, uint8_t seed)
{
  return mxCRC8_table[inData ^ seed];
}


//--------------------------------------------------------------------------
/*  Compute the CRC8 value of a data set.
 *  Naive method. (aed original)
 *
 *  This function will compute the CRC8 or DOW-CRC of inData using seed
 *  as inital value for the CRC.
 */
 //--------------------------------------------------------------------------
// The poly definition here should be (reflected) shifted right 1 and include
// the +1 factor, in this case 0x80.
#define SLOW_POLY (0x18>>1|0x80)
uint8_t crc8TernaryUnroll(uint8_t inData, uint8_t crc) __attribute__ ((const));
uint8_t crc8TernaryUnroll(uint8_t inData, uint8_t crc)
{
#if defined(CRC_INVERTIN)
  crc ^= 0xff;
#endif
  crc ^= inData;
  crc = crc & 1 ? (crc >> 1) ^ SLOW_POLY : crc >> 1;
  crc = crc & 1 ? (crc >> 1) ^ SLOW_POLY : crc >> 1;
  crc = crc & 1 ? (crc >> 1) ^ SLOW_POLY : crc >> 1;
  crc = crc & 1 ? (crc >> 1) ^ SLOW_POLY : crc >> 1;
  crc = crc & 1 ? (crc >> 1) ^ SLOW_POLY : crc >> 1;
  crc = crc & 1 ? (crc >> 1) ^ SLOW_POLY : crc >> 1;
  crc = crc & 1 ? (crc >> 1) ^ SLOW_POLY : crc >> 1;
  crc = crc & 1 ? (crc >> 1) ^ SLOW_POLY : crc >> 1;
#if defined(CRC_INVERTOUT)
  crc ^= 0xff;
#endif
  return crc;
}

//--------------------------------------------------------------------------
/*  Compute the CRC8 value of a data set.
 *  Bit flipping method. (Dattalo)
 *
 *  This function will compute the CRC8 or DOW-CRC of inData using seed
 *  as inital value for the CRC.
 */
 //--------------------------------------------------------------------------
uint8_t crc_bits(uint8_t data, uint8_t crc) __attribute__ ((const));
uint8_t crc_bits(uint8_t data, uint8_t crc)
{
  int i = (data ^ crc) & 0xff;

  crc = 0;

  if (i & 1)
    crc ^= 0x5e;
  if (i & 2)
    crc ^= 0xbc;
  if (i & 4)
    crc ^= 0x61;
  if (i & 8)
    crc ^= 0xc2;
  if (i & 0x10)
    crc ^= 0x9d;
  if (i & 0x20)
    crc ^= 0x23;
  if (i & 0x40)
    crc ^= 0x46;
  if (i & 0x80)
    crc ^= 0x8c;

  return crc;
}

/*!
  \brief Convert an ascii encoded nibble to an integer from 0 to 15

  \param c        - character to convert.

  \return 0 to 15 - Converted value.
  \return -1      - Error occurred.
 */
int8_t hexnibble2num(char c) __attribute__ ((const));
int8_t hexnibble2num(char c)
{
  int8_t res = -1;
  if (c >= '0' && c <= '9') { // assume contiguous character encoding.
    res = c - '0';
  } else {
    c = tolower(c);
    if (c >= 'a' && c <= 'f') {
      res = 10 + c - 'a'; // 'a' == 10
    }
  }
  return res;
}


/*!
  \brief Convert a hex string into binary.

  Not length safe! Potential overflow!

  \param bytesOut - binary output from conversion.
  \param hexIn - ascii encoded hexidecimal string.

  \return number of bytes converted on success.
  \return -1 on failure.
 */
int hex2bytes(uint8_t *bytesOut, const char * hexIn)
{
  assert(bytesOut && hexIn);
  int i = 0;
  int t_byte = 0;
  int strcnt = strlen(hexIn);
  if (strcnt & 1) { // odd number of hex digits?
    goto err_escape;
  }

  for (i = 0; i < strcnt/2; ++i) {
    t_byte = -1;
    t_byte = hexnibble2num(hexIn[i*2]);
    if (t_byte == -1) goto err_escape;

    bytesOut[i] = t_byte<<4; // top nibble.

    t_byte = hexnibble2num(hexIn[i*2+1]);
    if (t_byte == -1) goto err_escape;

    bytesOut[i] |= t_byte; // bottom nibble.
  }

  return strcnt/2;
err_escape:
  //*bytesOut = 0;
  return -1;
}

void printbytestohex(uint8_t *bytes, uint8_t cnt)
{
  int i = 0;
  for (i = 0; i < cnt; ++i) {
    printf("%02x", bytes[i]);
  }
  printf("\n");
}

int main()
{
  int i = 0, j = 0, k = 0;
  int bytecnt = 0;
  uint8_t crc = 0;
  struct {
    const char * str;
    uint8_t crc;
  } testHex[] = {
/* These are valid 1-wire serials.
       vv - CRC8, MSB
         v----------v - Unique serial (6 bytes)
                     vv - Family code, LSB */
     {"1d0000068139cc14",0x00} // a DS2430A I found
    ,{"b60008026a84f310",0x00} // temperature sensor?
    ,{"7700000003D97A0C",0x00} // 64kbit NVRAM, from the internet somewhere.
/* Some bad values with known CRC8s */
    ,{"fa2202cef4256f9c",0x4e}
    ,{"efae3798610f0ef4",0x76}
    ,{"d424c40d376ab68c",0xe5}
  };

  typedef uint8_t (*crc8StepFcn)(uint8_t,uint8_t);  
  struct {
    const char * fcnname;
    crc8StepFcn fcn;
  } FcnList[] = {
     {"doCRC8",doCRC8}
    ,{"mxCRC8",mxCRC8}
    ,{"crc8TernaryUnroll",crc8TernaryUnroll}
    ,{"crc_bits",crc_bits}
  };

  uint8_t bin_buffer[1024]; // why so big? because memory on PCs is cheap.

#if defined(SIMPLE_DEMO)
  const char * hexIn = testHex[0].str;
  bytecnt = hex2bytes(bin_buffer, hexIn); // convert hex string into binary data.
  if (bytecnt > 0) {
    crc = 0;
    for (j = bytecnt-1; j >= 0; --j) // 1-wire sends LE, calculate CRC starting from family code forward.
      crc = mxCRC8(bin_buffer[j], crc);
    printf("%s(%s): %02x [%s]\n", "mxCRC8", hexIn, crc,
           (crc == 0)?"PASS":"FAIL");
  } else {
    // Error happened.
  }
#else
  for (k = 0; k < (sizeof(FcnList)/sizeof(FcnList[0])); k++) {
    if (k) printf("\n----\n\n"); // some separation for 2nd & subsequent.
    for (i = 0; i < (sizeof(testHex)/sizeof(testHex[0])); ++i) {
      bytecnt = hex2bytes(bin_buffer, testHex[i].str);
      if (bytecnt > 0) {
        crc = 0;
        for (j = bytecnt-1; j >= 0; --j) // 1-wire sends LE, calculate CRC starting from family code forward.
          crc = FcnList[k].fcn(bin_buffer[j], crc);
        printf("%s(%s): %02x [%s]\n", FcnList[k].fcnname, testHex[i].str, crc,
               (crc == testHex[i].crc)?"PASS":"FAIL");
      } else {
        printf ("Test string invalid: %s\n", testHex[i].str);
      }
    }
  }
#endif
  return 0;
}