rslib.c

Error Correcting Code algorithms, for use whit E

/*
    ecc Version 1.2  by Paul Flaherty ([e-mail])
    Copyright (C) 1993 Free Software Foundation, Inc.

    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, 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., 675 Mass Ave, Cambridge, MA 02139, USA.
*/


/* rslib.c
	Library of Reed - Solomon Routines

	This file contains the actual routines to implement a Reed - Solomon
	(255,249,7) code.  The encoder uses a feedback shift register
	generator, which systematically encodes 249 bytes into a 255 byte
	block.  The decoder is a classic Peterson algorithm.
*/

#include "ecc.h"


/* Reed - Solomon Encoder.  The Encoder uses a shift register algorithm,
   as detailed in _Applied Modern Algebra_ by Dornhoff and Hohn (p.446).
   Note that the message is reversed in the code array; this was done to
   allow for (emergency) recovery of the message directly from the
   data stream.
*/

rsencode (m, c)

     unsigned char m[249], c[255];

{

  unsigned char r[6], rtmp;

  int i, j;

  for (i = 0; i < 6; i++)
    r[i] = 0;

  for (i = 0; i < 249; i++)
    {
      c[254 - i] = m[i];
      rtmp = gfadd (m[i], r[5]);
      for (j = 5; j > 0; j--)
	{
	  r[j] = gfadd (gfmul (rtmp, g[j]), r[j - 1]);
	}
      r[0] = gfmul (rtmp, g[0]);
    }
  for (i = 0; i < 6; i++)
    {
      c[i] = r[i];
    }
}


/* Polynomial Evaluator, used to determine the Syndrome Vector.  This is
   relatively straightforward, and there are faster algorithms.
*/

unsigned char
evalpoly (p, x)

     unsigned char p[255], x;

{

  unsigned char y;
  int i;
  y = 0;

  for (i = 0; i < 255; i++)
    {
      y = gfadd (y, gfmul (p[i], gfexp (x, i)));
    }
  return (y);

}


/* Determine the Syndrome Vector.  Note that in s[0] we return the OR of
   all of the syndromes; this allows for an easy check for the no - error
   condition.
*/

syndrome (c, s)

     unsigned char c[255], s[7];
{

  extern unsigned char e2v[256];
  int i;
  s[0] = 0;
  for (i = 1; i < 7; i++)
    {
      s[i] = evalpoly (c, e2v[i]);
      s[0] = s[0] | s[i];
    }

}


/* Determine the number of errors in a block.  Since we have to find the
   determinant of the S[] matrix in order to determine singularity, we
   also return the determinant to be used by the Cramer's Rule correction
   algorithm.
*/

errnum (s, det, errs)

     unsigned char s[7], *det;
     int *errs;

{


  *det = gfmul (s[2], gfmul (s[4], s[6]));
  *det = gfadd (*det, gfmul (s[2], gfmul (s[5], s[5])));
  *det = gfadd (*det, gfmul (s[6], gfmul (s[3], s[3])));
  *det = gfadd (*det, gfmul (s[4], gfmul (s[4], s[4])));
  *errs = 3;

  if (*det != 0)
    return;

  *det = gfadd (gfmul (s[2], s[4]), gfexp (s[3], 2));
  *errs = 2;
  if (*det != 0)
    return;

  *det = s[1];
  *errs = 1;
  if (*det != 0)
    return;

  *errs = 4;

}


/* Full impementation of the three error correcting Peterson decoder.  For
   t<6, it is faster than Massey - Berlekamp.  It is also somewhat more
   intuitive.
*/

