AVR Libc Home Page AVRs 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  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
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
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
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
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
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_ */
static __inline__ uint8_t _crc8_ccitt_update(uint8_t __crc, uint8_t __data)
Definition: crc16.h:386
static __inline__ uint16_t _crc_ccitt_update(uint16_t __crc, uint8_t __data)
Definition: crc16.h:253
static __inline__ uint16_t _crc16_update(uint16_t __crc, uint8_t __data)
Definition: crc16.h:113
static __inline__ uint16_t _crc_xmodem_update(uint16_t __crc, uint8_t __data)
Definition: crc16.h:179
static __inline__ uint8_t _crc_ibutton_update(uint8_t __crc, uint8_t __data)
Definition: crc16.h:320
unsigned char uint8_t
Definition: stdint.h:80
unsigned int uint16_t
Definition: stdint.h:90

Automatically generated by Doxygen 1.8.7 on Tue Aug 12 2014.