source: arduino-1-6-7/trunk/fuentes/arduino-ide-amd64/hardware/tools/avr/avr/include/util/crc16.h @ 4837

Last change on this file since 4837 was 4837, checked in by daduve, 2 years ago

Adding new version

File size: 10.6 KB
Line 
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$ */
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
112static __inline__ uint16_t
113_crc16_update(uint16_t __crc, uint8_t __data)
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
178static __inline__ uint16_t
179_crc_xmodem_update(uint16_t __crc, uint8_t __data)
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
252static __inline__ uint16_t
253_crc_ccitt_update (uint16_t __crc, uint8_t __data)
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
319static __inline__ uint8_t
320_crc_ibutton_update(uint8_t __crc, uint8_t __data)
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
385static __inline__ uint8_t
386_crc8_ccitt_update(uint8_t __crc, uint8_t __data)
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_ */
Note: See TracBrowser for help on using the repository browser.