3 * This is a simple Reed-Solomon encoder
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.
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.
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
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.
27 // <Some notes on the theory and implementation need to be added here>
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.
34 // These can be called repeatedly as required - but note that
35 // rs_init_code must be called following any rs_init_gf call.
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
42 #include <stdio.h> // only needed for debug (main)
43 #include <stdlib.h> // only needed for malloc/free
46 static int symsize; // in bits
47 static int logmod; // 2**symsize - 1
50 static int *log = NULL,
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
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.
64 void rs_init_gf (int poly)
71 // Return storage from previous setup
79 // Find the top bit, and hence the symbol size
80 for (b = 1, m = 0; b <= poly; b <<= 1)
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);
92 for (p = 1, v = 0; v < logmod; v++)
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.
109 void rs_init_code (int nsym, int index)
116 rspoly = (int *) malloc (sizeof (int) * (nsym + 1));
121 for (i = 1; i <= nsym; i++)
124 for (k = i - 1; k > 0; k--)
127 rspoly[k] = alog[(log[rspoly[k]] + index) % logmod];
128 rspoly[k] ^= rspoly[k - 1];
130 rspoly[0] = alog[(log[rspoly[0]] + index) % logmod];
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.
139 void rs_encode (int len, unsigned char *data, unsigned char *res)
144 for (i = 0; i < rlen; i++)
146 for (i = 0; i < len; i++)
148 m = res[rlen - 1] ^ data[i];
149 for (k = rlen - 1; k > 0; k--)
152 res[k] = res[k - 1] ^ alog[(log[m] + log[rspoly[k]]) % logmod];
157 res[0] = alog[(log[m] + log[rspoly[0]]) % logmod];
164 // The following tests the routines with the ISO/IEC 16022 Annexe R data
169 unsigned char data[9] = { 142, 164, 186 };
170 unsigned char out[5];
175 rs_encode (3, data, out);
177 printf ("Result of Annexe R encoding:\n");
178 for (i = 4; i >= 0; i--)
179 printf (" %d\n", out[i]);