1  | /* $Id: crc16.h,v 1.2.2.1 2006/04/19 20:35:54 joerg_wunsch Exp $ */
  | 
2  | 
  | 
3  | #ifndef _UTIL_CRC16_H_
  | 
4  | #define _UTIL_CRC16_H_
  | 
5  | 
  | 
6  | #include <stdint.h>
  | 
7  | 
  | 
8  | /** \defgroup util_crc <util/crc16.h>: CRC Computations
  | 
9  |     \code#include <util/crc16.h>\endcode
  | 
10  | 
  | 
11  |     This header file provides a optimized inline functions for calculating
  | 
12  |     cyclic redundancy checks (CRC) using common polynomials.
  | 
13  | 
  | 
14  |     \par References:
  | 
15  | 
  | 
16  |     \par
  | 
17  | 
  | 
18  |     See the Dallas Semiconductor app note 27 for 8051 assembler example and
  | 
19  |     general CRC optimization suggestions. The table on the last page of the
  | 
20  |     app note is the key to understanding these implementations.
  | 
21  | 
  | 
22  |     \par
  | 
23  | 
  | 
24  |     Jack Crenshaw's "Implementing CRCs" article in the January 1992 isue of \e
  | 
25  |     Embedded \e Systems \e Programming. This may be difficult to find, but it
  | 
26  |     explains CRC's in very clear and concise terms. Well worth the effort to
  | 
27  |     obtain a copy.
  | 
28  | 
  | 
29  |     A typical application would look like:
  | 
30  | 
  | 
31  |     \code
  | 
32  |     // Dallas iButton test vector.
  | 
33  |     uint8_t serno[] = { 0x02, 0x1c, 0xb8, 0x01, 0, 0, 0, 0xa2 };
 | 
34  | 
  | 
35  |     int
  | 
36  |     checkcrc(void)
  | 
37  |     {
 | 
38  |   uint8_t crc = 0, i;
  | 
39  | 
  | 
40  |   for (i = 0; i < sizeof serno / sizeof serno[0]; i++)
  | 
41  |       crc = _crc_ibutton_update(crc, serno[i]);
  | 
42  | 
  | 
43  |   return crc; // must be 0
  | 
44  |     }
  | 
45  |     \endcode
  | 
46  | */
  | 
47  | 
  | 
48  | /** \ingroup util_crc
  | 
49  |     Optimized CRC-16 calculation.
  | 
50  | 
  | 
51  |     Polynomial: x^16 + x^15 + x^2 + 1 (0xa001)<br>
  | 
52  |     Initial value: 0xffff
  | 
53  | 
  | 
54  |     This CRC is normally used in disk-drive controllers.
  | 
55  | 
  | 
56  |     The following is the equivalent functionality written in C.
  | 
57  | 
  | 
58  |     \code
  | 
59  |     uint16_t
  | 
60  |     crc16_update(uint16_t crc, uint8_t a)
  | 
61  |     {
 | 
62  |   int i;
  | 
63  | 
  | 
64  |   crc ^= a;
  | 
65  |   for (i = 0; i < 8; ++i)
  | 
66  |   {
 | 
67  |       if (crc & 1)
  | 
68  |     crc = (crc >> 1) ^ 0xA001;
  | 
69  |       else
  | 
70  |     crc = (crc >> 1);
  | 
71  |   }
  | 
72  | 
  | 
73  |   return crc;
  | 
74  |     }
  | 
75  | 
  | 
76  |     \endcode */
  | 
77  | 
  | 
78  | static __inline__ uint16_t
  | 
79  | _crc16_update(uint16_t crc, uint8_t a)
  | 
80  | {
 | 
81  | 
  | 
82  |   int i;
  | 
83  | 
  | 
84  |   crc ^= a;
  | 
85  |   for( i = 0; i < 8; ++i )
  | 
86  |   {
 | 
87  |       if( crc & 1 )
  | 
88  |     crc = (crc>>1) ^ 0xA001;
  | 
89  |       else
  | 
90  |     crc = (crc>>1);
  | 
91  |   }
  | 
92  | 
  | 
93  |   return crc;
  | 
94  | }
  | 
95  | 
  | 
