pkg/kamailio/(centos|fedora): Updated .spec and .appl files to build RPM for cdp...
[sip-router] / crc.c
1 /*
2  * $Id$
3  *
4  *  Crc - 32 + 16 BIT ANSI X3.66 + CCITT CRC checksum files
5  *
6  * Copyright (C) 2001-2003 FhG Fokus
7  *
8  * This file is part of SIP-router, a free SIP server.
9  *
10  * SIP-router is free software; you can redistribute it and/or modify
11  * it under the terms of the GNU General Public License as published by
12  * the Free Software Foundation; either version 2 of the License, or
13  * (at your option) any later version
14  *
15  * SIP-router is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18  * GNU General Public License for more details.
19  *
20  * You should have received a copy of the GNU General Public License 
21  * along with this program; if not, write to the Free Software 
22  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
23  */
24 /*!
25  * \file
26  * \brief SIP-router core ::  Crc - 32 + 16 BIT ANSI X3.66 + CCITT CRC checksum files
27  * \ingroup core
28  *
29  * Module: \ref core
30  */
31
32
33
34 #include <stdio.h>
35 #include "str.h"
36 #include "ut.h"
37 #include "crc.h"
38
39 #define OK 0
40 #define ERROR (-1)
41 #define UPDC32(ch, crc) (crc_32_tab[((crc) ^ (ch)) & 0xff] ^ ((crc) >> 8))
42 #define UPDCIT(ch, crc) (ccitt_tab[((crc) ^ (ch)) & 0xff] ^ ((crc) >> 8))
43 #define UPDC16(ch, crc) (crc_16_tab[((crc) ^ (ch)) & 0xff] ^ ((crc) >> 8))
44
45 /*
46  * Copyright (C) 1986 Gary S. Brown.  You may use this program, or
47  * code or tables extracted from it, as desired without restriction.
48  */
49 /* First, the polynomial itself and its table of feedback terms.  The  */
50 /* polynomial is                                                       */
51 /* 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 */
52 /* Note that we take it "backwards" and put the highest-order term in  */
53 /* the lowest-order bit.  The X^32 term is "implied"; the LSB is the   */
54 /* X^31 term, etc.  The X^0 term (usually shown as "+1") results in    */
55 /* the MSB being 1.                                                    */
56
57 /* added CCITT (X^16+X^12+X^5+X^0) and CRC-16 (X^16+X^15+X^2+X^0)      */
58 /* polynomials (Heinz Repp, Feb 4 1997)                                */
59
60 /* Note that the usual hardware shift register implementation, which   */
61 /* is what we're using (we're merely optimizing it by doing eight-bit  */
62 /* chunks at a time) shifts bits into the lowest-order term.  In our   */
63 /* implementation, that means shifting towards the right.  Why do we   */
64 /* do it this way?  Because the calculated CRC must be transmitted in  */
65 /* order from highest-order term to lowest-order term.  UARTs transmit */
66 /* characters in order from LSB to MSB.  By storing the CRC this way,  */
67 /* we hand it to the UART in the order low-byte to high-byte; the UART */
68 /* sends each low-bit to hight-bit; and the result is transmission bit */
69 /* by bit from highest- to lowest-order term without requiring any bit */
70 /* shuffling on our part.  Reception works similarly.                  */
71
72 /* The feedback terms table consists of 256, 32-bit entries.  Notes:   */
73 /*                                                                     */
74 /*  1. The table can be generated at runtime if desired; code to do so */
75 /*     is shown later.  It might not be obvious, but the feedback      */
76 /*     terms simply represent the results of eight shift/xor opera-    */
77 /*     tions for all combinations of data and CRC register values.     */
78 /*                                                                     */
79 /*  2. The CRC accumulation logic is the same for all CRC polynomials, */
80 /*     be they sixteen or thirty-two bits wide.  You simply choose the */
81 /*     appropriate table.  Alternatively, because the table can be     */
82 /*     generated at runtime, you can start by generating the table for */
83 /*     the polynomial in question and use exactly the same "updcrc",   */
84 /*     if your application needn't simultaneously handle two CRC       */
85 /*     polynomials.  (Note, however, that XMODEM is strange.)          */
86 /*                                                                     */
87 /*  3. For 16-bit CRCs, the table entries need be only 16 bits wide;   */
88 /*     of course, 32-bit entries work OK if the high 16 bits are zero. */
89 /*                                                                     */
90 /*  4. The values must be right-shifted by eight bits by the "updcrc"  */
91 /*     logic; the shift must be unsigned (bring in zeroes).  On some   */
92 /*     hardware you could probably optimize the shift in assembler by  */
93 /*     using byte-swap instructions.                                   */
94
95 unsigned long int crc_32_tab[] = { /* CRC polynomial 0xedb88320 */
96 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
97 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
98 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
99 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
100 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
101 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
102 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
103 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
104 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
105 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
106 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
107 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
108 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
109 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
110 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
111 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
112 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
113 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
114 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
115 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
116 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
117 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
118 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
119 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
120 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
121 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
122 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
123 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
124 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
125 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
126 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
127 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
128 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
129 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
130 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
131 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
132 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
133 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
134 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
135 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
136 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
137 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
138 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
139 };
140
141 unsigned short int ccitt_tab[] = { /* CRC polynomial 0x8408 */
142 0x0000, 0x1189, 0x2312, 0x329B, 0x4624, 0x57AD, 0x6536, 0x74BF,
143 0x8C48, 0x9DC1, 0xAF5A, 0xBED3, 0xCA6C, 0xDBE5, 0xE97E, 0xF8F7,
144 0x1081, 0x0108, 0x3393, 0x221A, 0x56A5, 0x472C, 0x75B7, 0x643E,
145 0x9CC9, 0x8D40, 0xBFDB, 0xAE52, 0xDAED, 0xCB64, 0xF9FF, 0xE876,
146 0x2102, 0x308B, 0x0210, 0x1399, 0x6726, 0x76AF, 0x4434, 0x55BD,
147 0xAD4A, 0xBCC3, 0x8E58, 0x9FD1, 0xEB6E, 0xFAE7, 0xC87C, 0xD9F5,
148 0x3183, 0x200A, 0x1291, 0x0318, 0x77A7, 0x662E, 0x54B5, 0x453C,
149 0xBDCB, 0xAC42, 0x9ED9, 0x8F50, 0xFBEF, 0xEA66, 0xD8FD, 0xC974,
150 0x4204, 0x538D, 0x6116, 0x709F, 0x0420, 0x15A9, 0x2732, 0x36BB,
151 0xCE4C, 0xDFC5, 0xED5E, 0xFCD7, 0x8868, 0x99E1, 0xAB7A, 0xBAF3,
152 0x5285, 0x430C, 0x7197, 0x601E, 0x14A1, 0x0528, 0x37B3, 0x263A,
153 0xDECD, 0xCF44, 0xFDDF, 0xEC56, 0x98E9, 0x8960, 0xBBFB, 0xAA72,
154 0x6306, 0x728F, 0x4014, 0x519D, 0x2522, 0x34AB, 0x0630, 0x17B9,
155 0xEF4E, 0xFEC7, 0xCC5C, 0xDDD5, 0xA96A, 0xB8E3, 0x8A78, 0x9BF1,
156 0x7387, 0x620E, 0x5095, 0x411C, 0x35A3, 0x242A, 0x16B1, 0x0738,
157 0xFFCF, 0xEE46, 0xDCDD, 0xCD54, 0xB9EB, 0xA862, 0x9AF9, 0x8B70,
158 0x8408, 0x9581, 0xA71A, 0xB693, 0xC22C, 0xD3A5, 0xE13E, 0xF0B7,
159 0x0840, 0x19C9, 0x2B52, 0x3ADB, 0x4E64, 0x5FED, 0x6D76, 0x7CFF,
160 0x9489, 0x8500, 0xB79B, 0xA612, 0xD2AD, 0xC324, 0xF1BF, 0xE036,
161 0x18C1, 0x0948, 0x3BD3, 0x2A5A, 0x5EE5, 0x4F6C, 0x7DF7, 0x6C7E,
162 0xA50A, 0xB483, 0x8618, 0x9791, 0xE32E, 0xF2A7, 0xC03C, 0xD1B5,
163 0x2942, 0x38CB, 0x0A50, 0x1BD9, 0x6F66, 0x7EEF, 0x4C74, 0x5DFD,
164 0xB58B, 0xA402, 0x9699, 0x8710, 0xF3AF, 0xE226, 0xD0BD, 0xC134,
165 0x39C3, 0x284A, 0x1AD1, 0x0B58, 0x7FE7, 0x6E6E, 0x5CF5, 0x4D7C,
166 0xC60C, 0xD785, 0xE51E, 0xF497, 0x8028, 0x91A1, 0xA33A, 0xB2B3,
167 0x4A44, 0x5BCD, 0x6956, 0x78DF, 0x0C60, 0x1DE9, 0x2F72, 0x3EFB,
168 0xD68D, 0xC704, 0xF59F, 0xE416, 0x90A9, 0x8120, 0xB3BB, 0xA232,
169 0x5AC5, 0x4B4C, 0x79D7, 0x685E, 0x1CE1, 0x0D68, 0x3FF3, 0x2E7A,
170 0xE70E, 0xF687, 0xC41C, 0xD595, 0xA12A, 0xB0A3, 0x8238, 0x93B1,
171 0x6B46, 0x7ACF, 0x4854, 0x59DD, 0x2D62, 0x3CEB, 0x0E70, 0x1FF9,
172 0xF78F, 0xE606, 0xD49D, 0xC514, 0xB1AB, 0xA022, 0x92B9, 0x8330,
173 0x7BC7, 0x6A4E, 0x58D5, 0x495C, 0x3DE3, 0x2C6A, 0x1EF1, 0x0F78,
174 };
175
176 unsigned short int crc_16_tab[] = { /* CRC polynomial 0xA001 */
177 0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241,
178 0xC601, 0x06C0, 0x0780, 0xC741, 0x0500, 0xC5C1, 0xC481, 0x0440,
179 0xCC01, 0x0CC0, 0x0D80, 0xCD41, 0x0F00, 0xCFC1, 0xCE81, 0x0E40,
180 0x0A00, 0xCAC1, 0xCB81, 0x0B40, 0xC901, 0x09C0, 0x0880, 0xC841,
181 0xD801, 0x18C0, 0x1980, 0xD941, 0x1B00, 0xDBC1, 0xDA81, 0x1A40,
182 0x1E00, 0xDEC1, 0xDF81, 0x1F40, 0xDD01, 0x1DC0, 0x1C80, 0xDC41,
183 0x1400, 0xD4C1, 0xD581, 0x1540, 0xD701, 0x17C0, 0x1680, 0xD641,
184 0xD201, 0x12C0, 0x1380, 0xD341, 0x1100, 0xD1C1, 0xD081, 0x1040,
185 0xF001, 0x30C0, 0x3180, 0xF141, 0x3300, 0xF3C1, 0xF281, 0x3240,
186 0x3600, 0xF6C1, 0xF781, 0x3740, 0xF501, 0x35C0, 0x3480, 0xF441,
187 0x3C00, 0xFCC1, 0xFD81, 0x3D40, 0xFF01, 0x3FC0, 0x3E80, 0xFE41,
188 0xFA01, 0x3AC0, 0x3B80, 0xFB41, 0x3900, 0xF9C1, 0xF881, 0x3840,
189 0x2800, 0xE8C1, 0xE981, 0x2940, 0xEB01, 0x2BC0, 0x2A80, 0xEA41,
190 0xEE01, 0x2EC0, 0x2F80, 0xEF41, 0x2D00, 0xEDC1, 0xEC81, 0x2C40,
191 0xE401, 0x24C0, 0x2580, 0xE541, 0x2700, 0xE7C1, 0xE681, 0x2640,
192 0x2200, 0xE2C1, 0xE381, 0x2340, 0xE101, 0x21C0, 0x2080, 0xE041,
193 0xA001, 0x60C0, 0x6180, 0xA141, 0x6300, 0xA3C1, 0xA281, 0x6240,
194 0x6600, 0xA6C1, 0xA781, 0x6740, 0xA501, 0x65C0, 0x6480, 0xA441,
195 0x6C00, 0xACC1, 0xAD81, 0x6D40, 0xAF01, 0x6FC0, 0x6E80, 0xAE41,
196 0xAA01, 0x6AC0, 0x6B80, 0xAB41, 0x6900, 0xA9C1, 0xA881, 0x6840,
197 0x7800, 0xB8C1, 0xB981, 0x7940, 0xBB01, 0x7BC0, 0x7A80, 0xBA41,
198 0xBE01, 0x7EC0, 0x7F80, 0xBF41, 0x7D00, 0xBDC1, 0xBC81, 0x7C40,
199 0xB401, 0x74C0, 0x7580, 0xB541, 0x7700, 0xB7C1, 0xB681, 0x7640,
200 0x7200, 0xB2C1, 0xB381, 0x7340, 0xB101, 0x71C0, 0x7080, 0xB041,
201 0x5000, 0x90C1, 0x9181, 0x5140, 0x9301, 0x53C0, 0x5280, 0x9241,
202 0x9601, 0x56C0, 0x5780, 0x9741, 0x5500, 0x95C1, 0x9481, 0x5440,
203 0x9C01, 0x5CC0, 0x5D80, 0x9D41, 0x5F00, 0x9FC1, 0x9E81, 0x5E40,
204 0x5A00, 0x9AC1, 0x9B81, 0x5B40, 0x9901, 0x59C0, 0x5880, 0x9841,
205 0x8801, 0x48C0, 0x4980, 0x8941, 0x4B00, 0x8BC1, 0x8A81, 0x4A40,
206 0x4E00, 0x8EC1, 0x8F81, 0x4F40, 0x8D01, 0x4DC0, 0x4C80, 0x8C41,
207 0x4400, 0x84C1, 0x8581, 0x4540, 0x8701, 0x47C0, 0x4680, 0x8641,
208 0x8201, 0x42C0, 0x4380, 0x8341, 0x4100, 0x81C1, 0x8081, 0x4040,
209 };
210
211 unsigned short crcitt_string_ex( char *s, int len, register unsigned short ccitt) {
212         ccitt = ~ccitt;
213         while( len ) {
214                 ccitt = UPDCIT(*s, ccitt);
215                 s++; len--;
216         }
217         return ~ccitt;
218 }
219
220 unsigned short crcitt_string( char *s, int len )
221 {
222         return crcitt_string_ex(s, len, 0);
223 }
224
225 void crcitt_string_array( char *dst, str src[], int size )
226 {
227         register int i;
228         register unsigned short ccitt;
229         register char *c;
230         register int len;
231         int str_len;
232
233         ccitt = 0xFFFF;
234         str_len=CRC16_LEN;
235         for (i=0; i<size; i++ ) {
236                 c=src[i].s;
237                 len=src[i].len;
238                 while(len) {
239                         ccitt = UPDCIT( *c, ccitt );
240                         c++;len--;
241                 }
242         }
243         ccitt = ~ccitt;
244         if (int2reverse_hex( &dst, &str_len, ccitt )==-1) {
245                 /* bug ... printed ccitt value longer than CRC32_LEN */
246                 LOG(L_CRIT, "ERROR: crcitt_string_array: string conversion incomplete\n");
247         }
248         /* padding */
249         while( str_len ) {
250                 *dst='0';
251                 dst++;
252                 str_len--;
253         }
254 }
255                 
256                                 
257
258 int crc32file (char *name)
259 {
260         register FILE *fin;
261         register unsigned long crc32;
262         register unsigned short ccitt, crc16;
263         register int c;
264         register long charcnt;
265
266         crc32 = 0xFFFFFFFF; ccitt = 0xFFFF;
267         crc16 = charcnt = 0;
268         if ((fin=fopen(name, "rb"))==NULL)
269         {
270                 perror(name);
271                 return ERROR;
272         }
273         while ((c=getc(fin))!=EOF) {
274                 ++charcnt;
275                 crc32 = UPDC32(c, crc32);
276                 ccitt = UPDCIT(c, ccitt);
277                 crc16 = UPDC16(c, crc16);
278         }
279
280         if (ferror(fin))
281         {
282                 perror(name);
283                 fclose(fin); return ERROR;
284         }
285         else
286         {
287                 crc32 = ~crc32;
288                 ccitt = ~ccitt;
289
290                 printf(" %08lX  %04X  %04X%10ld   %s\n",
291                                                 crc32, ccitt, crc16, charcnt, name);
292         }
293
294         fclose(fin); return OK;
295 }
296
297 /*!
298  * \brief CRC32 value from source string
299  * \param source_string source string
300  * \param hash_ret calulated CRC32
301  */
302 void crc32_uint (str *source_string, unsigned int *hash_ret) 
303 {       
304         unsigned int hash;      
305         unsigned int len;
306         const char *data;
307         
308         hash = 0xffffffff;
309         data = source_string->s;
310         
311         for (len = source_string->len / 4; len--; data += 4) {
312                 hash = crc_32_tab[((unsigned char)hash) ^ data[0]] ^ (hash >> 8);
313                 hash = crc_32_tab[((unsigned char)hash) ^ data[1]] ^ (hash >> 8);
314                 hash = crc_32_tab[((unsigned char)hash) ^ data[2]] ^ (hash >> 8);
315                 hash = crc_32_tab[((unsigned char)hash) ^ data[3]] ^ (hash >> 8);
316         }
317         
318         for (len = source_string->len % 4; len--; data++) {
319                 hash = crc_32_tab[((unsigned char)hash) ^ *data] ^ (hash >> 8);
320         }
321         
322         *hash_ret = ~hash;
323 }
324
325 /*
326
327 int main(int argc, char **argv)
328 {
329         register int errors = 0;
330
331         puts("  CRC-32  CCITT  CRC-16    size   name\n"
332                          "-----------------------------------------------");
333
334         while( --argc > 0)
335                 errors |= crc32file( *++argv);
336         exit(errors != 0);
337 }
338 */
339
340 /* End of crc.c */
341