diff options
Diffstat (limited to 'libc/tests/compr.c')
| -rw-r--r-- | libc/tests/compr.c | 383 |
1 files changed, 383 insertions, 0 deletions
diff --git a/libc/tests/compr.c b/libc/tests/compr.c new file mode 100644 index 0000000..8e53443 --- /dev/null +++ b/libc/tests/compr.c @@ -0,0 +1,383 @@ + +#include <sys/types.h> +#include <sys/stat.h> +#include <fcntl.h> +#include <stdio.h> +#include <malloc.h> + +#define MAXNO 32767 +#define MAXLEN 127 +#define XXQSCAN /* Speed up scanning at the cost of not being optimal */ + +unsigned char *fptr; +unsigned short *vptr; +FILE * fd; + +#define ITBSIZE 4096 +#define itbfunc() (ptr[mainscan]^(ptr[mainscan+1]<<4)^(ptr[mainscan+2]<<2)) +/* +#define ITBSIZE 4001 +#define itbfunc() ((ptr[mainscan]+ptr[mainscan+1]*79+ptr[mainscan+2]*307)%4001) +*/ +int * itb; + +int size; +int maxno= 8000; +long cnt=0; + +long icount = 0; +long ocount = 0; + +unsigned char key; + +int fl; + +main(argc, argv) +int argc; +char ** argv; +{ + if( argc < 2 ) { fprintf(stderr, "Usage; ... \n"); exit(1); } + + if( argc == 3 ) + { + maxno = atoi(argv[2]); + if( maxno < 256 ) maxno = 256; + if( maxno > MAXNO) maxno = MAXNO; + } + + if( strcmp(argv[1], "-") == 0 ) + fd = stdin; + else + fd = fopen(argv[1], "r" ); + if( fd == 0 ) { perror("Open failed\n"); exit(1); } + + fptr = (unsigned char * ) malloc((unsigned)maxno*2); + itb = (int * ) malloc(ITBSIZE*sizeof(int)); + if( itb ) + vptr = (unsigned short * ) malloc((unsigned)maxno * sizeof(short)*2 ); + else + vptr = 0; + + if( fptr == 0 ) + { + perror("Cannot allocate RAM"); + exit(1); + } + if( vptr == 0 && itb ) free(itb); + + fl = 0; + { + if( (size = fread(fptr, 1, (int)maxno, fd )) < 0 ) { fprintf(stderr, "\nRead failed\n"); exit(1); } + + if( size ) + { + icount += size; + if( fl == 0 ) + { + key = scan_min(); + putchar(key); ocount++; + fl = 1; + } + else + fprintf(stderr, "\rBlock %d \r", fl++ ); + if( vptr) compress(); + else slo_compress(); + } + } + + fprintf(stderr, "\n"); + exit(0); +} + +scan_min() +{ + long count[256]; + long i; + int j, n; + + for( j=0; j<256; j++ ) count[j] = 0; + + for( i=0; i<size; i++) count[ fptr[i] & 0xFF ]++; + + for( i= (((unsigned long) -1) >> 1), j=0; j<256; j++ ) + if( count[j] < i ) + { + i = count[j] ; + n = j; + } + + fprintf(stderr, "Most unused in 0x%lx to 0x%lx is 0x%02x at %ld\n", cnt, cnt+size, n, i ); + cnt+= size; + + return n; +} + +compress() +{ + register long mainscan; + register long secondscan; + register unsigned char * ptr = (unsigned char * ) fptr; + register int len; + register int matchlen; + long notepos; + long emark; +#ifdef QSCAN + int count; +#endif + + for( mainscan=0; mainscan <ITBSIZE; itb[mainscan++] = -1 ); + + mainscan=0; + emark = size - 130 ; +loopback: + + for( ; mainscan < emark; ) + { + matchlen = 3; + notepos = -1; +#ifdef QSCAN + count = 0; +#endif + for( secondscan=itb[itbfunc()]; + secondscan >= 0 && mainscan - secondscan < maxno; + secondscan -= vptr[secondscan] ) + { +#ifdef DEBUG +if( vptr[secondscan] == 0 ) +{ + fprintf(stderr, "\nOh !!!!! mainsc %ld, sec-scan %ld\n", mainscan, secondscan); + vptr[secondscan] = secondscan+1; +} +#endif + + for( len = 0; len < MAXLEN ; len++ ) + if( mainscan+len >= size || ptr[mainscan+len] != ptr[secondscan+len] ) break; + if( len > matchlen && (len != 4 || mainscan - secondscan < 256 ) ) + { + notepos = secondscan; + matchlen = len; + if( len == MAXLEN ) break; + } +#ifdef QSCAN + if( matchlen > 20 && len > 3 && ++count > 5 ) + break; +#endif + } + + if( notepos == -1 ) + { + if( ptr[mainscan] == key ) + { + ocount+=2; + putchar(key); + putchar(0); + } + else + { + ocount++; + putchar(ptr[mainscan]); + } + matchlen = 1; + } + else + { + long x = mainscan - notepos; + ocount+=3; + putchar(key); + if( x > 255 ) putchar(matchlen | 0x80); + else putchar(matchlen); + putchar((int)x); + if( x > 255 ) { putchar((int)x>>8); ocount++; } + } + + while( matchlen-- ) + { + len = itbfunc(); + vptr[mainscan] = mainscan - itb[len]; +#if 1 + if( vptr[mainscan] == 0 ) + { + fprintf(stderr, "\nHumm.. ms=%ld, hash=%d, itb[hash]=%ld\n", mainscan, len, itb[len]); + vptr[mainscan] = mainscan+1; + } +#endif + itb[len] = mainscan; + mainscan++; + } + } + + fprintf(stderr, "\rBlock %d ..In:%ld Out:%ld \r", fl-1, icount, ocount ); + + if( emark < size-4 ) + { + int cnt; + long l ; + if(mainscan > maxno ) + { + for(cnt=0; cnt<ITBSIZE; cnt++) + { + if( itb[cnt] < maxno) itb[cnt] = -1; + else itb[cnt] -= maxno; + } + for(l=0; l<maxno; l++) + { + ptr[l] = ptr[l+maxno]; + vptr[l] = vptr[l+maxno]; + } + mainscan -= maxno; + size -= maxno; + } + if( size <= maxno ) + { + if(( cnt = fread(ptr+size, 1, (int)maxno, fd)) < 0 ) + { fprintf(stderr, "\nRead failed\n"); exit(1); } + size += cnt; + icount += cnt; + fprintf(stderr, "\rBlock %d \r", fl++ ); + } + emark = size - 130; + if( mainscan >= emark ) + emark = size -4; + + goto loopback; + } + + for( ; mainscan < size; ) + { + if( ptr[mainscan] == key ) + { + ocount+=2; + putchar(key); + putchar(0); + } + else + { + ocount++; + putchar(fptr[mainscan]); + } + mainscan++; + } + fprintf(stderr, "\rBlock %d ..In:%ld Out:%ld \r", fl-1, icount, ocount ); + /* end */ +} + +slo_compress() +{ + register long mainscan; + register long secondscan; + register unsigned char * ptr = (unsigned char * ) fptr; + register int len; + register int matchlen; + long notepos; + long emark; +#ifdef QSCAN + int count; +#endif + + mainscan=0; + emark = size - 130 ; +loopback: + + for( ; mainscan < emark; ) + { + matchlen = 3; + notepos = -1; +#ifdef QSCAN + count = 0; +#endif + for( secondscan=mainscan-1; + secondscan >= 0 && mainscan - secondscan < maxno; + secondscan-- ) + { + for( len = 0; len < MAXLEN ; len++ ) + if( mainscan+len >= size || ptr[mainscan+len] != ptr[secondscan+len] ) break; + if( len > matchlen && (len != 4 || mainscan - secondscan < 256 ) ) + { + notepos = secondscan; + matchlen = len; + if( len == MAXLEN ) break; + } +#ifdef QSCAN + if( matchlen > 20 && len > 3 && ++count > 5 ) + break; +#endif + } + + if( notepos == -1 ) + { + if( ptr[mainscan] == key ) + { + ocount+=2; + putchar(key); + putchar(0); + } + else + { + ocount++; + putchar(ptr[mainscan]); + } + matchlen = 1; + } + else + { + long x = mainscan - notepos; + ocount+=3; + putchar(key); + if( x > 255 ) putchar(matchlen | 0x80); + else putchar(matchlen); + putchar((int)x); + if( x > 255 ) { putchar((int)x>>8); ocount++; } + } + + mainscan += matchlen; + } + + fprintf(stderr, "\rBlock %d ..In:%ld Out:%ld \r", fl-1, icount, ocount ); + + if( emark < size-4 ) + { + int cnt; + long l ; + if(mainscan > maxno ) + { + for(l=0; l<maxno; l++) + { + ptr[l] = ptr[l+maxno]; + } + mainscan -= maxno; + size -= maxno; + } + if( size <= maxno ) + { + if(( cnt = fread(ptr+size, 1, (int)maxno, fd)) < 0 ) + { fprintf(stderr, "\nRead failed\n"); exit(1); } + size += cnt; + icount += cnt; + fprintf(stderr, "\rBlock %d \r", fl++ ); + } + emark = size - 130; + if( mainscan >= emark ) + emark = size -4; + + goto loopback; + } + + for( ; mainscan < size; ) + { + if( ptr[mainscan] == key ) + { + ocount+=2; + putchar(key); + putchar(0); + } + else + { + ocount++; + putchar(fptr[mainscan]); + } + mainscan++; + } + fprintf(stderr, "\rBlock %d ..In:%ld Out:%ld \r", fl-1, icount, ocount ); + /* end */ +} + |