nux-1.14.0
CRC32.cpp
00001 /*
00002  * Copyright 2010 Inalogic® Inc.
00003  *
00004  * This program is free software: you can redistribute it and/or modify it
00005  * under the terms of the GNU Lesser General Public License, as
00006  * published by the  Free Software Foundation; either version 2.1 or 3.0
00007  * of the License.
00008  *
00009  * This program is distributed in the hope that it will be useful, but
00010  * WITHOUT ANY WARRANTY; without even the implied warranties of
00011  * MERCHANTABILITY, SATISFACTORY QUALITY or FITNESS FOR A PARTICULAR
00012  * PURPOSE.  See the applicable version of the GNU Lesser General Public
00013  * License for more details.
00014  *
00015  * You should have received a copy of both the GNU Lesser General Public
00016  * License along with this program. If not, see <http://www.gnu.org/licenses/>
00017  *
00018  * Authored by: Jay Taoko <jaytaoko@inalogic.com>
00019  *
00020  */
00021 
00022 
00023 #include "NuxCore.h"
00024 #include "CRC32.h"
00025 
00026 
00027 namespace nux
00028 {
00029 // The constants here are for the CRC-32 generator
00030 // polynomial, as defined in the Microsoft
00031 // Systems Journal, March 1995, pp. 107-108
00032 
00033   const unsigned int CRCTable [256] =
00034   {
00035     0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA,
00036     0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3,
00037     0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
00038     0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91,
00039     0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE,
00040     0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
00041     0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC,
00042     0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5,
00043     0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172,
00044     0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B,
00045     0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940,
00046     0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59,
00047     0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116,
00048     0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F,
00049     0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
00050     0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D,
00051 
00052     0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A,
00053     0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433,
00054     0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818,
00055     0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01,
00056     0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E,
00057     0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457,
00058     0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA, 0xFCB9887C,
00059     0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65,
00060     0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2,
00061     0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB,
00062     0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0,
00063     0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9,
00064     0x5005713C, 0x270241AA, 0xBE0B1010, 0xC90C2086,
00065     0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
00066     0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4,
00067     0x59B33D17, 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD,
00068 
00069     0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A,
00070     0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683,
00071     0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8,
00072     0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
00073     0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE,
00074     0xF762575D, 0x806567CB, 0x196C3671, 0x6E6B06E7,
00075     0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC,
00076     0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5,
00077     0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252,
00078     0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
00079     0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60,
00080     0xDF60EFC3, 0xA867DF55, 0x316E8EEF, 0x4669BE79,
00081     0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
00082     0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F,
00083     0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04,
00084     0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D,
00085 
00086     0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A,
00087     0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713,
00088     0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38,
00089     0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21,
00090     0x86D3D2D4, 0xF1D4E242, 0x68DDB3F8, 0x1FDA836E,
00091     0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777,
00092     0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C,
00093     0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45,
00094     0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2,
00095     0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB,
00096     0xAED16A4A, 0xD9D65ADC, 0x40DF0B66, 0x37D83BF0,
00097     0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
00098     0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6,
00099     0xBAD03605, 0xCDD70693, 0x54DE5729, 0x23D967BF,
00100     0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94,
00101     0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
00102   };
00103 
00104   CRC32::CRC32()
00105   {
00106     Initialize();
00107   }
00108 
00109   void CRC32::Initialize (void)
00110   {
00111     Memset (&CRCTable, 0, sizeof (CRCTable) );
00112 
00113     // 256 values representing ASCII character codes.
00114     for (int iCodes = 0; iCodes <= 0xFF; iCodes++)
00115     {
00116       CRCTable[iCodes] = Reflect (iCodes, 8) << 24;
00117 
00118       for (int iPos = 0; iPos < 8; iPos++)
00119       {
00120         CRCTable[iCodes] = (CRCTable[iCodes] << 1) ^ (CRCTable[iCodes] & (1 << 31) ? CRC32_POLYNOMIAL : 0);
00121       }
00122 
00123       CRCTable[iCodes] = Reflect (CRCTable[iCodes], 32);
00124     }
00125   }
00126 
00128 // Reflection is a requirement for the official CRC-32 standard.
00129 //      You can create CRCs without it, but they won't conform to the standard.
00130   t_u32 CRC32::Reflect (t_u32 ulReflect, char cChar)
00131   {
00132     t_u32 ulValue = 0;
00133 
00134     // Swap bit 0 for bit 7 bit 1 For bit 6, etc....
00135     for (int iPos = 1; iPos < (cChar + 1); iPos++)
00136     {
00137       if (ulReflect & 1)
00138         ulValue |= 1 << (cChar - iPos);
00139 
00140       ulReflect >>= 1;
00141     }
00142 
00143     return ulValue;
00144   }
00145 
00146   t_u32 CRC32::FileCRC (const char *sFileName)
00147   {
00148     t_u32 ulCRC = 0xffffffff;
00149 
00150     FILE *fSource = NULL;
00151     char sBuf[CRC32BUFSZ];
00152     t_u32 iBytesRead = 0;
00153 
00154 #ifdef WIN32_SECURE
00155 
00156     if (FOPEN_S (&fSource, sFileName, "rb") != 0)
00157 #else
00158     if (FOPEN_S (fSource, sFileName, "rb") != 0)
00159 #endif
00160     {
00161       return 0xffffffff;
00162     }
00163 
00164     do
00165     {
00166       iBytesRead = (t_u32) fread (sBuf, sizeof (char), CRC32BUFSZ, fSource);
00167       PartialCRC (&ulCRC, sBuf, iBytesRead);
00168     }
00169     while (iBytesRead == CRC32BUFSZ);
00170 
00171     fclose (fSource);
00172 
00173     return (ulCRC ^ 0xffffffff);
00174   }
00175 
00176 // This function uses the CRCTable lookup table to generate a CRC for sData
00177   t_u32 CRC32::FullCRC (const char *sData, t_u32 ulLength)
00178   {
00179     t_u32 ulCRC = 0xffffffff;
00180     PartialCRC (&ulCRC, sData, ulLength);
00181     return ulCRC ^ 0xffffffff;
00182   }
00183 
00184 // Perform the algorithm on each character
00185 // in the string, using the lookup table values.
00186   void CRC32::PartialCRC (t_u32 *ulInCRC, const char *sData, t_u32 ulLength)
00187   {
00188     while (ulLength--)
00189     {
00190       *ulInCRC = (*ulInCRC >> 8) ^ CRCTable[ (*ulInCRC & 0xFF) ^ *sData++];
00191     }
00192   }
00193 
00194 
00195 
00196   /*
00197   * A brief CRC tutorial.
00198   *
00199   * A CRC is a long-division remainder.  You add the CRC to the message,
00200   * and the whole thing (message+CRC) is a multiple of the given
00201   * CRC polynomial.  To check the CRC, you can either check that the
00202   * CRC matches the recomputed value, *or* you can check that the
00203   * remainder computed on the message+CRC is 0.  This latter approach
00204   * is used by a lot of hardware implementations, and is why so many
00205   * protocols put the end-of-frame flag after the CRC.
00206   *
00207   * It's actually the same long division you learned in school, except that
00208   * - We're working in binary, so the digits are only 0 and 1, and
00209   * - When dividing polynomials, there are no carries.  Rather than add and
00210   *   subtract, we just xor.  Thus, we tend to get a bit sloppy about
00211   *   the difference between adding and subtracting.
00212   *
00213   * A 32-bit CRC polynomial is actually 33 bits long.  But since it's
00214   * 33 bits long, bit 32 is always going to be set, so usually the CRC
00215   * is written in hex with the most significant bit omitted.  (If you're
00216   * familiar with the IEEE 754 floating-point format, it's the same idea.)
00217   *
00218   * Note that a CRC is computed over a string of *bits*, so you have
00219   * to decide on the endianness of the bits within each byte.  To get
00220   * the best error-detecting properties, this should correspond to the
00221   * order they're actually sent.  For example, standard RS-232 serial is
00222   * little-endian; the most significant bit (sometimes used for parity)
00223   * is sent last.  And when appending a CRC word to a message, you should
00224   * do it in the right order, matching the endianness.
00225   *
00226   * Just like with ordinary division, the remainder is always smaller than
00227   * the divisor (the CRC polynomial) you're dividing by.  Each step of the
00228   * division, you take one more digit (bit) of the dividend and append it
00229   * to the current remainder.  Then you figure out the appropriate multiple
00230   * of the divisor to subtract to being the remainder back into range.
00231   * In binary, it's easy - it has to be either 0 or 1, and to make the
00232   * XOR cancel, it's just a copy of bit 32 of the remainder.
00233   *
00234   * When computing a CRC, we don't care about the quotient, so we can
00235   * throw the quotient bit away, but subtract the appropriate multiple of
00236   * the polynomial from the remainder and we're back to where we started,
00237   * ready to process the next bit.
00238   *
00239   * A big-endian CRC written this way would be coded like:
00240   * for (i = 0; i < input_bits; i++) {
00241   *     multiple = remainder & 0x80000000 ? CRCPOLY : 0;
00242   *     remainder = (remainder << 1 | next_input_bit()) ^ multiple;
00243   * }
00244   * Notice how, to get at bit 32 of the shifted remainder, we look
00245   * at bit 31 of the remainder *before* shifting it.
00246   *
00247   * But also notice how the next_input_bit() bits we're shifting into
00248   * the remainder don't actually affect any decision-making until
00249   * 32 bits later.  Thus, the first 32 cycles of this are pretty boring.
00250   * Also, to add the CRC to a message, we need a 32-bit-long hole for it at
00251   * the end, so we have to add 32 extra cycles shifting in zeros at the
00252   * end of every message,
00253   *
00254   * So the standard trick is to rearrage merging in the next_input_bit()
00255   * until the moment it's needed.  Then the first 32 cycles can be precomputed,
00256   * and merging in the final 32 zero bits to make room for the CRC can be
00257   * skipped entirely.
00258   * This changes the code to:
00259   * for (i = 0; i < input_bits; i++) {
00260   *      remainder ^= next_input_bit() << 31;
00261   *     multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
00262   *     remainder = (remainder << 1) ^ multiple;
00263   * }
00264   * With this optimization, the little-endian code is simpler:
00265   * for (i = 0; i < input_bits; i++) {
00266   *      remainder ^= next_input_bit();
00267   *     multiple = (remainder & 1) ? CRCPOLY : 0;
00268   *     remainder = (remainder >> 1) ^ multiple;
00269   * }
00270   *
00271   * Note that the other details of endianness have been hidden in CRCPOLY
00272   * (which must be bit-reversed) and next_input_bit().
00273   *
00274   * However, as long as next_input_bit is returning the bits in a sensible
00275   * order, we can actually do the merging 8 or more bits at a time rather
00276   * than one bit at a time:
00277   * for (i = 0; i < input_bytes; i++) {
00278   *     remainder ^= next_input_byte() << 24;
00279   *     for (j = 0; j < 8; j++) {
00280   *             multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
00281   *             remainder = (remainder << 1) ^ multiple;
00282   *     }
00283   * }
00284   * Or in little-endian:
00285   * for (i = 0; i < input_bytes; i++) {
00286   *     remainder ^= next_input_byte();
00287   *     for (j = 0; j < 8; j++) {
00288   *             multiple = (remainder & 1) ? CRCPOLY : 0;
00289   *             remainder = (remainder << 1) ^ multiple;
00290   *     }
00291   * }
00292   * If the input is a multiple of 32 bits, you can even XOR in a 32-bit
00293   * word at a time and increase the inner loop count to 32.
00294   *
00295   * You can also mix and match the two loop styles, for example doing the
00296   * bulk of a message byte-at-a-time and adding bit-at-a-time processing
00297   * for any fractional bytes at the end.
00298   *
00299   * The only remaining optimization is to the byte-at-a-time table method.
00300   * Here, rather than just shifting one bit of the remainder to decide
00301   * in the correct multiple to subtract, we can shift a byte at a time.
00302   * This produces a 40-bit (rather than a 33-bit) intermediate remainder,
00303   * but again the multiple of the polynomial to subtract depends only on
00304   * the high bits, the high 8 bits in this case.
00305   *
00306   * The multile we need in that case is the low 32 bits of a 40-bit
00307   * value whose high 8 bits are given, and which is a multiple of the
00308   * generator polynomial.  This is simply the CRC-32 of the given
00309   * one-byte message.
00310   *
00311   * Two more details: normally, appending zero bits to a message which
00312   * is already a multiple of a polynomial produces a larger multiple of that
00313   * polynomial.  To enable a CRC to detect this condition, it's common to
00314   * invert the CRC before appending it.  This makes the remainder of the
00315   * message+crc come out not as zero, but some fixed non-zero value.
00316   *
00317   * The same problem applies to zero bits prepended to the message, and
00318   * a similar solution is used.  Instead of starting with a remainder of
00319   * 0, an initial remainder of all ones is used.  As long as you start
00320   * the same way on decoding, it doesn't make a difference.
00321   */
00322 
00323 }
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends