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");
519
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.