]> git.sur5r.net Git - openocd/blob - src/flash/nand_ecc_kw.c
David Brownell <david-b@pacbell.net>:
[openocd] / src / flash / nand_ecc_kw.c
1 /*
2  * Reed-Solomon ECC handling for the Marvell Kirkwood SOC
3  * Copyright (C) 2009 Marvell Semiconductor, Inc.
4  *
5  * Authors: Lennert Buytenhek <buytenh@wantstofly.org>
6  *          Nicolas Pitre <nico@cam.org>
7  *
8  * This file is free software; you can redistribute it and/or modify it
9  * under the terms of the GNU General Public License as published by the
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  */
18
19 #ifdef HAVE_CONFIG_H
20 #include "config.h"
21 #endif
22
23 #include <sys/types.h>
24 #include "nand.h"
25
26
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 */
34
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];
42
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[1024];
48
49 static void gf_build_log_exp_table(void)
50 {
51         int i;
52         int p_i;
53
54         /*
55          * p_i = x ^ i
56          *
57          * Initialise to 1 for i = 0.
58          */
59         p_i = 1;
60
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;
65
66                 /*
67                  * p_i = p_i * x
68                  */
69                 p_i <<= 1;
70                 if (p_i & (1 << 10))
71                         p_i ^= MODPOLY;
72         }
73 }
74
75
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;
108
109         if (!tables_initialized) {
110                 gf_build_log_exp_table();
111                 tables_initialized = 1;
112         }
113
114         /*
115          * Load bytes 504..511 of the data into r.
116          */
117         r0 = data[504];
118         r1 = data[505];
119         r2 = data[506];
120         r3 = data[507];
121         r4 = data[508];
122         r5 = data[509];
123         r6 = data[510];
124         r7 = data[511];
125
126
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;
134
135                 d = 0;
136                 if (i >= 0)
137                         d = data[i];
138
139                 if (r7) {
140                         u16 *t = gf_exp + gf_log[r7];
141
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         }
161
162         ecc[0] = r0;
163         ecc[1] = (r0 >> 8) | (r1 << 2);
164         ecc[2] = (r1 >> 6) | (r2 << 4);
165         ecc[3] = (r2 >> 4) | (r3 << 6);
166         ecc[4] = (r3 >> 2);
167         ecc[5] = r4;
168         ecc[6] = (r4 >> 8) | (r5 << 2);
169         ecc[7] = (r5 >> 6) | (r6 << 4);
170         ecc[8] = (r6 >> 4) | (r7 << 6);
171         ecc[9] = (r7 >> 2);
172
173         return 0;
174 }