SAM3S8/SD8 Software Package: libraries/libboard_sam3s-ek2/source/hamming.c Source File

SAM3S8/SD8 Software Package 1.2

# hamming.c

    00001 /* ----------------------------------------------------------------------------
    00002  *         ATMEL Microcontroller Software Support
    00003  * ----------------------------------------------------------------------------
    00004  * Copyright (c) 2008, 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     {
    00050         if (byte & 1)
    00051         {
    00052             count++;
    00053         }
    00054         byte >>= 1;
    00055     }
    00056
    00057     return count;
    00058 }
    00059
    00060 /**
    00061  *  Counts and return the number of bits set to '1' in the given hamming code.
    00062  *  \param code  Hamming code.
    00063  */
    00064 static uint8_t CountBitsInCode256(uint8_t *code)
    00065 {
    00066     return CountBitsInByte(code[0]) + CountBitsInByte(code[1]) + CountBitsInByte(code[2]);
    00067 }
    00068
    00069 /**
    00070  *  Calculates the 22-bit hamming code for a 256-bytes block of data.
    00071  *  \param data  Data buffer to calculate code for.
    00072  *  \param code  Pointer to a buffer where the code should be stored.
    00073  */
    00074 static void Compute256(const uint8_t *data, uint8_t *code)
    00075 {
    00076     uint32_t i;
    00077     uint8_t columnSum = 0;
    00078     uint8_t evenLineCode = 0;
    00079     uint8_t oddLineCode = 0;
    00080     uint8_t evenColumnCode = 0;
    00081     uint8_t oddColumnCode = 0;
    00082
    00083     // Xor all bytes together to get the column sum;
    00084     // At the same time, calculate the even and odd line codes
    00085     for (i=0; i < 256; i++)
    00086     {
    00087         columnSum ^= data[i];
    00088
    00089         // If the xor sum of the byte is 0, then this byte has no incidence on
    00090         // the computed code; so check if the sum is 1.
    00091         if ((CountBitsInByte(data[i]) & 1) == 1)
    00092         {
    00093             // Parity groups are formed by forcing a particular index bit to 0
    00094             // (even) or 1 (odd).
    00095             // Example on one byte:
    00096             //
    00097             // bits (dec)  7   6   5   4   3   2   1   0
    00098             //      (bin) 111 110 101 100 011 010 001 000
    00099             //                            '---'---'---'----------.
    00100             //                                                   |
    00101             // groups P4' ooooooooooooooo eeeeeeeeeeeeeee P4     |
    00102             //        P2' ooooooo eeeeeee ooooooo eeeeeee P2     |
    00103             //        P1' ooo eee ooo eee ooo eee ooo eee P1     |
    00104             //                                                   |
    00105             // We can see that:                                  |
    00106             //  - P4  -> bit 2 of index is 0 --------------------'
    00107             //  - P4' -> bit 2 of index is 1.
    00108             //  - P2  -> bit 1 of index if 0.
    00109             //  - etc...
    00110             // We deduce that a bit position has an impact on all even Px if
    00111             // the log2(x)nth bit of its index is 0
    00112             //     ex: log2(4) = 2, bit2 of the index must be 0 (-> 0 1 2 3)
    00113             // and on all odd Px' if the log2(x)nth bit of its index is 1
    00114             //     ex: log2(2) = 1, bit1 of the index must be 1 (-> 0 1 4 5)
    00115             //
    00116             // As such, we calculate all the possible Px and Px' values at the
    00117             // same time in two variables, evenLineCode and oddLineCode, such as
    00118             //     evenLineCode bits: P128  P64  P32  P16  P8  P4  P2  P1
    00119             //     oddLineCode  bits: P128' P64' P32' P16' P8' P4' P2' P1'
    00120             //
    00121             evenLineCode ^= (255 - i);
    00122             oddLineCode ^= i;
    00123         }
    00124     }
    00125
    00126     // At this point, we have the line parities, and the column sum. First, We
    00127     // must caculate the parity group values on the column sum.
    00128     for (i=0; i < 8; i++)
    00129     {
    00130         if (columnSum & 1)
    00131         {
    00132             evenColumnCode ^= (7 - i);
    00133             oddColumnCode ^= i;
    00134         }
    00135         columnSum >>= 1;
    00136     }
    00137
    00138     // Now, we must interleave the parity values, to obtain the following layout:
    00139     // Code[0] = Line1
    00140     // Code[1] = Line2
    00141     // Code[2] = Column
    00142     // Line = Px' Px P(x-1)- P(x-1) ...
    00143     // Column = P4' P4 P2' P2 P1' P1 PadBit PadBit
    00144     code[0] = 0;
    00145     code[1] = 0;
    00146     code[2] = 0;
    00147
    00148     for (i=0; i < 4; i++)
    00149     {
    00150         code[0] <<= 2;
    00151         code[1] <<= 2;
    00152         code[2] <<= 2;
    00153
    00154         // Line 1
    00155         if ((oddLineCode & 0x80) != 0)
    00156         {
    00157             code[0] |= 2;
    00158         }
    00159
    00160         if ((evenLineCode & 0x80) != 0)
    00161         {
    00162             code[0] |= 1;
    00163         }
    00164
    00165         // Line 2
    00166         if ((oddLineCode & 0x08) != 0)
    00167         {
    00168             code[1] |= 2;
    00169         }
    00170
    00171         if ((evenLineCode & 0x08) != 0)
    00172         {
    00173             code[1] |= 1;
    00174         }
    00175
    00176         // Column
    00177         if ((oddColumnCode & 0x04) != 0)
    00178         {
    00179             code[2] |= 2;
    00180         }
    00181
    00182         if ((evenColumnCode & 0x04) != 0)
    00183         {
    00184             code[2] |= 1;
    00185         }
    00186
    00187         oddLineCode <<= 1;
    00188         evenLineCode <<= 1;
    00189         oddColumnCode <<= 1;
    00190         evenColumnCode <<= 1;
    00191     }
    00192
    00193     // Invert codes (linux compatibility)
    00194     code[0] = (~(uint32_t)code[0]);
    00195     code[1] = (~(uint32_t)code[1]);
    00196     code[2] = (~(uint32_t)code[2]);
    00197
    00198     TRACE_DEBUG("Computed code = %02X %02X %02X\n\r",
    00199               code[0], code[1], code[2]);
    00200 }
    00201
    00202 /**
    00203  *  Verifies and corrects a 256-bytes block of data using the given 22-bits
    00204  *  hamming code.
    00205  *
    00206  *  \param data  Data buffer to check.
    00207  *  \param originalCode  Hamming code to use for verifying the data.
    00208  *
    00209  *  \return 0 if there is no error, otherwise returns a HAMMING_ERROR code.
    00210  */
    00211 static uint8_t Verify256( uint8_t* pucData, const uint8_t* pucOriginalCode )
    00212 {
    00213     /* Calculate new code */
    00214     uint8_t computedCode[3] ;
    00215     uint8_t correctionCode[3] ;
    00216
    00217     Compute256( pucData, computedCode ) ;
    00218
    00219     /* Xor both codes together */
    00220     correctionCode[0] = computedCode[0] ^ pucOriginalCode[0] ;
    00221     correctionCode[1] = computedCode[1] ^ pucOriginalCode[1] ;
    00222     correctionCode[2] = computedCode[2] ^ pucOriginalCode[2] ;
    00223
    00224     TRACE_DEBUG( "Correction code = %02X %02X %02X\n\r", correctionCode[0], correctionCode[1], correctionCode[2] ) ;
    00225
    00226     // If all bytes are 0, there is no error
    00227     if ( (correctionCode[0] == 0) && (correctionCode[1] == 0) && (correctionCode[2] == 0) )
    00228     {
    00229         return 0 ;
    00230     }
    00231
    00232     /* If there is a single bit error, there are 11 bits set to 1 */
    00233     if ( CountBitsInCode256( correctionCode ) == 11 )
    00234     {
    00235         // Get byte and bit indexes
    00236         uint8_t byte ;
    00237         uint8_t bit ;
    00238
    00239         byte = correctionCode[0] & 0x80;
    00240         byte |= (correctionCode[0] << 1) & 0x40;
    00241         byte |= (correctionCode[0] << 2) & 0x20;
    00242         byte |= (correctionCode[0] << 3) & 0x10;
    00243
    00244         byte |= (correctionCode[1] >> 4) & 0x08;
    00245         byte |= (correctionCode[1] >> 3) & 0x04;
    00246         byte |= (correctionCode[1] >> 2) & 0x02;
    00247         byte |= (correctionCode[1] >> 1) & 0x01;
    00248
    00249         bit = (correctionCode[2] >> 5) & 0x04;
    00250         bit |= (correctionCode[2] >> 4) & 0x02;
    00251         bit |= (correctionCode[2] >> 3) & 0x01;
    00252
    00253         /* Correct bit */
    00254         TRACE_DEBUG("Correcting byte #%d at bit %d\n\r", byte, bit ) ;
    00255         pucData[byte] ^= (1 << bit) ;
    00256
    00257         return Hamming_ERROR_SINGLEBIT ;
    00258     }
    00259
    00260     /* Check if ECC has been corrupted */
    00261     if ( CountBitsInCode256( correctionCode ) == 1 )
    00262     {
    00263         return Hamming_ERROR_ECC ;
    00264     }
    00265     /* Otherwise, this is a multi-bit error */
    00266     else
    00267     {
    00268         return Hamming_ERROR_MULTIPLEBITS ;
    00269     }
    00270 }
    00271
    00272 /*----------------------------------------------------------------------------
    00273  *         Exported functions
    00274  *----------------------------------------------------------------------------*/
    00275
    00276 /**
    00277  *  Computes 3-bytes hamming codes for a data block whose size is multiple of
    00278  *  256 bytes. Each 256 bytes block gets its own code.
    00279  *  \param data  Data to compute code for.
    00280  *  \param size  Data size in bytes.
    00281  *  \param code  Codes buffer.
    00282  */
    00283 void Hamming_Compute256x( const uint8_t *pucData, uint32_t dwSize, uint8_t* puCode )
    00284 {
    00285     TRACE_DEBUG("Hamming_Compute256x()\n\r");
    00286
    00287     while ( dwSize > 0 )
    00288     {
    00289         Compute256( pucData, puCode ) ;
    00290
    00291         pucData += 256;
    00292         puCode += 3;
    00293         dwSize -= 256;
    00294     }
    00295 }
    00296
    00297 /**
    00298  *  Verifies 3-bytes hamming codes for a data block whose size is multiple of
    00299  *  256 bytes. Each 256-bytes block is verified with its own code.
    00300  *
    00301  *  \return 0 if the data is correct, Hamming_ERROR_SINGLEBIT if one or more
    00302  *  block(s) have had a single bit corrected, or either Hamming_ERROR_ECC
    00303  *  or Hamming_ERROR_MULTIPLEBITS.
    00304  *
    00305  *  \param data  Data buffer to verify.
    00306  *  \param size  Size of the data in bytes.
    00307  *  \param code  Original codes.
    00308  */
    00309 uint8_t Hamming_Verify256x( uint8_t* pucData, uint32_t dwSize, const uint8_t* pucCode )
    00310 {
    00311     uint8_t error ;
    00312     uint8_t result = 0 ;
    00313
    00314     TRACE_DEBUG( "Hamming_Verify256x()\n\r" ) ;
    00315
    00316     while ( dwSize > 0 )
    00317     {
    00318         error = Verify256( pucData, pucCode ) ;
    00319
    00320         if ( error == Hamming_ERROR_SINGLEBIT )
    00321         {
    00322             result = Hamming_ERROR_SINGLEBIT ;
    00323         }
    00324         else
    00325         {
    00326             if ( error )
    00327             {
    00328                 return error ;
    00329             }
    00330         }
    00331
    00332         pucData += 256;
    00333         pucCode += 3;
    00334         dwSize -= 256;
    00335     }
    00336
    00337     return result ;
    00338 }
    00339

All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines