AVR Libc Home Page AVRs AVR Libc Development Pages
Main Page User Manual Library Reference FAQ Alphabetical Index Example Projects

crc16.h

Go to the documentation of this file.
00001 /* Copyright (c) 2002, 2003, 2004  Marek Michalkiewicz
00002    Copyright (c) 2005, 2007 Joerg Wunsch
00003    All rights reserved.
00004 
00005    Redistribution and use in source and binary forms, with or without
00006    modification, are permitted provided that the following conditions are met:
00007 
00008    * Redistributions of source code must retain the above copyright
00009      notice, this list of conditions and the following disclaimer.
00010 
00011    * Redistributions in binary form must reproduce the above copyright
00012      notice, this list of conditions and the following disclaimer in
00013      the documentation and/or other materials provided with the
00014      distribution.
00015 
00016    * Neither the name of the copyright holders nor the names of
00017      contributors may be used to endorse or promote products derived
00018      from this software without specific prior written permission.
00019 
00020   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
00021   AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00022   IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00023   ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
00024   LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
00025   CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
00026   SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
00027   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
00028   CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
00029   ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
00030   POSSIBILITY OF SUCH DAMAGE. */
00031 
00032 /* $Id: crc16.h 2136 2010-06-08 12:03:38Z joerg_wunsch $ */
00033 
00034 #ifndef _UTIL_CRC16_H_
00035 #define _UTIL_CRC16_H_
00036 
00037 #include <stdint.h>
00038 
00039 /** \file */
00040 /** \defgroup util_crc <util/crc16.h>: CRC Computations
00041     \code#include <util/crc16.h>\endcode
00042 
00043     This header file provides a optimized inline functions for calculating
00044     cyclic redundancy checks (CRC) using common polynomials.
00045 
00046     \par References:
00047 
00048     \par
00049 
00050     See the Dallas Semiconductor app note 27 for 8051 assembler example and
00051     general CRC optimization suggestions. The table on the last page of the
00052     app note is the key to understanding these implementations.
00053 
00054     \par
00055 
00056     Jack Crenshaw's "Implementing CRCs" article in the January 1992 isue of \e
00057     Embedded \e Systems \e Programming. This may be difficult to find, but it
00058     explains CRC's in very clear and concise terms. Well worth the effort to
00059     obtain a copy.
00060 
00061     A typical application would look like:
00062 
00063     \code
00064     // Dallas iButton test vector.
00065     uint8_t serno[] = { 0x02, 0x1c, 0xb8, 0x01, 0, 0, 0, 0xa2 };
00066 
00067     int
00068     checkcrc(void)
00069     {
00070         uint8_t crc = 0, i;
00071 
00072         for (i = 0; i < sizeof serno / sizeof serno[0]; i++)
00073             crc = _crc_ibutton_update(crc, serno[i]);
00074 
00075         return crc; // must be 0
00076     }
00077     \endcode
00078 */
00079 
00080 /** \ingroup util_crc
00081     Optimized CRC-16 calculation.
00082 
00083     Polynomial: x^16 + x^15 + x^2 + 1 (0xa001)<br>
00084     Initial value: 0xffff
00085 
00086     This CRC is normally used in disk-drive controllers.
00087 
00088     The following is the equivalent functionality written in C.
00089 
00090     \code
00091     uint16_t
00092     crc16_update(uint16_t crc, uint8_t a)
00093     {
00094         int i;
00095 
00096         crc ^= a;
00097         for (i = 0; i < 8; ++i)
00098         {
00099             if (crc & 1)
00100                 crc = (crc >> 1) ^ 0xA001;
00101             else
00102                 crc = (crc >> 1);
00103         }
00104 
00105         return crc;
00106     }
00107 
00108     \endcode */
00109 
00110 static __inline__ uint16_t
00111 _crc16_update(uint16_t __crc, uint8_t __data)
00112 {
00113         uint8_t __tmp;
00114         uint16_t __ret;
00115 
00116         __asm__ __volatile__ (
00117                 "eor %A0,%2" "\n\t"
00118                 "mov %1,%A0" "\n\t"
00119                 "swap %1" "\n\t"
00120                 "eor %1,%A0" "\n\t"
00121                 "mov __tmp_reg__,%1" "\n\t"
00122                 "lsr %1" "\n\t"
00123                 "lsr %1" "\n\t"
00124                 "eor %1,__tmp_reg__" "\n\t"
00125                 "mov __tmp_reg__,%1" "\n\t"
00126                 "lsr %1" "\n\t"
00127                 "eor %1,__tmp_reg__" "\n\t"
00128                 "andi %1,0x07" "\n\t"
00129                 "mov __tmp_reg__,%A0" "\n\t"
00130                 "mov %A0,%B0" "\n\t"
00131                 "lsr %1" "\n\t"
00132                 "ror __tmp_reg__" "\n\t"
00133                 "ror %1" "\n\t"
00134                 "mov %B0,__tmp_reg__" "\n\t"
00135                 "eor %A0,%1" "\n\t"
00136                 "lsr __tmp_reg__" "\n\t"
00137                 "ror %1" "\n\t"
00138                 "eor %B0,__tmp_reg__" "\n\t"
00139                 "eor %A0,%1"
00140                 : "=r" (__ret), "=d" (__tmp)
00141                 : "r" (__data), "0" (__crc)
00142                 : "r0"
00143         );
00144         return __ret;
00145 }
00146 
00147 /** \ingroup util_crc
00148     Optimized CRC-XMODEM calculation.
00149 
00150     Polynomial: x^16 + x^12 + x^5 + 1 (0x1021)<br>
00151     Initial value: 0x0
00152 
00153     This is the CRC used by the Xmodem-CRC protocol.
00154 
00155     The following is the equivalent functionality written in C.
00156 
00157     \code
00158     uint16_t
00159     crc_xmodem_update (uint16_t crc, uint8_t data)
00160     {
00161         int i;
00162 
00163         crc = crc ^ ((uint16_t)data << 8);
00164         for (i=0; i<8; i++)
00165         {
00166             if (crc & 0x8000)
00167                 crc = (crc << 1) ^ 0x1021;
00168             else
00169                 crc <<= 1;
00170         }
00171 
00172         return crc;
00173     }
00174     \endcode */
00175 
00176 static __inline__ uint16_t
00177 _crc_xmodem_update(uint16_t __crc, uint8_t __data)
00178 {
00179     uint16_t __ret;             /* %B0:%A0 (alias for __crc) */
00180     uint8_t __tmp1;             /* %1 */
00181     uint8_t __tmp2;             /* %2 */
00182                                 /* %3  __data */
00183 
00184     __asm__ __volatile__ (
00185         "eor    %B0,%3"          "\n\t" /* crc.hi ^ data */
00186         "mov    __tmp_reg__,%B0" "\n\t"
00187         "swap   __tmp_reg__"     "\n\t" /* swap(crc.hi ^ data) */
00188 
00189         /* Calculate the ret.lo of the CRC. */
00190         "mov    %1,__tmp_reg__"  "\n\t"
00191         "andi   %1,0x0f"         "\n\t"
00192         "eor    %1,%B0"          "\n\t"
00193         "mov    %2,%B0"          "\n\t"
00194         "eor    %2,__tmp_reg__"  "\n\t"
00195         "lsl    %2"              "\n\t"
00196         "andi   %2,0xe0"         "\n\t"
00197         "eor    %1,%2"           "\n\t" /* __tmp1 is now ret.lo. */
00198 
00199         /* Calculate the ret.hi of the CRC. */
00200         "mov    %2,__tmp_reg__"  "\n\t"
00201         "eor    %2,%B0"          "\n\t"
00202         "andi   %2,0xf0"         "\n\t"
00203         "lsr    %2"              "\n\t"
00204         "mov    __tmp_reg__,%B0" "\n\t"
00205         "lsl    __tmp_reg__"     "\n\t"
00206         "rol    %2"              "\n\t"
00207         "lsr    %B0"             "\n\t"
00208         "lsr    %B0"             "\n\t"
00209         "lsr    %B0"             "\n\t"
00210         "andi   %B0,0x1f"        "\n\t"
00211         "eor    %B0,%2"          "\n\t"
00212         "eor    %B0,%A0"         "\n\t" /* ret.hi is now ready. */
00213         "mov    %A0,%1"          "\n\t" /* ret.lo is now ready. */
00214         : "=d" (__ret), "=d" (__tmp1), "=d" (__tmp2)
00215         : "r" (__data), "0" (__crc)
00216         : "r0"
00217     );
00218     return __ret;
00219 }
00220 
00221 /** \ingroup util_crc
00222     Optimized CRC-CCITT calculation.
00223 
00224     Polynomial: x^16 + x^12 + x^5 + 1 (0x8408)<br>
00225     Initial value: 0xffff
00226 
00227     This is the CRC used by PPP and IrDA.
00228 
00229     See RFC1171 (PPP protocol) and IrDA IrLAP 1.1
00230 
00231     \note Although the CCITT polynomial is the same as that used by the Xmodem
00232     protocol, they are quite different. The difference is in how the bits are
00233     shifted through the alorgithm. Xmodem shifts the MSB of the CRC and the
00234     input first, while CCITT shifts the LSB of the CRC and the input first.
00235 
00236     The following is the equivalent functionality written in C.
00237 
00238     \code
00239     uint16_t
00240     crc_ccitt_update (uint16_t crc, uint8_t data)
00241     {
00242         data ^= lo8 (crc);
00243         data ^= data << 4;
00244 
00245         return ((((uint16_t)data << 8) | hi8 (crc)) ^ (uint8_t)(data >> 4) 
00246                 ^ ((uint16_t)data << 3));
00247     }
00248     \endcode */
00249 
00250 static __inline__ uint16_t
00251 _crc_ccitt_update (uint16_t __crc, uint8_t __data)
00252 {
00253     uint16_t __ret;
00254 
00255     __asm__ __volatile__ (
00256         "eor    %A0,%1"          "\n\t"
00257 
00258         "mov    __tmp_reg__,%A0" "\n\t"
00259         "swap   %A0"             "\n\t"
00260         "andi   %A0,0xf0"        "\n\t"
00261         "eor    %A0,__tmp_reg__" "\n\t"
00262 
00263         "mov    __tmp_reg__,%B0" "\n\t"
00264 
00265         "mov    %B0,%A0"         "\n\t"
00266 
00267         "swap   %A0"             "\n\t"
00268         "andi   %A0,0x0f"        "\n\t"
00269         "eor    __tmp_reg__,%A0" "\n\t"
00270 
00271         "lsr    %A0"             "\n\t"
00272         "eor    %B0,%A0"         "\n\t"
00273 
00274         "eor    %A0,%B0"         "\n\t"
00275         "lsl    %A0"             "\n\t"
00276         "lsl    %A0"             "\n\t"
00277         "lsl    %A0"             "\n\t"
00278         "eor    %A0,__tmp_reg__"
00279 
00280         : "=d" (__ret)
00281         : "r" (__data), "0" (__crc)
00282         : "r0"
00283     );
00284     return __ret;
00285 }
00286 
00287 /** \ingroup util_crc
00288     Optimized Dallas (now Maxim) iButton 8-bit CRC calculation.
00289 
00290     Polynomial: x^8 + x^5 + x^4 + 1 (0x8C)<br>
00291     Initial value: 0x0
00292 
00293     See http://www.maxim-ic.com/appnotes.cfm/appnote_number/27
00294 
00295     The following is the equivalent functionality written in C.
00296 
00297     \code
00298     uint8_t
00299     _crc_ibutton_update(uint8_t crc, uint8_t data)
00300     {
00301         uint8_t i;
00302 
00303         crc = crc ^ data;
00304         for (i = 0; i < 8; i++)
00305         {
00306             if (crc & 0x01)
00307                 crc = (crc >> 1) ^ 0x8C;
00308             else
00309                 crc >>= 1;
00310         }
00311 
00312         return crc;
00313     }
00314     \endcode
00315 */
00316 
00317 static __inline__ uint8_t
00318 _crc_ibutton_update(uint8_t __crc, uint8_t __data)
00319 {
00320         uint8_t __i, __pattern;
00321         __asm__ __volatile__ (
00322                 "       eor     %0, %4" "\n\t"
00323                 "       ldi     %1, 8" "\n\t"
00324                 "       ldi     %2, 0x8C" "\n\t"
00325                 "1:     lsr     %0" "\n\t"
00326                 "       brcc    2f" "\n\t"
00327                 "       eor     %0, %2" "\n\t"
00328                 "2:     dec     %1" "\n\t"
00329                 "       brne    1b" "\n\t"
00330                 : "=r" (__crc), "=d" (__i), "=d" (__pattern)
00331                 : "0" (__crc), "r" (__data));
00332         return __crc;
00333 }
00334 
00335 #endif /* _UTIL_CRC16_H_ */

Automatically generated by Doxygen 1.7.3 on Thu May 19 2011.