reed_solomon.c 9.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329
  1. /*
  2. * lib/reed_solomon/reed_solomon.c
  3. *
  4. * Overview:
  5. * Generic Reed Solomon encoder / decoder library
  6. *
  7. * Copyright (C) 2004 Thomas Gleixner (tglx@linutronix.de)
  8. *
  9. * Reed Solomon code lifted from reed solomon library written by Phil Karn
  10. * Copyright 2002 Phil Karn, KA9Q
  11. *
  12. * $Id: reed_solomon.c,v 1.1.1.1 2007/06/12 07:27:13 eyryu Exp $
  13. *
  14. * This program is free software; you can redistribute it and/or modify
  15. * it under the terms of the GNU General Public License version 2 as
  16. * published by the Free Software Foundation.
  17. *
  18. * Description:
  19. *
  20. * The generic Reed Solomon library provides runtime configurable
  21. * encoding / decoding of RS codes.
  22. * Each user must call init_rs to get a pointer to a rs_control
  23. * structure for the given rs parameters. This structure is either
  24. * generated or a already available matching control structure is used.
  25. * If a structure is generated then the polynomial arrays for
  26. * fast encoding / decoding are built. This can take some time so
  27. * make sure not to call this function from a time critical path.
  28. * Usually a module / driver should initialize the necessary
  29. * rs_control structure on module / driver init and release it
  30. * on exit.
  31. * The encoding puts the calculated syndrome into a given syndrome
  32. * buffer.
  33. * The decoding is a two step process. The first step calculates
  34. * the syndrome over the received (data + syndrome) and calls the
  35. * second stage, which does the decoding / error correction itself.
  36. * Many hw encoders provide a syndrome calculation over the received
  37. * data + syndrome and can call the second stage directly.
  38. *
  39. */
  40. #include <linux/errno.h>
  41. #include <linux/kernel.h>
  42. #include <linux/init.h>
  43. #include <linux/module.h>
  44. #include <linux/rslib.h>
  45. #include <linux/slab.h>
  46. #include <linux/mutex.h>
  47. #include <asm/semaphore.h>
  48. /* This list holds all currently allocated rs control structures */
  49. static LIST_HEAD (rslist);
  50. /* Protection for the list */
  51. static DEFINE_MUTEX(rslistlock);
  52. /**
  53. * rs_init - Initialize a Reed-Solomon codec
  54. * @symsize: symbol size, bits (1-8)
  55. * @gfpoly: Field generator polynomial coefficients
  56. * @fcr: first root of RS code generator polynomial, index form
  57. * @prim: primitive element to generate polynomial roots
  58. * @nroots: RS code generator polynomial degree (number of roots)
  59. *
  60. * Allocate a control structure and the polynom arrays for faster
  61. * en/decoding. Fill the arrays according to the given parameters.
  62. */
  63. static struct rs_control *rs_init(int symsize, int gfpoly, int fcr,
  64. int prim, int nroots)
  65. {
  66. struct rs_control *rs;
  67. int i, j, sr, root, iprim;
  68. /* Allocate the control structure */
  69. rs = kmalloc(sizeof (struct rs_control), GFP_KERNEL);
  70. if (rs == NULL)
  71. return NULL;
  72. INIT_LIST_HEAD(&rs->list);
  73. rs->mm = symsize;
  74. rs->nn = (1 << symsize) - 1;
  75. rs->fcr = fcr;
  76. rs->prim = prim;
  77. rs->nroots = nroots;
  78. rs->gfpoly = gfpoly;
  79. /* Allocate the arrays */
  80. rs->alpha_to = kmalloc(sizeof(uint16_t) * (rs->nn + 1), GFP_KERNEL);
  81. if (rs->alpha_to == NULL)
  82. goto errrs;
  83. rs->index_of = kmalloc(sizeof(uint16_t) * (rs->nn + 1), GFP_KERNEL);
  84. if (rs->index_of == NULL)
  85. goto erralp;
  86. rs->genpoly = kmalloc(sizeof(uint16_t) * (rs->nroots + 1), GFP_KERNEL);
  87. if(rs->genpoly == NULL)
  88. goto erridx;
  89. /* Generate Galois field lookup tables */
  90. rs->index_of[0] = rs->nn; /* log(zero) = -inf */
  91. rs->alpha_to[rs->nn] = 0; /* alpha**-inf = 0 */
  92. sr = 1;
  93. for (i = 0; i < rs->nn; i++) {
  94. rs->index_of[sr] = i;
  95. rs->alpha_to[i] = sr;
  96. sr <<= 1;
  97. if (sr & (1 << symsize))
  98. sr ^= gfpoly;
  99. sr &= rs->nn;
  100. }
  101. /* If it's not primitive, exit */
  102. if(sr != 1)
  103. goto errpol;
  104. /* Find prim-th root of 1, used in decoding */
  105. for(iprim = 1; (iprim % prim) != 0; iprim += rs->nn);
  106. /* prim-th root of 1, index form */
  107. rs->iprim = iprim / prim;
  108. /* Form RS code generator polynomial from its roots */
  109. rs->genpoly[0] = 1;
  110. for (i = 0, root = fcr * prim; i < nroots; i++, root += prim) {
  111. rs->genpoly[i + 1] = 1;
  112. /* Multiply rs->genpoly[] by @**(root + x) */
  113. for (j = i; j > 0; j--) {
  114. if (rs->genpoly[j] != 0) {
  115. rs->genpoly[j] = rs->genpoly[j -1] ^
  116. rs->alpha_to[rs_modnn(rs,
  117. rs->index_of[rs->genpoly[j]] + root)];
  118. } else
  119. rs->genpoly[j] = rs->genpoly[j - 1];
  120. }
  121. /* rs->genpoly[0] can never be zero */
  122. rs->genpoly[0] =
  123. rs->alpha_to[rs_modnn(rs,
  124. rs->index_of[rs->genpoly[0]] + root)];
  125. }
  126. /* convert rs->genpoly[] to index form for quicker encoding */
  127. for (i = 0; i <= nroots; i++)
  128. rs->genpoly[i] = rs->index_of[rs->genpoly[i]];
  129. return rs;
  130. /* Error exit */
  131. errpol:
  132. kfree(rs->genpoly);
  133. erridx:
  134. kfree(rs->index_of);
  135. erralp:
  136. kfree(rs->alpha_to);
  137. errrs:
  138. kfree(rs);
  139. return NULL;
  140. }
  141. /**
  142. * free_rs - Free the rs control structure, if it is no longer used
  143. * @rs: the control structure which is not longer used by the
  144. * caller
  145. */
  146. void free_rs(struct rs_control *rs)
  147. {
  148. mutex_lock(&rslistlock);
  149. rs->users--;
  150. if(!rs->users) {
  151. list_del(&rs->list);
  152. kfree(rs->alpha_to);
  153. kfree(rs->index_of);
  154. kfree(rs->genpoly);
  155. kfree(rs);
  156. }
  157. mutex_unlock(&rslistlock);
  158. }
  159. /**
  160. * init_rs - Find a matching or allocate a new rs control structure
  161. * @symsize: the symbol size (number of bits)
  162. * @gfpoly: the extended Galois field generator polynomial coefficients,
  163. * with the 0th coefficient in the low order bit. The polynomial
  164. * must be primitive;
  165. * @fcr: the first consecutive root of the rs code generator polynomial
  166. * in index form
  167. * @prim: primitive element to generate polynomial roots
  168. * @nroots: RS code generator polynomial degree (number of roots)
  169. */
  170. struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim,
  171. int nroots)
  172. {
  173. struct list_head *tmp;
  174. struct rs_control *rs;
  175. /* Sanity checks */
  176. if (symsize < 1)
  177. return NULL;
  178. if (fcr < 0 || fcr >= (1<<symsize))
  179. return NULL;
  180. if (prim <= 0 || prim >= (1<<symsize))
  181. return NULL;
  182. if (nroots < 0 || nroots >= (1<<symsize))
  183. return NULL;
  184. mutex_lock(&rslistlock);
  185. /* Walk through the list and look for a matching entry */
  186. list_for_each(tmp, &rslist) {
  187. rs = list_entry(tmp, struct rs_control, list);
  188. if (symsize != rs->mm)
  189. continue;
  190. if (gfpoly != rs->gfpoly)
  191. continue;
  192. if (fcr != rs->fcr)
  193. continue;
  194. if (prim != rs->prim)
  195. continue;
  196. if (nroots != rs->nroots)
  197. continue;
  198. /* We have a matching one already */
  199. rs->users++;
  200. goto out;
  201. }
  202. /* Create a new one */
  203. rs = rs_init(symsize, gfpoly, fcr, prim, nroots);
  204. if (rs) {
  205. rs->users = 1;
  206. list_add(&rs->list, &rslist);
  207. }
  208. out:
  209. mutex_unlock(&rslistlock);
  210. return rs;
  211. }
  212. #ifdef CONFIG_REED_SOLOMON_ENC8
  213. /**
  214. * encode_rs8 - Calculate the parity for data values (8bit data width)
  215. * @rs: the rs control structure
  216. * @data: data field of a given type
  217. * @len: data length
  218. * @par: parity data, must be initialized by caller (usually all 0)
  219. * @invmsk: invert data mask (will be xored on data)
  220. *
  221. * The parity uses a uint16_t data type to enable
  222. * symbol size > 8. The calling code must take care of encoding of the
  223. * syndrome result for storage itself.
  224. */
  225. int encode_rs8(struct rs_control *rs, uint8_t *data, int len, uint16_t *par,
  226. uint16_t invmsk)
  227. {
  228. #include "encode_rs.c"
  229. }
  230. EXPORT_SYMBOL_GPL(encode_rs8);
  231. #endif
  232. #ifdef CONFIG_REED_SOLOMON_DEC8
  233. /**
  234. * decode_rs8 - Decode codeword (8bit data width)
  235. * @rs: the rs control structure
  236. * @data: data field of a given type
  237. * @par: received parity data field
  238. * @len: data length
  239. * @s: syndrome data field (if NULL, syndrome is calculated)
  240. * @no_eras: number of erasures
  241. * @eras_pos: position of erasures, can be NULL
  242. * @invmsk: invert data mask (will be xored on data, not on parity!)
  243. * @corr: buffer to store correction bitmask on eras_pos
  244. *
  245. * The syndrome and parity uses a uint16_t data type to enable
  246. * symbol size > 8. The calling code must take care of decoding of the
  247. * syndrome result and the received parity before calling this code.
  248. */
  249. int decode_rs8(struct rs_control *rs, uint8_t *data, uint16_t *par, int len,
  250. uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
  251. uint16_t *corr)
  252. {
  253. #include "decode_rs.c"
  254. }
  255. EXPORT_SYMBOL_GPL(decode_rs8);
  256. #endif
  257. #ifdef CONFIG_REED_SOLOMON_ENC16
  258. /**
  259. * encode_rs16 - Calculate the parity for data values (16bit data width)
  260. * @rs: the rs control structure
  261. * @data: data field of a given type
  262. * @len: data length
  263. * @par: parity data, must be initialized by caller (usually all 0)
  264. * @invmsk: invert data mask (will be xored on data, not on parity!)
  265. *
  266. * Each field in the data array contains up to symbol size bits of valid data.
  267. */
  268. int encode_rs16(struct rs_control *rs, uint16_t *data, int len, uint16_t *par,
  269. uint16_t invmsk)
  270. {
  271. #include "encode_rs.c"
  272. }
  273. EXPORT_SYMBOL_GPL(encode_rs16);
  274. #endif
  275. #ifdef CONFIG_REED_SOLOMON_DEC16
  276. /**
  277. * decode_rs16 - Decode codeword (16bit data width)
  278. * @rs: the rs control structure
  279. * @data: data field of a given type
  280. * @par: received parity data field
  281. * @len: data length
  282. * @s: syndrome data field (if NULL, syndrome is calculated)
  283. * @no_eras: number of erasures
  284. * @eras_pos: position of erasures, can be NULL
  285. * @invmsk: invert data mask (will be xored on data, not on parity!)
  286. * @corr: buffer to store correction bitmask on eras_pos
  287. *
  288. * Each field in the data array contains up to symbol size bits of valid data.
  289. */
  290. int decode_rs16(struct rs_control *rs, uint16_t *data, uint16_t *par, int len,
  291. uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
  292. uint16_t *corr)
  293. {
  294. #include "decode_rs.c"
  295. }
  296. EXPORT_SYMBOL_GPL(decode_rs16);
  297. #endif
  298. EXPORT_SYMBOL_GPL(init_rs);
  299. EXPORT_SYMBOL_GPL(free_rs);
  300. MODULE_LICENSE("GPL");
  301. MODULE_DESCRIPTION("Reed Solomon encoder/decoder");
  302. MODULE_AUTHOR("Phil Karn, Thomas Gleixner");