June 2007 - Mndiff-dev - lists.mplayerhq.hu

[Mndiff-dev] [PATCH] mnzip: cosmetic patch for r37 changes
by Corey Hickey 21 Jun '07

21 Jun '07

As promised. -Corey Index: mnzip.c =================================================================== --- mnzip.c (revision 38) +++ mnzip.c (working copy) @@ -870,17 +870,17 @@ static const uint8_t header[7]={'M','N','Z','I','P',0,0}; if (argc > 1) { - for(i=0; argv[1][i]; i++){ - switch(argv[1][i]){ - case 'c' : comp=1 ; break; - case 'd' : comp=0 ; break; - case 'l' : low_mem =1 ; break; - case '0' ... '9': block_size= 1<<(argv[1][i]-'0'+20); break; - case '-' : break; - default : help() ; + for(i=0; argv[1][i]; i++){ + switch(argv[1][i]){ + case 'c' : comp=1 ; break; + case 'd' : comp=0 ; break; + case 'l' : low_mem =1 ; break; + case '0' ... '9': block_size= 1<<(argv[1][i]-'0'+20); break; + case '-' : break; + default : help() ; + } } } - } if (argc < 3 || !strcmp(argv[2], "-")) fi = stdin;

2 2

[Mndiff-dev] [mndiff]: r42 - trunk/mnzip/mnzip.c
by michael 21 Jun '07

21 Jun '07

Author: michael Date: Thu Jun 21 20:37:02 2007 New Revision: 42 Log: reuse begin of idx2 to improve cache useage and swaping if not enough memory Modified: trunk/mnzip/mnzip.c Modified: trunk/mnzip/mnzip.c ============================================================================== --- trunk/mnzip/mnzip.c (original) +++ trunk/mnzip/mnzip.c Thu Jun 21 20:37:02 2007 @@ -365,16 +365,16 @@ fprintf(stderr, "idx init done\n"); #define limit(i) ((i)>=len ? (i) - len : (i)) assert(right-(int)i+1 > 1); for(j=i; j<=right; j++){ - idx2[j]= idx[limit(ptr[j] - in + sorted)]; + idx2[j-i]= idx[limit(ptr[j] - in + sorted)]; // assert(idx[ptr[j] - in] == idx[ptr[i] - in]); } - qsort2(ptr + i, idx2 + i, right-i+1); + qsort2(ptr + i, idx2, right-i+1); last= right; assert(idx[ptr[right]-in] == right); last2= right+1; for(j=right-1; (int)j>=(int)i; j--){ - if(idx2[j] < idx2[j+1]){ + if(idx2[j-i] < idx2[j-i+1]){ assert(last - j >= 1); if(last - j > 1){ last2= j+1;

1 0

[Mndiff-dev] [mndiff]: r41 - trunk/mnzip/mnzip.c
by michael 21 Jun '07

21 Jun '07

Author: michael Date: Thu Jun 21 18:23:05 2007 New Revision: 41 Log: get rid of the bentley sedgewick bwt, this thing has a too creepy worst case behavior even under #if 0 ;) Modified: trunk/mnzip/mnzip.c Modified: trunk/mnzip/mnzip.c ============================================================================== --- trunk/mnzip/mnzip.c (original) +++ trunk/mnzip/mnzip.c Thu Jun 21 18:23:05 2007 @@ -268,53 +268,6 @@ static void qsort2(uint8_t **ptr, int *i #define read(p) ((p)>=end ? (p)[in - end] : *(p)) -static void bssort(const uint8_t **p, int len, int skip, uint8_t *in, uint8_t *end){ - int pivot; - int i=0; - int j=0; - int k=len-1; - - assert(len>1); - -retry: - pivot= read(p[len>>1] + skip); - for(i=0; i<len; i++) - if(read(p[i]+skip) != pivot) - break; - if(i==len){ - skip++; - goto retry; - } - - i=0; - while(j<=k){ - uint8_t *pj= p[j]; - int v= read(pj + skip); - if(v == pivot) - j++; - else if(v<pivot){ - p[j]= p[i]; p[i]= pj; - j++; - i++; - }else{ - p[j]= p[k]; p[k]= pj; - do{ - k--; - }while(read(p[k] + skip) > pivot); - } - } - assert(i>=0); - assert(i<=j); - assert(j<=k+1); - assert(k<=len-1); - if(i>1) - bssort(p , i , skip , in, end); - if(j-i>1) - bssort(p+i, j-i , skip+1, in, end); - if(len-k>2) - bssort(p+j, len-1-k, skip , in, end); -} - static unsigned int bwt(uint8_t *out, uint8_t *in, unsigned int len){ unsigned int i, j, ret; uint8_t **ptr = malloc(len*sizeof(uint8_t*)); @@ -361,7 +314,7 @@ static unsigned int bwt(uint8_t *out, ui ptr[ histogram[ptr2[i][1]]++ ]= ptr2[i]; } fprintf(stderr, "radix sort done\n"); -#if 1 + idx2= malloc(len*sizeof(int)); for(i=len-1; (int)i>=0; i--){ if(ptr[last][1] != ptr[i][1] || ptr[last][2] != ptr[i][2] || @@ -444,17 +397,6 @@ fprintf(stderr, "idx init done\n"); out[idx[i]]= in[i]; } ret= idx[0]; -#else - for(i=1; i<len; i++){ - if(memcmp(ptr[last]+1, ptr[i]+1, RADIX_PASSES)){ - if(i-last>1) - bssort(ptr + last, i-last, RADIX_PASSES+1, in, in+len); - last= i; - } - } - if(i-last>1) - bssort(ptr + last, i-last, RADIX_PASSES+1, in, in+len); -#endif free(ptr); free(ptr2);

1 0

[Mndiff-dev] [mndiff]: r40 - trunk/mnzip/mnzip.c
by michael 21 Jun '07

21 Jun '07

Author: michael Date: Thu Jun 21 18:09:58 2007 New Revision: 40 Log: move sorted sizes into unused parts of the existing arrays ~25% less memory needed for compression sadly ~3% slower and its not clear why Modified: trunk/mnzip/mnzip.c Modified: trunk/mnzip/mnzip.c ============================================================================== --- trunk/mnzip/mnzip.c (original) +++ trunk/mnzip/mnzip.c Thu Jun 21 18:09:58 2007 @@ -320,11 +320,11 @@ static unsigned int bwt(uint8_t *out, ui uint8_t **ptr = malloc(len*sizeof(uint8_t*)); uint8_t **ptr2= malloc(len*sizeof(uint8_t*)); int histogram[257]; - int last= 0; + int last= len-1; + int last2= len; int sorted; int *idx= ptr2; - int *siz1, *siz2, *idx2; - int siz1i=0; + int *idx2; if(!ptr || !ptr2 || len >= UINT_MAX / sizeof(uint8_t*)) //FIXME memleak return -1; @@ -362,57 +362,88 @@ static unsigned int bwt(uint8_t *out, ui } fprintf(stderr, "radix sort done\n"); #if 1 - siz1= malloc((len+3)/2*sizeof(int)); - siz2= malloc((len+3)/2*sizeof(int)); idx2= malloc(len*sizeof(int)); -assert(last==0); - for(i=0; i<len; i++){ + for(i=len-1; (int)i>=0; i--){ if(ptr[last][1] != ptr[i][1] || ptr[last][2] != ptr[i][2] || ptr[last][3] != ptr[i][3] || ptr[last][4] != ptr[i][4]){ - if(i-last>1) - siz1[siz1i++]= i; + + if(last - i > 1) + last2= i+1; + else{ + ptr[last]= in-last2; + assert(in - ptr[last] > last); + assert(last2 <= len); + } + last= i; } idx[ptr[i]-in]= last; } - if(i-last>1) - siz1[siz1i++]= i; - siz1[siz1i++]= 0; + + if(last - i == 1){ + ptr[last]= in-last2; + assert(in - ptr[last] > last); + } + fprintf(stderr, "idx init done\n"); for(sorted=RADIX_PASSES; sorted<len; sorted<<=1){ - int last=0; - int siz1i=0; - int siz2i=0; +//fprintf(stderr, "pass %d\n", sorted); + + i=0; for(;;){ - int i= siz1[siz1i++]; - if(!i) + int right; +// assert(i < len+1); +// assert(i>=0); + + if(i >= len) break; - last= idx[ptr[i-1]-in]; + + if(ptr[i] - in < 0){ + int openlink= i; + do{ + i = in - ptr[i]; + }while(i < len && ptr[i] - in < 0); + ptr[openlink]= in - i; + if(i >= len) + break; + } + + right= idx[ptr[i]-in]; #define limit(i) ((i)>=len ? (i) - len : (i)) - for(j=last; j<i; j++) + assert(right-(int)i+1 > 1); + for(j=i; j<=right; j++){ idx2[j]= idx[limit(ptr[j] - in + sorted)]; - qsort2(ptr + last, idx2 + last, i-last); - for(j=last+1; j<i; j++){ - if(idx2[j-1] < idx2[j]){ - if(j-last>1) - siz2[siz2i++]= j; - last= j; - } +// assert(idx[ptr[j] - in] == idx[ptr[i] - in]); + } + qsort2(ptr + i, idx2 + i, right-i+1); - assert(idx[ptr[j]-in] <= last); + last= right; + assert(idx[ptr[right]-in] == right); + last2= right+1; + for(j=right-1; (int)j>=(int)i; j--){ + if(idx2[j] < idx2[j+1]){ + assert(last - j >= 1); + if(last - j > 1){ + last2= j+1; + }else{ + ptr[last]= in - last2; + } + last=j; + } +// assert(ptr[j]-in >= 0); + assert(idx[ptr[j]-in] >= last); idx[ptr[j]-in]= last; } - if(j-idx[ptr[j-1]-in]>1) - siz2[siz2i++]= j; + if(last - j == 1) + ptr[last]= in - last2; + + i= right + 1; } - if(!siz2i) - break; - siz2[siz2i++]= 0; - FFSWAP(int*, siz1, siz2); - assert(idx[ptr[0]-in] == 0); } - free(siz1); - free(siz2); + for(i=0; i<len; i++){ + out[idx[i]]= in[i]; + } + ret= idx[0]; #else for(i=1; i<len; i++){ if(memcmp(ptr[last]+1, ptr[i]+1, RADIX_PASSES)){ @@ -424,12 +455,6 @@ fprintf(stderr, "idx init done\n"); if(i-last>1) bssort(ptr + last, i-last, RADIX_PASSES+1, in, in+len); #endif - ret=-1; - for(i=0; i<len; i++){ - out[i]= *ptr[i]; - if(ptr[i] == in) - ret= i; - } free(ptr); free(ptr2);

1 0

[Mndiff-dev] [mndiff]: r39 - trunk/mnzip/mnzip.c
by michael 21 Jun '07

21 Jun '07

Author: michael Date: Thu Jun 21 11:07:17 2007 New Revision: 39 Log: indention fix by Corey Hickey Modified: trunk/mnzip/mnzip.c Modified: trunk/mnzip/mnzip.c ============================================================================== --- trunk/mnzip/mnzip.c (original) +++ trunk/mnzip/mnzip.c Thu Jun 21 11:07:17 2007 @@ -870,17 +870,17 @@ int main(int argc, char **argv){ static const uint8_t header[7]={'M','N','Z','I','P',0,0}; if (argc > 1) { - for(i=0; argv[1][i]; i++){ - switch(argv[1][i]){ - case 'c' : comp=1 ; break; - case 'd' : comp=0 ; break; - case 'l' : low_mem =1 ; break; - case '0' ... '9': block_size= 1<<(argv[1][i]-'0'+20); break; - case '-' : break; - default : help() ; + for(i=0; argv[1][i]; i++){ + switch(argv[1][i]){ + case 'c' : comp=1 ; break; + case 'd' : comp=0 ; break; + case 'l' : low_mem =1 ; break; + case '0' ... '9': block_size= 1<<(argv[1][i]-'0'+20); break; + case '-' : break; + default : help() ; + } } } - } if (argc < 3 || !strcmp(argv[2], "-")) fi = stdin;

1 0

[Mndiff-dev] [BUG] mnzip: exit status 1 with some some files
by Corey Hickey 20 Jun '07

20 Jun '07

I don't know if this is a bug in compression or decompression, but 'mnzip d' exits with status 1 even though the operation appears to work--the output file is identical to the original. You can get bzip2-ed source files here: http://fatooh.org/files/tmp/mnzip/big.bz2 http://fatooh.org/files/tmp/mnzip/small.bz2 They're the first 4 MB and 1 MB of the linux 2.6.0 tar. $ ls -l total 5128 -rw-r--r-- 1 bugfood bugfood 4194304 2007-06-19 16:56:44 big -rw-r--r-- 1 bugfood bugfood 1048576 2007-06-19 16:56:55 small $ md5sum * 03dd4e4b175dda45093dd7183a6356b9 big 0a2b383ccb25969dd930dbe57da08d4f small To reproduce, run a set of commands like this: echo -----compressing------- mnzip c0 small > out.mnz echo exit status $? echo ---------decompressing---------- mnzip d out.mnz > out echo exit status $? The "big" file has the same problem even with "c" instead of "c0". I've posted logs: http://fatooh.org/files/tmp/mnzip/big.log http://fatooh.org/files/tmp/mnzip/small.log -Corey

2 2

Re: [Mndiff-dev] [PATCH] mndiff (er, mnzip): alternative stream usage patch
by Corey Hickey 20 Jun '07

20 Jun '07

Michael Niedermayer wrote: > Hi > > On Mon, Jun 18, 2007 at 01:21:48AM -0700, Corey Hickey wrote: >> This patch supersedes my previous two patches with regard to argument >> checking and file open checking. >> >> The version attached allows input and output to be files, stdin/stdout, >> or a combination. I've tested it pretty thoroughly, but, if I messed it >> up, blame it on the fact that I should have been in bed long ago. > > i dont think this will apply anymore after ive applied the last 3 Yeah, I meant it to be applied instead, but I guess I wasn't quick enough. ...and, of course, I meant mnzip in the subject of my previous message. I had a few minutes to re-make the patch; I also added some usage examples to help(). -Corey Index: mnzip.c =================================================================== --- mnzip.c (revision 36) +++ mnzip.c (working copy) @@ -458,7 +458,7 @@ 6,5 ( 3) -> 689 */ -static int ibwt(uint8_t *in, unsigned int len, unsigned int start, unsigned int histogram[256], int low_mem, int pretype){ +static int ibwt(uint8_t *in, FILE *fo, unsigned int len, unsigned int start, unsigned int histogram[256], int low_mem, int pretype){ int shift= low_mem*3; int shift2= shift + 8; int mask= (1<<shift)-1; @@ -539,7 +539,7 @@ if(pretype) inv_pretransform(buffer, pret_buf, len2, pretype); - fwrite(buffer, len2, 1, stdout); + fwrite(buffer, len2, 1, fo); } free(idx); @@ -766,7 +766,7 @@ return out_size+16; } -static int decompress(FILE *fi, int low_mem){ +static int decompress(FILE *fi, FILE *fo, int low_mem){ uint8_t *in; unsigned int in_len; unsigned int out_len,start,i, j, pretype; @@ -834,36 +834,42 @@ fprintf(stderr, "error (%d)\n", c.bytestream - c.bytestream_end); return -1; } - ibwt(tmp, out_len, start, histogram, low_mem, pretype); + ibwt(tmp, fo, out_len, start, histogram, low_mem, pretype); return out_len; } static void help(void){ fprintf(stderr, - "Usage: mnzip [OPTIONS] [INPUT-FILE]\n" + "Usage: mnzip [OPTIONS] [INPUT_FILE|-] [OUTPUT_FILE|-]\n" "options:\n" " c compress\n" " d decompress\n" " l slow/low memory mode\n" " 0-9 block size in 2^x megabyte (4mb is default)\n" + "\n" + "examples:\n" + " Compress one file to another file:\n" + " mnzip c input_file output_file\n" + " Compress from stdin to stdout:\n" + " mnzip c\n" + " mnzip c - -\n" + " Decompress from stdin to a file:\n" + " mnzip d - output_file\n" ); exit(1); } int main(int argc, char **argv){ - FILE *fi; + FILE *fi, *fo; uint8_t *out, *in; - int comp= !strcmp(argv[0], "mnzip"); + int comp= !strcmp(argv[0], "mnzib"); int low_mem= 0; int block_size= 1<<22; int outsize, i; static const uint8_t header[7]={'M','N','Z','I','P',0,0}; - if (argc != 3) - help(); - - for(i=0; argv[1][i]; i++){ + for(i=0; argv[1] && argv[1][i]; i++){ switch(argv[1][i]){ case 'c' : comp=1 ; break; case 'd' : comp=0 ; break; @@ -874,25 +880,34 @@ } } - if (! (fi = fopen(argv[2], "rb"))) { + if (argc < 3 || !strcmp(argv[2], "-")) + fi = stdin; + else if (! (fi = fopen(argv[2], "rb"))) { perror("Error opening input file"); exit(1); } + if (argc < 4 || !strcmp(argv[3], "-")) + fo = stdout; + else if (! (fo = fopen(argv[3], "w+b"))) { + perror("Error opening output file"); + exit(1); + } + init_prob(prob); if(comp){ in = malloc(block_size+RADIX_PASSES); out= malloc(2*block_size + 5000);//FIXME int and buffer overfl - fwrite(header, 7, 1, stdout); + fwrite(header, 7, 1, fo); while(!feof(fi)){ block_size= fread(in, 1, block_size, fi); fprintf(stderr, "bwt in %p %p %d\n", out, in, block_size); outsize= compress(out, in, block_size); fprintf(stderr, "bwt out %d\n", outsize); - fwrite(out, outsize, 1, stdout); + fwrite(out, outsize, 1, fo); } }else{ uint8_t tmp[256]; @@ -903,7 +918,7 @@ exit(1); } while(!feof(fi)){ - if(decompress(fi, low_mem)<0) + if(decompress(fi, fo, low_mem)<0) exit(1); } }

2 4

[Mndiff-dev] [mndiff]: r38 - trunk/mnzip/mnzip.c
by michael 20 Jun '07

20 Jun '07

Author: michael Date: Wed Jun 20 14:31:27 2007 New Revision: 38 Log: dont start a new block if the end is reached Modified: trunk/mnzip/mnzip.c Modified: trunk/mnzip/mnzip.c ============================================================================== --- trunk/mnzip/mnzip.c (original) +++ trunk/mnzip/mnzip.c Wed Jun 20 14:31:27 2007 @@ -907,6 +907,8 @@ int main(int argc, char **argv){ while(!feof(fi)){ block_size= fread(in, 1, block_size, fi); fprintf(stderr, "bwt in %p %p %d\n", out, in, block_size); + if(!block_size) + break; outsize= compress(out, in, block_size); fprintf(stderr, "bwt out %d\n", outsize); fwrite(out, outsize, 1, fo);

1 0

[Mndiff-dev] [mndiff]: r37 - trunk/mnzip/mnzip.c
by michael 20 Jun '07

20 Jun '07

Author: michael Date: Wed Jun 20 14:22:08 2007 New Revision: 37 Log: support file output and stdin input patch by Corey Hickey Modified: trunk/mnzip/mnzip.c Modified: trunk/mnzip/mnzip.c ============================================================================== --- trunk/mnzip/mnzip.c (original) +++ trunk/mnzip/mnzip.c Wed Jun 20 14:22:08 2007 @@ -458,7 +458,7 @@ fprintf(stderr, "idx init done\n"); 6,5 ( 3) -> 689 */ -static int ibwt(uint8_t *in, unsigned int len, unsigned int start, unsigned int histogram[256], int low_mem, int pretype){ +static int ibwt(uint8_t *in, FILE *fo, unsigned int len, unsigned int start, unsigned int histogram[256], int low_mem, int pretype){ int shift= low_mem*3; int shift2= shift + 8; int mask= (1<<shift)-1; @@ -539,7 +539,7 @@ static int ibwt(uint8_t *in, unsigned in if(pretype) inv_pretransform(buffer, pret_buf, len2, pretype); - fwrite(buffer, len2, 1, stdout); + fwrite(buffer, len2, 1, fo); } free(idx); @@ -766,7 +766,7 @@ fprintf(stderr," done (%d %d %d)\n", len return out_size+16; } -static int decompress(FILE *fi, int low_mem){ +static int decompress(FILE *fi, FILE *fo, int low_mem){ uint8_t *in; unsigned int in_len; unsigned int out_len,start,i, j, pretype; @@ -834,25 +834,34 @@ fprintf(stderr," block (%d %d %d)\n", ou fprintf(stderr, "error (%d)\n", c.bytestream - c.bytestream_end); return -1; } - ibwt(tmp, out_len, start, histogram, low_mem, pretype); + ibwt(tmp, fo, out_len, start, histogram, low_mem, pretype); return out_len; } static void help(void){ fprintf(stderr, - "Usage: mnzip [OPTIONS] [INPUT-FILE]\n" + "Usage: mnzip [OPTIONS] [INPUT_FILE|-] [OUTPUT_FILE|-]\n" "options:\n" " c compress\n" " d decompress\n" " l slow/low memory mode\n" " 0-9 block size in 2^x megabyte (4mb is default)\n" + "\n" + "examples:\n" + " Compress one file to another file:\n" + " mnzip c input_file output_file\n" + " Compress from stdin to stdout:\n" + " mnzip c\n" + " mnzip c - -\n" + " Decompress from stdin to a file:\n" + " mnzip d - output_file\n" ); exit(1); } int main(int argc, char **argv){ - FILE *fi; + FILE *fi, *fo; uint8_t *out, *in; int comp= !strcmp(argv[0], "mnzip"); int low_mem= 0; @@ -860,9 +869,7 @@ int main(int argc, char **argv){ int outsize, i; static const uint8_t header[7]={'M','N','Z','I','P',0,0}; - if (argc != 3) - help(); - + if (argc > 1) { for(i=0; argv[1][i]; i++){ switch(argv[1][i]){ case 'c' : comp=1 ; break; @@ -873,26 +880,36 @@ int main(int argc, char **argv){ default : help() ; } } + } - if (! (fi = fopen(argv[2], "rb"))) { + if (argc < 3 || !strcmp(argv[2], "-")) + fi = stdin; + else if (! (fi = fopen(argv[2], "rb"))) { perror("Error opening input file"); exit(1); } + if (argc < 4 || !strcmp(argv[3], "-")) + fo = stdout; + else if (! (fo = fopen(argv[3], "w+b"))) { + perror("Error opening output file"); + exit(1); + } + init_prob(prob); if(comp){ in = malloc(block_size+RADIX_PASSES); out= malloc(2*block_size + 5000);//FIXME int and buffer overfl - fwrite(header, 7, 1, stdout); + fwrite(header, 7, 1, fo); while(!feof(fi)){ block_size= fread(in, 1, block_size, fi); fprintf(stderr, "bwt in %p %p %d\n", out, in, block_size); outsize= compress(out, in, block_size); fprintf(stderr, "bwt out %d\n", outsize); - fwrite(out, outsize, 1, stdout); + fwrite(out, outsize, 1, fo); } }else{ uint8_t tmp[256]; @@ -903,7 +920,7 @@ fprintf(stderr, "bwt out %d\n", outsize) exit(1); } while(!feof(fi)){ - if(decompress(fi, low_mem)<0) + if(decompress(fi, fo, low_mem)<0) exit(1); } }

1 0

Re: [Mndiff-dev] [PATCH] mnzip: three small patches
by Michael Niedermayer 19 Jun '07

19 Jun '07

Hi On Mon, Jun 18, 2007 at 12:44:00AM -0700, Corey Hickey wrote: > Interesting program. I have yet to start messing with it, but the > benchmarks you posted are tantalizing. Here's a few simple fixes, since > I don't understand the more complex stuff. > > arg_check.diff > This fixes a segfault when mnzip is called with insufficient arguments. > > fopen_error.diff > This fixes a segfault when the input file is inaccessible. > > typo.diff > I guess this is a typo, but I'm not sure what you had in mind. all applied, and thanks alot for the patches, i was alraedy affraid noone would ever send one :) btw iam CCing mndiff-dev(a)mplayerhq.hu which is the correct ML for all the stuff in my personal repo on mphq [...] -- Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB If you really think that XML is the answer, then you definitly missunderstood the question -- Attila Kinali

2 2