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 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 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 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 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