14b4f3accSFerdinand Blomqvist // SPDX-License-Identifier: GPL-2.0
24b4f3accSFerdinand Blomqvist /*
34b4f3accSFerdinand Blomqvist * Tests for Generic Reed Solomon encoder / decoder library
44b4f3accSFerdinand Blomqvist *
54b4f3accSFerdinand Blomqvist * Written by Ferdinand Blomqvist
64b4f3accSFerdinand Blomqvist * Based on previous work by Phil Karn, KA9Q
74b4f3accSFerdinand Blomqvist */
84b4f3accSFerdinand Blomqvist #include <linux/rslib.h>
94b4f3accSFerdinand Blomqvist #include <linux/kernel.h>
104b4f3accSFerdinand Blomqvist #include <linux/module.h>
114b4f3accSFerdinand Blomqvist #include <linux/moduleparam.h>
124b4f3accSFerdinand Blomqvist #include <linux/random.h>
134b4f3accSFerdinand Blomqvist #include <linux/slab.h>
144b4f3accSFerdinand Blomqvist
154b4f3accSFerdinand Blomqvist enum verbosity {
164b4f3accSFerdinand Blomqvist V_SILENT,
174b4f3accSFerdinand Blomqvist V_PROGRESS,
184b4f3accSFerdinand Blomqvist V_CSUMMARY
194b4f3accSFerdinand Blomqvist };
204b4f3accSFerdinand Blomqvist
214b4f3accSFerdinand Blomqvist enum method {
224b4f3accSFerdinand Blomqvist CORR_BUFFER,
234b4f3accSFerdinand Blomqvist CALLER_SYNDROME,
244b4f3accSFerdinand Blomqvist IN_PLACE
254b4f3accSFerdinand Blomqvist };
264b4f3accSFerdinand Blomqvist
274b4f3accSFerdinand Blomqvist #define __param(type, name, init, msg) \
284b4f3accSFerdinand Blomqvist static type name = init; \
294b4f3accSFerdinand Blomqvist module_param(name, type, 0444); \
304b4f3accSFerdinand Blomqvist MODULE_PARM_DESC(name, msg)
314b4f3accSFerdinand Blomqvist
324b4f3accSFerdinand Blomqvist __param(int, v, V_PROGRESS, "Verbosity level");
334b4f3accSFerdinand Blomqvist __param(int, ewsc, 1, "Erasures without symbol corruption");
344b4f3accSFerdinand Blomqvist __param(int, bc, 1, "Test for correct behaviour beyond error correction capacity");
354b4f3accSFerdinand Blomqvist
364b4f3accSFerdinand Blomqvist struct etab {
374b4f3accSFerdinand Blomqvist int symsize;
384b4f3accSFerdinand Blomqvist int genpoly;
394b4f3accSFerdinand Blomqvist int fcs;
404b4f3accSFerdinand Blomqvist int prim;
414b4f3accSFerdinand Blomqvist int nroots;
424b4f3accSFerdinand Blomqvist int ntrials;
434b4f3accSFerdinand Blomqvist };
444b4f3accSFerdinand Blomqvist
454b4f3accSFerdinand Blomqvist /* List of codes to test */
464b4f3accSFerdinand Blomqvist static struct etab Tab[] = {
474b4f3accSFerdinand Blomqvist {2, 0x7, 1, 1, 1, 100000 },
484b4f3accSFerdinand Blomqvist {3, 0xb, 1, 1, 2, 100000 },
494b4f3accSFerdinand Blomqvist {3, 0xb, 1, 1, 3, 100000 },
504b4f3accSFerdinand Blomqvist {3, 0xb, 2, 1, 4, 100000 },
514b4f3accSFerdinand Blomqvist {4, 0x13, 1, 1, 4, 10000 },
524b4f3accSFerdinand Blomqvist {5, 0x25, 1, 1, 6, 1000 },
534b4f3accSFerdinand Blomqvist {6, 0x43, 3, 1, 8, 1000 },
544b4f3accSFerdinand Blomqvist {7, 0x89, 1, 1, 14, 500 },
554b4f3accSFerdinand Blomqvist {8, 0x11d, 1, 1, 30, 100 },
564b4f3accSFerdinand Blomqvist {8, 0x187, 112, 11, 32, 100 },
574b4f3accSFerdinand Blomqvist {9, 0x211, 1, 1, 33, 80 },
584b4f3accSFerdinand Blomqvist {0, 0, 0, 0, 0, 0},
594b4f3accSFerdinand Blomqvist };
604b4f3accSFerdinand Blomqvist
614b4f3accSFerdinand Blomqvist
624b4f3accSFerdinand Blomqvist struct estat {
634b4f3accSFerdinand Blomqvist int dwrong;
644b4f3accSFerdinand Blomqvist int irv;
654b4f3accSFerdinand Blomqvist int wepos;
664b4f3accSFerdinand Blomqvist int nwords;
674b4f3accSFerdinand Blomqvist };
684b4f3accSFerdinand Blomqvist
694b4f3accSFerdinand Blomqvist struct bcstat {
704b4f3accSFerdinand Blomqvist int rfail;
714b4f3accSFerdinand Blomqvist int rsuccess;
724b4f3accSFerdinand Blomqvist int noncw;
734b4f3accSFerdinand Blomqvist int nwords;
744b4f3accSFerdinand Blomqvist };
754b4f3accSFerdinand Blomqvist
764b4f3accSFerdinand Blomqvist struct wspace {
774b4f3accSFerdinand Blomqvist uint16_t *c; /* sent codeword */
784b4f3accSFerdinand Blomqvist uint16_t *r; /* received word */
794b4f3accSFerdinand Blomqvist uint16_t *s; /* syndrome */
804b4f3accSFerdinand Blomqvist uint16_t *corr; /* correction buffer */
814b4f3accSFerdinand Blomqvist int *errlocs;
824b4f3accSFerdinand Blomqvist int *derrlocs;
834b4f3accSFerdinand Blomqvist };
844b4f3accSFerdinand Blomqvist
854b4f3accSFerdinand Blomqvist struct pad {
864b4f3accSFerdinand Blomqvist int mult;
874b4f3accSFerdinand Blomqvist int shift;
884b4f3accSFerdinand Blomqvist };
894b4f3accSFerdinand Blomqvist
904b4f3accSFerdinand Blomqvist static struct pad pad_coef[] = {
914b4f3accSFerdinand Blomqvist { 0, 0 },
924b4f3accSFerdinand Blomqvist { 1, 2 },
934b4f3accSFerdinand Blomqvist { 1, 1 },
944b4f3accSFerdinand Blomqvist { 3, 2 },
954b4f3accSFerdinand Blomqvist { 1, 0 },
964b4f3accSFerdinand Blomqvist };
974b4f3accSFerdinand Blomqvist
free_ws(struct wspace * ws)984b4f3accSFerdinand Blomqvist static void free_ws(struct wspace *ws)
994b4f3accSFerdinand Blomqvist {
1004b4f3accSFerdinand Blomqvist if (!ws)
1014b4f3accSFerdinand Blomqvist return;
1024b4f3accSFerdinand Blomqvist
1034b4f3accSFerdinand Blomqvist kfree(ws->errlocs);
1044b4f3accSFerdinand Blomqvist kfree(ws->c);
1054b4f3accSFerdinand Blomqvist kfree(ws);
1064b4f3accSFerdinand Blomqvist }
1074b4f3accSFerdinand Blomqvist
alloc_ws(struct rs_codec * rs)1084b4f3accSFerdinand Blomqvist static struct wspace *alloc_ws(struct rs_codec *rs)
1094b4f3accSFerdinand Blomqvist {
1104b4f3accSFerdinand Blomqvist int nroots = rs->nroots;
1114b4f3accSFerdinand Blomqvist struct wspace *ws;
1124b4f3accSFerdinand Blomqvist int nn = rs->nn;
1134b4f3accSFerdinand Blomqvist
1144b4f3accSFerdinand Blomqvist ws = kzalloc(sizeof(*ws), GFP_KERNEL);
1154b4f3accSFerdinand Blomqvist if (!ws)
1164b4f3accSFerdinand Blomqvist return NULL;
1174b4f3accSFerdinand Blomqvist
1184b4f3accSFerdinand Blomqvist ws->c = kmalloc_array(2 * (nn + nroots),
1194b4f3accSFerdinand Blomqvist sizeof(uint16_t), GFP_KERNEL);
1204b4f3accSFerdinand Blomqvist if (!ws->c)
1214b4f3accSFerdinand Blomqvist goto err;
1224b4f3accSFerdinand Blomqvist
1234b4f3accSFerdinand Blomqvist ws->r = ws->c + nn;
1244b4f3accSFerdinand Blomqvist ws->s = ws->r + nn;
1254b4f3accSFerdinand Blomqvist ws->corr = ws->s + nroots;
1264b4f3accSFerdinand Blomqvist
1274b4f3accSFerdinand Blomqvist ws->errlocs = kmalloc_array(nn + nroots, sizeof(int), GFP_KERNEL);
1284b4f3accSFerdinand Blomqvist if (!ws->errlocs)
1294b4f3accSFerdinand Blomqvist goto err;
1304b4f3accSFerdinand Blomqvist
1314b4f3accSFerdinand Blomqvist ws->derrlocs = ws->errlocs + nn;
1324b4f3accSFerdinand Blomqvist return ws;
1334b4f3accSFerdinand Blomqvist
1344b4f3accSFerdinand Blomqvist err:
1354b4f3accSFerdinand Blomqvist free_ws(ws);
1364b4f3accSFerdinand Blomqvist return NULL;
1374b4f3accSFerdinand Blomqvist }
1384b4f3accSFerdinand Blomqvist
1394b4f3accSFerdinand Blomqvist
1404b4f3accSFerdinand Blomqvist /*
1414b4f3accSFerdinand Blomqvist * Generates a random codeword and stores it in c. Generates random errors and
1424b4f3accSFerdinand Blomqvist * erasures, and stores the random word with errors in r. Erasure positions are
1434b4f3accSFerdinand Blomqvist * stored in derrlocs, while errlocs has one of three values in every position:
1444b4f3accSFerdinand Blomqvist *
1454b4f3accSFerdinand Blomqvist * 0 if there is no error in this position;
1464b4f3accSFerdinand Blomqvist * 1 if there is a symbol error in this position;
1474b4f3accSFerdinand Blomqvist * 2 if there is an erasure without symbol corruption.
1484b4f3accSFerdinand Blomqvist *
1494b4f3accSFerdinand Blomqvist * Returns the number of corrupted symbols.
1504b4f3accSFerdinand Blomqvist */
get_rcw_we(struct rs_control * rs,struct wspace * ws,int len,int errs,int eras)1514b4f3accSFerdinand Blomqvist static int get_rcw_we(struct rs_control *rs, struct wspace *ws,
1524b4f3accSFerdinand Blomqvist int len, int errs, int eras)
1534b4f3accSFerdinand Blomqvist {
1544b4f3accSFerdinand Blomqvist int nroots = rs->codec->nroots;
1554b4f3accSFerdinand Blomqvist int *derrlocs = ws->derrlocs;
1564b4f3accSFerdinand Blomqvist int *errlocs = ws->errlocs;
1574b4f3accSFerdinand Blomqvist int dlen = len - nroots;
1584b4f3accSFerdinand Blomqvist int nn = rs->codec->nn;
1594b4f3accSFerdinand Blomqvist uint16_t *c = ws->c;
1604b4f3accSFerdinand Blomqvist uint16_t *r = ws->r;
1614b4f3accSFerdinand Blomqvist int errval;
1624b4f3accSFerdinand Blomqvist int errloc;
1634b4f3accSFerdinand Blomqvist int i;
1644b4f3accSFerdinand Blomqvist
1654b4f3accSFerdinand Blomqvist /* Load c with random data and encode */
1664b4f3accSFerdinand Blomqvist for (i = 0; i < dlen; i++)
167a251c17aSJason A. Donenfeld c[i] = get_random_u32() & nn;
1684b4f3accSFerdinand Blomqvist
1694b4f3accSFerdinand Blomqvist memset(c + dlen, 0, nroots * sizeof(*c));
1704b4f3accSFerdinand Blomqvist encode_rs16(rs, c, dlen, c + dlen, 0);
1714b4f3accSFerdinand Blomqvist
1724b4f3accSFerdinand Blomqvist /* Make copyand add errors and erasures */
1734b4f3accSFerdinand Blomqvist memcpy(r, c, len * sizeof(*r));
1744b4f3accSFerdinand Blomqvist memset(errlocs, 0, len * sizeof(*errlocs));
1754b4f3accSFerdinand Blomqvist memset(derrlocs, 0, nroots * sizeof(*derrlocs));
1764b4f3accSFerdinand Blomqvist
1774b4f3accSFerdinand Blomqvist /* Generating random errors */
1784b4f3accSFerdinand Blomqvist for (i = 0; i < errs; i++) {
1794b4f3accSFerdinand Blomqvist do {
1804b4f3accSFerdinand Blomqvist /* Error value must be nonzero */
181a251c17aSJason A. Donenfeld errval = get_random_u32() & nn;
1824b4f3accSFerdinand Blomqvist } while (errval == 0);
1834b4f3accSFerdinand Blomqvist
1844b4f3accSFerdinand Blomqvist do {
1854b4f3accSFerdinand Blomqvist /* Must not choose the same location twice */
186*8032bf12SJason A. Donenfeld errloc = get_random_u32_below(len);
1874b4f3accSFerdinand Blomqvist } while (errlocs[errloc] != 0);
1884b4f3accSFerdinand Blomqvist
1894b4f3accSFerdinand Blomqvist errlocs[errloc] = 1;
1904b4f3accSFerdinand Blomqvist r[errloc] ^= errval;
1914b4f3accSFerdinand Blomqvist }
1924b4f3accSFerdinand Blomqvist
1934b4f3accSFerdinand Blomqvist /* Generating random erasures */
1944b4f3accSFerdinand Blomqvist for (i = 0; i < eras; i++) {
1954b4f3accSFerdinand Blomqvist do {
1964b4f3accSFerdinand Blomqvist /* Must not choose the same location twice */
197*8032bf12SJason A. Donenfeld errloc = get_random_u32_below(len);
1984b4f3accSFerdinand Blomqvist } while (errlocs[errloc] != 0);
1994b4f3accSFerdinand Blomqvist
2004b4f3accSFerdinand Blomqvist derrlocs[i] = errloc;
2014b4f3accSFerdinand Blomqvist
202*8032bf12SJason A. Donenfeld if (ewsc && get_random_u32_below(2)) {
2034b4f3accSFerdinand Blomqvist /* Erasure with the symbol intact */
2044b4f3accSFerdinand Blomqvist errlocs[errloc] = 2;
2054b4f3accSFerdinand Blomqvist } else {
2064b4f3accSFerdinand Blomqvist /* Erasure with corrupted symbol */
2074b4f3accSFerdinand Blomqvist do {
2084b4f3accSFerdinand Blomqvist /* Error value must be nonzero */
209a251c17aSJason A. Donenfeld errval = get_random_u32() & nn;
2104b4f3accSFerdinand Blomqvist } while (errval == 0);
2114b4f3accSFerdinand Blomqvist
2124b4f3accSFerdinand Blomqvist errlocs[errloc] = 1;
2134b4f3accSFerdinand Blomqvist r[errloc] ^= errval;
2144b4f3accSFerdinand Blomqvist errs++;
2154b4f3accSFerdinand Blomqvist }
2164b4f3accSFerdinand Blomqvist }
2174b4f3accSFerdinand Blomqvist
2184b4f3accSFerdinand Blomqvist return errs;
2194b4f3accSFerdinand Blomqvist }
2204b4f3accSFerdinand Blomqvist
fix_err(uint16_t * data,int nerrs,uint16_t * corr,int * errlocs)2214b4f3accSFerdinand Blomqvist static void fix_err(uint16_t *data, int nerrs, uint16_t *corr, int *errlocs)
2224b4f3accSFerdinand Blomqvist {
2234b4f3accSFerdinand Blomqvist int i;
2244b4f3accSFerdinand Blomqvist
2254b4f3accSFerdinand Blomqvist for (i = 0; i < nerrs; i++)
2264b4f3accSFerdinand Blomqvist data[errlocs[i]] ^= corr[i];
2274b4f3accSFerdinand Blomqvist }
2284b4f3accSFerdinand Blomqvist
compute_syndrome(struct rs_control * rsc,uint16_t * data,int len,uint16_t * syn)2294b4f3accSFerdinand Blomqvist static void compute_syndrome(struct rs_control *rsc, uint16_t *data,
2304b4f3accSFerdinand Blomqvist int len, uint16_t *syn)
2314b4f3accSFerdinand Blomqvist {
2324b4f3accSFerdinand Blomqvist struct rs_codec *rs = rsc->codec;
2334b4f3accSFerdinand Blomqvist uint16_t *alpha_to = rs->alpha_to;
2344b4f3accSFerdinand Blomqvist uint16_t *index_of = rs->index_of;
2354b4f3accSFerdinand Blomqvist int nroots = rs->nroots;
2364b4f3accSFerdinand Blomqvist int prim = rs->prim;
2374b4f3accSFerdinand Blomqvist int fcr = rs->fcr;
2384b4f3accSFerdinand Blomqvist int i, j;
2394b4f3accSFerdinand Blomqvist
2404b4f3accSFerdinand Blomqvist /* Calculating syndrome */
2414b4f3accSFerdinand Blomqvist for (i = 0; i < nroots; i++) {
2424b4f3accSFerdinand Blomqvist syn[i] = data[0];
2434b4f3accSFerdinand Blomqvist for (j = 1; j < len; j++) {
2444b4f3accSFerdinand Blomqvist if (syn[i] == 0) {
2454b4f3accSFerdinand Blomqvist syn[i] = data[j];
2464b4f3accSFerdinand Blomqvist } else {
2474b4f3accSFerdinand Blomqvist syn[i] = data[j] ^
2484b4f3accSFerdinand Blomqvist alpha_to[rs_modnn(rs, index_of[syn[i]]
2494b4f3accSFerdinand Blomqvist + (fcr + i) * prim)];
2504b4f3accSFerdinand Blomqvist }
2514b4f3accSFerdinand Blomqvist }
2524b4f3accSFerdinand Blomqvist }
2534b4f3accSFerdinand Blomqvist
2544b4f3accSFerdinand Blomqvist /* Convert to index form */
2554b4f3accSFerdinand Blomqvist for (i = 0; i < nroots; i++)
2564b4f3accSFerdinand Blomqvist syn[i] = rs->index_of[syn[i]];
2574b4f3accSFerdinand Blomqvist }
2584b4f3accSFerdinand Blomqvist
2594b4f3accSFerdinand Blomqvist /* Test up to error correction capacity */
test_uc(struct rs_control * rs,int len,int errs,int eras,int trials,struct estat * stat,struct wspace * ws,int method)2604b4f3accSFerdinand Blomqvist static void test_uc(struct rs_control *rs, int len, int errs,
2614b4f3accSFerdinand Blomqvist int eras, int trials, struct estat *stat,
2624b4f3accSFerdinand Blomqvist struct wspace *ws, int method)
2634b4f3accSFerdinand Blomqvist {
2644b4f3accSFerdinand Blomqvist int dlen = len - rs->codec->nroots;
2654b4f3accSFerdinand Blomqvist int *derrlocs = ws->derrlocs;
2664b4f3accSFerdinand Blomqvist int *errlocs = ws->errlocs;
2674b4f3accSFerdinand Blomqvist uint16_t *corr = ws->corr;
2684b4f3accSFerdinand Blomqvist uint16_t *c = ws->c;
2694b4f3accSFerdinand Blomqvist uint16_t *r = ws->r;
2704b4f3accSFerdinand Blomqvist uint16_t *s = ws->s;
2714b4f3accSFerdinand Blomqvist int derrs, nerrs;
2724b4f3accSFerdinand Blomqvist int i, j;
2734b4f3accSFerdinand Blomqvist
2744b4f3accSFerdinand Blomqvist for (j = 0; j < trials; j++) {
2754b4f3accSFerdinand Blomqvist nerrs = get_rcw_we(rs, ws, len, errs, eras);
2764b4f3accSFerdinand Blomqvist
2774b4f3accSFerdinand Blomqvist switch (method) {
2784b4f3accSFerdinand Blomqvist case CORR_BUFFER:
2794b4f3accSFerdinand Blomqvist derrs = decode_rs16(rs, r, r + dlen, dlen,
2804b4f3accSFerdinand Blomqvist NULL, eras, derrlocs, 0, corr);
2814b4f3accSFerdinand Blomqvist fix_err(r, derrs, corr, derrlocs);
2824b4f3accSFerdinand Blomqvist break;
2834b4f3accSFerdinand Blomqvist case CALLER_SYNDROME:
2844b4f3accSFerdinand Blomqvist compute_syndrome(rs, r, len, s);
2854b4f3accSFerdinand Blomqvist derrs = decode_rs16(rs, NULL, NULL, dlen,
2864b4f3accSFerdinand Blomqvist s, eras, derrlocs, 0, corr);
2874b4f3accSFerdinand Blomqvist fix_err(r, derrs, corr, derrlocs);
2884b4f3accSFerdinand Blomqvist break;
2894b4f3accSFerdinand Blomqvist case IN_PLACE:
2904b4f3accSFerdinand Blomqvist derrs = decode_rs16(rs, r, r + dlen, dlen,
2914b4f3accSFerdinand Blomqvist NULL, eras, derrlocs, 0, NULL);
2924b4f3accSFerdinand Blomqvist break;
2934b4f3accSFerdinand Blomqvist default:
2944b4f3accSFerdinand Blomqvist continue;
2954b4f3accSFerdinand Blomqvist }
2964b4f3accSFerdinand Blomqvist
2974b4f3accSFerdinand Blomqvist if (derrs != nerrs)
2984b4f3accSFerdinand Blomqvist stat->irv++;
2994b4f3accSFerdinand Blomqvist
3004b4f3accSFerdinand Blomqvist if (method != IN_PLACE) {
3014b4f3accSFerdinand Blomqvist for (i = 0; i < derrs; i++) {
3024b4f3accSFerdinand Blomqvist if (errlocs[derrlocs[i]] != 1)
3034b4f3accSFerdinand Blomqvist stat->wepos++;
3044b4f3accSFerdinand Blomqvist }
3054b4f3accSFerdinand Blomqvist }
3064b4f3accSFerdinand Blomqvist
3074b4f3accSFerdinand Blomqvist if (memcmp(r, c, len * sizeof(*r)))
3084b4f3accSFerdinand Blomqvist stat->dwrong++;
3094b4f3accSFerdinand Blomqvist }
3104b4f3accSFerdinand Blomqvist stat->nwords += trials;
3114b4f3accSFerdinand Blomqvist }
3124b4f3accSFerdinand Blomqvist
ex_rs_helper(struct rs_control * rs,struct wspace * ws,int len,int trials,int method)313ede7c247SYueHaibing static int ex_rs_helper(struct rs_control *rs, struct wspace *ws,
3144b4f3accSFerdinand Blomqvist int len, int trials, int method)
3154b4f3accSFerdinand Blomqvist {
3164b4f3accSFerdinand Blomqvist static const char * const desc[] = {
3174b4f3accSFerdinand Blomqvist "Testing correction buffer interface...",
3184b4f3accSFerdinand Blomqvist "Testing with caller provided syndrome...",
3194b4f3accSFerdinand Blomqvist "Testing in-place interface..."
3204b4f3accSFerdinand Blomqvist };
3214b4f3accSFerdinand Blomqvist
3224b4f3accSFerdinand Blomqvist struct estat stat = {0, 0, 0, 0};
3234b4f3accSFerdinand Blomqvist int nroots = rs->codec->nroots;
3244b4f3accSFerdinand Blomqvist int errs, eras, retval;
3254b4f3accSFerdinand Blomqvist
3264b4f3accSFerdinand Blomqvist if (v >= V_PROGRESS)
3274b4f3accSFerdinand Blomqvist pr_info(" %s\n", desc[method]);
3284b4f3accSFerdinand Blomqvist
3294b4f3accSFerdinand Blomqvist for (errs = 0; errs <= nroots / 2; errs++)
3304b4f3accSFerdinand Blomqvist for (eras = 0; eras <= nroots - 2 * errs; eras++)
3314b4f3accSFerdinand Blomqvist test_uc(rs, len, errs, eras, trials, &stat, ws, method);
3324b4f3accSFerdinand Blomqvist
3334b4f3accSFerdinand Blomqvist if (v >= V_CSUMMARY) {
3344b4f3accSFerdinand Blomqvist pr_info(" Decodes wrong: %d / %d\n",
3354b4f3accSFerdinand Blomqvist stat.dwrong, stat.nwords);
3364b4f3accSFerdinand Blomqvist pr_info(" Wrong return value: %d / %d\n",
3374b4f3accSFerdinand Blomqvist stat.irv, stat.nwords);
3384b4f3accSFerdinand Blomqvist if (method != IN_PLACE)
3394b4f3accSFerdinand Blomqvist pr_info(" Wrong error position: %d\n", stat.wepos);
3404b4f3accSFerdinand Blomqvist }
3414b4f3accSFerdinand Blomqvist
3424b4f3accSFerdinand Blomqvist retval = stat.dwrong + stat.wepos + stat.irv;
3434b4f3accSFerdinand Blomqvist if (retval && v >= V_PROGRESS)
3444b4f3accSFerdinand Blomqvist pr_warn(" FAIL: %d decoding failures!\n", retval);
3454b4f3accSFerdinand Blomqvist
3464b4f3accSFerdinand Blomqvist return retval;
3474b4f3accSFerdinand Blomqvist }
3484b4f3accSFerdinand Blomqvist
exercise_rs(struct rs_control * rs,struct wspace * ws,int len,int trials)349ede7c247SYueHaibing static int exercise_rs(struct rs_control *rs, struct wspace *ws,
3504b4f3accSFerdinand Blomqvist int len, int trials)
3514b4f3accSFerdinand Blomqvist {
3524b4f3accSFerdinand Blomqvist
3534b4f3accSFerdinand Blomqvist int retval = 0;
3544b4f3accSFerdinand Blomqvist int i;
3554b4f3accSFerdinand Blomqvist
3564b4f3accSFerdinand Blomqvist if (v >= V_PROGRESS)
3574b4f3accSFerdinand Blomqvist pr_info("Testing up to error correction capacity...\n");
3584b4f3accSFerdinand Blomqvist
3594b4f3accSFerdinand Blomqvist for (i = 0; i <= IN_PLACE; i++)
3604b4f3accSFerdinand Blomqvist retval |= ex_rs_helper(rs, ws, len, trials, i);
3614b4f3accSFerdinand Blomqvist
3624b4f3accSFerdinand Blomqvist return retval;
3634b4f3accSFerdinand Blomqvist }
3644b4f3accSFerdinand Blomqvist
3654b4f3accSFerdinand Blomqvist /* Tests for correct behaviour beyond error correction capacity */
test_bc(struct rs_control * rs,int len,int errs,int eras,int trials,struct bcstat * stat,struct wspace * ws)3664b4f3accSFerdinand Blomqvist static void test_bc(struct rs_control *rs, int len, int errs,
3674b4f3accSFerdinand Blomqvist int eras, int trials, struct bcstat *stat,
3684b4f3accSFerdinand Blomqvist struct wspace *ws)
3694b4f3accSFerdinand Blomqvist {
3704b4f3accSFerdinand Blomqvist int nroots = rs->codec->nroots;
3714b4f3accSFerdinand Blomqvist int dlen = len - nroots;
3724b4f3accSFerdinand Blomqvist int *derrlocs = ws->derrlocs;
3734b4f3accSFerdinand Blomqvist uint16_t *corr = ws->corr;
3744b4f3accSFerdinand Blomqvist uint16_t *r = ws->r;
3754b4f3accSFerdinand Blomqvist int derrs, j;
3764b4f3accSFerdinand Blomqvist
3774b4f3accSFerdinand Blomqvist for (j = 0; j < trials; j++) {
3784b4f3accSFerdinand Blomqvist get_rcw_we(rs, ws, len, errs, eras);
3794b4f3accSFerdinand Blomqvist derrs = decode_rs16(rs, r, r + dlen, dlen,
3804b4f3accSFerdinand Blomqvist NULL, eras, derrlocs, 0, corr);
3814b4f3accSFerdinand Blomqvist fix_err(r, derrs, corr, derrlocs);
3824b4f3accSFerdinand Blomqvist
3834b4f3accSFerdinand Blomqvist if (derrs >= 0) {
3844b4f3accSFerdinand Blomqvist stat->rsuccess++;
3854b4f3accSFerdinand Blomqvist
3864b4f3accSFerdinand Blomqvist /*
3874b4f3accSFerdinand Blomqvist * We check that the returned word is actually a
3889dbbc3b9SZhen Lei * codeword. The obvious way to do this would be to
3894b4f3accSFerdinand Blomqvist * compute the syndrome, but we don't want to replicate
3904b4f3accSFerdinand Blomqvist * that code here. However, all the codes are in
3914b4f3accSFerdinand Blomqvist * systematic form, and therefore we can encode the
3924b4f3accSFerdinand Blomqvist * returned word, and see whether the parity changes or
3934b4f3accSFerdinand Blomqvist * not.
3944b4f3accSFerdinand Blomqvist */
3954b4f3accSFerdinand Blomqvist memset(corr, 0, nroots * sizeof(*corr));
3964b4f3accSFerdinand Blomqvist encode_rs16(rs, r, dlen, corr, 0);
3974b4f3accSFerdinand Blomqvist
3984b4f3accSFerdinand Blomqvist if (memcmp(r + dlen, corr, nroots * sizeof(*corr)))
3994b4f3accSFerdinand Blomqvist stat->noncw++;
4004b4f3accSFerdinand Blomqvist } else {
4014b4f3accSFerdinand Blomqvist stat->rfail++;
4024b4f3accSFerdinand Blomqvist }
4034b4f3accSFerdinand Blomqvist }
4044b4f3accSFerdinand Blomqvist stat->nwords += trials;
4054b4f3accSFerdinand Blomqvist }
4064b4f3accSFerdinand Blomqvist
exercise_rs_bc(struct rs_control * rs,struct wspace * ws,int len,int trials)407ede7c247SYueHaibing static int exercise_rs_bc(struct rs_control *rs, struct wspace *ws,
4084b4f3accSFerdinand Blomqvist int len, int trials)
4094b4f3accSFerdinand Blomqvist {
4104b4f3accSFerdinand Blomqvist struct bcstat stat = {0, 0, 0, 0};
4114b4f3accSFerdinand Blomqvist int nroots = rs->codec->nroots;
4124b4f3accSFerdinand Blomqvist int errs, eras, cutoff;
4134b4f3accSFerdinand Blomqvist
4144b4f3accSFerdinand Blomqvist if (v >= V_PROGRESS)
4154b4f3accSFerdinand Blomqvist pr_info("Testing beyond error correction capacity...\n");
4164b4f3accSFerdinand Blomqvist
4174b4f3accSFerdinand Blomqvist for (errs = 1; errs <= nroots; errs++) {
4184b4f3accSFerdinand Blomqvist eras = nroots - 2 * errs + 1;
4194b4f3accSFerdinand Blomqvist if (eras < 0)
4204b4f3accSFerdinand Blomqvist eras = 0;
4214b4f3accSFerdinand Blomqvist
4224b4f3accSFerdinand Blomqvist cutoff = nroots <= len - errs ? nroots : len - errs;
4234b4f3accSFerdinand Blomqvist for (; eras <= cutoff; eras++)
4244b4f3accSFerdinand Blomqvist test_bc(rs, len, errs, eras, trials, &stat, ws);
4254b4f3accSFerdinand Blomqvist }
4264b4f3accSFerdinand Blomqvist
4274b4f3accSFerdinand Blomqvist if (v >= V_CSUMMARY) {
4284b4f3accSFerdinand Blomqvist pr_info(" decoder gives up: %d / %d\n",
4294b4f3accSFerdinand Blomqvist stat.rfail, stat.nwords);
4304b4f3accSFerdinand Blomqvist pr_info(" decoder returns success: %d / %d\n",
4314b4f3accSFerdinand Blomqvist stat.rsuccess, stat.nwords);
4324b4f3accSFerdinand Blomqvist pr_info(" not a codeword: %d / %d\n",
4334b4f3accSFerdinand Blomqvist stat.noncw, stat.rsuccess);
4344b4f3accSFerdinand Blomqvist }
4354b4f3accSFerdinand Blomqvist
4364b4f3accSFerdinand Blomqvist if (stat.noncw && v >= V_PROGRESS)
4374b4f3accSFerdinand Blomqvist pr_warn(" FAIL: %d silent failures!\n", stat.noncw);
4384b4f3accSFerdinand Blomqvist
4394b4f3accSFerdinand Blomqvist return stat.noncw;
4404b4f3accSFerdinand Blomqvist }
4414b4f3accSFerdinand Blomqvist
run_exercise(struct etab * e)4424b4f3accSFerdinand Blomqvist static int run_exercise(struct etab *e)
4434b4f3accSFerdinand Blomqvist {
4444b4f3accSFerdinand Blomqvist int nn = (1 << e->symsize) - 1;
4454b4f3accSFerdinand Blomqvist int kk = nn - e->nroots;
4464b4f3accSFerdinand Blomqvist struct rs_control *rsc;
4474b4f3accSFerdinand Blomqvist int retval = -ENOMEM;
4484b4f3accSFerdinand Blomqvist int max_pad = kk - 1;
4494b4f3accSFerdinand Blomqvist int prev_pad = -1;
4504b4f3accSFerdinand Blomqvist struct wspace *ws;
4514b4f3accSFerdinand Blomqvist int i;
4524b4f3accSFerdinand Blomqvist
4534b4f3accSFerdinand Blomqvist rsc = init_rs(e->symsize, e->genpoly, e->fcs, e->prim, e->nroots);
4544b4f3accSFerdinand Blomqvist if (!rsc)
4554b4f3accSFerdinand Blomqvist return retval;
4564b4f3accSFerdinand Blomqvist
4574b4f3accSFerdinand Blomqvist ws = alloc_ws(rsc->codec);
4584b4f3accSFerdinand Blomqvist if (!ws)
4594b4f3accSFerdinand Blomqvist goto err;
4604b4f3accSFerdinand Blomqvist
4614b4f3accSFerdinand Blomqvist retval = 0;
4624b4f3accSFerdinand Blomqvist for (i = 0; i < ARRAY_SIZE(pad_coef); i++) {
4634b4f3accSFerdinand Blomqvist int pad = (pad_coef[i].mult * max_pad) >> pad_coef[i].shift;
4644b4f3accSFerdinand Blomqvist int len = nn - pad;
4654b4f3accSFerdinand Blomqvist
4664b4f3accSFerdinand Blomqvist if (pad == prev_pad)
4674b4f3accSFerdinand Blomqvist continue;
4684b4f3accSFerdinand Blomqvist
4694b4f3accSFerdinand Blomqvist prev_pad = pad;
4704b4f3accSFerdinand Blomqvist if (v >= V_PROGRESS) {
4714b4f3accSFerdinand Blomqvist pr_info("Testing (%d,%d)_%d code...\n",
4724b4f3accSFerdinand Blomqvist len, kk - pad, nn + 1);
4734b4f3accSFerdinand Blomqvist }
4744b4f3accSFerdinand Blomqvist
4754b4f3accSFerdinand Blomqvist retval |= exercise_rs(rsc, ws, len, e->ntrials);
4764b4f3accSFerdinand Blomqvist if (bc)
4774b4f3accSFerdinand Blomqvist retval |= exercise_rs_bc(rsc, ws, len, e->ntrials);
4784b4f3accSFerdinand Blomqvist }
4794b4f3accSFerdinand Blomqvist
4804b4f3accSFerdinand Blomqvist free_ws(ws);
4814b4f3accSFerdinand Blomqvist
4824b4f3accSFerdinand Blomqvist err:
4834b4f3accSFerdinand Blomqvist free_rs(rsc);
4844b4f3accSFerdinand Blomqvist return retval;
4854b4f3accSFerdinand Blomqvist }
4864b4f3accSFerdinand Blomqvist
test_rslib_init(void)4874b4f3accSFerdinand Blomqvist static int __init test_rslib_init(void)
4884b4f3accSFerdinand Blomqvist {
4894b4f3accSFerdinand Blomqvist int i, fail = 0;
4904b4f3accSFerdinand Blomqvist
4914b4f3accSFerdinand Blomqvist for (i = 0; Tab[i].symsize != 0 ; i++) {
4924b4f3accSFerdinand Blomqvist int retval;
4934b4f3accSFerdinand Blomqvist
4944b4f3accSFerdinand Blomqvist retval = run_exercise(Tab + i);
4954b4f3accSFerdinand Blomqvist if (retval < 0)
4964b4f3accSFerdinand Blomqvist return -ENOMEM;
4974b4f3accSFerdinand Blomqvist
4984b4f3accSFerdinand Blomqvist fail |= retval;
4994b4f3accSFerdinand Blomqvist }
5004b4f3accSFerdinand Blomqvist
5014b4f3accSFerdinand Blomqvist if (fail)
5024b4f3accSFerdinand Blomqvist pr_warn("rslib: test failed\n");
5034b4f3accSFerdinand Blomqvist else
5044b4f3accSFerdinand Blomqvist pr_info("rslib: test ok\n");
5054b4f3accSFerdinand Blomqvist
5064b4f3accSFerdinand Blomqvist return -EAGAIN; /* Fail will directly unload the module */
5074b4f3accSFerdinand Blomqvist }
5084b4f3accSFerdinand Blomqvist
test_rslib_exit(void)5094b4f3accSFerdinand Blomqvist static void __exit test_rslib_exit(void)
5104b4f3accSFerdinand Blomqvist {
5114b4f3accSFerdinand Blomqvist }
5124b4f3accSFerdinand Blomqvist
5134b4f3accSFerdinand Blomqvist module_init(test_rslib_init)
5144b4f3accSFerdinand Blomqvist module_exit(test_rslib_exit)
5154b4f3accSFerdinand Blomqvist
5164b4f3accSFerdinand Blomqvist MODULE_LICENSE("GPL");
5174b4f3accSFerdinand Blomqvist MODULE_AUTHOR("Ferdinand Blomqvist");
5184b4f3accSFerdinand Blomqvist MODULE_DESCRIPTION("Reed-Solomon library test");
519