docecc.c 14.8 KB
Newer Older
wdenk's avatar
wdenk committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
/*
 * ECC algorithm for M-systems disk on chip. We use the excellent Reed
 * Solmon code of Phil Karn (karn@ka9q.ampr.org) available under the
 * GNU GPL License. The rest is simply to convert the disk on chip
 * syndrom into a standard syndom.
 *
 * Author: Fabrice Bellard (fabrice.bellard@netgem.com)
 * Copyright (C) 2000 Netgem S.A.
 *
 * $Id: docecc.c,v 1.4 2001/10/02 15:05:13 dwmw2 Exp $
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#include <config.h>
#include <common.h>
#include <malloc.h>

#undef ECC_DEBUG
#undef PSYCHO_DEBUG

#if (CONFIG_COMMANDS & CFG_CMD_DOC)

wdenk's avatar
wdenk committed
36 37
#include <linux/mtd/doc2000.h>

wdenk's avatar
wdenk committed
38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
/* need to undef it (from asm/termbits.h) */
#undef B0

#define MM 10 /* Symbol size in bits */
#define KK (1023-4) /* Number of data symbols per block */
#define B0 510 /* First root of generator polynomial, alpha form */
#define PRIM 1 /* power of alpha used to generate roots of generator poly */
#define	NN ((1 << MM) - 1)

typedef unsigned short dtype;

/* 1+x^3+x^10 */
static const int Pp[MM+1] = { 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1 };

/* This defines the type used to store an element of the Galois Field
 * used by the code. Make sure this is something larger than a char if
 * if anything larger than GF(256) is used.
 *
 * Note: unsigned char will work up to GF(256) but int seems to run
 * faster on the Pentium.
 */
typedef int gf;

/* No legal value in index form represents zero, so
 * we need a special value for this purpose
 */
#define A0	(NN)

/* Compute x % NN, where NN is 2**MM - 1,
 * without a slow divide
 */
static inline gf
modnn(int x)
{
  while (x >= NN) {
    x -= NN;
    x = (x >> MM) + (x & NN);
  }
  return x;
}

#define	CLEAR(a,n) {\
int ci;\
for(ci=(n)-1;ci >=0;ci--)\
(a)[ci] = 0;\
}

#define	COPY(a,b,n) {\
int ci;\
for(ci=(n)-1;ci >=0;ci--)\
(a)[ci] = (b)[ci];\
}

#define	COPYDOWN(a,b,n) {\
int ci;\
for(ci=(n)-1;ci >=0;ci--)\
(a)[ci] = (b)[ci];\
}

#define Ldec 1

/* generate GF(2**m) from the irreducible polynomial p(X) in Pp[0]..Pp[m]
   lookup tables:  index->polynomial form   alpha_to[] contains j=alpha**i;
wdenk's avatar
wdenk committed
101
		   polynomial form -> index form  index_of[j=alpha**i] = i
wdenk's avatar
wdenk committed
102 103
   alpha=2 is the primitive element of GF(2**m)
   HARI's COMMENT: (4/13/94) alpha_to[] can be used as follows:
wdenk's avatar
wdenk committed
104
	Let @ represent the primitive element commonly called "alpha" that
wdenk's avatar
wdenk committed
105 106
   is the root of the primitive polynomial p(x). Then in GF(2^m), for any
   0 <= i <= 2^m-2,
wdenk's avatar
wdenk committed
107
	@^i = a(0) + a(1) @ + a(2) @^2 + ... + a(m-1) @^(m-1)
wdenk's avatar
wdenk committed
108 109 110 111
   where the binary vector (a(0),a(1),a(2),...,a(m-1)) is the representation
   of the integer "alpha_to[i]" with a(0) being the LSB and a(m-1) the MSB. Thus for
   example the polynomial representation of @^5 would be given by the binary
   representation of the integer "alpha_to[5]".
wdenk's avatar
wdenk committed
112 113
		   Similarily, index_of[] can be used as follows:
	As above, let @ represent the primitive element of GF(2^m) that is
wdenk's avatar
wdenk committed
114 115
   the root of the primitive polynomial p(x). In order to find the power
   of @ (alpha) that has the polynomial representation
wdenk's avatar
wdenk committed
116
	a(0) + a(1) @ + a(2) @^2 + ... + a(m-1) @^(m-1)
wdenk's avatar
wdenk committed
117 118 119 120 121
   we consider the integer "i" whose binary representation with a(0) being LSB
   and a(m-1) MSB is (a(0),a(1),...,a(m-1)) and locate the entry
   "index_of[i]". Now, @^index_of[i] is that element whose polynomial
    representation is (a(0),a(1),a(2),...,a(m-1)).
   NOTE:
wdenk's avatar
wdenk committed
122
	The element alpha_to[2^m-1] = 0 always signifying that the
wdenk's avatar
wdenk committed
123
   representation of "@^infinity" = 0 is (0,0,0,...,0).
wdenk's avatar
wdenk committed
124
	Similarily, the element index_of[0] = A0 always signifying
wdenk's avatar
wdenk committed
125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185
   that the power of alpha which has the polynomial representation
   (0,0,...,0) is "infinity".

*/

