RE: iSCSI CRC: A CRC-checking example

["Douglas Otis" <dotis@sanlight.net>]

Mark,

You appear to be incorrect about which bit is processed first.  The table is
reflected and therefore there should be no need to do any reflection as you
describe except within building the table.  Here is some example code for
generating this reflected table.

/* Example CRC32 reflected table creation */

#include <stdio.h>
#include <stdlib.h>

#define OUTPUT_FILE   "crc32_tab.h"
#define CRC32_POLY			0x1EDC6F41L
#define CRC_TYPE  "\
/* Castagnoli93                                                        */\n\
/* x^32+x^28+x^27+x^26+x^25+x^23+x^22+x^20+x^19+x^18+x^14+x^13+x^11+   */\n\
/* x^10+* x^9+x^8+x^6+x^0                                              */\n\
/* Guy Castagnoli Stefan Braeuer and Martin Herrman                    */\n\
/* \"Optimization of Cyclic Redundancy-Check Codes
*/\n\
/* with 24 and 32 Parity Bits\",
*/\n\
/* IEEE Transactions on Communications, Vol. 41, No. 6, June 1993      */\n"


FILE *tf;

unsigned long
  reflect_32 (unsigned long b)
{
  int i;
  unsigned long rw = 0;

  for (i = 0; i < 32; i++)
    {
      if (b & 1)
        rw |= 1 << (31 - i);
      b >>= 1;
    }
  return (rw);
}


unsigned long
  build_crc_table (int index)
{
  int i;
  unsigned long rb;

  rb = reflect_32 (index);

  for (i = 0; i < 8; i++)
    {
      if (rb & 0x80000000L)
	rb = (rb << 1) ^ CRC32_POLY;
      else
	rb <<= 1;
    }
  return (reflect_32 (rb));
}


/* here is a means to verify the bype order via serial equivalent */

unsigned long
  serial_gen (unsigned char buf[], int length)
{
  int i;
  int j = 0;
  unsigned char d;
  unsigned long crc = 0;

  while (j < length)
    {
      d = buf[j++];
      for (i = 0; i < 8; i++)
	  {
	  if ((crc >> 31) ^ (d & 1))
	      crc = (crc << 1) ^ CRC32_POLY;
	  else
	      crc <<= 1;
	  d >>= 1;
	  }
    }

  return (crc);
}

main ()
{
  int i;

  printf ("\nGenerating CRC32 Table file <%s>\n", OUTPUT_FILE);
  if ((tf = fopen (OUTPUT_FILE, "w")) == NULL)
    {
      printf ("Unable to open %s\n", OUTPUT_FILE);
      exit (1);
    }
  fprintf (tf, "#ifndef __crc32_table_h__\n");
  fprintf (tf, "#define __crc32_table_h__\n\n");
  fprintf (tf, "#define CRC32_POLY 0x%08lX\n", CRC32_POLY);
  fprintf (tf, "#define CRC32(c,d) (c=(c>>8)^crc32tab[(c^(d))&0xFF])\n");
  fprintf (tf, "\
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */\n\
/* 32 Bit Reflected CRC table generation for SCTP.                     */\n\
/* To accomodate serial byte data being shifted out least              */\n\
/* significant bit first, the table's 32 bit words are reflected       */\n\
/* which flips both byte and bit MS and LS positions.  The CRC         */\n\
/* is calculated MS bits first from the perspective of the serial      */\n\
/* stream.  The x^32 term is implied and the x^0 term may also         */\n\
/* be shown as +1.  The polynomial code used is 0x%08lX.            */\n%s\
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */\n"
	   , CRC32_POLY, CRC_TYPE);

  fprintf (tf, "\nunsigned long  crc32tab[256] =\n{\n");
  for (i = 0; i < 256; i++)
    {
      fprintf (tf, "0x%08lXL, ", build_crc_table (i));
      if ((i & 3) == 3)
        fprintf (tf, "\n");
    }

  fprintf (tf, "};\n\n#endif\n");

  if (fclose (tf) != 0)
    printf ("Unable to close <%s>." OUTPUT_FILE);
  else
    printf ("\nThe CRC32 table has been written to <%s>.\n", OUTPUT_FILE);
}


Doug


> -----Original Message-----
> From: owner-ips@ece.cmu.edu [mailto:owner-ips@ece.cmu.edu]On Behalf Of
> Mark Bakke
> Sent: Friday, August 17, 2001 1:13 PM
> To: Julian Satran; IPS
> Subject: iSCSI CRC: A CRC-checking example
>
>
>
> Julian and CRC enthusiasts-
>
> After several people ran the iSCSI CRC through their
> hardware and software implementations, we've found that
> there are a few important things to add to the CRC spec;
> that the bit order must be flipped, and the CRC bytes
> must be sent in network order.
>
> We should also specify that when running the CRC check
> on an iSCSI PDU with its CRC, that the remainder (before
> complement and bit-reversal) is a constant 0x1c2d19ed.
>
>
> How about replacing:
>
> The generator polynomial selected is evaluated in [Castagnioli93].
> When using the CRC the CRC register must be initialized to all 1s
> (0xFFFFFFFF) and the CRC bits must be complemented before
> transmission. Padding bytes, when present, in a segment covered by a
> CRC, should be set to 0 and are included in the CRC.
>
> With:
>
> The generator polynomial selected is evaluated in [Castagnioli93].
> When using the CRC the CRC register must be initialized to all 1s
> (0xFFFFFFFF).  Input bytes are processed with bit 7 being the most
> significant bit.  Before transmission, the CRC bits must be
> reflected (bit 31 swapped with bit 0, bit 30 swapped with bit 1,
> etc.), and complemented.  The CRC bytes must be transmitted in
> network order.  Padding bytes, when present, in a segment covered
> by a CRC, should be set to 0 and are included in the CRC.
>
> Running the CRC-32C generator on an input stream that includes a
> valid CRC-32C will result in the constant remainder 0x1c2d19ed,
> (without being reversed and complemented).
>
>
> --
> Mark A. Bakke
> Cisco Systems
> mbakke@cisco.com
> 763.398.1054