96  | /** \ingroup util_crc
  | 
97  |     Optimized CRC-XMODEM calculation.
  | 
98  | 
  | 
99  |     Polynomial: x^16 + x^12 + x^5 + 1 (0x1021)<br>
  | 
100  |     Initial value: 0x0
  | 
101  | 
  | 
102  |     This is the CRC used by the Xmodem-CRC protocol.
  | 
103  | 
  | 
104  |     The following is the equivalent functionality written in C.
  | 
105  | 
  | 
106  |     \code
  | 
107  |     uint16_t
  | 
108  |     crc_xmodem_update (uint16_t crc, uint8_t data)
  | 
109  |     {
 | 
110  |         int i;
  | 
111  | 
  | 
112  |         crc = crc ^ ((uint16_t)data << 8);
  | 
113  |         for (i=0; i<8; i++)
  | 
114  |         {
 | 
115  |             if (crc & 0x8000)
  | 
116  |                 crc = (crc << 1) ^ 0x1021;
  | 
117  |             else
  | 
118  |                 crc <<= 1;
  | 
119  |         }
  | 
120  | 
  | 
121  |         return crc;
  | 
122  |     }
  | 
123  |     \endcode */
  | 
124  | 
  | 
125  | static __inline__ uint16_t
  | 
126  | _crc_xmodem_update(uint16_t __crc, uint8_t __data)
  | 
127  | {
 | 
128  |     uint16_t __ret;             /* %B0:%A0 (alias for __crc) */
  | 
129  |     uint8_t __tmp1;             /* %1 */
  | 
130  |     uint8_t __tmp2;             /* %2 */
  | 
131  |                                 /* %3  __data */
  | 
132  | 
  | 
133  |     __asm__ __volatile__ (
  | 
134  |         "eor    %B0,%3"          "\n\t" /* crc.hi ^ data */
  | 
135  |         "mov    __tmp_reg__,%B0" "\n\t"
  | 
136  |         "swap   __tmp_reg__"     "\n\t" /* swap(crc.hi ^ data) */
  | 
137  | 
  | 
138  |         /* Calculate the ret.lo of the CRC. */
  | 
139  |         "mov    %1,__tmp_reg__"  "\n\t"
  | 
140  |         "andi   %1,0x0f"         "\n\t"
  | 
141  |         "eor    %1,%B0"          "\n\t"
  | 
142  |         "mov    %2,%B0"          "\n\t"
  | 
143  |         "eor    %2,__tmp_reg__"  "\n\t"
  | 
144  |         "lsl    %2"              "\n\t"
  | 
145  |         "andi   %2,0xe0"         "\n\t"
  | 
146  |         "eor    %1,%2"           "\n\t" /* __tmp1 is now ret.lo. */
  | 
147  | 
  | 
148  |         /* Calculate the ret.hi of the CRC. */
  | 
149  |         "mov    %2,__tmp_reg__"  "\n\t"
  | 
150  |         "eor    %2,%B0"          "\n\t"
  | 
151  |         "andi   %2,0xf0"         "\n\t"
  | 
152  |         "lsr    %2"              "\n\t"
  | 
153  |         "mov    __tmp_reg__,%B0" "\n\t"
  | 
154  |         "lsl    __tmp_reg__"     "\n\t"
  | 
155  |         "rol    %2"              "\n\t"
  | 
156  |         "lsr    %B0"             "\n\t"
  | 
157  |         "lsr    %B0"             "\n\t"
  | 
158  |         "lsr    %B0"             "\n\t"
  | 
159  |         "andi   %B0,0x1f"        "\n\t"
  | 
160  |         "eor    %B0,%2"          "\n\t"
  | 
161  |         "eor    %B0,%A0"         "\n\t" /* ret.hi is now ready. */
  | 
162  |         "mov    %A0,%1"          "\n\t" /* ret.lo is now ready. */
  | 
163  |         : "=d" (__ret), "=d" (__tmp1), "=d" (__tmp2)
  | 
164  |         : "r" (__data), "0" (__crc)
  | 
165  |         : "r0"
  | 
166  |     );
  | 
167  |     return __ret;
  | 
168  | }
  | 
169  | 
  | 
170  | /** \ingroup util_crc
  | 
171  |     Optimized CRC-CCITT calculation.
  | 
172  | 
  | 
173  |     Polynomial: x^16 + x^12 + x^5 + 1 (0x8408)<br>
  | 
174  |     Initial value: 0xffff
  | 
175  | 
  | 
176  |     This is the CRC used by PPP and IrDA.
  | 
177  | 
  | 
178  |     See RFC1171 (PPP protocol) and IrDA IrLAP 1.1
  | 
179  | 
  | 
180  |     \note Although the CCITT polynomial is the same as that used by the Xmodem
  | 
181  |     protocol, they are quite different. The difference is in how the bits are
  | 
182  |     shifted through the alorgithm. Xmodem shifts the MSB of the CRC and the
  | 
183  |     input first, while CCITT shifts the LSB of the CRC and the input first.
  | 
184  | 
  | 
185  |     The following is the equivalent functionality written in C.
  | 
186  | 
  | 
187  |     \code
  | 
188  |     uint16_t
  | 
189  |     crc_ccitt_update (uint16_t crc, uint8_t data)
  | 
190  |     {
 | 
191  |         data ^= lo8 (crc);
  | 
192  |         data ^= data << 4;
  | 
193  | 
  | 
194  |         return ((((uint16_t)data << 8) | hi8 (crc)) ^ (uint8_t)(data >> 4) 
  | 
195  |                 ^ ((uint16_t)data << 3));
  | 
196  |     }
  | 
197  |     \endcode */
  | 
