[mndiff]: r79 - in trunk/noe: bytestream.h filerw.c filerw.h galois.c galois.h gfft.c gfft.h noe.c noe_internal.h rs.c rs.h rw.c rw.h test.c
Author: michael Date: Tue Jul 10 00:37:39 2007 New Revision: 79 Log: version from unknown date, probably 2005 or 2006 this mostly reindents the code, and seems to loose the 2003 copyright on some files Modified: trunk/noe/bytestream.h trunk/noe/filerw.c trunk/noe/filerw.h trunk/noe/galois.c trunk/noe/galois.h trunk/noe/gfft.c trunk/noe/gfft.h trunk/noe/noe.c trunk/noe/noe_internal.h trunk/noe/rs.c trunk/noe/rs.h trunk/noe/rw.c trunk/noe/rw.h trunk/noe/test.c Modified: trunk/noe/bytestream.h ============================================================================== --- trunk/noe/bytestream.h (original) +++ trunk/noe/bytestream.h Tue Jul 10 00:37:39 2007 @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003 Michael Niedermayer <michaelni@gmx.at> + * Copyright (C) 2003-2005 Michael Niedermayer <michaelni@gmx.at> * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -16,138 +16,26 @@ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ -typedef struct ByteStream{ - uint8_t *buf; - uint8_t *buf_ptr; -// int length; - uint8_t *buf_end; -}ByteStream; - -static inline void initByteStream(ByteStream *bc, uint8_t *buf, int length){ - bc->buf= - bc->buf_ptr= buf; -// bc->length= length; - bc->buf_end= bc->buf + length; -} - -static inline int spaceLeft(ByteStream *bc){ -// return bc->length - ((int)(bc->buf_ptr - bc->buf)); - return ((int)(bc->buf_end - bc->buf_ptr)); -} - -/** - * - * @return <0 if an error occured - */ -static inline uint64_t get_v(ByteStream *bc){ - uint64_t val= 0; - - for(; spaceLeft(bc) > 0; ){ - int tmp= *(bc->buf_ptr++); - if(tmp&0x80) - val= (val<<7) + tmp - 0x80; - else - return (val<<7) + tmp; - } - - return -1; -} - -/** - * - * @return <0 if an error occured - */ -static inline int put_v(ByteStream *bc, uint64_t val){ - int i; - - if(spaceLeft(bc) < 9) return -1; //FIXME - - val &= 0x7FFFFFFFFFFFFFFFULL; // FIXME can only encode upto 63 bits currently - for(i=7; ; i+=7){ - if(val>>i == 0) break; - } - - for(i-=7; i>0; i-=7){ - *(bc->buf_ptr++)= 0x80 | (val>>i); - } - *(bc->buf_ptr++)= val&0x7F; - - return 0; -} - -/** - * - */ -static inline uint64_t get_c(ByteStream *bc, int length){ - uint64_t val= 0; - - for(i=length-1; i>=0; i--){ - val |= (*(bc->buf_ptr++)) << (8*i) ; - } - return val; -} - -/** - * - */ -static inline void put_c(ByteStream *bc, uint64_t val, int length){ - int i; - - for(i=length-1; i>=0; i--){ - *(bc->buf_ptr++)= val >> (i*8); - } -} - /** * - * @return <0 if an error occured */ -static inline int get_buffer(ByteStream *bc, uint8_t *dst, int length){ - int i; - - if(length > spaceLeft(bc) || length<0) return -1; - - for(i=0; i<length; i++){ - dst[i]= *(bc->buf_ptr++); - } - - return 0; -} - -/** - * - * @return <0 if an error occured - */ -static inline int put_buffer(ByteStream *bc, uint8_t *src, int length){ - int i; - - if(length > spaceLeft(bc)) return -1; - - for(i=0; i<length; i++){ - *(bc->buf_ptr++)= src[i]; - } +static inline uint64_t get_c(uint8_t **buf_ptr, int length){ + uint64_t val= 0; + int i; - return 0; + for(i=length-1; i>=0; i--){ + val |= (*((*buf_ptr)++)) << (8*i) ; + } + return val; } -#if 1 // just do a *_v() *_buffer() /** * - * @return <0 if an error occured */ -static inline int get_b(ByteStream *bc, uint8_t *dst, int max_length){ - const int length= get_v(bc); - if(length > max_length) return -1; - - return get_buffer(bc, dst, length); -} +static inline void put_c(uint8_t **buf_ptr, uint64_t val, int length){ + int i; -/** - * - * @return <0 if an error occured - */ -static inline int put_b(ByteStream *bc, uint8_t *src, int length){ - put_v(bc, length); - return put_buffer(bc, src, length); + for(i=length-1; i>=0; i--){ + *((*buf_ptr)++)= val >> (i*8); + } } -#endif \ No newline at end of file Modified: trunk/noe/filerw.c ============================================================================== --- trunk/noe/filerw.c (original) +++ trunk/noe/filerw.c Tue Jul 10 00:37:39 2007 @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003 Michael Niedermayer <michaelni@gmx.at> + * Copyright (C) 2003-2005 Michael Niedermayer <michaelni@gmx.at> * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -25,84 +25,84 @@ #include "filerw.h" static uint64_t fsize(FILE *f){ - uint64_t cur= ftell(f); - uint64_t size; - - fseek(f, 0, SEEK_END); //FIXME 64bit stuff? - size= ftell(f); - fseek(f, cur, SEEK_SET); - - return size; + uint64_t cur= ftell(f); + uint64_t size; + + fseek(f, 0, SEEK_END); //FIXME 64bit stuff? + size= ftell(f); + fseek(f, cur, SEEK_SET); + + return size; } static int fileIO(noe_RwContext *c, uint8_t *data, uint64_t pos, int len, int write){ - int i; - noe_FileRwContext *p= (noe_FileRwContext *)c; + int i; + noe_FileRwContext *p= (noe_FileRwContext *)c; - for(i=0; i<p->fileCount; i++){ - if(p->end[i] > pos){ - int e; - uint64_t currentLen= pos - p->end[i]; - if(currentLen > len) currentLen= len; - if(currentLen <= 0) return -1; - - if(write) - e= fwrite(data, currentLen, 1, p->file[i]); - else - e= fread(data, currentLen, 1, p->file[i]); - if(e!=1) return -1; - - len -= currentLen; - data+= currentLen; - pos += currentLen; - if(len==0) return 0; - } - } - return -1; + for(i=0; i<p->fileCount; i++){ + if(p->end[i] > pos){ + int e; + uint64_t currentLen= pos - p->end[i]; + if(currentLen > len) currentLen= len; + if(currentLen <= 0) return -1; + + if(write) + e= fwrite(data, currentLen, 1, p->file[i]); + else + e= fread(data, currentLen, 1, p->file[i]); + if(e!=1) return -1; + + len -= currentLen; + data+= currentLen; + pos += currentLen; + if(len==0) return 0; + } + } + return -1; } static void fileUninit(noe_RwContext *c){ - int i; - noe_FileRwContext *p= (noe_FileRwContext *)c; + int i; + noe_FileRwContext *p= (noe_FileRwContext *)c; - if(c==NULL) return; + if(c==NULL) return; - for(i=0; i<p->fileCount; i++){ - fclose(p->file[i]); - } - free(p->file); - free(p->end); - memset(p, 0, sizeof(noe_FileRwContext)); - free(p); + for(i=0; i<p->fileCount; i++){ + fclose(p->file[i]); + } + free(p->file); + free(p->end); + memset(p, 0, sizeof(noe_FileRwContext)); + free(p); } noe_RwContext *noe_getFileRwContext(char **fileNames, int fileCount, char *access){ - int i; - uint64_t pos; - noe_FileRwContext *p= malloc(sizeof(noe_FileRwContext)); - noe_RwContext *c= (noe_RwContext *)p; + int i; + uint64_t pos; + noe_FileRwContext *p= malloc(sizeof(noe_FileRwContext)); + noe_RwContext *c= (noe_RwContext *)p; - c->parent= NULL; + c->parent= NULL; - p->file= malloc(sizeof(FILE)*fileCount); - p->end= malloc(sizeof(uint64_t)*fileCount); + p->file= malloc(sizeof(FILE)*fileCount); + p->end= malloc(sizeof(uint64_t)*fileCount); - c->io= fileIO; - c->uninit= fileUninit; + c->io= fileIO; + c->uninit= fileUninit; - pos=0; - for(i=0; i<fileCount; i++){ - p->file[i]= fopen(fileNames[i], access); - if(p->file[i]==NULL) goto fail; - - pos+= fsize(p->file[i]); - p->end[i]= pos; - } - p->size= pos; - - return c; + pos=0; + for(i=0; i<fileCount; i++){ + p->file[i]= fopen(fileNames[i], access); + if(p->file[i]==NULL) goto fail; - fail: - fileUninit(c); - return NULL; + pos+= fsize(p->file[i]); + p->end[i]= pos; + } + c->size= p->end[i-1]; + + return c; + +fail: + fileUninit(c); + return NULL; } Modified: trunk/noe/filerw.h ============================================================================== --- trunk/noe/filerw.h (original) +++ trunk/noe/filerw.h Tue Jul 10 00:37:39 2007 @@ -17,14 +17,14 @@ */ typedef struct noe_FileRwContext{ - noe_RwContext rw; - FILE **file; + noe_RwContext rw; + FILE **file; - /** - * end of the ith file. - */ - uint64_t *end; - int fileCount; + /** + * end of the ith file. + */ + uint64_t *end; + int fileCount; }noe_FileRwContext; //FIXME move to .c if this is the only thing here Modified: trunk/noe/galois.c ============================================================================== --- trunk/noe/galois.c (original) +++ trunk/noe/galois.c Tue Jul 10 00:37:39 2007 @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003 Michael Niedermayer <michaelni@gmx.at> + * Copyright (C) 2002 Michael Niedermayer <michaelni@gmx.at> * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -31,64 +31,64 @@ GFF4Element noe_exp[SIZE]; GFF4Element noe_log[SIZE]; void noe_init(){ - GFF4Element ge= 1; - int i; - - for(i=0; i<SIZE; i++){ - noe_exp[i]= ge; - noe_log[ge]= i; - ge= prod(ge, PRIMITIVE_ELEMENT); - } - - noe_log[0]= 0xFFFF; - noe_log[1]= 0; - - noe_gfft_init(); + GFF4Element ge= 1; + int i; + + for(i=0; i<SIZE; i++){ + noe_exp[i]= ge; + noe_log[ge]= i; + ge= prod(ge, PRIMITIVE_ELEMENT); + } + + noe_log[0]= 0xFFFF; + noe_log[1]= 0; + + noe_gfft_init(); } /** * ... */ int noe_prodPoly(GFF4Element *dst, GFF4Element *src1, GFF4Element *src2, int order1, int order2){ - int order= order1 + order2; - int i; + int order= order1 + order2; + int i; - if(order1*order2 < (order1+order2)*64){ - for(i=order; i>=0; i--){ - unsigned int acc=0; - int j, end; + if(order1*order2 < (order1+order2)*64){ + for(i=order; i>=0; i--){ + unsigned int acc=0; + int j, end; - j = NOE_MAX(0, i - order2); - end= NOE_MIN(i, order1); + j = NOE_MAX(0, i - order2); + end= NOE_MIN(i, order1); - for(; j<=end; j++){ - acc+= prod(src1[j], src2[i-j]); - } - dst[i]= reduce(acc); - } - }else{ - const int logSize= noe_log2(order2 + order1)+1; - const int size= 1<<logSize; - GFF4Element temp[2][size]; //FIXME is this fast? - const GFF4Element scale= inv(size); + for(; j<=end; j++){ + acc+= prod(src1[j], src2[i-j]); + } + dst[i]= reduce(acc); + } + }else{ + const int logSize= noe_log2(order2 + order1)+1; + const int size= 1<<logSize; + GFF4Element temp[2][size]; //FIXME is this fast? + 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)); + //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)); - noe_gfft(temp[0], temp[0], logSize); - noe_gfft(temp[1], temp[1], logSize); - - for(i=0; i<size; i++){ - temp[0][i]= prod(prod(temp[0][i], temp[1][i]), scale); - } + noe_gfft(temp[0], temp[0], logSize); + noe_gfft(temp[1], temp[1], logSize); + + for(i=0; i<size; i++){ + temp[0][i]= prod(prod(temp[0][i], temp[1][i]), scale); + } - noe_igfft(temp[0], temp[0], logSize); - memcpy(dst, temp[0], sizeof(GFF4Element)*(order+1)); - } + noe_igfft(temp[0], temp[0], logSize); + memcpy(dst, temp[0], sizeof(GFF4Element)*(order+1)); + } - return order; + return order; } /** @@ -96,148 +96,148 @@ int noe_prodPoly(GFF4Element *dst, GFF4E * Note dst must be at least 2^log2(order1+order2) big FIXME benchmark if its worth it */ int noe_partialProdPoly(GFF4Element *dst, GFF4Element *src1, GFF4Element *src2, int order1, int order2){ - const int order= order2; - int i; - - if(order1*order2 < (order1+order2)*64){ - for(i=order; i>=0; i--){ - unsigned int acc=0; - int j, end; + const int order= order2; + int i; + + if(order1*order2 < (order1+order2)*64){ + for(i=order; i>=0; i--){ + unsigned int acc=0; + int j, end; - j = NOE_MAX(0, i - order2); - end= NOE_MIN(i, order1); + j = NOE_MAX(0, i - order2); + end= NOE_MIN(i, order1); - for(; j<=end; j++){ - acc+= prod(src1[j], src2[i-j]); - } - dst[i]= reduce(acc); - } - }else{ - const int logSize= noe_log2(order2 + order1)+1; - const int size= 1<<logSize; - GFF4Element temp[size]; //FIXME is this fast? - const GFF4Element scale= inv(size); + for(; j<=end; j++){ + acc+= prod(src1[j], src2[i-j]); + } + dst[i]= reduce(acc); + } + }else{ + const int logSize= noe_log2(order2 + order1)+1; + const int size= 1<<logSize; + GFF4Element temp[size]; //FIXME is this fast? + 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)); + //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)); - noe_gfft(dst, dst, logSize); - noe_gfft(temp, temp, logSize); - - for(i=0; i<size; i++){ - dst[i]= prod(prod(dst[i], temp[i]), scale); - } + noe_gfft(dst, dst, logSize); + noe_gfft(temp, temp, logSize); + + for(i=0; i<size; i++){ + dst[i]= prod(prod(dst[i], temp[i]), scale); + } - noe_igfft(dst, dst, logSize); - } + noe_igfft(dst, dst, logSize); + } - return order; + return order; } void noe_printPoly(GFF4Element *src, int order){ - int i; - - for(i=order; i>=0; i--){ - printf(" + %X*x^%d", src[i], i); - } - printf("\n"); + int i; + + for(i=order; i>=0; i--){ + printf(" + %X*x^%d", src[i], i); + } + printf("\n"); } /** * Evaluates the src polynom at x. */ GFF4Element noe_evalPoly(GFF4Element *src, int order, GFF4Element x){ - unsigned int acc=0; - int j; + unsigned int acc=0; + int j; - for(j=order; j>=0; j--){ - acc = sum(prod(acc, x), src[j]); - } + for(j=order; j>=0; j--){ + acc = sum(prod(acc, x), src[j]); + } - return acc; + return acc; } int noe_getDerivative(GFF4Element *dst, GFF4Element *src, int order){ - int i; - - for(i=0; i<order; i++){ - dst[i ]= prod(src[i+1], i+1); - } + int i; + + for(i=0; i<order; i++){ + dst[i ]= prod(src[i+1], i+1); + } - return order-1; + return order-1; } /** * ... */ void noe_synthPoly(GFF4Element *dst, GFF4Element *src, int count){ - if(count<20){ - int i; + if(count<20){ + int i; - dst[0]= 1; + dst[0]= 1; - for(i=0; i<count; i++){ - noe_prodPoly(dst, dst, src+2*i, i, 1); - } - }else{ - int pass, i, countLeft; - const int passCount= noe_log2(count-1)+1; - GFF4Element temp[2][4<<noe_log2(count-1)]; + for(i=0; i<count; i++){ + noe_prodPoly(dst, dst, src+2*i, i, 1); + } + }else{ + int pass, i, countLeft; + const int passCount= noe_log2(count-1)+1; + GFF4Element temp[2][4<<noe_log2(count-1)]; - assert(passCount>0); + assert(passCount>0); - countLeft= count; + countLeft= count; - // noe_printPoly(src, 1); - // noe_printPoly(src+2, 1); + // noe_printPoly(src, 1); + // noe_printPoly(src+2, 1); - for(i=0; i<(count>>1); i++){ - noe_prodPoly(temp[0]+4*i, src+4*i, src+4*i+2, 1, 1); - } - if(count&1){ - memcpy(temp[0]+4*i, src+4*i, 2*sizeof(GFF4Element)); - temp[0][4*i+2]= 0; - countLeft++; - } - countLeft>>=1; + for(i=0; i<(count>>1); i++){ + noe_prodPoly(temp[0]+4*i, src+4*i, src+4*i+2, 1, 1); + } + if(count&1){ + memcpy(temp[0]+4*i, src+4*i, 2*sizeof(GFF4Element)); + temp[0][4*i+2]= 0; + countLeft++; + } + countLeft>>=1; - // noe_printPoly(temp[0], 2); + // noe_printPoly(temp[0], 2); - for(pass=1; countLeft>1; pass++){ - const int step= 2<<pass; - GFF4Element *temp1= temp[ pass&1 ]; - GFF4Element *temp2= temp[(pass&1)^1]; + for(pass=1; countLeft>1; pass++){ + const int step= 2<<pass; + GFF4Element *temp1= temp[ pass&1 ]; + GFF4Element *temp2= temp[(pass&1)^1]; - for(i=0; i<(countLeft>>1); i++){ - noe_prodPoly(temp1+2*step*i, temp2+2*step*i, temp2+2*step*i+step, step>>1, step>>1); - } + for(i=0; i<(countLeft>>1); i++){ + noe_prodPoly(temp1+2*step*i, temp2+2*step*i, temp2+2*step*i+step, step>>1, step>>1); + } - if(countLeft&1){ - int len= (step>>1) + 1; - memcpy(temp1+2*step*i , temp2+2*step*i, len*sizeof(GFF4Element)); - memset(temp1+2*step*i + len , 0, step*sizeof(GFF4Element)); - countLeft++; - } - countLeft>>=1; - } + if(countLeft&1){ + int len= (step>>1) + 1; + memcpy(temp1+2*step*i , temp2+2*step*i, len*sizeof(GFF4Element)); + memset(temp1+2*step*i + len , 0, step*sizeof(GFF4Element)); + countLeft++; + } + countLeft>>=1; + } - assert(pass==passCount); + assert(pass==passCount); - // noe_printPoly(temp[0], count); + // noe_printPoly(temp[0], count); - memcpy(dst, temp[(pass&1)^1], (count+1)*sizeof(GFF4Element)); - // noe_printPoly(dst, count); - } + memcpy(dst, temp[(pass&1)^1], (count+1)*sizeof(GFF4Element)); + // noe_printPoly(dst, count); + } } int noe_getOrder(GFF4Element *src, int maxOrder){ - while(maxOrder && src[maxOrder]==0) - maxOrder--; + while(maxOrder && src[maxOrder]==0) + maxOrder--; - return maxOrder; + return maxOrder; } /** @@ -245,58 +245,58 @@ int noe_getOrder(GFF4Element *src, int m * Note: rem can be identical to nom */ int noe_divPoly(GFF4Element *quot, GFF4Element *rem, GFF4Element *nom, GFF4Element *denom, int nomOrder, int denomOrder){ - int i; - int remOrder= nomOrder; - int quotOrder= 0; + int i; + int remOrder= nomOrder; + int quotOrder= 0; - if(rem != nom) - memcpy(rem, nom, (nomOrder+1)*sizeof(GFF4Element)); + if(rem != nom) + memcpy(rem, nom, (nomOrder+1)*sizeof(GFF4Element)); - denomOrder= noe_getOrder(denom, denomOrder); + denomOrder= noe_getOrder(denom, denomOrder); - quot[0]=0; + quot[0]=0; - for(; remOrder >= denomOrder; remOrder--){ - GFF4Element scale; + for(; remOrder >= denomOrder; remOrder--){ + GFF4Element scale; - if(rem[remOrder]==0) continue; + if(rem[remOrder]==0) continue; - scale= prod(rem[remOrder], inv(denom[denomOrder])); + scale= prod(rem[remOrder], inv(denom[denomOrder])); - for(i=0; i<=denomOrder; i++){ //FIXME optimize - const int remIndex= i + remOrder - denomOrder; - rem[remIndex]= sum(rem[remIndex], SIZE - prod(scale, denom[i])); - } + for(i=0; i<=denomOrder; i++){ //FIXME optimize + const int remIndex= i + remOrder - denomOrder; + rem[remIndex]= sum(rem[remIndex], SIZE - prod(scale, denom[i])); + } - quot[remOrder - denomOrder]= scale; - if(quotOrder==0) - quotOrder= remOrder - denomOrder; - } - - return noe_getOrder(rem, remOrder); + quot[remOrder - denomOrder]= scale; + if(quotOrder==0) + quotOrder= remOrder - denomOrder; + } + + return noe_getOrder(rem, remOrder); } int noe_diffPoly(GFF4Element *dst, GFF4Element *src1, GFF4Element *src2, int order1, int order2){ - int i; - int minOrder= NOE_MIN(order1, order2); + int i; + int minOrder= NOE_MIN(order1, order2); - for(i=0; i<=minOrder; i++){ - dst[i]= sum(src1[i], SIZE - src2[i]); - } - - if(order1==order2){ - return noe_getOrder(dst, order1); - }else{ - if(dst!=src1){ - for(; i<=order1; i++){ - dst[i]= src1[i]; - } - } + for(i=0; i<=minOrder; i++){ + dst[i]= sum(src1[i], SIZE - src2[i]); + } + + if(order1==order2){ + return noe_getOrder(dst, order1); + }else{ + if(dst!=src1){ + for(; i<=order1; i++){ + dst[i]= src1[i]; + } + } - for(; i<=order2; i++){ - dst[i]= SIZE - src2[i]; - } + for(; i<=order2; i++){ + dst[i]= SIZE - src2[i]; + } - return NOE_MAX(order1, order2);; - } + return NOE_MAX(order1, order2);; + } } Modified: trunk/noe/galois.h ============================================================================== --- trunk/noe/galois.h (original) +++ trunk/noe/galois.h Tue Jul 10 00:37:39 2007 @@ -36,28 +36,28 @@ int noe_diffPoly(GFF4Element *dst, GFF4E int noe_getOrder(GFF4Element *src, int maxOrder); static inline GFF4Element reduce(GFF4Element a){ - a = (a&0xFFFF) - (a>>16); - a += (((int)a)>>31)&0x10001; - - return a; + a = (a&0xFFFF) - (a>>16); + a += (((int)a)>>31)&0x10001; + + return a; } static inline GFF4Element prod(GFF4Element a, GFF4Element b){ //printf("%d %d\n", a,b); - if((a&b)==0x10000) return 1; - else return reduce(a*b); + if((a&b)==0x10000) return 1; + else return reduce(a*b); } static inline GFF4Element sum(GFF4Element a, GFF4Element b){ - - a += b - 0x10001; - a += (((int)a)>>31)&0x10001; - - return a; + + a += b - 0x10001; + a += (((int)a)>>31)&0x10001; + + return a; } static inline GFF4Element inv(GFF4Element a){ - assert(a!=0); + assert(a!=0); - return noe_exp[SIZE - 1 - noe_log[a]]; + return noe_exp[SIZE - 1 - noe_log[a]]; } Modified: trunk/noe/gfft.c ============================================================================== --- trunk/noe/gfft.c (original) +++ trunk/noe/gfft.c Tue Jul 10 00:37:39 2007 @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003 Michael Niedermayer <michaelni@gmx.at> + * Copyright (C) 2002 Michael Niedermayer <michaelni@gmx.at> * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -28,16 +28,16 @@ uint8_t noe_revTable[256]; void noe_gfft_init(){ - int i; - - 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)); - - noe_revTable[i]= x; - } + int i; + + 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)); + + noe_revTable[i]= x; + } } int noe_log2(unsigned int v) // from ffmpeg @@ -68,46 +68,46 @@ int noe_log2(unsigned int v) // from ffm } void noe_permute(GFF4Element *dst, GFF4Element *src, int outCount){ - int i; + int i; - if(dst==src){ - for(i=1; i<outCount; i++){ - const int r= noe_bitReverse(i); - unsigned int t; - if(r<=i) continue; - t= dst[i]; - dst[i]= dst[r]; - dst[r]= t; - } - }else{ - for(i=0; i<outCount; i++){ - dst[i]= src[noe_bitReverse(i)]; - } - } + if(dst==src){ + for(i=1; i<outCount; i++){ + const int r= noe_bitReverse(i); + unsigned int t; + if(r<=i) continue; + t= dst[i]; + dst[i]= dst[r]; + dst[r]= t; + } + }else{ + for(i=0; i<outCount; i++){ + dst[i]= src[noe_bitReverse(i)]; + } + } } static inline void fft2(GFF4Element *p){ - const unsigned int a= p[0]; - const unsigned int b= p[1]; - - p[0]= sum(a, b); - p[1]= sum(a, SIZE - b); + const unsigned int a= p[0]; + const unsigned int b= p[1]; + + p[0]= sum(a, b); + p[1]= sum(a, SIZE - b); } static inline void fft4(GFF4Element *p){ - unsigned int a,b,c,d; + unsigned int a,b,c,d; - d= p[0] + SIZE*0x8000ULL; - - a= d +p[2]; - b= p[1]+p[3]; - c= d -p[2]; - d= (p[3] - p[1])<<8 /*(p[1] - p[3])*noe_exp[16384]*/; + d= p[0] + SIZE*0x8000ULL; + + a= d +p[2]; + b= p[1]+p[3]; + c= d -p[2]; + d= (p[3] - p[1])<<8 /*(p[1] - p[3])*noe_exp[16384]*/; - p[0]= reduce(a+b); - p[1]= reduce(a-b); - p[2]= reduce(c+d); - p[3]= reduce(c-d); + p[0]= reduce(a+b); + p[1]= reduce(a-b); + p[2]= reduce(c+d); + p[3]= reduce(c-d); } /* @@ -118,172 +118,172 @@ aWi + bWiWn (a - bWn)WiW2i */ static inline void fft8(GFF4Element *p){ - unsigned int a,b; + unsigned int a,b; - a= p[0]; - b= p[4]; - p[0]= a+b; - p[4]= a-b; + a= p[0]; + b= p[4]; + p[0]= a+b; + p[4]= a-b; - a= p[1]; - b= p[5]; - p[1]= a+b; - p[5]= reduce(SIZE*0x8000ULL + ((a-b)<<12))/*(a-b)*noe_exp[8192]*/; + a= p[1]; + b= p[5]; + p[1]= a+b; + p[5]= reduce(SIZE*0x8000ULL + ((a-b)<<12))/*(a-b)*noe_exp[8192]*/; - a= p[2]; - b= p[6]; - p[2]= a+b; - p[6]= (b-a)<<8 /*(a-b)*noe_exp[16384]*/; + a= p[2]; + b= p[6]; + p[2]= a+b; + p[6]= (b-a)<<8 /*(a-b)*noe_exp[16384]*/; - a= p[3]; - b= p[7]; - p[3]= a+b; - p[7]= (a-b)<<4/*(a-b)*noe_exp[3*8192]*/; + a= p[3]; + b= p[7]; + p[3]= a+b; + p[7]= (a-b)<<4/*(a-b)*noe_exp[3*8192]*/; - fft4(p); - fft4(p+4); + fft4(p); + fft4(p+4); } static void fft16(GFF4Element *p){ - int n; + int n; - for(n=0; n<8; n++){ - const unsigned int w= noe_exp[ n<<12 ]; - const unsigned int a= p[n ]; - const unsigned int b= p[n + 8]; + for(n=0; n<8; n++){ + const unsigned int w= noe_exp[ n<<12 ]; + const unsigned int a= p[n ]; + const unsigned int b= p[n + 8]; - p[n ]= sum(a, b); - p[n + 8]= reduce(sum(a, SIZE - b)*w); - } + p[n ]= sum(a, b); + p[n + 8]= reduce(sum(a, SIZE - b)*w); + } - fft8(p); - fft8(p+8); + fft8(p); + fft8(p+8); } static void fftn(GFF4Element *p, int logSize){ - int n; - const int size= 1<<(logSize-1); + int n; + const int size= 1<<(logSize-1); - for(n=0; n<size; n++){ - const unsigned int w= noe_exp[ n<<(16-logSize) ]; - const unsigned int a= p[n ]; - const unsigned int b= p[n + size]; + for(n=0; n<size; n++){ + const unsigned int w= noe_exp[ n<<(16-logSize) ]; + const unsigned int a= p[n ]; + const unsigned int b= p[n + size]; - p[n ]= sum(a, b); - p[n + size]= reduce(sum(a, SIZE - b)*w); - } - - if(logSize==5){ - fft16(p); - fft16(p+16); - }else{ - fftn(p, logSize-1); - fftn(p+size, logSize-1); - } + p[n ]= sum(a, b); + p[n + size]= reduce(sum(a, SIZE - b)*w); + } + + if(logSize==5){ + fft16(p); + fft16(p+16); + }else{ + fftn(p, logSize-1); + fftn(p+size, logSize-1); + } } static void fftn2(GFF4Element *p, GFF4Element *src, int logSize){ - int n; - const int size= 1<<(logSize-1); + int n; + const int size= 1<<(logSize-1); - for(n=0; n<size; n++){ - const unsigned int w= noe_exp[ n<<(16-logSize) ]; - const unsigned int a= src[n ]; - const unsigned int b= src[n + size]; + for(n=0; n<size; n++){ + const unsigned int w= noe_exp[ n<<(16-logSize) ]; + const unsigned int a= src[n ]; + const unsigned int b= src[n + size]; - p[n ]= sum(a, b); - p[n + size]= reduce(sum(a, SIZE - b)*w); - } - - if(logSize==5){ - fft16(p); - fft16(p+16); - }else{ - fftn(p, logSize-1); - fftn(p+size, logSize-1); - } + p[n ]= sum(a, b); + p[n + size]= reduce(sum(a, SIZE - b)*w); + } + + if(logSize==5){ + fft16(p); + fft16(p+16); + }else{ + fftn(p, logSize-1); + fftn(p+size, logSize-1); + } } static inline void ifft2(GFF4Element *p){ - const unsigned int a= p[0]; - const unsigned int b= p[1]; - - p[0]= sum(a, b); - p[1]= sum(a, SIZE - b); + const unsigned int a= p[0]; + const unsigned int b= p[1]; + + p[0]= sum(a, b); + p[1]= sum(a, SIZE - b); } static void ifftn(GFF4Element *p, int logSize){ - int n; - const int size= 1<<(logSize-1); + int n; + const int size= 1<<(logSize-1); - if(logSize==2){ - ifft2(p); - ifft2(p+2); - }else{ - ifftn(p, logSize-1); - ifftn(p+size, logSize-1); - } - - for(n=0; n<size; n++){ - const unsigned int w= noe_exp[ (1<<16) - (n<<(16-logSize)) ]; - const unsigned int a= p[n ]; - const unsigned int b= prod(p[n + size], w); + if(logSize==2){ + ifft2(p); + ifft2(p+2); + }else{ + ifftn(p, logSize-1); + ifftn(p+size, logSize-1); + } + + for(n=0; n<size; n++){ + const unsigned int w= noe_exp[ (1<<16) - (n<<(16-logSize)) ]; + const unsigned int a= p[n ]; + const unsigned int b= prod(p[n + size], w); - p[n ]= sum(a, b); - p[n + size]= sum(a, SIZE - b); - } - + p[n ]= sum(a, b); + p[n + size]= sum(a, SIZE - b); + } + } void noe_gfft(GFF4Element *dst, GFF4Element *src, int logSize){ -// int i, j, pass; +// int i, j, pass; //printf("%X %X\n", noe_exp[4096], noe_exp[3*4096]); - assert(logSize>=5); + assert(logSize>=5); - if(src==dst) - fftn(dst, logSize); - else - fftn2(dst, src, logSize); + if(src==dst) + fftn(dst, logSize); + else + fftn2(dst, src, logSize); #if 0 - memcpy(dst, src, sizeof(GFF4Element)<<logSize); - for(pass=0; pass<12; pass++){ - int block; - const int np= 1<<(16-pass-1); - const int blockCount= 1<<pass; - - for(block=0; block<blockCount; block++){ - int n; - const int top= block*np<<1; - const int bot= top + np; - - for(n=0; n<np; n++){ - const unsigned int w= noe_exp[ n<<pass ]; - const unsigned int a= dst[top + n]; - const unsigned int b= dst[bot + n]; - - dst[top + n]= sum(a, b); - dst[bot + n]= prod(sum(a, SIZE - b), w); - } - } - } + memcpy(dst, src, sizeof(GFF4Element)<<logSize); + for(pass=0; pass<12; pass++){ + int block; + const int np= 1<<(16-pass-1); + const int blockCount= 1<<pass; + + for(block=0; block<blockCount; block++){ + int n; + const int top= block*np<<1; + const int bot= top + np; + + for(n=0; n<np; n++){ + const unsigned int w= noe_exp[ n<<pass ]; + const unsigned int a= dst[top + n]; + const unsigned int b= dst[bot + n]; + + dst[top + n]= sum(a, b); + dst[bot + n]= prod(sum(a, SIZE - b), w); + } + } + } - { - int block; - for(block=0; block<4096; block++){ + { + int block; + for(block=0; block<4096; block++){ {START_TIMER - fft16(dst + block*16); + fft16(dst + block*16); STOP_TIMER} - } - } + } + } #endif } void noe_igfft(GFF4Element *dst, GFF4Element *src, int logSize){ - assert(logSize>=5); + assert(logSize>=5); - if(src!=dst) - memcpy(dst, src, sizeof(GFF4Element)<<logSize); + if(src!=dst) + memcpy(dst, src, sizeof(GFF4Element)<<logSize); - ifftn(dst, logSize); + ifftn(dst, logSize); } Modified: trunk/noe/gfft.h ============================================================================== --- trunk/noe/gfft.h (original) +++ trunk/noe/gfft.h Tue Jul 10 00:37:39 2007 @@ -25,6 +25,6 @@ int noe_log2(unsigned int v); extern uint8_t noe_revTable[256]; static inline unsigned int noe_bitReverse(unsigned int x){ - return (noe_revTable[x&255]<<8) | (noe_revTable[x>>8]); + return (noe_revTable[x&255]<<8) | (noe_revTable[x>>8]); } Modified: trunk/noe/noe.c ============================================================================== --- trunk/noe/noe.c (original) +++ trunk/noe/noe.c Tue Jul 10 00:37:39 2007 @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003 Michael Niedermayer <michaelni@gmx.at> + * Copyright (C) 2003-2005 Michael Niedermayer <michaelni@gmx.at> * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -17,26 +17,40 @@ */ #include <inttypes.h> - +#include <string.h> +#include <assert.h> +#include <limits.h> +#include "galois.h" +#include "rs.h" +#include "rw.h" +#include "bytestream.h" + static const uint8_t startcode[8]={0xAB, 0x2C, 0xE2, 0x47, 0x15, 'N', 'O', 'E'}; //#define STARTCODE (0xAB2CE24715000000ULL + ('N'<<16) + ('O'<<8) + 'E') #define STARTCODE_THRESHOLD 6 -#define HEADER_PARITY_LENGTH 26 -#define HEADER_LENGTH (38 + HEADER_PARITY_LENGTH) +#define HEADER_PARITY_LENGTH 16 +#define HEADER_DATA_LENGTH 34 +#define HEADER_LENGTH (HEADER_DATA_LENGTH + HEADER_PARITY_LENGTH) +#define HEADER_THRESHOLD (HEADER_LENGTH/2) //50 #define BUFFER_LENGTH 262144 +#define HASH_BITS 32 typedef struct NoeContext{ - int debug; - int fileId; - int fileChecksum; - int fileIdThreshold; - int seqNum; - int headerCount; - int parityCount; - int fingerprintCount; - int flags; - int dataSize; - int header[HEADER_LENGTH][256]; + int debug; + int fileChecksum; + int seqNum; + int headerCount; + int parityCount; + int fingerprintCount; + int flags; + int dataSize; + int fileIdThreshold; + int version; +// uint8_t header[HEADER_LENGTH]; + int header[HEADER_LENGTH][256]; + uint32_t *fingerprint; + uint8_t *fingerprintOk; + int fingerprintOk_count; }NoeContext; const static uint8_t parity[256]={ @@ -59,127 +73,124 @@ const static uint8_t parity[256]={ }; /** - * + * searches for a header. * @return length if not found */ -static uint64_t find_header(NoeContext *n, uint8_t *buffer, uint64_t length){ - int i; +static int find_header(NoeContext *n, uint8_t *buffer, int length){ + int i; - for(i=0; i + HEADER_LENGTH < length; i++){ - int j; - int score=8; + for(i=0; i + HEADER_LENGTH < length; i++){ + int j; + int score=8; - for(j=0; j<8; j++){ - if(buffer[i + j] != startcode[j]){ - score--; - if(score < STARTCODE_THRESHOLD) break; - } - } - if(score < STARTCODE_THRESHOLD) continue; + for(j=0; j<8; j++){ + if(buffer[i + j] != startcode[j]) + score--; + } + if(score < STARTCODE_THRESHOLD) continue; - score=8; - for(j=0; j<4; j++){ //FIXME cleaner? - if(buffer[i + 12 + j] != ((n->fileChecksum >> (24 - 8*j)) & 0xFF)) - score--; - } - for(j=0; j<4; j++){ - if(buffer[i + 16+ j] != ((n->fileId >> (24 - 8*j)) & 0xFF)) - score--; - } - if(score < n->fileIdThreshold) continue; + score+=4; + for(j=0; j<4; j++){ + if(buffer[i + 12 + j] != ((n->fileChecksum >> (24 - 8*j)) & 0xFF)) + score--; + } +/* for(j=0; j<4; j++){ + if(buffer[i + 16+ j] != ((n->fileId >> (24 - 8*j)) & 0xFF)) + score--; + }*/ + if(score < n->fileIdThreshold) continue; - return i; - } + return i; + } - return length; + return length; } static int decode_header(NoeContext *n, uint8_t *buffer){ - ByteStream bc; - int erasedCount=0; //FIXME - const int n= SIZE - 1; - const int k= SIZE - 1 - HEADER_PARITY_LENGTH; - GFF4Element erased[HEADER_PARITY_LENGTH]; - GFF4Element code[n]; - int i,j; + uint8_t *bs; + int erasedCount=0; //FIXME + const int nn= SIZE - 1; + const int k= SIZE - 1 - HEADER_PARITY_LENGTH; + GFF4Element erased[HEADER_PARITY_LENGTH]; + GFF4Element code[nn]; + int i,j; - for(j=0; j<8; j++){ - buffer[j] = startcode[j]; - } - - for(i=12; i<HEADER_LENGTH - HEADER_PARITY_LENGTH; i++){ - int best=0; - int bestScore=0; + for(j=0; j<8; j++){ + buffer[j] = startcode[j]; + } + + for(i=12; i<HEADER_DATA_LENGTH; i++){ + int best=0; + int bestScore=0; - for(j=0; j<256; j++){ - const int score= n->header[i][j]; - if(score > bestScore){ - bestScore= score; - best= j; - } - } - buffer[i]= best; //FIXME dont modify it / load into code directly - } + for(j=0; j<256; j++){ + const int score= n->header[i][j]; + if(score > bestScore){ + bestScore= score; + best= j; + } + } + buffer[i]= best; //FIXME dont modify it / load into code directly + } - initByteStream(&bc, buffer, HEADER_LENGTH); + bs= buffer; - memset(code, 0, sizeof(GFF4Element)*n); - for(i=0; 2*i<HEADER_LENGTH - HEADER_PARITY_LENGTH; i++){ - code[i ]= get_c(bc, 2); - } - for(i=0; 2*i<HEADER_PARITY_LENGTH; i++){ - code[k+i]= get_c(bc, 2); - } + memset(code, 0, sizeof(GFF4Element)*nn); + for(i=0; 2*i<HEADER_DATA_LENGTH; i++){ + code[i ]= get_c(&bs, 2); + } + for(i=0; 2*i<HEADER_PARITY_LENGTH; i++){ + code[k+i]= get_c(&bs, 2); + } - if(noe_rsDecode(code, erased, erasedCount, HEADER_PARITY_LENGTH) < 0) - return -1; + if(noe_rsDecode(code, erased, erasedCount, HEADER_PARITY_LENGTH) < 0) + return -1; - for(i=HEADER_LENGTH - HEADER_PARITY_LENGTH; i<k; i++){ - if(code[i] != 0) - return -2; - } - for(i=0; i<8; i++){ - if(buffer[i] != startcode[i]) - return -2; - } + for(i=HEADER_DATA_LENGTH; i<k; i++){ + if(code[i] != 0) + return -2; + } + for(i=0; i<8; i++){ + if(buffer[i] != startcode[i]) + return -2; + } - // noe_printPoly(gen, i); - // noe_printPoly(syn, i-1); + // noe_printPoly(gen, i); + // noe_printPoly(syn, i-1); - for(i=0; 2*i<HEADER_LENGTH - HEADER_PARITY_LENGTH; i++){ - buffer[2*i+0]= code[ i] >> 8; - buffer[2*i+1]= code[ i]; - } - for(i=0; 2*i<HEADER_PARITY_LENGTH; i++){ - const int j= i + (HEADER_LENGTH - HEADER_PARITY_LENGTH)/2; - buffer[2*j+0]= code[k+i] >> 8; - buffer[2*j+1]= code[k+i]; - } + for(i=0; 2*i<HEADER_DATA_LENGTH; i++){ + buffer[2*i+0]= code[ i] >> 8; + buffer[2*i+1]= code[ i]; + } + for(i=0; 2*i<HEADER_PARITY_LENGTH; i++){ + const int j= i + HEADER_DATA_LENGTH/2; + buffer[2*j+0]= code[k+i] >> 8; + buffer[2*j+1]= code[k+i]; + } - initByteStream(&bc, buffer, HEADER_LENGTH); + bs= buffer; - get_c(bc, 8); - n->seqNum= get_c(bc, 4); - n->fileChecksum= get_c(bc, 4); - n->fileId= get_c(bc, 4); - n->version= get_c(bc, 1); - if(n->version > 0) - return -3; + get_c(&bs, 8); + n->seqNum= get_c(&bs, 4); + n->fileChecksum= get_c(&bs, 4); + n->version= get_c(&bs, 1); + if(n->version > 0) + return -3; - n->flags= get_c(bc, 1); - n->headerCount= get_c(bc, 4); - if(n->seqNum >= n->headerCount) - return -2; + n->flags= get_c(&bs, 1); + n->headerCount= get_c(&bs, 4); + if(n->seqNum >= n->headerCount) + return -2; - n->parityCount= get_c(bc, 2); - n->fingerprintCount= get_c(bc, 2); - n->dataSize= get_c(bc, 8); + n->parityCount= get_c(&bs, 2); + n->fingerprintCount= get_c(&bs, 2); + n->dataSize= get_c(&bs, 8); - for(i=12; i<HEADER_LENGTH - HEADER_PARITY_LENGTH; i++){ - n->header[i][ buffer[i] ]= INT_MAX/2; - } + for(i=12; i<HEADER_DATA_LENGTH; i++){ + n->header[i][ buffer[i] ]= INT_MAX/2; + } - return n->seqNum; + return n->seqNum; } @@ -188,57 +199,61 @@ static int decode_header(NoeContext *n, * @return -1 if not found */ static int find_and_decode_global_header(NoeContext *n, noe_RwContext *rw){ - int length= BUFFER_LENGTH - uint64_t i; - uint8_t buffer[length]; + int length= BUFFER_LENGTH; + uint64_t i; + uint8_t buffer[length]; - for(i=rw->size; i>=0; i-= length - HEADER_LENGTH){ - int pos; + for(i=rw->size; i>=0; i-= length - HEADER_LENGTH){ + int pos; - if(i < length) length= i; - rw->io(rw, buffer, i - length, length, 0); + if(i < length) length= i; + rw->io(rw, buffer, i - length, length, 0); - for(pos=0; ; pos++){ - int j; - pos += find_header(n, buffer + pos, length - pos); - if(pos >= length) break; + for(pos=0; ; pos++){ + int j; + pos += find_header(n, buffer + pos, length - pos); + if(pos >= length) break; - for(j=0; j<HEADER_LENGTH; j++){ //FIXME bitwise histogram? - const int c= buffer[pos + j] - n->header[j][c]++; - } + for(j=0; j<HEADER_LENGTH; j++){ //FIXME bitwise histogram? + const int c= buffer[pos + j]; + n->header[j][c]++; + } - if( decode_header(n, buffer + pos) >= 0) - return 0; - } - length= BUFFER_LENGTH; - } + if( decode_header(n, buffer + pos) >= 0) + return 0; + } + length= BUFFER_LENGTH; + } - return -1; + return -1; } static inline int getChecksum(unsigned int fingerprint, unsigned int pos){ - return (fingerprint ^ pos) % 251; + return (fingerprint ^ pos) % 251; } static int decode_fingerprints(NoeContext *n, uint8_t *buffer, int length){ - int i, count; - ByteStream bc; + int i, count; + uint8_t *bs;; - count= MIN(n->fingerprintCount, length/5); + count= n->fingerprintCount; + if(count > length/5) + count= length/5; - initByteStream(&bc, buffer, 5*count); - for(i=0; i<count; i++){ - const unsigned int c= get_c(bc, 4); - const int checksum= get_c(bc, 1); - const int index= n->seqNum + i*n->headerCount; - const int expectedChecksum= getChecksum(c, index); + bs= buffer; + for(i=0; i<count; i++){ + const unsigned int c= get_c(&bs, 4); + const int checksum= get_c(&bs, 1); + const int index= n->seqNum + i*n->headerCount; + const int expectedChecksum= getChecksum(c, index); - if(expectedChecksum == checksum){ - n->fingerprintOk[index]= 1; - n->fingerprint[index]= c; - }//FIXME resync - } + if(expectedChecksum == checksum){ + n->fingerprintOk[index]= 1; + n->fingerprint[index]= c; + n->fingerprintOk_count++; + }//FIXME resync + } + return 0; } /** @@ -246,36 +261,65 @@ static int decode_fingerprints(NoeContex * @return -1 if not found */ static int find_and_decode_packets(NoeContext *n, noe_RwContext *rw){ - int length= BUFFER_LENGTH - const int packetLength= HEADER_LENGTH + 5*n->fingerprintCount; - uint64_t i; - uint8_t buffer[length]; + int length= BUFFER_LENGTH; + const int packetLength= HEADER_LENGTH + 5*n->fingerprintCount; + uint64_t i; + uint8_t buffer[length]; - n->fingerprint = malloc(n->fingerprintCount*n->headerCount * sizeof(int)); - n->fingerprintOk= malloc(n->fingerprintCount*n->headerCount); - memset(n->fingerprintOk, 0, n->fingerprintCount*n->headerCount); + n->fingerprint = malloc(n->fingerprintCount*n->headerCount * sizeof(int)); + n->fingerprintOk= malloc(n->fingerprintCount*n->headerCount); + memset(n->fingerprintOk, 0, n->fingerprintCount*n->headerCount); - for(i=rw->size; i>=0; i-= length - packetLength){ - int pos; + for(i=rw->size; i>=0; i-= length - packetLength){ + int pos; - if(i < length) length= i; - rw->io(rw, buffer, i - length, length, 0); + if(i < length) length= i; + rw->io(rw, buffer, i - length, length, 0); - for(pos=0; ; pos++){ - int j; - pos += find_header(n, buffer + pos, length - pos); - if(pos >= length) break; + for(pos=0; ; pos++){ + int j; + pos += find_header(n, buffer + pos, length - pos); + if(pos >= length) break; - if( decode_header(n, buffer + pos) < 0 ) - continue; - pos += HEADER_LENGTH; + if( decode_header(n, buffer + pos) < 0 ) + continue; + pos += HEADER_LENGTH; - decode_fingerprints(n, buffer + pos, length - pos); - } - length= BUFFER_LENGTH; - - //FIXME detect if enough packets - } + decode_fingerprints(n, buffer + pos, length - pos); + } + length= BUFFER_LENGTH; - return -1; + if(n->fingerprintOk_count >= n->fingerprintCount*n->headerCount*15/16) + break; + } + + return 0; +} + +static int match_fingerprints(NoeContext *n, noe_RwContext *rw){ + int length= BUFFER_LENGTH; +// const int packetLength= HEADER_LENGTH + 5*n->fingerprintCount; + uint64_t i; + uint8_t buffer[length]; + + for(i=0; i<n->fingerprintCount*n->headerCount; i++){ + if(!n->fingerprintOk[i]) + continue; + + } + + for(i=0; i<rw->size; i+= length - HASH_BITS/8){ + int pos; + + rw->io(rw, buffer, i, length, 0); + + for(pos=0; ; pos++){ + } + } + +// remove certainly false matches (where better match exists) + +// setup remap table } + +//decode data into another file Modified: trunk/noe/noe_internal.h ============================================================================== --- trunk/noe/noe_internal.h (original) +++ trunk/noe/noe_internal.h Tue Jul 10 00:37:39 2007 @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003 Michael Niedermayer <michaelni@gmx.at> + * Copyright (C) 2002 Michael Niedermayer <michaelni@gmx.at> * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -21,12 +21,12 @@ static inline long long rdtsc() { - long long l; - asm volatile( "rdtsc\n\t" - : "=A" (l) - ); -// printf("%d\n", int(l/1000)); - return l; + long long l; + asm volatile( "rdtsc\n\t" + : "=A" (l) + ); +// printf("%d\n", int(l/1000)); + return l; } #define START_TIMER \ Modified: trunk/noe/rs.c ============================================================================== --- trunk/noe/rs.c (original) +++ trunk/noe/rs.c Tue Jul 10 00:37:39 2007 @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003 Michael Niedermayer <michaelni@gmx.at> + * Copyright (C) 2002 Michael Niedermayer <michaelni@gmx.at> * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -32,139 +32,139 @@ * */ void noe_getRsGenerator(GFF4Element *dst, int first, int order){ - int i; - GFF4Element factor[2*order]; + int i; + GFF4Element factor[2*order]; - factor[0]= SIZE - noe_exp[first]; - factor[1]= 1; + factor[0]= SIZE - noe_exp[first]; + factor[1]= 1; - for(i=1; i<order; i++){ - factor[2*i+0]= prod(factor[2*i-2], PRIMITIVE_ELEMENT); - factor[2*i+1]= 1; - } - - noe_synthPoly(dst, factor, order); + for(i=1; i<order; i++){ + factor[2*i+0]= prod(factor[2*i-2], PRIMITIVE_ELEMENT); + factor[2*i+1]= 1; + } + + noe_synthPoly(dst, factor, order); } -void noe_getSyndrom(GFF4Element *syn, GFF4Element *src, int first, int order){ - noe_gfft(syn, src, 16); - noe_permute(syn, syn, order+1); +void noe_getSyndrom(GFF4Element *syn, GFF4Element *src, int order){ + noe_gfft(syn, src, 16); + noe_permute(syn, syn, order+1); - syn[0]= 1; + syn[0]= 1; #if 0 - for(i=0; i<order; i++){ - syn[i+1]= noe_evalPoly(src, SIZE-2, noe_exp[first + i]); - } + for(i=0; i<order; i++){ + syn[i+1]= noe_evalPoly(src, SIZE-2, noe_exp[1 + i]); + } #endif } #if 1 noe_RsEncoder *noe_getRsEncoder(int parityCount){ - const int dataCount= SIZE - parityCount - 1; - int i; - GFF4Element *locator, *factor; - GFF4Element locatorDerivative[parityCount]; - noe_RsEncoder *encoder= memalign(16, sizeof(noe_RsEncoder)); - - locator= encoder->parityLocator= memalign(16, sizeof(GFF4Element)*(parityCount+1)); - factor= encoder->parityFactor = memalign(16, sizeof(GFF4Element)* parityCount ); + const int dataCount= SIZE - parityCount - 1; + int i; + GFF4Element *locator, *factor; + GFF4Element locatorDerivative[parityCount]; + noe_RsEncoder *encoder= memalign(16, sizeof(noe_RsEncoder)); + + locator= encoder->parityLocator= memalign(16, sizeof(GFF4Element)*(parityCount+1)); + factor= encoder->parityFactor = memalign(16, sizeof(GFF4Element)* parityCount ); - encoder->parityCount= parityCount; - - locator[0]= 1; - for(i=0; i<parityCount; i++){ - GFF4Element locationFactor[2]; - - locationFactor[0] = 1; - locationFactor[1] = SIZE - noe_exp[dataCount + i]; - noe_prodPoly(locator, locator, locationFactor, i, 1); //FIXME use synthPoly - } + encoder->parityCount= parityCount; + + locator[0]= 1; + for(i=0; i<parityCount; i++){ + GFF4Element locationFactor[2]; + + locationFactor[0] = 1; + locationFactor[1] = SIZE - noe_exp[dataCount + i]; + noe_prodPoly(locator, locator, locationFactor, i, 1); //FIXME use synthPoly + } #if 0 for(i=0; i<parityCount; i++){ - if(noe_evalPoly(locator, parityCount, inv(noe_exp[dataCount + i]))){ - printf("Internal Error 1\n"); - } + if(noe_evalPoly(locator, parityCount, inv(noe_exp[dataCount + i]))){ + printf("Internal Error 1\n"); + } } if(!noe_evalPoly(locator, parityCount, inv(noe_exp[dataCount - 1]))) - printf("Internal Error 2\n"); + printf("Internal Error 2\n"); #endif - i= noe_getDerivative(locatorDerivative, locator, parityCount); - assert(i==parityCount-1); + i= noe_getDerivative(locatorDerivative, locator, parityCount); + assert(i==parityCount-1); - for(i=0; i<parityCount; i++){ - GFF4Element X= noe_exp[dataCount + i]; - GFF4Element invX= noe_exp[SIZE - dataCount - i - 1]; - GFF4Element denom; - - assert(X == inv(invX)); + for(i=0; i<parityCount; i++){ + GFF4Element X= noe_exp[dataCount + i]; + GFF4Element invX= noe_exp[SIZE - dataCount - i - 1]; + GFF4Element denom; + + assert(X == inv(invX)); - denom= noe_evalPoly(locatorDerivative, parityCount-1, invX); //FIXME do in freq domain if parityCount>1000 - factor[i]= prod(SIZE - X, inv(denom)); - } - - return encoder; + denom= noe_evalPoly(locatorDerivative, parityCount-1, invX); //FIXME do in freq domain if parityCount>1000 + factor[i]= prod(SIZE - X, inv(denom)); + } + + return encoder; } void noe_freeRsEncoder(noe_RsEncoder *encoder){ - if(!encoder) return; - - if(encoder->parityLocator) free(encoder->parityLocator); - encoder->parityLocator= NULL; - - if(encoder->parityFactor) free(encoder->parityFactor); - encoder->parityFactor= NULL; + if(!encoder) return; + + if(encoder->parityLocator) free(encoder->parityLocator); + encoder->parityLocator= NULL; + + if(encoder->parityFactor) free(encoder->parityFactor); + encoder->parityFactor= NULL; - free(encoder); + free(encoder); } /** * */ void noe_rsEncode(noe_RsEncoder *encoder, GFF4Element *data){ - int i; - const int parityCount= encoder->parityCount; - const int dataCount= SIZE - parityCount - 1; - GFF4Element syn[SIZE - 1]; - GFF4Element omega[SIZE - 1]; - GFF4Element *locator= encoder->parityLocator; - GFF4Element *factor= encoder->parityFactor; + int i; + const int parityCount= encoder->parityCount; + const int dataCount= SIZE - parityCount - 1; + GFF4Element syn[SIZE - 1]; + GFF4Element omega[SIZE - 1]; + GFF4Element *locator= encoder->parityLocator; + GFF4Element *factor= encoder->parityFactor; - memset(data + dataCount, 0, parityCount*sizeof(GFF4Element)); - - noe_getSyndrom(syn, data, 1, parityCount); + memset(data + dataCount, 0, parityCount*sizeof(GFF4Element)); + + noe_getSyndrom(syn, data, parityCount); - noe_partialProdPoly(omega, locator, syn, parityCount, parityCount); - - if(parityCount < 1000){ - for(i=0; i<parityCount; i++){ - GFF4Element invX= noe_exp[SIZE - dataCount - i - 1]; - - GFF4Element parity= prod(noe_evalPoly(omega, parityCount, invX), factor[i]); - - data[dataCount + i]= SIZE - parity; - } - }else{ + noe_partialProdPoly(omega, locator, syn, parityCount, parityCount); + + if(parityCount < 1000){ + for(i=0; i<parityCount; i++){ + GFF4Element invX= noe_exp[SIZE - dataCount - i - 1]; + + GFF4Element parity= prod(noe_evalPoly(omega, parityCount, invX), factor[i]); + + data[dataCount + i]= SIZE - parity; + } + }else{ //START_TIMER #if 0 - for(i=0; i<parityCount; i++){ - GFF4Element invX= noe_exp[SIZE - dataCount - i - 1]; - - GFF4Element parity= prod(noe_evalPoly(omega, parityCount, invX), factor[i]); - - data[dataCount + i]= SIZE - parity; - } + for(i=0; i<parityCount; i++){ + GFF4Element invX= noe_exp[SIZE - dataCount - i - 1]; + + GFF4Element parity= prod(noe_evalPoly(omega, parityCount, invX), factor[i]); + + data[dataCount + i]= SIZE - parity; + } #else - memset(omega + parityCount + 1, 0, (SIZE - 2 - parityCount)*sizeof(GFF4Element)); - noe_gfft(omega, omega, 16); - for(i=0; i<parityCount; i++){ - int index= SIZE - dataCount - i - 1; - - GFF4Element parity= prod(omega[noe_bitReverse(index)], factor[i]); - - data[dataCount + i]= SIZE - parity; - } + memset(omega + parityCount + 1, 0, (SIZE - 2 - parityCount)*sizeof(GFF4Element)); + noe_gfft(omega, omega, 16); + for(i=0; i<parityCount; i++){ + int index= SIZE - dataCount - i - 1; + + GFF4Element parity= prod(omega[noe_bitReverse(index)], factor[i]); + + data[dataCount + i]= SIZE - parity; + } #endif //STOP_TIMER - } + } } #endif @@ -173,168 +173,168 @@ void noe_rsEncode(noe_RsEncoder *encoder * @param omega must be parityCount+2 big */ int noe_rsEuclid(GFF4Element *locator[2], GFF4Element *omega[2], int parityCount, int erasureCount, int *locatorOrderP, int *omegaOrderP){ - int i, quotOrder; - int locatorOrder[2]= {0,0}; - int omegaOrder[2]= {parityCount+1, -1}; - GFF4Element quot[parityCount+2]; //FIXME size ok? + int i, quotOrder; + int locatorOrder[2]= {0,0}; + int omegaOrder[2]= {parityCount+1, -1}; + GFF4Element quot[parityCount+2]; //FIXME size ok? - memset(omega[0], 0, (parityCount+1)*sizeof(GFF4Element)); - omega[0][parityCount+1]= 1; - locator[0][0]=0; - locator[1][0]=1; - omegaOrder[1]= noe_getOrder(omega[1], parityCount); - - for(i=0; 1; i++){ - const int di= i&1; - const int si= 1-di; + memset(omega[0], 0, (parityCount+1)*sizeof(GFF4Element)); + omega[0][parityCount+1]= 1; + locator[0][0]=0; + locator[1][0]=1; + omegaOrder[1]= noe_getOrder(omega[1], parityCount); + + for(i=0; 1; i++){ + const int di= i&1; + const int si= 1-di; #ifdef DEBUG_EUCLID printf("Locator0:");noe_printPoly(locator[di], locatorOrder[di]); printf("Omega0:");noe_printPoly(omega[di], omegaOrder[di]); printf("Locator1:");noe_printPoly(locator[si], locatorOrder[si]); printf("Omega1:");noe_printPoly(omega[si], omegaOrder[si]); #endif - if(2*omegaOrder[si] <= parityCount + erasureCount) - break; + if(2*omegaOrder[si] <= parityCount + erasureCount) + break; - quotOrder= omegaOrder[di] - omegaOrder[si]; + quotOrder= omegaOrder[di] - omegaOrder[si]; - omegaOrder[di]= noe_divPoly(quot, omega[di], omega[di], omega[si], omegaOrder[di], omegaOrder[si]); + omegaOrder[di]= noe_divPoly(quot, omega[di], omega[di], omega[si], omegaOrder[di], omegaOrder[si]); - quotOrder= noe_prodPoly(quot, quot, locator[si], quotOrder, locatorOrder[si]); - locatorOrder[di]= noe_diffPoly(locator[di], locator[di], quot, locatorOrder[di], quotOrder); + quotOrder= noe_prodPoly(quot, quot, locator[si], quotOrder, locatorOrder[si]); + locatorOrder[di]= noe_diffPoly(locator[di], locator[di], quot, locatorOrder[di], quotOrder); #ifdef DEBUG_EUCLID printf("quot:");noe_printPoly(quot, quotOrder); printf("Locator:");noe_printPoly(locator[di], locatorOrder[di]); printf("Omega:");noe_printPoly(omega[di], omegaOrder[di]); #endif - } + } - i++; - - *locatorOrderP= locatorOrder[i&1]; - *omegaOrderP= omegaOrder[i&1]; + i++; + + *locatorOrderP= locatorOrder[i&1]; + *omegaOrderP= omegaOrder[i&1]; - return i&1; + return i&1; } int noe_rsDecode(GFF4Element *data, int *erasure, int erasureCount, int parityCount){ - int i; - int errorCount, psiOrder, gfftEval, omegaOrder, phantomErrorCount; - const int dataCount= SIZE - 1 - parityCount; - GFF4Element erasureLocator[erasureCount + 1]; - GFF4Element erasureSynthSrc[erasureCount*2 + 1]; - GFF4Element locator0[parityCount + 1]; - GFF4Element locator1[parityCount + 1]; - GFF4Element *locators[2]={locator0, locator1}; - GFF4Element omega0[SIZE - 1]; - GFF4Element omega1[SIZE - 1]; - GFF4Element *omegas[2]={omega0, omega1}; //FIXME clean this shit up - GFF4Element *fErrorLocator, *errorLocator, *omega, *syn, *psi; + int i; + int errorCount, psiOrder, gfftEval, omegaOrder, phantomErrorCount; + const int dataCount= SIZE - 1 - parityCount; + GFF4Element erasureLocator[erasureCount + 1]; + GFF4Element erasureSynthSrc[erasureCount*2 + 1]; + GFF4Element locator0[parityCount + 1]; + GFF4Element locator1[parityCount + 1]; + GFF4Element *locators[2]={locator0, locator1}; + GFF4Element omega0[SIZE - 1]; + GFF4Element omega1[SIZE - 1]; + GFF4Element *omegas[2]={omega0, omega1}; //FIXME clean this shit up + GFF4Element *fErrorLocator, *errorLocator, *omega, *syn, *psi; - syn= omegas[1]; - - /* kill erased symbols */ - for(i=0; i<erasureCount; i++){ + syn= omegas[1]; + + /* kill erased symbols */ + for(i=0; i<erasureCount; i++){ //printf("%d\n", erasure[i]); - data[ erasure[i] ]=0; - } + data[ erasure[i] ]=0; + } - noe_getSyndrom(syn, data, 1, parityCount); - for(i=1; i<=parityCount; i++){ - if(syn[i]) break; - } - if(i>parityCount) - return 0; + noe_getSyndrom(syn, data, parityCount); + for(i=1; i<=parityCount; i++){ + if(syn[i]) break; + } + if(i>parityCount) + return 0; - phantomErrorCount=0; - //FIXME check truncated symbols syndrom + phantomErrorCount=0; + //FIXME check truncated symbols syndrom - for(i=0; i<erasureCount; i++){ - erasureSynthSrc[2*i + 0] = 1; - erasureSynthSrc[2*i + 1] = SIZE - noe_exp[erasure[i]]; - } - noe_synthPoly(erasureLocator, erasureSynthSrc, erasureCount); -// noe_printPoly(erasureLocator, erasureCount); + for(i=0; i<erasureCount; i++){ + erasureSynthSrc[2*i + 0] = 1; + erasureSynthSrc[2*i + 1] = SIZE - noe_exp[erasure[i]]; + } + noe_synthPoly(erasureLocator, erasureSynthSrc, erasureCount); +// noe_printPoly(erasureLocator, erasureCount); #if 0 for(i=0; i<erasureCount; i++){ - int eval= noe_evalPoly(erasureLocator, erasureCount, inv(noe_exp[erasure[i]])); - assert( eval==0); + int eval= noe_evalPoly(erasureLocator, erasureCount, inv(noe_exp[erasure[i]])); + assert( eval==0); } #endif - noe_partialProdPoly(syn, erasureLocator, syn, erasureCount, parityCount); + noe_partialProdPoly(syn, erasureLocator, syn, erasureCount, parityCount); - i= noe_rsEuclid(locators, omegas, parityCount, erasureCount, &errorCount, &omegaOrder); + i= noe_rsEuclid(locators, omegas, parityCount, erasureCount, &errorCount, &omegaOrder); //printf("errorCount %d \n", errorCount); - if(i<0) return -1; + if(i<0) return -1; - omega= omegas[i]; - errorLocator= locators[i]; - fErrorLocator= omegas[1-i]; //reuse some unused space - psi= locators[1-i]; //reuse some unused space + omega= omegas[i]; + errorLocator= locators[i]; + fErrorLocator= omegas[1-i]; //reuse some unused space + psi= locators[1-i]; //reuse some unused space - gfftEval= errorCount>20; - if(gfftEval && errorCount){ - memcpy(fErrorLocator, errorLocator, (errorCount+1)*sizeof(GFF4Element)); - memset(fErrorLocator + errorCount+1, 0, (SIZE - errorCount-2)*sizeof(GFF4Element)); - noe_gfft(fErrorLocator, fErrorLocator, 16); - } + gfftEval= errorCount>20; + if(gfftEval && errorCount){ + memcpy(fErrorLocator, errorLocator, (errorCount+1)*sizeof(GFF4Element)); + memset(fErrorLocator + errorCount+1, 0, (SIZE - errorCount-2)*sizeof(GFF4Element)); + noe_gfft(fErrorLocator, fErrorLocator, 16); + } - psiOrder= noe_prodPoly(psi, errorLocator, erasureLocator, errorCount, erasureCount); - psiOrder= noe_getDerivative(psi, psi, psiOrder); + psiOrder= noe_prodPoly(psi, errorLocator, erasureLocator, errorCount, erasureCount); + psiOrder= noe_getDerivative(psi, psi, psiOrder); - if(errorCount){ - for(i=0; i<SIZE-1; i++){ - int r, e; - GFF4Element X, invX, nom, denom; + if(errorCount){ + for(i=0; i<SIZE-1; i++){ + int r, e; + GFF4Element X, invX, nom, denom; - if(gfftEval){ //FIXME optimize - if(fErrorLocator[i]) - continue; - - r= (- noe_bitReverse(i))&0xFFFF; - }else{ - if(noe_evalPoly(errorLocator, errorCount, noe_exp[i])) - continue; - - r= (-i)&0xFFFF; - } + if(gfftEval){ //FIXME optimize + if(fErrorLocator[i]) + continue; + + r= (- noe_bitReverse(i))&0xFFFF; + }else{ + if(noe_evalPoly(errorLocator, errorCount, noe_exp[i])) + continue; + + r= (-i)&0xFFFF; + } //printf("E%6d %6d\n", i, r); - X = noe_exp[r]; - invX= noe_exp[SIZE - r - 1]; - nom= prod(X, noe_evalPoly(omega, omegaOrder, invX)); - denom= noe_evalPoly(psi, psiOrder, invX); + X = noe_exp[r]; + invX= noe_exp[SIZE - r - 1]; + nom= prod(X, noe_evalPoly(omega, omegaOrder, invX)); + denom= noe_evalPoly(psi, psiOrder, invX); - assert(r>=0 && r<=SIZE-2); - e= prod(nom, inv(denom)); - if(data[r]==0 && e==0x10000){ - if(r < dataCount) - return -1; - else - phantomErrorCount++; - } - data[r]= sum(data[r], e); - } - } + assert(r>=0 && r<=SIZE-2); + e= prod(nom, inv(denom)); + if(data[r]==0 && e==0x10000){ + if(r < dataCount) + return -1; + else + phantomErrorCount++; + } + data[r]= sum(data[r], e); + } + } - for(i=0; i<erasureCount; i++){ - const int r= erasure[i]; - const GFF4Element X = noe_exp[r]; - const GFF4Element invX= noe_exp[SIZE - r - 1]; - GFF4Element nom, denom; + for(i=0; i<erasureCount; i++){ + const int r= erasure[i]; + const GFF4Element X = noe_exp[r]; + const GFF4Element invX= noe_exp[SIZE - r - 1]; + GFF4Element nom, denom; - assert(r>=0 && r<0x10000); - assert(prod(X, invX)==1); - - nom= prod(X, noe_evalPoly(omega, omegaOrder, invX)); - denom= noe_evalPoly(psi, psiOrder, invX); + assert(r>=0 && r<0x10000); + assert(prod(X, invX)==1); + + nom= prod(X, noe_evalPoly(omega, omegaOrder, invX)); + denom= noe_evalPoly(psi, psiOrder, invX); - assert(data[r]==0); - data[r]= prod(nom, inv(denom)); - } + assert(data[r]==0); + data[r]= prod(nom, inv(denom)); + } - return erasureCount + errorCount - phantomErrorCount; + return erasureCount + errorCount - phantomErrorCount; } Modified: trunk/noe/rs.h ============================================================================== --- trunk/noe/rs.h (original) +++ trunk/noe/rs.h Tue Jul 10 00:37:39 2007 @@ -17,9 +17,9 @@ */ typedef struct noe_RsEncoder{ - int parityCount; - GFF4Element *parityLocator; - GFF4Element *parityFactor; + int parityCount; + GFF4Element *parityLocator; + GFF4Element *parityFactor; }noe_RsEncoder; void noe_getRsGenerator(GFF4Element *dst, int first, int order); @@ -29,7 +29,7 @@ void noe_getRsGenerator(GFF4Element *dst * @param src a 2^16 entry long polynom * @param syn the syndrom polynom will be stored here */ -void noe_getSyndrom(GFF4Element *syn, GFF4Element *src, int first, int order); +void noe_getSyndrom(GFF4Element *syn, GFF4Element *src, int order); noe_RsEncoder *noe_getRsEncoder(int parityOrder); void noe_freeRsEncoder(noe_RsEncoder *encoder); Modified: trunk/noe/rw.c ============================================================================== --- trunk/noe/rw.c (original) +++ trunk/noe/rw.c Tue Jul 10 00:37:39 2007 @@ -19,65 +19,107 @@ #include <inttypes.h> #include <stdlib.h> #include <string.h> +#include <assert.h> #include "rw.h" typedef struct noe_RemapRwContext{ - noe_RwContext rw; - noe_Map *map; - int count; + noe_RwContext rw; + noe_Map *map; + int count; }noe_RemapRwContext; static int remapIO(noe_RwContext *c, uint8_t *data, uint64_t pos, int len, int write){ - int i; - noe_RemapRwContext * const p= (noe_RemapRwContext *)c; - noe_RwContext *parent= c->parent; + int i; + noe_RemapRwContext * const p= (noe_RemapRwContext *)c; + noe_RwContext *parent= c->parent; - //FIXME do binary search or cache last + //FIXME do binary search or cache last - for(i=0; i<p->count; i++){ - if(pos < p->map[i].src + p->map[i].len){ - const uint64_t diff= p->map[i].dst - p->map[i].src; - uint64_t currentLen= p->map[i].src + p->map[i].len - pos; - if(currentLen > len) currentLen= len; + for(i=0; i<p->count; i++){ + if(pos < p->map[i].src + p->map[i].len){ + const uint64_t diff= p->map[i].dst - p->map[i].src; + uint64_t currentLen= p->map[i].src + p->map[i].len - pos; + if(currentLen > len) currentLen= len; - parent->io(parent, data, pos + diff, currentLen, write); - - data+= currentLen; - pos+= currentLen; - len-= currentLen; - if(len == 0) return 0; - } - } + parent->io(parent, data, pos + diff, currentLen, write); + + data+= currentLen; + pos+= currentLen; + len-= currentLen; + if(len == 0) return 0; + } + } - return -1; + return -1; } static void remapUninit(noe_RwContext *c){ - noe_RemapRwContext * const p= (noe_RemapRwContext *)c; + noe_RemapRwContext * const p= (noe_RemapRwContext *)c; - if(c==NULL) return; + if(c==NULL) return; - free(p->map); - memset(p, 0, sizeof(noe_RemapRwContext)); - free(p); + free(p->map); + memset(p, 0, sizeof(noe_RemapRwContext)); + free(p); } noe_RwContext *noe_getRemapRwContext(noe_RwContext *parent, noe_Map *map, int count){ - noe_RemapRwContext *p= malloc(sizeof(noe_RemapRwContext)); - noe_RwContext *c= (noe_RwContext*)p; + noe_RemapRwContext *p= malloc(sizeof(noe_RemapRwContext)); + noe_RwContext *c= (noe_RwContext*)p; - c->parent= parent; + c->parent= parent; - p->map= malloc(sizeof(noe_Map)*count); - memcpy(p->map, map, sizeof(noe_Map)*count); - p->count= count; - - //FIXME sort map + p->map= malloc(sizeof(noe_Map)*count); + memcpy(p->map, map, sizeof(noe_Map)*count); + p->count= count; + + //FIXME sort map - c->io= remapIO; - c->uninit= remapUninit; + c->io= remapIO; + c->uninit= remapUninit; - return c; + return c; +} + +static void update_buf(noe_RwContext *c, uint64_t pos, int len){ + assert(len>0 && len<=64); +// assert(pos < 8*c->size); + + if(pos<8*c->pos || pos + len > 8*c->pos + 8*RW_SIZE){ + if(c->flush){ + c->io(c, c->buffer, c->pos, RW_SIZE, 1); + c->flush=0; + } + c->pos= pos/8 - RW_SIZE/2; + if(c->pos<0) c->pos=0; + //FIXME memmove the old to avoid redundant io + c->io(c, c->buffer, c->pos, RW_SIZE, 0); + } +} + +uint64_t noe_read(noe_RwContext *c, uint64_t pos, int len){ + int i; + uint64_t v=0; + + update_buf(c, pos, len); + + for(i=0; i<len; i++){ + v += v + (c->buffer[(pos+i)/8 - c->pos] >> (8-((pos+i)&7))); + } + return v; +} + +void noe_write(noe_RwContext *c, uint64_t pos, int len, uint64_t v){ + int i; + + update_buf(c, pos, len); + + for(i=0; i<len; i++){ + int bit= (v>>(len-i))&1; + c->buffer[(pos+i)/8 - c->pos] &= ~(1 <<(8-((pos+i)&7))); + c->buffer[(pos+i)/8 - c->pos] |= (bit<<(8-((pos+i)&7))); + } + c->flush=1; } Modified: trunk/noe/rw.h ============================================================================== --- trunk/noe/rw.h (original) +++ trunk/noe/rw.h Tue Jul 10 00:37:39 2007 @@ -15,23 +15,30 @@ * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ - + +#define RW_SIZE (1<<18) + typedef struct noe_RwContext{ - uint64_t size; + uint8_t buffer[RW_SIZE]; + uint64_t pos; + int flush; + uint64_t size; - /** - * reads or writes some data. - * @returns <0 if an error occured - */ - int (*io )(struct noe_RwContext *context, uint8_t *data, uint64_t pos, int len, int write); + /** + * reads or writes some data. + * @returns <0 if an error occured + */ + int (*io )(struct noe_RwContext *context, uint8_t *data, uint64_t pos, int len, int write); - void (*uninit)(struct noe_RwContext *context); - struct noe_RwContext *parent; + void (*uninit)(struct noe_RwContext *context); + struct noe_RwContext *parent; }noe_RwContext; typedef struct noe_Map{ - uint64_t src; - uint64_t dst; - uint64_t len; + uint64_t src; + uint64_t dst; + uint64_t len; }noe_Map; +uint64_t noe_read(noe_RwContext *c, uint64_t pos, int len); +void noe_write(noe_RwContext *c, uint64_t pos, int len, uint64_t v); Modified: trunk/noe/test.c ============================================================================== --- trunk/noe/test.c (original) +++ trunk/noe/test.c Tue Jul 10 00:37:39 2007 @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003 Michael Niedermayer <michaelni@gmx.at> + * Copyright (C) 2002 Michael Niedermayer <michaelni@gmx.at> * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -52,280 +52,281 @@ static const unsigned int gfftChecksums[ }; int main(){ - int i, j; - GFF4Element bp=1; + int i, j; + GFF4Element bp=1; - noe_init(); + noe_init(); - printf("Testing GF(65537)\n"); - for(i=0; i<SIZE-1; i++){ - if((bp==1 || bp==0) && i>0){ - printf("FAIL %d %d\n", i, bp); - break; - } - bp= prod(bp, PRIMITIVE_ELEMENT); - } - if(bp!=1) printf("FAILED to reach 1\n"); - - printf("Testing inverse\n"); - bp=1; - for(i=1; i<SIZE; i++){ - if(prod(bp, inv(bp)) != 1){ - printf("FAIL %X %X\n", (int)bp, (int)inv(bp)); - break; - } - bp= prod(bp, PRIMITIVE_ELEMENT); - } + printf("Testing GF(65537)\n"); + for(i=0; i<SIZE-1; i++){ + if((bp==1 || bp==0) && i>0){ + printf("FAIL %d %d\n", i, bp); + break; + } + bp= prod(bp, PRIMITIVE_ELEMENT); + } + if(bp!=1) printf("FAILED to reach 1\n"); + + printf("Testing inverse\n"); + bp=1; + for(i=1; i<SIZE; i++){ + if(prod(bp, inv(bp)) != 1){ + printf("FAIL %X %X\n", (int)bp, (int)inv(bp)); + break; + } + bp= prod(bp, PRIMITIVE_ELEMENT); + } #if 0 - printf("Experiment"); - for(i=0; i<(1<<30); i++){ - unsigned int a= reduce(i*0xFF01); - unsigned int b= reduce(reduce(i)*0xFF01); - - if(a!=b) printf("%X %X %X %X\n", i, reduce(i), i*0xFF01, reduce(i)*0xFF01); - } + printf("Experiment"); + for(i=0; i<(1<<30); i++){ + unsigned int a= reduce(i*0xFF01); + unsigned int b= reduce(reduce(i)*0xFF01); + + if(a!=b) printf("%X %X %X %X\n", i, reduce(i), i*0xFF01, reduce(i)*0xFF01); + } #endif - srand (31415); + srand (31415); - printf("Testing GFFT"); - for(i=1; i<20; i++){ - int n= SIZE - 1; - GFF4Element syn[n]; - GFF4Element code[n]; - int acc=0; - - for(j=0; j<n; j++) - code[j]= rand() % 0x10001; + printf("Testing GFFT"); + for(i=1; i<20; i++){ + int n= SIZE - 1; + GFF4Element syn[n]; + GFF4Element code[n]; + int acc=0; + + for(j=0; j<n; j++) + code[j]= rand() % 0x10001; - noe_gfft(syn, code, 16); - - for(j=0; j<n; j++){ - acc+= syn[j]; - acc*=2*j+1; - } - if(gfftChecksums[i-1] != acc) - printf("FAIL: 0x%08X != 0x%08X\n", gfftChecksums[i-1], acc); - - noe_igfft(syn, syn, 16); - for(j=0; j<n; j++){ - syn[j]= prod(syn[j], inv(1<<16)); - } - - for(j=0; j<n; j++){ - if(syn[j] != code[j]) printf("IGFFT missmatch at %d %X!=%X\n", j, syn[j], code[j]); - } - -// noe_printPoly(gen, i); -// noe_printPoly(syn, i-1); - - printf("."); fflush(stdout); - } - - srand (31415); + noe_gfft(syn, code, 16); + + for(j=0; j<n; j++){ + acc+= syn[j]; + acc*=2*j+1; + } + if(gfftChecksums[i-1] != acc) + printf("FAIL: 0x%08X != 0x%08X\n", gfftChecksums[i-1], acc); + + noe_igfft(syn, syn, 16); + for(j=0; j<n; j++){ + syn[j]= prod(syn[j], inv(1<<16)); + } + + for(j=0; j<n; j++){ + if(syn[j] != code[j]) printf("IGFFT missmatch at %d %X!=%X\n", j, syn[j], code[j]); + } + +// noe_printPoly(gen, i); +// noe_printPoly(syn, i-1); + + printf("."); fflush(stdout); + } + + srand (31415); - printf("\nTesting generator polynoms"); - for(i=1; i<100; i+=5){ - int n= SIZE - 1; - int k= SIZE - 1 - i; - GFF4Element syn[n]; - GFF4Element gen[i+1]; - GFF4Element data[k]; - GFF4Element code[n]; - - for(j=0; j<k; j++) - data[j]= rand() & 0xFFFF; - - noe_getRsGenerator(gen, 1, i); - j=noe_prodPoly(code, gen, data, i, k-1); - assert(j==n-1); - - noe_getSyndrom(syn, code, 1, i); - -// noe_printPoly(gen, i); -// noe_printPoly(syn, i-1); - - for(j=0; j<i; j++){ - if(syn[j+1]) printf("FAIL generator:%d coefficient:%d\n", i, j); - } - printf("."); fflush(stdout); - } + printf("\nTesting generator polynoms"); + for(i=1; i<100; i+=5){ + int n= SIZE - 1; + int k= SIZE - 1 - i; + GFF4Element syn[n]; + GFF4Element gen[i+1]; + GFF4Element data[k]; + GFF4Element code[n]; + + for(j=0; j<k; j++) + data[j]= rand() & 0xFFFF; + + noe_getRsGenerator(gen, 1, i); + j=noe_prodPoly(code, gen, data, i, k-1); + assert(j==n-1); + + noe_getSyndrom(syn, code, i); + +// noe_printPoly(gen, i); +// noe_printPoly(syn, i-1); + + for(j=0; j<i; j++){ + if(syn[j+1]) printf("FAIL generator:%d coefficient:%d\n", i, j); + } + printf("."); fflush(stdout); + } - printf("\nTesting encoder"); - for(i=1; i<1000; i+=200){ - int n= SIZE - 1; - int k= SIZE - 1 - i; - GFF4Element syn[n]; -// GFF4Element gen[i+1]; - GFF4Element data[k]; - GFF4Element code[n]; - noe_RsEncoder *encoder; - int pass=5; + printf("\nTesting encoder"); + for(i=1; i<1000; i+=200){ + int n= SIZE - 1; + int k= SIZE - 1 - i; + GFF4Element syn[n]; +// GFF4Element gen[i+1]; + GFF4Element data[k]; + GFF4Element code[n]; + noe_RsEncoder *encoder; + int pass=5; - encoder= noe_getRsEncoder(i); + encoder= noe_getRsEncoder(i); - for(pass=5; pass; pass--){ - for(j=0; j<k; j++) - data[j]= rand() & 0xFFFF; + for(pass=5; pass; pass--){ + for(j=0; j<k; j++) + data[j]= rand() & 0xFFFF; - memcpy(code, data, n*sizeof(GFF4Element)); + memcpy(code, data, n*sizeof(GFF4Element)); - noe_rsEncode(encoder, code); + noe_rsEncode(encoder, code); - noe_getSyndrom(syn, code, 1, i); - //FIXME check that code contains data, but its not touched so ... + noe_getSyndrom(syn, code, i); + //FIXME check that code contains data, but its not touched so ... - // noe_printPoly(gen, i); - // noe_printPoly(syn, i-1); + // noe_printPoly(gen, i); + // noe_printPoly(syn, i-1); - for(j=0; j<i; j++){ - if(syn[j+1]) printf("FAIL generator:%d coefficient:%d is %X\n", i, j, syn[j+1]); - } - printf("."); fflush(stdout); - } - noe_freeRsEncoder(encoder); - } - - printf("\nTesting decoder"); - for(i=1; i<2000; i+=100){ - int n= SIZE - 1; - int k= SIZE - 1 - i; -// GFF4Element syn[n]; - GFF4Element erased[i]; - GFF4Element data[k]; - GFF4Element code[n]; - noe_RsEncoder *encoder; - int pass=5; + for(j=0; j<i; j++){ + if(syn[j+1]) printf("FAIL generator:%d coefficient:%d is %X\n", i, j, syn[j+1]); + } + printf("."); fflush(stdout); + } + noe_freeRsEncoder(encoder); + } + + printf("\nTesting decoder"); + for(i=1; i<2000; i+=100){ + int n= SIZE - 1; + int k= SIZE - 1 - i; +// GFF4Element syn[n]; + GFF4Element erased[i]; + GFF4Element data[k]; + GFF4Element code[n]; + noe_RsEncoder *encoder; + int pass=5; - encoder= noe_getRsEncoder(i); + encoder= noe_getRsEncoder(i); - for(pass=5; pass; pass--){ - int erasedCount, errorCount; - for(j=0; j<k; j++) - data[j]= rand() & 0xFFFF; + for(pass=5; pass; pass--){ + int erasedCount, errorCount; + for(j=0; j<k; j++) + data[j]= rand() & 0xFFFF; - memcpy(code, data, n*sizeof(GFF4Element)); + memcpy(code, data, n*sizeof(GFF4Element)); - noe_rsEncode(encoder, code); - - erasedCount=0; - if(rand()&0x40){ - erasedCount= (rand()%i)+1; - for(j=0; j<erasedCount; j++){ - int e=-1; - - while(e==-1 || code[e]==0x10000) e=rand()%n; + noe_rsEncode(encoder, code); + + erasedCount=0; + if(rand()&0x40){ + erasedCount= (rand()%i)+1; + for(j=0; j<erasedCount; j++){ + int e=-1; + + while(e==-1 || code[e]==0x10000) e=rand()%n; - erased[j]= e; - code[ e ]= 0x10000; - } - for(j=0; j<erasedCount; j++){ - int e= erased[j]; + erased[j]= e; + code[ e ]= 0x10000; + } + for(j=0; j<erasedCount; j++){ + int e= erased[j]; - code[ e ]= rand()%0xFFFF; - } - } - errorCount=0; - if(erasedCount==0 || (rand()&0x40)){ - int max= (i - erasedCount)/2; - if(max){ - errorCount= (rand() % max)+1; - for(j=0; j<errorCount; j++){ - int pos= rand()%n; - code[pos] = rand()%0xFFFF; -// printf("P%6d\n", pos); - } - } - } + code[ e ]= rand()%0xFFFF; + } + } + errorCount=0; + if(erasedCount==0 || (rand()&0x40)){ + int max= (i - erasedCount)/2; + if(max){ + errorCount= (rand() % max)+1; + for(j=0; j<errorCount; j++){ + int pos= rand()%n; + code[pos] = rand()%0xFFFF; +// printf("P%6d\n", pos); + } + } + } //printf("erased:%d errors:%d parity:%d\n", erasedCount, errorCount, i); - noe_rsDecode(code, erased, erasedCount, i); + noe_rsDecode(code, erased, erasedCount, i); - // noe_printPoly(gen, i); - // noe_printPoly(syn, i-1); + // noe_printPoly(gen, i); + // noe_printPoly(syn, i-1); - for(j=0; j<k; j++){ - if(data[j]!=code[j]){ - printf("FAIL at:%d is %X %X\n", j, data[j], code[j]); - break; - } - } - printf("."); fflush(stdout); - } - noe_freeRsEncoder(encoder); - } - { - uint8_t buffer[20000]; - uint32_t val[2000]; - ByteStream bs; + for(j=0; j<k; j++){ + if(data[j]!=code[j]){ + printf("FAIL at:%d is %X %X\n", j, data[j], code[j]); + break; + } + } + printf("."); fflush(stdout); + } + noe_freeRsEncoder(encoder); + } +#if 0 + { + uint8_t buffer[20000]; + uint32_t val[2000]; + ByteStream bs; - printf("\nTesting v coder"); - - initByteStream(&bs, buffer, 20000); - for(i=0; i<2000; i++){ - int len= rand()%32; - val[i] = rand() % (1<<len); - put_v(&bs, val[i]); - if(i%100 == 0) printf("."); - } + printf("\nTesting v coder"); + + initByteStream(&bs, buffer, 20000); + for(i=0; i<2000; i++){ + int len= rand()%32; + val[i] = rand() % (1<<len); + put_v(&bs, val[i]); + if(i%100 == 0) printf("."); + } - initByteStream(&bs, buffer, 20000); - for(i=0; i<2000; i++){ - if(val[i] != get_v(&bs)){ - printf("FAIL\n"); - break; - } - if(i%100 == 0) printf("."); - } - } - - printf("\n"); + initByteStream(&bs, buffer, 20000); + for(i=0; i<2000; i++){ + if(val[i] != get_v(&bs)){ + printf("FAIL\n"); + break; + } + if(i%100 == 0) printf("."); + } + } +#endif + printf("\n"); return 0; - - printf("Testing erasure decoding\n"); - for(i=1; i<20; i++){ - int n= SIZE - 1; - int k= SIZE - 1 - i; - GFF4Element syn[n]; - GFF4Element gen[i+1]; - GFF4Element data[k]; - GFF4Element code[n]; - GFF4Element locator[i+1]; - GFF4Element omega[2*i]; + + printf("Testing erasure decoding\n"); + for(i=1; i<20; i++){ + int n= SIZE - 1; + int k= SIZE - 1 - i; + GFF4Element syn[n]; + GFF4Element gen[i+1]; + GFF4Element data[k]; + GFF4Element code[n]; + GFF4Element locator[i+1]; + GFF4Element omega[2*i]; - int locatorOrder=0; - - for(j=0; j<k; j++) - data[j]= rand() & 0xFFFF; - - noe_getRsGenerator(gen, 1, i); - j=noe_prodPoly(code, gen, data, i, k); - assert(j==n); - - locator[0] = 1; - for(j=0; j<i; j++){ - int index; - GFF4Element locationFactor[2]; - - if((rand()&7)==0 && j) continue; - - index= rand()%0xFFFF; - locationFactor[0] = 1; - locationFactor[1] = inv(noe_exp[index]); - locatorOrder= noe_prodPoly(locator, locator, locationFactor, j, 1); - - code[index] += rand()&0xFFFF; - } - - noe_getSyndrom(syn, code, 1, i); - noe_prodPoly(omega, syn, locator, i-1, locatorOrder); -// noe_getDeriative(locator, locator, locatorOrder); - + int locatorOrder=0; + + for(j=0; j<k; j++) + data[j]= rand() & 0xFFFF; + + noe_getRsGenerator(gen, 1, i); + j=noe_prodPoly(code, gen, data, i, k); + assert(j==n); + + locator[0] = 1; + for(j=0; j<i; j++){ + int index; + GFF4Element locationFactor[2]; + + if((rand()&7)==0 && j) continue; + + index= rand()%0xFFFF; + locationFactor[0] = 1; + locationFactor[1] = inv(noe_exp[index]); + locatorOrder= noe_prodPoly(locator, locator, locationFactor, j, 1); + + code[index] = 0; + } + + noe_getSyndrom(syn, code, i); + noe_prodPoly(omega, syn, locator, i-1, locatorOrder); +// noe_getDeriative(locator, locator, locatorOrder); + -// noe_printPoly(gen, i); -// noe_printPoly(syn, i-1); - - for(j=0; j<i; j++){ - if(syn[j]) printf("FAIL generator:%d coefficient:%d\n", i, j); - } - } - return 0; +// noe_printPoly(gen, i); +// noe_printPoly(syn, i-1); + + for(j=0; j<i; j++){ + if(syn[j]) printf("FAIL generator:%d coefficient:%d\n", i, j); + } + } + return 0; }
participants (1)
-
michael