00001 /* ---------------------------------------------------------------------------- 00002 * SAM Software Package License 00003 * ---------------------------------------------------------------------------- 00004 * Copyright (c) 2012, Atmel Corporation 00005 * 00006 * All rights reserved. 00007 * 00008 * Redistribution and use in source and binary forms, with or without 00009 * modification, are permitted provided that the following conditions are met: 00010 * 00011 * - Redistributions of source code must retain the above copyright notice, 00012 * this list of conditions and the disclaimer below. 00013 * 00014 * Atmel's name may not be used to endorse or promote products derived from 00015 * this software without specific prior written permission. 00016 * 00017 * DISCLAIMER: THIS SOFTWARE IS PROVIDED BY ATMEL "AS IS" AND ANY EXPRESS OR 00018 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 00019 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT ARE 00020 * DISCLAIMED. IN NO EVENT SHALL ATMEL BE LIABLE FOR ANY DIRECT, INDIRECT, 00021 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 00022 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, 00023 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 00024 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 00025 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, 00026 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00027 * ---------------------------------------------------------------------------- 00028 */ 00029 00030 /*---------------------------------------------------------------------------- 00031 * Headers 00032 *----------------------------------------------------------------------------*/ 00033 00034 #include "board.h" 00035 00036 /*---------------------------------------------------------------------------- 00037 * Internal function 00038 *----------------------------------------------------------------------------*/ 00039 00040 /** 00041 * Counts and return the number of bits set to '1' in the given byte. 00042 * \param byte Byte to count. 00043 */ 00044 static uint8_t CountBitsInByte(uint8_t byte) 00045 { 00046 uint8_t count = 0; 00047 00048 while (byte > 0) { 00049 if (byte & 1) { 00050 count++; 00051 } 00052 byte >>= 1; 00053 } 00054 00055 return count; 00056 } 00057 00058 /** 00059 * Counts and return the number of bits set to '1' in the given hamming code. 00060 * \param code Hamming code. 00061 */ 00062 static uint8_t CountBitsInCode256(uint8_t *code) 00063 { 00064 return CountBitsInByte(code[0]) + CountBitsInByte(code[1]) 00065 + CountBitsInByte(code[2]); 00066 } 00067 00068 /** 00069 * Calculates the 22-bit hamming code for a 256-bytes block of data. 00070 * \param data Data buffer to calculate code for. 00071 * \param code Pointer to a buffer where the code should be stored. 00072 */ 00073 static void Compute256(const uint8_t *data, uint8_t *code) 00074 { 00075 uint32_t i; 00076 uint8_t columnSum = 0; 00077 uint8_t evenLineCode = 0; 00078 uint8_t oddLineCode = 0; 00079 uint8_t evenColumnCode = 0; 00080 uint8_t oddColumnCode = 0; 00081 00082 // Xor all bytes together to get the column sum; 00083 // At the same time, calculate the even and odd line codes 00084 for (i=0; i < 256; i++){ 00085 columnSum ^= data[i]; 00086 00087 // If the xor sum of the byte is 0, then this byte has no incidence on 00088 // the computed code; so check if the sum is 1. 00089 if ((CountBitsInByte(data[i]) & 1) == 1) 00090 { 00091 // Parity groups are formed by forcing a particular index bit to 0 00092 // (even) or 1 (odd). 00093 // Example on one byte: 00094 // 00095 // bits (dec) 7 6 5 4 3 2 1 0 00096 // (bin) 111 110 101 100 011 010 001 000 00097 // '---'---'---'----------. 00098 // | 00099 // groups P4' ooooooooooooooo eeeeeeeeeeeeeee P4 | 00100 // P2' ooooooo eeeeeee ooooooo eeeeeee P2 | 00101 // P1' ooo eee ooo eee ooo eee ooo eee P1 | 00102 // | 00103 // We can see that: | 00104 // - P4 -> bit 2 of index is 0 --------------------' 00105 // - P4' -> bit 2 of index is 1. 00106 // - P2 -> bit 1 of index if 0. 00107 // - etc... 00108 // We deduce that a bit position has an impact on all even Px if 00109 // the log2(x)nth bit of its index is 0 00110 // ex: log2(4) = 2, bit2 of the index must be 0 (-> 0 1 2 3) 00111 // and on all odd Px' if the log2(x)nth bit of its index is 1 00112 // ex: log2(2) = 1, bit1 of the index must be 1 (-> 0 1 4 5) 00113 // 00114 // As such, we calculate all the possible Px and Px' values at the 00115 // same time in two variables, evenLineCode and oddLineCode, such as 00116 // evenLineCode bits: P128 P64 P32 P16 P8 P4 P2 P1 00117 // oddLineCode bits: P128' P64' P32' P16' P8' P4' P2' P1' 00118 // 00119 evenLineCode ^= (255 - i); 00120 oddLineCode ^= i; 00121 } 00122 } 00123 00124 // At this point, we have the line parities, and the column sum. First, We 00125 // must calculate the parity group values on the column sum. 00126 for (i=0; i < 8; i++) { 00127 if (columnSum & 1) { 00128 evenColumnCode ^= (7 - i); 00129 oddColumnCode ^= i; 00130 } 00131 columnSum >>= 1; 00132 } 00133 00134 // Now, we must interleave the parity values, to obtain the following layout: 00135 // Code[0] = Line1 00136 // Code[1] = Line2 00137 // Code[2] = Column 00138 // Line = Px' Px P(x-1)- P(x-1) ... 00139 // Column = P4' P4 P2' P2 P1' P1 PadBit PadBit 00140 code[0] = 0; 00141 code[1] = 0; 00142 code[2] = 0; 00143 00144 for (i=0; i < 4; i++) { 00145 code[0] <<= 2; 00146 code[1] <<= 2; 00147 code[2] <<= 2; 00148 00149 // Line 1 00150 if ((oddLineCode & 0x80) != 0) { 00151 code[0] |= 2; 00152 } 00153 00154 if ((evenLineCode & 0x80) != 0) { 00155 code[0] |= 1; 00156 } 00157 00158 // Line 2 00159 if ((oddLineCode & 0x08) != 0) { 00160 code[1] |= 2; 00161 } 00162 00163 if ((evenLineCode & 0x08) != 0) { 00164 code[1] |= 1; 00165 } 00166 00167 // Column 00168 if ((oddColumnCode & 0x04) != 0) { 00169 code[2] |= 2; 00170 } 00171 00172 if ((evenColumnCode & 0x04) != 0) { 00173 code[2] |= 1; 00174 } 00175 00176 oddLineCode <<= 1; 00177 evenLineCode <<= 1; 00178 oddColumnCode <<= 1; 00179 evenColumnCode <<= 1; 00180 } 00181 00182 // Invert codes (Linux compatibility) 00183 code[0] = (~(uint32_t)code[0]); 00184 code[1] = (~(uint32_t)code[1]); 00185 code[2] = (~(uint32_t)code[2]); 00186 00187 TRACE_DEBUG("Computed code = %02X %02X %02X\n\r", 00188 code[0], code[1], code[2]); 00189 } 00190 00191 /** 00192 * Verifies and corrects a 256-bytes block of data using the given 22-bits 00193 * hamming code. 00194 * 00195 * \param data Data buffer to check. 00196 * \param originalCode Hamming code to use for verifying the data. 00197 * 00198 * \return 0 if there is no error, otherwise returns a HAMMING_ERROR code. 00199 */ 00200 static uint8_t Verify256( uint8_t* pucData, const uint8_t* pucOriginalCode ) 00201 { 00202 /* Calculate new code */ 00203 uint8_t computedCode[3]; 00204 uint8_t correctionCode[3]; 00205 00206 Compute256( pucData, computedCode ); 00207 00208 /* Xor both codes together */ 00209 correctionCode[0] = computedCode[0] ^ pucOriginalCode[0]; 00210 correctionCode[1] = computedCode[1] ^ pucOriginalCode[1]; 00211 correctionCode[2] = computedCode[2] ^ pucOriginalCode[2]; 00212 00213 TRACE_DEBUG( "Correction code = %02X %02X %02X\n\r", 00214 correctionCode[0], correctionCode[1], correctionCode[2] ); 00215 00216 // If all bytes are 0, there is no error 00217 if ( (correctionCode[0] == 0) && (correctionCode[1] == 0) 00218 && (correctionCode[2] == 0) ) { 00219 return 0; 00220 } 00221 00222 /* If there is a single bit error, there are 11 bits set to 1 */ 00223 if ( CountBitsInCode256( correctionCode ) == 11 ) { 00224 // Get byte and bit indexes 00225 uint8_t byte; 00226 uint8_t bit; 00227 00228 byte = correctionCode[0] & 0x80; 00229 byte |= (correctionCode[0] << 1) & 0x40; 00230 byte |= (correctionCode[0] << 2) & 0x20; 00231 byte |= (correctionCode[0] << 3) & 0x10; 00232 00233 byte |= (correctionCode[1] >> 4) & 0x08; 00234 byte |= (correctionCode[1] >> 3) & 0x04; 00235 byte |= (correctionCode[1] >> 2) & 0x02; 00236 byte |= (correctionCode[1] >> 1) & 0x01; 00237 00238 bit = (correctionCode[2] >> 5) & 0x04; 00239 bit |= (correctionCode[2] >> 4) & 0x02; 00240 bit |= (correctionCode[2] >> 3) & 0x01; 00241 00242 /* Correct bit */ 00243 TRACE_DEBUG("Correcting byte #%d at bit %d\n\r", byte, bit ); 00244 pucData[byte] ^= (1 << bit); 00245 00246 return Hamming_ERROR_SINGLEBIT; 00247 } 00248 00249 /* Check if ECC has been corrupted */ 00250 if ( CountBitsInCode256( correctionCode ) == 1 ) { 00251 return Hamming_ERROR_ECC; 00252 } else { 00253 /* Otherwise, this is a multi-bit error */ 00254 return Hamming_ERROR_MULTIPLEBITS; 00255 } 00256 } 00257 00258 /*---------------------------------------------------------------------------- 00259 * Exported functions 00260 *----------------------------------------------------------------------------*/ 00261 00262 /** 00263 * Computes 3-bytes hamming codes for a data block whose size is multiple of 00264 * 256 bytes. Each 256 bytes block gets its own code. 00265 * \param data Data to compute code for. 00266 * \param size Data size in bytes. 00267 * \param code Codes buffer. 00268 */ 00269 void Hamming_Compute256x( const uint8_t *pucData, uint32_t dwSize, 00270 uint8_t* puCode ) 00271 { 00272 TRACE_DEBUG("Hamming_Compute256x()\n\r"); 00273 00274 while ( dwSize > 0 ) { 00275 Compute256( pucData, puCode ); 00276 pucData += 256; 00277 puCode += 3; 00278 dwSize -= 256; 00279 } 00280 } 00281 00282 /** 00283 * Verifies 3-bytes hamming codes for a data block whose size is multiple of 00284 * 256 bytes. Each 256-bytes block is verified with its own code. 00285 * 00286 * \return 0 if the data is correct, Hamming_ERROR_SINGLEBIT if one or more 00287 * block(s) have had a single bit corrected, or either Hamming_ERROR_ECC 00288 * or Hamming_ERROR_MULTIPLEBITS. 00289 * 00290 * \param data Data buffer to verify. 00291 * \param size Size of the data in bytes. 00292 * \param code Original codes. 00293 */ 00294 uint8_t Hamming_Verify256x( uint8_t* pucData, uint32_t dwSize, 00295 const uint8_t* pucCode ) 00296 { 00297 uint8_t error; 00298 uint8_t result = 0; 00299 00300 TRACE_DEBUG( "Hamming_Verify256x()\n\r" ); 00301 00302 while ( dwSize > 0 ) { 00303 error = Verify256( pucData, pucCode ); 00304 00305 if ( error == Hamming_ERROR_SINGLEBIT ) { 00306 result = Hamming_ERROR_SINGLEBIT; 00307 } else { 00308 if ( error ) { 00309 return error; 00310 } 00311 } 00312 pucData += 256; 00313 pucCode += 3; 00314 dwSize -= 256; 00315 } 00316 00317 return result; 00318 } 00319