FEC.cpp
Go to the documentation of this file.
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 */


fiducial_lib
Author(s): Wayne Gramlich
autogenerated on Thu Jun 6 2019 18:08:04