More functions, changed license to LGPL
[metawatch.git] / crc16ccitt.c
1 /*
2  * derived from crctester.c
3  * original header:
4  * ----------------------------------------------------------------------------
5  * CRC tester v1.3 written on 4th of February 2003 by Sven Reifegerste (zorc/reflex)
6  * This is the complete compilable C program, consisting only of this .c file.
7  * No guarantee for any mistakes.
8  *
9  * changes to CRC tester v1.2:
10  *
11  * - remove unneccessary (!(polynom&1)) test for invalid polynoms
12  *   (now also XMODEM parameters 0x8408 work in c-code as they should)
13  *
14  * changes to CRC tester v1.1:
15  *
16  * - include an crc&0crcmask after converting non-direct to direct initial
17  *   value to avoid overflow
18  *
19  * changes to CRC tester v1.0:
20  *
21  * - most int's were replaced by unsigned long's to allow longer input strings
22  *   and avoid overflows and unnecessary type-casting's
23  * ----------------------------------------------------------------------------
24  */
25
26 static const int order = 16;
27 static const unsigned long polynom = 0x1021;
28 static const int direct = 1;
29 static const unsigned long crcinit = 0xffff;
30 static const unsigned long crcxor = 0x0000;
31 static const int refin = 1;
32 static const int refout = 0;
33
34 // 'order' [1..32] is the CRC polynom order, counted without the leading '1' bit
35 // 'polynom' is the CRC polynom without leading '1' bit
36 // 'direct' [0,1] specifies the kind of algorithm: 1=direct, no augmented zero bits
37 // 'crcinit' is the initial CRC value belonging to that algorithm
38 // 'crcxor' is the final XOR value
39 // 'refin' [0,1] specifies if a data byte is reflected before processing (UART) or not
40 // 'refout' [0,1] specifies if the CRC will be reflected before XOR
41
42
43 // internal global values:
44
45 static unsigned long crcmask;
46 static unsigned long crchighbit;
47 static unsigned long crcinit_direct;
48 static unsigned long crcinit_nondirect;
49 static unsigned long crctab[256];
50
51
52 // subroutines
53
54 static unsigned long reflect (unsigned long crc, int bitnum) {
55
56         // reflects the lower 'bitnum' bits of 'crc'
57
58         unsigned long i, j=1, crcout=0;
59
60         for (i=(unsigned long)1<<(bitnum-1); i; i>>=1) {
61                 if (crc & i) crcout|=j;
62                 j<<= 1;
63         }
64         return (crcout);
65 }
66
67
68
69 static void generate_crc_table(void)
70 {
71         // make CRC lookup table used by table algorithms
72
73         int i, j;
74         unsigned long bit, crc;
75
76         for (i=0; i<256; i++) {
77
78                 crc=(unsigned long)i;
79                 if (refin) crc=reflect(crc, 8);
80                 crc<<= order-8;
81
82                 for (j=0; j<8; j++) {
83
84                         bit = crc & crchighbit;
85                         crc<<= 1;
86                         if (bit) crc^= polynom;
87                 }                       
88
89                 if (refin) crc = reflect(crc, order);
90                 crc&= crcmask;
91                 crctab[i]= crc;
92         }
93 }
94
95
96 static unsigned long crctablefast (unsigned char* p, unsigned long len)
97 {
98         // fast lookup table algorithm without augmented zero bytes, e.g. used in pkzip.
99         // only usable with polynom orders of 8, 16, 24 or 32.
100
101         unsigned long crc = crcinit_direct;
102
103         if (refin) crc = reflect(crc, order);
104
105         if (!refin) while (len--) crc = (crc << 8) ^ crctab[ ((crc >> (order-8)) & 0xff) ^ *p++];
106         else while (len--) crc = (crc >> 8) ^ crctab[ (crc & 0xff) ^ *p++];
107
108         if (refout^refin) crc = reflect(crc, order);
109         crc^= crcxor;
110         crc&= crcmask;
111
112         return(crc);
113 }
114
115 static unsigned long crctable (unsigned char* p, unsigned long len)
116 {
117         // normal lookup table algorithm with augmented zero bytes.
118         // only usable with polynom orders of 8, 16, 24 or 32.
119
120         unsigned long crc = crcinit_nondirect;
121
122         if (refin)
123                 crc = reflect(crc, order);
124
125         if (!refin)
126                 while (len--)
127                         crc = ((crc << 8) | *p++) ^ crctab[ (crc >> (order-8))  & 0xff];
128         else
129                 while (len--)
130                         crc = ((crc >> 8) | (*p++ << (order-8))) ^ crctab[ crc & 0xff];
131
132         if (!refin)
133                 while (++len < order/8)
134                         crc = (crc << 8) ^ crctab[ (crc >> (order-8))  & 0xff];
135         else
136                 while (++len < order/8)
137                         crc = (crc >> 8) ^ crctab[crc & 0xff];
138
139         if (refout^refin)
140                 crc = reflect(crc, order);
141         crc^= crcxor;
142         crc&= crcmask;
143
144         return(crc);
145 }
146
147
148
149 unsigned long crcbitbybit(unsigned char* p, unsigned long len) {
150
151         // bit by bit algorithm with augmented zero bytes.
152         // does not use lookup table, suited for polynom orders between 1...32.
153
154         unsigned long i, j, c, bit;
155         unsigned long crc = crcinit_nondirect;
156
157         for (i=0; i<len; i++) {
158
159                 c = (unsigned long)*p++;
160                 if (refin)
161                         c = reflect(c, 8);
162
163                 for (j=0x80; j; j>>=1) {
164                         bit = crc & crchighbit;
165                         crc<<= 1;
166                         if (c & j)
167                                 crc|= 1;
168                         if (bit)
169                                 crc^= polynom;
170                 }
171         }       
172
173         for (i=0; i<order; i++) {
174                 bit = crc & crchighbit;
175                 crc <<= 1;
176                 if (bit)
177                         crc^= polynom;
178         }
179
180         if (refout)
181                 crc=reflect(crc, order);
182         crc ^= crcxor;
183         crc &= crcmask;
184
185         return(crc);
186 }
187
188
189
190 unsigned long crcbitbybitfast(unsigned char* p, unsigned long len) {
191
192         // fast bit by bit algorithm without augmented zero bytes.
193         // does not use lookup table, suited for polynom orders between 1...32.
194
195         unsigned long i, j, c, bit;
196         unsigned long crc = crcinit_direct;
197
198         for (i=0; i<len; i++) {
199                 c = (unsigned long)*p++;
200                 if (refin)
201                         c = reflect(c, 8);
202
203                 for (j=0x80; j; j>>=1) {
204                         bit = crc & crchighbit;
205                         crc <<= 1;
206                         if (c & j)
207                                 bit^= crchighbit;
208                         if (bit)
209                                 crc^= polynom;
210                 }
211         }       
212
213         if (refout)
214                 crc=reflect(crc, order);
215         crc^= crcxor;
216         crc&= crcmask;
217
218         return(crc);
219 }
220
221 void crc16ccitt_init(void)
222 {
223         int i;
224         unsigned long bit, crc;
225
226         crcmask = ((((unsigned long)1<<(order-1))-1)<<1)|1;
227         crchighbit = (unsigned long)1<<(order-1);
228
229         generate_crc_table();
230
231         if (!direct) {
232                 crcinit_nondirect = crcinit;
233                 crc = crcinit;
234                 for (i=0; i<order; i++) {
235                         bit = crc & crchighbit;
236                         crc <<= 1;
237                         if (bit)
238                                 crc^= polynom;
239                 }
240                 crc &= crcmask;
241                 crcinit_direct = crc;
242         } else {
243                 crcinit_direct = crcinit;
244                 crc = crcinit;
245                 for (i=0; i<order; i++) {
246                         bit = crc & 1;
247                         if (bit)
248                                 crc^= polynom;
249                         crc >>= 1;
250                         if (bit)
251                                 crc|= crchighbit;
252                 }       
253                 crcinit_nondirect = crc;
254         }
255 }
256
257 unsigned short crc16ccitt (unsigned char *data, int len)
258 {
259         // call CRC algorithms using the CRC parameters above and print result to the console
260         return crcbitbybitfast((unsigned char *)data, len);
261 }
262
263 #if 0
264 int main() {
265
266         // test program for checking four different CRC computing types that are:
267         // crcbit(), crcbitfast(), crctable() and crctablefast(), see above.
268         // parameters are at the top of this program.
269         // Result will be printed on the console.
270
271         int i;
272         unsigned long bit, crc;
273
274
275         // at first, compute constant bit masks for whole CRC and CRC high bit
276
277         crcmask = ((((unsigned long)1<<(order-1))-1)<<1)|1;
278         crchighbit = (unsigned long)1<<(order-1);
279
280
281         // check parameters
282
283         if (order < 1 || order > 32) {
284                 printf("ERROR, invalid order, it must be between 1..32.\n");
285                 return(0);
286         }
287
288         if (polynom != (polynom & crcmask)) {
289                 printf("ERROR, invalid polynom.\n");
290                 return(0);
291         }
292
293         if (crcinit != (crcinit & crcmask)) {
294                 printf("ERROR, invalid crcinit.\n");
295                 return(0);
296         }
297
298         if (crcxor != (crcxor & crcmask)) {
299                 printf("ERROR, invalid crcxor.\n");
300                 return(0);
301         }
302
303         
304         // generate lookup table
305
306         generate_crc_table();
307
308
309         // compute missing initial CRC value
310
311         if (!direct) {
312
313                 crcinit_nondirect = crcinit;
314                 crc = crcinit;
315                 for (i=0; i<order; i++) {
316
317                         bit = crc & crchighbit;
318                         crc<<= 1;
319                         if (bit) crc^= polynom;
320                 }
321                 crc&= crcmask;
322                 crcinit_direct = crc;
323         }
324
325         else {
326
327                 crcinit_direct = crcinit;
328                 crc = crcinit;
329                 for (i=0; i<order; i++) {
330
331                         bit = crc & 1;
332                         if (bit) crc^= polynom;
333                         crc >>= 1;
334                         if (bit) crc|= crchighbit;
335                 }       
336                 crcinit_nondirect = crc;
337         }
338         
339
340         // call CRC algorithms using the CRC parameters above and print result to the console
341
342         printf("\n");
343         printf("CRC tester v1.1 written on 13/01/2003 by Sven Reifegerste (zorc/reflex)\n");
344         printf("-----------------------------------------------------------------------\n");
345         printf("\n");
346         printf("Parameters:\n");
347         printf("\n");
348         printf(" polynom             :  0x%x\n", polynom);
349         printf(" order               :  %d\n", order);
350         printf(" crcinit             :  0x%x direct, 0x%x nondirect\n", crcinit_direct, crcinit_nondirect);
351         printf(" crcxor              :  0x%x\n", crcxor);
352         printf(" refin               :  %d\n", refin);
353         printf(" refout              :  %d\n", refout);
354         printf("\n");
355         printf(" data string         :  '%s' (%d bytes)\n", string, strlen(string));
356         printf("\n");
357         printf("Results:\n");
358         printf("\n");
359
360         printf(" crc bit by bit      :  0x%x\n", crcbitbybit((unsigned char *)string, strlen(string)));
361         printf(" crc bit by bit fast :  0x%x\n", crcbitbybitfast((unsigned char *)string, strlen(string)));
362         if (!(order&7)) printf(" crc table           :  0x%x\n", crctable((unsigned char *)string, strlen(string)));
363         if (!(order&7)) printf(" crc table fast      :  0x%x\n", crctablefast((unsigned char *)string, strlen(string)));
364
365         return(0);
366 }
367 #endif