1 // SPDX-License-Identifier: GPL-2.0-or-later
4 * Reed-Solomon ECC handling for the Marvell Kirkwood SOC
5 * Copyright (C) 2009 Marvell Semiconductor, Inc.
7 * Authors: Lennert Buytenhek <buytenh@wantstofly.org>
8 * Nicolas Pitre <nico@fluxnic.net>
17 /*****************************************************************************
18 * Arithmetic in GF(2^10) ("F") modulo x^10 + x^3 + 1.
20 * For multiplication, a discrete log/exponent table is used, with
21 * primitive element x (F is a primitive field, so x is primitive).
23 #define MODPOLY 0x409 /* x^10 + x^3 + 1 in binary */
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.
31 static uint16_t gf_exp[1023 + 1023];
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.
37 static uint16_t gf_log[1024];
39 static void gf_build_log_exp_table(void)
47 * Initialise to 1 for i = 0.
51 for (i = 0; i < 1023; i++) {
53 gf_exp[i + 1023] = p_i;
66 /*****************************************************************************
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.
73 * Given 512 bytes of data, computes 10 bytes of ECC.
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
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).
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
93 int nand_calculate_ecc_kw(struct nand_device *nand, const uint8_t *data, uint8_t *ecc)
95 unsigned int r7, r6, r5, r4, r3, r2, r1, r0;
97 static int tables_initialized;
99 if (!tables_initialized) {
100 gf_build_log_exp_table();
101 tables_initialized = 1;
105 * Load bytes 504..511 of the data into r.
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.
121 for (i = 503; i >= -8; i--) {
129 uint16_t *t = gf_exp + gf_log[r7];
152 ecc[1] = (r0 >> 8) | (r1 << 2);
153 ecc[2] = (r1 >> 6) | (r2 << 4);
154 ecc[3] = (r2 >> 4) | (r3 << 6);
157 ecc[6] = (r4 >> 8) | (r5 << 2);
158 ecc[7] = (r5 >> 6) | (r6 << 4);
159 ecc[8] = (r6 >> 4) | (r7 << 6);