AVR Libc Home Page
AVR Libc Development Pages
Main Page
User Manual
Library Reference
FAQ
Alphabetical Index
Example Projects
src
avr-libc
include
util
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_ */
Automatically generated by Doxygen 1.8.1.1 on Fri Aug 17 2012.