static void
generate_gf(dtype Alpha_to[NN + 1], dtype Index_of[NN + 1])
{
  register int i, mask;

  mask = 1;
  Alpha_to[MM] = 0;
  for (i = 0; i < MM; i++) {
    Alpha_to[i] = mask;
    Index_of[Alpha_to[i]] = i;
    /* If Pp[i] == 1 then, term @^i occurs in poly-repr of @^MM */
    if (Pp[i] != 0)
      Alpha_to[MM] ^= mask;	/* Bit-wise EXOR operation */
    mask <<= 1;	/* single left-shift */
  }
  Index_of[Alpha_to[MM]] = MM;
  /*
   * Have obtained poly-repr of @^MM. Poly-repr of @^(i+1) is given by
   * poly-repr of @^i shifted left one-bit and accounting for any @^MM
   * term that may occur when poly-repr of @^i is shifted.
   */
  mask >>= 1;
  for (i = MM + 1; i < NN; i++) {
    if (Alpha_to[i - 1] >= mask)
      Alpha_to[i] = Alpha_to[MM] ^ ((Alpha_to[i - 1] ^ mask) << 1);
    else
      Alpha_to[i] = Alpha_to[i - 1] << 1;
    Index_of[Alpha_to[i]] = i;
  }
  Index_of[0] = A0;
  Alpha_to[NN] = 0;
}

/*
 * Performs ERRORS+ERASURES decoding of RS codes. bb[] is the content
 * of the feedback shift register after having processed the data and
 * the ECC.
 *
 * Return number of symbols corrected, or -1 if codeword is illegal
 * or uncorrectable. If eras_pos is non-null, the detected error locations
 * are written back. NOTE! This array must be at least NN-KK elements long.
 * The corrected data are written in eras_val[]. They must be xor with the data
 * to retrieve the correct data : data[erase_pos[i]] ^= erase_val[i] .
 *
 * First "no_eras" erasures are declared by the calling program. Then, the
 * maximum # of errors correctable is t_after_eras = floor((NN-KK-no_eras)/2).
 * If the number of channel errors is not greater than "t_after_eras" the
 * transmitted codeword will be recovered. Details of algorithm can be found
 * in R. Blahut's "Theory ... of Error-Correcting Codes".

 * Warning: the eras_pos[] array must not contain duplicate entries; decoder failure
 * will result. The decoder *could* check for this condition, but it would involve
 * extra time on every decoding operation.
 * */
static int
eras_dec_rs(dtype Alpha_to[NN + 1], dtype Index_of[NN + 1],
wdenk's avatar
wdenk committed
186 187
	    gf bb[NN - KK + 1], gf eras_val[NN-KK], int eras_pos[NN-KK],
	    int no_eras)
