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_ */
|