AVR-LibC  2.2.0
Standard C library for AVR-GCC
 

AVR-LibC Documentation

Logo

AVR-LibC Development Pages

Main Page

User Manual

Library Reference

FAQ

Example Projects

File List

Loading...
Searching...
No Matches
crc16.h
Go to the documentation of this file.
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$ */
35
36#ifndef _UTIL_CRC16_H_
37#define _UTIL_CRC16_H_
38
39#include <stdint.h>
40
41#ifndef __DOXYGEN__
42#ifndef __ATTR_ALWAYS_INLINE__
43#define __ATTR_ALWAYS_INLINE__ __inline__ __attribute__((__always_inline__))
44#endif
45#endif /* ! DOXYGEN */
46
47/** \file */
48/** \defgroup util_crc <util/crc16.h>: CRC Computations
49 \code#include <util/crc16.h>\endcode
50
51 This header file provides a optimized inline functions for calculating
52 cyclic redundancy checks (CRC) using common polynomials.
53
54 \par References:
55
56 \par
57
58 See the Dallas Semiconductor app note 27 for 8051 assembler example and
59 general CRC optimization suggestions. The table on the last page of the
60 app note is the key to understanding these implementations.
61
62 \par
63
64 Jack Crenshaw's "Implementing CRCs" article in the January 1992 isue of \e
65 Embedded \e Systems \e Programming. This may be difficult to find, but it
66 explains CRC's in very clear and concise terms. Well worth the effort to
67 obtain a copy.
68
69 A typical application would look like:
70
71 \code
72 // Dallas iButton test vector.
73 uint8_t serno[] = { 0x02, 0x1c, 0xb8, 0x01, 0, 0, 0, 0xa2 };
74
75 int
76 checkcrc (void)
77 {
78 uint8_t crc = 0, i;
79
80 for (i = 0; i < sizeof serno / sizeof serno[0]; i++)
81 crc = _crc_ibutton_update (crc, serno[i]);
82
83 return crc; // must be 0
84 }
85 \endcode
86*/
87
88/** \ingroup util_crc
89 Optimized CRC-16 calculation.
90
91 Polynomial: x<sup>16</sup> + x<sup>15</sup> + x<sup>2</sup> + 1 (0xa001)<br>
92 Initial value: \c 0xffff
93
94 This CRC is normally used in disk-drive controllers.
95
96 The following is the equivalent functionality written in C.
97
98 \code
99 uint16_t
100 crc16_update (uint16_t crc, uint8_t a)
101 {
102 crc ^= a;
103 for (int i = 0; i < 8; ++i)
104 {
105 if (crc & 1)
106 crc = (crc >> 1) ^ 0xA001;
107 else
108 crc = crc >> 1;
109 }
110
111 return crc;
112 }
113 \endcode */
114
115static __ATTR_ALWAYS_INLINE__ uint16_t
117{
118 uint8_t __tmp;
119 uint16_t __ret;
120
121 __asm__ __volatile__ (
122 "eor %A0,%2" "\n\t"
123 "mov %1,%A0" "\n\t"
124 "swap %1" "\n\t"
125 "eor %1,%A0" "\n\t"
126 "mov __tmp_reg__,%1" "\n\t"
127 "lsr %1" "\n\t"
128 "lsr %1" "\n\t"
129 "eor %1,__tmp_reg__" "\n\t"
130 "mov __tmp_reg__,%1" "\n\t"
131 "lsr %1" "\n\t"
132 "eor %1,__tmp_reg__" "\n\t"
133 "andi %1,0x07" "\n\t"
134 "mov __tmp_reg__,%A0" "\n\t"
135 "mov %A0,%B0" "\n\t"
136 "lsr %1" "\n\t"
137 "ror __tmp_reg__" "\n\t"
138 "ror %1" "\n\t"
139 "mov %B0,__tmp_reg__" "\n\t"
140 "eor %A0,%1" "\n\t"
141 "lsr __tmp_reg__" "\n\t"
142 "ror %1" "\n\t"
143 "eor %B0,__tmp_reg__" "\n\t"
144 "eor %A0,%1"
145 : "=r" (__ret), "=d" (__tmp)
146 : "r" (__data), "0" (__crc)
147 : "r0"
148 );
149 return __ret;
150}
151
152/** \ingroup util_crc
153 Optimized CRC-XMODEM calculation.
154
155 Polynomial: x<sup>16</sup> + x<sup>12</sup> + x<sup>5</sup> + 1 (0x1021)<br>
156 Initial value: \c 0x0
157
158 This is the CRC used by the Xmodem-CRC protocol.
159
160 The following is the equivalent functionality written in C.
161
162 \code
163 uint16_t
164 crc_xmodem_update (uint16_t crc, uint8_t data)
165 {
166 crc = crc ^ ((uint16_t)data << 8);
167 for (int i = 0; i < 8; i++)
168 {
169 if (crc & 0x8000)
170 crc = (crc << 1) ^ 0x1021;
171 else
172 crc <<= 1;
173 }
174
175 return crc;
176 }
177 \endcode */
178
179static __ATTR_ALWAYS_INLINE__ uint16_t
181{
182 uint16_t __ret; /* %B0:%A0 (alias for __crc) */
183 uint8_t __tmp1; /* %1 */
184 uint8_t __tmp2; /* %2 */
185 /* %3 __data */
186
187 __asm__ __volatile__ (
188 "eor %B0,%3" "\n\t"
189 "mov %1,%A0" "\n\t"
190 "mov %2,%B0" "\n\t"
191
192 "mov %A0,%B0" "\n\t"
193 "swap %B0" "\n\t"
194 "eor %A0,%B0" "\n\t"
195
196 "andi %A0,0xf0" "\n\t"
197 "andi %B0,0x0f" "\n\t"
198
199 "eor %1,%A0" "\n\t"
200 "eor %2,%B0" "\n\t"
201
202 "lsl %A0" "\n\t"
203 "rol %B0" "\n\t"
204
205 "eor %B0,%1" "\n\t"
206 "eor %A0,%2"
207 : "=d" (__ret), "=r" (__tmp1), "=r" (__tmp2)
208 : "r" (__data), "0" (__crc)
209 );
210 return __ret;
211}
212
213/** \ingroup util_crc
214 Optimized CRC-CCITT calculation.
215
216 Polynomial: x<sup>16</sup> + x<sup>12</sup> + x<sup>5</sup> + 1 (0x8408)<br>
217 Initial value: \c 0xffff
218
219 This is the CRC used by PPP and IrDA.
220
221 See RFC1171 (PPP protocol) and IrDA IrLAP 1.1
222
223 \note Although the CCITT polynomial is the same as that used by the Xmodem
224 protocol, they are quite different. The difference is in how the bits are
225 shifted through the alorgithm. Xmodem shifts the MSB of the CRC and the
226 input first, while CCITT shifts the LSB of the CRC and the input first.
227
228 The following is the equivalent functionality written in C.
229
230 \code
231 uint16_t
232 crc_ccitt_update (uint16_t crc, uint8_t data)
233 {
234 data ^= lo8 (crc);
235 data ^= data << 4;
236
237 return ((((uint16_t)data << 8) | hi8 (crc)) ^ (uint8_t)(data >> 4)
238 ^ ((uint16_t)data << 3));
239 }
240 \endcode */
241
242static __ATTR_ALWAYS_INLINE__ uint16_t
244{
245 uint16_t __ret;
246
247 __asm__ __volatile__ (
248 "eor %A0,%1" "\n\t"
249
250 "mov __tmp_reg__,%A0" "\n\t"
251 "swap %A0" "\n\t"
252 "andi %A0,0xf0" "\n\t"
253 "eor %A0,__tmp_reg__" "\n\t"
254
255 "mov __tmp_reg__,%B0" "\n\t"
256
257 "mov %B0,%A0" "\n\t"
258
259 "swap %A0" "\n\t"
260 "andi %A0,0x0f" "\n\t"
261 "eor __tmp_reg__,%A0" "\n\t"
262
263 "lsr %A0" "\n\t"
264 "eor %B0,%A0" "\n\t"
265
266 "eor %A0,%B0" "\n\t"
267 "lsl %A0" "\n\t"
268 "lsl %A0" "\n\t"
269 "lsl %A0" "\n\t"
270 "eor %A0,__tmp_reg__"
271
272 : "=d" (__ret)
273 : "r" (__data), "0" (__crc)
274 : "r0"
275 );
276 return __ret;
277}
278
279/** \ingroup util_crc
280 Optimized Dallas (now Maxim) iButton 8-bit CRC calculation.
281
282 Polynomial: x<sup>8</sup> + x<sup>5</sup> + x<sup>4</sup> + 1 (0x8C)<br>
283 Initial value: \c 0x0
284
285 See http://www.maxim-ic.com/appnotes.cfm/appnote_number/27
286
287 The following is the equivalent functionality written in C.
288
289 \code
290 uint8_t
291 _crc_ibutton_update (uint8_t crc, uint8_t data)
292 {
293 crc = crc ^ data;
294 for (uint8_t i = 0; i < 8; i++)
295 {
296 if (crc & 0x01)
297 crc = (crc >> 1) ^ 0x8C;
298 else
299 crc >>= 1;
300 }
301
302 return crc;
303 }
304 \endcode
305*/
306
307static __ATTR_ALWAYS_INLINE__ uint8_t
309{
310 uint8_t __i, __pattern;
311 __asm__ __volatile__ (
312 "eor %0, %4" "\n\t"
313 "ldi %1, 8" "\n\t"
314 "ldi %2, 0x8C" "\n"
315 "1: lsr %0" "\n\t"
316 "brcc 2f" "\n\t"
317 "eor %0, %2" "\n"
318 "2: dec %1" "\n\t"
319 "brne 1b"
320 : "=r" (__crc), "=d" (__i), "=d" (__pattern)
321 : "0" (__crc), "r" (__data));
322 return __crc;
323}
324
325/** \ingroup util_crc
326 Optimized CRC-8-CCITT calculation.
327
328 Polynomial: x<sup>8</sup> + x<sup>2</sup> + x + 1 (0xE0)<br>
329
330 For use with simple CRC-8<br>
331 Initial value: 0x0
332
333 For use with CRC-8-ROHC<br>
334 Initial value: 0xff<br>
335 Reference: http://tools.ietf.org/html/rfc3095#section-5.9.1
336
337 For use with CRC-8-ATM/ITU<br>
338 Initial value: 0xff<br>
339 Final XOR value: 0x55<br>
340 Reference: http://www.itu.int/rec/T-REC-I.432.1-199902-I/en
341
342 The C equivalent has been originally written by Dave Hylands.
343 Assembly code is based on _crc_ibutton_update optimization.
344
345 The following is the equivalent functionality written in C.
346
347 \code
348 uint8_t
349 _crc8_ccitt_update (uint8_t inCrc, uint8_t inData)
350 {
351 uint8_t data = inCrc ^ inData;
352
353 for (int i = 0; i < 8; i++)
354 {
355 if ((data & 0x80) != 0)
356 {
357 data <<= 1;
358 data ^= 0x07;
359 }
360 else
361 {
362 data <<= 1;
363 }
364 }
365 return data;
366 }
367 \endcode
368*/
369
370static __ATTR_ALWAYS_INLINE__ uint8_t
372{
373 uint8_t __i, __pattern;
374 __asm__ __volatile__ (
375 "eor %0, %4" "\n\t"
376 "ldi %1, 8" "\n\t"
377 "ldi %2, 0x07" "\n"
378 "1: lsl %0" "\n\t"
379 "brcc 2f" "\n\t"
380 "eor %0, %2" "\n"
381 "2: dec %1" "\n\t"
382 "brne 1b"
383 : "=r" (__crc), "=d" (__i), "=d" (__pattern)
384 : "0" (__crc), "r" (__data));
385 return __crc;
386}
387
388#endif /* _UTIL_CRC16_H_ */
unsigned int uint16_t
Definition: stdint.h:93
unsigned char uint8_t
Definition: stdint.h:83
static uint16_t _crc_xmodem_update(uint16_t __crc, uint8_t __data)
Definition: crc16.h:180
static uint16_t _crc_ccitt_update(uint16_t __crc, uint8_t __data)
Definition: crc16.h:243
static uint8_t _crc8_ccitt_update(uint8_t __crc, uint8_t __data)
Definition: crc16.h:371
static uint8_t _crc_ibutton_update(uint8_t __crc, uint8_t __data)
Definition: crc16.h:308
static uint16_t _crc16_update(uint16_t __crc, uint8_t __data)
Definition: crc16.h:116