October 2008 - Mndiff-dev - lists.mplayerhq.hu

[mndiff]: r115 - in trunk/noe: galois.c rs.c
by michael 25 Oct '08

25 Oct '08

Author: michael Date: Sat Oct 25 19:33:42 2008 New Revision: 115 Log: indent Modified: trunk/noe/galois.c trunk/noe/rs.c Modified: trunk/noe/galois.c ============================================================================== --- trunk/noe/galois.c (original) +++ trunk/noe/galois.c Sat Oct 25 19:33:42 2008 @@ -259,8 +259,8 @@ GFF4Element EXT(evalPoly)(GFF4Element *s int j; if(M || x==MINUS1){ - for(j=src[0]; j>0; j--) - acc = sum(prod(acc, x), src[j]); + for(j=src[0]; j>0; j--) + acc = sum(prod(acc, x), src[j]); }else{ for(j=src[0]; j>0; j--) acc = reduce(acc*x + src[j]); Modified: trunk/noe/rs.c ============================================================================== --- trunk/noe/rs.c (original) +++ trunk/noe/rs.c Sat Oct 25 19:33:42 2008 @@ -462,15 +462,15 @@ 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); - } + 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); + } for(i=0; i<erasureCount + errorCount; i++){ const int r= i<erasureCount ? erasure[i] : error[i-erasureCount];

1 0

[mndiff]: r114 - trunk/noe/galois.c
by michael 25 Oct '08

25 Oct '08

Author: michael Date: Sat Oct 25 19:33:07 2008 New Revision: 114 Log: Faster evalPoly() Modified: trunk/noe/galois.c Modified: trunk/noe/galois.c ============================================================================== --- trunk/noe/galois.c (original) +++ trunk/noe/galois.c Sat Oct 25 19:33:07 2008 @@ -258,8 +258,13 @@ GFF4Element EXT(evalPoly)(GFF4Element *s unsigned int acc=src[ src[0] + 1 ]; int j; + if(M || x==MINUS1){ for(j=src[0]; j>0; j--) acc = sum(prod(acc, x), src[j]); + }else{ + for(j=src[0]; j>0; j--) + acc = reduce(acc*x + src[j]); + } return acc; }

1 0

[mndiff]: r113 - trunk/noe/rs.c
by michael 25 Oct '08

25 Oct '08

Author: michael Date: Sat Oct 25 17:42:00 2008 New Revision: 113 Log: Seperate the choice for how to evaluate the errorLocator. This improves speed for the case of few errors and many erasures. Modified: trunk/noe/rs.c Modified: trunk/noe/rs.c ============================================================================== --- trunk/noe/rs.c (original) +++ trunk/noe/rs.c Sat Oct 25 17:42:00 2008 @@ -361,7 +361,7 @@ static int rsBerlekampMassey(GFF4Element int EXT(rsDecode)(GFF4Element *data, int *erasure, GFF4Element *erasureLocator, int erasureCount, int parityCount, int codeBits){ int i, j, k; - int errorCount, gfftEval; + int errorCount, elfft, gfftEval; const int decimate= SHIFT - codeBits; const int codeCount= (SIZE - 1)>>decimate; GFF4Element locator0[SIZE]; //[parityCount + 1 + 1]; @@ -418,6 +418,8 @@ for(i=0; i<erasureCount; i++){ errorLocator= locators[i]; psi= locators[1-i]; //reuse some unused space + elfft = !M && errorCount>20; //FIXME finetune threshold + if(M) gfftEval= 0; else if(errorCount + erasureCount > codeCount/64) gfftEval= 2; else gfftEval= errorCount>20; @@ -428,19 +430,10 @@ for(i=0; i<erasureCount; i++){ memcpy(psi, errorLocator, (errorLocator[0]+2)*sizeof(GFF4Element)); EXT(getDerivative)(psi, psi); - if(gfftEval){ + if(elfft){ memset(errorLocator + errorCount+2, 0, (codeCount - errorCount - 1)*sizeof(GFF4Element)); errorLocator++; EXT(gfft)(errorLocator, errorLocator, codeBits); - 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); - } for(j=0,i=0; j<errorCount; i++){ if(i > codeCount) @@ -469,6 +462,16 @@ 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); + } + for(i=0; i<erasureCount + errorCount; i++){ const int r= i<erasureCount ? erasure[i] : error[i-erasureCount]; int e;

1 0

[mndiff]: r112 - trunk/noe/gfft.c
by michael 24 Oct '08

24 Oct '08

Author: michael Date: Fri Oct 24 16:28:04 2008 New Revision: 112 Log: Split radix gfft. Modified: trunk/noe/gfft.c Modified: trunk/noe/gfft.c ============================================================================== --- trunk/noe/gfft.c (original) +++ trunk/noe/gfft.c Fri Oct 24 16:28:04 2008 @@ -120,60 +120,97 @@ static inline void fft8(GFF4Element *p){ static void fft16(GFF4Element *p){ int n; - for(n=0; n<8; n++){ - const unsigned int w= EXT(exp)[ n<<(SHIFT-4) ]; - const unsigned int a= p[n ]; - const unsigned int b= p[n + 8]; + for(n=0; n<4; n++){ + const unsigned int w2= EXT(exp)[( n+4)<<(SHIFT-4) ]; + const unsigned int wx= EXT(exp)[(3*n+4)<<(SHIFT-4) ]; + unsigned int a= p[n ]; + unsigned int b= p[n + 4]; + const unsigned int c= p[n + 2*4]; + const unsigned int d= p[n + 3*4]; - p[n ]= sum(a, b); - p[n + 8]= reduce(sum(a, SIZE - b)*w); + p[n ]= sum (a, c); + a = SIZE + (SIZE<<(SHIFT/2)) + ((a - c)<<(SHIFT/2)); + p[n + 4]= sum (b, d); + b = b - d; + + p[n + 2*4]= reduce(reduce(a + b)*w2); + p[n + 3*4]= reduce(reduce(a - b)*wx); } fft8(p); - fft8(p+8); + fft4(p+8); + fft4(p+12); } static void fftn(GFF4Element *p, int logSize){ int n; - const int size= 1<<(logSize-1); + const int size= 1<<(logSize-2); for(n=0; n<size; n++){ - const unsigned int w= EXT(exp)[ n<<(SHIFT-logSize) ]; - const unsigned int a= p[n ]; - const unsigned int b= p[n + size]; + const unsigned int w2= EXT(exp)[( n+size)<<(SHIFT-logSize ) ]; + const unsigned int wx= EXT(exp)[(3*n+size)<<(SHIFT-logSize ) ]; + unsigned int a= p[n ]; + unsigned int b= p[n + size]; + const unsigned int c= p[n + 2*size]; + const unsigned int d= p[n + 3*size]; - p[n ]= sum(a, b); - p[n + size]= reduce(sum(a, SIZE - b)*w); + p[n ]= sum (a, c); + a = SIZE + (SIZE<<(SHIFT/2)) + ((a - c)<<(SHIFT/2)); + p[n + size]= sum (b, d); + b = b - d; + + p[n + 2*size]= reduce(reduce(a + b)*w2); + p[n + 3*size]= reduce(reduce(a - b)*wx); } - - if(logSize==5){ + + if(logSize==6){ + fftn(p, logSize-1); + fft16(p+32); + fft16(p+48); + }else if(logSize==5){ fft16(p); - fft16(p+16); + fft8 (p+16); + fft8 (p+24); }else{ - fftn(p, logSize-1); - fftn(p+size, logSize-1); + fftn(p , logSize-1); + fftn(p+2*size, logSize-2); + fftn(p+3*size, logSize-2); } } static void fftn2(GFF4Element *p, GFF4Element *src, int logSize){ int n; - const int size= 1<<(logSize-1); + const int size= 1<<(logSize-2); for(n=0; n<size; n++){ - const unsigned int w= EXT(exp)[ n<<(SHIFT-logSize) ]; - const unsigned int a= src[n ]; - const unsigned int b= src[n + size]; + const unsigned int w2= EXT(exp)[( n+size)<<(SHIFT-logSize ) ]; + const unsigned int wx= EXT(exp)[(3*n+size)<<(SHIFT-logSize ) ]; + unsigned int a= src[n ]; + unsigned int b= src[n + size]; + const unsigned int c= src[n + 2*size]; + const unsigned int d= src[n + 3*size]; - p[n ]= sum(a, b); - p[n + size]= reduce(sum(a, SIZE - b)*w); + p[n ]= sum (a, c); + a = SIZE + (SIZE<<(SHIFT/2)) + ((a - c)<<(SHIFT/2)); + p[n + size]= sum (b, d); + b = b - d; + + p[n + 2*size]= reduce(reduce(a + b)*w2); + p[n + 3*size]= reduce(reduce(a - b)*wx); } - - if(logSize==5){ + + if(logSize==6){ + fftn(p, logSize-1); + fft16(p+32); + fft16(p+48); + }else if(logSize==5){ fft16(p); - fft16(p+16); + fft8 (p+16); + fft8 (p+24); }else{ - fftn(p, logSize-1); - fftn(p+size, logSize-1); + fftn(p , logSize-1); + fftn(p+2*size, logSize-2); + fftn(p+3*size, logSize-2); } } @@ -185,25 +222,83 @@ static inline void ifft2(GFF4Element *p) p[1]= sum(a, SIZE - b); } +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)); + c= p[2] + p[3]; + d=(p[2] - p[3])<<(SHIFT/2); + + p[0]= reduce(a+c); + p[1]= reduce(b+d); + p[2]= reduce(a-c + 2*SIZE); + p[3]= reduce(b-d); +} + +static void ifft8(GFF4Element *p){ + unsigned a,b,c,d,t; + + ifft4(p); + ifft2(p+4); + ifft2(p+6); + + 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); + + p[0]= sum(a, c); + p[4]= sum(a, SIZE - c); + p[2]= reduce(b + d); + p[6]= reduce(b - d); + + 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); +} + static void ifftn(GFF4Element *p, int logSize){ int n; - const int size= 1<<(logSize-1); + const int size= 1<<(logSize-2); - if(logSize==2){ - ifft2(p); - ifft2(p+2); + if(logSize==4){ + ifft8(p); + ifft4(p+8); + ifft4(p+12); + } else if(logSize==5){ + ifftn(p , logSize-1); + ifft8(p+16); + ifft8(p+24); }else{ - ifftn(p, logSize-1); - ifftn(p+size, logSize-1); + ifftn(p , logSize-1); + ifftn(p+2*size, logSize-2); + ifftn(p+3*size, logSize-2); } for(n=0; n<size; n++){ - const unsigned int w= EXT(exp)[ MINUS1 - (n<<(SHIFT-logSize)) ]; - const unsigned int a= p[n ]; - const unsigned int b= prod(p[n + size], w); + const unsigned int w1= EXT(exp)[ MINUS1 - ( n <<(SHIFT-logSize)) ]; + const unsigned int wx= EXT(exp)[ MINUS1 - ((3*n )<<(SHIFT-logSize)) ]; + 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, b); - p[n + size]= sum(a, SIZE - b); + 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); } }

