• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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