00001 /* 00002 * This code appears to be mostly copied from with some additional minor 00003 * code provided by Michael Thompson. 00004 * 00005 * http://www.piclist.com/techref/method/error/rs-gp-pk-uoh-199609/rs_c.htm 00006 * 00007 * This code claims to be written by Phil Karns in 1996. The code at that 00008 * site unfortunately has no license in it. 00009 * 00010 * The most current version of Phil's library (fec-3.0.1) is at: 00011 * 00012 * http://www.ka9q.net/code/fec/ 00013 * 00014 * The fec-3.0.1 library (August 7, 2007) is distributed under LPGL. 00015 * 00016 * By the time I got the the code, it appears that Michael Thompson had 00017 * attached a GNU Public License to it all. Given that Phil Karn is 00018 * distributing his latest code under the GNU LGPL, my assumption is 00019 * that his older code is actually distributed under LGPL. So I have 00020 * removed the GPL and I have reattached the LGPL back onto this code 00021 * (see end of this file.) 00022 * 00023 * Wayne C. Gramlich 00024 * September 17, 2010 00025 */ 00026 00027 /* 00028 This code implements general purpose Reed-Solomon forward error correction 00029 algorithm for buffers of 3-bit to 8-bit symbols. It is a based on code by 00030 Phil Karn, which is in turn a rewrite of code by Robert Morelos-Zaragoza 00031 and Hari Thirumoorthy, which was in turn based on an earlier program by 00032 Simon Rockliff. Further information on Phil Karn's implementation can be 00033 found at: 00034 00035 http://www.piclist.com/techref/method/error/rs-gp-pk-uoh-199609/index.htm 00036 00037 This code is woefully undocumented and uncommented. Hopefully someone 00038 who can understand the math within the Reed Solomon algorithm can comment 00039 and optimize this code further. 00040 */ 00041 00042 #include <stdlib.h> 00043 #include <alloca.h> 00044 00045 #include "FEC.hpp" 00046 00047 // No legal value in index form represents zero, so 00048 // we use nn as a special value for this purpose. 00049 #define ALPHA_ZERO ((uintGF) self->nn) 00050 00051 // Alpha exponent for the first root of the generator polynomial. 00052 #define ALPHA_ROOT 1 00053 00054 // Helper macro to find minimum value. 00055 #define MIN(a,b) (((a) < (b)) ? (a) : (b)) 00056 00057 // Primitive polynomial tables. See Lin & Costello, Error Control Coding 00058 // Appendix A and Lee & Messerschmitt, Digital Communication p. 453. 00059 00060 // 1 + x + x^3 00061 rvUint8 pp_3[4] = { 1, 1, 0, 1 }; 00062 00063 // 1 + x + x^4 00064 rvUint8 pp_4[5] = { 1, 1, 0, 0, 1 }; 00065 00066 // 1 + x^2 + x^5 00067 rvUint8 pp_5[6] = { 1, 0, 1, 0, 0, 1 }; 00068 00069 // 1 + x + x^6 00070 rvUint8 pp_6[7] = { 1, 1, 0, 0, 0, 0, 1 }; 00071 00072 // 1 + x^3 + x^7 00073 rvUint8 pp_7[8] = { 1, 0, 0, 1, 0, 0, 0, 1 }; 00074 00075 // 1+x^2+x^3+x^4+x^8 00076 rvUint8 pp_8[9] = { 1, 0, 1, 1, 1, 0, 0, 0, 1 }; 00077 00078 #if 0 00079 // The following primitive polynomial tables are currently unused, but 00080 // copied here for future reference. 00081 00082 // 1+x^4+x^9 00083 rvUint8 pp_9[10] = { 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 }; 00084 00085 // 1+x^3+x^10 00086 rvUint8 pp_10[11] = { 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1 }; 00087 00088 // 1+x^2+x^11 00089 rvUint8 pp_11[12] = { 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 }; 00090 00091 // 1+x+x^4+x^6+x^12 00092 rvUint8 pp_12[13] = { 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1 }; 00093 00094 // 1+x+x^3+x^4+x^13 00095 rvUint8 pp_13[14] = { 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 }; 00096 00097 // 1+x+x^6+x^10+x^14 00098 rvUint8 pp_14[15] = { 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1 }; 00099 00100 // 1+x+x^15 00101 rvUint8 pp_15[16] = { 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }; 00102 00103 // 1+x+x^3+x^12+x^16 00104 rvUint8 pp_16[17] = { 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1 }; 00105 #endif 00106 00107 // Helper macro to compute x mod nn. 00108 #define modnn(x) ((x) % self->nn) 00109 00110 static void rvFec_InitGaloisField(rvFec* self, rvUint8 *pp) 00111 // Initialize GF(2**mm) table from the irreducible polynomial p(X) in pp[0]..pp[MM - 1]. 00112 // 00113 // The following tables are created: 00114 // 00115 // index form to polynomial form alphaTo[] contains j=alpha**i; 00116 // polynomial form to index form indexOf[j=alpha**i] = i 00117 // 00118 // The representation of the elements of GF(2**mm) is either in index form, 00119 // where the number is the power of the primitive element alpha, which is 00120 // convenient for multiplication (add the powers modulo 2**mm-1) or in 00121 // polynomial form, where the bits represent the coefficients of the 00122 // polynomial representation of the number, which is the most convenient form 00123 // for addition. The two forms are swapped between via lookup tables. 00124 // This leads to fairly messy looking expressions, but unfortunately, there 00125 // is no easy alternative when working with Galois arithmetic. 00126 { 00127 rvUint16 i; 00128 rvUint16 mask; 00129 00130 // Local references so code is easier on the eyes. 00131 uintGF mm = (uintGF) self->mm; 00132 uintGF nn = (uintGF) self->nn; 00133 uintGF *alphaTo = self->alphaTo; 00134 uintGF *indexOf = self->indexOf; 00135 00136 mask = 1; 00137 alphaTo[mm] = 0; 00138 for (i = 0; i < mm; i++) { 00139 alphaTo[i] = (uintGF) mask; 00140 indexOf[alphaTo[i]] = (uintGF) i; 00141 if (pp[i] != 0) { 00142 alphaTo[mm] ^= (uintGF) mask; 00143 } 00144 mask <<= 1; 00145 } 00146 indexOf[alphaTo[mm]] = mm; 00147 mask >>= 1; 00148 for (i = mm + 1; i < nn; i++) { 00149 if (alphaTo[i - 1] >= mask) { 00150 alphaTo[i] = alphaTo[mm] ^ ((alphaTo[i - 1] ^ mask) << 1); 00151 } else { 00152 alphaTo[i] = alphaTo[i - 1] << 1; 00153 } 00154 indexOf[alphaTo[i]] = (uintGF) i; 00155 } 00156 indexOf[0] = ALPHA_ZERO; 00157 alphaTo[nn] = 0; 00158 } 00159 00160 00161 static void 00162 rvFec_InitPolynomial( 00163 rvFec* self) 00164 { 00165 // Initialize the generator polynomial table. 00166 rvInt16 i; 00167 rvInt16 j; 00168 00169 // Local references so code is easier on the eyes. 00170 uintGF *gg = self->gg; 00171 uintGF *alphaTo = self->alphaTo; 00172 uintGF *indexOf = self->indexOf; 00173 00174 gg[0] = alphaTo[ALPHA_ROOT]; 00175 gg[1] = 1; 00176 for (i = 2; i <= self->paritySize; i++) { 00177 gg[i] = 1; 00178 for (j = i - 1; j > 0; --j) { 00179 if (gg[j] != 0) { 00180 gg[j] = gg[j - 1] ^ 00181 alphaTo[modnn((indexOf[gg[j]]) + ALPHA_ROOT + i - 1)]; 00182 } else { 00183 gg[j] = gg[j - 1]; 00184 } 00185 } 00186 gg[0] = alphaTo[modnn((indexOf[gg[0]]) + ALPHA_ROOT + i - 1)]; 00187 } 00188 00189 // Convert gg[] to index form for quicker encoding. 00190 for (i = 0; i <= self->paritySize; i++) { 00191 gg[i] = indexOf[gg[i]]; 00192 } 00193 } 00194 00195 00196 rvFec* rvFec_New(rvInt16 symbolSize, rvInt16 dataSize, rvInt16 paritySize) 00197 // Initialize the encoder object. 00198 { 00199 rvInt16 mm; 00200 rvInt16 nn; 00201 rvInt16 kk; 00202 rvInt16 zeroSize; 00203 rvInt16 blockSize; 00204 rvUint8* pp = NULL; 00205 uintGF* gg = NULL; 00206 uintGF* alphaTo = NULL; 00207 uintGF* indexOf = NULL; 00208 rvFec* self = NULL; 00209 00210 // Set the Reed Solomon properties. 00211 mm = symbolSize; 00212 nn = ((1 << mm) - 1); 00213 kk = nn - paritySize; 00214 00215 // The block size is the combined data and parity size. 00216 blockSize = dataSize + paritySize; 00217 00218 // The zero size is the size of the zero padded data. 00219 zeroSize = nn - blockSize; 00220 00221 // Sanity check block and data size. 00222 if ((blockSize < 1) || (blockSize > nn)) return NULL; 00223 if ((dataSize < 1) || (dataSize >= blockSize)) return NULL; 00224 00225 // Point to primative polynomial table. 00226 if (symbolSize == 3) pp = pp_3; 00227 else if (symbolSize == 4) pp = pp_4; 00228 else if (symbolSize == 5) pp = pp_5; 00229 else if (symbolSize == 6) pp = pp_6; 00230 else if (symbolSize == 7) pp = pp_7; 00231 else if (symbolSize == 8) pp = pp_8; 00232 else return NULL; 00233 00234 // Allocate a new ecc object and tables. 00235 self = (rvFec *) malloc(sizeof(rvFec)); 00236 gg = (uintGF*) malloc(sizeof(uintGF) * (paritySize + 1)); 00237 alphaTo = (uintGF*) malloc(sizeof(uintGF) * (nn + 1)); 00238 indexOf = (uintGF*) malloc(sizeof(uintGF) * (nn + 1)); 00239 00240 // Did we allocate the object. 00241 if ((self != NULL) && (gg != NULL) && 00242 (alphaTo != NULL) && (indexOf != NULL)) { 00243 // Set the Reed Solomon properties. 00244 self->mm = mm; 00245 self->nn = nn; 00246 self->kk = kk; 00247 00248 // Set the buffer properties. 00249 self->zeroSize = zeroSize; 00250 self->dataSize = dataSize; 00251 self->paritySize = paritySize; 00252 self->blockSize = blockSize; 00253 00254 // Set the allocated tables. 00255 self->gg = gg; 00256 self->alphaTo = alphaTo; 00257 self->indexOf = indexOf; 00258 00259 // Initialize Galois Field table 00260 rvFec_InitGaloisField(self, pp); 00261 00262 // Initialize generator polynomial. 00263 rvFec_InitPolynomial(self); 00264 } else { 00265 // Clean up. 00266 if (self) free(self); 00267 if (gg) free(gg); 00268 if (alphaTo) free(alphaTo); 00269 if (indexOf) free(indexOf); 00270 } 00271 00272 return self; 00273 } 00274 00275 00276 rvInt16 rvFec_Parity(rvFec* self, rvUint8* dataBuffer, rvUint8* parityBuffer) 00277 // Encode parity for the data buffer. Returns 1 if success or 0 if 00278 // unable to encode. Encoding is done by using a feedback shift register 00279 // with appropriate connections specified by the elements of gg[], which 00280 // was generated by the ecc_generate_galois_field() function. 00281 { 00282 rvInt16 i; 00283 rvInt16 j; 00284 uintGF feedback; 00285 00286 // Local references so code is easier on the eyes. 00287 uintGF *gg = self->gg; 00288 uintGF *alphaTo = self->alphaTo; 00289 uintGF *indexOf = self->indexOf; 00290 00291 // Zero the parity data. 00292 for (i = 0; i < self->paritySize; ++i) parityBuffer[i] = 0; 00293 00294 // Loop over the data portion of the encode buffer. 00295 for (i = self->zeroSize + self->dataSize; i >= 0; --i) { 00296 // Pad data with zero to account for shortened buffer when 00297 // determining feedback. 00298 feedback = 00299 indexOf[((i >= self->zeroSize) ? dataBuffer[i - self->zeroSize] : 0) ^ 00300 parityBuffer[self->paritySize - 1]]; 00301 00302 // Is the feedback term non-zero? 00303 if (feedback != ALPHA_ZERO) { 00304 for (j = self->paritySize - 1; j > 0; --j) { 00305 if (gg[j] != ALPHA_ZERO) { 00306 parityBuffer[j] = 00307 parityBuffer[j - 1] ^ alphaTo[modnn(gg[j] + feedback)]; 00308 } else { 00309 parityBuffer[j] = parityBuffer[j - 1]; 00310 } 00311 } 00312 parityBuffer[0] = alphaTo[modnn(gg[0] + feedback)]; 00313 } else { 00314 for (j = self->paritySize - 1; j > 0; --j) { 00315 parityBuffer[j] = parityBuffer[j - 1]; 00316 } 00317 parityBuffer[0] = 0; 00318 } 00319 } 00320 00321 return 1; 00322 } 00323 00324 00325 rvInt16 rvFec_Correct(rvFec* self, rvUint8* blockBuffer) 00326 // Correct the block buffer. Returns 1 if success or 0 if unable to correct. 00327 { 00328 rvInt16 i; 00329 rvInt16 j; 00330 rvInt16 r; 00331 rvInt16 el; 00332 rvInt16 count; 00333 rvInt16 syn_error; 00334 rvInt16 deg_omega; 00335 rvInt16 deg_lambda; 00336 rvInt16 *loc; 00337 uintGF q; 00338 uintGF *b; 00339 uintGF *t; 00340 uintGF *reg; 00341 uintGF *recd; 00342 uintGF *root; 00343 uintGF *omega; 00344 uintGF *lambda; 00345 uintGF *syndromes; 00346 00347 // Local references so code is easier on the eyes. 00348 rvInt16 nn = self->nn; 00349 uintGF *gg = self->gg; 00350 uintGF *alphaTo = self->alphaTo; 00351 uintGF *indexOf = self->indexOf; 00352 00353 // Allocate the recieve buffer off the stack. 00354 recd = (uintGF*) alloca(sizeof(uintGF) * nn); 00355 00356 // Copy and convert the encoded buffer from polynomial form to index form. 00357 for (i = nn - 1; i >= 0; --i) { 00358 // Pad data with zero to account for shortened buffer. 00359 recd[i] = 00360 indexOf[(i >= self->zeroSize) ? blockBuffer[i - self->zeroSize] : 0]; 00361 } 00362 00363 // Allocate the syndromes buffer off the stack. 00364 syndromes = (uintGF*) alloca(sizeof(uintGF) * (self->paritySize + 1)); 00365 00366 // Initialize the syndrome error flag. 00367 syn_error = 0; 00368 00369 // Form and store each syndrome by evaluating recd(x) at roots of g(x) 00370 // namely @**(ALPHA_ROOT+i), i = 0, ... ,(nn-KK-1) 00371 for (i = 1; i <= self->paritySize; i++) { 00372 uintGF syndrome = 0; 00373 00374 // Loop over each data byte. 00375 for (j = 0; j < nn; j++) { 00376 // All non-zero receive values added to the syndrome. 00377 if (recd[j] != ALPHA_ZERO) { 00378 syndrome ^= alphaTo[modnn(recd[j] + (ALPHA_ROOT + i - 1) * j)]; 00379 } 00380 } 00381 00382 // Set flag if non-zero syndrome. 00383 syn_error |= syndrome; 00384 00385 // Store syndrome in index form. 00386 syndromes[i] = indexOf[syndrome]; 00387 } 00388 00389 if (!syn_error) { 00390 // If all syndromes are zero there are no errors to correct. 00391 return 1; 00392 } 00393 00394 // Allocate the lambda buffer off the stack. 00395 lambda = (uintGF*) alloca(sizeof(uintGF) * (self->paritySize + 1)); 00396 00397 // Clear the lampda buffer. 00398 for (i = 1; i < self->paritySize + 1; ++i) lambda[i] = 0; 00399 00400 lambda[0] = 1; 00401 00402 b = (uintGF*) alloca(sizeof(uintGF) * (self->paritySize + 1)); 00403 t = (uintGF*) alloca(sizeof(uintGF) * (self->paritySize + 1)); 00404 00405 for (i = 0; i < self->paritySize + 1; i++) { 00406 b[i] = indexOf[lambda[i]]; 00407 } 00408 00409 // Begin Berlekamp-Massey algorithm to determine error locator polynomial. 00410 el = 0; 00411 00412 for (r = 1; r <= self->paritySize; ++r) { 00413 uintGF discrepancy = 0; 00414 00415 // Compute discrepancy at the r-th step in poly-form. 00416 for (i = 0; i < r; i++) { 00417 if ((lambda[i] != 0) && (syndromes[r - i] != ALPHA_ZERO)) { 00418 discrepancy ^= 00419 alphaTo[modnn(indexOf[lambda[i]] + syndromes[r - i])]; 00420 } 00421 } 00422 00423 // Convert the discrepancy to index form. 00424 discrepancy = indexOf[discrepancy]; 00425 00426 // Is the discrepancy zero? 00427 if (discrepancy == ALPHA_ZERO) { 00428 // Move all array elements up. 00429 for (i = self->paritySize - 1; i >= 0; --i) { 00430 b[i + 1] = b[i]; 00431 } 00432 00433 // The first array element is zero. 00434 b[0] = ALPHA_ZERO; 00435 } else { 00436 // 7 lines below: T(x) <-- lambda(x) - discrepancy*x*b(x) 00437 t[0] = lambda[0]; 00438 00439 for (i = 0 ; i < self->paritySize; i++) { 00440 if (b[i] != ALPHA_ZERO) { 00441 t[i+1] = lambda[i+1] ^ alphaTo[modnn(discrepancy + b[i])]; 00442 } else { 00443 t[i+1] = lambda[i+1]; 00444 } 00445 } 00446 00447 if ((2 * el) <= (r - 1)) { 00448 el = r - el; 00449 00450 // 2 lines below: B(x) <-- inv(discrepancy) * lambda(x) 00451 for (i = 0; i <= self->paritySize; i++) { 00452 b[i] = (lambda[i] == 0) ? ALPHA_ZERO : 00453 modnn(indexOf[lambda[i]] - discrepancy + nn); 00454 } 00455 } else { 00456 // Move all array elements up. 00457 for (i = self->paritySize - 1; i >= 0; --i) { 00458 b[i + 1] = b[i]; 00459 } 00460 00461 // The first array element is zero. 00462 b[0] = ALPHA_ZERO; 00463 } 00464 00465 for (i = 0; i < self->paritySize + 1; ++i) lambda[i] = t[i]; 00466 } 00467 } 00468 00469 deg_lambda = 0; 00470 00471 // Convert lambda to index form and compute deg(lambda(x)). 00472 for (i = 0; i < self->paritySize + 1; ++i) { 00473 lambda[i] = indexOf[lambda[i]]; 00474 00475 if (lambda[i] != ALPHA_ZERO) { 00476 deg_lambda = i; 00477 } 00478 } 00479 00480 loc = (rvInt16*) alloca(sizeof(rvInt16) * self->paritySize); 00481 reg = (uintGF*) alloca(sizeof(uintGF) * (self->paritySize + 1)); 00482 root = (uintGF*) alloca(sizeof(uintGF) * self->paritySize); 00483 00484 // Find roots of the error locator polynomial by Chien search. 00485 for (i = 1; i < self->paritySize + 1; ++i) { 00486 reg[i] = lambda[i]; 00487 } 00488 00489 // Number of roots of lambda(x). 00490 count = 0; 00491 00492 for (i = 1; i <= nn; i++) { 00493 q = 1; 00494 00495 for (j = deg_lambda; j > 0; j--) { 00496 if (reg[j] != ALPHA_ZERO) { 00497 reg[j] = modnn(reg[j] + j); 00498 q ^= alphaTo[reg[j]]; 00499 } 00500 } 00501 00502 if (!q) { 00503 // Store root (index-form) and error location number. 00504 root[count] = (uintGF) i; 00505 loc[count] = nn - i; 00506 count++; 00507 } 00508 } 00509 00510 #ifdef DEBUG 00511 printf("\n Final error positions:\t"); 00512 for (i = 0; i < count; i++) { 00513 printf("%d ", loc[i]); 00514 } 00515 printf("\n"); 00516 #endif 00517 00518 // If deg(lambda) unequal to number of roots then uncorrectable error 00519 // detected: 00520 if (deg_lambda != count) { 00521 return 0; 00522 } 00523 00524 deg_omega = 0; 00525 00526 omega = (uintGF*) alloca(sizeof(uintGF) * (self->paritySize + 1)); 00527 00528 // Compute error evaluator poly omega(x) = 00529 // s(x) * lambda(x) (modulo x**(NN-KK)) 00530 // in index form. Also find deg(omega). 00531 for (i = 0; i < self->paritySize; ++i) { 00532 uintGF tmp = 0; 00533 00534 for (j = (deg_lambda < i) ? deg_lambda : i; j >= 0; --j) { 00535 if ((syndromes[i + 1 - j] != ALPHA_ZERO) && 00536 (lambda[j] != ALPHA_ZERO)) { 00537 tmp ^= alphaTo[modnn(syndromes[i + 1 - j] + lambda[j])]; 00538 } 00539 } 00540 00541 if (tmp != 0) { 00542 deg_omega = i; 00543 } 00544 00545 omega[i] = indexOf[tmp]; 00546 } 00547 00548 omega[self->paritySize] = ALPHA_ZERO; 00549 00550 // Compute error values in poly-form. 00551 for (j = count - 1; j >= 0; j--) { 00552 uintGF den; 00553 uintGF num1; 00554 uintGF num2; 00555 00556 num1 = 0; 00557 00558 for (i = deg_omega; i >= 0; i--) { 00559 if (omega[i] != ALPHA_ZERO) { 00560 num1 ^= alphaTo[modnn(omega[i] + i * root[j])]; 00561 } 00562 } 00563 00564 num2 = alphaTo[modnn(root[j] * (ALPHA_ROOT - 1) + nn)]; 00565 00566 den = 0; 00567 00568 // lambda[i+1] for i even is the formal derivative lambda_pr 00569 // of lambda[i]: 00570 for (i = MIN(deg_lambda, self->paritySize - 1) & ~1; i >= 0; i -=2) { 00571 if (lambda[i + 1] != ALPHA_ZERO) { 00572 den ^= alphaTo[modnn(lambda[i+1] + i * root[j])]; 00573 } 00574 } 00575 00576 if (den == 0) { 00577 #ifdef DEBUG 00578 printf("\n ERROR: denominator = 0\n"); 00579 #endif 00580 return 0; 00581 } 00582 00583 // Apply error to data. 00584 if (num1 != 0) { 00585 // We should never need to correct in the zero padding. 00586 if (loc[j] < self->zeroSize) { 00587 return 0; 00588 } 00589 00590 // Account for shortened data. 00591 if ((loc[j] >= self->zeroSize) && 00592 (loc[j] < self->zeroSize + self->dataSize)) { 00593 blockBuffer[loc[j] - self->zeroSize] ^= 00594 alphaTo[modnn(indexOf[num1] + indexOf[num2] + 00595 nn - indexOf[den])]; 00596 } 00597 } 00598 } 00599 00600 return 1; 00601 } 00602 00603 bool 00604 FEC__correct( 00605 FEC fec, 00606 unsigned int *data, 00607 unsigned int size) 00608 { 00609 unsigned char data_bytes[8]; 00610 unsigned int index; 00611 bool result; 00612 00613 /* Load {data} into {data_bytes}: */ 00614 for (index = 0; index < size; index++) { 00615 data_bytes[index] = data[index] & 0xff; 00616 } 00617 00618 /* Correct any errors: */ 00619 result = rvFec_Correct(fec, data_bytes); 00620 00621 /* Load {data_bytes} into {data}: */ 00622 for (index = 0; index < size; index++) { 00623 data[index] = data_bytes[index]; 00624 } 00625 00626 return result; 00627 } 00628 00629 void 00630 FEC__parity( 00631 FEC fec, 00632 unsigned int *data, 00633 unsigned int size) 00634 { 00635 unsigned char data_bytes[8]; 00636 unsigned int index; 00637 00638 /* Load {data} into {data_bytes}: */ 00639 for (index = 0; index < 8; index++) { 00640 data_bytes[index] = data[index] & 0xff; 00641 } 00642 00643 /* Compute the parity information: */ 00644 rvFec_Parity(fec, data_bytes, data_bytes + 4); 00645 00646 /* Load {data_bytes} into {data}: */ 00647 for (index = 0; index < 8; index++) { 00648 data[index] = data_bytes[index]; 00649 } 00650 } 00651 00652 FEC 00653 FEC__create( 00654 unsigned int symbol_size, 00655 unsigned int data_size, 00656 unsigned int parity_size) 00657 { 00658 return rvFec_New(symbol_size, data_size, parity_size); 00659 } 00660 00661 /* 00662 00663 GNU LESSER GENERAL PUBLIC LICENSE 00664 Version 2.1, February 1999 00665 00666 Copyright (C) 1991, 1999 Free Software Foundation, Inc. 00667 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 00668 Everyone is permitted to copy and distribute verbatim copies 00669 of this license document, but changing it is not allowed. 00670 00671 [This is the first released version of the Lesser GPL. It also counts 00672 as the successor of the GNU Library Public License, version 2, hence 00673 the version number 2.1.] 00674 00675 Preamble 00676 00677 The licenses for most software are designed to take away your 00678 freedom to share and change it. By contrast, the GNU General Public 00679 Licenses are intended to guarantee your freedom to share and change 00680 free software--to make sure the software is free for all its users. 00681 00682 This license, the Lesser General Public License, applies to some 00683 specially designated software packages--typically libraries--of the 00684 Free Software Foundation and other authors who decide to use it. You 00685 can use it too, but we suggest you first think carefully about whether 00686 this license or the ordinary General Public License is the better 00687 strategy to use in any particular case, based on the explanations below. 00688 00689 When we speak of free software, we are referring to freedom of use, 00690 not price. Our General Public Licenses are designed to make sure that 00691 you have the freedom to distribute copies of free software (and charge 00692 for this service if you wish); that you receive source code or can get 00693 it if you want it; that you can change the software and use pieces of 00694 it in new free programs; and that you are informed that you can do 00695 these things. 00696 00697 To protect your rights, we need to make restrictions that forbid 00698 distributors to deny you these rights or to ask you to surrender these 00699 rights. These restrictions translate to certain responsibilities for 00700 you if you distribute copies of the library or if you modify it. 00701 00702 For example, if you distribute copies of the library, whether gratis 00703 or for a fee, you must give the recipients all the rights that we gave 00704 you. You must make sure that they, too, receive or can get the source 00705 code. If you link other code with the library, you must provide 00706 complete object files to the recipients, so that they can relink them 00707 with the library after making changes to the library and recompiling 00708 it. And you must show them these terms so they know their rights. 00709 00710 We protect your rights with a two-step method: (1) we copyright the 00711 library, and (2) we offer you this license, which gives you legal 00712 permission to copy, distribute and/or modify the library. 00713 00714 To protect each distributor, we want to make it very clear that 00715 there is no warranty for the free library. Also, if the library is 00716 modified by someone else and passed on, the recipients should know 00717 that what they have is not the original version, so that the original 00718 author's reputation will not be affected by problems that might be 00719 introduced by others. 00720 00721 Finally, software patents pose a constant threat to the existence of 00722 any free program. We wish to make sure that a company cannot 00723 effectively restrict the users of a free program by obtaining a 00724 restrictive license from a patent holder. Therefore, we insist that 00725 any patent license obtained for a version of the library must be 00726 consistent with the full freedom of use specified in this license. 00727 00728 Most GNU software, including some libraries, is covered by the 00729 ordinary GNU General Public License. This license, the GNU Lesser 00730 General Public License, applies to certain designated libraries, and 00731 is quite different from the ordinary General Public License. We use 00732 this license for certain libraries in order to permit linking those 00733 libraries into non-free programs. 00734 00735 When a program is linked with a library, whether statically or using 00736 a shared library, the combination of the two is legally speaking a 00737 combined work, a derivative of the original library. The ordinary 00738 General Public License therefore permits such linking only if the 00739 entire combination fits its criteria of freedom. The Lesser General 00740 Public License permits more lax criteria for linking other code with 00741 the library. 00742 00743 We call this license the "Lesser" General Public License because it 00744 does Less to protect the user's freedom than the ordinary General 00745 Public License. It also provides other free software developers Less 00746 of an advantage over competing non-free programs. These disadvantages 00747 are the reason we use the ordinary General Public License for many 00748 libraries. However, the Lesser license provides advantages in certain 00749 special circumstances. 00750 00751 For example, on rare occasions, there may be a special need to 00752 encourage the widest possible use of a certain library, so that it becomes 00753 a de-facto standard. To achieve this, non-free programs must be 00754 allowed to use the library. A more frequent case is that a free 00755 library does the same job as widely used non-free libraries. In this 00756 case, there is little to gain by limiting the free library to free 00757 software only, so we use the Lesser General Public License. 00758 00759 In other cases, permission to use a particular library in non-free 00760 programs enables a greater number of people to use a large body of 00761 free software. For example, permission to use the GNU C Library in 00762 non-free programs enables many more people to use the whole GNU 00763 operating system, as well as its variant, the GNU/Linux operating 00764 system. 00765 00766 Although the Lesser General Public License is Less protective of the 00767 users' freedom, it does ensure that the user of a program that is 00768 linked with the Library has the freedom and the wherewithal to run 00769 that program using a modified version of the Library. 00770 00771 The precise terms and conditions for copying, distribution and 00772 modification follow. Pay close attention to the difference between a 00773 "work based on the library" and a "work that uses the library". The 00774 former contains code derived from the library, whereas the latter must 00775 be combined with the library in order to run. 00776 00777 GNU LESSER GENERAL PUBLIC LICENSE 00778 TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION 00779 00780 0. This License Agreement applies to any software library or other 00781 program which contains a notice placed by the copyright holder or 00782 other authorized party saying it may be distributed under the terms of 00783 this Lesser General Public License (also called "this License"). 00784 Each licensee is addressed as "you". 00785 00786 A "library" means a collection of software functions and/or data 00787 prepared so as to be conveniently linked with application programs 00788 (which use some of those functions and data) to form executables. 00789 00790 The "Library", below, refers to any such software library or work 00791 which has been distributed under these terms. A "work based on the 00792 Library" means either the Library or any derivative work under 00793 copyright law: that is to say, a work containing the Library or a 00794 portion of it, either verbatim or with modifications and/or translated 00795 straightforwardly into another language. (Hereinafter, translation is 00796 included without limitation in the term "modification".) 00797 00798 "Source code" for a work means the preferred form of the work for 00799 making modifications to it. For a library, complete source code means 00800 all the source code for all modules it contains, plus any associated 00801 interface definition files, plus the scripts used to control compilation 00802 and installation of the library. 00803 00804 Activities other than copying, distribution and modification are not 00805 covered by this License; they are outside its scope. The act of 00806 running a program using the Library is not restricted, and output from 00807 such a program is covered only if its contents constitute a work based 00808 on the Library (independent of the use of the Library in a tool for 00809 writing it). Whether that is true depends on what the Library does 00810 and what the program that uses the Library does. 00811 00812 1. You may copy and distribute verbatim copies of the Library's 00813 complete source code as you receive it, in any medium, provided that 00814 you conspicuously and appropriately publish on each copy an 00815 appropriate copyright notice and disclaimer of warranty; keep intact 00816 all the notices that refer to this License and to the absence of any 00817 warranty; and distribute a copy of this License along with the 00818 Library. 00819 00820 You may charge a fee for the physical act of transferring a copy, 00821 and you may at your option offer warranty protection in exchange for a 00822 fee. 00823 00824 2. You may modify your copy or copies of the Library or any portion 00825 of it, thus forming a work based on the Library, and copy and 00826 distribute such modifications or work under the terms of Section 1 00827 above, provided that you also meet all of these conditions: 00828 00829 a) The modified work must itself be a software library. 00830 00831 b) You must cause the files modified to carry prominent notices 00832 stating that you changed the files and the date of any change. 00833 00834 c) You must cause the whole of the work to be licensed at no 00835 charge to all third parties under the terms of this License. 00836 00837 d) If a facility in the modified Library refers to a function or a 00838 table of data to be supplied by an application program that uses 00839 the facility, other than as an argument passed when the facility 00840 is invoked, then you must make a good faith effort to ensure that, 00841 in the event an application does not supply such function or 00842 table, the facility still operates, and performs whatever part of 00843 its purpose remains meaningful. 00844 00845 (For example, a function in a library to compute square roots has 00846 a purpose that is entirely well-defined independent of the 00847 application. Therefore, Subsection 2d requires that any 00848 application-supplied function or table used by this function must 00849 be optional: if the application does not supply it, the square 00850 root function must still compute square roots.) 00851 00852 These requirements apply to the modified work as a whole. If 00853 identifiable sections of that work are not derived from the Library, 00854 and can be reasonably considered independent and separate works in 00855 themselves, then this License, and its terms, do not apply to those 00856 sections when you distribute them as separate works. But when you 00857 distribute the same sections as part of a whole which is a work based 00858 on the Library, the distribution of the whole must be on the terms of 00859 this License, whose permissions for other licensees extend to the 00860 entire whole, and thus to each and every part regardless of who wrote 00861 it. 00862 00863 Thus, it is not the intent of this section to claim rights or contest 00864 your rights to work written entirely by you; rather, the intent is to 00865 exercise the right to control the distribution of derivative or 00866 collective works based on the Library. 00867 00868 In addition, mere aggregation of another work not based on the Library 00869 with the Library (or with a work based on the Library) on a volume of 00870 a storage or distribution medium does not bring the other work under 00871 the scope of this License. 00872 00873 3. You may opt to apply the terms of the ordinary GNU General Public 00874 License instead of this License to a given copy of the Library. To do 00875 this, you must alter all the notices that refer to this License, so 00876 that they refer to the ordinary GNU General Public License, version 2, 00877 instead of to this License. (If a newer version than version 2 of the 00878 ordinary GNU General Public License has appeared, then you can specify 00879 that version instead if you wish.) Do not make any other change in 00880 these notices. 00881 00882 Once this change is made in a given copy, it is irreversible for 00883 that copy, so the ordinary GNU General Public License applies to all 00884 subsequent copies and derivative works made from that copy. 00885 00886 This option is useful when you wish to copy part of the code of 00887 the Library into a program that is not a library. 00888 00889 4. You may copy and distribute the Library (or a portion or 00890 derivative of it, under Section 2) in object code or executable form 00891 under the terms of Sections 1 and 2 above provided that you accompany 00892 it with the complete corresponding machine-readable source code, which 00893 must be distributed under the terms of Sections 1 and 2 above on a 00894 medium customarily used for software interchange. 00895 00896 If distribution of object code is made by offering access to copy 00897 from a designated place, then offering equivalent access to copy the 00898 source code from the same place satisfies the requirement to 00899 distribute the source code, even though third parties are not 00900 compelled to copy the source along with the object code. 00901 00902 5. A program that contains no derivative of any portion of the 00903 Library, but is designed to work with the Library by being compiled or 00904 linked with it, is called a "work that uses the Library". Such a 00905 work, in isolation, is not a derivative work of the Library, and 00906 therefore falls outside the scope of this License. 00907 00908 However, linking a "work that uses the Library" with the Library 00909 creates an executable that is a derivative of the Library (because it 00910 contains portions of the Library), rather than a "work that uses the 00911 library". The executable is therefore covered by this License. 00912 Section 6 states terms for distribution of such executables. 00913 00914 When a "work that uses the Library" uses material from a header file 00915 that is part of the Library, the object code for the work may be a 00916 derivative work of the Library even though the source code is not. 00917 Whether this is true is especially significant if the work can be 00918 linked without the Library, or if the work is itself a library. The 00919 threshold for this to be true is not precisely defined by law. 00920 00921 If such an object file uses only numerical parameters, data 00922 structure layouts and accessors, and small macros and small inline 00923 functions (ten lines or less in length), then the use of the object 00924 file is unrestricted, regardless of whether it is legally a derivative 00925 work. (Executables containing this object code plus portions of the 00926 Library will still fall under Section 6.) 00927 00928 Otherwise, if the work is a derivative of the Library, you may 00929 distribute the object code for the work under the terms of Section 6. 00930 Any executables containing that work also fall under Section 6, 00931 whether or not they are linked directly with the Library itself. 00932 00933 6. As an exception to the Sections above, you may also combine or 00934 link a "work that uses the Library" with the Library to produce a 00935 work containing portions of the Library, and distribute that work 00936 under terms of your choice, provided that the terms permit 00937 modification of the work for the customer's own use and reverse 00938 engineering for debugging such modifications. 00939 00940 You must give prominent notice with each copy of the work that the 00941 Library is used in it and that the Library and its use are covered by 00942 this License. You must supply a copy of this License. If the work 00943 during execution displays copyright notices, you must include the 00944 copyright notice for the Library among them, as well as a reference 00945 directing the user to the copy of this License. Also, you must do one 00946 of these things: 00947 00948 a) Accompany the work with the complete corresponding 00949 machine-readable source code for the Library including whatever 00950 changes were used in the work (which must be distributed under 00951 Sections 1 and 2 above); and, if the work is an executable linked 00952 with the Library, with the complete machine-readable "work that 00953 uses the Library", as object code and/or source code, so that the 00954 user can modify the Library and then relink to produce a modified 00955 executable containing the modified Library. (It is understood 00956 that the user who changes the contents of definitions files in the 00957 Library will not necessarily be able to recompile the application 00958 to use the modified definitions.) 00959 00960 b) Use a suitable shared library mechanism for linking with the 00961 Library. A suitable mechanism is one that (1) uses at run time a 00962 copy of the library already present on the user's computer system, 00963 rather than copying library functions into the executable, and (2) 00964 will operate properly with a modified version of the library, if 00965 the user installs one, as long as the modified version is 00966 interface-compatible with the version that the work was made with. 00967 00968 c) Accompany the work with a written offer, valid for at 00969 least three years, to give the same user the materials 00970 specified in Subsection 6a, above, for a charge no more 00971 than the cost of performing this distribution. 00972 00973 d) If distribution of the work is made by offering access to copy 00974 from a designated place, offer equivalent access to copy the above 00975 specified materials from the same place. 00976 00977 e) Verify that the user has already received a copy of these 00978 materials or that you have already sent this user a copy. 00979 00980 For an executable, the required form of the "work that uses the 00981 Library" must include any data and utility programs needed for 00982 reproducing the executable from it. However, as a special exception, 00983 the materials to be distributed need not include anything that is 00984 normally distributed (in either source or binary form) with the major 00985 components (compiler, kernel, and so on) of the operating system on 00986 which the executable runs, unless that component itself accompanies 00987 the executable. 00988 00989 It may happen that this requirement contradicts the license 00990 restrictions of other proprietary libraries that do not normally 00991 accompany the operating system. Such a contradiction means you cannot 00992 use both them and the Library together in an executable that you 00993 distribute. 00994 00995 7. You may place library facilities that are a work based on the 00996 Library side-by-side in a single library together with other library 00997 facilities not covered by this License, and distribute such a combined 00998 library, provided that the separate distribution of the work based on 00999 the Library and of the other library facilities is otherwise 01000 permitted, and provided that you do these two things: 01001 01002 a) Accompany the combined library with a copy of the same work 01003 based on the Library, uncombined with any other library 01004 facilities. This must be distributed under the terms of the 01005 Sections above. 01006 01007 b) Give prominent notice with the combined library of the fact 01008 that part of it is a work based on the Library, and explaining 01009 where to find the accompanying uncombined form of the same work. 01010 01011 8. You may not copy, modify, sublicense, link with, or distribute 01012 the Library except as expressly provided under this License. Any 01013 attempt otherwise to copy, modify, sublicense, link with, or 01014 distribute the Library is void, and will automatically terminate your 01015 rights under this License. However, parties who have received copies, 01016 or rights, from you under this License will not have their licenses 01017 terminated so long as such parties remain in full compliance. 01018 01019 9. You are not required to accept this License, since you have not 01020 signed it. However, nothing else grants you permission to modify or 01021 distribute the Library or its derivative works. These actions are 01022 prohibited by law if you do not accept this License. Therefore, by 01023 modifying or distributing the Library (or any work based on the 01024 Library), you indicate your acceptance of this License to do so, and 01025 all its terms and conditions for copying, distributing or modifying 01026 the Library or works based on it. 01027 01028 10. Each time you redistribute the Library (or any work based on the 01029 Library), the recipient automatically receives a license from the 01030 original licensor to copy, distribute, link with or modify the Library 01031 subject to these terms and conditions. You may not impose any further 01032 restrictions on the recipients' exercise of the rights granted herein. 01033 You are not responsible for enforcing compliance by third parties with 01034 this License. 01035 01036 11. If, as a consequence of a court judgment or allegation of patent 01037 infringement or for any other reason (not limited to patent issues), 01038 conditions are imposed on you (whether by court order, agreement or 01039 otherwise) that contradict the conditions of this License, they do not 01040 excuse you from the conditions of this License. If you cannot 01041 distribute so as to satisfy simultaneously your obligations under this 01042 License and any other pertinent obligations, then as a consequence you 01043 may not distribute the Library at all. For example, if a patent 01044 license would not permit royalty-free redistribution of the Library by 01045 all those who receive copies directly or indirectly through you, then 01046 the only way you could satisfy both it and this License would be to 01047 refrain entirely from distribution of the Library. 01048 01049 If any portion of this section is held invalid or unenforceable under any 01050 particular circumstance, the balance of the section is intended to apply, 01051 and the section as a whole is intended to apply in other circumstances. 01052 01053 It is not the purpose of this section to induce you to infringe any 01054 patents or other property right claims or to contest validity of any 01055 such claims; this section has the sole purpose of protecting the 01056 integrity of the free software distribution system which is 01057 implemented by public license practices. Many people have made 01058 generous contributions to the wide range of software distributed 01059 through that system in reliance on consistent application of that 01060 system; it is up to the author/donor to decide if he or she is willing 01061 to distribute software through any other system and a licensee cannot 01062 impose that choice. 01063 01064 This section is intended to make thoroughly clear what is believed to 01065 be a consequence of the rest of this License. 01066 01067 12. If the distribution and/or use of the Library is restricted in 01068 certain countries either by patents or by copyrighted interfaces, the 01069 original copyright holder who places the Library under this License may add 01070 an explicit geographical distribution limitation excluding those countries, 01071 so that distribution is permitted only in or among countries not thus 01072 excluded. In such case, this License incorporates the limitation as if 01073 written in the body of this License. 01074 01075 13. The Free Software Foundation may publish revised and/or new 01076 versions of the Lesser General Public License from time to time. 01077 Such new versions will be similar in spirit to the present version, 01078 but may differ in detail to address new problems or concerns. 01079 01080 Each version is given a distinguishing version number. If the Library 01081 specifies a version number of this License which applies to it and 01082 "any later version", you have the option of following the terms and 01083 conditions either of that version or of any later version published by 01084 the Free Software Foundation. If the Library does not specify a 01085 license version number, you may choose any version ever published by 01086 the Free Software Foundation. 01087 01088 14. If you wish to incorporate parts of the Library into other free 01089 programs whose distribution conditions are incompatible with these, 01090 write to the author to ask for permission. For software which is 01091 copyrighted by the Free Software Foundation, write to the Free 01092 Software Foundation; we sometimes make exceptions for this. Our 01093 decision will be guided by the two goals of preserving the free status 01094 of all derivatives of our free software and of promoting the sharing 01095 and reuse of software generally. 01096 01097 NO WARRANTY 01098 01099 15. BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO 01100 WARRANTY FOR THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW. 01101 EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR 01102 OTHER PARTIES PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY 01103 KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE 01104 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 01105 PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE 01106 LIBRARY IS WITH YOU. SHOULD THE LIBRARY PROVE DEFECTIVE, YOU ASSUME 01107 THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION. 01108 01109 16. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN 01110 WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY 01111 AND/OR REDISTRIBUTE THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU 01112 FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR 01113 CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE 01114 LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING 01115 RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A 01116 FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF 01117 SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH 01118 DAMAGES. 01119 01120 END OF TERMS AND CONDITIONS 01121 01122 How to Apply These Terms to Your New Libraries 01123 01124 If you develop a new library, and you want it to be of the greatest 01125 possible use to the public, we recommend making it free software that 01126 everyone can redistribute and change. You can do so by permitting 01127 redistribution under these terms (or, alternatively, under the terms of the 01128 ordinary General Public License). 01129 01130 To apply these terms, attach the following notices to the library. It is 01131 safest to attach them to the start of each source file to most effectively 01132 convey the exclusion of warranty; and each file should have at least the 01133 "copyright" line and a pointer to where the full notice is found. 01134 01135 <one line to give the library's name and a brief idea of what it does.> 01136 Copyright (C) <year> <name of author> 01137 01138 This library is free software; you can redistribute it and/or 01139 modify it under the terms of the GNU Lesser General Public 01140 License as published by the Free Software Foundation; either 01141 version 2.1 of the License, or (at your option) any later version. 01142 01143 This library is distributed in the hope that it will be useful, 01144 but WITHOUT ANY WARRANTY; without even the implied warranty of 01145 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 01146 Lesser General Public License for more details. 01147 01148 You should have received a copy of the GNU Lesser General Public 01149 License along with this library; if not, write to the Free Software 01150 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 01151 01152 Also add information on how to contact you by electronic and paper mail. 01153 01154 You should also get your employer (if you work as a programmer) or your 01155 school, if any, to sign a "copyright disclaimer" for the library, if 01156 necessary. Here is a sample; alter the names: 01157 01158 Yoyodyne, Inc., hereby disclaims all copyright interest in the 01159 library `Frob' (a library for tweaking knobs) written by James Random Hacker. 01160 01161 <signature of Ty Coon>, 1 April 1990 01162 Ty Coon, President of Vice 01163 01164 That's all there is to it! 01165 01166 */