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 rs_init_gf (int poly)
  65 {
  66    int m,
  67      b,
  68      p,
  69      v;
  70
  71    // Return storage from previous setup
  72    if (log)
  73    {
  74       free (log);
  75       free (alog);
  76       free (rspoly);
  77       rspoly = NULL;
  78    }
  79    // Find the top bit, and hence the symbol size
  80    for (b = 1, m = 0; b <= poly; b <<= 1)
  81       m++;
  82    b >>= 1;
  83    m--;
  84    gfpoly = poly;
  85    symsize = m;
  86
  87    // Calculate the log/alog tables
  88    logmod = (1 << m) - 1;
  89    log = (int *) malloc (sizeof (int) * (logmod + 1));
  90    alog = (int *) malloc (sizeof (int) * logmod);
  91
  92    for (p = 1, v = 0; v < logmod; v++)
  93    {
  94       alog[v] = p;
  95       log[p] = v;
  96       p <<= 1;
  97       if (p & b)
  98          p ^= poly;
  99    }
 100 }
 101
 102 // rs_init_code(nsym, index) initialises the Reed-Solomon encoder
 103 // nsym is the number of symbols to be generated (to be appended
 104 // to the input data).  index is usually 1 - it is the index of
 105 // the constant in the first term (i) of the RS generator polynomial:
 106 // (x + 2**i)*(x + 2**(i+1))*...   [nsym terms]
 107 // For ECC200, index is 1.
 108
 109 void rs_init_code (int nsym, int index)
 110 {
 111    int i,
 112      k;
 113
 114    if (rspoly)
 115       free (rspoly);
 116    rspoly = (int *) malloc (sizeof (int) * (nsym + 1));
 117
 118    rlen = nsym;
 119
 120    rspoly[0] = 1;
 121    for (i = 1; i <= nsym; i++)
 122    {
 123       rspoly[i] = 1;
 124       for (k = i - 1; k > 0; k--)
 125       {
 126          if (rspoly[k])
 127             rspoly[k] = alog[(log[rspoly[k]] + index) % logmod];
 128          rspoly[k] ^= rspoly[k - 1];
 129       }
 130       rspoly[0] = alog[(log[rspoly[0]] + index) % logmod];
 131       index++;
 132    }
 133 }
 134
 135 // Note that the following uses byte arrays, so is only suitable for
 136 // symbol sizes up to 8 bits.  Just change the data type of data and res
 137 // to unsigned int * for larger symbols.
 138
 139 void rs_encode (int len, unsigned char *data, unsigned char *res)
 140 {
 141    int i,
 142      k,
 143      m;
 144    for (i = 0; i < rlen; i++)
 145       res[i] = 0;
 146    for (i = 0; i < len; i++)
 147    {
 148       m = res[rlen - 1] ^ data[i];
 149       for (k = rlen - 1; k > 0; k--)
 150       {
 151          if (m && rspoly[k])
 152             res[k] = res[k - 1] ^ alog[(log[m] + log[rspoly[k]]) % logmod];
 153          else
 154             res[k] = res[k - 1];
 155       }
 156       if (m && rspoly[0])
 157          res[0] = alog[(log[m] + log[rspoly[0]]) % logmod];
 158       else
 159          res[0] = 0;
 160    }
 161 }
 162
 163 #ifndef LIB
 164 // The following tests the routines with the ISO/IEC 16022 Annexe R data
 165 int main (void)
 166 {
 167    register int i;
 168
 169    unsigned char data[9] = { 142, 164, 186 };
 170    unsigned char out[5];
 171
 172    rs_init_gf (0x12d);
 173    rs_init_code (5, 1);
 174
 175    rs_encode (3, data, out);
 176
 177    printf ("Result of Annexe R encoding:\n");
 178    for (i = 4; i >= 0; i--)
 179       printf ("  %d\n", out[i]);
 180
 181    return 0;
 182 }
 183 #endif