test_rslib.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518
  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. enum verbosity {
  15. V_SILENT,
  16. V_PROGRESS,
  17. V_CSUMMARY
  18. };
  19. enum method {
  20. CORR_BUFFER,
  21. CALLER_SYNDROME,
  22. IN_PLACE
  23. };
  24. #define __param(type, name, init, msg) \
  25. static type name = init; \
  26. module_param(name, type, 0444); \
  27. MODULE_PARM_DESC(name, msg)
  28. __param(int, v, V_PROGRESS, "Verbosity level");
  29. __param(int, ewsc, 1, "Erasures without symbol corruption");
  30. __param(int, bc, 1, "Test for correct behaviour beyond error correction capacity");
  31. struct etab {
  32. int symsize;
  33. int genpoly;
  34. int fcs;
  35. int prim;
  36. int nroots;
  37. int ntrials;
  38. };
  39. /* List of codes to test */
  40. static struct etab Tab[] = {
  41. {2, 0x7, 1, 1, 1, 100000 },
  42. {3, 0xb, 1, 1, 2, 100000 },
  43. {3, 0xb, 1, 1, 3, 100000 },
  44. {3, 0xb, 2, 1, 4, 100000 },
  45. {4, 0x13, 1, 1, 4, 10000 },
  46. {5, 0x25, 1, 1, 6, 1000 },
  47. {6, 0x43, 3, 1, 8, 1000 },
  48. {7, 0x89, 1, 1, 14, 500 },
  49. {8, 0x11d, 1, 1, 30, 100 },
  50. {8, 0x187, 112, 11, 32, 100 },
  51. {9, 0x211, 1, 1, 33, 80 },
  52. {0, 0, 0, 0, 0, 0},
  53. };
  54. struct estat {
  55. int dwrong;
  56. int irv;
  57. int wepos;
  58. int nwords;
  59. };
  60. struct bcstat {
  61. int rfail;
  62. int rsuccess;
  63. int noncw;
  64. int nwords;
  65. };
  66. struct wspace {
  67. uint16_t *c; /* sent codeword */
  68. uint16_t *r; /* received word */
  69. uint16_t *s; /* syndrome */
  70. uint16_t *corr; /* correction buffer */
  71. int *errlocs;
  72. int *derrlocs;
  73. };
  74. struct pad {
  75. int mult;
  76. int shift;
  77. };
  78. static struct pad pad_coef[] = {
  79. { 0, 0 },
  80. { 1, 2 },
  81. { 1, 1 },
  82. { 3, 2 },
  83. { 1, 0 },
  84. };
  85. static void free_ws(struct wspace *ws)
  86. {
  87. if (!ws)
  88. return;
  89. kfree(ws->errlocs);
  90. kfree(ws->c);
  91. kfree(ws);
  92. }
  93. static struct wspace *alloc_ws(struct rs_codec *rs)
  94. {
  95. int nroots = rs->nroots;
  96. struct wspace *ws;
  97. int nn = rs->nn;
  98. ws = kzalloc(sizeof(*ws), GFP_KERNEL);
  99. if (!ws)
  100. return NULL;
  101. ws->c = kmalloc_array(2 * (nn + nroots),
  102. sizeof(uint16_t), GFP_KERNEL);
  103. if (!ws->c)
  104. goto err;
  105. ws->r = ws->c + nn;
  106. ws->s = ws->r + nn;
  107. ws->corr = ws->s + nroots;
  108. ws->errlocs = kmalloc_array(nn + nroots, sizeof(int), GFP_KERNEL);
  109. if (!ws->errlocs)
  110. goto err;
  111. ws->derrlocs = ws->errlocs + nn;
  112. return ws;
  113. err:
  114. free_ws(ws);
  115. return NULL;
  116. }
  117. /*
  118. * Generates a random codeword and stores it in c. Generates random errors and
  119. * erasures, and stores the random word with errors in r. Erasure positions are
  120. * stored in derrlocs, while errlocs has one of three values in every position:
  121. *
  122. * 0 if there is no error in this position;
  123. * 1 if there is a symbol error in this position;
  124. * 2 if there is an erasure without symbol corruption.
  125. *
  126. * Returns the number of corrupted symbols.
  127. */
  128. static int get_rcw_we(struct rs_control *rs, struct wspace *ws,
  129. int len, int errs, int eras)
  130. {
  131. int nroots = rs->codec->nroots;
  132. int *derrlocs = ws->derrlocs;
  133. int *errlocs = ws->errlocs;
  134. int dlen = len - nroots;
  135. int nn = rs->codec->nn;
  136. uint16_t *c = ws->c;
  137. uint16_t *r = ws->r;
  138. int errval;
  139. int errloc;
  140. int i;
  141. /* Load c with random data and encode */
  142. for (i = 0; i < dlen; i++)
  143. c[i] = prandom_u32() & nn;
  144. memset(c + dlen, 0, nroots * sizeof(*c));
  145. encode_rs16(rs, c, dlen, c + dlen, 0);
  146. /* Make copyand add errors and erasures */
  147. memcpy(r, c, len * sizeof(*r));
  148. memset(errlocs, 0, len * sizeof(*errlocs));
  149. memset(derrlocs, 0, nroots * sizeof(*derrlocs));
  150. /* Generating random errors */
  151. for (i = 0; i < errs; i++) {
  152. do {
  153. /* Error value must be nonzero */
  154. errval = prandom_u32() & nn;
  155. } while (errval == 0);
  156. do {
  157. /* Must not choose the same location twice */
  158. errloc = prandom_u32() % len;
  159. } while (errlocs[errloc] != 0);
  160. errlocs[errloc] = 1;
  161. r[errloc] ^= errval;
  162. }
  163. /* Generating random erasures */
  164. for (i = 0; i < eras; i++) {
  165. do {
  166. /* Must not choose the same location twice */
  167. errloc = prandom_u32() % len;
  168. } while (errlocs[errloc] != 0);
  169. derrlocs[i] = errloc;
  170. if (ewsc && (prandom_u32() & 1)) {
  171. /* Erasure with the symbol intact */
  172. errlocs[errloc] = 2;
  173. } else {
  174. /* Erasure with corrupted symbol */
  175. do {
  176. /* Error value must be nonzero */
  177. errval = prandom_u32() & nn;
  178. } while (errval == 0);
  179. errlocs[errloc] = 1;
  180. r[errloc] ^= errval;
  181. errs++;
  182. }
  183. }
  184. return errs;
  185. }
  186. static void fix_err(uint16_t *data, int nerrs, uint16_t *corr, int *errlocs)
  187. {
  188. int i;
  189. for (i = 0; i < nerrs; i++)
  190. data[errlocs[i]] ^= corr[i];
  191. }
  192. static void compute_syndrome(struct rs_control *rsc, uint16_t *data,
  193. int len, uint16_t *syn)
  194. {
  195. struct rs_codec *rs = rsc->codec;
  196. uint16_t *alpha_to = rs->alpha_to;
  197. uint16_t *index_of = rs->index_of;
  198. int nroots = rs->nroots;
  199. int prim = rs->prim;
  200. int fcr = rs->fcr;
  201. int i, j;
  202. /* Calculating syndrome */
  203. for (i = 0; i < nroots; i++) {
  204. syn[i] = data[0];
  205. for (j = 1; j < len; j++) {
  206. if (syn[i] == 0) {
  207. syn[i] = data[j];
  208. } else {
  209. syn[i] = data[j] ^
  210. alpha_to[rs_modnn(rs, index_of[syn[i]]
  211. + (fcr + i) * prim)];
  212. }
  213. }
  214. }
  215. /* Convert to index form */
  216. for (i = 0; i < nroots; i++)
  217. syn[i] = rs->index_of[syn[i]];
  218. }
  219. /* Test up to error correction capacity */
  220. static void test_uc(struct rs_control *rs, int len, int errs,
  221. int eras, int trials, struct estat *stat,
  222. struct wspace *ws, int method)
  223. {
  224. int dlen = len - rs->codec->nroots;
  225. int *derrlocs = ws->derrlocs;
  226. int *errlocs = ws->errlocs;
  227. uint16_t *corr = ws->corr;
  228. uint16_t *c = ws->c;
  229. uint16_t *r = ws->r;
  230. uint16_t *s = ws->s;
  231. int derrs, nerrs;
  232. int i, j;
  233. for (j = 0; j < trials; j++) {
  234. nerrs = get_rcw_we(rs, ws, len, errs, eras);
  235. switch (method) {
  236. case CORR_BUFFER:
  237. derrs = decode_rs16(rs, r, r + dlen, dlen,
  238. NULL, eras, derrlocs, 0, corr);
  239. fix_err(r, derrs, corr, derrlocs);
  240. break;
  241. case CALLER_SYNDROME:
  242. compute_syndrome(rs, r, len, s);
  243. derrs = decode_rs16(rs, NULL, NULL, dlen,
  244. s, eras, derrlocs, 0, corr);
  245. fix_err(r, derrs, corr, derrlocs);
  246. break;
  247. case IN_PLACE:
  248. derrs = decode_rs16(rs, r, r + dlen, dlen,
  249. NULL, eras, derrlocs, 0, NULL);
  250. break;
  251. default:
  252. continue;
  253. }
  254. if (derrs != nerrs)
  255. stat->irv++;
  256. if (method != IN_PLACE) {
  257. for (i = 0; i < derrs; i++) {
  258. if (errlocs[derrlocs[i]] != 1)
  259. stat->wepos++;
  260. }
  261. }
  262. if (memcmp(r, c, len * sizeof(*r)))
  263. stat->dwrong++;
  264. }
  265. stat->nwords += trials;
  266. }
  267. static int ex_rs_helper(struct rs_control *rs, struct wspace *ws,
  268. int len, int trials, int method)
  269. {
  270. static const char * const desc[] = {
  271. "Testing correction buffer interface...",
  272. "Testing with caller provided syndrome...",
  273. "Testing in-place interface..."
  274. };
  275. struct estat stat = {0, 0, 0, 0};
  276. int nroots = rs->codec->nroots;
  277. int errs, eras, retval;
  278. if (v >= V_PROGRESS)
  279. pr_info(" %s\n", desc[method]);
  280. for (errs = 0; errs <= nroots / 2; errs++)
  281. for (eras = 0; eras <= nroots - 2 * errs; eras++)
  282. test_uc(rs, len, errs, eras, trials, &stat, ws, method);
  283. if (v >= V_CSUMMARY) {
  284. pr_info(" Decodes wrong: %d / %d\n",
  285. stat.dwrong, stat.nwords);
  286. pr_info(" Wrong return value: %d / %d\n",
  287. stat.irv, stat.nwords);
  288. if (method != IN_PLACE)
  289. pr_info(" Wrong error position: %d\n", stat.wepos);
  290. }
  291. retval = stat.dwrong + stat.wepos + stat.irv;
  292. if (retval && v >= V_PROGRESS)
  293. pr_warn(" FAIL: %d decoding failures!\n", retval);
  294. return retval;
  295. }
  296. static int exercise_rs(struct rs_control *rs, struct wspace *ws,
  297. int len, int trials)
  298. {
  299. int retval = 0;
  300. int i;
  301. if (v >= V_PROGRESS)
  302. pr_info("Testing up to error correction capacity...\n");
  303. for (i = 0; i <= IN_PLACE; i++)
  304. retval |= ex_rs_helper(rs, ws, len, trials, i);
  305. return retval;
  306. }
  307. /* Tests for correct behaviour beyond error correction capacity */
  308. static void test_bc(struct rs_control *rs, int len, int errs,
  309. int eras, int trials, struct bcstat *stat,
  310. struct wspace *ws)
  311. {
  312. int nroots = rs->codec->nroots;
  313. int dlen = len - nroots;
  314. int *derrlocs = ws->derrlocs;
  315. uint16_t *corr = ws->corr;
  316. uint16_t *r = ws->r;
  317. int derrs, j;
  318. for (j = 0; j < trials; j++) {
  319. get_rcw_we(rs, ws, len, errs, eras);
  320. derrs = decode_rs16(rs, r, r + dlen, dlen,
  321. NULL, eras, derrlocs, 0, corr);
  322. fix_err(r, derrs, corr, derrlocs);
  323. if (derrs >= 0) {
  324. stat->rsuccess++;
  325. /*
  326. * We check that the returned word is actually a
  327. * codeword. The obious way to do this would be to
  328. * compute the syndrome, but we don't want to replicate
  329. * that code here. However, all the codes are in
  330. * systematic form, and therefore we can encode the
  331. * returned word, and see whether the parity changes or
  332. * not.
  333. */
  334. memset(corr, 0, nroots * sizeof(*corr));
  335. encode_rs16(rs, r, dlen, corr, 0);
  336. if (memcmp(r + dlen, corr, nroots * sizeof(*corr)))
  337. stat->noncw++;
  338. } else {
  339. stat->rfail++;
  340. }
  341. }
  342. stat->nwords += trials;
  343. }
  344. static int exercise_rs_bc(struct rs_control *rs, struct wspace *ws,
  345. int len, int trials)
  346. {
  347. struct bcstat stat = {0, 0, 0, 0};
  348. int nroots = rs->codec->nroots;
  349. int errs, eras, cutoff;
  350. if (v >= V_PROGRESS)
  351. pr_info("Testing beyond error correction capacity...\n");
  352. for (errs = 1; errs <= nroots; errs++) {
  353. eras = nroots - 2 * errs + 1;
  354. if (eras < 0)
  355. eras = 0;
  356. cutoff = nroots <= len - errs ? nroots : len - errs;
  357. for (; eras <= cutoff; eras++)
  358. test_bc(rs, len, errs, eras, trials, &stat, ws);
  359. }
  360. if (v >= V_CSUMMARY) {
  361. pr_info(" decoder gives up: %d / %d\n",
  362. stat.rfail, stat.nwords);
  363. pr_info(" decoder returns success: %d / %d\n",
  364. stat.rsuccess, stat.nwords);
  365. pr_info(" not a codeword: %d / %d\n",
  366. stat.noncw, stat.rsuccess);
  367. }
  368. if (stat.noncw && v >= V_PROGRESS)
  369. pr_warn(" FAIL: %d silent failures!\n", stat.noncw);
  370. return stat.noncw;
  371. }
  372. static int run_exercise(struct etab *e)
  373. {
  374. int nn = (1 << e->symsize) - 1;
  375. int kk = nn - e->nroots;
  376. struct rs_control *rsc;
  377. int retval = -ENOMEM;
  378. int max_pad = kk - 1;
  379. int prev_pad = -1;
  380. struct wspace *ws;
  381. int i;
  382. rsc = init_rs(e->symsize, e->genpoly, e->fcs, e->prim, e->nroots);
  383. if (!rsc)
  384. return retval;
  385. ws = alloc_ws(rsc->codec);
  386. if (!ws)
  387. goto err;
  388. retval = 0;
  389. for (i = 0; i < ARRAY_SIZE(pad_coef); i++) {
  390. int pad = (pad_coef[i].mult * max_pad) >> pad_coef[i].shift;
  391. int len = nn - pad;
  392. if (pad == prev_pad)
  393. continue;
  394. prev_pad = pad;
  395. if (v >= V_PROGRESS) {
  396. pr_info("Testing (%d,%d)_%d code...\n",
  397. len, kk - pad, nn + 1);
  398. }
  399. retval |= exercise_rs(rsc, ws, len, e->ntrials);
  400. if (bc)
  401. retval |= exercise_rs_bc(rsc, ws, len, e->ntrials);
  402. }
  403. free_ws(ws);
  404. err:
  405. free_rs(rsc);
  406. return retval;
  407. }
  408. static int __init test_rslib_init(void)
  409. {
  410. int i, fail = 0;
  411. for (i = 0; Tab[i].symsize != 0 ; i++) {
  412. int retval;
  413. retval = run_exercise(Tab + i);
  414. if (retval < 0)
  415. return -ENOMEM;
  416. fail |= retval;
  417. }
  418. if (fail)
  419. pr_warn("rslib: test failed\n");
  420. else
  421. pr_info("rslib: test ok\n");
  422. return -EAGAIN; /* Fail will directly unload the module */
  423. }
  424. static void __exit test_rslib_exit(void)
  425. {
  426. }
  427. module_init(test_rslib_init)
  428. module_exit(test_rslib_exit)
  429. MODULE_LICENSE("GPL");
  430. MODULE_AUTHOR("Ferdinand Blomqvist");
  431. MODULE_DESCRIPTION("Reed-Solomon library test");