32位CRC校验代码及其应用

分类： 50. linux/uclinux2007-08-20 14:24 811人阅读 评论(0) 收藏 举报

转载时请注明出处和作者联系方式：http://blog.csdn.net/mimepp

作者联系方式：YU TAO <yut616 at sohu dot com>

近来看了一下有关CRC校验的内容,这里做个笔记.

CRC有关的RFC,可以参考
http://www.faqs.org/rfcs/rfc1952.html

crc的本质主要是XOR异或运算.
32位crc,一般使用查表法来处理, 速度也比较快. 代码示例如下:

8. Appendix: Sample CRC Code

   The following sample code represents a practical implementation of

   the CRC (Cyclic Redundancy Check). (See also ISO 3309 and ITU-T V.42

   for a formal specification.)

   The sample code is in the ANSI C programming language. Non C users

   may find it easier to read with these hints:

      &      Bitwise AND operator.

      ^      Bitwise exclusive-OR operator.

      >>     Bitwise right shift operator. When applied to an

             unsigned quantity, as here, right shift inserts zero

             bit(s) at the left.

      !      Logical NOT operator.

      ++     "n++" increments the variable n.

      0xNNN  0x introduces a hexadecimal (base 16) constant.

             Suffix L indicates a long value (at least 32 bits).

      /* Table of CRCs of all 8-bit messages. */

      unsigned long crc_table[256];

      /* Flag: has the table been computed? Initially false. */

      int crc_table_computed = 0;

      /* Make the table for a fast CRC. */

      void make_crc_table(void)

      {

        unsigned long c;

        int n, k;

        for (n = 0; n < 256; n++) {

          c = (unsigned long) n;

          for (k = 0; k < 8; k++) {

            if (c & 1) {

              c = 0xedb88320L ^ (c >> 1);

            } else {

              c = c >> 1;

            }

          }

          crc_table[n] = c;

        }

        crc_table_computed = 1;

      }

      /*

         Update a running crc with the bytes buf[0..len-1] and return

       the updated crc. The crc should be initialized to zero. Pre- and

       post-conditioning (one's complement) is performed within this

       function so it shouldn't be done by the caller. Usage example:

         unsigned long crc = 0L;

         while (read_buffer(buffer, length) != EOF) {

           crc = update_crc(crc, buffer, length);

         }

         if (crc != original_crc) error();

      */

      unsigned long update_crc(unsigned long crc,

                      unsigned char *buf, int len)

      {

        unsigned long c = crc ^ 0xffffffffL;

        int n;

        if (!crc_table_computed)

          make_crc_table();

        for (n = 0; n < len; n++) {

          c = crc_table[(c ^ buf[n]) & 0xff] ^ (c >> 8);

        }

        return c ^ 0xffffffffL;

      }

      /* Return the CRC of the bytes buf[0..len-1]. */

      unsigned long crc(unsigned char *buf, int len)

      {

        return update_crc(0L, buf, len);

      }

crc校验,除了一般的用途, 还有其他用途.
比如监视一个目录中的文件是否发生变化, 可以将文件名name与最后modified time时间做成一个字串name-time, 然后将这个字串算一下crc, 将所有文件的crc都算好后, 最后对比上次的crc, 就可以看出文件修改时间是否已经变化.这个时候crc就变成了一个监视的标记,好处是不管文件个数是多少, 在你的代码里是须记录单个文件信息的,而且增加文件和删除文件也都能看到crc有变化.