reedsol.c

truefs for vxworks, make fs on flash or rom

/* HOOK. Fixed comments; otherwise impossible to compile */
/*
 * $Log:   P:/user/amir/lite/vcs/reedsol.c_v  $
 * 
 *    Rev 1.8   10 Sep 1997 16:29:44   danig
 * Got rid of generic names
 * 
 *    Rev 1.7   19 Aug 1997 20:08:16   danig
 * Andray's changes
 *
 *    Rev 1.6   07 Jul 1997 15:22:36   amirban
 * Ver 2.0
 *
 *    Rev 1.5   29 May 1997 15:04:52   amirban
 * More comments
 *
 *    Rev 1.4   27 May 1997 11:10:12   danig
 * Changed far to FAR1 & log() to flog()
 *
 *    Rev 1.3   25 May 1997 19:16:38   danig
 * Comments
 *
 *    Rev 1.2   25 May 1997 16:42:34   amirban
 * Up-to-date
 *
 *    Rev 1.1   18 May 1997 17:56:36   danig
 * Changed NO_ERROR to NO_EDC_ERROR
 *
 *    Rev 1.0   08 Apr 1997 18:35:32   danig
 * Initial revision.
 */

/************************************************************************/
/*                                                                      */
/*		FAT-FTL Lite Software Development Kit			*/
/*		Copyright (C) M-Systems Ltd. 1995-1997			*/
/*									*/
/************************************************************************/


#include "reedsol.h"

#define T 2			 /* Number of recoverable errors */
#define SYND_LEN (T*2)           /* length of syndrom vector */
#define K512  (((512+1)*8+6)/10) /* number of inf symbols for record
				    of 512 bytes (K512=411) */
#define N512  (K512 + SYND_LEN)  /* code word length for record of 512 bytes */
#define INIT_DEG 510
#define MOD 1023

static short  gfi(short val);
static short  gfmul( short f, short s );
static short  gfdiv( short f, short s );
static short  flog(short val);
static short  alog(short val);

/*------------------------------------------------------------------------------*/
/* Function Name: RTLeightToTen                                                 */
/* Purpose......: convert an array of five 8-bit values into an array of        */
/*                four 10-bit values, from right to left.                       */
/* Returns......: Nothing                                                       */
/*------------------------------------------------------------------------------*/
static void RTLeightToTen(char *reg8, unsigned short reg10[])
{
	reg10[0] =  (reg8[0] & 0xFF)       | ((reg8[1] & 0x03) << 8);
	reg10[1] = ((reg8[1] & 0xFC) >> 2) | ((reg8[2] & 0x0F) << 6);
	reg10[2] = ((reg8[2] & 0xF0) >> 4) | ((reg8[3] & 0x3F) << 4);
	reg10[3] = ((reg8[3] & 0xC0) >> 6) | ((reg8[4] & 0xFF) << 2);
}


#ifdef EDC_IN_SOFTWARE

/*----------------------------------------------------------------------------*/
/* Function Name: RTLtenToEight                                               */
/* Purpose......: convert an array of four 10-bit values into an array of     */
/*                five 8-bit values, from right to left.                      */
/* Returns......: Nothing                                                     */
/*----------------------------------------------------------------------------*/
static void RTLtenToEight(unsigned short reg10[], char reg8[])
{
	reg8[0] =                                reg10[0] & 0x00FF;
	reg8[1] = ((reg10[0] & 0x0300) >> 8) | ((reg10[1] & 0x003F) << 2);
	reg8[2] = ((reg10[1] & 0x03C0) >> 6) | ((reg10[2] & 0x000F) << 4);
	reg8[3] = ((reg10[2] & 0x03F0) >> 4) | ((reg10[3] & 0x0003) << 6);
	reg8[4] =  (reg10[3] & 0x03FC) >> 2;
}


/*----------------------------------------------------------------------------*/
/* Function Name: LTReightToTen                                               */
/* Purpose......: convert an array of five 8-bit values into an array of      */
/*                four 10-bit values, from left to right.                     */
/* Returns......: Nothing                                                     */
/*----------------------------------------------------------------------------*/
static void LTReightToTen(char reg8[], unsigned short reg10[])
{
	reg10[0] = ((reg8[0] & 0xFF) << 2) | ((reg8[1] & 0xC0) >> 6);
	reg10[1] = ((reg8[1] & 0x3F) << 4) | ((reg8[2] & 0xF0) >> 4);
	reg10[2] = ((reg8[2] & 0x0F) << 6) | ((reg8[3] & 0xFC) >> 2);
	reg10[3] = ((reg8[3] & 0x03) << 8) |  (reg8[4] & 0xFF);
}

