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