git.sur5r.net Git - freertos/blob - FreeRTOS/Demo/CORTEX_M7_SAMV71_Xplained_IAR_Keil/libboard_samv7-ek/source/hamming.c

   1 /* ----------------------------------------------------------------------------\r
   2  *         SAM Software Package License\r
   3  * ----------------------------------------------------------------------------\r
   4  * Copyright (c) 2012, Atmel Corporation\r
   5  *\r
   6  * All rights reserved.\r
   7  *\r
   8  * Redistribution and use in source and binary forms, with or without\r
   9  * modification, are permitted provided that the following conditions are met:\r
  10  *\r
  11  * - Redistributions of source code must retain the above copyright notice,\r
  12  * this list of conditions and the disclaimer below.\r
  13  *\r
  14  * Atmel's name may not be used to endorse or promote products derived from\r
  15  * this software without specific prior written permission.\r
  16  *\r
  17  * DISCLAIMER: THIS SOFTWARE IS PROVIDED BY ATMEL "AS IS" AND ANY EXPRESS OR\r
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF\r
  19  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT ARE\r
  20  * DISCLAIMED. IN NO EVENT SHALL ATMEL BE LIABLE FOR ANY DIRECT, INDIRECT,\r
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT\r
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,\r
  23  * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF\r
  24  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING\r
  25  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,\r
  26  * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\r
  27  * ----------------------------------------------------------------------------\r
  28  */\r
  29 \r
  30 /*----------------------------------------------------------------------------\r
  31  *        Headers\r
  32  *----------------------------------------------------------------------------*/\r
  33 \r
  34 #include "board.h"\r
  35 \r
  36 /*----------------------------------------------------------------------------\r
  37  *         Internal function\r
  38  *----------------------------------------------------------------------------*/\r
  39 \r
  40 /**\r
  41  *  Counts and return the number of bits set to '1' in the given byte.\r
  42  *  \param byte  Byte to count.\r
  43  */\r
  44 static uint8_t CountBitsInByte(uint8_t byte)\r
  45 {\r
  46     uint8_t count = 0;\r
  47 \r
  48     while (byte > 0)\r
  49     {\r
  50         if (byte & 1)\r
  51         {\r
  52             count++;\r
  53         }\r
  54         byte >>= 1;\r
  55     }\r
  56 \r
  57     return count;\r
  58 }\r
  59 \r
  60 /**\r
  61  *  Counts and return the number of bits set to '1' in the given hamming code.\r
  62  *  \param code  Hamming code.\r
  63  */\r
  64 static uint8_t CountBitsInCode256(uint8_t *code)\r
  65 {\r
  66     return CountBitsInByte(code[0]) + CountBitsInByte(code[1]) + CountBitsInByte(code[2]);\r
  67 }\r
  68 \r
  69 /**\r
  70  *  Calculates the 22-bit hamming code for a 256-bytes block of data.\r
  71  *  \param data  Data buffer to calculate code for.\r
  72  *  \param code  Pointer to a buffer where the code should be stored.\r
  73  */\r
  74 static void Compute256(const uint8_t *data, uint8_t *code)\r
  75 {\r
  76     uint32_t i;\r
  77     uint8_t columnSum = 0;\r
  78     uint8_t evenLineCode = 0;\r
  79     uint8_t oddLineCode = 0;\r
  80     uint8_t evenColumnCode = 0;\r
  81     uint8_t oddColumnCode = 0;\r
  82 \r
  83     // Xor all bytes together to get the column sum;\r
  84     // At the same time, calculate the even and odd line codes\r
  85     for (i=0; i < 256; i++)\r
  86     {\r
  87         columnSum ^= data[i];\r
  88 \r
  89         // If the xor sum of the byte is 0, then this byte has no incidence on\r
  90         // the computed code; so check if the sum is 1.\r
  91         if ((CountBitsInByte(data[i]) & 1) == 1)\r
  92         {\r
  93             // Parity groups are formed by forcing a particular index bit to 0\r
  94             // (even) or 1 (odd).\r
  95             // Example on one byte:\r
  96             //\r
  97             // bits (dec)  7   6   5   4   3   2   1   0\r
  98             //      (bin) 111 110 101 100 011 010 001 000\r
  99             //                            '---'---'---'----------.\r
 100             //                                                   |\r
 101             // groups P4' ooooooooooooooo eeeeeeeeeeeeeee P4     |\r
 102             //        P2' ooooooo eeeeeee ooooooo eeeeeee P2     |\r
 103             //        P1' ooo eee ooo eee ooo eee ooo eee P1     |\r
 104             //                                                   |\r
 105             // We can see that:                                  |\r
 106             //  - P4  -> bit 2 of index is 0 --------------------'\r
 107             //  - P4' -> bit 2 of index is 1.\r
 108             //  - P2  -> bit 1 of index if 0.\r
 109             //  - etc...\r
 110             // We deduce that a bit position has an impact on all even Px if\r
 111             // the log2(x)nth bit of its index is 0\r
 112             //     ex: log2(4) = 2, bit2 of the index must be 0 (-> 0 1 2 3)\r
 113             // and on all odd Px' if the log2(x)nth bit of its index is 1\r
 114             //     ex: log2(2) = 1, bit1 of the index must be 1 (-> 0 1 4 5)\r
 115             //\r
 116             // As such, we calculate all the possible Px and Px' values at the\r
 117             // same time in two variables, evenLineCode and oddLineCode, such as\r
 118             //     evenLineCode bits: P128  P64  P32  P16  P8  P4  P2  P1\r
 119             //     oddLineCode  bits: P128' P64' P32' P16' P8' P4' P2' P1'\r
 120             //\r
 121             evenLineCode ^= (255 - i);\r
 122             oddLineCode ^= i;\r
 123         }\r
 124     }\r
 125 \r
 126     // At this point, we have the line parities, and the column sum. First, We\r
 127     // must caculate the parity group values on the column sum.\r
 128     for (i=0; i < 8; i++)\r
 129     {\r
 130         if (columnSum & 1)\r
 131         {\r
 132             evenColumnCode ^= (7 - i);\r
 133             oddColumnCode ^= i;\r
 134         }\r
 135         columnSum >>= 1;\r
 136     }\r
 137 \r
 138     // Now, we must interleave the parity values, to obtain the following layout:\r
 139     // Code[0] = Line1\r
 140     // Code[1] = Line2\r
 141     // Code[2] = Column\r
 142     // Line = Px' Px P(x-1)- P(x-1) ...\r
 143     // Column = P4' P4 P2' P2 P1' P1 PadBit PadBit\r
 144     code[0] = 0;\r
 145     code[1] = 0;\r
 146     code[2] = 0;\r
 147 \r
 148     for (i=0; i < 4; i++)\r
 149     {\r
 150         code[0] <<= 2;\r
 151         code[1] <<= 2;\r
 152         code[2] <<= 2;\r
 153 \r
 154         // Line 1\r
 155         if ((oddLineCode & 0x80) != 0)\r
 156         {\r
 157             code[0] |= 2;\r
 158         }\r
 159 \r
 160         if ((evenLineCode & 0x80) != 0)\r
 161         {\r
 162             code[0] |= 1;\r
 163         }\r
 164 \r
 165         // Line 2\r
 166         if ((oddLineCode & 0x08) != 0)\r
 167         {\r
 168             code[1] |= 2;\r
 169         }\r
 170 \r
 171         if ((evenLineCode & 0x08) != 0)\r
 172         {\r
 173             code[1] |= 1;\r
 174         }\r
 175 \r
 176         // Column\r
 177         if ((oddColumnCode & 0x04) != 0)\r
 178         {\r
 179             code[2] |= 2;\r
 180         }\r
 181 \r
 182         if ((evenColumnCode & 0x04) != 0)\r
 183         {\r
 184             code[2] |= 1;\r
 185         }\r
 186 \r
 187         oddLineCode <<= 1;\r
 188         evenLineCode <<= 1;\r
 189         oddColumnCode <<= 1;\r
 190         evenColumnCode <<= 1;\r
 191     }\r
 192 \r
 193     // Invert codes (linux compatibility)\r
 194     code[0] = (~(uint32_t)code[0]);\r
 195     code[1] = (~(uint32_t)code[1]);\r
 196     code[2] = (~(uint32_t)code[2]);\r
 197 \r
 198     TRACE_DEBUG("Computed code = %02X %02X %02X\n\r",\r
 199               code[0], code[1], code[2]);\r
 200 }\r
 201 \r
 202 /**\r
 203  *  Verifies and corrects a 256-bytes block of data using the given 22-bits\r
 204  *  hamming code.\r
 205  *\r
 206  *  \param data  Data buffer to check.\r
 207  *  \param originalCode  Hamming code to use for verifying the data.\r
 208  *\r
 209  *  \return 0 if there is no error, otherwise returns a HAMMING_ERROR code.\r
 210  */\r
 211 static uint8_t Verify256( uint8_t* pucData, const uint8_t* pucOriginalCode )\r
 212 {\r
 213     /* Calculate new code */\r
 214     uint8_t computedCode[3] ;\r
 215     uint8_t correctionCode[3] ;\r
 216 \r
 217     Compute256( pucData, computedCode ) ;\r
 218 \r
 219     /* Xor both codes together */\r
 220     correctionCode[0] = computedCode[0] ^ pucOriginalCode[0] ;\r
 221     correctionCode[1] = computedCode[1] ^ pucOriginalCode[1] ;\r
 222     correctionCode[2] = computedCode[2] ^ pucOriginalCode[2] ;\r
 223 \r
 224     TRACE_DEBUG( "Correction code = %02X %02X %02X\n\r", correctionCode[0], correctionCode[1], correctionCode[2] ) ;\r
 225 \r
 226     // If all bytes are 0, there is no error\r
 227     if ( (correctionCode[0] == 0) && (correctionCode[1] == 0) && (correctionCode[2] == 0) )\r
 228     {\r
 229         return 0 ;\r
 230     }\r
 231 \r
 232     /* If there is a single bit error, there are 11 bits set to 1 */\r
 233     if ( CountBitsInCode256( correctionCode ) == 11 )\r
 234     {\r
 235         // Get byte and bit indexes\r
 236         uint8_t byte ;\r
 237         uint8_t bit ;\r
 238         \r
 239         byte = correctionCode[0] & 0x80;\r
 240         byte |= (correctionCode[0] << 1) & 0x40;\r
 241         byte |= (correctionCode[0] << 2) & 0x20;\r
 242         byte |= (correctionCode[0] << 3) & 0x10;\r
 243 \r
 244         byte |= (correctionCode[1] >> 4) & 0x08;\r
 245         byte |= (correctionCode[1] >> 3) & 0x04;\r
 246         byte |= (correctionCode[1] >> 2) & 0x02;\r
 247         byte |= (correctionCode[1] >> 1) & 0x01;\r
 248 \r
 249         bit = (correctionCode[2] >> 5) & 0x04;\r
 250         bit |= (correctionCode[2] >> 4) & 0x02;\r
 251         bit |= (correctionCode[2] >> 3) & 0x01;\r
 252 \r
 253         /* Correct bit */\r
 254         TRACE_DEBUG("Correcting byte #%d at bit %d\n\r", byte, bit ) ;\r
 255         pucData[byte] ^= (1 << bit) ;\r
 256 \r
 257         return Hamming_ERROR_SINGLEBIT ;\r
 258     }\r
 259 \r
 260     /* Check if ECC has been corrupted */\r
 261     if ( CountBitsInCode256( correctionCode ) == 1 )\r
 262     {\r
 263         return Hamming_ERROR_ECC ;\r
 264     }\r
 265     /* Otherwise, this is a multi-bit error */\r
 266     else\r
 267     {\r
 268         return Hamming_ERROR_MULTIPLEBITS ;\r
 269     }\r
 270 }\r
 271 \r
 272 /*----------------------------------------------------------------------------\r
 273  *         Exported functions\r
 274  *----------------------------------------------------------------------------*/\r
 275 \r
 276 /**\r
 277  *  Computes 3-bytes hamming codes for a data block whose size is multiple of\r
 278  *  256 bytes. Each 256 bytes block gets its own code.\r
 279  *  \param data  Data to compute code for.\r
 280  *  \param size  Data size in bytes.\r
 281  *  \param code  Codes buffer.\r
 282  */\r
 283 void Hamming_Compute256x( const uint8_t *pucData, uint32_t dwSize, uint8_t* puCode )\r
 284 {\r
 285     TRACE_DEBUG("Hamming_Compute256x()\n\r");\r
 286 \r
 287     while ( dwSize > 0 )\r
 288     {\r
 289         Compute256( pucData, puCode ) ;\r
 290 \r
 291         pucData += 256;\r
 292         puCode += 3;\r
 293         dwSize -= 256;\r
 294     }\r
 295 }\r
 296 \r
 297 /**\r
 298  *  Verifies 3-bytes hamming codes for a data block whose size is multiple of\r
 299  *  256 bytes. Each 256-bytes block is verified with its own code.\r
 300  *\r
 301  *  \return 0 if the data is correct, Hamming_ERROR_SINGLEBIT if one or more\r
 302  *  block(s) have had a single bit corrected, or either Hamming_ERROR_ECC\r
 303  *  or Hamming_ERROR_MULTIPLEBITS.\r
 304  *\r
 305  *  \param data  Data buffer to verify.\r
 306  *  \param size  Size of the data in bytes.\r
 307  *  \param code  Original codes.\r
 308  */\r
 309 uint8_t Hamming_Verify256x( uint8_t* pucData, uint32_t dwSize, const uint8_t* pucCode )\r
 310 {\r
 311     uint8_t error ;\r
 312     uint8_t result = 0 ;\r
 313 \r
 314     TRACE_DEBUG( "Hamming_Verify256x()\n\r" ) ;\r
 315 \r
 316     while ( dwSize > 0 )\r
 317     {\r
 318         error = Verify256( pucData, pucCode ) ;\r
 319 \r
 320         if ( error == Hamming_ERROR_SINGLEBIT )\r
 321         {\r
 322             result = Hamming_ERROR_SINGLEBIT ;\r
 323         }\r
 324         else\r
 325         {\r
 326             if ( error )\r
 327             {\r
 328                 return error ;\r
 329             }\r
 330         }\r
 331 \r
 332         pucData += 256;\r
 333         pucCode += 3;\r
 334         dwSize -= 256;\r
 335     }\r
 336 \r
 337     return result ;\r
 338 }\r
 339 \r