SAMV71 Xplained Ultra Software Package 1.3

hamming.c

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 
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines