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
15enum verbosity {
16	V_SILENT,
17	V_PROGRESS,
18	V_CSUMMARY
19};
20
21enum 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
36struct 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 */
46static 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
62struct estat {
63	int	dwrong;
64	int	irv;
65	int	wepos;
66	int	nwords;
67};
68
69struct bcstat {
70	int	rfail;
71	int	rsuccess;
72	int	noncw;
73	int	nwords;
74};
75
76struct 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
85struct pad {
86	int	mult;
87	int	shift;
88};
89
90static struct pad pad_coef[] = {
91	{ 0, 0 },
92	{ 1, 2 },
93	{ 1, 1 },
94	{ 3, 2 },
95	{ 1, 0 },
96};
97
98static 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
108static 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
134err:
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 */
151static 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
221static 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
229static 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 */
260static 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
313static 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
349static 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 */
366static 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
407static 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
442static 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
482err:
483	free_rs(rsc);
484	return retval;
485}
486
487static 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
509static void __exit test_rslib_exit(void)
510{
511}
512
513module_init(test_rslib_init)
514module_exit(test_rslib_exit)
515
516MODULE_LICENSE("GPL");
517MODULE_AUTHOR("Ferdinand Blomqvist");
518MODULE_DESCRIPTION("Reed-Solomon library test");
519