Mndiff-dev

Download

mndiff-dev@mplayerhq.hu

April 2007

1 participants
2 discussions

[Mndiff-dev] [mndiff]: r11 - trunk/mnzip/mnzip.c
by michael 29 Apr '07

29 Apr '07

Author: michael Date: Sun Apr 29 20:47:45 2007 New Revision: 11 Log: replace current qsort-memcmp based bwt by karp-miller-rosenberg and bentley-sedgewick based sorting algorithms also kill some global which where needed due to retarded c standard design of qsort() Modified: trunk/mnzip/mnzip.c Modified: trunk/mnzip/mnzip.c ============================================================================== --- trunk/mnzip/mnzip.c (original) +++ trunk/mnzip/mnzip.c Sun Apr 29 20:47:45 2007 @@ -37,31 +37,102 @@ #define MAX(a,b) ((a) > (b) ? (a) : (b)) #define MIN(a,b) ((a) > (b) ? (b) : (a)) -static uint8_t *global_end, *global_start; //FIXME remove ugly globals +static void qsort2(uint8_t **ptr, int *idx, int len){ + int pivot; + int i=0; + int j=0; + int k=len-1; -static int cmp(const uint8_t **pa, const uint8_t **pb){ - const uint8_t *a= *pa+1+RADIX_PASSES; - const uint8_t *b= *pb+1+RADIX_PASSES; + assert(len>1); - for(;;){ - int len= global_end - MAX(a, b); - if(len>0){ - int i= memcmp(a, b, len); - if(i) return i; - a+=len; - b+=len; + pivot= idx[len>>1]; + i=0; + while(j<=k){ + int v= idx[j]; + if(v == pivot) + j++; + else if(v<pivot){ + FFSWAP(int, idx[j], idx[i]); + FFSWAP(uint8_t*, ptr[j], ptr[i]); + j++; + i++; + }else{ + FFSWAP(int, idx[j], idx[k]); + FFSWAP(uint8_t*, ptr[j], ptr[k]); + do{ + k--; + }while(idx[k] > pivot); + } + } + assert(i>=0); + assert(i<=j); + assert(j<=k+1); + assert(k<=len-1); + if(i>1) + qsort2(ptr ,idx , i ); + if(len-k>2) + qsort2(ptr+j,idx+j, len-1-k); +} + +#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); } - if(a>=global_end) a-= global_end - global_start; - if(b>=global_end) b-= global_end - global_start; } + 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, ret; + unsigned int i, j, ret; uint8_t **ptr = malloc(len*sizeof(uint8_t*)); uint8_t **ptr2= malloc(len*sizeof(uint8_t*)); int histogram[257]; int last= 0; + int sorted; + int *idx= ptr2; + int *siz1, *siz2, *idx2; + int siz1i=0; if(!ptr || !ptr2 || len >= UINT_MAX / sizeof(uint8_t*)) //FIXME memleak return -1; @@ -97,20 +168,70 @@ static unsigned int bwt(uint8_t *out, ui for(i=0; i<len; i++){ ptr[ histogram[ptr2[i][1]]++ ]= ptr2[i]; } - free(ptr2); - - global_start= in; //FIXME - global_end = in+len; +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++){ + 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; + last= i; + } + idx[ptr[i]-in]= last; + } + if(i-last>1) + siz1[siz1i++]= i; + siz1[siz1i++]= 0; +fprintf(stderr, "idx init done\n"); + for(sorted=RADIX_PASSES; sorted<len; sorted<<=1){ + int last=0; + int siz1i=0; + int siz2i=0; + for(;;){ + int i= siz1[siz1i++]; + if(!i) + break; + last= idx[ptr[i-1]-in]; +#define limit(i) ((i)>=len ? (i) - len : (i)) + for(j=last; j<i; 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] <= last); + idx[ptr[j]-in]= last; + } + if(j-idx[ptr[j-1]-in]>1) + siz2[siz2i++]= j; + } + if(!siz2i) + break; + siz2[siz2i++]= 0; + FFSWAP(int*, siz1, siz2); + assert(idx[ptr[0]-in] == 0); + } + free(siz1); + free(siz2); +#else for(i=1; i<len; i++){ if(memcmp(ptr[last]+1, ptr[i]+1, RADIX_PASSES)){ if(i-last>1) - qsort(ptr + last, i-last, sizeof(uint8_t*), cmp); + bssort(ptr + last, i-last, RADIX_PASSES+1, in, in+len); last= i; } } - qsort(ptr + last, i-last, sizeof(uint8_t*), cmp); - + 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]; @@ -119,6 +240,7 @@ static unsigned int bwt(uint8_t *out, ui } free(ptr); + free(ptr2); return ret; }

