git.gag.com Git - fw/openocd/blob - src/flash/nand_ecc_kw.c

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