lib/reed_solomon/test_rslib.c

   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 = 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
 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");