reed_solomon.c 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * Generic Reed Solomon encoder / decoder library
  4. *
  5. * Copyright (C) 2004 Thomas Gleixner (tglx@linutronix.de)
  6. *
  7. * Reed Solomon code lifted from reed solomon library written by Phil Karn
  8. * Copyright 2002 Phil Karn, KA9Q
  9. *
  10. * Description:
  11. *
  12. * The generic Reed Solomon library provides runtime configurable
  13. * encoding / decoding of RS codes.
  14. *
  15. * Each user must call init_rs to get a pointer to a rs_control structure
  16. * for the given rs parameters. The control struct is unique per instance.
  17. * It points to a codec which can be shared by multiple control structures.
  18. * If a codec is newly allocated then the polynomial arrays for fast
  19. * encoding / decoding are built. This can take some time so make sure not
  20. * to call this function from a time critical path. Usually a module /
  21. * driver should initialize the necessary rs_control structure on module /
  22. * driver init and release it on exit.
  23. *
  24. * The encoding puts the calculated syndrome into a given syndrome buffer.
  25. *
  26. * The decoding is a two step process. The first step calculates the
  27. * syndrome over the received (data + syndrome) and calls the second stage,
  28. * which does the decoding / error correction itself. Many hw encoders
  29. * provide a syndrome calculation over the received data + syndrome and can
  30. * call the second stage directly.
  31. */
  32. #include <linux/errno.h>
  33. #include <linux/kernel.h>
  34. #include <linux/init.h>
  35. #include <linux/module.h>
  36. #include <linux/rslib.h>
  37. #include <linux/slab.h>
  38. #include <linux/mutex.h>
  39. enum {
  40. RS_DECODE_LAMBDA,
  41. RS_DECODE_SYN,
  42. RS_DECODE_B,
  43. RS_DECODE_T,
  44. RS_DECODE_OMEGA,
  45. RS_DECODE_ROOT,
  46. RS_DECODE_REG,
  47. RS_DECODE_LOC,
  48. RS_DECODE_NUM_BUFFERS
  49. };
  50. /* This list holds all currently allocated rs codec structures */
  51. static LIST_HEAD(codec_list);
  52. /* Protection for the list */
  53. static DEFINE_MUTEX(rslistlock);
  54. /**
  55. * codec_init - Initialize a Reed-Solomon codec
  56. * @symsize: symbol size, bits (1-8)
  57. * @gfpoly: Field generator polynomial coefficients
  58. * @gffunc: Field generator function
  59. * @fcr: first root of RS code generator polynomial, index form
  60. * @prim: primitive element to generate polynomial roots
  61. * @nroots: RS code generator polynomial degree (number of roots)
  62. * @gfp: GFP_ flags for allocations
  63. *
  64. * Allocate a codec structure and the polynom arrays for faster
  65. * en/decoding. Fill the arrays according to the given parameters.
  66. */
  67. static struct rs_codec *codec_init(int symsize, int gfpoly, int (*gffunc)(int),
  68. int fcr, int prim, int nroots, gfp_t gfp)
  69. {
  70. int i, j, sr, root, iprim;
  71. struct rs_codec *rs;
  72. rs = kzalloc(sizeof(*rs), gfp);
  73. if (!rs)
  74. return NULL;
  75. INIT_LIST_HEAD(&rs->list);
  76. rs->mm = symsize;
  77. rs->nn = (1 << symsize) - 1;
  78. rs->fcr = fcr;
  79. rs->prim = prim;
  80. rs->nroots = nroots;
  81. rs->gfpoly = gfpoly;
  82. rs->gffunc = gffunc;
  83. /* Allocate the arrays */
  84. rs->alpha_to = kmalloc_array(rs->nn + 1, sizeof(uint16_t), gfp);
  85. if (rs->alpha_to == NULL)
  86. goto err;
  87. rs->index_of = kmalloc_array(rs->nn + 1, sizeof(uint16_t), gfp);
  88. if (rs->index_of == NULL)
  89. goto err;
  90. rs->genpoly = kmalloc_array(rs->nroots + 1, sizeof(uint16_t), gfp);
  91. if(rs->genpoly == NULL)
  92. goto err;
  93. /* Generate Galois field lookup tables */
  94. rs->index_of[0] = rs->nn; /* log(zero) = -inf */
  95. rs->alpha_to[rs->nn] = 0; /* alpha**-inf = 0 */
  96. if (gfpoly) {
  97. sr = 1;
  98. for (i = 0; i < rs->nn; i++) {
  99. rs->index_of[sr] = i;
  100. rs->alpha_to[i] = sr;
  101. sr <<= 1;
  102. if (sr & (1 << symsize))
  103. sr ^= gfpoly;
  104. sr &= rs->nn;
  105. }
  106. } else {
  107. sr = gffunc(0);
  108. for (i = 0; i < rs->nn; i++) {
  109. rs->index_of[sr] = i;
  110. rs->alpha_to[i] = sr;
  111. sr = gffunc(sr);
  112. }
  113. }
  114. /* If it's not primitive, exit */
  115. if(sr != rs->alpha_to[0])
  116. goto err;
  117. /* Find prim-th root of 1, used in decoding */
  118. for(iprim = 1; (iprim % prim) != 0; iprim += rs->nn);
  119. /* prim-th root of 1, index form */
  120. rs->iprim = iprim / prim;
  121. /* Form RS code generator polynomial from its roots */
  122. rs->genpoly[0] = 1;
  123. for (i = 0, root = fcr * prim; i < nroots; i++, root += prim) {
  124. rs->genpoly[i + 1] = 1;
  125. /* Multiply rs->genpoly[] by @**(root + x) */
  126. for (j = i; j > 0; j--) {
  127. if (rs->genpoly[j] != 0) {
  128. rs->genpoly[j] = rs->genpoly[j -1] ^
  129. rs->alpha_to[rs_modnn(rs,
  130. rs->index_of[rs->genpoly[j]] + root)];
  131. } else
  132. rs->genpoly[j] = rs->genpoly[j - 1];
  133. }
  134. /* rs->genpoly[0] can never be zero */
  135. rs->genpoly[0] =
  136. rs->alpha_to[rs_modnn(rs,
  137. rs->index_of[rs->genpoly[0]] + root)];
  138. }
  139. /* convert rs->genpoly[] to index form for quicker encoding */
  140. for (i = 0; i <= nroots; i++)
  141. rs->genpoly[i] = rs->index_of[rs->genpoly[i]];
  142. rs->users = 1;
  143. list_add(&rs->list, &codec_list);
  144. return rs;
  145. err:
  146. kfree(rs->genpoly);
  147. kfree(rs->index_of);
  148. kfree(rs->alpha_to);
  149. kfree(rs);
  150. return NULL;
  151. }
  152. /**
  153. * free_rs - Free the rs control structure
  154. * @rs: The control structure which is not longer used by the
  155. * caller
  156. *
  157. * Free the control structure. If @rs is the last user of the associated
  158. * codec, free the codec as well.
  159. */
  160. void free_rs(struct rs_control *rs)
  161. {
  162. struct rs_codec *cd;
  163. if (!rs)
  164. return;
  165. cd = rs->codec;
  166. mutex_lock(&rslistlock);
  167. cd->users--;
  168. if(!cd->users) {
  169. list_del(&cd->list);
  170. kfree(cd->alpha_to);
  171. kfree(cd->index_of);
  172. kfree(cd->genpoly);
  173. kfree(cd);
  174. }
  175. mutex_unlock(&rslistlock);
  176. kfree(rs);
  177. }
  178. EXPORT_SYMBOL_GPL(free_rs);
  179. /**
  180. * init_rs_internal - Allocate rs control, find a matching codec or allocate a new one
  181. * @symsize: the symbol size (number of bits)
  182. * @gfpoly: the extended Galois field generator polynomial coefficients,
  183. * with the 0th coefficient in the low order bit. The polynomial
  184. * must be primitive;
  185. * @gffunc: pointer to function to generate the next field element,
  186. * or the multiplicative identity element if given 0. Used
  187. * instead of gfpoly if gfpoly is 0
  188. * @fcr: the first consecutive root of the rs code generator polynomial
  189. * in index form
  190. * @prim: primitive element to generate polynomial roots
  191. * @nroots: RS code generator polynomial degree (number of roots)
  192. * @gfp: GFP_ flags for allocations
  193. */
  194. static struct rs_control *init_rs_internal(int symsize, int gfpoly,
  195. int (*gffunc)(int), int fcr,
  196. int prim, int nroots, gfp_t gfp)
  197. {
  198. struct list_head *tmp;
  199. struct rs_control *rs;
  200. unsigned int bsize;
  201. /* Sanity checks */
  202. if (symsize < 1)
  203. return NULL;
  204. if (fcr < 0 || fcr >= (1<<symsize))
  205. return NULL;
  206. if (prim <= 0 || prim >= (1<<symsize))
  207. return NULL;
  208. if (nroots < 0 || nroots >= (1<<symsize))
  209. return NULL;
  210. /*
  211. * The decoder needs buffers in each control struct instance to
  212. * avoid variable size or large fixed size allocations on
  213. * stack. Size the buffers to arrays of [nroots + 1].
  214. */
  215. bsize = sizeof(uint16_t) * RS_DECODE_NUM_BUFFERS * (nroots + 1);
  216. rs = kzalloc(sizeof(*rs) + bsize, gfp);
  217. if (!rs)
  218. return NULL;
  219. mutex_lock(&rslistlock);
  220. /* Walk through the list and look for a matching entry */
  221. list_for_each(tmp, &codec_list) {
  222. struct rs_codec *cd = list_entry(tmp, struct rs_codec, list);
  223. if (symsize != cd->mm)
  224. continue;
  225. if (gfpoly != cd->gfpoly)
  226. continue;
  227. if (gffunc != cd->gffunc)
  228. continue;
  229. if (fcr != cd->fcr)
  230. continue;
  231. if (prim != cd->prim)
  232. continue;
  233. if (nroots != cd->nroots)
  234. continue;
  235. /* We have a matching one already */
  236. cd->users++;
  237. rs->codec = cd;
  238. goto out;
  239. }
  240. /* Create a new one */
  241. rs->codec = codec_init(symsize, gfpoly, gffunc, fcr, prim, nroots, gfp);
  242. if (!rs->codec) {
  243. kfree(rs);
  244. rs = NULL;
  245. }
  246. out:
  247. mutex_unlock(&rslistlock);
  248. return rs;
  249. }
  250. /**
  251. * init_rs_gfp - Create a RS control struct and initialize it
  252. * @symsize: the symbol size (number of bits)
  253. * @gfpoly: the extended Galois field generator polynomial coefficients,
  254. * with the 0th coefficient in the low order bit. The polynomial
  255. * must be primitive;
  256. * @fcr: the first consecutive root of the rs code generator polynomial
  257. * in index form
  258. * @prim: primitive element to generate polynomial roots
  259. * @nroots: RS code generator polynomial degree (number of roots)
  260. * @gfp: Memory allocation flags.
  261. */
  262. struct rs_control *init_rs_gfp(int symsize, int gfpoly, int fcr, int prim,
  263. int nroots, gfp_t gfp)
  264. {
  265. return init_rs_internal(symsize, gfpoly, NULL, fcr, prim, nroots, gfp);
  266. }
  267. EXPORT_SYMBOL_GPL(init_rs_gfp);
  268. /**
  269. * init_rs_non_canonical - Allocate rs control struct for fields with
  270. * non-canonical representation
  271. * @symsize: the symbol size (number of bits)
  272. * @gffunc: pointer to function to generate the next field element,
  273. * or the multiplicative identity element if given 0. Used
  274. * instead of gfpoly if gfpoly is 0
  275. * @fcr: the first consecutive root of the rs code generator polynomial
  276. * in index form
  277. * @prim: primitive element to generate polynomial roots
  278. * @nroots: RS code generator polynomial degree (number of roots)
  279. */
  280. struct rs_control *init_rs_non_canonical(int symsize, int (*gffunc)(int),
  281. int fcr, int prim, int nroots)
  282. {
  283. return init_rs_internal(symsize, 0, gffunc, fcr, prim, nroots,
  284. GFP_KERNEL);
  285. }
  286. EXPORT_SYMBOL_GPL(init_rs_non_canonical);
  287. #ifdef CONFIG_REED_SOLOMON_ENC8
  288. /**
  289. * encode_rs8 - Calculate the parity for data values (8bit data width)
  290. * @rsc: the rs control structure
  291. * @data: data field of a given type
  292. * @len: data length
  293. * @par: parity data, must be initialized by caller (usually all 0)
  294. * @invmsk: invert data mask (will be xored on data)
  295. *
  296. * The parity uses a uint16_t data type to enable
  297. * symbol size > 8. The calling code must take care of encoding of the
  298. * syndrome result for storage itself.
  299. */
  300. int encode_rs8(struct rs_control *rsc, uint8_t *data, int len, uint16_t *par,
  301. uint16_t invmsk)
  302. {
  303. #include "encode_rs.c"
  304. }
  305. EXPORT_SYMBOL_GPL(encode_rs8);
  306. #endif
  307. #ifdef CONFIG_REED_SOLOMON_DEC8
  308. /**
  309. * decode_rs8 - Decode codeword (8bit data width)
  310. * @rsc: the rs control structure
  311. * @data: data field of a given type
  312. * @par: received parity data field
  313. * @len: data length
  314. * @s: syndrome data field, must be in index form
  315. * (if NULL, syndrome is calculated)
  316. * @no_eras: number of erasures
  317. * @eras_pos: position of erasures, can be NULL
  318. * @invmsk: invert data mask (will be xored on data, not on parity!)
  319. * @corr: buffer to store correction bitmask on eras_pos
  320. *
  321. * The syndrome and parity uses a uint16_t data type to enable
  322. * symbol size > 8. The calling code must take care of decoding of the
  323. * syndrome result and the received parity before calling this code.
  324. *
  325. * Note: The rs_control struct @rsc contains buffers which are used for
  326. * decoding, so the caller has to ensure that decoder invocations are
  327. * serialized.
  328. *
  329. * Returns the number of corrected symbols or -EBADMSG for uncorrectable
  330. * errors. The count includes errors in the parity.
  331. */
  332. int decode_rs8(struct rs_control *rsc, uint8_t *data, uint16_t *par, int len,
  333. uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
  334. uint16_t *corr)
  335. {
  336. #include "decode_rs.c"
  337. }
  338. EXPORT_SYMBOL_GPL(decode_rs8);
  339. #endif
  340. #ifdef CONFIG_REED_SOLOMON_ENC16
  341. /**
  342. * encode_rs16 - Calculate the parity for data values (16bit data width)
  343. * @rsc: the rs control structure
  344. * @data: data field of a given type
  345. * @len: data length
  346. * @par: parity data, must be initialized by caller (usually all 0)
  347. * @invmsk: invert data mask (will be xored on data, not on parity!)
  348. *
  349. * Each field in the data array contains up to symbol size bits of valid data.
  350. */
  351. int encode_rs16(struct rs_control *rsc, uint16_t *data, int len, uint16_t *par,
  352. uint16_t invmsk)
  353. {
  354. #include "encode_rs.c"
  355. }
  356. EXPORT_SYMBOL_GPL(encode_rs16);
  357. #endif
  358. #ifdef CONFIG_REED_SOLOMON_DEC16
  359. /**
  360. * decode_rs16 - Decode codeword (16bit data width)
  361. * @rsc: the rs control structure
  362. * @data: data field of a given type
  363. * @par: received parity data field
  364. * @len: data length
  365. * @s: syndrome data field, must be in index form
  366. * (if NULL, syndrome is calculated)
  367. * @no_eras: number of erasures
  368. * @eras_pos: position of erasures, can be NULL
  369. * @invmsk: invert data mask (will be xored on data, not on parity!)
  370. * @corr: buffer to store correction bitmask on eras_pos
  371. *
  372. * Each field in the data array contains up to symbol size bits of valid data.
  373. *
  374. * Note: The rc_control struct @rsc contains buffers which are used for
  375. * decoding, so the caller has to ensure that decoder invocations are
  376. * serialized.
  377. *
  378. * Returns the number of corrected symbols or -EBADMSG for uncorrectable
  379. * errors. The count includes errors in the parity.
  380. */
  381. int decode_rs16(struct rs_control *rsc, uint16_t *data, uint16_t *par, int len,
  382. uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
  383. uint16_t *corr)
  384. {
  385. #include "decode_rs.c"
  386. }
  387. EXPORT_SYMBOL_GPL(decode_rs16);
  388. #endif
  389. MODULE_LICENSE("GPL");
  390. MODULE_DESCRIPTION("Reed Solomon encoder/decoder");
  391. MODULE_AUTHOR("Phil Karn, Thomas Gleixner");