1 /* ----------------------------------------------------------------------------
\r
2 * SAM Software Package License
\r
3 * ----------------------------------------------------------------------------
\r
4 * Copyright (c) 2012, Atmel Corporation
\r
6 * All rights reserved.
\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
11 * - Redistributions of source code must retain the above copyright notice,
\r
12 * this list of conditions and the disclaimer below.
\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
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
30 /*----------------------------------------------------------------------------
\r
32 *----------------------------------------------------------------------------*/
\r
36 /*----------------------------------------------------------------------------
\r
38 *----------------------------------------------------------------------------*/
\r
41 * Counts and return the number of bits set to '1' in the given byte.
\r
42 * \param byte Byte to count.
\r
44 static uint8_t CountBitsInByte(uint8_t byte)
\r
61 * Counts and return the number of bits set to '1' in the given hamming code.
\r
62 * \param code Hamming code.
\r
64 static uint8_t CountBitsInCode256(uint8_t *code)
\r
66 return CountBitsInByte(code[0]) + CountBitsInByte(code[1]) + CountBitsInByte(code[2]);
\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
74 static void Compute256(const uint8_t *data, uint8_t *code)
\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
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
87 columnSum ^= data[i];
\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
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
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
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
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
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
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
121 evenLineCode ^= (255 - i);
\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
132 evenColumnCode ^= (7 - i);
\r
133 oddColumnCode ^= i;
\r
138 // Now, we must interleave the parity values, to obtain the following layout:
\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
148 for (i=0; i < 4; i++)
\r
155 if ((oddLineCode & 0x80) != 0)
\r
160 if ((evenLineCode & 0x80) != 0)
\r
166 if ((oddLineCode & 0x08) != 0)
\r
171 if ((evenLineCode & 0x08) != 0)
\r
177 if ((oddColumnCode & 0x04) != 0)
\r
182 if ((evenColumnCode & 0x04) != 0)
\r
188 evenLineCode <<= 1;
\r
189 oddColumnCode <<= 1;
\r
190 evenColumnCode <<= 1;
\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
198 TRACE_DEBUG("Computed code = %02X %02X %02X\n\r",
\r
199 code[0], code[1], code[2]);
\r
203 * Verifies and corrects a 256-bytes block of data using the given 22-bits
\r
206 * \param data Data buffer to check.
\r
207 * \param originalCode Hamming code to use for verifying the data.
\r
209 * \return 0 if there is no error, otherwise returns a HAMMING_ERROR code.
\r
211 static uint8_t Verify256( uint8_t* pucData, const uint8_t* pucOriginalCode )
\r
213 /* Calculate new code */
\r
214 uint8_t computedCode[3] ;
\r
215 uint8_t correctionCode[3] ;
\r
217 Compute256( pucData, computedCode ) ;
\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
224 TRACE_DEBUG( "Correction code = %02X %02X %02X\n\r", correctionCode[0], correctionCode[1], correctionCode[2] ) ;
\r
226 // If all bytes are 0, there is no error
\r
227 if ( (correctionCode[0] == 0) && (correctionCode[1] == 0) && (correctionCode[2] == 0) )
\r
232 /* If there is a single bit error, there are 11 bits set to 1 */
\r
233 if ( CountBitsInCode256( correctionCode ) == 11 )
\r
235 // Get byte and bit indexes
\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
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
249 bit = (correctionCode[2] >> 5) & 0x04;
\r
250 bit |= (correctionCode[2] >> 4) & 0x02;
\r
251 bit |= (correctionCode[2] >> 3) & 0x01;
\r
254 TRACE_DEBUG("Correcting byte #%d at bit %d\n\r", byte, bit ) ;
\r
255 pucData[byte] ^= (1 << bit) ;
\r
257 return Hamming_ERROR_SINGLEBIT ;
\r
260 /* Check if ECC has been corrupted */
\r
261 if ( CountBitsInCode256( correctionCode ) == 1 )
\r
263 return Hamming_ERROR_ECC ;
\r
265 /* Otherwise, this is a multi-bit error */
\r
268 return Hamming_ERROR_MULTIPLEBITS ;
\r
272 /*----------------------------------------------------------------------------
\r
273 * Exported functions
\r
274 *----------------------------------------------------------------------------*/
\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
283 void Hamming_Compute256x( const uint8_t *pucData, uint32_t dwSize, uint8_t* puCode )
\r
285 TRACE_DEBUG("Hamming_Compute256x()\n\r");
\r
287 while ( dwSize > 0 )
\r
289 Compute256( pucData, puCode ) ;
\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
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
305 * \param data Data buffer to verify.
\r
306 * \param size Size of the data in bytes.
\r
307 * \param code Original codes.
\r
309 uint8_t Hamming_Verify256x( uint8_t* pucData, uint32_t dwSize, const uint8_t* pucCode )
\r
312 uint8_t result = 0 ;
\r
314 TRACE_DEBUG( "Hamming_Verify256x()\n\r" ) ;
\r
316 while ( dwSize > 0 )
\r
318 error = Verify256( pucData, pucCode ) ;
\r
320 if ( error == Hamming_ERROR_SINGLEBIT )
\r
322 result = Hamming_ERROR_SINGLEBIT ;
\r