wdenk's avatar
wdenk committed
188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227
{
  int deg_lambda, el, deg_omega;
  int i, j, r,k;
  gf u,q,tmp,num1,num2,den,discr_r;
  gf lambda[NN-KK + 1], s[NN-KK + 1];	/* Err+Eras Locator poly
					 * and syndrome poly */
  gf b[NN-KK + 1], t[NN-KK + 1], omega[NN-KK + 1];
  gf root[NN-KK], reg[NN-KK + 1], loc[NN-KK];
  int syn_error, count;

  syn_error = 0;
  for(i=0;i<NN-KK;i++)
      syn_error |= bb[i];

  if (!syn_error) {
    /* if remainder is zero, data[] is a codeword and there are no
     * errors to correct. So return data[] unmodified
     */
    count = 0;
    goto finish;
  }

  for(i=1;i<=NN-KK;i++){
    s[i] = bb[0];
  }
  for(j=1;j<NN-KK;j++){
    if(bb[j] == 0)
      continue;
    tmp = Index_of[bb[j]];

    for(i=1;i<=NN-KK;i++)
      s[i] ^= Alpha_to[modnn(tmp + (B0+i-1)*PRIM*j)];
  }

  /* undo the feedback register implicit multiplication and convert
     syndromes to index form */

  for(i=1;i<=NN-KK;i++) {
      tmp = Index_of[s[i]];
      if (tmp != A0)
wdenk's avatar
wdenk committed
228
	  tmp = modnn(tmp + 2 * KK * (B0+i-1)*PRIM);
wdenk's avatar
wdenk committed
229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414
      s[i] = tmp;
  }

  CLEAR(&lambda[1],NN-KK);
  lambda[0] = 1;

  if (no_eras > 0) {
    /* Init lambda to be the erasure locator polynomial */
    lambda[1] = Alpha_to[modnn(PRIM * eras_pos[0])];
    for (i = 1; i < no_eras; i++) {
      u = modnn(PRIM*eras_pos[i]);
      for (j = i+1; j > 0; j--) {
	tmp = Index_of[lambda[j - 1]];
	if(tmp != A0)
	  lambda[j] ^= Alpha_to[modnn(u + tmp)];
      }
    }
#ifdef ECC_DEBUG
    /* Test code that verifies the erasure locator polynomial just constructed
       Needed only for decoder debugging. */

    /* find roots of the erasure location polynomial */
    for(i=1;i<=no_eras;i++)
      reg[i] = Index_of[lambda[i]];
    count = 0;
    for (i = 1,k=NN-Ldec; i <= NN; i++,k = modnn(NN+k-Ldec)) {
      q = 1;
      for (j = 1; j <= no_eras; j++)
	if (reg[j] != A0) {
	  reg[j] = modnn(reg[j] + j);
	  q ^= Alpha_to[reg[j]];
	}
      if (q != 0)
	continue;
      /* store root and error location number indices */
      root[count] = i;
      loc[count] = k;
      count++;
    }
    if (count != no_eras) {
      printf("\n lambda(x) is WRONG\n");
      count = -1;
      goto finish;
    }
#ifdef PSYCHO_DEBUG
    printf("\n Erasure positions as determined by roots of Eras Loc Poly:\n");
    for (i = 0; i < count; i++)
      printf("%d ", loc[i]);
    printf("\n");
#endif
#endif
  }
  for(i=0;i<NN-KK+1;i++)
    b[i] = Index_of[lambda[i]];

  /*
   * Begin Berlekamp-Massey algorithm to determine error+erasure
   * locator polynomial
   */
  r = no_eras;
  el = no_eras;
  while (++r <= NN-KK) {	/* r is the step number */
    /* Compute discrepancy at the r-th step in poly-form */
    discr_r = 0;
    for (i = 0; i < r; i++){
      if ((lambda[i] != 0) && (s[r - i] != A0)) {
	discr_r ^= Alpha_to[modnn(Index_of[lambda[i]] + s[r - i])];
      }
    }
    discr_r = Index_of[discr_r];	/* Index form */
    if (discr_r == A0) {
      /* 2 lines below: B(x) <-- x*B(x) */
      COPYDOWN(&b[1],b,NN-KK);
      b[0] = A0;
    } else {
      /* 7 lines below: T(x) <-- lambda(x) - discr_r*x*b(x) */
      t[0] = lambda[0];
      for (i = 0 ; i < NN-KK; i++) {
	if(b[i] != A0)
	  t[i+1] = lambda[i+1] ^ Alpha_to[modnn(discr_r + b[i])];
	else
	  t[i+1] = lambda[i+1];
      }
      if (2 * el <= r + no_eras - 1) {
	el = r + no_eras - el;
	/*
	 * 2 lines below: B(x) <-- inv(discr_r) *
	 * lambda(x)
	 */
	for (i = 0; i <= NN-KK; i++)
	  b[i] = (lambda[i] == 0) ? A0 : modnn(Index_of[lambda[i]] - discr_r + NN);
      } else {
	/* 2 lines below: B(x) <-- x*B(x) */
	COPYDOWN(&b[1],b,NN-KK);
	b[0] = A0;
      }
      COPY(lambda,t,NN-KK+1);
    }
  }

  /* Convert lambda to index form and compute deg(lambda(x)) */
  deg_lambda = 0;
  for(i=0;i<NN-KK+1;i++){
    lambda[i] = Index_of[lambda[i]];
    if(lambda[i] != A0)
      deg_lambda = i;
  }
  /*
   * Find roots of the error+erasure locator polynomial by Chien
   * Search
   */
  COPY(&reg[1],&lambda[1],NN-KK);
  count = 0;		/* Number of roots of lambda(x) */
  for (i = 1,k=NN-Ldec; i <= NN; i++,k = modnn(NN+k-Ldec)) {
    q = 1;
    for (j = deg_lambda; j > 0; j--){
      if (reg[j] != A0) {
	reg[j] = modnn(reg[j] + j);
	q ^= Alpha_to[reg[j]];
      }
    }
    if (q != 0)
      continue;
    /* store root (index-form) and error location number */
    root[count] = i;
    loc[count] = k;
    /* If we've already found max possible roots,
     * abort the search to save time
     */
    if(++count == deg_lambda)
      break;
  }
  if (deg_lambda != count) {
    /*
     * deg(lambda) unequal to number of roots => uncorrectable
     * error detected
     */
    count = -1;
    goto finish;
  }
  /*
   * Compute err+eras evaluator poly omega(x) = s(x)*lambda(x) (modulo
   * x**(NN-KK)). in index form. Also find deg(omega).
   */
  deg_omega = 0;
  for (i = 0; i < NN-KK;i++){
    tmp = 0;
    j = (deg_lambda < i) ? deg_lambda : i;
    for(;j >= 0; j--){
      if ((s[i + 1 - j] != A0) && (lambda[j] != A0))
	tmp ^= Alpha_to[modnn(s[i + 1 - j] + lambda[j])];
    }
    if(tmp != 0)
      deg_omega = i;
    omega[i] = Index_of[tmp];
  }
  omega[NN-KK] = A0;

  /*
   * Compute error values in poly-form. num1 = omega(inv(X(l))), num2 =
   * inv(X(l))**(B0-1) and den = lambda_pr(inv(X(l))) all in poly-form
   */
  for (j = count-1; j >=0; j--) {
    num1 = 0;
    for (i = deg_omega; i >= 0; i--) {
      if (omega[i] != A0)
	num1  ^= Alpha_to[modnn(omega[i] + i * root[j])];
    }
    num2 = Alpha_to[modnn(root[j] * (B0 - 1) + NN)];
    den = 0;

    /* lambda[i+1] for i even is the formal derivative lambda_pr of lambda[i] */
    for (i = min(deg_lambda,NN-KK-1) & ~1; i >= 0; i -=2) {
      if(lambda[i+1] != A0)
	den ^= Alpha_to[modnn(lambda[i+1] + i * root[j])];
    }
    if (den == 0) {
#ifdef ECC_DEBUG
      printf("\n ERROR: denominator = 0\n");
#endif
      /* Convert to dual- basis */
      count = -1;
      goto finish;
    }
    /* Apply error to data */
    if (num1 != 0) {
wdenk's avatar
wdenk committed
415
	eras_val[j] = Alpha_to[modnn(Index_of[num1] + Index_of[num2] + NN - Index_of[den])];
wdenk's avatar
wdenk committed
416
    } else {
wdenk's avatar
wdenk committed
417
	eras_val[j] = 0;
wdenk's avatar
wdenk committed
418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449
    }
  }
 finish:
  for(i=0;i<count;i++)
      eras_pos[i] = loc[i];
  return count;
}

