git.sur5r.net Git - iec16022/blob - reedsol.c

   1 /**
   2  *
   3  * This is a simple Reed-Solomon encoder
   4  * (C) Cliff Hones 2004
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
  19  *
  20  */
  21
  22
  23 // It is not written with high efficiency in mind, so is probably
  24 // not suitable for real-time encoding.  The aim was to keep it
  25 // simple, general and clear.
  26 //
  27 // <Some notes on the theory and implementation need to be added here>
  28
  29 // Usage:
  30 // First call rs_init_gf(poly) to set up the Galois Field parameters.
  31 // Then  call rs_init_code(size, index) to set the encoding size
  32 // Then  call rs_encode(datasize, data, out) to encode the data.
  33 //
  34 // These can be called repeatedly as required - but note that
  35 // rs_init_code must be called following any rs_init_gf call.
  36 //
  37 // If the parameters are fixed, some of the statics below can be
  38 // replaced with constants in the obvious way, and additionally
  39 // malloc/free can be avoided by using static arrays of a suitable
  40 // size.
  41
  42 #include <stdio.h>              // only needed for debug (main)
  43 #include <stdlib.h>             // only needed for malloc/free
  44
  45 static int gfpoly;
  46 static int symsize;             // in bits
  47 static int logmod;              // 2**symsize - 1
  48 static int rlen;
  49
  50 static int *log = NULL,
  51    *alog = NULL,
  52    *rspoly = NULL;
  53
  54 // rs_init_gf(poly) initialises the parameters for the Galois Field.
  55 // The symbol size is determined from the highest bit set in poly
  56 // This implementation will support sizes up to 30 bits (though that
  57 // will result in very large log/antilog tables) - bit sizes of
  58 // 8 or 4 are typical
  59 //
  60 // The poly is the bit pattern representing the GF characteristic
  61 // polynomial.  e.g. for ECC200 (8-bit symbols) the polynomial is
  62 // a**8 + a**5 + a**3 + a**2 + 1, which translates to 0x12d.
  63
  64 void
  65 rs_init_gf (int poly)
  66 {
  67    int m,
  68      b,
  69      p,
  70      v;
  71
  72    // Return storage from previous setup
  73    if (log)
  74    {
  75       free (log);
  76       free (alog);
  77       free (rspoly);
  78       rspoly = NULL;
  79    }
  80    // Find the top bit, and hence the symbol size
  81    for (b = 1, m = 0; b <= poly; b <<= 1)
  82       m++;
  83    b >>= 1;
  84    m--;
  85    gfpoly = poly;
  86    symsize = m;
  87
  88    // Calculate the log/alog tables
  89    logmod = (1 << m) - 1;
  90    log = (int *) malloc (sizeof (int) * (logmod + 1));
  91    alog = (int *) malloc (sizeof (int) * logmod);
  92
  93    for (p = 1, v = 0; v < logmod; v++)
  94    {
  95       alog[v] = p;
  96       log[p] = v;
  97       p <<= 1;
  98       if (p & b)
  99          p ^= poly;
 100    }
 101 }
 102
 103 // rs_init_code(nsym, index) initialises the Reed-Solomon encoder
 104 // nsym is the number of symbols to be generated (to be appended
 105 // to the input data).  index is usually 1 - it is the index of
 106 // the constant in the first term (i) of the RS generator polynomial:
 107 // (x + 2**i)*(x + 2**(i+1))*...   [nsym terms]
 108 // For ECC200, index is 1.
 109
 110 void
 111 rs_init_code (int nsym, int index)
 112 {
 113    int i,
 114      k;
 115
 116    if (rspoly)
 117       free (rspoly);
 118    rspoly = (int *) malloc (sizeof (int) * (nsym + 1));
 119
 120    rlen = nsym;
 121
 122    rspoly[0] = 1;
 123    for (i = 1; i <= nsym; i++)
 124    {
 125       rspoly[i] = 1;
 126       for (k = i - 1; k > 0; k--)
 127       {
 128          if (rspoly[k])
 129             rspoly[k] = alog[(log[rspoly[k]] + index) % logmod];
 130          rspoly[k] ^= rspoly[k - 1];
 131       }
 132       rspoly[0] = alog[(log[rspoly[0]] + index) % logmod];
 133       index++;
 134    }
 135 }
 136
 137 // Note that the following uses byte arrays, so is only suitable for
 138 // symbol sizes up to 8 bits.  Just change the data type of data and res
 139 // to unsigned int * for larger symbols.
 140
 141 void
 142 rs_encode (int len, unsigned char *data, unsigned char *res)
 143 {
 144    int i,
 145      k,
 146      m;
 147    for (i = 0; i < rlen; i++)
 148       res[i] = 0;
 149    for (i = 0; i < len; i++)
 150    {
 151       m = res[rlen - 1] ^ data[i];
 152       for (k = rlen - 1; k > 0; k--)
 153       {
 154          if (m && rspoly[k])
 155             res[k] = res[k - 1] ^ alog[(log[m] + log[rspoly[k]]) % logmod];
 156          else
 157             res[k] = res[k - 1];
 158       }
 159       if (m && rspoly[0])
 160          res[0] = alog[(log[m] + log[rspoly[0]]) % logmod];
 161       else
 162          res[0] = 0;
 163    }
 164 }
 165
 166 #ifndef LIB
 167 // The following tests the routines with the ISO/IEC 16022 Annexe R data
 168 int
 169 main (void)
 170 {
 171    register int i;
 172
 173    unsigned char data[9] = { 142, 164, 186 };
 174    unsigned char out[5];
 175
 176    rs_init_gf (0x12d);
 177    rs_init_code (5, 1);
 178
 179    rs_encode (3, data, out);
 180
 181    printf ("Result of Annexe R encoding:\n");
 182    for (i = 4; i >= 0; i--)
 183       printf ("  %d\n", out[i]);
 184
 185    return 0;
 186 }
 187 #endif