flash_journal_crc.c

00001 /**********************************************************************
00002  *
00003  * Filename:    flash_journal_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 #include "flash-journal-strategy-sequential/flash_journal_crc.h"
00019 
00020 #define FALSE   0
00021 #define TRUE    !FALSE
00022 
00023 #define CRC_NAME            "CRC-32"
00024 #define POLYNOMIAL          0x04C11DB7
00025 #define INITIAL_REMAINDER   0xFFFFFFFF
00026 #define FINAL_XOR_VALUE     0xFFFFFFFF
00027 #define REFLECT_DATA        TRUE
00028 #define REFLECT_REMAINDER   TRUE
00029 #define CHECK_VALUE         0xCBF43926
00030 
00031 
00032 /*
00033  * Derive parameters from the standard-specific parameters in crc.h.
00034  */
00035 #define WIDTH    (8 * sizeof(flash_journal_crc32_t))
00036 /* U postfix required to suppress the following warning with TOOLCHAIN_ARM:
00037  * #61-D: integer operation result is out of range
00038  */
00039 #define TOPBIT   0x80000000U
00040 
00041 #if (REFLECT_DATA == TRUE)
00042 #undef  REFLECT_DATA
00043 #define REFLECT_DATA(X)         ((unsigned char) reflect((X), 8))
00044 #else
00045 #undef  REFLECT_DATA
00046 #define REFLECT_DATA(X)         (X)
00047 #endif
00048 
00049 #if (REFLECT_REMAINDER == TRUE)
00050 #undef  REFLECT_REMAINDER
00051 #define REFLECT_REMAINDER(X)    ((flash_journal_crc32_t) reflect((X), WIDTH))
00052 #else
00053 #undef  REFLECT_REMAINDER
00054 #define REFLECT_REMAINDER(X)    (X)
00055 #endif
00056 
00057 
00058 /*********************************************************************
00059  *
00060  * Function:    reflect()
00061  *
00062  * Description: Reorder the bits of a binary sequence, by reflecting
00063  *              them about the middle position.
00064  *
00065  * Notes:       No checking is done that nBits <= 32.
00066  *
00067  * Returns:     The reflection of the original data.
00068  *
00069  *********************************************************************/
00070 static uint32_t
00071 reflect(uint32_t data, unsigned char nBits)
00072 {
00073     uint32_t  reflection = 0x00000000;
00074     unsigned char  bit;
00075 
00076     /*
00077      * Reflect the data about the center bit.
00078      */
00079     for (bit = 0; bit < nBits; ++bit)
00080     {
00081         /*
00082          * If the LSB bit is set, set the reflection of it.
00083          */
00084         if (data & 0x01)
00085         {
00086             reflection |= (1 << ((nBits - 1) - bit));
00087         }
00088 
00089         data = (data >> 1);
00090     }
00091 
00092     return (reflection);
00093 
00094 }   /* reflect() */
00095 
00096 
00097 static flash_journal_crc32_t  crcTable[256];
00098 static flash_journal_crc32_t  crcEngineRemainder = INITIAL_REMAINDER;
00099 
00100 /*********************************************************************
00101  *
00102  * Function:    flashJournalCrcInit()
00103  *
00104  * Description: Populate the partial CRC lookup table.
00105  *
00106  * Notes:       This function must be rerun any time the CRC standard
00107  *              is changed.  If desired, it can be run "offline" and
00108  *              the table results stored in an embedded system's ROM.
00109  *
00110  * Returns:     None defined.
00111  *
00112  *********************************************************************/
00113 void
00114 flashJournalCrcInit(void)
00115 {
00116     flash_journal_crc32_t            remainder;
00117     int            dividend;
00118     unsigned char  bit;
00119 
00120 
00121     /*
00122      * Compute the remainder of each possible dividend.
00123      */
00124     for (dividend = 0; dividend < 256; ++dividend)
00125     {
00126         /*
00127          * Start with the dividend followed by zeros.
00128          */
00129         remainder = dividend << (WIDTH - 8);
00130 
00131         /*
00132          * Perform modulo-2 division, a bit at a time.
00133          */
00134         for (bit = 8; bit > 0; --bit)
00135         {
00136             /*
00137              * Try to divide the current data bit.
00138              */
00139             if (remainder & TOPBIT)
00140             {
00141                 remainder = (remainder << 1) ^ POLYNOMIAL;
00142             }
00143             else
00144             {
00145                 remainder = (remainder << 1);
00146             }
00147         }
00148 
00149         /*
00150          * Store the result into the table.
00151          */
00152         crcTable[dividend] = remainder;
00153     }
00154 
00155 }   /* flashJournalCrcInit() */
00156 
00157 /*********************************************************************
00158  *
00159  * Function:    flashJournalCrcReset()
00160  *
00161  * Description: Resets internal state before calling crcCummulative().
00162  *
00163  * Notes: See the notes to crcCummulative().
00164  *
00165  * Returns:     None defined.
00166  *
00167  *********************************************************************/
00168 void
00169 flashJournalCrcReset(void)
00170 {
00171     static unsigned initCalled = 0;
00172     if (!initCalled) {
00173         flashJournalCrcInit();
00174         initCalled = 1;
00175     }
00176 
00177     crcEngineRemainder = INITIAL_REMAINDER;
00178 
00179 }   /* flashJournalCrcReset() */
00180 
00181 /*********************************************************************
00182  *
00183  * Function:    crcCummulative()
00184  *
00185  * Description: Compute the CRC of a group of messages.
00186  *
00187  * Notes:
00188  * This function is intended to be used in the following way:
00189  *  - crcReset() is called first to reset internal state before the first
00190  *    fragment of a new message is processed with crcCummulative().
00191  *  - crcCummulative() called successfully appending additional message
00192  *    fragments to those previously supplied (in order), and returning
00193  *    the current crc for the message payload so far.
00194  *
00195  * Returns:     The CRC of the message.
00196  *
00197  *********************************************************************/
00198 flash_journal_crc32_t
00199 flashJournalCrcCummulative(unsigned char const message[], int nBytes)
00200 {
00201     unsigned char  data;
00202     int            byte;
00203 
00204 
00205     /*
00206      * Divide the message by the polynomial, a byte at a time.
00207      */
00208     for (byte = 0; byte < nBytes; ++byte)
00209     {
00210         data = REFLECT_DATA(message[byte]) ^ (crcEngineRemainder >> (WIDTH - 8));
00211         crcEngineRemainder = crcTable[data] ^ (crcEngineRemainder << 8);
00212     }
00213 
00214     /*
00215      * The final remainder is the CRC.
00216      */
00217     return (REFLECT_REMAINDER(crcEngineRemainder) ^ FINAL_XOR_VALUE);
00218 
00219 }   /* crcCummulative() */
00220