/*----------------------------------------------------------------------------*/
/* Function Name: LTRtenToEight                                               */
/* Purpose......: convert an array of four 10-bit values into an array of     */
/*                five 8-bit values, from left to right.                      */
/* Returns......: Nothing                                                     */
/*----------------------------------------------------------------------------*/
static void LTRtenToEight(unsigned short reg10[], char reg8[])
{
	reg8[0]   =                             (reg10[0] & 0x03FC) >> 2;
	reg8[1] = ((reg10[0] & 0x0003) << 6) | ((reg10[1] & 0x03F0) >> 4);
	reg8[2] = ((reg10[1] & 0x000F) << 4) | ((reg10[2] & 0x03C0) >> 6);
	reg8[3] = ((reg10[2] & 0x003F) << 2) | ((reg10[3] & 0x0300) >> 8);
	reg8[4] =  (reg10[3] & 0x00FF);
}


/*----------------------------------------------------------------------------*/
/* Function Name: LTRarrayEightToTen                                          */
/* Purpose......: convert an array of 512 8-bit values into an array of       */
/*                415 10-bit values (from left to right). The 6 msb on the    */
/*                first 10-bit value are zero, an so are the 8 lsb on the     */
/*                411'th 10-bit value. The last four 10-bit values are zeroed.*/
/* Returns......: Nothing                                                     */
/*----------------------------------------------------------------------------*/
static void LTRarrayEightToTen(char FAR1 *reg8, unsigned short *reg10)
{
  short i8;                               /* Index in the 8-bit array */
  short i10;                              /* Index in the 10-bit array */
  short j;

					  /* Create the first three 10-bit values */
					  /* (the six msb on the first 10-bit */
					  /* value are zeroes): */
	reg10[0] =                            (reg8[0] & 0xF0) >> 4;
	reg10[1] = ((reg8[0] & 0x0F) << 6) | ((reg8[1] & 0xFC) >> 2);
	reg10[2] = ((reg8[1] & 0x03) << 8) |  (reg8[2] & 0xFF);
					  /* Create the next 101 quadruples of */
					  /* 10-bit values: */
	for(i10=3, i8=3; i10 < (4*101)+3; i10+=4, i8+=5)
	{
		reg10[i10]   = ((reg8[i8]   & 0xFF) << 2) | ((reg8[i8+1] & 0xC0) >> 6);
		reg10[i10+1] = ((reg8[i8+1] & 0x3F) << 4) | ((reg8[i8+2] & 0xF0) >> 4);
		reg10[i10+2] = ((reg8[i8+2] & 0x0F) << 6) | ((reg8[i8+3] & 0xFC) >> 2);
		reg10[i10+3] = ((reg8[i8+3] & 0x03) << 8) |  (reg8[i8+4] & 0xFF);
	}
					  /* Create the last quadruple of 10-bit */
					  /* values. The the 8 lsb of the */
					  /* last 10-bit value are zeroed: */
	reg10[i10]   = ((reg8[i8]   & 0xFF) << 2) | ((reg8[i8+1] & 0xC0) >> 6);
	reg10[i10+1] = ((reg8[i8+1] & 0x3F) << 4) | ((reg8[i8+2] & 0xF0) >> 4);
	reg10[i10+2] = ((reg8[i8+2] & 0x0F) << 6) | ((reg8[i8+3] & 0xFC) >> 2);
	reg10[i10+3] =  (reg8[i8+3] & 0x03) << 8;
					/* Zero the last four 10-bit values: */
  i10+=4;
  for(j=i10; j<(i10+4); j++)
    reg10[j] = 0;
}


/*----------------------------------------------------------------------------*/
/* Function Name: resolveParity                                               */
/* Purpose......: find the parity byte for an array of bytes.                 */
/* Returns......: The parity byte                                             */
/*----------------------------------------------------------------------------*/
static char resolveParity(char FAR1 *block, short len)
{
  char par=0;
  short i;

  for(i=0; i<len; i++)
    par ^= block[i];

  return par;
}

#endif   /* EDC_IN_SOFTWARE */


/*----------------------------------------------------------------------------*/
static void unpack( short word, short length, short vector[] )
/*                                                                            */
/*   Function unpacks word into vector                                        */
/*                                                                            */
/*   Parameters:                                                              */
/*     word   - word to be unpacked                                           */
/*     vector - array to be filled                                            */
/*     length - number of bits in word                                        */

{
  short i, *ptr;

  ptr = vector + length - 1;
  for( i = 0; i < length; i++ )
  {
    *ptr-- = word & 1;
    word >>= 1;
  }
}


