July 2010 - Mndiff-dev - lists.mplayerhq.hu

[mndiff]: r213 - in trunk/noe: galois.c gfft.c gfft.h rs.c
by michael 23 Jul '10

23 Jul '10

Author: michael Date: Fri Jul 23 03:25:01 2010 New Revision: 213 Log: add gfft_0padded() a bit faster Modified: trunk/noe/galois.c trunk/noe/gfft.c trunk/noe/gfft.h trunk/noe/rs.c Modified: trunk/noe/galois.c ============================================================================== --- trunk/noe/galois.c Fri Jul 23 00:20:22 2010 (r212) +++ trunk/noe/galois.c Fri Jul 23 03:25:01 2010 (r213) @@ -103,14 +103,8 @@ void EXT(prodPoly)(GFF4Element *dst, GFF GFF4Element temp[2][SIZE]; //[size] const GFF4Element scale= inv(size); - //FIXME avoid mem* (but note the memcpy/set only takes 2% of the prodPoly time) - memcpy(temp[0], src1, sizeof(GFF4Element)*(order1+1)); - memset(temp[0] + order1 + 1, 0, sizeof(GFF4Element)*(size - order1 - 1)); - memcpy(temp[1], src2, sizeof(GFF4Element)*(order2+1)); - memset(temp[1] + order2 + 1, 0, sizeof(GFF4Element)*(size - order2 - 1)); - - EXT(gfft)(temp[0], temp[0], logSize); - EXT(gfft)(temp[1], temp[1], logSize); + EXT(gfft_0padded)(temp[0], src1, logSize, order1+1); + EXT(gfft_0padded)(temp[1], src2, logSize, order2+1); for(i=0; i<size; i++){ temp[0][i]= prod(prod(temp[0][i], temp[1][i]), scale); @@ -228,14 +222,8 @@ void EXT(partialProdPoly)(GFF4Element *d GFF4Element temp[SIZE]; //[size] const GFF4Element scale= inv(size); - //FIXME avoid mem* (but note the memcpy/set only takes 2% of the prodPoly time) - memcpy(temp, src2, sizeof(GFF4Element)*(order2+1)); - memset(temp + order2 + 1, 0, sizeof(GFF4Element)*(size - order2 - 1)); - memcpy(dst, src1, sizeof(GFF4Element)*(order1+1)); - memset(dst + order1 + 1, 0, sizeof(GFF4Element)*(size - order1 - 1)); - - EXT(gfft)(dst, dst, logSize); - EXT(gfft)(temp, temp, logSize); + EXT(gfft_0padded)(temp, src2, logSize, order2+1); + EXT(gfft_0padded)(dst , src1, logSize, order1+1); for(i=0; i<size; i++){ dst[i]= prod(prod(dst[i], temp[i]), scale); Modified: trunk/noe/gfft.c ============================================================================== --- trunk/noe/gfft.c Fri Jul 23 00:20:22 2010 (r212) +++ trunk/noe/gfft.c Fri Jul 23 03:25:01 2010 (r213) @@ -330,6 +330,15 @@ void EXT(gfft)(GFF4Element *dst, GFF4Ele // int i, j, pass; //printf("%X %X\n", noe_exp[4096], noe_exp[3*4096]); + if(logSize<5){ + memcpy(dst, src, sizeof(*dst)<<logSize); + if(logSize==1) fft2(dst); + else if(logSize==2) fft4(dst); + else if(logSize==3) fft8(dst); + else if(logSize==4) fft16(dst); + return; + } + assert(logSize>=5); if(src==dst) @@ -370,6 +379,25 @@ STOP_TIMER} #endif } +void EXT(gfft_0padded)(GFF4Element *dst, GFF4Element *src, int logSize, int nzCoeffs){ + int lognz= noe_log2(nzCoeffs-1)+1; + int i, j; + + for(i=1; i<1<<(logSize-lognz); i++){ + int idx= i<<lognz; + int m= bitReverse(i, SHIFT)>>lognz; + for(j=0; j<nzCoeffs; j++){ + dst[idx+j]= prod(src[j], EXT(exp)[ j*m ]); + } + memset(dst+nzCoeffs+idx, 0, sizeof(*dst)*((1<<lognz)-nzCoeffs)); + EXT(gfft)(dst+idx, dst+idx, lognz); + } + + memcpy(dst, src, sizeof(*dst)*nzCoeffs); + memset(dst+nzCoeffs, 0, sizeof(*dst)*((1<<lognz)-nzCoeffs)); + EXT(gfft)(dst, dst, lognz); +} + void EXT(igfft)(GFF4Element *dst, GFF4Element *src, int logSize){ assert(logSize>=5); Modified: trunk/noe/gfft.h ============================================================================== --- trunk/noe/gfft.h Fri Jul 23 00:20:22 2010 (r212) +++ trunk/noe/gfft.h Fri Jul 23 03:25:01 2010 (r213) @@ -18,6 +18,7 @@ void noe_gfft_init(); void EXT(gfft)(GFF4Element *dst, GFF4Element *src, int size); +void EXT(gfft_0padded)(GFF4Element *dst, GFF4Element *src, int logSize, int nzCoeffs); void EXT(igfft)(GFF4Element *dst, GFF4Element *src, int size); void EXT(permute)(GFF4Element *dst, GFF4Element *src, int outCount, int codeBits); Modified: trunk/noe/rs.c ============================================================================== --- trunk/noe/rs.c Fri Jul 23 00:20:22 2010 (r212) +++ trunk/noe/rs.c Fri Jul 23 03:25:01 2010 (r213) @@ -434,9 +434,8 @@ for(i=0; i<erasureCount; i++){ } if(elfft){ - memset(errorLocator + errorCount+2, 0, (codeCount - errorCount - 1)*sizeof(GFF4Element)); errorLocator++; - EXT(gfft)(errorLocator, errorLocator, codeBits); + EXT(gfft_0padded)(errorLocator, errorLocator, codeBits, errorLocator[-1]+1); for(j=0,i=0; j<errorCount; i++){ if(i >= codeCount) @@ -466,13 +465,10 @@ for(i=0; i<erasureCount; i++){ } if(gfftEval>1){ - //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, codeBits); - EXT(gfft)(psi , psi , codeBits); + EXT(gfft_0padded)(omega, omega, codeBits, omega[-1]+1); + EXT(gfft_0padded)(psi , psi , codeBits, psi [-1]+1); } for(i=0; i<erasureCount + errorCount; i++){

1 0

[mndiff]: r212 - trunk/noe/gfft.c
by michael 22 Jul '10

22 Jul '10

Author: michael Date: Fri Jul 23 00:20:22 2010 New Revision: 212 Log: ifft16() Modified: trunk/noe/gfft.c Modified: trunk/noe/gfft.c ============================================================================== --- trunk/noe/gfft.c Fri Jul 23 00:20:21 2010 (r211) +++ trunk/noe/gfft.c Fri Jul 23 00:20:22 2010 (r212) @@ -265,18 +265,43 @@ static inline void ifft8(GFF4Element *p) ifft4(p+1,2); } +static void ifft16(GFF4Element *p){ + int n; + const int size= 1<<(4-2); + + ifft8(p); + ifft4(p+8 ,1); + ifft4(p+12,1); + + for(n=0; n<size; n++){ + const unsigned int w1= EXT(exp)[ MINUS1 - ( n <<(SHIFT-4)) ]; + const unsigned int wx= EXT(exp)[ MINUS1 - ((3*n )<<(SHIFT-4)) ]; + const unsigned int a= p[n ]; + const unsigned int b= p[n + size] + SIZE + (SIZE<<(SHIFT/2)); + unsigned int c= reduce(p[n + 2*size]*w1); + const unsigned int t= reduce(p[n + 3*size]*wx); + unsigned int d= (c - t)<<(SHIFT/2); + c= sum (c, t); + + p[n ]= sum(a, c); + p[n + 2*size]= sum(a, SIZE - c); + p[n + 1*size]= reduce(b + d); + p[n + 3*size]= reduce(b - d); + } +} + static void ifftn(GFF4Element *p, int logSize){ int n; const int size= 1<<(logSize-2); - if(logSize==4){ - ifft8(p); - ifft4(p+8 ,1); - ifft4(p+12,1); - } else if(logSize==5){ - ifftn(p , logSize-1); + if(logSize==5){ + ifft16(p); ifft8(p+16); ifft8(p+24); + } else if(logSize==6){ + ifftn(p , logSize-1); + ifft16(p+32); + ifft16(p+48); }else{ ifftn(p , logSize-1); ifftn(p+2*size, logSize-2);

1 0

[mndiff]: r211 - trunk/noe/gfft.c
by michael 22 Jul '10

22 Jul '10

Author: michael Date: Fri Jul 23 00:20:21 2010 New Revision: 211 Log: port optimizations from fft8 to ifft8 Modified: trunk/noe/gfft.c Modified: trunk/noe/gfft.c ============================================================================== --- trunk/noe/gfft.c Fri Jul 23 00:20:20 2010 (r210) +++ trunk/noe/gfft.c Fri Jul 23 00:20:21 2010 (r211) @@ -222,51 +222,47 @@ static inline void ifft2(GFF4Element *p) p[1]= sum(a, SIZE - b); } -static inline void ifft4(GFF4Element *p){ +static inline void ifft4(GFF4Element *p, int step){ unsigned int a,b,c,d; d= p[0] + SIZE*(SIZE/2ULL); - a= d + p[1]; - b= d - p[1]; - c= p[2] + p[3]; - d=(p[2] - p[3])<<(SHIFT/2); + a= d +p[step]; + c= d -p[step]; + b= p[2*step] + p[3*step]; + d= (p[2*step] - p[3*step])<<(SHIFT/2) /*(p[1] - p[3])*noe_exp[16384]*/; - p[0]= reduce(a+c); - p[2]= reduce(a-c); - p[1]= reduce(b+d); - p[3]= reduce(b-d); + p[0 ]= reduce(a+b); + p[2*step]= reduce(a-b); + p[1*step]= reduce(c+d); + p[3*step]= reduce(c-d); } -static void ifft8(GFF4Element *p){ - unsigned a,b,c,d,t; - - ifft4(p); - ifft2(p+4); - ifft2(p+6); +static inline void ifft8(GFF4Element *p){ + unsigned int a,b; a= p[0]; - b= p[2] + SIZE + (SIZE<<(SHIFT/2)); - c= p[4]; - t= p[6]; - d= (c - t)<<(SHIFT/2); - c= sum (c, t); + b= p[1]; + p[0]= a+b; + p[1]= a-b; - p[0]= sum(a, c); - p[4]= sum(a, SIZE - c); - p[2]= reduce(b + d); - p[6]= reduce(b - d); + a= p[6]; + b= p[7]; + p[6]= a+b; + p[7]= hsreduce(((b-a)<<(SHIFT*3/4)))/*(a-b)*noe_exp[8192]*/; - a= p[1] + (SIZE<<(SHIFT-1)); - b= p[3] + (SIZE<<(SHIFT-1)); - c= p[5]<<(SHIFT/4); - t= reduce(p[7]<<(SHIFT*3/4)); - d= (t - c)<<(SHIFT/2); - c+= t; - p[1]= reduce(a - c); - p[5]= reduce(a + c); - p[3]= reduce(b + d); - p[7]= reduce(b - d); + a= p[2]; + b= p[3]; + p[2]= a+b; + p[3]= (a-b)<<(SHIFT/2) /*(a-b)*noe_exp[16384]*/; + + a= p[4]; + b= p[5]; + p[4]= a+b; + p[5]= (b-a)<<(SHIFT/4)/*(a-b)*noe_exp[3*8192]*/; + + ifft4(p ,2); + ifft4(p+1,2); } static void ifftn(GFF4Element *p, int logSize){ @@ -275,8 +271,8 @@ static void ifftn(GFF4Element *p, int lo if(logSize==4){ ifft8(p); - ifft4(p+8); - ifft4(p+12); + ifft4(p+8 ,1); + ifft4(p+12,1); } else if(logSize==5){ ifftn(p , logSize-1); ifft8(p+16);

1 0

[mndiff]: r210 - in trunk/noe: galois_internal.h gfft.c
by michael 22 Jul '10

22 Jul '10

Author: michael Date: Fri Jul 23 00:20:20 2010 New Revision: 210 Log: add half reduce functions and use them in the gfft Modified: trunk/noe/galois_internal.h trunk/noe/gfft.c Modified: trunk/noe/galois_internal.h ============================================================================== --- trunk/noe/galois_internal.h Fri Jul 23 00:20:19 2010 (r209) +++ trunk/noe/galois_internal.h Fri Jul 23 00:20:20 2010 (r210) @@ -78,6 +78,20 @@ static inline GFF4Element reduce(GFF4Ele return a; } +static inline GFF4Element hsreduce(GFF4Element a){ +#if M==0 + a = (a&MASK) - ((int)a>>SHIFT); +#endif + return a; +} + +static inline GFF4Element hureduce(GFF4Element a){ +#if M==0 + a = (a&MASK) - (a>>SHIFT); +#endif + return a; +} + static inline GFF4Element prod(GFF4Element a, GFF4Element b){ #if SIZE == 2 return a&b; Modified: trunk/noe/gfft.c ============================================================================== --- trunk/noe/gfft.c Fri Jul 23 00:20:19 2010 (r209) +++ trunk/noe/gfft.c Fri Jul 23 00:20:20 2010 (r210) @@ -101,7 +101,7 @@ static inline void fft8(GFF4Element *p){ a= p[1]; b= p[5]; p[1]= a+b; - p[5]= reduce(SIZE*(SIZE/2ULL) + ((a-b)<<(SHIFT*3/4)))/*(a-b)*noe_exp[8192]*/; + p[5]= hsreduce(((a-b)<<(SHIFT*3/4)))/*(a-b)*noe_exp[8192]*/; a= p[2]; b= p[6]; @@ -128,13 +128,13 @@ static void fft16(GFF4Element *p){ const unsigned int c= p[n + 2*4]; const unsigned int d= p[n + 3*4]; - p[n ]= sum (a, c); + p[n ]= a + c; a = SIZE + (SIZE<<(SHIFT/2)) + ((a - c)<<(SHIFT/2)); - p[n + 4]= sum (b, d); + p[n + 4]= b + d; b = b - d; - p[n + 2*4]= reduce(reduce(a + b)*w2); - p[n + 3*4]= reduce(reduce(a - b)*wx); + p[n + 2*4]= hureduce(reduce(a + b)*w2); + p[n + 3*4]= hureduce(reduce(a - b)*wx); } fft8(p);

1 0

[mndiff]: r209 - trunk/noe/gfft.c
by michael 22 Jul '10

22 Jul '10

Author: michael Date: Fri Jul 23 00:20:19 2010 New Revision: 209 Log: Optimize ifft4() in line of fft4() Modified: trunk/noe/gfft.c Modified: trunk/noe/gfft.c ============================================================================== --- trunk/noe/gfft.c Mon Jul 19 17:23:53 2010 (r208) +++ trunk/noe/gfft.c Fri Jul 23 00:20:19 2010 (r209) @@ -225,14 +225,16 @@ static inline void ifft2(GFF4Element *p) static inline void ifft4(GFF4Element *p){ unsigned int a,b,c,d; - a= p[0] + p[1]; - b= p[0] - p[1] + SIZE + (SIZE<<(SHIFT/2)); + d= p[0] + SIZE*(SIZE/2ULL); + + a= d + p[1]; + b= d - p[1]; c= p[2] + p[3]; d=(p[2] - p[3])<<(SHIFT/2); p[0]= reduce(a+c); + p[2]= reduce(a-c); p[1]= reduce(b+d); - p[2]= reduce(a-c + 2*SIZE); p[3]= reduce(b-d); }

1 0

[mndiff]: r208 - trunk/noe/test.c
by michael 19 Jul '10

19 Jul '10

Author: michael Date: Mon Jul 19 17:23:53 2010 New Revision: 208 Log: 10l, actually use usedParityCount. Modified: trunk/noe/test.c Modified: trunk/noe/test.c ============================================================================== --- trunk/noe/test.c Mon Jul 19 16:20:21 2010 (r207) +++ trunk/noe/test.c Mon Jul 19 17:23:53 2010 (r208) @@ -279,7 +279,7 @@ STOP_TIMER} usedParityCount= i; //printf("erased:%d errors:%d parity:%d\n", erasedCount, errorCount, i); - EXT(rsDecode)(code, erased, erasureLocator, erasedCount, i, codeBits); + EXT(rsDecode)(code, erased, erasureLocator, erasedCount, usedParityCount, codeBits); // EXT(printPoly)(gen, i); // EXT(printPoly)(syn, i-1);

1 0

[mndiff]: r207 - trunk/noe/test.c
by michael 19 Jul '10

19 Jul '10

Author: michael Date: Mon Jul 19 16:20:21 2010 New Revision: 207 Log: Test smaller parityCounts, this speeds the test up as well. Modified: trunk/noe/test.c Modified: trunk/noe/test.c ============================================================================== --- trunk/noe/test.c Mon Jul 19 16:20:20 2010 (r206) +++ trunk/noe/test.c Mon Jul 19 16:20:21 2010 (r207) @@ -230,6 +230,7 @@ STOP_TIMER} GFF4Element parityLocator [SIZE/2+2]; int pass=5; uint64_t end, start= rdtsc(); + int usedParityCount; parityLocator[0]= 0; @@ -272,6 +273,11 @@ STOP_TIMER} } } } + if(get_random(&rnd)&0x40){ + usedParityCount= erasedCount + 2*errorCount; + }else + usedParityCount= i; + //printf("erased:%d errors:%d parity:%d\n", erasedCount, errorCount, i); EXT(rsDecode)(code, erased, erasureLocator, erasedCount, i, codeBits);

1 0

[mndiff]: r206 - trunk/noe/rs.h
by michael 19 Jul '10

19 Jul '10

Author: michael Date: Mon Jul 19 16:20:20 2010 New Revision: 206 Log: Clarify that one can use a parityCount during decoding that is smaller than what was used during encoding. Modified: trunk/noe/rs.h Modified: trunk/noe/rs.h ============================================================================== --- trunk/noe/rs.h Mon Jul 19 16:20:19 2010 (r205) +++ trunk/noe/rs.h Mon Jul 19 16:20:20 2010 (r206) @@ -50,7 +50,10 @@ void noe_rsEncode_10001(GFF4Element *dat /** * Corrects some data using a Reed Solomon code. * @param data The input codeword to correct and the corrected output codeword. - * @param parityCount The number of parity symbols + * @param parityCount The number of parity symbols. + * You can pass a smaller value here than what was used during noe_rsEncode*() + * Using a smaller value here is faster but decoding is only guranteed to succeed + * as long as parityCount >= erasedCount + 2*errorCount * @param erasedCount The number of erased symbols, that is symbols for which we know they * are damaged / damaged symbols with known locations. * @param erased the indexes in the input codeword of erased symbols.

1 0

[mndiff]: r205 - trunk/noe/rs.c
by michael 19 Jul '10

19 Jul '10

Author: michael Date: Mon Jul 19 16:20:19 2010 New Revision: 205 Log: Fix apparent off by 1 error in failure detection of scaning the error locator Modified: trunk/noe/rs.c Modified: trunk/noe/rs.c ============================================================================== --- trunk/noe/rs.c Mon Jul 19 16:20:18 2010 (r204) +++ trunk/noe/rs.c Mon Jul 19 16:20:19 2010 (r205) @@ -439,7 +439,7 @@ for(i=0; i<erasureCount; i++){ EXT(gfft)(errorLocator, errorLocator, codeBits); for(j=0,i=0; j<errorCount; i++){ - if(i > codeCount) + if(i >= codeCount) return -1; if(!errorLocator[i]) error[j++]= i ? MINUS1 - bitReverse(i, SHIFT) : 0;

1 0

[mndiff]: r204 - trunk/noe/rs.c
by michael 19 Jul '10

19 Jul '10

Author: michael Date: Mon Jul 19 16:20:18 2010 New Revision: 204 Log: Fix a bug in rsEuclid() about syndrom order. Modified: trunk/noe/rs.c Modified: trunk/noe/rs.c ============================================================================== --- trunk/noe/rs.c Tue Jul 13 23:27:41 2010 (r203) +++ trunk/noe/rs.c Mon Jul 19 16:20:18 2010 (r204) @@ -275,7 +275,9 @@ static int rsEuclid(GFF4Element *locator omega[0][parityCount+1+1]= 1; SET_POLY0(locator[0], 0); SET_POLY0(locator[1], 1); - + + EXT(getOrder)(omega[1]); //get syndrom isnt guranteed to set this correctly divPoly asserts on it though + for(i=0; 1; i++){ const int di= i&1; const int si= 1-di;

1 0