please dont rip this site
/*
    ecc Version 1.2  by Paul Flaherty (paulf at stanford.edu)
    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"

/* Also uses gflib.c */

/* 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;
	}
    }
}

file: /Techref/method/error/rs-255-248-7-pf-1993/rslib_c.htm, 70KB, , updated: 2000/5/10 12:16, local time: 2024/12/23 00:35,
TOP NEW HELP FIND: 
18.222.161.119:LOG IN

 ©2024 These pages are served without commercial sponsorship. (No popup ads, etc...).Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE. Questions?
Please DO link to this page! Digg it! / MAKE!

<A HREF="http://massmind.org/Techref/method/error/rs-255-248-7-pf-1993/rslib_c.htm"> Colorized Source Code</A>

After you find an appropriate page, you are invited to your to this massmind site! (posts will be visible only to you before review) Just type a nice message (short messages are blocked as spam) in the box and press the Post button. (HTML welcomed, but not the <A tag: Instead, use the link box to link to another page. A tutorial is available Members can login to post directly, become page editors, and be credited for their posts.


Link? Put it here: 
if you want a response, please enter your email address: 
Attn spammers: All posts are reviewed before being made visible to anyone other than the poster.
Did you find what you needed?

 

Welcome to massmind.org!

 

Welcome to massmind.org!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  .