| AVR Libc Home Page |
|
AVR Libc Development Pages | ||
| Main Page | User Manual | Reference | FAQ | Example Projects |
crc16.8h
Go to the documentation of this file.
01 Copyright (c) 2002, 2003, 2004 Marek Michalkiewicz
02 Copyright (c) 2005, 2007 Joerg Wunsch
03 3Copyright (c) 2013 Dave Hylands
04 4Copyright (c) 2013 Frederic Nadeau
05 5All rights reserved.
06 6
07 7Redistribution and use in source and binary forms, with or without
08 8modification, are permitted provided that the following conditions are met:
09 910 10* Redistributions of source code must retain the above copyright
11 11notice, this list of conditions and the following disclaimer.
12 1213 13* Redistributions in binary form must reproduce the above copyright
14 14notice, this list of conditions and the following disclaimer in
15 15the documentation and/or other materials provided with the
16 16distribution.
17 1718 18* Neither the name of the copyright holders nor the names of
19 19contributors may be used to endorse or promote products derived
20 20from this software without specific prior written permission.
21 2122 22THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
23 23AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 24IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 25ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
26 26LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
27 27CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
28 28SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
29 29INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
30 30CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
31 31ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 32POSSIBILITY OF SUCH DAMAGE. */
33 3334 34/* $Id: crc16.h 2398 2013-05-08 11:45:54Z joerg_wunsch $ */
35 3536 36#ifndef _UTIL_CRC16_H_
37 37#define _UTIL_CRC16_H_
38 3839 39#include <stdint.h>
40 4041 41/** \file */
42 42/** \defgroup util_crc <util/crc16.h>: CRC Computations
43 43\code#include <util/crc16.h>\endcode
44 4445 45This header file provides a optimized inline functions for calculating
46 46cyclic redundancy checks (CRC) using common polynomials.
47 4748 48\par References:
49 4950 50\par
51 5152 52See the Dallas Semiconductor app note 27 for 8051 assembler example and
53 53general CRC optimization suggestions. The table on the last page of the
54 54app note is the key to understanding these implementations.
55 5556 56\par
57 5758 58Jack Crenshaw's "Implementing CRCs" article in the January 1992 isue of \e
59 59Embedded \e Systems \e Programming. This may be difficult to find, but it
60 60explains CRC's in very clear and concise terms. Well worth the effort to
61 61obtain a copy.
62 6263 63A typical application would look like:
64 6465 65\code
66 66// Dallas iButton test vector.
67 67uint8_t serno[] = { 0x02, 0x1c, 0xb8, 0x01, 0, 0, 0, 0xa2 };
68 6869 69int
70 70checkcrc(void)
71 71{
72 72uint8_t crc = 0, i;
73 7374 74for (i = 0; i < sizeof serno / sizeof serno[0]; i++)
75 75crc = _crc_ibutton_update(crc, serno[i]);
76 7677 77return crc; // must be 0
78 78}
79 79\endcode
80 80*/
81 8182 82/** \ingroup util_crc
83 83Optimized CRC-16 calculation.
84 8485 85Polynomial: x^16 + x^15 + x^2 + 1 (0xa001)<br>
86 86Initial value: 0xffff
87 8788 88This CRC is normally used in disk-drive controllers.
89 8990 90The following is the equivalent functionality written in C.
91 9192 92\code
93 93uint16_t
94 94crc16_update(uint16_t crc, uint8_t a)
95 95{
96 96int i;
97 9798 98crc ^= a;
99 99for (i = 0; i < 8; ++i)
100 100{
101 101if (crc & 1)
102 102crc = (crc >> 1) ^ 0xA001;
103 103else
104 104crc = (crc >> 1);
105 105}
106 106107 107return crc;
108 108}
109 109110 110\endcode */
111 111112 112static __inline__ uint16_t
113 113
_crc16_update(uint16_t __crc, uint8_t __data)
114 114{
115 115uint8_t __tmp;
116 116uint16_t __ret;
117 117118 118__asm__ __volatile__ (
119 119"eor %A0,%2" "\n\t"
120120"mov %1,%A0" "\n\t"
121121"swap %1" "\n\t"
122122"eor %1,%A0" "\n\t"
123123"mov __tmp_reg__,%1" "\n\t"
124124"lsr %1" "\n\t"
125125"lsr %1" "\n\t"
126126"eor %1,__tmp_reg__" "\n\t"
127127"mov __tmp_reg__,%1" "\n\t"
128128"lsr %1" "\n\t"
129129"eor %1,__tmp_reg__" "\n\t"
130130"andi %1,0x07" "\n\t"
131131"mov __tmp_reg__,%A0" "\n\t"
132132"mov %A0,%B0" "\n\t"
133133"lsr %1" "\n\t"
134134"ror __tmp_reg__" "\n\t"
135135"ror %1" "\n\t"
136136"mov %B0,__tmp_reg__" "\n\t"
137137"eor %A0,%1" "\n\t"
138138"lsr __tmp_reg__" "\n\t"
139139"ror %1" "\n\t"
140140"eor %B0,__tmp_reg__" "\n\t"
141141"eor %A0,%1"
142142: "=r" (__ret), "=d" (__tmp)
143143: "r" (__data), "0" (__crc)
144144: "r0"
145145);
146 146 return __ret;
147147}
148 148149 149/** \ingroup util_crc
150 150Optimized CRC-XMODEM calculation.
151 151152 152Polynomial: x^16 + x^12 + x^5 + 1 (0x1021)<br>
153 153Initial value: 0x0
154 154155 155This is the CRC used by the Xmodem-CRC protocol.
156 156157 157The following is the equivalent functionality written in C.
158 158159 159\code
160 160uint16_t
161 161crc_xmodem_update (uint16_t crc, uint8_t data)
162 162{
163 163int i;
164 164165 165crc = crc ^ ((uint16_t)data << 8);
166 166for (i=0; i<8; i++)
167 167{
168 168if (crc & 0x8000)
169 169crc = (crc << 1) ^ 0x1021;
170 170else
171 171crc <<= 1;
172 172}
173 173174 174return crc;
175 175}
176 176\endcode */
177 177178 178static __inline__ uint16_t
179 179
_crc_xmodem_update(uint16_t __crc, uint8_t __data)
180 180{
181 181uint16_t __ret; /* %B0:%A0 (alias for __crc) */
182 182uint8_t __tmp1; /* %1 */
183 183uint8_t __tmp2; /* %2 */
184 184/* %3 __data */
185 185186 186__asm__ __volatile__ (
187 187"eor %B0,%3" "\n\t" /* crc.hi ^ data */
188188"mov __tmp_reg__,%B0" "\n\t"
189189"swap __tmp_reg__" "\n\t" /* swap(crc.hi ^ data) */
190190191 191/* Calculate the ret.lo of the CRC. */
192 192"mov %1,__tmp_reg__" "\n\t"
193193"andi %1,0x0f" "\n\t"
194194"eor %1,%B0" "\n\t"
195195"mov %2,%B0" "\n\t"
196196"eor %2,__tmp_reg__" "\n\t"
197197"lsl %2" "\n\t"
198198"andi %2,0xe0" "\n\t"
199199"eor %1,%2" "\n\t" /* __tmp1 is now ret.lo. */
200200201 201/* Calculate the ret.hi of the CRC. */
202 202"mov %2,__tmp_reg__" "\n\t"
203203"eor %2,%B0" "\n\t"
204204"andi %2,0xf0" "\n\t"
205205"lsr %2" "\n\t"
206206"mov __tmp_reg__,%B0" "\n\t"
207207"lsl __tmp_reg__" "\n\t"
208208"rol %2" "\n\t"
209209"lsr %B0" "\n\t"
210210"lsr %B0" "\n\t"
211211"lsr %B0" "\n\t"
212212"andi %B0,0x1f" "\n\t"
213213"eor %B0,%2" "\n\t"
214214"eor %B0,%A0" "\n\t" /* ret.hi is now ready. */
215215"mov %A0,%1" "\n\t" /* ret.lo is now ready. */
216216: "=d" (__ret), "=d" (__tmp1), "=d" (__tmp2)
217217: "r" (__data), "0" (__crc)
218218: "r0"
219219);
220 220 return __ret;
221221}
222 222223 223/** \ingroup util_crc
224 224Optimized CRC-CCITT calculation.
225 225226 226Polynomial: x^16 + x^12 + x^5 + 1 (0x8408)<br>
227 227Initial value: 0xffff
228 228229 229This is the CRC used by PPP and IrDA.
230 230231 231See RFC1171 (PPP protocol) and IrDA IrLAP 1.1
232 232233 233\note Although the CCITT polynomial is the same as that used by the Xmodem
234 234protocol, they are quite different. The difference is in how the bits are
235 235shifted through the alorgithm. Xmodem shifts the MSB of the CRC and the
236 236input first, while CCITT shifts the LSB of the CRC and the input first.
237 237238 238The following is the equivalent functionality written in C.
239 239240 240\code
241 241uint16_t
242 242crc_ccitt_update (uint16_t crc, uint8_t data)
243 243{
244 244data ^= lo8 (crc);
245 245data ^= data << 4;
246 246247 247return ((((uint16_t)data << 8) | hi8 (crc)) ^ (uint8_t)(data >> 4)
248 248^ ((uint16_t)data << 3));
249 249}
250 250\endcode */
251 251252 252static __inline__ uint16_t
253 253
_crc_ccitt_update (uint16_t __crc, uint8_t __data)
254 254{
255 255uint16_t __ret;
256 256257 257__asm__ __volatile__ (
258 258"eor %A0,%1" "\n\t"
259259260 260"mov __tmp_reg__,%A0" "\n\t"
261261"swap %A0" "\n\t"
262262"andi %A0,0xf0" "\n\t"
263263"eor %A0,__tmp_reg__" "\n\t"
264264265 265"mov __tmp_reg__,%B0" "\n\t"
266266267 267"mov %B0,%A0" "\n\t"
268268269 269"swap %A0" "\n\t"
270270"andi %A0,0x0f" "\n\t"
271271"eor __tmp_reg__,%A0" "\n\t"
272272273 273"lsr %A0" "\n\t"
274274"eor %B0,%A0" "\n\t"
275275276 276"eor %A0,%B0" "\n\t"
277277"lsl %A0" "\n\t"
278278"lsl %A0" "\n\t"
279279"lsl %A0" "\n\t"
280280"eor %A0,__tmp_reg__"
281281282 282: "=d" (__ret)
283283: "r" (__data), "0" (__crc)
284284: "r0"
285285);
286 286return __ret;
287287}
288 288289 289/** \ingroup util_crc
290 290Optimized Dallas (now Maxim) iButton 8-bit CRC calculation.
291 291292 292Polynomial: x^8 + x^5 + x^4 + 1 (0x8C)<br>
293 293Initial value: 0x0
294 294295 295See http://www.maxim-ic.com/appnotes.cfm/appnote_number/27
296 296297 297The following is the equivalent functionality written in C.
298 298299 299\code
300 300uint8_t
301 301_crc_ibutton_update(uint8_t crc, uint8_t data)
302 302{
303 303uint8_t i;
304 304305 305crc = crc ^ data;
306 306for (i = 0; i < 8; i++)
307 307{
308 308if (crc & 0x01)
309 309crc = (crc >> 1) ^ 0x8C;
310 310else
311 311crc >> = 1;
312 312}
313 313314 314return crc;
315 315}
316 316\endcode
317 317*/
318 318319 319static __inline__ uint8_t
320 320
_crc_ibutton_update(uint8_t __crc, uint8_t __data)
321 321{
322 322uint8_t __i, __pattern;
323 323__asm__ __volatile__ (
324 324" eor %0, %4" "\n\t"
325325" ldi %1, 8" "\n\t"
326326" ldi %2, 0x8C" "\n\t"
327327"1: lsr %0" "\n\t"
328328" brcc 2f" "\n\t"
329329" eor %0, %2" "\n\t"
330330"2: dec %1" "\n\t"
331331" brne 1b" "\n\t"
332332: "=r" (__crc), "=d" (__i), "=d" (__pattern)
333333: "0" (__crc), "r" (__data));
334334return __crc;
335335}
336 336337 337/** \ingroup util_crc
338 338Optimized CRC-8-CCITT calculation.
339 339340 340Polynomial: x^8 + x^2 + x + 1 (0xE0)<br>
341 341342 342For use with simple CRC-8<br>
343 343Initial value: 0x0
344 344345 345For use with CRC-8-ROHC<br>
346 346Initial value: 0xff<br>
347 347Reference: http://tools.ietf.org/html/rfc3095#section-5.9.1
348 348349 349For use with CRC-8-ATM/ITU<br>
350 350Initial value: 0xff<br>
351 351Final XOR value: 0x55<br>
352 352Reference: http://www.itu.int/rec/T-REC-I.432.1-199902-I/en
353 353354 354The C equivalent has been originally written by Dave Hylands.
355 355Assembly code is based on _crc_ibutton_update optimization.
356 356357 357The following is the equivalent functionality written in C.
358 358359 359\code
360 360uint8_t
361 361_crc8_ccitt_update (uint8_t inCrc, uint8_t inData)
362 362{
363 363uint8_t i;
364 364uint8_t data;
365 365366 366data = inCrc ^ inData;
367 367368 368for ( i = 0; i < 8; i++ )
369 369{
370 370if (( data & 0x80 ) != 0 )
371 371{
372 372data <<= 1;
373 373data ^= 0x07;
374 374}
375 375else
376 376{
377 377data <<= 1;
378 378}
379 379}
380 380return data;
381 381}
382 382\endcode
383 383*/
384 384385 385static __inline__ uint8_t
386 386
_crc8_ccitt_update(uint8_t __crc, uint8_t __data)
387 387{
388 388uint8_t __i, __pattern;
389 389__asm__ __volatile__ (
390 390" eor %0, %4" "\n\t"
391391" ldi %1, 8" "\n\t"
392392" ldi %2, 0x07" "\n\t"
393393"1: lsl %0" "\n\t"
394394" brcc 2f" "\n\t"
395395" eor %0, %2" "\n\t"
396396"2: dec %1" "\n\t"
397397" brne 1b" "\n\t"
398398: "=r" (__crc), "=d" (__i), "=d" (__pattern)
399399: "0" (__crc), "r" (__data));
400400return __crc;
401401}
402 402403 403#endif /* _UTIL_CRC16_H_ */
_crc8_ccitt_update static __inline__ uint8_t _crc8_ccitt_update(uint8_t __crc, uint8_t __data)
Definition: crc16.h:386
_crc_ccitt_update static __inline__ uint16_t _crc_ccitt_update(uint16_t __crc, uint8_t __data)
Definition: crc16.h:253
_crc16_update static __inline__ uint16_t _crc16_update(uint16_t __crc, uint8_t __data)
Definition: crc16.h:113
_crc_xmodem_update static __inline__ uint16_t _crc_xmodem_update(uint16_t __crc, uint8_t __data)
Definition: crc16.h:179
_crc_ibutton_update static __inline__ uint8_t _crc_ibutton_update(uint8_t __crc, uint8_t __data)
Definition: crc16.h:320
uint8_t unsigned char uint8_t
Definition: stdint.h:83
uint16_t unsigned int uint16_t
Definition: stdint.h:93