git.gag.com Git - fw/openocd/blob - 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@fluxnic.net>
   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  * You should have received a copy of the GNU General Public License
  19  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  20  */
  21
  22 #ifdef HAVE_CONFIG_H
  23 #include "config.h"
  24 #endif
  25
  26 #include "core.h"
  27
  28 /*****************************************************************************
  29  * Arithmetic in GF(2^10) ("F") modulo x^10 + x^3 + 1.
  30  *
  31  * For multiplication, a discrete log/exponent table is used, with
  32  * primitive element x (F is a primitive field, so x is primitive).
  33  */
  34 #define MODPOLY 0x409           /* x^10 + x^3 + 1 in binary */
  35
  36 /*
  37  * Maps an integer a [0..1022] to a polynomial b = gf_exp[a] in
  38  * GF(2^10) mod x^10 + x^3 + 1 such that b = x ^ a.  There's two
  39  * identical copies of this array back-to-back so that we can save
  40  * the mod 1023 operation when doing a GF multiplication.
  41  */
  42 static uint16_t gf_exp[1023 + 1023];
  43
  44 /*
  45  * Maps a polynomial b in GF(2^10) mod x^10 + x^3 + 1 to an index
  46  * a = gf_log[b] in [0..1022] such that b = x ^ a.
  47  */
  48 static uint16_t gf_log[1024];
  49
  50 static void gf_build_log_exp_table(void)
  51 {
  52         int i;
  53         int p_i;
  54
  55         /*
  56          * p_i = x ^ i
  57          *
  58          * Initialise to 1 for i = 0.
  59          */
  60         p_i = 1;
  61
  62         for (i = 0; i < 1023; i++) {
  63                 gf_exp[i] = p_i;
  64                 gf_exp[i + 1023] = p_i;
  65                 gf_log[p_i] = i;
  66
  67                 /*
  68                  * p_i = p_i * x
  69                  */
  70                 p_i <<= 1;
  71                 if (p_i & (1 << 10))
  72                         p_i ^= MODPOLY;
  73         }
  74 }
  75
  76
  77 /*****************************************************************************
  78  * Reed-Solomon code
  79  *
  80  * This implements a (1023,1015) Reed-Solomon ECC code over GF(2^10)
  81  * mod x^10 + x^3 + 1, shortened to (520,512).  The ECC data consists
  82  * of 8 10-bit symbols, or 10 8-bit bytes.
  83  *
  84  * Given 512 bytes of data, computes 10 bytes of ECC.
  85  *
  86  * This is done by converting the 512 bytes to 512 10-bit symbols
  87  * (elements of F), interpreting those symbols as a polynomial in F[X]
  88  * by taking symbol 0 as the coefficient of X^8 and symbol 511 as the
  89  * coefficient of X^519, and calculating the residue of that polynomial
  90  * divided by the generator polynomial, which gives us the 8 ECC symbols
  91  * as the remainder.  Finally, we convert the 8 10-bit ECC symbols to 10
  92  * 8-bit bytes.
  93  *
  94  * The generator polynomial is hardcoded, as that is faster, but it
  95  * can be computed by taking the primitive element a = x (in F), and
  96  * constructing a polynomial in F[X] with roots a, a^2, a^3, ..., a^8
  97  * by multiplying the minimal polynomials for those roots (which are
  98  * just 'x - a^i' for each i).
  99  *
 100  * Note: due to unfortunate circumstances, the bootrom in the Kirkwood SOC
 101  * expects the ECC to be computed backward, i.e. from the last byte down
 102  * to the first one.
 103  */
 104 int nand_calculate_ecc_kw(struct nand_device *nand, const uint8_t *data, uint8_t *ecc)
 105 {
 106         unsigned int r7, r6, r5, r4, r3, r2, r1, r0;
 107         int i;
 108         static int tables_initialized;
 109
 110         if (!tables_initialized) {
 111                 gf_build_log_exp_table();
 112                 tables_initialized = 1;
 113         }
 114
 115         /*
 116          * Load bytes 504..511 of the data into r.
 117          */
 118         r0 = data[504];
 119         r1 = data[505];
 120         r2 = data[506];
 121         r3 = data[507];
 122         r4 = data[508];
 123         r5 = data[509];
 124         r6 = data[510];
 125         r7 = data[511];
 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                         uint16_t *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 }