/*----------------------------------------------------------------------------*/
static short pack( short *vector, short length )
/*                                                                            */
/*   Function packs vector into word                                          */
/*                                                                            */
/*   Parameters:                                                              */
/*     vector - array to be packed                                            */
/*     length - number of bits in word                                        */

{
  short tmp, i;

  vector += length - 1;
  tmp = 0;
  i = 1;
  while( length-- > 0 )
  {
    if( *vector-- )
      tmp |= i;
    i <<= 1;
  }
  return( tmp );
}


/*----------------------------------------------------------------------------*/
static short gfi( short val)		/* GF inverse */
{
  return alog(MOD-flog(val));
}


/*----------------------------------------------------------------------------*/
static short gfmul( short f, short s ) /* GF multiplication */
{
  short i;
  if( f==0 || s==0 )
     return 0;
  else
  {
    i = flog(f) + flog(s);
    if( i > MOD ) i -= MOD;
    return( alog(i) );
  }
}


/*----------------------------------------------------------------------------*/
static short gfdiv( short f, short s ) /* GF division */
{
  return gfmul(f,gfi(s));
}


#ifdef EDC_IN_SOFTWARE

/*----------------------------------------------------------------------------*/
static void register_division( short reg[], short input[], short len )
/*                                                                            */
/*  Function emulates hardware division by generator polynom                  */
/*                                                                            */
/*  Parameters:                                                               */
/*    reg   - hardware register with feedback                                 */
/*    input - input sequence ( devidend )                                     */
/*    len   - number of steps for division procedure                          */

{
  short i, j, feedback, tmp0, tmp1, tmp4;

	for( i = 0; i < SYND_LEN; i++ )  reg[i] = 0x03ff;

	for( i = 0; i < len; i++ )
	{
		tmp4 = reg[0] ^ input[i];
		if( tmp4 == 0 )
		{
			reg[0] = reg[1];
			reg[1] = reg[2];
			reg[2] = reg[3];
			reg[3] = 0;
		}
		else
		{
      feedback = flog(tmp4);
			if( (j = feedback + 741) >= MOD )
	      j -= MOD;
      tmp0 = alog(j);

			if( (j = feedback +  85) >= MOD )
	j -= MOD;
      tmp1 = alog(j);


			reg[0] = reg[1] ^ tmp0;
			reg[1] = reg[2] ^ tmp1;
			reg[2] = reg[3] ^ tmp0;
			reg[3] = tmp4;
		}
	}
}

#endif  /* EDC_IN_SOFTWARE */


/*----------------------------------------------------------------------------*/
static void residue_to_syndrom( short reg[], short realsynd[] )
{
   short i,l,alpha,x,s,x4;
   short deg,deg4;


   for(i=0,deg=INIT_DEG;i<SYND_LEN;i++,deg++)
   {
      s = reg[0];
      alpha = x = alog(deg);
      deg4 = deg+deg;
      if( deg4 >= MOD ) deg4 -= MOD;
      deg4 += deg4;
      if( deg4 >= MOD ) deg4 -= MOD;
      x4 = alog(deg4);

      for(l=1;l<SYND_LEN;l++)
      {
	s ^= gfmul( reg[l], x );
	x  = gfmul( alpha, x );
      }

      realsynd[i] = gfdiv( s, x4 );
   }
}


/*----------------------------------------------------------------------------*/
static short alog(short i)
{
  short j=0, val=1;

  for( ; j < i ; j++ )
  {
    val <<= 1 ;

    if ( val > 0x3FF )
    {
      if ( val & 8 )   val -= (0x400+7);
      else             val -= (0x400-9);
    }
  }

  return val ;
}


static short flog(short val)
{
  short j, val1;

  if (val == 0)
    return (short)0xFFFF;

  j=0;
  val1=1;

  for( ; j <= MOD ; j++ )
  {
    if (val1 == val)
      return j;

    val1 <<= 1 ;

    if ( val1 > 0x3FF )
    {
      if ( val1 & 8 )   val1 -= (0x400+7);
      else              val1 -= (0x400-9);
    }

  }

  return 0;
}


#ifdef EDC_IN_SOFTWARE

static short packed_symbol[415];/* RS code word packed bit in bit */

/*----------------------------------------------------------------------------*/
/* Function Name: encodeEDC                                                   */
/* Purpose......: Encode 512 bytes of data, given in block[].                 */
/*                Upon returning code[] will contain the EDC code as          */
/*                5 bytes, and one parity byte.                               */
/* Returns......: Nothing                                                     */
/*----------------------------------------------------------------------------*/
static void encodeEDC(char FAR1 *block, char code[6])
{
  short reg[SYND_LEN];         /* register for main division procedure */
					/* Convert block[] into a 10-bit values */
					/* array: */