1 /* Copyright (c) 2002, 2003, 2004 Marek Michalkiewicz
2 Copyright (c) 2005, 2007 Joerg Wunsch
3 Copyright (c) 2013 Dave Hylands
4 Copyright (c) 2013 Frederic Nadeau
5 All rights reserved.
6
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions are met:
9
10 * Redistributions of source code must retain the above copyright
11 notice, this list of conditions and the following disclaimer.
12
13 * Redistributions in binary form must reproduce the above copyright
14 notice, this list of conditions and the following disclaimer in
15 the documentation and/or other materials provided with the
16 distribution.
17
18 * Neither the name of the copyright holders nor the names of
19 contributors may be used to endorse or promote products derived
20 from this software without specific prior written permission.
21
22 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
23 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
26 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
27 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
28 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
29 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
30 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
31 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 POSSIBILITY OF SUCH DAMAGE. */
33
34 /* $Id: crc16.h 2398 2013-05-08 11:45:54Z joerg_wunsch $ */
35
36 #ifndef _UTIL_CRC16_H_
37 #define _UTIL_CRC16_H_
38
39 #include <stdint.h>
40
41 /** \file */
42 /** \defgroup util_crc <util/crc16.h>: CRC Computations
43 \code#include <util/crc16.h>\endcode
44
45 This header file provides a optimized inline functions for calculating
46 cyclic redundancy checks (CRC) using common polynomials.
47
48 \par References:
49
50 \par
51
52 See the Dallas Semiconductor app note 27 for 8051 assembler example and
53 general CRC optimization suggestions. The table on the last page of the
54 app note is the key to understanding these implementations.
55
56 \par
57
58 Jack Crenshaw's "Implementing CRCs" article in the January 1992 isue of \e
59 Embedded \e Systems \e Programming. This may be difficult to find, but it
60 explains CRC's in very clear and concise terms. Well worth the effort to
61 obtain a copy.
62
63 A typical application would look like:
64
65 \code
66 // Dallas iButton test vector.
67 uint8_t serno[] = { 0x02, 0x1c, 0xb8, 0x01, 0, 0, 0, 0xa2 };
68
69 int
70 checkcrc(void)
71 {
72 uint8_t crc = 0, i;
73
74 for (i = 0; i < sizeof serno / sizeof serno[0]; i++)
75 crc = _crc_ibutton_update(crc, serno[i]);
76
77 return crc; // must be 0
78 }
79 \endcode
80 */
81
82 /** \ingroup util_crc
83 Optimized CRC-16 calculation.
84
85 Polynomial: x^16 + x^15 + x^2 + 1 (0xa001)<br>
86 Initial value: 0xffff
87
88 This CRC is normally used in disk-drive controllers.
89
90 The following is the equivalent functionality written in C.
91
92 \code
93 uint16_t
94 crc16_update(uint16_t crc, uint8_t a)
95 {
96 int i;
97
98 crc ^= a;
99 for (i = 0; i < 8; ++i)
100 {
101 if (crc & 1)
102 crc = (crc >> 1) ^ 0xA001;
103 else
104 crc = (crc >> 1);
105 }
106
107 return crc;
108 }
109
110 \endcode */
111
112 static __inline__ uint16_t
_crc16_update(uint16_t __crc,uint8_t __data)113 _crc16_update(uint16_t __crc, uint8_t __data)
114 {
115 uint8_t __tmp;
116 uint16_t __ret;
117
118 __asm__ __volatile__ (
119 "eor %A0,%2" "\n\t"
120 "mov %1,%A0" "\n\t"
121 "swap %1" "\n\t"
122 "eor %1,%A0" "\n\t"
123 "mov __tmp_reg__,%1" "\n\t"
124 "lsr %1" "\n\t"
125 "lsr %1" "\n\t"
126 "eor %1,__tmp_reg__" "\n\t"
127 "mov __tmp_reg__,%1" "\n\t"
128 "lsr %1" "\n\t"
129 "eor %1,__tmp_reg__" "\n\t"
130 "andi %1,0x07" "\n\t"
131 "mov __tmp_reg__,%A0" "\n\t"
132 "mov %A0,%B0" "\n\t"
133 "lsr %1" "\n\t"
134 "ror __tmp_reg__" "\n\t"
135 "ror %1" "\n\t"
136 "mov %B0,__tmp_reg__" "\n\t"
137 "eor %A0,%1" "\n\t"
138 "lsr __tmp_reg__" "\n\t"
139 "ror %1" "\n\t"
140 "eor %B0,__tmp_reg__" "\n\t"
141 "eor %A0,%1"
142 : "=r" (__ret), "=d" (__tmp)
143 : "r" (__data), "0" (__crc)
144 : "r0"
145 );
146 return __ret;
147 }
148
149 /** \ingroup util_crc
150 Optimized CRC-XMODEM calculation.
151
152 Polynomial: x^16 + x^12 + x^5 + 1 (0x1021)<br>
153 Initial value: 0x0
154
155 This is the CRC used by the Xmodem-CRC protocol.
156
157 The following is the equivalent functionality written in C.
158
159 \code
160 uint16_t
161 crc_xmodem_update (uint16_t crc, uint8_t data)
162 {
163 int i;
164
165 crc = crc ^ ((uint16_t)data << 8);
166 for (i=0; i<8; i++)
167 {
168 if (crc & 0x8000)
169 crc = (crc << 1) ^ 0x1021;
170 else
171 crc <<= 1;
172 }
173
174 return crc;
175 }
176 \endcode */
177
178 static __inline__ uint16_t
_crc_xmodem_update(uint16_t __crc,uint8_t __data)179 _crc_xmodem_update(uint16_t __crc, uint8_t __data)
180 {
181 uint16_t __ret; /* %B0:%A0 (alias for __crc) */
182 uint8_t __tmp1; /* %1 */
183 uint8_t __tmp2; /* %2 */
184 /* %3 __data */
185
186 __asm__ __volatile__ (
187 "eor %B0,%3" "\n\t" /* crc.hi ^ data */
188 "mov __tmp_reg__,%B0" "\n\t"
189 "swap __tmp_reg__" "\n\t" /* swap(crc.hi ^ data) */
190
191 /* Calculate the ret.lo of the CRC. */
192 "mov %1,__tmp_reg__" "\n\t"
193 "andi %1,0x0f" "\n\t"
194 "eor %1,%B0" "\n\t"
195 "mov %2,%B0" "\n\t"
196 "eor %2,__tmp_reg__" "\n\t"
197 "lsl %2" "\n\t"
198 "andi %2,0xe0" "\n\t"
199 "eor %1,%2" "\n\t" /* __tmp1 is now ret.lo. */
200
201 /* Calculate the ret.hi of the CRC. */
202 "mov %2,__tmp_reg__" "\n\t"
203 "eor %2,%B0" "\n\t"
204 "andi %2,0xf0" "\n\t"
205 "lsr %2" "\n\t"
206 "mov __tmp_reg__,%B0" "\n\t"
207 "lsl __tmp_reg__" "\n\t"
208 "rol %2" "\n\t"
209 "lsr %B0" "\n\t"
210 "lsr %B0" "\n\t"
211 "lsr %B0" "\n\t"
212 "andi %B0,0x1f" "\n\t"
213 "eor %B0,%2" "\n\t"
214 "eor %B0,%A0" "\n\t" /* ret.hi is now ready. */
215 "mov %A0,%1" "\n\t" /* ret.lo is now ready. */
216 : "=d" (__ret), "=d" (__tmp1), "=d" (__tmp2)
217 : "r" (__data), "0" (__crc)
218 : "r0"
219 );
220 return __ret;
221 }
222
223 /** \ingroup util_crc
224 Optimized CRC-CCITT calculation.
225
226 Polynomial: x^16 + x^12 + x^5 + 1 (0x8408)<br>
227 Initial value: 0xffff
228
229 This is the CRC used by PPP and IrDA.
230
231 See RFC1171 (PPP protocol) and IrDA IrLAP 1.1
232
233 \note Although the CCITT polynomial is the same as that used by the Xmodem
234 protocol, they are quite different. The difference is in how the bits are
235 shifted through the alorgithm. Xmodem shifts the MSB of the CRC and the
236 input first, while CCITT shifts the LSB of the CRC and the input first.
237
238 The following is the equivalent functionality written in C.
239
240 \code
241 uint16_t
242 crc_ccitt_update (uint16_t crc, uint8_t data)
243 {
244 data ^= lo8 (crc);
245 data ^= data << 4;
246
247 return ((((uint16_t)data << 8) | hi8 (crc)) ^ (uint8_t)(data >> 4)
248 ^ ((uint16_t)data << 3));
249 }
250 \endcode */
251
252 static __inline__ uint16_t
_crc_ccitt_update(uint16_t __crc,uint8_t __data)253 _crc_ccitt_update (uint16_t __crc, uint8_t __data)
254 {
255 uint16_t __ret;
256
257 __asm__ __volatile__ (
258 "eor %A0,%1" "\n\t"
259
260 "mov __tmp_reg__,%A0" "\n\t"
261 "swap %A0" "\n\t"
262 "andi %A0,0xf0" "\n\t"
263 "eor %A0,__tmp_reg__" "\n\t"
264
265 "mov __tmp_reg__,%B0" "\n\t"
266
267 "mov %B0,%A0" "\n\t"
268
269 "swap %A0" "\n\t"
270 "andi %A0,0x0f" "\n\t"
271 "eor __tmp_reg__,%A0" "\n\t"
272
273 "lsr %A0" "\n\t"
274 "eor %B0,%A0" "\n\t"
275
276 "eor %A0,%B0" "\n\t"
277 "lsl %A0" "\n\t"
278 "lsl %A0" "\n\t"
279 "lsl %A0" "\n\t"
280 "eor %A0,__tmp_reg__"
281
282 : "=d" (__ret)
283 : "r" (__data), "0" (__crc)
284 : "r0"
285 );
286 return __ret;
287 }
288
289 /** \ingroup util_crc
290 Optimized Dallas (now Maxim) iButton 8-bit CRC calculation.
291
292 Polynomial: x^8 + x^5 + x^4 + 1 (0x8C)<br>
293 Initial value: 0x0
294
295 See http://www.maxim-ic.com/appnotes.cfm/appnote_number/27
296
297 The following is the equivalent functionality written in C.
298
299 \code
300 uint8_t
301 _crc_ibutton_update(uint8_t crc, uint8_t data)
302 {
303 uint8_t i;
304
305 crc = crc ^ data;
306 for (i = 0; i < 8; i++)
307 {
308 if (crc & 0x01)
309 crc = (crc >> 1) ^ 0x8C;
310 else
311 crc >>= 1;
312 }
313
314 return crc;
315 }
316 \endcode
317 */
318
319 static __inline__ uint8_t
_crc_ibutton_update(uint8_t __crc,uint8_t __data)320 _crc_ibutton_update(uint8_t __crc, uint8_t __data)
321 {
322 uint8_t __i, __pattern;
323 __asm__ __volatile__ (
324 " eor %0, %4" "\n\t"
325 " ldi %1, 8" "\n\t"
326 " ldi %2, 0x8C" "\n\t"
327 "1: lsr %0" "\n\t"
328 " brcc 2f" "\n\t"
329 " eor %0, %2" "\n\t"
330 "2: dec %1" "\n\t"
331 " brne 1b" "\n\t"
332 : "=r" (__crc), "=d" (__i), "=d" (__pattern)
333 : "0" (__crc), "r" (__data));
334 return __crc;
335 }
336
337 /** \ingroup util_crc
338 Optimized CRC-8-CCITT calculation.
339
340 Polynomial: x^8 + x^2 + x + 1 (0xE0)<br>
341
342 For use with simple CRC-8<br>
343 Initial value: 0x0
344
345 For use with CRC-8-ROHC<br>
346 Initial value: 0xff<br>
347 Reference: http://tools.ietf.org/html/rfc3095#section-5.9.1
348
349 For use with CRC-8-ATM/ITU<br>
350 Initial value: 0xff<br>
351 Final XOR value: 0x55<br>
352 Reference: http://www.itu.int/rec/T-REC-I.432.1-199902-I/en
353
354 The C equivalent has been originally written by Dave Hylands.
355 Assembly code is based on _crc_ibutton_update optimization.
356
357 The following is the equivalent functionality written in C.
358
359 \code
360 uint8_t
361 _crc8_ccitt_update (uint8_t inCrc, uint8_t inData)
362 {
363 uint8_t i;
364 uint8_t data;
365
366 data = inCrc ^ inData;
367
368 for ( i = 0; i < 8; i++ )
369 {
370 if (( data & 0x80 ) != 0 )
371 {
372 data <<= 1;
373 data ^= 0x07;
374 }
375 else
376 {
377 data <<= 1;
378 }
379 }
380 return data;
381 }
382 \endcode
383 */
384
385 static __inline__ uint8_t
_crc8_ccitt_update(uint8_t __crc,uint8_t __data)386 _crc8_ccitt_update(uint8_t __crc, uint8_t __data)
387 {
388 uint8_t __i, __pattern;
389 __asm__ __volatile__ (
390 " eor %0, %4" "\n\t"
391 " ldi %1, 8" "\n\t"
392 " ldi %2, 0x07" "\n\t"
393 "1: lsl %0" "\n\t"
394 " brcc 2f" "\n\t"
395 " eor %0, %2" "\n\t"
396 "2: dec %1" "\n\t"
397 " brne 1b" "\n\t"
398 : "=r" (__crc), "=d" (__i), "=d" (__pattern)
399 : "0" (__crc), "r" (__data));
400 return __crc;
401 }
402
403 #endif /* _UTIL_CRC16_H_ */
404