/***************************************************************************/
/* The DOC specific code begins here */

#define SECTOR_SIZE 512
/* The sector bytes are packed into NB_DATA MM bits words */
#define NB_DATA (((SECTOR_SIZE + 1) * 8 + 6) / MM)

/*
 * Correct the errors in 'sector[]' by using 'ecc1[]' which is the
 * content of the feedback shift register applyied to the sector and
 * the ECC. Return the number of errors corrected (and correct them in
 * sector), or -1 if error
 */
int doc_decode_ecc(unsigned char sector[SECTOR_SIZE], unsigned char ecc1[6])
{
    int parity, i, nb_errors;
    gf bb[NN - KK + 1];
    gf error_val[NN-KK];
    int error_pos[NN-KK], pos, bitpos, index, val;
    dtype *Alpha_to, *Index_of;

    /* init log and exp tables here to save memory. However, it is slower */
    Alpha_to = malloc((NN + 1) * sizeof(dtype));
    if (!Alpha_to)
wdenk's avatar
wdenk committed
450
	return -1;
wdenk's avatar
wdenk committed
451 452 453

    Index_of = malloc((NN + 1) * sizeof(dtype));
    if (!Index_of) {
wdenk's avatar
wdenk committed
454 455
	free(Alpha_to);
	return -1;
wdenk's avatar
wdenk committed
456 457 458 459 460 461 462 463 464 465 466 467
    }

    generate_gf(Alpha_to, Index_of);

    parity = ecc1[1];

    bb[0] =  (ecc1[4] & 0xff) | ((ecc1[5] & 0x03) << 8);
    bb[1] = ((ecc1[5] & 0xfc) >> 2) | ((ecc1[2] & 0x0f) << 6);
    bb[2] = ((ecc1[2] & 0xf0) >> 4) | ((ecc1[3] & 0x3f) << 4);
    bb[3] = ((ecc1[3] & 0xc0) >> 6) | ((ecc1[0] & 0xff) << 2);

    nb_errors = eras_dec_rs(Alpha_to, Index_of, bb,
wdenk's avatar
wdenk committed
468
			    error_val, error_pos, 0);
wdenk's avatar
wdenk committed
469
    if (nb_errors <= 0)
wdenk's avatar
wdenk committed
470
	goto the_end;
wdenk's avatar
wdenk committed
471 472 473

    /* correct the errors */
    for(i=0;i<nb_errors;i++) {
wdenk's avatar
wdenk committed
474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504
	pos = error_pos[i];
	if (pos >= NB_DATA && pos < KK) {
	    nb_errors = -1;
	    goto the_end;
	}
	if (pos < NB_DATA) {
	    /* extract bit position (MSB first) */
	    pos = 10 * (NB_DATA - 1 - pos) - 6;
	    /* now correct the following 10 bits. At most two bytes
	       can be modified since pos is even */
	    index = (pos >> 3) ^ 1;
	    bitpos = pos & 7;
	    if ((index >= 0 && index < SECTOR_SIZE) ||
		index == (SECTOR_SIZE + 1)) {
		val = error_val[i] >> (2 + bitpos);
		parity ^= val;
		if (index < SECTOR_SIZE)
		    sector[index] ^= val;
	    }
	    index = ((pos >> 3) + 1) ^ 1;
	    bitpos = (bitpos + 10) & 7;
	    if (bitpos == 0)
		bitpos = 8;
	    if ((index >= 0 && index < SECTOR_SIZE) ||
		index == (SECTOR_SIZE + 1)) {
		val = error_val[i] << (8 - bitpos);
		parity ^= val;
		if (index < SECTOR_SIZE)
		    sector[index] ^= val;
	    }
	}
wdenk's avatar
wdenk committed
505 506 507 508
    }

    /* use parity to test extra errors */
    if ((parity & 0xff) != 0)
wdenk's avatar
wdenk committed
509
	nb_errors = -1;
wdenk's avatar
wdenk committed
510 511 512 513 514 515 516 517

 the_end:
    free(Alpha_to);
    free(Index_of);
    return nb_errors;
}

#endif /* (CONFIG_COMMANDS & CFG_CMD_DOC) */