1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Tests for Generic Reed Solomon encoder / decoder library 4 * 5 * Written by Ferdinand Blomqvist 6 * Based on previous work by Phil Karn, KA9Q 7 */ 8 #include <linux/rslib.h> 9 #include <linux/kernel.h> 10 #include <linux/module.h> 11 #include <linux/moduleparam.h> 12 #include <linux/random.h> 13 #include <linux/slab.h> 14 15 enum verbosity { 16 V_SILENT, 17 V_PROGRESS, 18 V_CSUMMARY 19 }; 20 21 enum method { 22 CORR_BUFFER, 23 CALLER_SYNDROME, 24 IN_PLACE 25 }; 26 27 #define __param(type, name, init, msg) \ 28 static type name = init; \ 29 module_param(name, type, 0444); \ 30 MODULE_PARM_DESC(name, msg) 31 32 __param(int, v, V_PROGRESS, "Verbosity level"); 33 __param(int, ewsc, 1, "Erasures without symbol corruption"); 34 __param(int, bc, 1, "Test for correct behaviour beyond error correction capacity"); 35 36 struct etab { 37 int symsize; 38 int genpoly; 39 int fcs; 40 int prim; 41 int nroots; 42 int ntrials; 43 }; 44 45 /* List of codes to test */ 46 static struct etab Tab[] = { 47 {2, 0x7, 1, 1, 1, 100000 }, 48 {3, 0xb, 1, 1, 2, 100000 }, 49 {3, 0xb, 1, 1, 3, 100000 }, 50 {3, 0xb, 2, 1, 4, 100000 }, 51 {4, 0x13, 1, 1, 4, 10000 }, 52 {5, 0x25, 1, 1, 6, 1000 }, 53 {6, 0x43, 3, 1, 8, 1000 }, 54 {7, 0x89, 1, 1, 14, 500 }, 55 {8, 0x11d, 1, 1, 30, 100 }, 56 {8, 0x187, 112, 11, 32, 100 }, 57 {9, 0x211, 1, 1, 33, 80 }, 58 {0, 0, 0, 0, 0, 0}, 59 }; 60 61 62 struct estat { 63 int dwrong; 64 int irv; 65 int wepos; 66 int nwords; 67 }; 68 69 struct bcstat { 70 int rfail; 71 int rsuccess; 72 int noncw; 73 int nwords; 74 }; 75 76 struct wspace { 77 uint16_t *c; /* sent codeword */ 78 uint16_t *r; /* received word */ 79 uint16_t *s; /* syndrome */ 80 uint16_t *corr; /* correction buffer */ 81 int *errlocs; 82 int *derrlocs; 83 }; 84 85 struct pad { 86 int mult; 87 int shift; 88 }; 89 90 static struct pad pad_coef[] = { 91 { 0, 0 }, 92 { 1, 2 }, 93 { 1, 1 }, 94 { 3, 2 }, 95 { 1, 0 }, 96 }; 97 98 static void free_ws(struct wspace *ws) 99 { 100 if (!ws) 101 return; 102 103 kfree(ws->errlocs); 104 kfree(ws->c); 105 kfree(ws); 106 } 107 108 static struct wspace *alloc_ws(struct rs_codec *rs) 109 { 110 int nroots = rs->nroots; 111 struct wspace *ws; 112 int nn = rs->nn; 113 114 ws = kzalloc(sizeof(*ws), GFP_KERNEL); 115 if (!ws) 116 return NULL; 117 118 ws->c = kmalloc_array(2 * (nn + nroots), 119 sizeof(uint16_t), GFP_KERNEL); 120 if (!ws->c) 121 goto err; 122 123 ws->r = ws->c + nn; 124 ws->s = ws->r + nn; 125 ws->corr = ws->s + nroots; 126 127 ws->errlocs = kmalloc_array(nn + nroots, sizeof(int), GFP_KERNEL); 128 if (!ws->errlocs) 129 goto err; 130 131 ws->derrlocs = ws->errlocs + nn; 132 return ws; 133 134 err: 135 free_ws(ws); 136 return NULL; 137 } 138 139 140 /* 141 * Generates a random codeword and stores it in c. Generates random errors and 142 * erasures, and stores the random word with errors in r. Erasure positions are 143 * stored in derrlocs, while errlocs has one of three values in every position: 144 * 145 * 0 if there is no error in this position; 146 * 1 if there is a symbol error in this position; 147 * 2 if there is an erasure without symbol corruption. 148 * 149 * Returns the number of corrupted symbols. 150 */ 151 static int get_rcw_we(struct rs_control *rs, struct wspace *ws, 152 int len, int errs, int eras) 153 { 154 int nroots = rs->codec->nroots; 155 int *derrlocs = ws->derrlocs; 156 int *errlocs = ws->errlocs; 157 int dlen = len - nroots; 158 int nn = rs->codec->nn; 159 uint16_t *c = ws->c; 160 uint16_t *r = ws->r; 161 int errval; 162 int errloc; 163 int i; 164 165 /* Load c with random data and encode */ 166 for (i = 0; i < dlen; i++) 167 c[i] = get_random_u32() & nn; 168 169 memset(c + dlen, 0, nroots * sizeof(*c)); 170 encode_rs16(rs, c, dlen, c + dlen, 0); 171 172 /* Make copyand add errors and erasures */ 173 memcpy(r, c, len * sizeof(*r)); 174 memset(errlocs, 0, len * sizeof(*errlocs)); 175 memset(derrlocs, 0, nroots * sizeof(*derrlocs)); 176 177 /* Generating random errors */ 178 for (i = 0; i < errs; i++) { 179 do { 180 /* Error value must be nonzero */ 181 errval = get_random_u32() & nn; 182 } while (errval == 0); 183 184 do { 185 /* Must not choose the same location twice */ 186 errloc = prandom_u32_max(len); 187 } while (errlocs[errloc] != 0); 188 189 errlocs[errloc] = 1; 190 r[errloc] ^= errval; 191 } 192 193 /* Generating random erasures */ 194 for (i = 0; i < eras; i++) { 195 do { 196 /* Must not choose the same location twice */ 197 errloc = prandom_u32_max(len); 198 } while (errlocs[errloc] != 0); 199 200 derrlocs[i] = errloc; 201 202 if (ewsc && prandom_u32_max(2)) { 203 /* Erasure with the symbol intact */ 204 errlocs[errloc] = 2; 205 } else { 206 /* Erasure with corrupted symbol */ 207 do { 208 /* Error value must be nonzero */ 209 errval = get_random_u32() & nn; 210 } while (errval == 0); 211 212 errlocs[errloc] = 1; 213 r[errloc] ^= errval; 214 errs++; 215 } 216 } 217 218 return errs; 219 } 220 221 static void fix_err(uint16_t *data, int nerrs, uint16_t *corr, int *errlocs) 222 { 223 int i; 224 225 for (i = 0; i < nerrs; i++) 226 data[errlocs[i]] ^= corr[i]; 227 } 228 229 static void compute_syndrome(struct rs_control *rsc, uint16_t *data, 230 int len, uint16_t *syn) 231 { 232 struct rs_codec *rs = rsc->codec; 233 uint16_t *alpha_to = rs->alpha_to; 234 uint16_t *index_of = rs->index_of; 235 int nroots = rs->nroots; 236 int prim = rs->prim; 237 int fcr = rs->fcr; 238 int i, j; 239 240 /* Calculating syndrome */ 241 for (i = 0; i < nroots; i++) { 242 syn[i] = data[0]; 243 for (j = 1; j < len; j++) { 244 if (syn[i] == 0) { 245 syn[i] = data[j]; 246 } else { 247 syn[i] = data[j] ^ 248 alpha_to[rs_modnn(rs, index_of[syn[i]] 249 + (fcr + i) * prim)]; 250 } 251 } 252 } 253 254 /* Convert to index form */ 255 for (i = 0; i < nroots; i++) 256 syn[i] = rs->index_of[syn[i]]; 257 } 258 259 /* Test up to error correction capacity */ 260 static void test_uc(struct rs_control *rs, int len, int errs, 261 int eras, int trials, struct estat *stat, 262 struct wspace *ws, int method) 263 { 264 int dlen = len - rs->codec->nroots; 265 int *derrlocs = ws->derrlocs; 266 int *errlocs = ws->errlocs; 267 uint16_t *corr = ws->corr; 268 uint16_t *c = ws->c; 269 uint16_t *r = ws->r; 270 uint16_t *s = ws->s; 271 int derrs, nerrs; 272 int i, j; 273 274 for (j = 0; j < trials; j++) { 275 nerrs = get_rcw_we(rs, ws, len, errs, eras); 276 277 switch (method) { 278 case CORR_BUFFER: 279 derrs = decode_rs16(rs, r, r + dlen, dlen, 280 NULL, eras, derrlocs, 0, corr); 281 fix_err(r, derrs, corr, derrlocs); 282 break; 283 case CALLER_SYNDROME: 284 compute_syndrome(rs, r, len, s); 285 derrs = decode_rs16(rs, NULL, NULL, dlen, 286 s, eras, derrlocs, 0, corr); 287 fix_err(r, derrs, corr, derrlocs); 288 break; 289 case IN_PLACE: 290 derrs = decode_rs16(rs, r, r + dlen, dlen, 291 NULL, eras, derrlocs, 0, NULL); 292 break; 293 default: 294 continue; 295 } 296 297 if (derrs != nerrs) 298 stat->irv++; 299 300 if (method != IN_PLACE) { 301 for (i = 0; i < derrs; i++) { 302 if (errlocs[derrlocs[i]] != 1) 303 stat->wepos++; 304 } 305 } 306 307 if (memcmp(r, c, len * sizeof(*r))) 308 stat->dwrong++; 309 } 310 stat->nwords += trials; 311 } 312 313 static int ex_rs_helper(struct rs_control *rs, struct wspace *ws, 314 int len, int trials, int method) 315 { 316 static const char * const desc[] = { 317 "Testing correction buffer interface...", 318 "Testing with caller provided syndrome...", 319 "Testing in-place interface..." 320 }; 321 322 struct estat stat = {0, 0, 0, 0}; 323 int nroots = rs->codec->nroots; 324 int errs, eras, retval; 325 326 if (v >= V_PROGRESS) 327 pr_info(" %s\n", desc[method]); 328 329 for (errs = 0; errs <= nroots / 2; errs++) 330 for (eras = 0; eras <= nroots - 2 * errs; eras++) 331 test_uc(rs, len, errs, eras, trials, &stat, ws, method); 332 333 if (v >= V_CSUMMARY) { 334 pr_info(" Decodes wrong: %d / %d\n", 335 stat.dwrong, stat.nwords); 336 pr_info(" Wrong return value: %d / %d\n", 337 stat.irv, stat.nwords); 338 if (method != IN_PLACE) 339 pr_info(" Wrong error position: %d\n", stat.wepos); 340 } 341 342 retval = stat.dwrong + stat.wepos + stat.irv; 343 if (retval && v >= V_PROGRESS) 344 pr_warn(" FAIL: %d decoding failures!\n", retval); 345 346 return retval; 347 } 348 349 static int exercise_rs(struct rs_control *rs, struct wspace *ws, 350 int len, int trials) 351 { 352 353 int retval = 0; 354 int i; 355 356 if (v >= V_PROGRESS) 357 pr_info("Testing up to error correction capacity...\n"); 358 359 for (i = 0; i <= IN_PLACE; i++) 360 retval |= ex_rs_helper(rs, ws, len, trials, i); 361 362 return retval; 363 } 364 365 /* Tests for correct behaviour beyond error correction capacity */ 366 static void test_bc(struct rs_control *rs, int len, int errs, 367 int eras, int trials, struct bcstat *stat, 368 struct wspace *ws) 369 { 370 int nroots = rs->codec->nroots; 371 int dlen = len - nroots; 372 int *derrlocs = ws->derrlocs; 373 uint16_t *corr = ws->corr; 374 uint16_t *r = ws->r; 375 int derrs, j; 376 377 for (j = 0; j < trials; j++) { 378 get_rcw_we(rs, ws, len, errs, eras); 379 derrs = decode_rs16(rs, r, r + dlen, dlen, 380 NULL, eras, derrlocs, 0, corr); 381 fix_err(r, derrs, corr, derrlocs); 382 383 if (derrs >= 0) { 384 stat->rsuccess++; 385 386 /* 387 * We check that the returned word is actually a 388 * codeword. The obvious way to do this would be to 389 * compute the syndrome, but we don't want to replicate 390 * that code here. However, all the codes are in 391 * systematic form, and therefore we can encode the 392 * returned word, and see whether the parity changes or 393 * not. 394 */ 395 memset(corr, 0, nroots * sizeof(*corr)); 396 encode_rs16(rs, r, dlen, corr, 0); 397 398 if (memcmp(r + dlen, corr, nroots * sizeof(*corr))) 399 stat->noncw++; 400 } else { 401 stat->rfail++; 402 } 403 } 404 stat->nwords += trials; 405 } 406 407 static int exercise_rs_bc(struct rs_control *rs, struct wspace *ws, 408 int len, int trials) 409 { 410 struct bcstat stat = {0, 0, 0, 0}; 411 int nroots = rs->codec->nroots; 412 int errs, eras, cutoff; 413 414 if (v >= V_PROGRESS) 415 pr_info("Testing beyond error correction capacity...\n"); 416 417 for (errs = 1; errs <= nroots; errs++) { 418 eras = nroots - 2 * errs + 1; 419 if (eras < 0) 420 eras = 0; 421 422 cutoff = nroots <= len - errs ? nroots : len - errs; 423 for (; eras <= cutoff; eras++) 424 test_bc(rs, len, errs, eras, trials, &stat, ws); 425 } 426 427 if (v >= V_CSUMMARY) { 428 pr_info(" decoder gives up: %d / %d\n", 429 stat.rfail, stat.nwords); 430 pr_info(" decoder returns success: %d / %d\n", 431 stat.rsuccess, stat.nwords); 432 pr_info(" not a codeword: %d / %d\n", 433 stat.noncw, stat.rsuccess); 434 } 435 436 if (stat.noncw && v >= V_PROGRESS) 437 pr_warn(" FAIL: %d silent failures!\n", stat.noncw); 438 439 return stat.noncw; 440 } 441 442 static int run_exercise(struct etab *e) 443 { 444 int nn = (1 << e->symsize) - 1; 445 int kk = nn - e->nroots; 446 struct rs_control *rsc; 447 int retval = -ENOMEM; 448 int max_pad = kk - 1; 449 int prev_pad = -1; 450 struct wspace *ws; 451 int i; 452 453 rsc = init_rs(e->symsize, e->genpoly, e->fcs, e->prim, e->nroots); 454 if (!rsc) 455 return retval; 456 457 ws = alloc_ws(rsc->codec); 458 if (!ws) 459 goto err; 460 461 retval = 0; 462 for (i = 0; i < ARRAY_SIZE(pad_coef); i++) { 463 int pad = (pad_coef[i].mult * max_pad) >> pad_coef[i].shift; 464 int len = nn - pad; 465 466 if (pad == prev_pad) 467 continue; 468 469 prev_pad = pad; 470 if (v >= V_PROGRESS) { 471 pr_info("Testing (%d,%d)_%d code...\n", 472 len, kk - pad, nn + 1); 473 } 474 475 retval |= exercise_rs(rsc, ws, len, e->ntrials); 476 if (bc) 477 retval |= exercise_rs_bc(rsc, ws, len, e->ntrials); 478 } 479 480 free_ws(ws); 481 482 err: 483 free_rs(rsc); 484 return retval; 485 } 486 487 static int __init test_rslib_init(void) 488 { 489 int i, fail = 0; 490 491 for (i = 0; Tab[i].symsize != 0 ; i++) { 492 int retval; 493 494 retval = run_exercise(Tab + i); 495 if (retval < 0) 496 return -ENOMEM; 497 498 fail |= retval; 499 } 500 501 if (fail) 502 pr_warn("rslib: test failed\n"); 503 else 504 pr_info("rslib: test ok\n"); 505 506 return -EAGAIN; /* Fail will directly unload the module */ 507 } 508 509 static void __exit test_rslib_exit(void) 510 { 511 } 512 513 module_init(test_rslib_init) 514 module_exit(test_rslib_exit) 515 516 MODULE_LICENSE("GPL"); 517 MODULE_AUTHOR("Ferdinand Blomqvist"); 518 MODULE_DESCRIPTION("Reed-Solomon library test"); 519