198  | 
  | 
199  | static __inline__ uint16_t
  | 
200  | _crc_ccitt_update (uint16_t __crc, uint8_t __data)
  | 
201  | {
 | 
202  |     uint16_t __ret;
  | 
203  | 
  | 
204  |     __asm__ __volatile__ (
  | 
205  |         "eor    %A0,%1"          "\n\t"
  | 
206  | 
  | 
207  |         "mov    __tmp_reg__,%A0" "\n\t"
  | 
208  |         "swap   %A0"             "\n\t"
  | 
209  |         "andi   %A0,0xf0"        "\n\t"
  | 
210  |         "eor    %A0,__tmp_reg__" "\n\t"
  | 
211  | 
  | 
212  |         "mov    __tmp_reg__,%B0" "\n\t"
  | 
213  | 
  | 
214  |         "mov    %B0,%A0"         "\n\t"
  | 
215  | 
  | 
216  |         "swap   %A0"             "\n\t"
  | 
217  |         "andi   %A0,0x0f"        "\n\t"
  | 
218  |         "eor    __tmp_reg__,%A0" "\n\t"
  | 
219  | 
  | 
220  |         "lsr    %A0"             "\n\t"
  | 
221  |         "eor    %B0,%A0"         "\n\t"
  | 
222  | 
  | 
223  |         "eor    %A0,%B0"         "\n\t"
  | 
224  |         "lsl    %A0"             "\n\t"
  | 
225  |         "lsl    %A0"             "\n\t"
  | 
226  |         "lsl    %A0"             "\n\t"
  | 
227  |         "eor    %A0,__tmp_reg__"
  | 
228  | 
  | 
229  |         : "=d" (__ret)
  | 
230  |         : "r" (__data), "0" (__crc)
  | 
231  |         : "r0"
  | 
232  |     );
  | 
233  |     return __ret;
  | 
234  | }
  | 
235  | 
  | 
236  | /** \ingroup util_crc
  | 
237  |     Optimized Dallas (now Maxim) iButton 8-bit CRC calculation.
  | 
238  | 
  | 
239  |     Polynomial: x^8 + x^5 + x^4 + 1 (0x8C)<br>
  | 
240  |     Initial value: 0x0
  | 
241  | 
  | 
242  |     See http://www.maxim-ic.com/appnotes.cfm/appnote_number/27
  | 
243  | 
  | 
244  |     The following is the equivalent functionality written in C.
  | 
245  | 
  | 
246  |     \code
  | 
247  |     uint8_t
  | 
248  |     _crc_ibutton_update(uint8_t crc, uint8_t data)
  | 
249  |     {
 | 
250  |   uint8_t i;
  | 
251  | 
  | 
252  |   crc = crc ^ data;
  | 
253  |   for (i = 0; i < 8; i++)
  | 
254  |   {
 | 
255  |       if (crc & 0x01)
  | 
256  |           crc = (crc >> 1) ^ 0x8C;
  | 
257  |       else
  | 
258  |           crc >>= 1;
  | 
259  |   }
  | 
260  | 
  | 
261  |   return crc;
  | 
262  |     }
  | 
263  |     \endcode
  | 
264  | */
  | 
265  | 
  | 
266  | static __inline__ uint8_t
  | 
267  | _crc_ibutton_update(uint8_t __crc, uint8_t __data)
  | 
268  | {
 | 
269  |   uint8_t __i, __pattern;
  | 
270  |   __asm__ __volatile__ (
  | 
271  |     "  eor  %0, %4" "\n\t"
  | 
272  |     "  ldi  %1, 8" "\n\t"
  | 
273  |     "  ldi  %2, 0x8C" "\n\t"
  | 
274  |     "1:  bst  %0, 0" "\n\t"
  | 
275  |     "  lsr  %0" "\n\t"
  | 
276  |     "  brtc  2f" "\n\t"
  | 
277  |     "  eor  %0, %2" "\n\t"
  | 
278  |     "2:  dec  %1" "\n\t"
  | 
279  |     "  brne  1b" "\n\t"
  | 
280  |     : "=r" (__crc), "=d" (__i), "=d" (__pattern)
  | 
281  |     : "0" (__crc), "r" (__data));
  | 
282  |   return __crc;
  | 
283  | }
  | 
284  | 
  | 
285  | #endif /* _UTIL_CRC16_H_ */
  |