xref: /openbmc/linux/lib/reed_solomon/test_rslib.c (revision 8032bf12)
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 
free_ws(struct wspace * ws)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 
alloc_ws(struct rs_codec * rs)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  */
get_rcw_we(struct rs_control * rs,struct wspace * ws,int len,int errs,int eras)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 
fix_err(uint16_t * data,int nerrs,uint16_t * corr,int * errlocs)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 
compute_syndrome(struct rs_control * rsc,uint16_t * data,int len,uint16_t * syn)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 */
test_uc(struct rs_control * rs,int len,int errs,int eras,int trials,struct estat * stat,struct wspace * ws,int method)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 
ex_rs_helper(struct rs_control * rs,struct wspace * ws,int len,int trials,int method)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 
exercise_rs(struct rs_control * rs,struct wspace * ws,int len,int trials)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 */
test_bc(struct rs_control * rs,int len,int errs,int eras,int trials,struct bcstat * stat,struct wspace * ws)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 
exercise_rs_bc(struct rs_control * rs,struct wspace * ws,int len,int trials)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 
run_exercise(struct etab * e)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 
test_rslib_init(void)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 
test_rslib_exit(void)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