flight/libraries/rscode/rs.c

   1 /*
   2  * Reed Solomon Encoder/Decoder
   3  *
   4  * Copyright Henry Minsky (hqm@alum.mit.edu) 1991-2009
   5  *
   6  * This software library is licensed under terms of the GNU GENERAL
   7  * PUBLIC LICENSE
   8  *
   9  * RSCODE is free software: you can redistribute it and/or modify
  10  * it under the terms of the GNU General Public License as published by
  11  * the Free Software Foundation, either version 3 of the License, or
  12  * (at your option) any later version.
  13  *
  14  * RSCODE is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  * GNU General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License
  20  * along with Rscode.  If not, see <http://www.gnu.org/licenses/>.
  21
  22  * Commercial licensing is available under a separate license, please
  23  * contact author for details.
  24  *
  25  * Source code is available at http://rscode.sourceforge.net
  26  */
  27
  28 #include <stdio.h>
  29 #include <ctype.h>
  30 #include "ecc.h"
  31
  32 /* Encoder parity bytes */
  33 int pBytes[MAXDEG];
  34
  35 /* Decoder syndrome bytes */
  36 int synBytes[MAXDEG];
  37
  38 /* generator polynomial */
  39 int genPoly[MAXDEG*2];
  40
  41 //int DEBUG = FALSE;
  42
  43 static void
  44 compute_genpoly (int nbytes, int genpoly[]);
  45
  46 /* Initialize lookup tables, polynomials, etc. */
  47 void
  48 initialize_ecc ()
  49 {
  50   /* Initialize the galois field arithmetic tables */
  51     init_galois_tables();
  52
  53     /* Compute the encoder generator polynomial */
  54     compute_genpoly(RS_ECC_NPARITY, genPoly);
  55 }
  56
  57 void
  58 zero_fill_from (unsigned char buf[], int from, int to)
  59 {
  60   int i;
  61   for (i = from; i < to; i++) buf[i] = 0;
  62 }
  63
  64 /* debugging routines */
  65 void
  66 print_parity (void)
  67 {
  68 #ifdef NEVER
  69   int i;
  70   printf("Parity Bytes: ");
  71   for (i = 0; i < RS_ECC_NPARITY; i++)
  72     printf("[%d]:%x, ",i,pBytes[i]);
  73   printf("\n");
  74 #endif
  75 }
  76
  77
  78 void
  79 print_syndrome (void)
  80 {
  81 #ifdef NEVER
  82   int i;
  83   printf("Syndrome Bytes: ");
  84   for (i = 0; i < RS_ECC_NPARITY; i++)
  85     printf("[%d]:%x, ",i,synBytes[i]);
  86   printf("\n");
  87 #endif
  88 }
  89
  90 /* Append the parity bytes onto the end of the message */
  91 void
  92 build_codeword (unsigned char msg[], int nbytes, unsigned char dst[])
  93 {
  94   int i;
  95
  96   for (i = 0; i < nbytes; i++) dst[i] = msg[i];
  97
  98   for (i = 0; i < RS_ECC_NPARITY; i++) {
  99     dst[i+nbytes] = pBytes[RS_ECC_NPARITY-1-i];
 100   }
 101 }
 102
 103 /**********************************************************
 104  * Reed Solomon Decoder
 105  *
 106  * Computes the syndrome of a codeword. Puts the results
 107  * into the synBytes[] array.
 108  */
 109
 110 void
 111 decode_data(unsigned char data[], int nbytes)
 112 {
 113   int i, j, sum;
 114   for (j = 0; j < RS_ECC_NPARITY;  j++) {
 115     sum = 0;
 116     for (i = 0; i < nbytes; i++) {
 117       sum = data[i] ^ gmult(gexp[j+1], sum);
 118     }
 119     synBytes[j]  = sum;
 120   }
 121 }
 122
 123
 124 /* Check if the syndrome is zero */
 125 int
 126 check_syndrome (void)
 127 {
 128  int i, nz = 0;
 129  for (i =0 ; i < RS_ECC_NPARITY; i++) {
 130   if (synBytes[i] != 0) {
 131       nz = 1;
 132       break;
 133   }
 134  }
 135  return nz;
 136 }
 137
 138
 139 void
 140 debug_check_syndrome (void)
 141 {
 142 #ifdef NEVER
 143   int i;
 144
 145   for (i = 0; i < 3; i++) {
 146     printf(" inv log S[%d]/S[%d] = %d\n", i, i+1,
 147            glog[gmult(synBytes[i], ginv(synBytes[i+1]))]);
 148   }
 149 #endif
 150 }
 151
 152
 153 /* Create a generator polynomial for an n byte RS code.
 154  * The coefficients are returned in the genPoly arg.
 155  * Make sure that the genPoly array which is passed in is
 156  * at least n+1 bytes long.
 157  */
 158
 159 static void
 160 compute_genpoly (int nbytes, int genpoly[])
 161 {
 162   int i, tp[MAXDEG], tp1[MAXDEG];
 163
 164   /* multiply (x + a^n) for n = 1 to nbytes */
 165
 166   zero_poly(tp1);
 167   tp1[0] = 1;
 168
 169   for (i = 1; i <= nbytes; i++) {
 170     zero_poly(tp);
 171     tp[0] = gexp[i];            /* set up x+a^n */
 172     tp[1] = 1;
 173
 174     mult_polys(genpoly, tp, tp1);
 175     copy_poly(tp1, genpoly);
 176   }
 177 }
 178
 179 /* Simulate a LFSR with generator polynomial for n byte RS code.
 180  * Pass in a pointer to the data array, and amount of data.
 181  *
 182  * The parity bytes are deposited into pBytes[], and the whole message
 183  * and parity are copied to dest to make a codeword.
 184  *
 185  */
 186
 187 void
 188 encode_data (unsigned char msg[], int nbytes, unsigned char dst[])
 189 {
 190   int i, LFSR[RS_ECC_NPARITY+1],dbyte, j;
 191
 192   for(i=0; i < RS_ECC_NPARITY+1; i++) LFSR[i]=0;
 193
 194   for (i = 0; i < nbytes; i++) {
 195     dbyte = msg[i] ^ LFSR[RS_ECC_NPARITY-1];
 196     for (j = RS_ECC_NPARITY-1; j > 0; j--) {
 197       LFSR[j] = LFSR[j-1] ^ gmult(genPoly[j], dbyte);
 198     }
 199     LFSR[0] = gmult(genPoly[0], dbyte);
 200   }
 201
 202   for (i = 0; i < RS_ECC_NPARITY; i++)
 203     pBytes[i] = LFSR[i];
 204
 205   build_codeword(msg, nbytes, dst);
 206 }
 207