Commit | Line | Data |
---|---|---|
4b4f3acc FB |
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++) | |
a251c17a | 167 | c[i] = get_random_u32() & nn; |
4b4f3acc FB |
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 */ | |
a251c17a | 181 | errval = get_random_u32() & nn; |
4b4f3acc FB |
182 | } while (errval == 0); |
183 | ||
184 | do { | |
185 | /* Must not choose the same location twice */ | |
8032bf12 | 186 | errloc = get_random_u32_below(len); |
4b4f3acc FB |
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 */ | |
8032bf12 | 197 | errloc = get_random_u32_below(len); |
4b4f3acc FB |
198 | } while (errlocs[errloc] != 0); |
199 | ||
200 | derrlocs[i] = errloc; | |
201 | ||
8032bf12 | 202 | if (ewsc && get_random_u32_below(2)) { |
4b4f3acc FB |
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 */ | |
a251c17a | 209 | errval = get_random_u32() & nn; |
4b4f3acc FB |
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 | ||
ede7c247 Y |
313 | static int ex_rs_helper(struct rs_control *rs, struct wspace *ws, |
314 | int len, int trials, int method) | |
4b4f3acc FB |
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 | ||
ede7c247 Y |
349 | static int exercise_rs(struct rs_control *rs, struct wspace *ws, |
350 | int len, int trials) | |
4b4f3acc FB |
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 | |
9dbbc3b9 | 388 | * codeword. The obvious way to do this would be to |
4b4f3acc FB |
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 | ||
ede7c247 Y |
407 | static int exercise_rs_bc(struct rs_control *rs, struct wspace *ws, |
408 | int len, int trials) | |
4b4f3acc FB |
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"); |