[MN-dev] [mndiff]: r87 - in trunk/noe: gfft.c gfft.h mina.c rs.c rs.h test.c
michael
subversion at mplayerhq.hu
Tue Oct 21 13:54:49 CEST 2008
Author: michael
Date: Tue Oct 21 13:54:49 2008
New Revision: 87
Log:
Efficiently support shortened codes.
Modified:
trunk/noe/gfft.c
trunk/noe/gfft.h
trunk/noe/mina.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 Oct 21 13:54:49 2008
@@ -40,12 +40,12 @@ void noe_gfft_init(){
}
}
-void EXT(permute)(GFF4Element *dst, GFF4Element *src, int outCount){
+void EXT(permute)(GFF4Element *dst, GFF4Element *src, int outCount, int codeBits){
int i;
if(dst==src){
for(i=1; i<outCount; i++){
- const int r= bitReverse(i);
+ const int r= bitReverse(i, codeBits);
unsigned int t;
if(r<=i) continue;
t= dst[i];
@@ -54,7 +54,7 @@ void EXT(permute)(GFF4Element *dst, GFF4
}
}else{
for(i=0; i<outCount; i++){
- dst[i]= src[bitReverse(i)];
+ dst[i]= src[bitReverse(i, codeBits)];
}
}
}
Modified: trunk/noe/gfft.h
==============================================================================
--- trunk/noe/gfft.h (original)
+++ trunk/noe/gfft.h Tue Oct 21 13:54:49 2008
@@ -19,14 +19,15 @@
void noe_gfft_init();
void EXT(gfft)(GFF4Element *dst, GFF4Element *src, int size);
void EXT(igfft)(GFF4Element *dst, GFF4Element *src, int size);
-void EXT(permute)(GFF4Element *dst, GFF4Element *src, int outCount);
+void EXT(permute)(GFF4Element *dst, GFF4Element *src, int outCount, int codeBits);
extern uint8_t noe_revTable[256];
-static inline unsigned int bitReverse(unsigned int x){
+static inline unsigned int bitReverse(unsigned int x, int codeBits){
#if SHIFT==16
- return (noe_revTable[x&255]<<8) | (noe_revTable[x>>8]);
+ return ((noe_revTable[x&255]<<8) | (noe_revTable[x>>8]))>>(SHIFT-codeBits);
#else
+ assert(codeBits == 8);
return noe_revTable[x];
#endif
}
Modified: trunk/noe/mina.c
==============================================================================
--- trunk/noe/mina.c (original)
+++ trunk/noe/mina.c Tue Oct 21 13:54:49 2008
@@ -261,7 +261,7 @@ printf("%d %d %d\n", n, k, n-k);
}
}
- e= EXT(rsDecode)(code, erased, erasureLocator, erasedCount, n-k);
+ e= EXT(rsDecode)(code, erased, erasureLocator, erasedCount, n-k, SHIFT);
if(e<0){
fprintf(stderr, "reed solomon decoding error\n");
return 9;
@@ -270,10 +270,10 @@ printf("%d %d %d\n", n, k, n-k);
}
}else{
code[k-1]=0;
- EXT(rsEncode)(code, parityLocator, n-k);
+ EXT(rsEncode)(code, parityLocator, n-k, SHIFT);
}
- if(EXT(rsTransform)(code, parityLocator, n-k, tPoly, k-1, !decode) < 0){
+ if(EXT(rsTransform)(code, parityLocator, n-k, tPoly, k-1, !decode, SHIFT) < 0){
fprintf(stderr, "transform failure\n");
return 6;
}
Modified: trunk/noe/rs.c
==============================================================================
--- trunk/noe/rs.c (original)
+++ trunk/noe/rs.c Tue Oct 21 13:54:49 2008
@@ -31,13 +31,14 @@
#undef NDEBUG
#include <assert.h>
-void EXT(getSyndrom)(GFF4Element *syn, GFF4Element *src, int order){
+void EXT(getSyndrom)(GFF4Element *syn, GFF4Element *src, int order, int codeBits){
*syn++= order;
- if(order>6 && !M){
- EXT(gfft)(syn, src, SHIFT);
- EXT(permute)(syn, syn, order+1);
+ if(!M){
+ EXT(gfft)(syn, src, codeBits);
+ EXT(permute)(syn, syn, order+1, codeBits);
}else{
int i;
+ assert(codeBits == SHIFT);
for(i=1; i<=order; i++){
int bak= src[-1];
src[-1]= SIZE-2;
@@ -51,22 +52,24 @@ void EXT(getSyndrom)(GFF4Element *syn, G
/**
*
*/
-void EXT(rsEncode)(GFF4Element *data, GFF4Element *parityLocator, int parityCount){
+void EXT(rsEncode)(GFF4Element *data, GFF4Element *parityLocator, int parityCount, int codeBits){
int i;
- const int dataCount= SIZE - parityCount - 1;
+ const int decimate= SHIFT - codeBits;
+ const int dataCount= ((SIZE - 1)>>decimate) - parityCount;
int parityLocations[parityCount];
for(i=0; i<parityCount; i++)
- parityLocations[i]= dataCount + i;
+ parityLocations[i]= (dataCount + i)<<decimate;
- EXT(rsDecode)(data, parityLocations, parityLocator, parityCount, parityCount);
+ EXT(rsDecode)(data, parityLocations, parityLocator, parityCount, parityCount, codeBits);
}
#if M==0
//FIXME avoid the noe_RsEncoder dependancy
-int EXT(rsTransform)(GFF4Element *data, GFF4Element *parityLocator, int parityCount, GFF4Element *tPoly, int tLocation, int encode){
+int EXT(rsTransform)(GFF4Element *data, GFF4Element *parityLocator, int parityCount, GFF4Element *tPoly, int tLocation, int encode, int codeBits){
int i, j;
- const int dataCount= SIZE - parityCount - 1;
+ const int decimate= SHIFT - codeBits;
+ const int dataCount= ((SIZE - 1)>>decimate) - parityCount;
GFF4Element temp[SIZE-1];
char *stats= (char*)temp;
GFF4Element t= data[ tLocation ];
@@ -77,7 +80,7 @@ int EXT(rsTransform)(GFF4Element *data,
if(tPoly[0]<=0){
memset(temp, 0, sizeof(temp));
temp[tLocation]= 1;
- EXT(rsEncode)(temp, parityLocator, parityCount);
+ EXT(rsEncode)(temp, parityLocator, parityCount, codeBits);
memcpy(tPoly, temp + dataCount, parityCount*sizeof(GFF4Element));
}
@@ -354,10 +357,12 @@ static int rsBerlekampMassey(GFF4Element
return k;
}
-int EXT(rsDecode)(GFF4Element *data, int *erasure, GFF4Element *erasureLocator, int erasureCount, int parityCount){
+int EXT(rsDecode)(GFF4Element *data, int *erasure, GFF4Element *erasureLocator, int erasureCount, int parityCount, int codeBits){
int i, j, k;
int errorCount, gfftEval;
- const int dataCount= SIZE - 1 - parityCount;
+ const int decimate= SHIFT - codeBits;
+ const int codeCount= (SIZE - 1)>>decimate;
+ const int dataCount= codeCount - parityCount;
GFF4Element locator0[SIZE]; //[parityCount + 1 + 1];
GFF4Element locator1[SIZE]; //[parityCount + 1 + 1];
GFF4Element *locators[2]={locator0, locator1};
@@ -374,10 +379,10 @@ int EXT(rsDecode)(GFF4Element *data, int
/* kill erased symbols */
for(i=0; i<erasureCount; i++){
- data[ erasure[i] ]=0;
+ data[ erasure[i]>>decimate ]=0;
}
- EXT(getSyndrom)(syn, data, parityCount);
+ EXT(getSyndrom)(syn, data, parityCount, codeBits);
for(i=1; i<=parityCount; i++){
if(syn[i+1]) break;
@@ -423,39 +428,42 @@ for(i=0; i<erasureCount; i++){
EXT(getDerivative)(psi, psi);
if(gfftEval){
- memset(errorLocator + errorCount+2, 0, (SIZE - errorCount-2)*sizeof(GFF4Element));
+ memset(errorLocator + errorCount+2, 0, (codeCount - errorCount - 1)*sizeof(GFF4Element));
errorLocator++;
- EXT(gfft)(errorLocator, errorLocator, SHIFT);
+ EXT(gfft)(errorLocator, errorLocator, codeBits);
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));
+ //FIXME
+ memset(omega + omega[0] + 2, 0, (codeCount - omega[0] - 1)*sizeof(GFF4Element));
+ memset(psi + psi [0] + 2, 0, (codeCount - psi [0] - 1)*sizeof(GFF4Element));
omega++;
psi++;
- EXT(gfft)(omega, omega, SHIFT);
- EXT(gfft)(psi , psi , SHIFT);
+ EXT(gfft)(omega, omega, codeBits);
+ EXT(gfft)(psi , psi , codeBits);
}
for(j=0,i=0; j<errorCount; i++){
- if(i>=SIZE)
+ if(i > codeCount)
return -1;
- assert(i<SIZE);
if(!errorLocator[i])
- error[j++]= i ? MINUS1 - bitReverse(i) : 0;
+ error[j++]= i ? MINUS1 - bitReverse(i, SHIFT) : 0;
}
}else{
- for(j=0,i=0; j<errorCount; i++){
- assert(i<SIZE);
- if(!EXT(evalPoly)(errorLocator, i)){
+ for(j=0,i=0; j<errorCount; i += 1<<decimate){
+ int i2= EXT(exp)[MINUS1 - i];
+ if(i >= SIZE)
+ return -1;
+ if(!EXT(evalPoly)(errorLocator, i2)){
GFF4Element rem=errorLocator[ errorLocator[0]+1 ];
for(k=errorLocator[0]; k>0; k--){
- GFF4Element temp= sum(errorLocator[k], prod(rem, i));
+ GFF4Element temp= sum(errorLocator[k], prod(rem, i2));
errorLocator[k]= rem;
rem= temp;
}
assert(rem == 0);
errorLocator[0]--;
- error[j++]= EXT(log)[i] ? MINUS1 - EXT(log)[i] : 0;
+ error[j++]= i;
+ assert(!decimate || !(error[j-1]&1));
}
}
}
@@ -467,7 +475,7 @@ for(i=0; i<erasureCount; i++){
assert(r>=0 && r<MINUS1);
if(gfftEval>1){
- int i2= bitReverse(MINUS1 - r);
+ int i2= bitReverse(MINUS1 - r, SHIFT);
e= r - EXT(log)[ psi[i2]];
if(e<0) e+= MINUS1;
e+= EXT(log)[omega[i2]];
@@ -478,7 +486,7 @@ for(i=0; i<erasureCount; i++){
e+= EXT(log)[EXT(evalPoly)(omega, invX)];
}
- data[r]= sum(data[r], EXT(exp)[e]);
+ data[r>>decimate]= sum(data[r>>decimate], EXT(exp)[e]);
}
return erasureCount + errorCount;
Modified: trunk/noe/rs.h
==============================================================================
--- trunk/noe/rs.h (original)
+++ trunk/noe/rs.h Tue Oct 21 13:54:49 2008
@@ -20,15 +20,27 @@
* gets the syndroms.
* @param src a 2^16 entry long polynom
* @param syn the syndrom polynom will be stored here
+ * @param codeBits log2(codeSize)
*/
-void EXT(getSyndrom)(GFF4Element *syn, GFF4Element *src, int order);
+void EXT(getSyndrom)(GFF4Element *syn, GFF4Element *src, int order, int codeBits);
/**
*
+ * @param codeBits log2(codeSize)
*/
-void EXT(rsEncode)(GFF4Element *data, GFF4Element *parityLocator, int parityCount);
+void EXT(rsEncode)(GFF4Element *data, GFF4Element *parityLocator, int parityCount, int codeBits);
+
+/**
+ *
+ * @param codeBits log2(codeSize)
+ */
+int EXT(rsDecode)(GFF4Element *data, int *erased, GFF4Element *erassureLocator, int erasedCount, int parityCount, int codeBits);
-int EXT(rsDecode)(GFF4Element *data, int *erased, GFF4Element *erassureLocator, int erasedCount, int parityCount);
#if M==0
-int EXT(rsTransform)(GFF4Element *data, GFF4Element *parityLocator, int parityCount, GFF4Element *tPoly, int tLocation, int encode);
+
+/**
+ *
+ * @param codeBits log2(codeSize)
+ */
+int EXT(rsTransform)(GFF4Element *data, GFF4Element *parityLocator, int parityCount, GFF4Element *tPoly, int tLocation, int encode, int codeBits);
#endif
Modified: trunk/noe/test.c
==============================================================================
--- trunk/noe/test.c (original)
+++ trunk/noe/test.c Tue Oct 21 13:54:49 2008
@@ -52,7 +52,7 @@ static const unsigned int gfftChecksums[
};
int main(){
- int i, j;
+ int i, j, decimate, codeBits;
GFF4Element bp=1;
EXT(init)();
@@ -124,11 +124,14 @@ int main(){
#if 1
srand (31415);
+ for(codeBits=8; codeBits<=SHIFT; codeBits++){
+ printf("\n\nCodeSize=%d\n", 1<<codeBits);
+ decimate= SHIFT - codeBits;
#if 0 // only func using getRsGenerator so droped with it
printf("\nTesting generator polynoms");
for(i=1; i<100; i+=5){
- int n= SIZE - 1;
- int k= SIZE - 1 - i;
+ int n= (SIZE - 1)>>decimate;
+ int k= n - i;
GFF4Element syn[n+1];
GFF4Element gen[i+1+1];
GFF4Element data[k+1];
@@ -142,7 +145,7 @@ int main(){
EXT(prodPoly)(code, gen, data);
assert(code[0]==n-1);
- EXT(getSyndrom)(syn, code+1, i);
+ EXT(getSyndrom)(syn, code+1, i, codeBits);
// EXT(printPoly)(gen, i);
// EXT(printPoly)(syn, i-1);
@@ -155,9 +158,9 @@ int main(){
#endif
#if 0
printf("\nTesting encoder");
- for(i=1; i<SIZE/2; i+=i+5){
- int n= SIZE - 1;
- int k= SIZE - 1 - i;
+ for(i=1; i<(SIZE/2)>>decimate; i+=i+5){
+ int n= (SIZE - 1)>>decimate;
+ int k= n - i;
GFF4Element syn[n+1];
// GFF4Element gen[i+1];
GFF4Element data[k];
@@ -173,13 +176,13 @@ int main(){
for(pass=5; pass; pass--){
for(j=0; j<k; j++)
data[j]= rand() & MASK;
- data[tLoc] %= SIZE - 1 - n + k;
+ data[tLoc] %= k;
memcpy(code, data, k*sizeof(GFF4Element));
{START_TIMER
- EXT(rsEncode)(code, parityLocator, i);
+ EXT(rsEncode)(code, parityLocator, i, codeBits);
STOP_TIMER}
- EXT(getSyndrom)(syn, code, i);
+ EXT(getSyndrom)(syn, code, i, codeBits);
//FIXME check that code contains data, but its not touched so ...
// EXT(printPoly)(gen, i);
@@ -189,9 +192,9 @@ 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)(code, parityLocator, i, tPoly, tLoc, 1) < 0)
+ if(EXT(rsTransform)(code, parityLocator, i, tPoly, tLoc, 1, codeBits) < 0)
printf("transform failure\n");
- EXT(getSyndrom)(syn, code, i);
+ EXT(getSyndrom)(syn, code, i, codeBits);
for(j=0; j<i; j++)
if(syn[j+1+1]) printf("FAILT generator:%d coefficient:%d is %X\n", i, j, syn[j+1]);
for(j=0; j<n; j++){
@@ -199,9 +202,9 @@ STOP_TIMER}
printf("illegal symbol detected\n");
}
- if(EXT(rsTransform)(code, parityLocator, i, tPoly, tLoc, 0) < 0)
+ if(EXT(rsTransform)(code, parityLocator, i, tPoly, tLoc, 0, codeBits) < 0)
printf("inv-transform failure\n");
- EXT(getSyndrom)(syn, code, i);
+ EXT(getSyndrom)(syn, code, i, codeBits);
for(j=0; j<i; j++)
if(syn[j+1+1]) printf("FAILTT generator:%d coefficient:%d is %X\n", i, j, syn[j+1]);
for(j=0; j<k; j++){
@@ -215,9 +218,9 @@ STOP_TIMER}
#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;
+ for(i=1; i<2000 && i<(SIZE/2)>>decimate; i+=(SIZE == 0x10001 ? 100 : 10)){
+ int n= (SIZE - 1)>>decimate;
+ int k= n - i;
int erased[i];
GFF4Element erasureLocator[i+2];
GFF4Element data[k];
@@ -235,7 +238,7 @@ STOP_TIMER}
memcpy(code, data, n*sizeof(GFF4Element));
erasureLocator[0]= 0;
- EXT(rsEncode)(code, parityLocator, i);
+ EXT(rsEncode)(code, parityLocator, i, codeBits);
erasedCount=0;
if(rand()&0x40){
@@ -245,11 +248,11 @@ STOP_TIMER}
while(e==-1 || code[e]==MINUS1) e=rand()%n;
- erased[j]= e;
+ erased[j]= e<<decimate;
code[ e ]= MINUS1;
}
for(j=0; j<erasedCount; j++){
- int e= erased[j];
+ int e= erased[j]>>decimate;
code[ e ]= rand()&MASK;
}
@@ -267,7 +270,7 @@ STOP_TIMER}
}
}
//printf("erased:%d errors:%d parity:%d\n", erasedCount, errorCount, i);
- EXT(rsDecode)(code, erased, erasureLocator, erasedCount, i);
+ EXT(rsDecode)(code, erased, erasureLocator, erasedCount, i, codeBits);
// EXT(printPoly)(gen, i);
// EXT(printPoly)(syn, i-1);
@@ -281,6 +284,7 @@ STOP_TIMER}
printf("."); fflush(stdout);
}
}
+ }
#if 0
{
uint8_t buffer[20000];
More information about the Mndiff-dev
mailing list