1 0

[mndiff]: r111 - trunk/noe/README
by michael 22 Oct '08

22 Oct '08

Author: michael Date: Wed Oct 22 21:38:31 2008 New Revision: 111 Log: README Added: trunk/noe/README Added: trunk/noe/README ============================================================================== --- (empty file) +++ trunk/noe/README Wed Oct 22 21:38:31 2008 @@ -0,0 +1,80 @@ +noe / libnoe / mina README +-------------------------- + +Building: +--------- +make + +Note, most files will be compiled 3 times, each for a different galois field. + + +Installing: +----------- +make install + + +mina: +----- +mina takes 1 file and generates 1 error correction file from it or it takes +the name of the error correction file and tries to fix errors. +It always uses interleaved codewords of 131072 bytes (65536 GF(65537) symbols) +mina is capable to correct errors and erasures (erasures are errors for which +the user knows where they are but does not know the value of the damaged part +just which byte is damaged) +mina is able to correct 2*error_count + erasure_count < parity_count symbols +per codeword. And mina is fast! + +If you want to use more than 1 file as input, you can combine them with tar or +another archiver before using mina. +If you want to have many small data and error correction files you can just +use the split command after mina and use dd if=/dev/zero and cat to combine +things again. And yes i know this is not terribly user friendly, a patch +improving this is welcome! +The upside though is that such manual spliting has almost no negative effect +compared to spliting optimally at "slice" boundaries. + +To generate a error correction file: +mina e<size of the error correction file> <data file> +(this will generate a <data file>.mina) + +To correct a damaged file / error correction file pair: +mina d <data file>.mina + +To correct a damaged file / error correction file pair where some but not +neccesarily all error positions are known and have been marked by zeroing +them: +mina dz <data file>.mina + +To specify the known error positions on the command line instead of zeroing +and hoping. +send a patch :) + + + +Developer info: +--------------- +If you want to use libnoe, see rs.h and mina.c. +If you want to improve, bugfix, ... things, patches are welcome at: +mndiff-dev(a)mplayerhq.hu (or if you are scared of mailing lists +michaelni(a)gmx.at) + + +File list: +---------- +galois.c/h galois field mathematic operations +gfft.c galois field fast fourier transform +mina.c a simple example application using libnoe +rs.h the main public header (with documentation) +rs.c reed solomon related code +test.c program for self testing and benchmarking +README this file :) + + +Author of noe, mina and libnoe: +------------------------------- +Michael Niedermayer + + +Legalcrap: +---------- +Its all GPL

