1 /* Test the Reed-Solomon codecs
2 * for various block sizes and with random data and random error patterns
3 *
4 * Copyright 2002 Phil Karn, KA9Q
5 * May be used under the terms of the GNU Lesser General Public License (LGPL)
6 */
7
8 #include <stdio.h>
9 #include <stdlib.h>
10 #include <memory.h>
11 #include <time.h>
12 #include "fec.h"
13
14
15 struct etab {
16 int symsize;
17 int genpoly;
18 int fcs;
19 int prim;
20 int nroots;
21 int ntrials;
22 } Tab[] = {
23 {2, 0x7, 1, 1, 1, 10 },
24 {3, 0xb, 1, 1, 2, 10 },
25 {4, 0x13, 1, 1, 4, 10 },
26 {5, 0x25, 1, 1, 6, 10 },
27 {6, 0x43, 1, 1, 8, 10 },
28 {7, 0x89, 1, 1, 10, 10 },
29 {8, 0x11d, 1, 1, 32, 10 },
30 {8, 0x187, 112,11, 32, 10 }, /* Duplicates CCSDS codec */
31 {9, 0x211, 1, 1, 32, 10 },
32 {10,0x409, 1, 1, 32, 10 },
33 {11,0x805, 1, 1, 32, 10 },
34 {12,0x1053, 1, 1, 32, 5 },
35 {13,0x201b, 1, 1, 32, 2 },
36 {14,0x4443, 1, 1, 32, 1 },
37 {15,0x8003, 1, 1, 32, 1 },
38 {16,0x1100b, 1, 1, 32, 1 },
39 {0, 0, 0, 0, 0},
40 };
41
42 int exercise_char(struct etab *e);
43 int exercise_int(struct etab *e);
44 int exercise_8(void);
45
main()46 int main(){
47 int i;
48
49 srandom(time(NULL));
50
51 printf("Testing fixed CCSDS encoder...\n");
52 exercise_8();
53 for(i=0;Tab[i].symsize != 0;i++){
54 int nn,kk;
55
56 nn = (1<<Tab[i].symsize) - 1;
57 kk = nn - Tab[i].nroots;
58 printf("Testing (%d,%d) code...\n",nn,kk);
59 if(Tab[i].symsize <= 8)
60 exercise_char(&Tab[i]);
61 else
62 exercise_int(&Tab[i]);
63 }
64 exit(0);
65 }
66
exercise_8(void)67 int exercise_8(void){
68 int nn = 255;
69 unsigned char block[nn],tblock[nn];
70 int errlocs[nn],derrlocs[nn];
71 int i;
72 int errors;
73 int derrors,kk;
74 int errval,errloc;
75 int erasures;
76 int decoder_errors = 0;
77
78 /* Compute code parameters */
79 kk = 223;
80
81
82 /* Test up to the error correction capacity of the code */
83 for(errors=0;errors<=(nn-kk)/2;errors++){
84
85 /* Load block with random data and encode */
86 for(i=0;i<kk;i++)
87 block[i] = random() & nn;
88 memcpy(tblock,block,sizeof(block));
89 encode_rs_8(block,&block[kk],0);
90
91 /* Make temp copy, seed with errors */
92 memcpy(tblock,block,sizeof(block));
93 memset(errlocs,0,sizeof(errlocs));
94 memset(derrlocs,0,sizeof(derrlocs));
95 erasures=0;
96 for(i=0;i<errors;i++){
97 do {
98 errval = random() & nn;
99 } while(errval == 0); /* Error value must be nonzero */
100
101 do {
102 errloc = random() % nn;
103 } while(errlocs[errloc] != 0); /* Must not choose the same location twice */
104
105 errlocs[errloc] = 1;
106
107 #if FLAG_ERASURE
108 if(random() & 1) /* 50-50 chance */
109 derrlocs[erasures++] = errloc;
110 #endif
111 tblock[errloc] ^= errval;
112 }
113
114 /* Decode the errored block */
115 derrors = decode_rs_8(tblock,derrlocs,erasures,0);
116
117 if(derrors != errors){
118 printf("(%d,%d) decoder says %d errors, true number is %d\n",nn,kk,derrors,errors);
119 decoder_errors++;
120 }
121 for(i=0;i<derrors;i++){
122 if(errlocs[derrlocs[i]] == 0){
123 printf("(%d,%d) decoder indicates error in location %d without error\n",nn,kk,derrlocs[i]);
124 decoder_errors++;
125 }
126 }
127 if(memcmp(tblock,block,sizeof(tblock)) != 0){
128 printf("(%d,%d) decoder uncorrected errors! output ^ input:",nn,kk);
129 decoder_errors++;
130 for(i=0;i<nn;i++)
131 printf(" %02x",tblock[i] ^ block[i]);
132 printf("\n");
133 }
134 }
135 return decoder_errors;
136 }
137
138
exercise_char(struct etab * e)139 int exercise_char(struct etab *e){
140 int nn = (1<<e->symsize) - 1;
141 unsigned char block[nn],tblock[nn];
142 int errlocs[nn],derrlocs[nn];
143 int i;
144 int errors;
145 int derrors,kk;
146 int errval,errloc;
147 int erasures;
148 int decoder_errors = 0;
149 void *rs;
150
151 if(e->symsize > 8)
152 return -1;
153
154 /* Compute code parameters */
155 kk = nn - e->nroots;
156
157 rs = init_rs_char(e->symsize,e->genpoly,e->fcs,e->prim,e->nroots,0);
158 if(rs == NULL){
159 printf("init_rs_char failed!\n");
160 return -1;
161 }
162 /* Test up to the error correction capacity of the code */
163 for(errors=0;errors <= e->nroots/2;errors++){
164
165 /* Load block with random data and encode */
166 for(i=0;i<kk;i++)
167 block[i] = random() & nn;
168 memcpy(tblock,block,sizeof(block));
169 encode_rs_char(rs,block,&block[kk]);
170
171 /* Make temp copy, seed with errors */
172 memcpy(tblock,block,sizeof(block));
173 memset(errlocs,0,sizeof(errlocs));
174 memset(derrlocs,0,sizeof(derrlocs));
175 erasures=0;
176 for(i=0;i<errors;i++){
177 do {
178 errval = random() & nn;
179 } while(errval == 0); /* Error value must be nonzero */
180
181 do {
182 errloc = random() % nn;
183 } while(errlocs[errloc] != 0); /* Must not choose the same location twice */
184
185 errlocs[errloc] = 1;
186
187 #if FLAG_ERASURE
188 if(random() & 1) /* 50-50 chance */
189 derrlocs[erasures++] = errloc;
190 #endif
191 tblock[errloc] ^= errval;
192 }
193
194 /* Decode the errored block */
195 derrors = decode_rs_char(rs,tblock,derrlocs,erasures);
196
197 if(derrors != errors){
198 printf("(%d,%d) decoder says %d errors, true number is %d\n",nn,kk,derrors,errors);
199 decoder_errors++;
200 }
201 for(i=0;i<derrors;i++){
202 if(errlocs[derrlocs[i]] == 0){
203 printf("(%d,%d) decoder indicates error in location %d without error\n",nn,kk,derrlocs[i]);
204 decoder_errors++;
205 }
206 }
207 if(memcmp(tblock,block,sizeof(tblock)) != 0){
208 printf("(%d,%d) decoder uncorrected errors! output ^ input:",nn,kk);
209 decoder_errors++;
210 for(i=0;i<nn;i++)
211 printf(" %02x",tblock[i] ^ block[i]);
212 printf("\n");
213 }
214 }
215
216 free_rs_char(rs);
217 return 0;
218 }
219
exercise_int(struct etab * e)220 int exercise_int(struct etab *e){
221 int nn = (1<<e->symsize) - 1;
222 int block[nn],tblock[nn];
223 int errlocs[nn],derrlocs[nn];
224 int i;
225 int errors;
226 int derrors,kk;
227 int errval,errloc;
228 int erasures;
229 int decoder_errors = 0;
230 void *rs;
231
232 /* Compute code parameters */
233 kk = nn - e->nroots;
234
235 rs = init_rs_int(e->symsize,e->genpoly,e->fcs,e->prim,e->nroots,0);
236 if(rs == NULL){
237 printf("init_rs_int failed!\n");
238 return -1;
239 }
240 /* Test up to the error correction capacity of the code */
241 for(errors=0;errors <= e->nroots/2;errors++){
242
243 /* Load block with random data and encode */
244 for(i=0;i<kk;i++)
245 block[i] = random() & nn;
246 memcpy(tblock,block,sizeof(block));
247 encode_rs_int(rs,block,&block[kk]);
248
249 /* Make temp copy, seed with errors */
250 memcpy(tblock,block,sizeof(block));
251 memset(errlocs,0,sizeof(errlocs));
252 memset(derrlocs,0,sizeof(derrlocs));
253 erasures=0;
254 for(i=0;i<errors;i++){
255 do {
256 errval = random() & nn;
257 } while(errval == 0); /* Error value must be nonzero */
258
259 do {
260 errloc = random() % nn;
261 } while(errlocs[errloc] != 0); /* Must not choose the same location twice */
262
263 errlocs[errloc] = 1;
264
265 #if FLAG_ERASURE
266 if(random() & 1) /* 50-50 chance */
267 derrlocs[erasures++] = errloc;
268 #endif
269 tblock[errloc] ^= errval;
270 }
271
272 /* Decode the errored block */
273 derrors = decode_rs_int(rs,tblock,derrlocs,erasures);
274
275 if(derrors != errors){
276 printf("(%d,%d) decoder says %d errors, true number is %d\n",nn,kk,derrors,errors);
277 decoder_errors++;
278 }
279 for(i=0;i<derrors;i++){
280 if(errlocs[derrlocs[i]] == 0){
281 printf("(%d,%d) decoder indicates error in location %d without error\n",nn,kk,derrlocs[i]);
282 decoder_errors++;
283 }
284 }
285 if(memcmp(tblock,block,sizeof(tblock)) != 0){
286 printf("(%d,%d) decoder uncorrected errors! output ^ input:",nn,kk);
287 decoder_errors++;
288 for(i=0;i<nn;i++)
289 printf(" %02x",tblock[i] ^ block[i]);
290 printf("\n");
291 }
292 }
293
294 free_rs_int(rs);
295 return 0;
296 }
297