- Mndiff-dev - lists.mplayerhq.hu

[mndiff]: r214 - in trunk/sudokoso: . H1 H2 H3 H4 H5 h1 h2 sudokoso.c test0.sud test1.sud test2.sud test3.sud test5.sud
by michael 30 Nov '10

30 Nov '10

Author: michael Date: Wed Dec 1 00:31:05 2010 New Revision: 214 Log: Yet another sudoko solver Added: trunk/sudokoso/ trunk/sudokoso/H1 trunk/sudokoso/H2 trunk/sudokoso/H3 trunk/sudokoso/H4 trunk/sudokoso/H5 trunk/sudokoso/h1 trunk/sudokoso/h2 trunk/sudokoso/sudokoso.c trunk/sudokoso/test0.sud trunk/sudokoso/test1.sud trunk/sudokoso/test2.sud trunk/sudokoso/test3.sud trunk/sudokoso/test5.sud Added: trunk/sudokoso/H1 ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ trunk/sudokoso/H1 Wed Dec 1 00:31:05 2010 (r214) @@ -0,0 +1,11 @@ +1 . . | . . . | . . 2 +. 9 . | 4 . . | . 5 . +. . 6 | . . . | 7 . . +------+-------+------ +. 5 . | 9 . 3 | . . . +. . . | . 7 . | . . . +. . . | 8 5 . | . 4 . +------+-------+------ +7 . . | . . . | 6 . . +. 3 . | . . 9 | . 8 . +. . 2 | . . . | . . 1 \ No newline at end of file Added: trunk/sudokoso/H2 ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ trunk/sudokoso/H2 Wed Dec 1 00:31:05 2010 (r214) @@ -0,0 +1,11 @@ +. . 1 | . . 4 | . . . +. . . | . 6 . | 3 . 5 +. . . | 9 . . | . . . +------+-------+------ +8 . . | . . . | 7 . 3 +. . . | . . . | . 2 8 +5 . . | . 7 . | 6 . . +------+-------+------ +3 . . | . 8 . | . . 6 +. . 9 | 2 . . | . . . +. 4 . | . . 1 | . . . Added: trunk/sudokoso/H3 ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ trunk/sudokoso/H3 Wed Dec 1 00:31:05 2010 (r214) @@ -0,0 +1,11 @@ +. . 1 | . . 4 | . . . +. . . | . 6 . | 3 . 5 +. . . | 9 . . | . . . +------+-------+------ +8 . . | . . . | 7 . 3 +. . . | . . . | . 2 8 +5 . . | . 7 . | 6 . . +------+-------+------ +3 . . | . 8 . | . . 6 +. . 9 | 2 . . | . . . +. 4 . | . . 1 | . . . \ No newline at end of file Added: trunk/sudokoso/H4 ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ trunk/sudokoso/H4 Wed Dec 1 00:31:05 2010 (r214) @@ -0,0 +1,11 @@ +. . . | . . . | . 3 9 +. . . | . . 1 | . . 5 +. . 3 | . 5 . | 8 . . +------+-------+------ +. . 8 | . 9 . | . . 6 +. 7 . | . . 2 | . . . +1 . . | 4 . . | . . . +------+-------+------ +. . 9 | . 8 . | . 5 . +. 2 . | . . . | 6 . . +4 . . | 7 . . | . . . Added: trunk/sudokoso/H5 ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ trunk/sudokoso/H5 Wed Dec 1 00:31:05 2010 (r214) @@ -0,0 +1,11 @@ +. 2 . | 4 . 3 | 7 . . +. . . | . . . | . 3 2 +. . . | . . . | . . 4 +------+-------+------ +. 4 . | 2 . . | . 7 . +8 . . | . 5 . | . . . +. . . | . . 1 | . . . +------+-------+------ +5 . . | . . . | 9 . . +. 3 . | 9 . . | . . 7 +. . 1 | . . 8 | 6 . . Added: trunk/sudokoso/h1 ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ trunk/sudokoso/h1 Wed Dec 1 00:31:05 2010 (r214) @@ -0,0 +1,9 @@ +..1.8.6.4 +.376..... +5........ +.....5... +..6.1.8.. +...4..... +........3 +.....752. +8.2.9.7.. \ No newline at end of file Added: trunk/sudokoso/h2 ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ trunk/sudokoso/h2 Wed Dec 1 00:31:05 2010 (r214) @@ -0,0 +1,9 @@ +.....3.6. +.......1. +.975...8. +....9.2.. +..8.7.4.. +..3.6.... +.1...289. +.4....... +.5.1..... \ No newline at end of file Added: trunk/sudokoso/sudokoso.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ trunk/sudokoso/sudokoso.c Wed Dec 1 00:31:05 2010 (r214) @@ -0,0 +1,182 @@ +//GPL Copyright Michael Niedermayer michaelni(a)gmx.at 2010 + +#include <inttypes.h> +#include <stdio.h> +#include <string.h> + +#undef NDEBUG +#include <assert.h> + +#define ICOUNT 81 +#define VCOUNT 9 +#define GSIZE 3 + +typedef struct Context{ + uint8_t bitmap[ICOUNT][VCOUNT]; + uint8_t gcounts[27][VCOUNT]; + uint8_t icounts[ICOUNT]; +}Context; + +static uint8_t i2g[ICOUNT][4]; +static uint8_t g2i[27][16]; + +static int max_solutions=2; + +static int findval(uint8_t bitmap[ICOUNT][VCOUNT], int idx){ + int val; + for(val=0; val<VCOUNT; val++) + if(bitmap[idx][val]) + return val; + return -1; +} + +static int findidx(uint8_t bitmap[ICOUNT][VCOUNT], int group, int val){ + int i; + for(i=0; i<9; i++) + if(bitmap[ g2i[group][i] ][val]) + return g2i[group][i]; + return -1; +} + +static void check(Context *s){ + int i, j; + for(i=0; i<ICOUNT; i++){ + int c=0; + for(j=0; j<VCOUNT; j++){ + c+= s->bitmap[i][j]; + } + if(c!= s->icounts[i]){ + fprintf(stderr, "icount missmatch idx=%d real=%d icount=%d\n", i, c, s->icounts[i]); + } + } +} + +static int rem(Context *s, int idx, int val); + +static int fix(Context *s, int idx, int val){ + int i, j; + assert(idx>=0); + + if(s->icounts[idx]>1) + for(i=0; i<VCOUNT; i++) + if(i!=val && s->bitmap[idx][i] && rem(s, idx, i)<0) + return -1; + + for(i=0; i<3; i++){ + if(s->gcounts[ i2g[idx][i] ][val]>1) + for(j=0; j<9; j++){ + int idx2= g2i[ i2g[idx][i] ][j]; + if(idx2 != idx && s->bitmap[idx2][val] && rem(s, idx2, val)<0) + return -1; + } + } + + return 0; +} + +static int rem(Context *s, int idx, int val){ + int i, c[4]; + int idxs[3]; + assert(s->bitmap[idx][val]); + + s->bitmap[idx][val]= 0; + c[0]= --s->icounts[idx]; + if(c[0]==0) + return -1; + for(i=0; i<3; i++){ + c[1+i]= --s->gcounts[ i2g[idx][i] ][val]; + if(c[1+i]==0){ + return -1; + }else if(c[1+i]==1) + idxs[i]= findidx(s->bitmap, i2g[idx][i], val); + } + if(c[0]==1){ + assert(idx>=0); + if(fix(s, idx, findval(s->bitmap, idx)) < 0) + return -1; + } + for(i=0; i<3; i++) + if(c[1+i]==1){ + assert(idxs[i]>=0); + if(fix(s, idxs[i], val) < 0) + return -1; + } + return 1; +} + +static int checkNsplit(Context *s){ + int i, j; + int bestidx=-1; + check(s); + if(max_solutions<=0) + return -2; + + for(i=0; i<ICOUNT; i++){ + assert(s->icounts[i]>0); + if(s->icounts[i]>1 && (bestidx<0 || s->icounts[i] < s->icounts[bestidx])) + bestidx= i; + } + if(bestidx >= 0){ + for(i=0; i<VCOUNT; i++){ + if(s->bitmap[bestidx][i]){ + Context s2= *s; + fprintf(stderr, "split at %2d with val %d\n", bestidx, i); + if(fix(&s2, bestidx, i) >= 0) + checkNsplit(&s2); + } + } + }else if(max_solutions>0){ + int chks=0; + printf("\n"); + for(i=0; i<ICOUNT; i++){ + if(s->icounts[i]>1){ + printf("?"); + }else{ + for(j=0; j<VCOUNT; j++){ + if(s->bitmap[i][j]) + break; + } + printf("%d", j+1); + chks += j+1; + } + chks*=17; + if(i%9==8) + printf("\n"); + } + printf("chk=%d\n", chks); + max_solutions--; + return 0; + } + return -2; +} + +int main(){ + int i,j; + Context s; + + for(i=0; i<81; i++){ + i2g[i][0]= i%9; + i2g[i][1]= i/9+9; + i2g[i][2]= ((i/3)%3)+3*(i/27)+18; + for(j=0; j<3; j++){ + g2i[ i2g[i][j] ][ g2i[i2g[i][j]][9]++ ]= i; + } + } + memset(s.bitmap , 1, sizeof(s.bitmap)); + memset(s.gcounts, 9, sizeof(s.gcounts)); + memset(s.icounts, 9, sizeof(s.icounts)); + for(i=0; i<ICOUNT; i++){ + int ch= getchar(); + if(ch==' ' || ch=='-' || ch=='+' || ch=='|' || ch=='\n'){ + i--; + }else if(ch>='1' && ch<='9'){ + fprintf(stderr, "will fix %d %d\n", i, ch-'1'); + if(fix(&s, i, ch-'1') < 0){ + fprintf(stderr, "No solutions\n"); + return 0; + } + } + } + checkNsplit(&s); + return 2-max_solutions; +} Added: trunk/sudokoso/test0.sud ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ trunk/sudokoso/test0.sud Wed Dec 1 00:31:05 2010 (r214) @@ -0,0 +1,9 @@ +12345678. +45698712. +78....... +2........ +3........ +5........ +6........ +9........ +......... Added: trunk/sudokoso/test1.sud ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ trunk/sudokoso/test1.sud Wed Dec 1 00:31:05 2010 (r214) @@ -0,0 +1,9 @@ +12345678. +78912345. +45678912. +31264597. +97831264. +64597831. +231564... +897...... +......... \ No newline at end of file Added: trunk/sudokoso/test2.sud ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ trunk/sudokoso/test2.sud Wed Dec 1 00:31:05 2010 (r214) @@ -0,0 +1,9 @@ +9........ +6.2.7.... +.8..146.. +.......4. +8.64.5... +724.9..5. +4.....897 +269...314 +.78.49.6. \ No newline at end of file Added: trunk/sudokoso/test3.sud ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ trunk/sudokoso/test3.sud Wed Dec 1 00:31:05 2010 (r214) @@ -0,0 +1,9 @@ +9........ +..2.7.... +....146.. +.......4. +8.6..5... +724.9..5. +.......97 +.6....314 +..8.49... \ No newline at end of file Added: trunk/sudokoso/test5.sud ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ trunk/sudokoso/test5.sud Wed Dec 1 00:31:05 2010 (r214) @@ -0,0 +1,9 @@ +5....7... +...6....2 +.2......4 +.481..2.. +9....2..5 +7......4. +.3..8.... +.....5.71 +....2.9.. \ No newline at end of file

1 0

[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