1 /* The guts of the Reed-Solomon decoder, meant to be #included 2 * into a function body with the following typedefs, macros and variables supplied 3 * according to the code parameters: 4 5 * data_t - a typedef for the data symbol 6 * data_t data[] - array of NN data and parity symbols to be corrected in place 7 * retval - an integer lvalue into which the decoder's return code is written 8 * NROOTS - the number of roots in the RS code generator polynomial, 9 * which is the same as the number of parity symbols in a block. 10 Integer variable or literal. 11 * NN - the total number of symbols in a RS block. Integer variable or literal. 12 * PAD - the number of pad symbols in a block. Integer variable or literal. 13 * ALPHA_TO - The address of an array of NN elements to convert Galois field 14 * elements in index (log) form to polynomial form. Read only. 15 * INDEX_OF - The address of an array of NN elements to convert Galois field 16 * elements in polynomial form to index (log) form. Read only. 17 * MODNN - a function to reduce its argument modulo NN. May be inline or a macro. 18 * FCR - An integer literal or variable specifying the first consecutive root of the 19 * Reed-Solomon generator polynomial. Integer variable or literal. 20 * PRIM - The primitive root of the generator poly. Integer variable or literal. 21 * DEBUG - If set to 1 or more, do various internal consistency checking. Leave this 22 * undefined for production code 23 24 * The memset(), memmove(), and memcpy() functions are used. The appropriate header 25 * file declaring these functions (usually <string.h>) must be included by the calling 26 * program. 27 */ 28 29 30 #if !defined(NROOTS) 31 #error "NROOTS not defined" 32 #endif 33 34 #if !defined(NN) 35 #error "NN not defined" 36 #endif 37 38 #if !defined(PAD) 39 #error "PAD not defined" 40 #endif 41 42 #if !defined(ALPHA_TO) 43 #error "ALPHA_TO not defined" 44 #endif 45 46 #if !defined(INDEX_OF) 47 #error "INDEX_OF not defined" 48 #endif 49 50 #if !defined(MODNN) 51 #error "MODNN not defined" 52 #endif 53 54 #if !defined(FCR) 55 #error "FCR not defined" 56 #endif 57 58 #if !defined(PRIM) 59 #error "PRIM not defined" 60 #endif 61 62 #if !defined(NULL) 63 #define NULL ((void *)0) 64 #endif 65 66 #undef MIN 67 #define MIN(a,b) ((a) < (b) ? (a) : (b)) 68 #undef A0 69 #define A0 (NN) 70 71 { 72 int deg_lambda, el, deg_omega; 73 int i, j, r,k; 74 data_t u,q,tmp,num1,num2,den,discr_r; 75 data_t lambda[NROOTS+1], s[NROOTS]; /* Err+Eras Locator poly 76 * and syndrome poly */ 77 data_t b[NROOTS+1], t[NROOTS+1], omega[NROOTS+1]; 78 data_t root[NROOTS], reg[NROOTS+1], loc[NROOTS]; 79 int syn_error, count; 80 81 /* form the syndromes; i.e., evaluate data(x) at roots of g(x) */ 82 for(i=0;i<NROOTS;i++) 83 s[i] = data[0]; 84 85 for(j=1;j<NN-PAD;j++){ 86 for(i=0;i<NROOTS;i++){ 87 if(s[i] == 0){ 88 s[i] = data[j]; 89 } else { 90 s[i] = data[j] ^ ALPHA_TO[MODNN(INDEX_OF[s[i]] + (FCR+i)*PRIM)]; 91 } 92 } 93 } 94 95 /* Convert syndromes to index form, checking for nonzero condition */ 96 syn_error = 0; 97 for(i=0;i<NROOTS;i++){ 98 syn_error |= s[i]; 99 s[i] = INDEX_OF[s[i]]; 100 } 101 102 if (!syn_error) { 103 /* if syndrome is zero, data[] is a codeword and there are no 104 * errors to correct. So return data[] unmodified 105 */ 106 count = 0; 107 goto finish; 108 } 109 memset(&lambda[1],0,NROOTS*sizeof(lambda[0])); 110 lambda[0] = 1; 111 112 if (no_eras > 0) { 113 /* Init lambda to be the erasure locator polynomial */ 114 lambda[1] = ALPHA_TO[MODNN(PRIM*(NN-1-eras_pos[0]))]; 115 for (i = 1; i < no_eras; i++) { 116 u = MODNN(PRIM*(NN-1-eras_pos[i])); 117 for (j = i+1; j > 0; j--) { 118 tmp = INDEX_OF[lambda[j - 1]]; 119 if(tmp != A0) 120 lambda[j] ^= ALPHA_TO[MODNN(u + tmp)]; 121 } 122 } 123 124 #if DEBUG >= 1 125 /* Test code that verifies the erasure locator polynomial just constructed 126 Needed only for decoder debugging. */ 127 128 /* find roots of the erasure location polynomial */ 129 for(i=1;i<=no_eras;i++) 130 reg[i] = INDEX_OF[lambda[i]]; 131 132 count = 0; 133 for (i = 1,k=IPRIM-1; i <= NN; i++,k = MODNN(k+IPRIM)) { 134 q = 1; 135 for (j = 1; j <= no_eras; j++) 136 if (reg[j] != A0) { 137 reg[j] = MODNN(reg[j] + j); 138 q ^= ALPHA_TO[reg[j]]; 139 } 140 if (q != 0) 141 continue; 142 /* store root and error location number indices */ 143 root[count] = i; 144 loc[count] = k; 145 count++; 146 } 147 if (count != no_eras) { 148 printf("count = %d no_eras = %d\n lambda(x) is WRONG\n",count,no_eras); 149 count = -1; 150 goto finish; 151 } 152 #if DEBUG >= 2 153 printf("\n Erasure positions as determined by roots of Eras Loc Poly:\n"); 154 for (i = 0; i < count; i++) 155 printf("%d ", loc[i]); 156 printf("\n"); 157 #endif 158 #endif 159 } 160 for(i=0;i<NROOTS+1;i++) 161 b[i] = INDEX_OF[lambda[i]]; 162 163 /* 164 * Begin Berlekamp-Massey algorithm to determine error+erasure 165 * locator polynomial 166 */ 167 r = no_eras; 168 el = no_eras; 169 while (++r <= NROOTS) { /* r is the step number */ 170 /* Compute discrepancy at the r-th step in poly-form */ 171 discr_r = 0; 172 for (i = 0; i < r; i++){ 173 if ((lambda[i] != 0) && (s[r-i-1] != A0)) { 174 discr_r ^= ALPHA_TO[MODNN(INDEX_OF[lambda[i]] + s[r-i-1])]; 175 } 176 } 177 discr_r = INDEX_OF[discr_r]; /* Index form */ 178 if (discr_r == A0) { 179 /* 2 lines below: B(x) <-- x*B(x) */ 180 memmove(&b[1],b,NROOTS*sizeof(b[0])); 181 b[0] = A0; 182 } else { 183 /* 7 lines below: T(x) <-- lambda(x) - discr_r*x*b(x) */ 184 t[0] = lambda[0]; 185 for (i = 0 ; i < NROOTS; i++) { 186 if(b[i] != A0) 187 t[i+1] = lambda[i+1] ^ ALPHA_TO[MODNN(discr_r + b[i])]; 188 else 189 t[i+1] = lambda[i+1]; 190 } 191 if (2 * el <= r + no_eras - 1) { 192 el = r + no_eras - el; 193 /* 194 * 2 lines below: B(x) <-- inv(discr_r) * 195 * lambda(x) 196 */ 197 for (i = 0; i <= NROOTS; i++) 198 b[i] = (lambda[i] == 0) ? A0 : MODNN(INDEX_OF[lambda[i]] - discr_r + NN); 199 } else { 200 /* 2 lines below: B(x) <-- x*B(x) */ 201 memmove(&b[1],b,NROOTS*sizeof(b[0])); 202 b[0] = A0; 203 } 204 memcpy(lambda,t,(NROOTS+1)*sizeof(t[0])); 205 } 206 } 207 208 /* Convert lambda to index form and compute deg(lambda(x)) */ 209 deg_lambda = 0; 210 for(i=0;i<NROOTS+1;i++){ 211 lambda[i] = INDEX_OF[lambda[i]]; 212 if(lambda[i] != A0) 213 deg_lambda = i; 214 } 215 /* Find roots of the error+erasure locator polynomial by Chien search */ 216 memcpy(®[1],&lambda[1],NROOTS*sizeof(reg[0])); 217 count = 0; /* Number of roots of lambda(x) */ 218 for (i = 1,k=IPRIM-1; i <= NN; i++,k = MODNN(k+IPRIM)) { 219 q = 1; /* lambda[0] is always 0 */ 220 for (j = deg_lambda; j > 0; j--){ 221 if (reg[j] != A0) { 222 reg[j] = MODNN(reg[j] + j); 223 q ^= ALPHA_TO[reg[j]]; 224 } 225 } 226 if (q != 0) 227 continue; /* Not a root */ 228 /* store root (index-form) and error location number */ 229 #if DEBUG>=2 230 printf("count %d root %d loc %d\n",count,i,k); 231 #endif 232 root[count] = i; 233 loc[count] = k; 234 /* If we've already found max possible roots, 235 * abort the search to save time 236 */ 237 if(++count == deg_lambda) 238 break; 239 } 240 if (deg_lambda != count) { 241 /* 242 * deg(lambda) unequal to number of roots => uncorrectable 243 * error detected 244 */ 245 count = -1; 246 goto finish; 247 } 248 /* 249 * Compute err+eras evaluator poly omega(x) = s(x)*lambda(x) (modulo 250 * x**NROOTS). in index form. Also find deg(omega). 251 */ 252 deg_omega = deg_lambda-1; 253 for (i = 0; i <= deg_omega;i++){ 254 tmp = 0; 255 for(j=i;j >= 0; j--){ 256 if ((s[i - j] != A0) && (lambda[j] != A0)) 257 tmp ^= ALPHA_TO[MODNN(s[i - j] + lambda[j])]; 258 } 259 omega[i] = INDEX_OF[tmp]; 260 } 261 262 /* 263 * Compute error values in poly-form. num1 = omega(inv(X(l))), num2 = 264 * inv(X(l))**(FCR-1) and den = lambda_pr(inv(X(l))) all in poly-form 265 */ 266 for (j = count-1; j >=0; j--) { 267 num1 = 0; 268 for (i = deg_omega; i >= 0; i--) { 269 if (omega[i] != A0) 270 num1 ^= ALPHA_TO[MODNN(omega[i] + i * root[j])]; 271 } 272 num2 = ALPHA_TO[MODNN(root[j] * (FCR - 1) + NN)]; 273 den = 0; 274 275 /* lambda[i+1] for i even is the formal derivative lambda_pr of lambda[i] */ 276 for (i = MIN(deg_lambda,NROOTS-1) & ~1; i >= 0; i -=2) { 277 if(lambda[i+1] != A0) 278 den ^= ALPHA_TO[MODNN(lambda[i+1] + i * root[j])]; 279 } 280 #if DEBUG >= 1 281 if (den == 0) { 282 printf("\n ERROR: denominator = 0\n"); 283 count = -1; 284 goto finish; 285 } 286 #endif 287 /* Apply error to data */ 288 if (num1 != 0 && loc[j] >= PAD) { 289 data[loc[j]-PAD] ^= ALPHA_TO[MODNN(INDEX_OF[num1] + INDEX_OF[num2] + NN - INDEX_OF[den])]; 290 } 291 } 292 finish: 293 if(eras_pos != NULL){ 294 for(i=0;i<count;i++) 295 eras_pos[i] = loc[i]; 296 } 297 retval = count; 298 } 299