| 1 | |
| 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 |
|
| 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;
|
| 78 | uint16_t *r;
|
| 79 | uint16_t *s;
|
| 80 | uint16_t *corr;
|
| 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_obj(*ws);
|
| 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_objs(int, nn + nroots);
|
| 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 |
|
| 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 |
|
| 173 | memcpy(r, c, len * sizeof(*r));
|
| 174 | memset(errlocs, 0, len * sizeof(*errlocs));
|
| 175 | memset(derrlocs, 0, nroots * sizeof(*derrlocs));
|
| 176 |
|
| 177 |
|
| 178 | for (i = 0; i < errs; i++) {
|
| 179 | do {
|
| 180 |
|
| 181 | errval = get_random_u32() & nn;
|
| 182 | } while (errval == 0);
|
| 183 |
|
| 184 | do {
|
| 185 |
|
| 186 | errloc = get_random_u32_below(len);
|
| 187 | } while (errlocs[errloc] != 0);
|
| 188 |
|
| 189 | errlocs[errloc] = 1;
|
| 190 | r[errloc] ^= errval;
|
| 191 | }
|
| 192 |
|
| 193 |
|
| 194 | for (i = 0; i < eras; i++) {
|
| 195 | do {
|
| 196 |
|
| 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 |
|
| 204 | errlocs[errloc] = 2;
|
| 205 | } else {
|
| 206 |
|
| 207 | do {
|
| 208 |
|
| 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 |
|
| 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 |
|
| 255 | for (i = 0; i < nroots; i++)
|
| 256 | syn[i] = rs->index_of[syn[i]];
|
| 257 | }
|
| 258 |
|
| 259 |
|
| 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 |
|
| 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;
|
| 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");
|