1 /*
2 * Reed-Solomon ECC handling for the Marvell Kirkwood SOC
3 * Copyright (C) 2009 Marvell Semiconductor, Inc.
4 *
6 * Nicolas Pitre <nico@cam.org>
7 *
8 * This file is free software; you can redistribute it and/or modify it
10 * Free Software Foundation; either version 2 or (at your option) any
11 * later version.
12 *
13 * This file is distributed in the hope that it will be useful, but WITHOUT
14 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 * for more details.
17 */
19 #ifdef HAVE_CONFIG_H
20 #include "config.h"
21 #endif
23 #include <sys/types.h>
24 #include "nand.h"
27 /*****************************************************************************
28 * Arithmetic in GF(2^10) ("F") modulo x^10 + x^3 + 1.
29 *
30 * For multiplication, a discrete log/exponent table is used, with
31 * primitive element x (F is a primitive field, so x is primitive).
32 */
33 #define MODPOLY 0x409 /* x^10 + x^3 + 1 in binary */
35 /*
36 * Maps an integer a [0..1022] to a polynomial b = gf_exp[a] in
37 * GF(2^10) mod x^10 + x^3 + 1 such that b = x ^ a. There's two
38 * identical copies of this array back-to-back so that we can save
39 * the mod 1023 operation when doing a GF multiplication.
40 */
41 static uint16_t gf_exp[1023 + 1023];
43 /*
44 * Maps a polynomial b in GF(2^10) mod x^10 + x^3 + 1 to an index
45 * a = gf_log[b] in [0..1022] such that b = x ^ a.
46 */
47 static uint16_t gf_log;
49 static void gf_build_log_exp_table(void)
50 {
51 int i;
52 int p_i;
54 /*
55 * p_i = x ^ i
56 *
57 * Initialise to 1 for i = 0.
58 */
59 p_i = 1;
61 for (i = 0; i < 1023; i++) {
62 gf_exp[i] = p_i;
63 gf_exp[i + 1023] = p_i;
64 gf_log[p_i] = i;
66 /*
67 * p_i = p_i * x
68 */
69 p_i <<= 1;
70 if (p_i & (1 << 10))
71 p_i ^= MODPOLY;
72 }
73 }
76 /*****************************************************************************
77 * Reed-Solomon code
78 *
79 * This implements a (1023,1015) Reed-Solomon ECC code over GF(2^10)
80 * mod x^10 + x^3 + 1, shortened to (520,512). The ECC data consists
81 * of 8 10-bit symbols, or 10 8-bit bytes.
82 *
83 * Given 512 bytes of data, computes 10 bytes of ECC.
84 *
85 * This is done by converting the 512 bytes to 512 10-bit symbols
86 * (elements of F), interpreting those symbols as a polynomial in F[X]
87 * by taking symbol 0 as the coefficient of X^8 and symbol 511 as the
88 * coefficient of X^519, and calculating the residue of that polynomial
89 * divided by the generator polynomial, which gives us the 8 ECC symbols
90 * as the remainder. Finally, we convert the 8 10-bit ECC symbols to 10
91 * 8-bit bytes.
92 *
93 * The generator polynomial is hardcoded, as that is faster, but it
94 * can be computed by taking the primitive element a = x (in F), and
95 * constructing a polynomial in F[X] with roots a, a^2, a^3, ..., a^8
96 * by multiplying the minimal polynomials for those roots (which are
97 * just 'x - a^i' for each i).
98 *
99 * Note: due to unfortunate circumstances, the bootrom in the Kirkwood SOC
100 * expects the ECC to be computed backward, i.e. from the last byte down
101 * to the first one.
102 */
103 int nand_calculate_ecc_kw(struct nand_device_s *device, const u8 *data, u8 *ecc)
104 {
105 unsigned int r7, r6, r5, r4, r3, r2, r1, r0;
106 int i;
107 static int tables_initialized = 0;
109 if (!tables_initialized) {
110 gf_build_log_exp_table();
111 tables_initialized = 1;
112 }
114 /*
115 * Load bytes 504..511 of the data into r.
116 */
117 r0 = data;
118 r1 = data;
119 r2 = data;
120 r3 = data;
121 r4 = data;
122 r5 = data;
123 r6 = data;
124 r7 = data;
127 /*
128 * Shift bytes 503..0 (in that order) into r0, followed
129 * by eight zero bytes, while reducing the polynomial by the
130 * generator polynomial in every step.
131 */
132 for (i = 503; i >= -8; i--) {
133 unsigned int d;
135 d = 0;
136 if (i >= 0)
137 d = data[i];
139 if (r7) {
140 u16 *t = gf_exp + gf_log[r7];
142 r7 = r6 ^ t[0x21c];
143 r6 = r5 ^ t[0x181];
144 r5 = r4 ^ t[0x18e];
145 r4 = r3 ^ t[0x25f];
146 r3 = r2 ^ t[0x197];
147 r2 = r1 ^ t[0x193];
148 r1 = r0 ^ t[0x237];
149 r0 = d ^ t[0x024];
150 } else {
151 r7 = r6;
152 r6 = r5;
153 r5 = r4;
154 r4 = r3;
155 r3 = r2;
156 r2 = r1;
157 r1 = r0;
158 r0 = d;
159 }
160 }
162 ecc = r0;
163 ecc = (r0 >> 8) | (r1 << 2);
164 ecc = (r1 >> 6) | (r2 << 4);
165 ecc = (r2 >> 4) | (r3 << 6);
166 ecc = (r3 >> 2);
167 ecc = r4;
168 ecc = (r4 >> 8) | (r5 << 2);
169 ecc = (r5 >> 6) | (r6 << 4);
170 ecc = (r6 >> 4) | (r7 << 6);
171 ecc = (r7 >> 2);
173 return 0;
174 }