AVR Libc Home Page |  | AVR Libc Development Pages
Main Page | User Manual | Library Reference | FAQ | Alphabetical Index | Example Projects

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

Automatically generated by Doxygen 1.8.3.1 on Sun Sep 29 2013.