lib/reed_solomon/test_rslib.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * Tests for Generic Reed Solomon encoder / decoder library
0004  *
0005  * Written by Ferdinand Blomqvist
0006  * Based on previous work by Phil Karn, KA9Q
0007  */
0008 #include <linux/rslib.h>
0009 #include <linux/kernel.h>
0010 #include <linux/module.h>
0011 #include <linux/moduleparam.h>
0012 #include <linux/random.h>
0013 #include <linux/slab.h>
0014
0015 enum verbosity {
0016     V_SILENT,
0017     V_PROGRESS,
0018     V_CSUMMARY
0019 };
0020
0021 enum method {
0022     CORR_BUFFER,
0023     CALLER_SYNDROME,
0024     IN_PLACE
0025 };
0026
0027 #define __param(type, name, init, msg)      \
0028     static type name = init;        \
0029     module_param(name, type, 0444);     \
0030     MODULE_PARM_DESC(name, msg)
0031
0032 __param(int, v, V_PROGRESS, "Verbosity level");
0033 __param(int, ewsc, 1, "Erasures without symbol corruption");
0034 __param(int, bc, 1, "Test for correct behaviour beyond error correction capacity");
0035
0036 struct etab {
0037     int symsize;
0038     int genpoly;
0039     int fcs;
0040     int prim;
0041     int nroots;
0042     int ntrials;
0043 };
0044
0045 /* List of codes to test */
0046 static struct etab Tab[] = {
0047     {2, 0x7,    1,  1,  1,  100000  },
0048     {3, 0xb,    1,  1,  2,  100000  },
0049     {3, 0xb,    1,  1,  3,  100000  },
0050     {3, 0xb,    2,  1,  4,  100000  },
0051     {4, 0x13,   1,  1,  4,  10000   },
0052     {5, 0x25,   1,  1,  6,  1000    },
0053     {6, 0x43,   3,  1,  8,  1000    },
0054     {7, 0x89,   1,  1,  14, 500 },
0055     {8, 0x11d,  1,  1,  30, 100 },
0056     {8, 0x187,  112,    11, 32, 100 },
0057     {9, 0x211,  1,  1,  33, 80  },
0058     {0, 0, 0, 0, 0, 0},
0059 };
0060
0061
0062 struct estat {
0063     int dwrong;
0064     int irv;
0065     int wepos;
0066     int nwords;
0067 };
0068
0069 struct bcstat {
0070     int rfail;
0071     int rsuccess;
0072     int noncw;
0073     int nwords;
0074 };
0075
0076 struct wspace {
0077     uint16_t    *c;     /* sent codeword */
0078     uint16_t    *r;     /* received word */
0079     uint16_t    *s;     /* syndrome */
0080     uint16_t    *corr;      /* correction buffer */
0081     int     *errlocs;
0082     int     *derrlocs;
0083 };
0084
0085 struct pad {
0086     int mult;
0087     int shift;
0088 };
0089
0090 static struct pad pad_coef[] = {
0091     { 0, 0 },
0092     { 1, 2 },
0093     { 1, 1 },
0094     { 3, 2 },
0095     { 1, 0 },
0096 };
0097
0098 static void free_ws(struct wspace *ws)
0099 {
0100     if (!ws)
0101         return;
0102
0103     kfree(ws->errlocs);
0104     kfree(ws->c);
0105     kfree(ws);
0106 }
0107
0108 static struct wspace *alloc_ws(struct rs_codec *rs)
0109 {
0110     int nroots = rs->nroots;
0111     struct wspace *ws;
0112     int nn = rs->nn;
0113
0114     ws = kzalloc(sizeof(*ws), GFP_KERNEL);
0115     if (!ws)
0116         return NULL;
0117
0118     ws->c = kmalloc_array(2 * (nn + nroots),
0119                 sizeof(uint16_t), GFP_KERNEL);
0120     if (!ws->c)
0121         goto err;
0122
0123     ws->r = ws->c + nn;
0124     ws->s = ws->r + nn;
0125     ws->corr = ws->s + nroots;
0126
0127     ws->errlocs = kmalloc_array(nn + nroots, sizeof(int), GFP_KERNEL);
0128     if (!ws->errlocs)
0129         goto err;
0130
0131     ws->derrlocs = ws->errlocs + nn;
0132     return ws;
0133
0134 err:
0135     free_ws(ws);
0136     return NULL;
0137 }
0138
0139
0140 /*
0141  * Generates a random codeword and stores it in c. Generates random errors and
0142  * erasures, and stores the random word with errors in r. Erasure positions are
0143  * stored in derrlocs, while errlocs has one of three values in every position:
0144  *
0145  * 0 if there is no error in this position;
0146  * 1 if there is a symbol error in this position;
0147  * 2 if there is an erasure without symbol corruption.
0148  *
0149  * Returns the number of corrupted symbols.
0150  */
0151 static int get_rcw_we(struct rs_control *rs, struct wspace *ws,
0152             int len, int errs, int eras)
0153 {
0154     int nroots = rs->codec->nroots;
0155     int *derrlocs = ws->derrlocs;
0156     int *errlocs = ws->errlocs;
0157     int dlen = len - nroots;
0158     int nn = rs->codec->nn;
0159     uint16_t *c = ws->c;
0160     uint16_t *r = ws->r;
0161     int errval;
0162     int errloc;
0163     int i;
0164
0165     /* Load c with random data and encode */
0166     for (i = 0; i < dlen; i++)
0167         c[i] = prandom_u32() & nn;
0168
0169     memset(c + dlen, 0, nroots * sizeof(*c));
0170     encode_rs16(rs, c, dlen, c + dlen, 0);
0171
0172     /* Make copyand add errors and erasures */
0173     memcpy(r, c, len * sizeof(*r));
0174     memset(errlocs, 0, len * sizeof(*errlocs));
0175     memset(derrlocs, 0, nroots * sizeof(*derrlocs));
0176
0177     /* Generating random errors */
0178     for (i = 0; i < errs; i++) {
0179         do {
0180             /* Error value must be nonzero */
0181             errval = prandom_u32() & nn;
0182         } while (errval == 0);
0183
0184         do {
0185             /* Must not choose the same location twice */
0186             errloc = prandom_u32() % len;
0187         } while (errlocs[errloc] != 0);
0188
0189         errlocs[errloc] = 1;
0190         r[errloc] ^= errval;
0191     }
0192
0193     /* Generating random erasures */
0194     for (i = 0; i < eras; i++) {
0195         do {
0196             /* Must not choose the same location twice */
0197             errloc = prandom_u32() % len;
0198         } while (errlocs[errloc] != 0);
0199
0200         derrlocs[i] = errloc;
0201
0202         if (ewsc && (prandom_u32() & 1)) {
0203             /* Erasure with the symbol intact */
0204             errlocs[errloc] = 2;
0205         } else {
0206             /* Erasure with corrupted symbol */
0207             do {
0208                 /* Error value must be nonzero */
0209                 errval = prandom_u32() & nn;
0210             } while (errval == 0);
0211
0212             errlocs[errloc] = 1;
0213             r[errloc] ^= errval;
0214             errs++;
0215         }
0216     }
0217
0218     return errs;
0219 }
0220
0221 static void fix_err(uint16_t *data, int nerrs, uint16_t *corr, int *errlocs)
0222 {
0223     int i;
0224
0225     for (i = 0; i < nerrs; i++)
0226         data[errlocs[i]] ^= corr[i];
0227 }
0228
0229 static void compute_syndrome(struct rs_control *rsc, uint16_t *data,
0230                 int len, uint16_t *syn)
0231 {
0232     struct rs_codec *rs = rsc->codec;
0233     uint16_t *alpha_to = rs->alpha_to;
0234     uint16_t *index_of = rs->index_of;
0235     int nroots = rs->nroots;
0236     int prim = rs->prim;
0237     int fcr = rs->fcr;
0238     int i, j;
0239
0240     /* Calculating syndrome */
0241     for (i = 0; i < nroots; i++) {
0242         syn[i] = data[0];
0243         for (j = 1; j < len; j++) {
0244             if (syn[i] == 0) {
0245                 syn[i] = data[j];
0246             } else {
0247                 syn[i] = data[j] ^
0248                     alpha_to[rs_modnn(rs, index_of[syn[i]]
0249                         + (fcr + i) * prim)];
0250             }
0251         }
0252     }
0253
0254     /* Convert to index form */
0255     for (i = 0; i < nroots; i++)
0256         syn[i] = rs->index_of[syn[i]];
0257 }
0258
0259 /* Test up to error correction capacity */
0260 static void test_uc(struct rs_control *rs, int len, int errs,
0261         int eras, int trials, struct estat *stat,
0262         struct wspace *ws, int method)
0263 {
0264     int dlen = len - rs->codec->nroots;
0265     int *derrlocs = ws->derrlocs;
0266     int *errlocs = ws->errlocs;
0267     uint16_t *corr = ws->corr;
0268     uint16_t *c = ws->c;
0269     uint16_t *r = ws->r;
0270     uint16_t *s = ws->s;
0271     int derrs, nerrs;
0272     int i, j;
0273
0274     for (j = 0; j < trials; j++) {
0275         nerrs = get_rcw_we(rs, ws, len, errs, eras);
0276
0277         switch (method) {
0278         case CORR_BUFFER:
0279             derrs = decode_rs16(rs, r, r + dlen, dlen,
0280                     NULL, eras, derrlocs, 0, corr);
0281             fix_err(r, derrs, corr, derrlocs);
0282             break;
0283         case CALLER_SYNDROME:
0284             compute_syndrome(rs, r, len, s);
0285             derrs = decode_rs16(rs, NULL, NULL, dlen,
0286                     s, eras, derrlocs, 0, corr);
0287             fix_err(r, derrs, corr, derrlocs);
0288             break;
0289         case IN_PLACE:
0290             derrs = decode_rs16(rs, r, r + dlen, dlen,
0291                     NULL, eras, derrlocs, 0, NULL);
0292             break;
0293         default:
0294             continue;
0295         }
0296
0297         if (derrs != nerrs)
0298             stat->irv++;
0299
0300         if (method != IN_PLACE) {
0301             for (i = 0; i < derrs; i++) {
0302                 if (errlocs[derrlocs[i]] != 1)
0303                     stat->wepos++;
0304             }
0305         }
0306
0307         if (memcmp(r, c, len * sizeof(*r)))
0308             stat->dwrong++;
0309     }
0310     stat->nwords += trials;
0311 }
0312
0313 static int ex_rs_helper(struct rs_control *rs, struct wspace *ws,
0314             int len, int trials, int method)
0315 {
0316     static const char * const desc[] = {
0317         "Testing correction buffer interface...",
0318         "Testing with caller provided syndrome...",
0319         "Testing in-place interface..."
0320     };
0321
0322     struct estat stat = {0, 0, 0, 0};
0323     int nroots = rs->codec->nroots;
0324     int errs, eras, retval;
0325
0326     if (v >= V_PROGRESS)
0327         pr_info("  %s\n", desc[method]);
0328
0329     for (errs = 0; errs <= nroots / 2; errs++)
0330         for (eras = 0; eras <= nroots - 2 * errs; eras++)
0331             test_uc(rs, len, errs, eras, trials, &stat, ws, method);
0332
0333     if (v >= V_CSUMMARY) {
0334         pr_info("    Decodes wrong:        %d / %d\n",
0335                 stat.dwrong, stat.nwords);
0336         pr_info("    Wrong return value:   %d / %d\n",
0337                 stat.irv, stat.nwords);
0338         if (method != IN_PLACE)
0339             pr_info("    Wrong error position: %d\n", stat.wepos);
0340     }
0341
0342     retval = stat.dwrong + stat.wepos + stat.irv;
0343     if (retval && v >= V_PROGRESS)
0344         pr_warn("    FAIL: %d decoding failures!\n", retval);
0345
0346     return retval;
0347 }
0348
0349 static int exercise_rs(struct rs_control *rs, struct wspace *ws,
0350                int len, int trials)
0351 {
0352
0353     int retval = 0;
0354     int i;
0355
0356     if (v >= V_PROGRESS)
0357         pr_info("Testing up to error correction capacity...\n");
0358
0359     for (i = 0; i <= IN_PLACE; i++)
0360         retval |= ex_rs_helper(rs, ws, len, trials, i);
0361
0362     return retval;
0363 }
0364
0365 /* Tests for correct behaviour beyond error correction capacity */
0366 static void test_bc(struct rs_control *rs, int len, int errs,
0367         int eras, int trials, struct bcstat *stat,
0368         struct wspace *ws)
0369 {
0370     int nroots = rs->codec->nroots;
0371     int dlen = len - nroots;
0372     int *derrlocs = ws->derrlocs;
0373     uint16_t *corr = ws->corr;
0374     uint16_t *r = ws->r;
0375     int derrs, j;
0376
0377     for (j = 0; j < trials; j++) {
0378         get_rcw_we(rs, ws, len, errs, eras);
0379         derrs = decode_rs16(rs, r, r + dlen, dlen,
0380                 NULL, eras, derrlocs, 0, corr);
0381         fix_err(r, derrs, corr, derrlocs);
0382
0383         if (derrs >= 0) {
0384             stat->rsuccess++;
0385
0386             /*
0387              * We check that the returned word is actually a
0388              * codeword. The obvious way to do this would be to
0389              * compute the syndrome, but we don't want to replicate
0390              * that code here. However, all the codes are in
0391              * systematic form, and therefore we can encode the
0392              * returned word, and see whether the parity changes or
0393              * not.
0394              */
0395             memset(corr, 0, nroots * sizeof(*corr));
0396             encode_rs16(rs, r, dlen, corr, 0);
0397
0398             if (memcmp(r + dlen, corr, nroots * sizeof(*corr)))
0399                 stat->noncw++;
0400         } else {
0401             stat->rfail++;
0402         }
0403     }
0404     stat->nwords += trials;
0405 }
0406
0407 static int exercise_rs_bc(struct rs_control *rs, struct wspace *ws,
0408               int len, int trials)
0409 {
0410     struct bcstat stat = {0, 0, 0, 0};
0411     int nroots = rs->codec->nroots;
0412     int errs, eras, cutoff;
0413
0414     if (v >= V_PROGRESS)
0415         pr_info("Testing beyond error correction capacity...\n");
0416
0417     for (errs = 1; errs <= nroots; errs++) {
0418         eras = nroots - 2 * errs + 1;
0419         if (eras < 0)
0420             eras = 0;
0421
0422         cutoff = nroots <= len - errs ? nroots : len - errs;
0423         for (; eras <= cutoff; eras++)
0424             test_bc(rs, len, errs, eras, trials, &stat, ws);
0425     }
0426
0427     if (v >= V_CSUMMARY) {
0428         pr_info("  decoder gives up:        %d / %d\n",
0429                 stat.rfail, stat.nwords);
0430         pr_info("  decoder returns success: %d / %d\n",
0431                 stat.rsuccess, stat.nwords);
0432         pr_info("    not a codeword:        %d / %d\n",
0433                 stat.noncw, stat.rsuccess);
0434     }
0435
0436     if (stat.noncw && v >= V_PROGRESS)
0437         pr_warn("    FAIL: %d silent failures!\n", stat.noncw);
0438
0439     return stat.noncw;
0440 }
0441
0442 static int run_exercise(struct etab *e)
0443 {
0444     int nn = (1 << e->symsize) - 1;
0445     int kk = nn - e->nroots;
0446     struct rs_control *rsc;
0447     int retval = -ENOMEM;
0448     int max_pad = kk - 1;
0449     int prev_pad = -1;
0450     struct wspace *ws;
0451     int i;
0452
0453     rsc = init_rs(e->symsize, e->genpoly, e->fcs, e->prim, e->nroots);
0454     if (!rsc)
0455         return retval;
0456
0457     ws = alloc_ws(rsc->codec);
0458     if (!ws)
0459         goto err;
0460
0461     retval = 0;
0462     for (i = 0; i < ARRAY_SIZE(pad_coef); i++) {
0463         int pad = (pad_coef[i].mult * max_pad) >> pad_coef[i].shift;
0464         int len = nn - pad;
0465
0466         if (pad == prev_pad)
0467             continue;
0468
0469         prev_pad = pad;
0470         if (v >= V_PROGRESS) {
0471             pr_info("Testing (%d,%d)_%d code...\n",
0472                     len, kk - pad, nn + 1);
0473         }
0474
0475         retval |= exercise_rs(rsc, ws, len, e->ntrials);
0476         if (bc)
0477             retval |= exercise_rs_bc(rsc, ws, len, e->ntrials);
0478     }
0479
0480     free_ws(ws);
0481
0482 err:
0483     free_rs(rsc);
0484     return retval;
0485 }
0486
0487 static int __init test_rslib_init(void)
0488 {
0489     int i, fail = 0;
0490
0491     for (i = 0; Tab[i].symsize != 0 ; i++) {
0492         int retval;
0493
0494         retval = run_exercise(Tab + i);
0495         if (retval < 0)
0496             return -ENOMEM;
0497
0498         fail |= retval;
0499     }
0500
0501     if (fail)
0502         pr_warn("rslib: test failed\n");
0503     else
0504         pr_info("rslib: test ok\n");
0505
0506     return -EAGAIN; /* Fail will directly unload the module */
0507 }
0508
0509 static void __exit test_rslib_exit(void)
0510 {
0511 }
0512
0513 module_init(test_rslib_init)
0514 module_exit(test_rslib_exit)
0515
0516 MODULE_LICENSE("GPL");
0517 MODULE_AUTHOR("Ferdinand Blomqvist");
0518 MODULE_DESCRIPTION("Reed-Solomon library test");