1 0

[Mndiff-dev] [mndiff]: r10 - in trunk/mnzip: . mnzip.c
by michael 26 Apr '07

26 Apr '07

Author: michael Date: Thu Apr 26 03:15:04 2007 New Revision: 10 Log: my own generic file compressor current algorithm is similar to bzip2 but compresses much better (at least for the bunch of files ive tried it on) decompression speed is about the same as bzip2, compression is slower current code is a mess and needs a cleanup ... Added: trunk/mnzip/ trunk/mnzip/mnzip.c Added: trunk/mnzip/mnzip.c ============================================================================== --- (empty file) +++ trunk/mnzip/mnzip.c Thu Apr 26 03:15:04 2007 @@ -0,0 +1,567 @@ +/* + * Copyright (c) 2007 Michael Niedermayer <michaelni(a)gmx.at> + * + * mnzip is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * mnzip is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with mnzip; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + * + */ + +#include <stdlib.h> +#include <stdio.h> +#include <inttypes.h> +#include <limits.h> +#include <string.h> +#include <assert.h> +#include "common.h" //for av_log2 FIXME avoid this +#define attribute_unused +#include "rangecoder.h" + + +#undef NDEBUG +#include <assert.h> + +#define RADIX_PASSES 4 + + +#define MAX(a,b) ((a) > (b) ? (a) : (b)) +#define MIN(a,b) ((a) > (b) ? (b) : (a)) + +static uint8_t *global_end, *global_start; //FIXME remove ugly globals + +static int cmp(const uint8_t **pa, const uint8_t **pb){ + const uint8_t *a= *pa+1+RADIX_PASSES; + const uint8_t *b= *pb+1+RADIX_PASSES; + + for(;;){ + int len= global_end - MAX(a, b); + if(len>0){ + int i= memcmp(a, b, len); + if(i) return i; + a+=len; + b+=len; + } + if(a>=global_end) a-= global_end - global_start; + if(b>=global_end) b-= global_end - global_start; + } +} + +static unsigned int bwt(uint8_t *out, uint8_t *in, unsigned int len){ + unsigned int i, ret; + uint8_t **ptr = malloc(len*sizeof(uint8_t*)); + uint8_t **ptr2= malloc(len*sizeof(uint8_t*)); + int histogram[257]; + int last= 0; + + if(!ptr || !ptr2 || len >= UINT_MAX / sizeof(uint8_t*)) //FIXME memleak + return -1; + + memset(histogram, 0, sizeof(histogram)); + for(i=0; i<len; i++) + histogram[ in[i] + 1 ]++; + + for(i=1; i<257; i++) + histogram[i] += histogram[i-1]; + + for(i=0; i<RADIX_PASSES; i++) + in[len+i]= in[i]; + + for(i=0; i<len; i++){ + ptr2[ histogram[in[i+4]]++ ]= in+i; + } + + memmove(histogram+1, histogram, sizeof(int)*256); //FIXME simplify + histogram[0]= 0; + for(i=0; i<len; i++){ + ptr[ histogram[ptr2[i][3]]++ ]= ptr2[i]; + } + + memmove(histogram+1, histogram, sizeof(int)*256); //FIXME simplify + histogram[0]= 0; + for(i=0; i<len; i++){ + ptr2[ histogram[ptr[i][2]]++ ]= ptr[i]; + } + + memmove(histogram+1, histogram, sizeof(int)*256); //FIXME simplify + histogram[0]= 0; + for(i=0; i<len; i++){ + ptr[ histogram[ptr2[i][1]]++ ]= ptr2[i]; + } + free(ptr2); + + global_start= in; //FIXME + global_end = in+len; + + for(i=1; i<len; i++){ + if(memcmp(ptr[last]+1, ptr[i]+1, RADIX_PASSES)){ + if(i-last>1) + qsort(ptr + last, i-last, sizeof(uint8_t*), cmp); + last= i; + } + } + qsort(ptr + last, i-last, sizeof(uint8_t*), cmp); + + ret=-1; + for(i=0; i<len; i++){ + out[i]= *ptr[i]; + if(ptr[i] == in) + ret= i; + } + + free(ptr); + return ret; +} + +/* + 3,0 (48) -> 35 + 2,2 (40) -> 26 + 2,3 (36) -> 31 + 2,4 (34) -> 37 + 2,5 (33) -> 44 + 3,1 (32) -> 42 + 3,2 (24) -> 51 4,1 (24) -> 76 + 3,3 (20) -> 62 5,1 (20) -> 166 + 3,4 (18) -> 75 + 3,5 (17) -> 90 + 4,2 (16) -> 93 + 4,3 (12) -> 115 5,2 (12) -> 199 + 4,4 (10) -> 141 + 4,5 ( 9) -> 172 + 5,3 ( 8) -> 239 + 5,4 ( 6) -> 289 + 5,5 ( 5) -> 348 + 6,4 ( 4) -> 580 + 6,5 ( 3) -> 689 +*/ + +static int ibwt(uint8_t *in, unsigned int len, unsigned int start, unsigned int histogram[256], int low_mem){ + int shift= low_mem*3; + int shift2= shift + 8; + int mask= (1<<shift)-1; + unsigned int i, j; + unsigned int int_histogram[257], int_histogram2[257]; + uint8_t buffer[1024*32]; + unsigned idx_len = len>>shift; + unsigned idx2_len= len>>shift2; + uint32_t *idx= malloc(idx_len*sizeof(uint32_t)); + uint8_t *idx2=malloc(idx2_len*256*sizeof(uint8_t)); + int packed= idx_len <= 256*256*256 && !shift; + + if(!idx || idx_len >= UINT32_MAX / sizeof(uint32_t)) //FIXME memleak + return -1; + + if(start >= len) + return -1; + + int_histogram[0]= 0; + for(i=1; i<257; i++) + int_histogram[i]= int_histogram[i-1]+histogram[i-1]; + memcpy(int_histogram2, int_histogram, sizeof(int_histogram)); //FIXME remove + + for(i=0; i<len; i++){ + int j= int_histogram2[ in[i] ]++; + if(!(j&mask)){ + idx[j>>shift]= i; + if(packed) + idx[j>>shift]|= in[j]<<24; + idx2[ idx2_len*in[i] + (i>>shift2)]= 1; + }else + idx2[ idx2_len*in[i] + (i>>shift2)]++; + } + + for(i=0; i<len; i+=sizeof(buffer)){ + unsigned int len2= MIN(sizeof(buffer), len-i); + for(j=0; j<len2; j++){ + int skip= start&mask; + unsigned int target= start; + if(packed){ + buffer[j]= idx[start>>shift]>>24; + start= idx[start>>shift] & 0xFFFFFF; + }else{ + buffer[j]= in[start]; + start= idx[start>>shift]; + } + if(skip){ + int byte= in[start]; + unsigned int next= idx[(target + mask)>>shift]; + +// assert(int_histogram2[byte] > target - skip); + while(int_histogram2[byte] <= target){ + start=0; + skip= target - int_histogram2[byte++]; +// assert(target - int_histogram2[byte-1] <= mask); +// assert(skip >= 0); + } + + while((target + mask)>>shift < idx_len && next > ((start>>shift2)+1)<<shift2 && 0 ){ //FIXME buggy, works with one but not the second file + unsigned int i2= idx2[ idx2_len*byte + (start>>shift2)]; + + if(i2 > skip) + break; + if(start==0 && i2) //FIXME figure out why this is needed + break; + + start=((start>>shift2)+1)<<shift2; + skip-= i2; + } + + for(; start<len; start++){ + if(in[start] == byte && !skip--) + break; + } + } + } + fwrite(buffer, len2, 1, stdout); + } + + free(idx); + return 0; +} +#if 1 +static inline int clip(int a, int amin, int amax){ + if (a < amin) return amin; + else if (a > amax) return amax; + else return a; +} +#endif +static inline void putbit_clip(RangeCoder *c, uint16_t *state, int b, int min, int max){ +#if 0 + if(*state &1){ + int x= (*state&0xFF)>>1; + int y= *state>>9; + uint8_t s= clip((256*x + (x+y)/2) / (x+y), min, max); + put_rac(c, &s, b); + + if(b) x++; + else y++; + if(x+y>8) + *state= ((65536*x + (x+y)/2) / (x+y)) & 0xFFFE; + else + *state= (x + y*256)*2+1; + }else{ + uint8_t s= clip(*state>>8, min, max); + put_rac(c, &s, b); + + *state+= ((b*65536 - *state)*30 + 512)>>10; + *state&=0xFFFE; + } +#elif 0 + put_rac(c, (uint8_t*)state + 1, b); +#else + uint8_t s= clip(*state>>8, 1, 255); + put_rac(c, &s, b); + + *state+= ((b*65536 - *state)*30 + 512)>>10; +#endif +} + +static inline void putbit(RangeCoder *c, uint16_t *state, int b){ + putbit_clip(c, state, b, 1, 255); +} + +static inline int getbit(RangeCoder *c, uint16_t *state){ + uint8_t s= clip(*state>>8, 1, 255); + int b= get_rac(c, &s); + + *state+= ((b*65536 - *state)*30 + 512)>>10; + + return b; +} + +static inline void put_symbol(RangeCoder *c, uint16_t *state, int v){ + int i; + + if(v){ + const int e= av_log2(v); + const int el= MIN(e, 8); + putbit(c, state+0, 0); + + for(i=0; i<el; i++){ + putbit(c, state+1+i, 1); //1..8 + } + for(; i<e; i++){ + putbit(c, state+1+7, 1); //1..8 + } + putbit(c, state+1+MIN(i,7), 0); + + for(i=e-1; i>=el; i--){ + putbit(c, state+9+7, (v>>i)&1); //9..16 + } + for(; i>=0; i--){ + putbit(c, state+9+i, (v>>i)&1); //9..16 + } + }else{ + putbit(c, state+0, 1); + } +} + +static inline void put_symbol_255(RangeCoder *c, uint16_t *state, int v){ + const int e= av_log2(v); + int i; + + assert(v); + assert(e<8); + putbit(c, state, e>3); //0 + putbit(c, state+1+(e>3), (e&2)>>1); //1..2 + putbit(c, state+3+(e>>1), (e&1)); //3..6 + + for(i=e-1; i>=0; i--) + putbit(c, state+7+i, (v>>i)&1); //7..13 +} + +static inline int get_symbol_255(RangeCoder *c, uint16_t *state){ + int e,a,i; + + e =4*getbit(c, state); //0 + e+=2*getbit(c, state+1+(e>3)); //1..2 + e+= getbit(c, state+3+(e>>1)); //3..6 + + a= 1; + for(i=e-1; i>=0; i--) + a += a + getbit(c, state+7 + i); //7..13 + + return a; +} + +static inline int get_symbol(RangeCoder *c, uint16_t *state){ + if(getbit(c, state+0)) + return 0; + else{ + int i, e, a; + e= 0; + while(getbit(c, state+1 + MIN(e,7))) //1..8 + e++; + + a= 1; + for(i=e-1; i>=0; i--) + a += a + getbit(c, state+9 + MIN(i,7)); //9..16 + + return a; + } +} + +static inline int rb32(uint8_t *p){ + return (p[0]<<24) + (p[1]<<16) + (p[2]<<8) + p[3]; +} + +static inline void wb32(uint8_t *p, int v){ + p[0]= v>>24; + p[1]= v>>16; + p[2]= v>>8; + p[3]= v; +} + +static unsigned int compress(uint8_t *out, uint8_t *in, unsigned int len){ + uint8_t *tmp= malloc(len); + unsigned int start,j, out_size; + int i; + RangeCoder c; + uint16_t state[16*512*32+1]; + int mtf[256]; +fprintf(stderr, "bwt\n"); + start= bwt(tmp, in, len); +fprintf(stderr," done\n"); + +fprintf(stderr,"range coding (%d %d)\n", len, start); + wb32(out, 0 ); out+=4; + wb32(out, len ); out+=4; + wb32(out, start); out+=4; + wb32(out, 0 ); out+=4; + + memset(state, 128, sizeof(state)); +//memset(state, 3, sizeof(state)); + + for(i=0; i<256; i++) + mtf[i]= i; + + ff_init_range_encoder(&c, out, len); + ff_build_rac_states(&c, 0.04*(1LL<<32), 256-4); //FIXME shouldnt be needed + + for(i=len-1; i>=0; i--){ + int v= tmp[i]; + for(j=0; mtf[j] != v; j++); + assert(j<256); + tmp[i]= j; + for(;j>0; j--) + mtf[j]=mtf[j-1]; + mtf[0]= v; + } + + for(i=0; i<256; i++){ + put_symbol(&c, &state[256*32*2], mtf[i]); + } + + for(i=0; i<len; i++){ + int run, v, ndx; + for(run=0; i<len && !tmp[i]; i++) + run++; + + ndx= tmp[i]; + v= mtf[0]; + for(j=0; j<ndx; j++) + mtf[j]= mtf[j+1]; + mtf[ndx]= v; + put_symbol_255(&c, &state[v*32], ndx); + put_symbol(&c, &state[256*32 + 32*v], run); + } +//FIXME last byte mtf= 0 and run mess +//FIXME right order mtf optim +assert(tmp[len-1]); + + free(tmp); + out_size= ff_rac_terminate(&c); + wb32(out-4, out_size); +fprintf(stderr," done (%d %d %d)\n", len, start, out_size); + return out_size+16; +} + +static int decompress(FILE *fi, int low_mem){ + uint8_t *in; + unsigned int in_len; + unsigned int out_len,start,i, j; + int ret; + uint8_t *tmp; //FIXME reduce memory needs + RangeCoder c; + uint16_t state[32*1024+1]; //FIXME isnt needed to be that large + unsigned int histogram[256]={0}; + int mtf[256]; + uint8_t tmpX[16]; + + ret=fread(tmpX, 1, 16, fi); + if(ret==0) + return 0; + else if(ret != 16) + return -1; + + out_len= rb32(tmpX+4); + start = rb32(tmpX+8); + in_len = rb32(tmpX+12); +fprintf(stderr," block (%d %d %d)\n", out_len, start, in_len); + if(out_len<=0 || start<=0 || in_len<=0 || start >= out_len) + return -1; + + in = malloc(in_len); + tmp= malloc(out_len); + if(!in || !tmp) + return -1; + + if(fread(in, in_len, 1, fi)!=1) + return -1; //FIXME check all return memleaks + + //FIXME check all fread + + memset(state, 128, sizeof(state)); + + ff_init_range_decoder(&c, in, in_len); + ff_build_rac_states(&c, 0.04*(1LL<<32), 256-4); + + for(i=0; i<256; i++){ + int test[256]={0}; + mtf[i]= get_symbol(&c, &state[256*32*2]); + if(mtf[i] > 255U || test[mtf[i]]++){ + fprintf(stderr, "fatal error mtf invalid\n"); + return -1; + } + } + + for(i=0; i<out_len; ){ + int v= mtf[0]; + int ndx= get_symbol_255(&c, &state[v*32]); + int run= get_symbol(&c, &state[256*32 + 32*v]) + 1; + + for(j=0; j<ndx; j++) + mtf[j]= mtf[j+1]; + mtf[ndx]= v; + + if(i+run > out_len || i+run<i){ + fprintf(stderr, "fatal error, run to large\n"); + return -1; + } + do{ + tmp[i++]= v; + histogram[v]++; + }while(--run); + } + + free(in); + if(c.bytestream_end - c.bytestream != -1){ + fprintf(stderr, "error (%d)\n", c.bytestream - c.bytestream_end); + return -1; + } + ibwt(tmp, out_len, start, histogram, low_mem); + + return out_len; +} + +static void help(void){ + fprintf(stderr, + "Usage: mnzip [OPTIONS] [INPUT-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" + ); + exit(1); +} + +int main(int argc, char **argv){ + FILE *fi= fopen(argv[2], "rb"); + uint8_t *out, *in; + 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}; + + for(i=0; argv[1] && 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(comp){ + in = malloc(block_size+RADIX_PASSES); + out= malloc(2*block_size + 5000);//FIXME int and buffer overfl + + fwrite(header, 7, 1, stdout); + + 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); + } + }else{ + uint8_t tmp[256]; + + fread(tmp, sizeof(header), 1, fi); + if(memcmp(tmp, header, sizeof(header))){ + fprintf(stderr, "input header missmatch\n"); + exit(1); + } + while(!feof(fi)){ + if(decompress(fi, low_mem)<0) + exit(1); + } + } + fclose(fi); + + return 0; +}

1 0