[MN-dev] [mndiff]: r83 - in trunk/noe: gfft.c rs.c rs.h test.c
michael
subversion at mplayerhq.hu
Tue Jul 10 00:57:06 CEST 2007
Author: michael
Date: Tue Jul 10 00:57:06 2007
New Revision: 83
Log:
version from 2006-06-22 20:40
Modified:
trunk/noe/gfft.c
trunk/noe/rs.c
trunk/noe/rs.h
trunk/noe/test.c
Modified: trunk/noe/gfft.c
==============================================================================
--- trunk/noe/gfft.c (original)
+++ trunk/noe/gfft.c Tue Jul 10 00:57:06 2007
@@ -32,9 +32,9 @@ void noe_gfft_init(){
for(i=0; i<256; i++){
int x= i;
- x = (((x & 0xaa) >> 1) | ((x & 0x55) << 1));
- x = (((x & 0xcc) >> 2) | ((x & 0x33) << 2));
- x = (( x >> 4) | ((x & 0x0f) << 4));
+ x = ((x & 0xaa) >> 1) | ((x & 0x55) << 1);
+ x = ((x & 0xcc) >> 2) | ((x & 0x33) << 2);
+ x = ( x >> 4) | ( x << 4);
noe_revTable[i]= x;
}
Modified: trunk/noe/rs.c
==============================================================================
--- trunk/noe/rs.c (original)
+++ trunk/noe/rs.c Tue Jul 10 00:57:06 2007
@@ -48,91 +48,63 @@ void EXT(getSyndrom)(GFF4Element *syn, G
syn[0]= 1;
}
-noe_RsEncoder *EXT(getRsEncoder)(int parityCount, int tLocation){
- const int dataCount= SIZE - parityCount - 1;
- noe_RsEncoder *encoder= memalign(16, sizeof(noe_RsEncoder));
-
- encoder->tPoly=NULL;
-
- encoder->parityCount= parityCount;
-
- if(tLocation>=0 && tLocation<dataCount && !M){
- GFF4Element temp[SIZE - 1];
- memset(temp, 0, sizeof(temp));
- temp[tLocation]= 1;
- EXT(rsEncode)(encoder, temp);
- encoder->tPoly= memalign(16, sizeof(GFF4Element)*(parityCount));
- encoder->tLocation= tLocation;
- memcpy(encoder->tPoly, temp + dataCount, parityCount*sizeof(GFF4Element));
- }
-
- return encoder;
-}
-
-#define free(p) if(p) free(p); p=NULL;
-void EXT(freeRsEncoder)(noe_RsEncoder *encoder){
- if(!encoder) return;
-
- free(encoder->tPoly);
-
- free(encoder);
-}
-
/**
*
*/
-void EXT(rsEncode)(noe_RsEncoder *encoder, GFF4Element *data){
+void EXT(rsEncode)(GFF4Element *data, GFF4Element *parityLocator, int parityCount){
int i;
- const int parityCount= encoder->parityCount;
const int dataCount= SIZE - parityCount - 1;
- int erasureLocations[parityCount];
+ int parityLocations[parityCount];
for(i=0; i<parityCount; i++)
- erasureLocations[i]= dataCount + i;
+ parityLocations[i]= dataCount + i;
- EXT(rsDecode)(data, erasureLocations, parityCount, parityCount);
+ EXT(rsDecode)(data, parityLocations, parityLocator, parityCount, parityCount);
}
#if M==0
//FIXME avoid the noe_RsEncoder dependancy
-int EXT(rsTransform)(noe_RsEncoder *e, GFF4Element *data, int encode){
+int EXT(rsTransform)(GFF4Element *data, GFF4Element *parityLocator, int parityCount, GFF4Element *tPoly, int tLocation, int encode){
int i, j;
- const int parityCount= e->parityCount;
const int dataCount= SIZE - parityCount - 1;
- char stats[SIZE];
- GFF4Element t= data[ e->tLocation ];
+ GFF4Element temp[SIZE-1];
+ char *stats= (char*)temp;
+ GFF4Element t= data[ tLocation ];
- memset(stats, 0, sizeof(stats));
+ if(tLocation<0 || tLocation>=dataCount)
+ return -1;
+
+ if(tPoly[0]<=0){
+ memset(temp, 0, sizeof(temp));
+ temp[tLocation]= 1;
+ EXT(rsEncode)(temp, parityLocator, parityCount);
+ memcpy(tPoly, temp + dataCount, parityCount*sizeof(GFF4Element));
+ }
+
+ memset(stats, 0, SIZE);
for(i=0; i<parityCount; i++){
- GFF4Element p= diff(data[i+dataCount], prod(e->tPoly[i], t));
+ GFF4Element p= diff(data[i+dataCount], prod(tPoly[i], t));
- stats[ prod(MINUS1 - p, inv(e->tPoly[i])) ]|=1; //FIXME get rid of the neg
+ stats[ prod(MINUS1 - p, inv(tPoly[i])) ]=1; //FIXME get rid of the neg
}
if(encode){
- for(j=i=0; i<SIZE; i++){
- if(stats[i])
- continue;
- if(j == t)
- break;
- j++;
- }
+ for(j=i=0; i<SIZE && j<=t; i++)
+ j+= !stats[i];
+ i--;
if(i>=SIZE)
return -1;
}else{
- for(j=i=0; j<t; j++){
- if(stats[j])
- continue;
- i++;
- }
+ for(j=i=0; j<t; j++)
+ i+= stats[j]^1;
}
- data[ e->tLocation ]= i;
+ data[ tLocation ]= i;
t= diff(i, t);
- for(i=0; i<parityCount; i++){
- data[i+dataCount]= sum(data[i+dataCount], prod(e->tPoly[i], t));
- }
+ for(i=0; i<parityCount; i++)
+ data[i+dataCount]= sum(data[i+dataCount], prod(tPoly[i], t));
+
return 0;
}
#endif
@@ -382,11 +354,10 @@ static int rsBerlekampMassey(GFF4Element
return k;
}
-int EXT(rsDecode)(GFF4Element *data, int *erasure, int erasureCount, int parityCount){
- int i;
+int EXT(rsDecode)(GFF4Element *data, int *erasure, GFF4Element *erasureLocator, int erasureCount, int parityCount){
+ int i, j, k;
int errorCount, gfftEval;
const int dataCount= SIZE - 1 - parityCount;
- GFF4Element erasureLocator[erasureCount + 1];
GFF4Element locator0[SIZE]; //[parityCount + 1 + 1];
GFF4Element locator1[SIZE]; //[parityCount + 1 + 1];
GFF4Element *locators[2]={locator0, locator1};
@@ -394,6 +365,7 @@ int EXT(rsDecode)(GFF4Element *data, int
GFF4Element omega1[SIZE - 1 + 1];
GFF4Element *omegas[2]={omega0, omega1}; //FIXME clean this shit up
GFF4Element *errorLocator, *omega, *syn, *psi;
+ int error[parityCount>>1];
syn= omegas[1];
@@ -413,7 +385,8 @@ int EXT(rsDecode)(GFF4Element *data, int
//FIXME check truncated symbols syndrom
if(erasureCount){
- EXT(synthPoly)(erasureLocator, erasure, erasureCount);
+ if(erasureLocator[0]<=0)
+ EXT(synthPoly)(erasureLocator, erasure, erasureCount);
EXT(partialProdPoly)(syn, erasureLocator, syn, syn[0]);
}
#if 0
@@ -450,71 +423,57 @@ for(i=0; i<erasureCount; i++){
memset(errorLocator + errorCount+2, 0, (SIZE - errorCount-2)*sizeof(GFF4Element));
errorLocator++;
EXT(gfft)(errorLocator, errorLocator, SHIFT);
- }
- if(gfftEval>1){
- memset(omega + omega[0] + 2, 0, (SIZE - omega[0] - 2)*sizeof(GFF4Element));
- memset(psi + psi [0] + 2, 0, (SIZE - psi [0] - 2)*sizeof(GFF4Element));
- omega++;
- psi++;
- EXT(gfft)(omega, omega, SHIFT);
- EXT(gfft)(psi , psi , SHIFT);
- }
-
- if(errorCount){
- for(i=0; i<SIZE-1; i++){
- int r, e;
- GFF4Element X, nom, denom;
+ if(gfftEval>1){
+ memset(omega + omega[0] + 2, 0, (SIZE - omega[0] - 2)*sizeof(GFF4Element));
+ memset(psi + psi [0] + 2, 0, (SIZE - psi [0] - 2)*sizeof(GFF4Element));
+ omega++;
+ psi++;
+ EXT(gfft)(omega, omega, SHIFT);
+ EXT(gfft)(psi , psi , SHIFT);
+ }
- if(gfftEval){ //FIXME optimize
- if(errorLocator[i])
- continue;
-
- r= i ? MINUS1 - bitReverse(i) : 0; //FIXME i=0 <->MINUS1 ?
- }else{
- if(EXT(evalPoly)(errorLocator, EXT(exp)[i]))
- continue;
-
- r= i ? MINUS1 - i : 0;
- }
-//printf("E%6d %6d\n", i, r);
+ for(j=0,i=0; j<errorCount; i++){
+ assert(i<SIZE);
+ if(!errorLocator[i])
+ error[j++]= i ? MINUS1 - bitReverse(i) : 0;
+ }
+ }else{
+ for(j=0,i=0; j<errorCount; i++){
+ assert(i<SIZE);
+ if(!EXT(evalPoly)(errorLocator, i)){
+ GFF4Element rem=errorLocator[ errorLocator[0]+1 ];
+ for(k=errorLocator[0]; k>0; k--){
+ GFF4Element temp= sum(errorLocator[k], prod(rem, i));
+ errorLocator[k]= rem;
+ rem= temp;
+ }
+ assert(rem == 0);
+ errorLocator[0]--;
- X= EXT(exp)[r];
- if(gfftEval>1){
- nom= prod(X, omega[i]);
- denom= psi[i];
- }else{
- GFF4Element invX= EXT(exp)[MINUS1 - r];
- nom= prod(X, EXT(evalPoly)(omega, invX));
- denom= EXT(evalPoly)(psi, invX);
+ error[j++]= EXT(log)[i] ? MINUS1 - EXT(log)[i] : 0;
}
-
- assert(r>=0 && r<=SIZE-2);
- e= prod(nom, inv(denom));
- if(data[r]==0 && e==MINUS1 && r < dataCount)
- return -1;
- data[r]= sum(data[r], e);
}
}
- for(i=0; i<erasureCount; i++){
- const int r= erasure[i];
- const GFF4Element X = EXT(exp)[r];
- GFF4Element nom, denom;
+ for(i=0; i<erasureCount + errorCount; i++){
+ const int r= i<erasureCount ? erasure[i] : error[i-erasureCount];
+ int e;
assert(r>=0 && r<MINUS1);
if(gfftEval>1){
int i2= bitReverse(MINUS1 - r);
- nom= prod(X, omega[i2]);
- denom= psi[i2];
+ e= r - EXT(log)[ psi[i2]];
+ if(e<0) e+= MINUS1;
+ e+= EXT(log)[omega[i2]];
}else{
- const GFF4Element invX= EXT(exp)[MINUS1 - r];
- nom= prod(X, EXT(evalPoly)(omega, invX));
- denom= EXT(evalPoly)(psi, invX);
+ GFF4Element invX= EXT(exp)[MINUS1 - r];
+ e= r - EXT(log)[EXT(evalPoly)( psi, invX)];
+ if(e<0) e+= MINUS1;
+ e+= EXT(log)[EXT(evalPoly)(omega, invX)];
}
- assert(data[r]==0);
- data[r]= prod(nom, inv(denom));
+ data[r]= sum(data[r], EXT(exp)[e]);
}
return erasureCount + errorCount;
Modified: trunk/noe/rs.h
==============================================================================
--- trunk/noe/rs.h (original)
+++ trunk/noe/rs.h Tue Jul 10 00:57:06 2007
@@ -16,27 +16,19 @@
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
-typedef struct noe_RsEncoder{
- int parityCount;
- int tLocation;
- GFF4Element *tPoly;
-}noe_RsEncoder;
-
/**
* gets the syndroms.
* @param src a 2^16 entry long polynom
* @param syn the syndrom polynom will be stored here
*/
void EXT(getSyndrom)(GFF4Element *syn, GFF4Element *src, int order);
-noe_RsEncoder *EXT(getRsEncoder)(int parityOrder, int tLocation);
-void EXT(freeRsEncoder)(noe_RsEncoder *encoder);
/**
*
*/
-void EXT(rsEncode)(noe_RsEncoder *encoder, GFF4Element *data);
+void EXT(rsEncode)(GFF4Element *data, GFF4Element *parityLocator, int parityCount);
-int EXT(rsDecode)(GFF4Element *data, int *erased, int erasedCount, int parityCount);
+int EXT(rsDecode)(GFF4Element *data, int *erased, GFF4Element *erassureLocator, int erasedCount, int parityCount);
#if M==0
-int EXT(rsTransform)(noe_RsEncoder *e, GFF4Element *data, int encode);
+int EXT(rsTransform)(GFF4Element *data, GFF4Element *parityLocator, int parityCount, GFF4Element *tPoly, int tLocation, int encode);
#endif
Modified: trunk/noe/test.c
==============================================================================
--- trunk/noe/test.c (original)
+++ trunk/noe/test.c Tue Jul 10 00:57:06 2007
@@ -153,6 +153,7 @@ int main(){
printf("."); fflush(stdout);
}
#endif
+#if 0
printf("\nTesting encoder");
for(i=1; i<SIZE/2; i+=i+5){
int n= SIZE - 1;
@@ -161,11 +162,13 @@ int main(){
// GFF4Element gen[i+1];
GFF4Element data[k];
GFF4Element code[n];
- noe_RsEncoder *encoder;
int pass=5;
int tLoc= rand() % k;
+ GFF4Element parityLocator[i+2];
+ GFF4Element tPoly[i];
- encoder= EXT(getRsEncoder)(i, tLoc);
+ parityLocator[0]=0;
+ tPoly[0]= 0;
for(pass=5; pass; pass--){
for(j=0; j<k; j++)
@@ -174,7 +177,7 @@ int main(){
memcpy(code, data, n*sizeof(GFF4Element));
{START_TIMER
- EXT(rsEncode)(encoder, code);
+ EXT(rsEncode)(code, parityLocator, i);
STOP_TIMER}
EXT(getSyndrom)(syn, code, i);
//FIXME check that code contains data, but its not touched so ...
@@ -186,7 +189,7 @@ STOP_TIMER}
if(syn[j+1+1]) printf("FAIL generator:%d coefficient:%d is %X\n", i, j, syn[j+1]);
}
#if M==0
- if(EXT(rsTransform)(encoder, code, 1) < 0)
+ if(EXT(rsTransform)(code, parityLocator, i, tPoly, tLoc, 1) < 0)
printf("transform failure\n");
EXT(getSyndrom)(syn, code, i);
for(j=0; j<i; j++)
@@ -196,7 +199,7 @@ STOP_TIMER}
printf("illegal symbol detected\n");
}
- if(EXT(rsTransform)(encoder, code, 0) < 0)
+ if(EXT(rsTransform)(code, parityLocator, i, tPoly, tLoc, 0) < 0)
printf("inv-transform failure\n");
EXT(getSyndrom)(syn, code, i);
for(j=0; j<i; j++)
@@ -208,21 +211,21 @@ STOP_TIMER}
#endif
printf("."); fflush(stdout);
}
- EXT(freeRsEncoder)(encoder);
}
#endif
+#endif
printf("\nTesting decoder");
for(i=1; i<2000 && i<SIZE/2; i+=(SIZE == 0x10001 ? 100 : 10)){
int n= SIZE - 1;
int k= SIZE - 1 - i;
-// GFF4Element syn[n];
int erased[i];
+ GFF4Element erasureLocator[i+2];
GFF4Element data[k];
GFF4Element code[n];
- noe_RsEncoder *encoder;
+ GFF4Element parityLocator[i+2];
int pass=5;
- encoder= EXT(getRsEncoder)(i, 0);
+ parityLocator[0]= 0;
for(pass=5; pass; pass--){
int erasedCount, errorCount;
@@ -230,8 +233,9 @@ STOP_TIMER}
data[j]= rand() & MASK;
memcpy(code, data, n*sizeof(GFF4Element));
+ erasureLocator[0]= 0;
- EXT(rsEncode)(encoder, code);
+ EXT(rsEncode)(code, parityLocator, i);
erasedCount=0;
if(rand()&0x40){
@@ -263,7 +267,7 @@ STOP_TIMER}
}
}
//printf("erased:%d errors:%d parity:%d\n", erasedCount, errorCount, i);
- EXT(rsDecode)(code, erased, erasedCount, i);
+ EXT(rsDecode)(code, erased, erasureLocator, erasedCount, i);
// EXT(printPoly)(gen, i);
// EXT(printPoly)(syn, i-1);
@@ -276,7 +280,6 @@ STOP_TIMER}
}
printf("."); fflush(stdout);
}
- EXT(freeRsEncoder)(encoder);
}
#if 0
{
More information about the Mndiff-dev
mailing list