drivers/mtd/nand/nand_ecc_rs.c

   1 /*
   2  * Reed-Solomon ECC handling for the Marvell Kirkwood SOC
   3  * Copyright (C) 2017 Lothar Waßmann <LW@KARO-electronics.de>
   4  *
   5  * derived from openocd src/flash/nand/ecc_kw.c:
   6  * Copyright (C) 2009 Marvell Semiconductor, Inc.
   7  *
   8  * Authors: Lennert Buytenhek <buytenh@wantstofly.org>
   9  *          Nicolas Pitre <nico@fluxnic.net>
  10  *
  11  * This file is free software; you can redistribute it and/or modify it
  12  * under the terms of the GNU General Public License as published by the
  13  * Free Software Foundation; either version 2 or (at your option) any
  14  * later version.
  15  *
  16  * This file is distributed in the hope that it will be useful, but WITHOUT
  17  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  18  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  19  * for more details.
  20  */
  21 #include <common.h>
  22 #include <asm-generic/errno.h>
  23 #include <linux/mtd/nand.h>
  24 #include <linux/mtd/nand_ecc.h>
  25
  26 /*****************************************************************************
  27  * Arithmetic in GF(2^10) ("F") modulo x^10 + x^3 + 1.
  28  *
  29  * For multiplication, a discrete log/exponent table is used, with
  30  * primitive element x (F is a primitive field, so x is primitive).
  31  */
  32 #define MODPOLY 0x409           /* x^10 + x^3 + 1 in binary */
  33
  34 /*
  35  * Maps an integer a [0..1022] to a polynomial b = gf_exp[a] in
  36  * GF(2^10) mod x^10 + x^3 + 1 such that b = x ^ a.  There's two
  37  * identical copies of this array back-to-back so that we can save
  38  * the mod 1023 operation when doing a GF multiplication.
  39  */
  40 static uint16_t gf_exp[1023 + 1023];
  41
  42 /*
  43  * Maps a polynomial b in GF(2^10) mod x^10 + x^3 + 1 to an index
  44  * a = gf_log[b] in [0..1022] such that b = x ^ a.
  45  */
  46 static uint16_t gf_log[1024];
  47
  48 static void gf_build_log_exp_table(void)
  49 {
  50         int i;
  51         int p_i;
  52
  53         /*
  54          * p_i = x ^ i
  55          *
  56          * Initialise to 1 for i = 0.
  57          */
  58         p_i = 1;
  59
  60         for (i = 0; i < 1023; i++) {
  61                 gf_exp[i] = p_i;
  62                 gf_exp[i + 1023] = p_i;
  63                 gf_log[p_i] = i;
  64
  65                 /*
  66                  * p_i = p_i * x
  67                  */
  68                 p_i <<= 1;
  69                 if (p_i & (1 << 10))
  70                         p_i ^= MODPOLY;
  71         }
  72 #ifdef DEBUG
  73         for (i = 0; i < ARRAY_SIZE(gf_log); i++) {
  74                 printf("exp[%03x]=%4d log[%03x]=%4d\n", i, gf_exp[i], i, gf_log[i]);
  75         }
  76         for (; i < ARRAY_SIZE(gf_exp); i++) {
  77                 printf("exp[%03x]=%4d\n", i, gf_exp[i]);
  78         }
  79 #endif
  80 }
  81
  82 /*****************************************************************************
  83  * Reed-Solomon code
  84  *
  85  * This implements a (1023,1015) Reed-Solomon ECC code over GF(2^10)
  86  * mod x^10 + x^3 + 1, shortened to (520,512).  The ECC data consists
  87  * of 8 10-bit symbols, or 10 8-bit bytes.
  88  *
  89  * Given 512 bytes of data, computes 10 bytes of ECC.
  90  *
  91  * This is done by converting the 512 bytes to 512 10-bit symbols
  92  * (elements of F), interpreting those symbols as a polynomial in F[X]
  93  * by taking symbol 0 as the coefficient of X^8 and symbol 511 as the
  94  * coefficient of X^519, and calculating the residue of that polynomial
  95  * divided by the generator polynomial, which gives us the 8 ECC symbols
  96  * as the remainder.  Finally, we convert the 8 10-bit ECC symbols to 10
  97  * 8-bit bytes.
  98  *
  99  * The generator polynomial is hardcoded, as that is faster, but it
 100  * can be computed by taking the primitive element a = x (in F), and
 101  * constructing a polynomial in F[X] with roots a, a^2, a^3, ..., a^8
 102  * by multiplying the minimal polynomials for those roots (which are
 103  * just 'x - a^i' for each i).
 104  *
 105  * Note: due to unfortunate circumstances, the bootrom in the Kirkwood SOC
 106  * expects the ECC to be computed backward, i.e. from the last byte down
 107  * to the first one.
 108  */
 109 int nand_rs_calculate_ecc(struct mtd_info *mtd, const uint8_t *data,
 110                           uint8_t *ecc)
 111 {
 112         unsigned int r7, r6, r5, r4, r3, r2, r1, r0;
 113         int i;
 114         static int tables_initialized;
 115
 116         if (!tables_initialized) {
 117                 printf("Using RS-ECC\n");
 118                 gf_build_log_exp_table();
 119                 tables_initialized = 1;
 120         }
 121
 122         /*
 123          * Load bytes 504..511 of the data into r.
 124          */
 125         r0 = data[504];
 126         r1 = data[505];
 127         r2 = data[506];
 128         r3 = data[507];
 129         r4 = data[508];
 130         r5 = data[509];
 131         r6 = data[510];
 132         r7 = data[511];
 133
 134         /*
 135          * Shift bytes 503..0 (in that order) into r0, followed
 136          * by eight zero bytes, while reducing the polynomial by the
 137          * generator polynomial in every step.
 138          */
 139         for (i = 503; i >= -8; i--) {
 140                 unsigned int d = (i >= 0) ? data[i] : 0;
 141
 142                 if (r7) {
 143                         uint16_t *t = &gf_exp[gf_log[r7]];
 144
 145                         r7 = r6 ^ t[0x21c]; // 540
 146                         r6 = r5 ^ t[0x181]; // 385
 147                         r5 = r4 ^ t[0x18e]; // 398
 148                         r4 = r3 ^ t[0x25f]; // 607
 149                         r3 = r2 ^ t[0x197]; // 407
 150                         r2 = r1 ^ t[0x193]; // 403
 151                         r1 = r0 ^ t[0x237]; // 567
 152                         r0 = d  ^ t[0x024]; //  36
 153                 } else {
 154                         r7 = r6;
 155                         r6 = r5;
 156                         r5 = r4;
 157                         r4 = r3;
 158                         r3 = r2;
 159                         r2 = r1;
 160                         r1 = r0;
 161                         r0 = d;
 162                 }
 163         }
 164
 165         ecc[0] = r0;
 166         ecc[1] = (r0 >> 8) | (r1 << 2);
 167         ecc[2] = (r1 >> 6) | (r2 << 4);
 168         ecc[3] = (r2 >> 4) | (r3 << 6);
 169         ecc[4] = (r3 >> 2);
 170         ecc[5] = r4;
 171         ecc[6] = (r4 >> 8) | (r5 << 2);
 172         ecc[7] = (r5 >> 6) | (r6 << 4);
 173         ecc[8] = (r6 >> 4) | (r7 << 6);
 174         ecc[9] = (r7 >> 2);
 175
 176         debug("ECC: %03x %03x %03x %03x %03x %03x %03x %03x\n",
 177               r0, r1, r2, r3, r4, r5, r6, r7);
 178
 179         return 0;
 180 }
 181
 182 int nand_rs_correct_data(struct mtd_info *mtd, u_char *dat,
 183                          u_char *read_ecc, u_char *calc_ecc)
 184 {
 185         static int once;
 186         if (!once) {
 187                 printf("Reading NAND with RS-ECC not supported\n");
 188                 once++;
 189         }
 190         return -EINVAL;
 191 }