1 0

[mndiff]: r110 - trunk/noe/Makefile
by michael 22 Oct '08

22 Oct '08

Author: michael Date: Wed Oct 22 20:57:05 2008 New Revision: 110 Log: install target Modified: trunk/noe/Makefile Modified: trunk/noe/Makefile ============================================================================== --- trunk/noe/Makefile (original) +++ trunk/noe/Makefile Wed Oct 22 20:57:05 2008 @@ -1,7 +1,10 @@ LIBOBJS = galois.o rs.o OBJS = rw.o filerw.o noe.o +LIBS = libnoe_100.a libnoe_101.a libnoe_10001.a +PUBLIC_HEADERS = rs.h galois.h LIBSRCS = $(LIBOBJS:.o=.c) $(ASM_LIBOBJS:.o=.s) SRCS = $(OBJS:.o=.c) +INSTALL_BASE = /usr/local CFLAGS = -g -Wall -O4 $(OPTFLAGS) -I. $(EXTRA_INC) @@ -44,3 +47,8 @@ dep: depend depend: $(CC) -MM $(CFLAGS) $(LIBSRCS) $(SRCS) 1>.depend + +install: mina $(LIBS) $(PUBLIC_HEADERS) + install -m 755 mina $(INSTALL_BASE)/bin + install -m 644 $(LIBS) $(INSTALL_BASE)/lib + install -m 644 $(PUBLIC_HEADERS) $(INSTALL_BASE)/include

