1 /* 2 * lib/reed_solomon/rslib.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: rslib.c,v 1.7 2005/11/07 11:14:59 gleixner 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 41 #include <linux/errno.h> 42 #include <linux/kernel.h> 43 #include <linux/init.h> 44 #include <linux/module.h> 45 #include <linux/rslib.h> 46 #include <linux/slab.h> 47 #include <linux/mutex.h> 48 #include <asm/semaphore.h> 49 50 /* This list holds all currently allocated rs control structures */ 51 static LIST_HEAD (rslist); 52 /* Protection for the list */ 53 static DEFINE_MUTEX(rslistlock); 54 55 /** 56 * rs_init - Initialize a Reed-Solomon codec 57 * 58 * @symsize: symbol size, bits (1-8) 59 * @gfpoly: Field generator polynomial coefficients 60 * @fcr: first root of RS code generator polynomial, index form 61 * @prim: primitive element to generate polynomial roots 62 * @nroots: RS code generator polynomial degree (number of roots) 63 * 64 * Allocate a control structure and the polynom arrays for faster 65 * en/decoding. Fill the arrays according to the given parameters 66 */ 67 static struct rs_control *rs_init(int symsize, int gfpoly, int fcr, 68 int prim, int nroots) 69 { 70 struct rs_control *rs; 71 int i, j, sr, root, iprim; 72 73 /* Allocate the control structure */ 74 rs = kmalloc(sizeof (struct rs_control), GFP_KERNEL); 75 if (rs == NULL) 76 return NULL; 77 78 INIT_LIST_HEAD(&rs->list); 79 80 rs->mm = symsize; 81 rs->nn = (1 << symsize) - 1; 82 rs->fcr = fcr; 83 rs->prim = prim; 84 rs->nroots = nroots; 85 rs->gfpoly = gfpoly; 86 87 /* Allocate the arrays */ 88 rs->alpha_to = kmalloc(sizeof(uint16_t) * (rs->nn + 1), GFP_KERNEL); 89 if (rs->alpha_to == NULL) 90 goto errrs; 91 92 rs->index_of = kmalloc(sizeof(uint16_t) * (rs->nn + 1), GFP_KERNEL); 93 if (rs->index_of == NULL) 94 goto erralp; 95 96 rs->genpoly = kmalloc(sizeof(uint16_t) * (rs->nroots + 1), GFP_KERNEL); 97 if(rs->genpoly == NULL) 98 goto erridx; 99 100 /* Generate Galois field lookup tables */ 101 rs->index_of[0] = rs->nn; /* log(zero) = -inf */ 102 rs->alpha_to[rs->nn] = 0; /* alpha**-inf = 0 */ 103 sr = 1; 104 for (i = 0; i < rs->nn; i++) { 105 rs->index_of[sr] = i; 106 rs->alpha_to[i] = sr; 107 sr <<= 1; 108 if (sr & (1 << symsize)) 109 sr ^= gfpoly; 110 sr &= rs->nn; 111 } 112 /* If it's not primitive, exit */ 113 if(sr != 1) 114 goto errpol; 115 116 /* Find prim-th root of 1, used in decoding */ 117 for(iprim = 1; (iprim % prim) != 0; iprim += rs->nn); 118 /* prim-th root of 1, index form */ 119 rs->iprim = iprim / prim; 120 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 return rs; 143 144 /* Error exit */ 145 errpol: 146 kfree(rs->genpoly); 147 erridx: 148 kfree(rs->index_of); 149 erralp: 150 kfree(rs->alpha_to); 151 errrs: 152 kfree(rs); 153 return NULL; 154 } 155 156 157 /** 158 * free_rs - Free the rs control structure, if its not longer used 159 * 160 * @rs: the control structure which is not longer used by the 161 * caller 162 */ 163 void free_rs(struct rs_control *rs) 164 { 165 mutex_lock(&rslistlock); 166 rs->users--; 167 if(!rs->users) { 168 list_del(&rs->list); 169 kfree(rs->alpha_to); 170 kfree(rs->index_of); 171 kfree(rs->genpoly); 172 kfree(rs); 173 } 174 mutex_unlock(&rslistlock); 175 } 176 177 /** 178 * init_rs - Find a matching or allocate a new rs control structure 179 * 180 * @symsize: the symbol size (number of bits) 181 * @gfpoly: the extended Galois field generator polynomial coefficients, 182 * with the 0th coefficient in the low order bit. The polynomial 183 * must be primitive; 184 * @fcr: the first consecutive root of the rs code generator polynomial 185 * in index form 186 * @prim: primitive element to generate polynomial roots 187 * @nroots: RS code generator polynomial degree (number of roots) 188 */ 189 struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim, 190 int nroots) 191 { 192 struct list_head *tmp; 193 struct rs_control *rs; 194 195 /* Sanity checks */ 196 if (symsize < 1) 197 return NULL; 198 if (fcr < 0 || fcr >= (1<<symsize)) 199 return NULL; 200 if (prim <= 0 || prim >= (1<<symsize)) 201 return NULL; 202 if (nroots < 0 || nroots >= (1<<symsize)) 203 return NULL; 204 205 mutex_lock(&rslistlock); 206 207 /* Walk through the list and look for a matching entry */ 208 list_for_each(tmp, &rslist) { 209 rs = list_entry(tmp, struct rs_control, list); 210 if (symsize != rs->mm) 211 continue; 212 if (gfpoly != rs->gfpoly) 213 continue; 214 if (fcr != rs->fcr) 215 continue; 216 if (prim != rs->prim) 217 continue; 218 if (nroots != rs->nroots) 219 continue; 220 /* We have a matching one already */ 221 rs->users++; 222 goto out; 223 } 224 225 /* Create a new one */ 226 rs = rs_init(symsize, gfpoly, fcr, prim, nroots); 227 if (rs) { 228 rs->users = 1; 229 list_add(&rs->list, &rslist); 230 } 231 out: 232 mutex_unlock(&rslistlock); 233 return rs; 234 } 235 236 #ifdef CONFIG_REED_SOLOMON_ENC8 237 /** 238 * encode_rs8 - Calculate the parity for data values (8bit data width) 239 * 240 * @rs: the rs control structure 241 * @data: data field of a given type 242 * @len: data length 243 * @par: parity data, must be initialized by caller (usually all 0) 244 * @invmsk: invert data mask (will be xored on data) 245 * 246 * The parity uses a uint16_t data type to enable 247 * symbol size > 8. The calling code must take care of encoding of the 248 * syndrome result for storage itself. 249 */ 250 int encode_rs8(struct rs_control *rs, uint8_t *data, int len, uint16_t *par, 251 uint16_t invmsk) 252 { 253 #include "encode_rs.c" 254 } 255 EXPORT_SYMBOL_GPL(encode_rs8); 256 #endif 257 258 #ifdef CONFIG_REED_SOLOMON_DEC8 259 /** 260 * decode_rs8 - Decode codeword (8bit data width) 261 * 262 * @rs: the rs control structure 263 * @data: data field of a given type 264 * @par: received parity data field 265 * @len: data length 266 * @s: syndrome data field (if NULL, syndrome is calculated) 267 * @no_eras: number of erasures 268 * @eras_pos: position of erasures, can be NULL 269 * @invmsk: invert data mask (will be xored on data, not on parity!) 270 * @corr: buffer to store correction bitmask on eras_pos 271 * 272 * The syndrome and parity uses a uint16_t data type to enable 273 * symbol size > 8. The calling code must take care of decoding of the 274 * syndrome result and the received parity before calling this code. 275 */ 276 int decode_rs8(struct rs_control *rs, uint8_t *data, uint16_t *par, int len, 277 uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk, 278 uint16_t *corr) 279 { 280 #include "decode_rs.c" 281 } 282 EXPORT_SYMBOL_GPL(decode_rs8); 283 #endif 284 285 #ifdef CONFIG_REED_SOLOMON_ENC16 286 /** 287 * encode_rs16 - Calculate the parity for data values (16bit data width) 288 * 289 * @rs: the rs control structure 290 * @data: data field of a given type 291 * @len: data length 292 * @par: parity data, must be initialized by caller (usually all 0) 293 * @invmsk: invert data mask (will be xored on data, not on parity!) 294 * 295 * Each field in the data array contains up to symbol size bits of valid data. 296 */ 297 int encode_rs16(struct rs_control *rs, uint16_t *data, int len, uint16_t *par, 298 uint16_t invmsk) 299 { 300 #include "encode_rs.c" 301 } 302 EXPORT_SYMBOL_GPL(encode_rs16); 303 #endif 304 305 #ifdef CONFIG_REED_SOLOMON_DEC16 306 /** 307 * decode_rs16 - Decode codeword (16bit data width) 308 * 309 * @rs: the rs control structure 310 * @data: data field of a given type 311 * @par: received parity data field 312 * @len: data length 313 * @s: syndrome data field (if NULL, syndrome is calculated) 314 * @no_eras: number of erasures 315 * @eras_pos: position of erasures, can be NULL 316 * @invmsk: invert data mask (will be xored on data, not on parity!) 317 * @corr: buffer to store correction bitmask on eras_pos 318 * 319 * Each field in the data array contains up to symbol size bits of valid data. 320 */ 321 int decode_rs16(struct rs_control *rs, uint16_t *data, uint16_t *par, int len, 322 uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk, 323 uint16_t *corr) 324 { 325 #include "decode_rs.c" 326 } 327 EXPORT_SYMBOL_GPL(decode_rs16); 328 #endif 329 330 EXPORT_SYMBOL_GPL(init_rs); 331 EXPORT_SYMBOL_GPL(free_rs); 332 333 MODULE_LICENSE("GPL"); 334 MODULE_DESCRIPTION("Reed Solomon encoder/decoder"); 335 MODULE_AUTHOR("Phil Karn, Thomas Gleixner"); 336 337