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(objp: ws->errlocs); |
104 | kfree(objp: ws->c); |
105 | kfree(objp: 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(size: sizeof(*ws), GFP_KERNEL); |
115 | if (!ws) |
116 | return NULL; |
117 | |
118 | ws->c = kmalloc_array(n: 2 * (nn + nroots), |
119 | size: 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(n: nn + nroots, size: 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, data: c, len: dlen, par: c + dlen, invmsk: 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(ceil: 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(ceil: len); |
198 | } while (errlocs[errloc] != 0); |
199 | |
200 | derrlocs[i] = errloc; |
201 | |
202 | if (ewsc && get_random_u32_below(ceil: 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, x: 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, data: r, par: r + dlen, len: dlen, |
280 | NULL, no_eras: eras, eras_pos: derrlocs, invmsk: 0, corr); |
281 | fix_err(data: r, nerrs: derrs, corr, errlocs: derrlocs); |
282 | break; |
283 | case CALLER_SYNDROME: |
284 | compute_syndrome(rsc: rs, data: r, len, syn: s); |
285 | derrs = decode_rs16(rs, NULL, NULL, len: dlen, |
286 | s, no_eras: eras, eras_pos: derrlocs, invmsk: 0, corr); |
287 | fix_err(data: r, nerrs: derrs, corr, errlocs: derrlocs); |
288 | break; |
289 | case IN_PLACE: |
290 | derrs = decode_rs16(rs, data: r, par: r + dlen, len: dlen, |
291 | NULL, no_eras: eras, eras_pos: derrlocs, invmsk: 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(p: r, q: c, size: 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: &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, method: 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, data: r, par: r + dlen, len: dlen, |
380 | NULL, no_eras: eras, eras_pos: derrlocs, invmsk: 0, corr); |
381 | fix_err(data: r, nerrs: derrs, corr, errlocs: 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, data: r, len: dlen, par: corr, invmsk: 0); |
397 | |
398 | if (memcmp(p: r + dlen, q: corr, size: 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: &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(symsize: e->symsize, gfpoly: e->genpoly, fcr: e->fcs, prim: e->prim, nroots: e->nroots); |
454 | if (!rsc) |
455 | return retval; |
456 | |
457 | ws = alloc_ws(rs: 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(rs: rsc, ws, len, trials: e->ntrials); |
476 | if (bc) |
477 | retval |= exercise_rs_bc(rs: rsc, ws, len, trials: e->ntrials); |
478 | } |
479 | |
480 | free_ws(ws); |
481 | |
482 | err: |
483 | free_rs(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(e: 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 | |