aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorSegher Boessenkool <segher@kernel.crashing.org>2007-05-02 06:18:41 -0400
committerDavid Woodhouse <dwmw2@infradead.org>2007-05-02 06:56:33 -0400
commitd7e5a5462f68270ed66efff22b1981be57a28c19 (patch)
treed8125b02762dfd169d110fb67c6f9a7acb686939 /lib
parent7c96b7a146eb81d13be738709c36752c20abe4fc (diff)
[RSLIB] Support non-canonical GF representations
For the CAFÉ NAND controller, we need to support non-canonical representations of the Galois field. Allow the caller to provide its own function for generating the field, and CAFÉ can use rslib instead of its own implementation. Signed-off-by: Segher Boessenkool <segher@kernel.crashing.org> Signed-off-by: David Woodhouse <dwmw2@infradead.org>
Diffstat (limited to 'lib')
-rw-r--r--lib/reed_solomon/reed_solomon.c84
1 files changed, 69 insertions, 15 deletions
diff --git a/lib/reed_solomon/reed_solomon.c b/lib/reed_solomon/reed_solomon.c
index a4b730a2180c..5b0d8522b7ca 100644
--- a/lib/reed_solomon/reed_solomon.c
+++ b/lib/reed_solomon/reed_solomon.c
@@ -56,6 +56,7 @@ static DEFINE_MUTEX(rslistlock);
56 * rs_init - Initialize a Reed-Solomon codec 56 * rs_init - Initialize a Reed-Solomon codec
57 * @symsize: symbol size, bits (1-8) 57 * @symsize: symbol size, bits (1-8)
58 * @gfpoly: Field generator polynomial coefficients 58 * @gfpoly: Field generator polynomial coefficients
59 * @gffunc: Field generator function
59 * @fcr: first root of RS code generator polynomial, index form 60 * @fcr: first root of RS code generator polynomial, index form
60 * @prim: primitive element to generate polynomial roots 61 * @prim: primitive element to generate polynomial roots
61 * @nroots: RS code generator polynomial degree (number of roots) 62 * @nroots: RS code generator polynomial degree (number of roots)
@@ -63,8 +64,8 @@ static DEFINE_MUTEX(rslistlock);
63 * Allocate a control structure and the polynom arrays for faster 64 * Allocate a control structure and the polynom arrays for faster
64 * en/decoding. Fill the arrays according to the given parameters. 65 * en/decoding. Fill the arrays according to the given parameters.
65 */ 66 */
66static struct rs_control *rs_init(int symsize, int gfpoly, int fcr, 67static struct rs_control *rs_init(int symsize, int gfpoly, int (*gffunc)(int),
67 int prim, int nroots) 68 int fcr, int prim, int nroots)
68{ 69{
69 struct rs_control *rs; 70 struct rs_control *rs;
70 int i, j, sr, root, iprim; 71 int i, j, sr, root, iprim;
@@ -82,6 +83,7 @@ static struct rs_control *rs_init(int symsize, int gfpoly, int fcr,
82 rs->prim = prim; 83 rs->prim = prim;
83 rs->nroots = nroots; 84 rs->nroots = nroots;
84 rs->gfpoly = gfpoly; 85 rs->gfpoly = gfpoly;
86 rs->gffunc = gffunc;
85 87
86 /* Allocate the arrays */ 88 /* Allocate the arrays */
87 rs->alpha_to = kmalloc(sizeof(uint16_t) * (rs->nn + 1), GFP_KERNEL); 89 rs->alpha_to = kmalloc(sizeof(uint16_t) * (rs->nn + 1), GFP_KERNEL);
@@ -99,17 +101,26 @@ static struct rs_control *rs_init(int symsize, int gfpoly, int fcr,
99 /* Generate Galois field lookup tables */ 101 /* Generate Galois field lookup tables */
100 rs->index_of[0] = rs->nn; /* log(zero) = -inf */ 102 rs->index_of[0] = rs->nn; /* log(zero) = -inf */
101 rs->alpha_to[rs->nn] = 0; /* alpha**-inf = 0 */ 103 rs->alpha_to[rs->nn] = 0; /* alpha**-inf = 0 */
102 sr = 1; 104 if (gfpoly) {
103 for (i = 0; i < rs->nn; i++) { 105 sr = 1;
104 rs->index_of[sr] = i; 106 for (i = 0; i < rs->nn; i++) {
105 rs->alpha_to[i] = sr; 107 rs->index_of[sr] = i;
106 sr <<= 1; 108 rs->alpha_to[i] = sr;
107 if (sr & (1 << symsize)) 109 sr <<= 1;
108 sr ^= gfpoly; 110 if (sr & (1 << symsize))
109 sr &= rs->nn; 111 sr ^= gfpoly;
112 sr &= rs->nn;
113 }
114 } else {
115 sr = gffunc(0);
116 for (i = 0; i < rs->nn; i++) {
117 rs->index_of[sr] = i;
118 rs->alpha_to[i] = sr;
119 sr = gffunc(sr);
120 }
110 } 121 }
111 /* If it's not primitive, exit */ 122 /* If it's not primitive, exit */
112 if(sr != 1) 123 if(sr != rs->alpha_to[0])
113 goto errpol; 124 goto errpol;
114 125
115 /* Find prim-th root of 1, used in decoding */ 126 /* Find prim-th root of 1, used in decoding */
@@ -173,18 +184,22 @@ void free_rs(struct rs_control *rs)
173} 184}
174 185
175/** 186/**
176 * init_rs - Find a matching or allocate a new rs control structure 187 * init_rs_internal - Find a matching or allocate a new rs control structure
177 * @symsize: the symbol size (number of bits) 188 * @symsize: the symbol size (number of bits)
178 * @gfpoly: the extended Galois field generator polynomial coefficients, 189 * @gfpoly: the extended Galois field generator polynomial coefficients,
179 * with the 0th coefficient in the low order bit. The polynomial 190 * with the 0th coefficient in the low order bit. The polynomial
180 * must be primitive; 191 * must be primitive;
192 * @gffunc: pointer to function to generate the next field element,
193 * or the multiplicative identity element if given 0. Used
194 * instead of gfpoly if gfpoly is 0
181 * @fcr: the first consecutive root of the rs code generator polynomial 195 * @fcr: the first consecutive root of the rs code generator polynomial
182 * in index form 196 * in index form
183 * @prim: primitive element to generate polynomial roots 197 * @prim: primitive element to generate polynomial roots
184 * @nroots: RS code generator polynomial degree (number of roots) 198 * @nroots: RS code generator polynomial degree (number of roots)
185 */ 199 */
186struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim, 200static struct rs_control *init_rs_internal(int symsize, int gfpoly,
187 int nroots) 201 int (*gffunc)(int), int fcr,
202 int prim, int nroots)
188{ 203{
189 struct list_head *tmp; 204 struct list_head *tmp;
190 struct rs_control *rs; 205 struct rs_control *rs;
@@ -208,6 +223,8 @@ struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim,
208 continue; 223 continue;
209 if (gfpoly != rs->gfpoly) 224 if (gfpoly != rs->gfpoly)
210 continue; 225 continue;
226 if (gffunc != rs->gffunc)
227 continue;
211 if (fcr != rs->fcr) 228 if (fcr != rs->fcr)
212 continue; 229 continue;
213 if (prim != rs->prim) 230 if (prim != rs->prim)
@@ -220,7 +237,7 @@ struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim,
220 } 237 }
221 238
222 /* Create a new one */ 239 /* Create a new one */
223 rs = rs_init(symsize, gfpoly, fcr, prim, nroots); 240 rs = rs_init(symsize, gfpoly, gffunc, fcr, prim, nroots);
224 if (rs) { 241 if (rs) {
225 rs->users = 1; 242 rs->users = 1;
226 list_add(&rs->list, &rslist); 243 list_add(&rs->list, &rslist);
@@ -230,6 +247,42 @@ out:
230 return rs; 247 return rs;
231} 248}
232 249
250/**
251 * init_rs - Find a matching or allocate a new rs control structure
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 */
261struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim,
262 int nroots)
263{
264 return init_rs_internal(symsize, gfpoly, NULL, fcr, prim, nroots);
265}
266
267/**
268 * init_rs_non_canonical - Find a matching or allocate a new rs control
269 * structure, for fields with non-canonical
270 * 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 */
280struct 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}
285
233#ifdef CONFIG_REED_SOLOMON_ENC8 286#ifdef CONFIG_REED_SOLOMON_ENC8
234/** 287/**
235 * encode_rs8 - Calculate the parity for data values (8bit data width) 288 * encode_rs8 - Calculate the parity for data values (8bit data width)
@@ -321,6 +374,7 @@ EXPORT_SYMBOL_GPL(decode_rs16);
321#endif 374#endif
322 375
323EXPORT_SYMBOL_GPL(init_rs); 376EXPORT_SYMBOL_GPL(init_rs);
377EXPORT_SYMBOL_GPL(init_rs_non_canonical);
324EXPORT_SYMBOL_GPL(free_rs); 378EXPORT_SYMBOL_GPL(free_rs);
325 379
326MODULE_LICENSE("GPL"); 380MODULE_LICENSE("GPL");