[MN-dev] [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
michael
subversion at mplayerhq.hu
Tue Jul 10 00:37:40 CEST 2007
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 at gmx.at>
+ * Copyright (C) 2003-2005 Michael Niedermayer <michaelni at 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 at gmx.at>
+ * Copyright (C) 2003-2005 Michael Niedermayer <michaelni at 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 at gmx.at>
+ * Copyright (C) 2002 Michael Niedermayer <michaelni at 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 at gmx.at>
+ * Copyright (C) 2002 Michael Niedermayer <michaelni at 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 at gmx.at>
+ * Copyright (C) 2003-2005 Michael Niedermayer <michaelni at 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 at gmx.at>
+ * Copyright (C) 2002 Michael Niedermayer <michaelni at 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 at gmx.at>
+ * Copyright (C) 2002 Michael Niedermayer <michaelni at 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 at gmx.at>
+ * Copyright (C) 2002 Michael Niedermayer <michaelni at 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;
}
More information about the Mndiff-dev
mailing list