crc32.c

00001 /**********************************************************************
00002  *
00003  * Filename:    crc.c
00004  *
00005  * Description: Slow and fast implementations of the CRC standards.
00006  *
00007  * Notes:       The parameters for each supported CRC standard are
00008  *              defined in the header file crc.h.  The implementations
00009  *              here should stand up to further additions to that list.
00010  *
00011  *
00012  * Copyright (c) 2000 by Michael Barr.  This software is placed into
00013  * the public domain and may be used for any purpose.  However, this
00014  * notice must not be changed or removed and no warranty is either
00015  * expressed or implied by its publication or distribution.
00016  **********************************************************************/
00017 
00018 /**
00019  * @file    crc32.c
00020  * @brief   Implementation of crc.h
00021  */
00022 
00023 #include "crc.h"
00024 
00025 #define FALSE   0
00026 #define TRUE    !FALSE
00027 
00028 typedef unsigned long  crc;
00029 
00030 #define CRC_NAME            "CRC-32"
00031 #define POLYNOMIAL          0x04C11DB7
00032 #define INITIAL_REMAINDER   0xFFFFFFFF
00033 #define FINAL_XOR_VALUE     0xFFFFFFFF
00034 #define REFLECT_DATA        TRUE
00035 #define REFLECT_REMAINDER   TRUE
00036 #define CHECK_VALUE         0xCBF43926
00037 
00038 /*
00039  * Derive parameters from the standard-specific parameters in crc.h.
00040  */
00041 #define WIDTH    (8 * sizeof(crc))
00042 #define TOPBIT   (1U << (WIDTH - 1))
00043 
00044 #if (REFLECT_DATA == TRUE)
00045 #undef  REFLECT_DATA
00046 #define REFLECT_DATA(X)         ((unsigned char) reflect((X), 8))
00047 #else
00048 #undef  REFLECT_DATA
00049 #define REFLECT_DATA(X)         (X)
00050 #endif
00051 
00052 #if (REFLECT_REMAINDER == TRUE)
00053 #undef  REFLECT_REMAINDER
00054 #define REFLECT_REMAINDER(X)    ((crc) reflect((X), WIDTH))
00055 #else
00056 #undef  REFLECT_REMAINDER
00057 #define REFLECT_REMAINDER(X)    (X)
00058 #endif
00059 
00060 
00061 /*********************************************************************
00062  *
00063  * Function:    reflect()
00064  *
00065  * Description: Reorder the bits of a binary sequence, by reflecting
00066  *              them about the middle position.
00067  *
00068  * Notes:       No checking is done that nBits <= 32.
00069  *
00070  * Returns:     The reflection of the original data.
00071  *
00072  *********************************************************************/
00073 static unsigned long
00074 reflect(unsigned long data, unsigned char nBits)
00075 {
00076     unsigned long  reflection = 0x00000000;
00077     unsigned char  bit;
00078 
00079     /*
00080      * Reflect the data about the center bit.
00081      */
00082     for (bit = 0; bit < nBits; ++bit) {
00083         /*
00084          * If the LSB bit is set, set the reflection of it.
00085          */
00086         if (data & 0x01) {
00087             reflection |= (1 << ((nBits - 1) - bit));
00088         }
00089 
00090         data = (data >> 1);
00091     }
00092 
00093     return (reflection);
00094 }   /* reflect() */
00095 
00096 
00097 /*********************************************************************
00098  *
00099  * Function:    crc32()
00100  *
00101  * Description: Compute the CRC of a given message.
00102  *
00103  * Notes:
00104  *
00105  * Returns:     The CRC of the message.
00106  *
00107  *********************************************************************/
00108 uint32_t
00109 crc32(const void *data, int nBytes)
00110 {
00111     crc            remainder = INITIAL_REMAINDER;
00112     int            byte;
00113     unsigned char  bit;
00114     unsigned char const *message = data;
00115 
00116     /*
00117      * Perform modulo-2 division, a byte at a time.
00118      */
00119     for (byte = 0; byte < nBytes; ++byte) {
00120         /*
00121          * Bring the next byte into the remainder.
00122          */
00123         remainder ^= (REFLECT_DATA(message[byte]) << (WIDTH - 8));
00124 
00125         /*
00126          * Perform modulo-2 division, a bit at a time.
00127          */
00128         for (bit = 8; bit > 0; --bit) {
00129             /*
00130              * Try to divide the current data bit.
00131              */
00132             if (remainder & TOPBIT) {
00133                 remainder = (remainder << 1) ^ POLYNOMIAL;
00134             } else {
00135                 remainder = (remainder << 1);
00136             }
00137         }
00138     }
00139 
00140     /*
00141      * The final remainder is the CRC result.
00142      */
00143     return (REFLECT_REMAINDER(remainder) ^ FINAL_XOR_VALUE);
00144 }   /* crc32() */
00145 
00146 /*********************************************************************
00147  *
00148  * Function:    crc32_continue()
00149  *
00150  * Description: Compute the CRC of a given message.
00151  *
00152  * Notes:
00153  *
00154  * Returns:     The CRC of the message.
00155  *
00156  *********************************************************************/
00157 uint32_t
00158 crc32_continue(uint32_t prev_crc, const void *data, int nBytes)
00159 {
00160     crc            remainder = REFLECT_REMAINDER(prev_crc ^ FINAL_XOR_VALUE);
00161     int            byte;
00162     unsigned char  bit;
00163     unsigned char const *message = data;
00164 
00165     /*
00166      * Perform modulo-2 division, a byte at a time.
00167      */
00168     for (byte = 0; byte < nBytes; ++byte) {
00169         /*
00170          * Bring the next byte into the remainder.
00171          */
00172         remainder ^= (REFLECT_DATA(message[byte]) << (WIDTH - 8));
00173 
00174         /*
00175          * Perform modulo-2 division, a bit at a time.
00176          */
00177         for (bit = 8; bit > 0; --bit) {
00178             /*
00179              * Try to divide the current data bit.
00180              */
00181             if (remainder & TOPBIT) {
00182                 remainder = (remainder << 1) ^ POLYNOMIAL;
00183             } else {
00184                 remainder = (remainder << 1);
00185             }
00186         }
00187     }
00188 
00189     /*
00190      * The final remainder is the CRC result.
00191      */
00192     return (REFLECT_REMAINDER(remainder) ^ FINAL_XOR_VALUE);
00193 }   /* crc32_continue() */