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