1 0

[mndiff]: r109 - trunk/noe/rs.c
by michael 22 Oct '08

22 Oct '08

Author: michael Date: Wed Oct 22 20:12:32 2008 New Revision: 109 Log: Remove unused variable. Modified: trunk/noe/rs.c Modified: trunk/noe/rs.c ============================================================================== --- trunk/noe/rs.c (original) +++ trunk/noe/rs.c Wed Oct 22 20:12:32 2008 @@ -364,7 +364,6 @@ int EXT(rsDecode)(GFF4Element *data, int int errorCount, gfftEval; 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};

1 0

[mndiff]: r108 - trunk/noe/mina.c
by michael 22 Oct '08

22 Oct '08

Author: michael Date: Wed Oct 22 19:33:50 2008 New Revision: 108 Log: Ensure that reading between data and padded size does not overflow the buffer. Modified: trunk/noe/mina.c Modified: trunk/noe/mina.c ============================================================================== --- trunk/noe/mina.c (original) +++ trunk/noe/mina.c Wed Oct 22 19:33:50 2008 @@ -64,7 +64,7 @@ static int read(uint8_t *buf, int64_t po return -1; } }else if(pos < paddedsize){ - len2= paddedsize - pos; + len2= MIN(len, paddedsize-pos); memset(buf, 0, len2); }else{ int64_t pos2= pos - paddedsize;

1 0

[mndiff]: r107 - trunk/noe/mina.c
by michael 22 Oct '08

22 Oct '08

Author: michael Date: Wed Oct 22 19:29:40 2008 New Revision: 107 Log: Execute noe_rsTransform_10001() only for encoding. Modified: trunk/noe/mina.c Modified: trunk/noe/mina.c ============================================================================== --- trunk/noe/mina.c (original) +++ trunk/noe/mina.c Wed Oct 22 19:29:40 2008 @@ -276,11 +276,10 @@ printf("%d %d %d\n", n, k, n-k); }else{ code[k-1]=0; noe_rsEncode_10001(code, parityLocator, n-k, SHIFT); - } - - if(noe_rsTransform_10001(code, parityLocator, n-k, tPoly, k-1, !decode, SHIFT) < 0){ - fprintf(stderr, "transform failure\n"); - return 6; + if(noe_rsTransform_10001(code, parityLocator, n-k, tPoly, k-1, 1, SHIFT) < 0){ + fprintf(stderr, "transform failure\n"); + return 6; + } } for(j= decode ? 0 : k-1; j<n; j++){

1 0

[mndiff]: r106 - trunk/noe/mina.c
by michael 22 Oct '08

22 Oct '08

Author: michael Date: Wed Oct 22 19:28:12 2008 New Revision: 106 Log: Forgot writing first slice. Modified: trunk/noe/mina.c Modified: trunk/noe/mina.c ============================================================================== --- trunk/noe/mina.c (original) +++ trunk/noe/mina.c Wed Oct 22 19:28:12 2008 @@ -283,7 +283,7 @@ printf("%d %d %d\n", n, k, n-k); return 6; } - for(j= decode ? 0 : k; j<n; j++){ + for(j= decode ? 0 : k-1; j<n; j++){ assert(code[j] <= 0xFFFF); buffer[2*(j*buffersize + i2 - i) ]= code[j]>>8; buffer[2*(j*buffersize + i2 - i)+1]= code[j];

1 0