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_ */
_crc_ccitt_update
static __inline__ uint16_t _crc_ccitt_update(uint16_t __crc, uint8_t __data)
Definition: crc16.h:251
_crc16_update
static __inline__ uint16_t _crc16_update(uint16_t __crc, uint8_t __data)
Definition: crc16.h:111
_crc_xmodem_update
static __inline__ uint16_t _crc_xmodem_update(uint16_t __crc, uint8_t __data)
Definition: crc16.h:177
_crc_ibutton_update
static __inline__ uint8_t _crc_ibutton_update(uint8_t __crc, uint8_t __data)
Definition: crc16.h:318
uint8_t
unsigned char uint8_t
Definition: stdint.h:79
uint16_t
unsigned int uint16_t
Definition: stdint.h:89

Automatically generated by Doxygen 1.8.7 on Tue Jul 8 2014. Dash Docset conversion by Matt Kane