OpenOCD
ecc_kw.c
Go to the documentation of this file.
1 // SPDX-License-Identifier: GPL-2.0-or-later
2 
3 /*
4  * Reed-Solomon ECC handling for the Marvell Kirkwood SOC
5  * Copyright (C) 2009 Marvell Semiconductor, Inc.
6  *
7  * Authors: Lennert Buytenhek <buytenh@wantstofly.org>
8  * Nicolas Pitre <nico@fluxnic.net>
9  */
10 
11 #ifdef HAVE_CONFIG_H
12 #include "config.h"
13 #endif
14 
15 #include "core.h"
16 
17 /*****************************************************************************
18  * Arithmetic in GF(2^10) ("F") modulo x^10 + x^3 + 1.
19  *
20  * For multiplication, a discrete log/exponent table is used, with
21  * primitive element x (F is a primitive field, so x is primitive).
22  */
23 #define MODPOLY 0x409 /* x^10 + x^3 + 1 in binary */
24 
25 /*
26  * Maps an integer a [0..1022] to a polynomial b = gf_exp[a] in
27  * GF(2^10) mod x^10 + x^3 + 1 such that b = x ^ a. There's two
28  * identical copies of this array back-to-back so that we can save
29  * the mod 1023 operation when doing a GF multiplication.
30  */
31 static uint16_t gf_exp[1023 + 1023];
32 
33 /*
34  * Maps a polynomial b in GF(2^10) mod x^10 + x^3 + 1 to an index
35  * a = gf_log[b] in [0..1022] such that b = x ^ a.
36  */
37 static uint16_t gf_log[1024];
38 
39 static void gf_build_log_exp_table(void)
40 {
41  int i;
42  int p_i;
43 
44  /*
45  * p_i = x ^ i
46  *
47  * Initialise to 1 for i = 0.
48  */
49  p_i = 1;
50 
51  for (i = 0; i < 1023; i++) {
52  gf_exp[i] = p_i;
53  gf_exp[i + 1023] = p_i;
54  gf_log[p_i] = i;
55 
56  /*
57  * p_i = p_i * x
58  */
59  p_i <<= 1;
60  if (p_i & (1 << 10))
61  p_i ^= MODPOLY;
62  }
63 }
64 
65 
66 /*****************************************************************************
67  * Reed-Solomon code
68  *
69  * This implements a (1023,1015) Reed-Solomon ECC code over GF(2^10)
70  * mod x^10 + x^3 + 1, shortened to (520,512). The ECC data consists
71  * of 8 10-bit symbols, or 10 8-bit bytes.
72  *
73  * Given 512 bytes of data, computes 10 bytes of ECC.
74  *
75  * This is done by converting the 512 bytes to 512 10-bit symbols
76  * (elements of F), interpreting those symbols as a polynomial in F[X]
77  * by taking symbol 0 as the coefficient of X^8 and symbol 511 as the
78  * coefficient of X^519, and calculating the residue of that polynomial
79  * divided by the generator polynomial, which gives us the 8 ECC symbols
80  * as the remainder. Finally, we convert the 8 10-bit ECC symbols to 10
81  * 8-bit bytes.
82  *
83  * The generator polynomial is hardcoded, as that is faster, but it
84  * can be computed by taking the primitive element a = x (in F), and
85  * constructing a polynomial in F[X] with roots a, a^2, a^3, ..., a^8
86  * by multiplying the minimal polynomials for those roots (which are
87  * just 'x - a^i' for each i).
88  *
89  * Note: due to unfortunate circumstances, the bootrom in the Kirkwood SOC
90  * expects the ECC to be computed backward, i.e. from the last byte down
91  * to the first one.
92  */
93 int nand_calculate_ecc_kw(struct nand_device *nand, const uint8_t *data, uint8_t *ecc)
94 {
95  unsigned int r7, r6, r5, r4, r3, r2, r1, r0;
96  int i;
97  static int tables_initialized;
98 
99  if (!tables_initialized) {
101  tables_initialized = 1;
102  }
103 
104  /*
105  * Load bytes 504..511 of the data into r.
106  */
107  r0 = data[504];
108  r1 = data[505];
109  r2 = data[506];
110  r3 = data[507];
111  r4 = data[508];
112  r5 = data[509];
113  r6 = data[510];
114  r7 = data[511];
115 
116  /*
117  * Shift bytes 503..0 (in that order) into r0, followed
118  * by eight zero bytes, while reducing the polynomial by the
119  * generator polynomial in every step.
120  */
121  for (i = 503; i >= -8; i--) {
122  unsigned int d;
123 
124  d = 0;
125  if (i >= 0)
126  d = data[i];
127 
128  if (r7) {
129  uint16_t *t = gf_exp + gf_log[r7];
130 
131  r7 = r6 ^ t[0x21c];
132  r6 = r5 ^ t[0x181];
133  r5 = r4 ^ t[0x18e];
134  r4 = r3 ^ t[0x25f];
135  r3 = r2 ^ t[0x197];
136  r2 = r1 ^ t[0x193];
137  r1 = r0 ^ t[0x237];
138  r0 = d ^ t[0x024];
139  } else {
140  r7 = r6;
141  r6 = r5;
142  r5 = r4;
143  r4 = r3;
144  r3 = r2;
145  r2 = r1;
146  r1 = r0;
147  r0 = d;
148  }
149  }
150 
151  ecc[0] = r0;
152  ecc[1] = (r0 >> 8) | (r1 << 2);
153  ecc[2] = (r1 >> 6) | (r2 << 4);
154  ecc[3] = (r2 >> 4) | (r3 << 6);
155  ecc[4] = (r3 >> 2);
156  ecc[5] = r4;
157  ecc[6] = (r4 >> 8) | (r5 << 2);
158  ecc[7] = (r5 >> 6) | (r6 << 4);
159  ecc[8] = (r6 >> 4) | (r7 << 6);
160  ecc[9] = (r7 >> 2);
161 
162  return 0;
163 }
ecc
Definition: davinci.c:22
static void gf_build_log_exp_table(void)
Definition: ecc_kw.c:39
#define MODPOLY
Definition: ecc_kw.c:23
int nand_calculate_ecc_kw(struct nand_device *nand, const uint8_t *data, uint8_t *ecc)
Definition: ecc_kw.c:93
static uint16_t gf_exp[1023+1023]
Definition: ecc_kw.c:31
static uint16_t gf_log[1024]
Definition: ecc_kw.c:37
Upper level NOR flash interfaces.