AVR Libc Home Page | AVR Libc Development Pages | ||||
Main Page | User Manual | Library Reference | FAQ | Alphabetical Index | Example Projects |
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_ */