1 /* $NetBSD: hamming.c,v 1.2 2021/12/07 21:37:37 andvar Exp $ */
2
3 /*
4 * Copyright (c) 2008, Atmel Corporation
5 *
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions are met:
10 *
11 * - Redistributions of source code must retain the above copyright notice,
12 * this list of conditions and the disclaimer below.
13 *
14 * Atmel's name may not be used to endorse or promote products derived from
15 * this software without specific prior written permission.
16 *
17 * DISCLAIMER: THIS SOFTWARE IS PROVIDED BY ATMEL "AS IS" AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT ARE
20 * DISCLAIMED. IN NO EVENT SHALL ATMEL BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
23 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
24 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
25 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
26 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 #include <sys/cdefs.h>
30 __KERNEL_RCSID(0, "$NetBSD: hamming.c,v 1.2 2021/12/07 21:37:37 andvar Exp $");
31
32 #include <sys/param.h>
33 #include <lib/libkern/libkern.h>
34 #include "hamming.h"
35
36 /**
37 * Calculates the 22-bit hamming code for a 256-bytes block of data.
38 * \param data Data buffer to calculate code for.
39 * \param code Pointer to a buffer where the code should be stored.
40 */
41 void
hamming_compute_256(const uint8_t * data,uint8_t * code)42 hamming_compute_256(const uint8_t *data, uint8_t *code)
43 {
44 unsigned int i;
45 uint8_t column_sum = 0;
46 uint8_t even_line_code = 0;
47 uint8_t odd_line_code = 0;
48 uint8_t even_column_code = 0;
49 uint8_t odd_column_code = 0;
50
51 /*-
52 * Xor all bytes together to get the column sum;
53 * At the same time, calculate the even and odd line codes
54 */
55 for (i = 0; i < 256; i++) {
56 column_sum ^= data[i];
57
58 /*-
59 * If the xor sum of the byte is 0, then this byte has no
60 * incidence on the computed code; so check if the sum is 1.
61 */
62 if ((popcount(data[i]) & 1) == 1) {
63 /*-
64 * Parity groups are formed by forcing a particular
65 * index bit to 0 (even) or 1 (odd).
66 * Example on one byte:
67 *
68 * bits (dec) 7 6 5 4 3 2 1 0
69 * (bin) 111 110 101 100 011 010 001 000
70 * '---'---'---'----------.
71 * |
72 * groups P4' ooooooooooooooo eeeeeeeeeeeeeee P4 |
73 * P2' ooooooo eeeeeee ooooooo eeeeeee P2 |
74 * P1' ooo eee ooo eee ooo eee ooo eee P1 |
75 * |
76 * We can see that: |
77 * - P4 -> bit 2 of index is 0 --------------------'
78 * - P4' -> bit 2 of index is 1.
79 * - P2 -> bit 1 of index if 0.
80 * - etc...
81 * We deduce that a bit position has an impact on all
82 * even Px if the log2(x)nth bit of its index is 0
83 * ex: log2(4) = 2,
84 * bit2 of the index must be 0 (-> 0 1 2 3)
85 * and on all odd Px' if the log2(x)nth bit
86 * of its index is 1
87 * ex: log2(2) = 1,
88 * bit1 of the index must be 1 (-> 0 1 4 5)
89 *
90 * As such, we calculate all the possible Px and Px'
91 * values at the same time in two variables,
92 * even_line_code and odd_line_code, such as
93 * even_line_code bits: P128 P64 P32
94 * P16 P8 P4 P2 P1
95 * odd_line_code bits: P128' P64' P32' P16'
96 * P8' P4' P2' P1'
97 */
98 even_line_code ^= (255 - i);
99 odd_line_code ^= i;
100 }
101 }
102
103 /*-
104 * At this point, we have the line parities, and the column sum.
105 * First, We must calculate the parity group values on the column sum.
106 */
107 for (i = 0; i < 8; i++) {
108 if (column_sum & 1) {
109 even_column_code ^= (7 - i);
110 odd_column_code ^= i;
111 }
112 column_sum >>= 1;
113 }
114
115 /*-
116 * Now, we must interleave the parity values,
117 * to obtain the following layout:
118 * Code[0] = Line1
119 * Code[1] = Line2
120 * Code[2] = Column
121 * Line = Px' Px P(x-1)- P(x-1) ...
122 * Column = P4' P4 P2' P2 P1' P1 PadBit PadBit
123 */
124 code[0] = 0;
125 code[1] = 0;
126 code[2] = 0;
127
128 for (i = 0; i < 4; i++) {
129 code[0] <<= 2;
130 code[1] <<= 2;
131 code[2] <<= 2;
132
133 /* Line 1 */
134 if ((odd_line_code & 0x80) != 0) {
135
136 code[0] |= 2;
137 }
138 if ((even_line_code & 0x80) != 0) {
139
140 code[0] |= 1;
141 }
142
143 /* Line 2 */
144 if ((odd_line_code & 0x08) != 0) {
145
146 code[1] |= 2;
147 }
148 if ((even_line_code & 0x08) != 0) {
149
150 code[1] |= 1;
151 }
152
153 /* Column */
154 if ((odd_column_code & 0x04) != 0) {
155
156 code[2] |= 2;
157 }
158 if ((even_column_code & 0x04) != 0) {
159
160 code[2] |= 1;
161 }
162
163 odd_line_code <<= 1;
164 even_line_code <<= 1;
165 odd_column_code <<= 1;
166 even_column_code <<= 1;
167 }
168
169 /* Invert codes (linux compatibility) */
170 code[0] = ~code[0];
171 code[1] = ~code[1];
172 code[2] = ~code[2];
173 }
174
175 /**
176 * Verifies and corrects a 256-bytes block of data using the given 22-bits
177 * hamming code.
178 * Returns 0 if there is no error, otherwise returns a HAMMING_ERROR code.
179 * param data Data buffer to check.
180 * \param original_code Hamming code to use for verifying the data.
181 */
182 uint8_t
hamming_correct_256(uint8_t * data,const uint8_t * original_code,const uint8_t * computed_code)183 hamming_correct_256(uint8_t *data, const uint8_t *original_code,
184 const uint8_t *computed_code)
185 {
186 /* Calculate new code */
187 /* we allocate 4 bytes so we can use popcount32 in one step */
188 uint8_t correction_code[4];
189
190 /* this byte should remain zero all the time */
191 correction_code[3] = 0;
192
193 /* Xor both codes together */
194 correction_code[0] = computed_code[0] ^ original_code[0];
195 correction_code[1] = computed_code[1] ^ original_code[1];
196 correction_code[2] = computed_code[2] ^ original_code[2];
197
198 /* If all bytes are 0, there is no error */
199 if (*(uint32_t *)correction_code == 0) {
200 return 0;
201 }
202 /* If there is a single bit error, there are 11 bits set to 1 */
203 if (popcount32(*(uint32_t *)correction_code) == 11) {
204 /* Get byte and bit indexes */
205 uint8_t byte = correction_code[0] & 0x80;
206 byte |= (correction_code[0] << 1) & 0x40;
207 byte |= (correction_code[0] << 2) & 0x20;
208 byte |= (correction_code[0] << 3) & 0x10;
209
210 byte |= (correction_code[1] >> 4) & 0x08;
211 byte |= (correction_code[1] >> 3) & 0x04;
212 byte |= (correction_code[1] >> 2) & 0x02;
213 byte |= (correction_code[1] >> 1) & 0x01;
214
215 uint8_t bit = (correction_code[2] >> 5) & 0x04;
216 bit |= (correction_code[2] >> 4) & 0x02;
217 bit |= (correction_code[2] >> 3) & 0x01;
218
219 /* Correct bit */
220 data[byte] ^= (1 << bit);
221
222 return HAMMING_ERROR_SINGLEBIT;
223 }
224 /* Check if ECC has been corrupted */
225 if (popcount32(*(uint32_t *)correction_code) == 1) {
226 return HAMMING_ERROR_ECC;
227 } else {
228 /* Otherwise, this is a multi-bit error */
229 return HAMMING_ERROR_MULTIPLEBITS;
230 }
231 }
232
233