1/*	$NetBSD$	*/
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$");
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 */
41void
42hamming_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 caculate 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 */
182uint8_t
183hamming_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