519 lines · c
1// SPDX-License-Identifier: GPL-2.02/*3 * Tests for Generic Reed Solomon encoder / decoder library4 *5 * Written by Ferdinand Blomqvist6 * Based on previous work by Phil Karn, KA9Q7 */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 15enum verbosity {16 V_SILENT,17 V_PROGRESS,18 V_CSUMMARY19};20 21enum method {22 CORR_BUFFER,23 CALLER_SYNDROME,24 IN_PLACE25};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 36struct 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 */46static 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 62struct estat {63 int dwrong;64 int irv;65 int wepos;66 int nwords;67};68 69struct bcstat {70 int rfail;71 int rsuccess;72 int noncw;73 int nwords;74};75 76struct 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 85struct pad {86 int mult;87 int shift;88};89 90static struct pad pad_coef[] = {91 { 0, 0 },92 { 1, 2 },93 { 1, 1 },94 { 3, 2 },95 { 1, 0 },96};97 98static 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 108static 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 134err:135 free_ws(ws);136 return NULL;137}138 139 140/*141 * Generates a random codeword and stores it in c. Generates random errors and142 * erasures, and stores the random word with errors in r. Erasure positions are143 * 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 */151static 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 = get_random_u32_below(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 = get_random_u32_below(len);198 } while (errlocs[errloc] != 0);199 200 derrlocs[i] = errloc;201 202 if (ewsc && get_random_u32_below(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 221static 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 229static 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 */260static 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 313static 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 349static 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 */366static 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 a388 * codeword. The obvious way to do this would be to389 * compute the syndrome, but we don't want to replicate390 * that code here. However, all the codes are in391 * systematic form, and therefore we can encode the392 * returned word, and see whether the parity changes or393 * 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 407static 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 442static 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 482err:483 free_rs(rsc);484 return retval;485}486 487static 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 else504 pr_info("rslib: test ok\n");505 506 return -EAGAIN; /* Fail will directly unload the module */507}508 509static void __exit test_rslib_exit(void)510{511}512 513module_init(test_rslib_init)514module_exit(test_rslib_exit)515 516MODULE_LICENSE("GPL");517MODULE_AUTHOR("Ferdinand Blomqvist");518MODULE_DESCRIPTION("Reed-Solomon library test");519