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 #include <string.h> // only needed for memset
44 #include "reedsol.h"
45
46 static int gfpoly;
47 static int symsize; // in bits
48 static int logmod; // 2**symsize - 1
49 static int rlen;
50
51 static int *log = NULL, *alog = NULL, *rspoly = NULL;
52
53 // rs_init_gf(poly) initialises the parameters for the Galois Field.
54 // The symbol size is determined from the highest bit set in poly
55 // This implementation will support sizes up to 30 bits (though that
56 // will result in very large log/antilog tables) - bit sizes of
57 // 8 or 4 are typical
58 //
59 // The poly is the bit pattern representing the GF characteristic
60 // polynomial. e.g. for ECC200 (8-bit symbols) the polynomial is
61 // a**8 + a**5 + a**3 + a**2 + 1, which translates to 0x12d.
62
rs_init_gf(int poly)63 void rs_init_gf(int poly)
64 {
65 int m, b, p, v;
66
67 // Return storage from previous setup
68 if (log) {
69 free(log);
70 free(alog);
71 free(rspoly);
72 rspoly = NULL;
73 }
74 // Find the top bit, and hence the symbol size
75 for (b = 2, m = 0; b <= poly; b <<= 1)
76 m++;
77 b >>= 1;
78 gfpoly = poly;
79 symsize = m;
80
81 // Calculate the log/alog tables
82 logmod = (1 << m) - 1;
83 log = (int *)calloc(logmod + 1, sizeof(*log));
84 alog = (int *)calloc(logmod, sizeof(*alog));
85
86 for (p = 1, v = 0; v < logmod; v++) {
87 alog[v] = p;
88 log[p] = v;
89 p <<= 1;
90 if (p & b)
91 p ^= poly;
92 }
93 }
94
95 // rs_init_code(nsym, index) initialises the Reed-Solomon encoder
96 // nsym is the number of symbols to be generated (to be appended
97 // to the input data). index is usually 1 - it is the index of
98 // the constant in the first term (i) of the RS generator polynomial:
99 // (x + 2**i)*(x + 2**(i+1))*... [nsym terms]
100 // For ECC200, index is 1.
101
rs_init_code(int nsym,int index)102 void rs_init_code(int nsym, int index)
103 {
104 int i, k;
105
106 if (rspoly)
107 free(rspoly);
108 rspoly = (int *)malloc(sizeof(int) * (nsym + 1));
109
110 rlen = nsym;
111
112 rspoly[0] = 1;
113 for (i = 1; i <= nsym; i++) {
114 rspoly[i] = 1;
115 for (k = i - 1; k > 0; k--) {
116 if (rspoly[k])
117 rspoly[k] =
118 alog[(log[rspoly[k]] + index) % logmod];
119 rspoly[k] ^= rspoly[k - 1];
120 }
121 rspoly[0] = alog[(log[rspoly[0]] + index) % logmod];
122 index++;
123 }
124 }
125
126 // Note that the following uses byte arrays, so is only suitable for
127 // symbol sizes up to 8 bits. Just change the data type of data and res
128 // to unsigned int * for larger symbols.
129
rs_encode(int len,const unsigned char * data,unsigned char * res)130 void rs_encode(int len, const unsigned char *data, unsigned char *res)
131 {
132 int i, k, m;
133 memset(res, 0, rlen);
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 #ifdef TEST
153 // The following tests the routines with the ISO/IEC 16022 Annexe R data
reedsol_main(void)154 int reedsol_main(void)
155 {
156 register int i;
157
158 static const 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
173