Kamailio - The Open Source SIP Server: crc.c Source File

00001 /*
00002  * $Id: crc.c 4924 2008-09-16 11:08:44Z henningw $
00003  *
00004  * Copyright (C) 1986 Gary S. Brown.  You may use this program, or
00005  * code or tables extracted from it, as desired without restriction.
00006  * Copyright (C) 2001-2003 FhG Fokus
00007  *
00008  * This file is part of Kamailio, a free SIP server.
00009  *
00010  * Kamailio is free software; you can redistribute it and/or modify
00011  * it under the terms of the GNU General Public License as published by
00012  * the Free Software Foundation; either version 2 of the License, or
00013  * (at your option) any later version
00014  *
00015  * Kamailio is distributed in the hope that it will be useful,
00016  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00017  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00018  * GNU General Public License for more details.
00019  *
00020  * You should have received a copy of the GNU General Public License 
00021  * along with this program; if not, write to the Free Software 
00022  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00023  */
00024 
00025 /*!
00026  * \file
00027  * \brief CRC - 32 + 16 BIT ANSI X3.66 + CCITT CRC checksum files
00028  * - \ref CRCImplementation
00029  */
00030 
00031 /*! \page CRCImplementation CRC 32, CRC16 and CCITT implementation
00032  * \section introduction Introduction
00033  * First, the polynomial itself and its table of feedback terms.  The
00034  * polynomial is
00035  * X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^1+X^0
00036  * Note that we take it "backwards" and put the highest-order term in
00037  * the lowest-order bit.  The X^32 term is "implied"; the LSB is the
00038  * X^31 term, etc.  The X^0 term (usually shown as "+1") results in
00039  * the MSB being 1.
00040  * added CCITT (X^16+X^12+X^5+X^0) and CRC-16 (X^16+X^15+X^2+X^0)
00041  * polynomials (Heinz Repp, Feb 4 1997)
00042  * \section method Working method
00043  * Note that the usual hardware shift register implementation, which
00044  * is what we're using (we're merely optimizing it by doing eight-bit
00045  * chunks at a time) shifts bits into the lowest-order term.  In our
00046  * implementation, that means shifting towards the right.  Why do we
00047  * do it this way?  Because the calculated CRC must be transmitted in
00048  * order from highest-order term to lowest-order term.  UARTs transmit
00049  * characters in order from LSB to MSB.  By storing the CRC this way,
00050  * we hand it to the UART in the order low-byte to high-byte; the UART
00051  * sends each low-bit to hight-bit; and the result is transmission bit
00052  * by bit from highest- to lowest-order term without requiring any bit
00053  * shuffling on our part.  Reception works similarly.
00054  * \section tables Tables
00055  * The feedback terms table consists of 256, 32-bit entries.  Notes:
00056  *  - The table can be generated at runtime if desired; code to do so
00057  *     is shown later.  It might not be obvious, but the feedback
00058  *     terms simply represent the results of eight shift/xor opera-
00059  *     tions for all combinations of data and CRC register values.
00060  *  - The CRC accumulation logic is the same for all CRC polynomials,
00061  *     be they sixteen or thirty-two bits wide.  You simply choose the
00062  *     appropriate table.  Alternatively, because the table can be
00063  *     generated at runtime, you can start by generating the table for
00064  *     the polynomial in question and use exactly the same "updcrc",
00065  *     if your application needn't simultaneously handle two CRC
00066  *     polynomials.  (Note, however, that XMODEM is strange.)
00067  *  - For 16-bit CRCs, the table entries need be only 16 bits wide;
00068  *     of course, 32-bit entries work OK if the high 16 bits are zero.
00069  *  - The values must be right-shifted by eight bits by the "updcrc"
00070  *     logic; the shift must be unsigned (bring in zeroes).  On some
00071  *     hardware you could probably optimize the shift in assembler by
00072  *     using byte-swap instructions.
00073  */
00074 
00075 #include <stdio.h>
00076 #include "str.h"
00077 #include "ut.h"
00078 #include "crc.h"
00079 
00080 #define UPDC32(ch, crc) (crc_32_tab[((crc) ^ (ch)) & 0xff] ^ ((crc) >> 8))
00081 #define UPDCIT(ch, crc) (ccitt_tab[((crc) ^ (ch)) & 0xff] ^ ((crc) >> 8))
00082 #define UPDC16(ch, crc) (crc_16_tab[((crc) ^ (ch)) & 0xff] ^ ((crc) >> 8))
00083 
00084 
00085 /*! CRC polynomial 0xedb88320 */
00086 unsigned long int crc_32_tab[] = {
00087 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
00088 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
00089 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
00090 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
00091 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
00092 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
00093 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
00094 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
00095 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
00096 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
00097 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
00098 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
00099 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
00100 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
00101 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
00102 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
00103 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
00104 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
00105 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
00106 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
00107 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
00108 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
00109 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
00110 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
00111 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
00112 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
00113 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
00114 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
00115 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
00116 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
00117 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
00118 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
00119 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
00120 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
00121 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
00122 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
00123 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
00124 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
00125 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
00126 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
00127 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
00128 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
00129 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
00130 };
00131 
00132 
00133 /*! CRC polynomial 0x8408 */
00134 unsigned short int ccitt_tab[] = {
00135 0x0000, 0x1189, 0x2312, 0x329B, 0x4624, 0x57AD, 0x6536, 0x74BF,
00136 0x8C48, 0x9DC1, 0xAF5A, 0xBED3, 0xCA6C, 0xDBE5, 0xE97E, 0xF8F7,
00137 0x1081, 0x0108, 0x3393, 0x221A, 0x56A5, 0x472C, 0x75B7, 0x643E,
00138 0x9CC9, 0x8D40, 0xBFDB, 0xAE52, 0xDAED, 0xCB64, 0xF9FF, 0xE876,
00139 0x2102, 0x308B, 0x0210, 0x1399, 0x6726, 0x76AF, 0x4434, 0x55BD,
00140 0xAD4A, 0xBCC3, 0x8E58, 0x9FD1, 0xEB6E, 0xFAE7, 0xC87C, 0xD9F5,
00141 0x3183, 0x200A, 0x1291, 0x0318, 0x77A7, 0x662E, 0x54B5, 0x453C,
00142 0xBDCB, 0xAC42, 0x9ED9, 0x8F50, 0xFBEF, 0xEA66, 0xD8FD, 0xC974,
00143 0x4204, 0x538D, 0x6116, 0x709F, 0x0420, 0x15A9, 0x2732, 0x36BB,
00144 0xCE4C, 0xDFC5, 0xED5E, 0xFCD7, 0x8868, 0x99E1, 0xAB7A, 0xBAF3,
00145 0x5285, 0x430C, 0x7197, 0x601E, 0x14A1, 0x0528, 0x37B3, 0x263A,
00146 0xDECD, 0xCF44, 0xFDDF, 0xEC56, 0x98E9, 0x8960, 0xBBFB, 0xAA72,
00147 0x6306, 0x728F, 0x4014, 0x519D, 0x2522, 0x34AB, 0x0630, 0x17B9,
00148 0xEF4E, 0xFEC7, 0xCC5C, 0xDDD5, 0xA96A, 0xB8E3, 0x8A78, 0x9BF1,
00149 0x7387, 0x620E, 0x5095, 0x411C, 0x35A3, 0x242A, 0x16B1, 0x0738,
00150 0xFFCF, 0xEE46, 0xDCDD, 0xCD54, 0xB9EB, 0xA862, 0x9AF9, 0x8B70,
00151 0x8408, 0x9581, 0xA71A, 0xB693, 0xC22C, 0xD3A5, 0xE13E, 0xF0B7,
00152 0x0840, 0x19C9, 0x2B52, 0x3ADB, 0x4E64, 0x5FED, 0x6D76, 0x7CFF,
00153 0x9489, 0x8500, 0xB79B, 0xA612, 0xD2AD, 0xC324, 0xF1BF, 0xE036,
00154 0x18C1, 0x0948, 0x3BD3, 0x2A5A, 0x5EE5, 0x4F6C, 0x7DF7, 0x6C7E,
00155 0xA50A, 0xB483, 0x8618, 0x9791, 0xE32E, 0xF2A7, 0xC03C, 0xD1B5,
00156 0x2942, 0x38CB, 0x0A50, 0x1BD9, 0x6F66, 0x7EEF, 0x4C74, 0x5DFD,
00157 0xB58B, 0xA402, 0x9699, 0x8710, 0xF3AF, 0xE226, 0xD0BD, 0xC134,
00158 0x39C3, 0x284A, 0x1AD1, 0x0B58, 0x7FE7, 0x6E6E, 0x5CF5, 0x4D7C,
00159 0xC60C, 0xD785, 0xE51E, 0xF497, 0x8028, 0x91A1, 0xA33A, 0xB2B3,
00160 0x4A44, 0x5BCD, 0x6956, 0x78DF, 0x0C60, 0x1DE9, 0x2F72, 0x3EFB,
00161 0xD68D, 0xC704, 0xF59F, 0xE416, 0x90A9, 0x8120, 0xB3BB, 0xA232,
00162 0x5AC5, 0x4B4C, 0x79D7, 0x685E, 0x1CE1, 0x0D68, 0x3FF3, 0x2E7A,
00163 0xE70E, 0xF687, 0xC41C, 0xD595, 0xA12A, 0xB0A3, 0x8238, 0x93B1,
00164 0x6B46, 0x7ACF, 0x4854, 0x59DD, 0x2D62, 0x3CEB, 0x0E70, 0x1FF9,
00165 0xF78F, 0xE606, 0xD49D, 0xC514, 0xB1AB, 0xA022, 0x92B9, 0x8330,
00166 0x7BC7, 0x6A4E, 0x58D5, 0x495C, 0x3DE3, 0x2C6A, 0x1EF1, 0x0F78,
00167 };
00168 
00169 
00170 /*! CRC polynomial 0xA001 */
00171 unsigned short int crc_16_tab[] = {
00172 0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241,
00173 0xC601, 0x06C0, 0x0780, 0xC741, 0x0500, 0xC5C1, 0xC481, 0x0440,
00174 0xCC01, 0x0CC0, 0x0D80, 0xCD41, 0x0F00, 0xCFC1, 0xCE81, 0x0E40,
00175 0x0A00, 0xCAC1, 0xCB81, 0x0B40, 0xC901, 0x09C0, 0x0880, 0xC841,
00176 0xD801, 0x18C0, 0x1980, 0xD941, 0x1B00, 0xDBC1, 0xDA81, 0x1A40,
00177 0x1E00, 0xDEC1, 0xDF81, 0x1F40, 0xDD01, 0x1DC0, 0x1C80, 0xDC41,
00178 0x1400, 0xD4C1, 0xD581, 0x1540, 0xD701, 0x17C0, 0x1680, 0xD641,
00179 0xD201, 0x12C0, 0x1380, 0xD341, 0x1100, 0xD1C1, 0xD081, 0x1040,
00180 0xF001, 0x30C0, 0x3180, 0xF141, 0x3300, 0xF3C1, 0xF281, 0x3240,
00181 0x3600, 0xF6C1, 0xF781, 0x3740, 0xF501, 0x35C0, 0x3480, 0xF441,
00182 0x3C00, 0xFCC1, 0xFD81, 0x3D40, 0xFF01, 0x3FC0, 0x3E80, 0xFE41,
00183 0xFA01, 0x3AC0, 0x3B80, 0xFB41, 0x3900, 0xF9C1, 0xF881, 0x3840,
00184 0x2800, 0xE8C1, 0xE981, 0x2940, 0xEB01, 0x2BC0, 0x2A80, 0xEA41,
00185 0xEE01, 0x2EC0, 0x2F80, 0xEF41, 0x2D00, 0xEDC1, 0xEC81, 0x2C40,
00186 0xE401, 0x24C0, 0x2580, 0xE541, 0x2700, 0xE7C1, 0xE681, 0x2640,
00187 0x2200, 0xE2C1, 0xE381, 0x2340, 0xE101, 0x21C0, 0x2080, 0xE041,
00188 0xA001, 0x60C0, 0x6180, 0xA141, 0x6300, 0xA3C1, 0xA281, 0x6240,
00189 0x6600, 0xA6C1, 0xA781, 0x6740, 0xA501, 0x65C0, 0x6480, 0xA441,
00190 0x6C00, 0xACC1, 0xAD81, 0x6D40, 0xAF01, 0x6FC0, 0x6E80, 0xAE41,
00191 0xAA01, 0x6AC0, 0x6B80, 0xAB41, 0x6900, 0xA9C1, 0xA881, 0x6840,
00192 0x7800, 0xB8C1, 0xB981, 0x7940, 0xBB01, 0x7BC0, 0x7A80, 0xBA41,
00193 0xBE01, 0x7EC0, 0x7F80, 0xBF41, 0x7D00, 0xBDC1, 0xBC81, 0x7C40,
00194 0xB401, 0x74C0, 0x7580, 0xB541, 0x7700, 0xB7C1, 0xB681, 0x7640,
00195 0x7200, 0xB2C1, 0xB381, 0x7340, 0xB101, 0x71C0, 0x7080, 0xB041,
00196 0x5000, 0x90C1, 0x9181, 0x5140, 0x9301, 0x53C0, 0x5280, 0x9241,
00197 0x9601, 0x56C0, 0x5780, 0x9741, 0x5500, 0x95C1, 0x9481, 0x5440,
00198 0x9C01, 0x5CC0, 0x5D80, 0x9D41, 0x5F00, 0x9FC1, 0x9E81, 0x5E40,
00199 0x5A00, 0x9AC1, 0x9B81, 0x5B40, 0x9901, 0x59C0, 0x5880, 0x9841,
00200 0x8801, 0x48C0, 0x4980, 0x8941, 0x4B00, 0x8BC1, 0x8A81, 0x4A40,
00201 0x4E00, 0x8EC1, 0x8F81, 0x4F40, 0x8D01, 0x4DC0, 0x4C80, 0x8C41,
00202 0x4400, 0x84C1, 0x8581, 0x4540, 0x8701, 0x47C0, 0x4680, 0x8641,
00203 0x8201, 0x42C0, 0x4380, 0x8341, 0x4100, 0x81C1, 0x8081, 0x4040,
00204 };
00205 
00206 
00207 /*!
00208  * \brief Return CCITT value from string
00209  * \param s intput char
00210  * \param len input length
00211  * \return CCITT string 
00212  */
00213 unsigned short crcitt_string( char *s, int len )
00214 {
00215    register unsigned short ccitt;
00216    
00217    ccitt = 0xFFFF;
00218 
00219    while( len ) {
00220       ccitt = UPDCIT(*s, ccitt);
00221       s++; len--;
00222    }
00223    return ~ccitt;
00224 }
00225 
00226 
00227 /*!
00228  * \brief CCITT value from array
00229  * \param dst destination
00230  * \param src source array
00231  * \param size array size
00232  */
00233 void crcitt_string_array( char *dst, str src[], int size )
00234 {
00235    register int i;
00236    register unsigned short ccitt;
00237    register char *c;
00238    register int len;
00239    int str_len;
00240 
00241    ccitt = 0xFFFF;
00242    str_len=CRC16_LEN;
00243    for (i=0; i<size; i++ ) {
00244       c=src[i].s;
00245       len=src[i].len;
00246       while(len) {
00247          ccitt = UPDCIT( *c, ccitt );
00248          c++;len--;
00249       }
00250    }
00251    ccitt = ~ccitt;
00252    if (int2reverse_hex( &dst, &str_len, ccitt )==-1) {
00253       /* bug ... printed ccitt value longer than CRC32_LEN */
00254       LM_CRIT("string conversion incomplete\n");
00255    }
00256    /* padding */
00257    while( str_len ) {
00258       *dst='0';
00259       dst++;
00260       str_len--;
00261    }
00262 }
00263 
00264 
00265 /*!
00266  * \brief CRC32 value from source string
00267  * \param source_string source string
00268  * \param hash_ret calulated CRC32
00269  */
00270 void crc32_uint (str *source_string, unsigned int *hash_ret) {
00271    unsigned int hash;
00272    unsigned int len;
00273    const char *data;
00274 
00275    hash = 0xffffffff;
00276    data = source_string->s;
00277    for (len = source_string->len / 4; len--; data += 4) {
00278       hash = crc_32_tab[((unsigned char)hash) ^ data[0]] ^ (hash >> 8);
00279       hash = crc_32_tab[((unsigned char)hash) ^ data[1]] ^ (hash >> 8);
00280       hash = crc_32_tab[((unsigned char)hash) ^ data[2]] ^ (hash >> 8);
00281       hash = crc_32_tab[((unsigned char)hash) ^ data[3]] ^ (hash >> 8);
00282    }
00283    for (len = source_string->len % 4; len--; data++) {
00284       hash = crc_32_tab[((unsigned char)hash) ^ *data] ^ (hash >> 8);
00285    }
00286    *hash_ret = hash;
00287 }