rsdecode (code, mesg, errcode)

     unsigned char code[255], mesg[249];
     int *errcode;
{

  extern unsigned char v2e[256];
  unsigned char syn[7], deter, z[4], e0, e1, e2, n0, n1, n2, w0, w1, w2,
    x0, x[3];
  int i, sols;

  *errcode = 0;

  /* First, get the message out of the code, so that even if we can't correct
	   it, we return an estimate.
	*/

  for (i = 0; i < 249; i++)
    mesg[i] = code[254 - i];

  syndrome (code, syn);

  if (syn[0] == 0)
    return;

  /* We now know we have at least one error.  If there are no errors detected,
	   we assume that something funny is going on, and so return with errcode 4,
	   else pass the number of errors back via errcode.
	*/

  errnum (syn, &deter, errcode);

  if (*errcode == 4)
    return;

  /* Having obtained the syndrome, the number of errors, and the determinant,
	   we now proceed to correct the block.  If we do not find exactly the
	   number of solutions equal to the number of errors, we have exceeded our
	   error capacity, and return with the block uncorrected, and errcode 4.
	*/

  switch (*errcode)
    {

    case 1:

      x0 = gfmul (syn[2], gfinv (syn[1]));
      w0 = gfmul (gfexp (syn[1], 2), gfinv (syn[2]));
      if (v2e[x0] > 5)
	mesg[254 - v2e[x0]] = gfadd (mesg[254 - v2e[x0]], w0);
      return;

    case 2:

      z[0] = gfmul (gfadd (gfmul (syn[1], syn[3]), gfexp (syn[2], 2)), gfinv (deter));
      z[1] = gfmul (gfadd (gfmul (syn[2], syn[3]), gfmul (syn[1], syn[4])), gfinv (deter));
      z[2] = 1;
      z[3] = 0;

      polysolve (z, x, &sols);
      if (sols != 2)
	{
	  *errcode = 4;
	  return;
	}

      w0 = gfmul (z[0], syn[1]);
      w1 = gfadd (gfmul (z[0], syn[2]), gfmul (z[1], syn[1]));
      n0 = 254 - v2e[gfinv (x[0])];
      n1 = 254 - v2e[gfinv (x[1])];
      e0 = gfmul (gfadd (w0, gfmul (w1, x[0])), gfinv (z[1]));
      e1 = gfmul (gfadd (w0, gfmul (w1, x[1])), gfinv (z[1]));

      if (n0 < 249)
	mesg[n0] = gfadd (mesg[n0], e0);
      if (n1 < 249)
	mesg[n1] = gfadd (mesg[n1], e1);
      return;

    case 3:

      z[3] = 1;
      z[2] = gfmul (syn[1], gfmul (syn[4], syn[6]));
      z[2] = gfadd (z[2], gfmul (syn[1], gfmul (syn[5], syn[5])));
      z[2] = gfadd (z[2], gfmul (syn[5], gfmul (syn[3], syn[3])));
      z[2] = gfadd (z[2], gfmul (syn[3], gfmul (syn[4], syn[4])));
      z[2] = gfadd (z[2], gfmul (syn[2], gfmul (syn[5], syn[4])));
      z[2] = gfadd (z[2], gfmul (syn[2], gfmul (syn[3], syn[6])));
      z[2] = gfmul (z[2], gfinv (deter));

      z[1] = gfmul (syn[1], gfmul (syn[3], syn[6]));
      z[1] = gfadd (z[1], gfmul (syn[1], gfmul (syn[5], syn[4])));
      z[1] = gfadd (z[1], gfmul (syn[4], gfmul (syn[3], syn[3])));
      z[1] = gfadd (z[1], gfmul (syn[2], gfmul (syn[4], syn[4])));
      z[1] = gfadd (z[1], gfmul (syn[2], gfmul (syn[3], syn[5])));
      z[1] = gfadd (z[1], gfmul (syn[2], gfmul (syn[2], syn[6])));
      z[1] = gfmul (z[1], gfinv (deter));

      z[0] = gfmul (syn[2], gfmul (syn[3], syn[4]));
      z[0] = gfadd (z[0], gfmul (syn[3], gfmul (syn[2], syn[4])));
      z[0] = gfadd (z[0], gfmul (syn[3], gfmul (syn[5], syn[1])));
      z[0] = gfadd (z[0], gfmul (syn[4], gfmul (syn[4], syn[1])));
      z[0] = gfadd (z[0], gfmul (syn[3], gfmul (syn[3], syn[3])));
      z[0] = gfadd (z[0], gfmul (syn[2], gfmul (syn[2], syn[5])));
      z[0] = gfmul (z[0], gfinv (deter));

      polysolve (z, x, &sols);
      if (sols != 3)
	{
	  *errcode = 4;
	  return;
	}

      w0 = gfmul (z[0], syn[1]);
      w1 = gfadd (gfmul (z[0], syn[2]), gfmul (z[1], syn[1]));
      w2 = gfadd (gfmul (z[0], syn[3]), gfadd (gfmul (z[1], syn[2]), gfmul (z[2], syn[1])));

      n0 = 254 - v2e[gfinv (x[0])];
      n1 = 254 - v2e[gfinv (x[1])];
      n2 = 254 - v2e[gfinv (x[2])];

      e0 = gfadd (w0, gfadd (gfmul (w1, x[0]), gfmul (w2, gfexp (x[0], 2))));
      e0 = gfmul (e0, gfinv (gfadd (z[1], gfexp (x[0], 2))));
      e1 = gfadd (w0, gfadd (gfmul (w1, x[1]), gfmul (w2, gfexp (x[1], 2))));
      e1 = gfmul (e1, gfinv (gfadd (z[1], gfexp (x[1], 2))));
      e2 = gfadd (w0, gfadd (gfmul (w1, x[2]), gfmul (w2, gfexp (x[2], 2))));
      e2 = gfmul (e2, gfinv (gfadd (z[1], gfexp (x[2], 2))));

      if (n0 < 249)
	mesg[n0] = gfadd (mesg[n0], e0);
      if (n1 < 249)
	mesg[n1] = gfadd (mesg[n1], e1);
      if (n2 < 249)
	mesg[n2] = gfadd (mesg[n2], e2);

      return;

    default:

      *errcode = 4;
      return;

    }

}


/* Polynomial Solver.  Simple exhaustive search, as solving polynomials is
   generally NP - Complete anyway.
*/

polysolve (polynom, roots, numsol)

     unsigned char polynom[4], roots[3];
     int *numsol;

{
  extern unsigned char e2v[256];
  int i, j;
  unsigned char y;

  *numsol = 0;

  for (i = 0; i < 255; i++)
    {
      y = 0;
      for (j = 0; j < 4; j++)
	y = gfadd (y, gfmul (polynom[j], gfexp (e2v[i], j)));
      if (y == 0)
	{
	  roots[*numsol] = e2v[i];
	  *numsol = *numsol + 1;
	}
    }
}