/*
 * A simple algorithm for swap compression/decompression/
 *
 * Copyright (C) 1996 Luigi Rizzo, luigi@iet.unipi.it
 *
 * The implementation contained in this file represents work in
 * progress. It is made available for evaluation purposes only.
 * Users are kindly requested not to redistribute the code and
 * refer anyone interested to the author.
 * Users are also encouraged to report bugs and comments on this code
 * to the author.
 *
 * The final code _will_ be available for general distribution under
 * an UCB-like copyright.
 *
 * This program analyzes the speed of swap compression.
 * use it as
 *
 *     test your_swap_dev count skip
 *
 * where your_swap_dev is the raw swap device (e.g. /dev/rwd0b),
 * count is the amount of 4KB pages to be compressed,
 * skip is the number of pages to skip.
 *
 * The program compresses and decompressed pages, comparing the
 * result to guarantee from the absence of mistakes.
 *
 * The average compression and decompression times are printed,
 * together with the distribution of compressed values.
 *
 * depending on the arguments, compress, decompress, does nothing.
 */
#include <stdio.h>
#include <fcntl.h>
#include <sys/time.h>

#define	DATATYPE	unsigned int
#define	BIT32		unsigned int
#define	DSZ	(sizeof(DATATYPE))
/*  #define LZRW1 /* if you want to test this algorithm instead */
#define	LIMIT	4080
#define PAGESIZE 4096
#define	GRAIN	64
typedef unsigned long	ctr;

ctr locomp[PAGESIZE/GRAIN];	/* compression statistics */

unsigned long decomp=0; /* number of decompressed pages */
unsigned long buf[PAGESIZE/4];
unsigned long temp[PAGESIZE/4];
unsigned long dst[2*PAGESIZE/4];

struct timeval t1, t2, t3, tot_c, tot_d;

int
gzip_compr(DATATYPE *src, int size, DATATYPE *dst)
{
    int fp, count;
    int i;
    unsigned char *p=(unsigned char *)src;
#if 0
    /*
     * the following piece of code reverses the buffer. If 0s
     * are more frequent at the end, it might be useful to improve
     * the compression performance.
     */
    for (i=0; i<size/2; i++) {
	unsigned char a=p[i];
	p[i]=p[size-i-1];
	p[size-i-1]=a;
    }
#endif
    fp=open("a.out",O_CREAT | O_RDWR, 0666);
    write(fp,src, size);
    close(fp);
    system("gzip -f -9 a.out");
    fp=open("a.out.gz", O_RDONLY);
    count=read(fp,dst,size);
    close(fp);
    return count;
}

/*
 * the compression algorithm uses operands of size DSZ=sizeof(DATATYPE)
 *
 * The data segment is split in words of size DSZ. Only non-zero values
 *      are written to destination. A bitmap indicates the location of
 *	non-zero values.
 *
 * The bitmap has one bit per data word, i.e. size
 *	BM_SZ = ( (size/DSZ)/8 ) bytes (but is written to as DATATYPE)
 *	It is stored in compressed format, only non-zero bytes are
 *	written to destination. A directory (bitmap) indicates the
 *	location of non-zero bytes.
 *
 * The directory has one bit per entry in the bitmap, i.e. size
 *	DIR_SZ = (BM_SZ/8)/DSZ) DATATYPE (again, it is written to as DATATYPE)
 *
 * LAYOUT OF THE COMPRESSION BUFFER:
 * =================================
 * 1 		DATATYPE: DSZ offset into dst for compressed bitmap,
 *		plus flags.
 * DIR_SZ	DATATYPE: directory. MSB first.
 * --		DATATYPE: non zero words
 * --		BYTE:	 compressed bitmap. LSB first.
 *
 * The first word in dst contains a pointer to the intermediate map.
 *
 * The next words contains the primary map. It has size
 */

#define	BM_SZ_BYTES ( (size/DSZ)/8 )
#define	BM_SZ_DATA	(BM_SZ_BYTES/DSZ)
#define	DIR_SZ_DATA ( (BM_SZ_BYTES/8)/DSZ )

int
compr(DATATYPE *src, int size, DATATYPE *dst)
{
    int i,j;
    /*
     * temporary first level bitmap. It has size
     * 	size/DSZ bits. The "2" is a safety factor
     */
    BIT32 bitmap[2*PAGESIZE/DSZ/sizeof(BIT32)];

    /* these ought to be of type DATATYPE */
    BIT32 d_entry, *d_bitmap=bitmap;
    DATATYPE d;
    unsigned char c, *c_bitmap=(unsigned char *)bitmap;

    unsigned char *map;

    int dataoff=1+ DIR_SZ_DATA;

#define DOWORD if ( (d_entry >>= 1), (d= *src++)) {\
	dst[dataoff++]=d; \
	d_entry |= 0x80000000UL ; }

    for (i= BM_SZ_DATA; i-- ; ) {
	d_entry=0;
	for (j=2;j--;) {
	    DOWORD; DOWORD; DOWORD; DOWORD;
	    DOWORD; DOWORD; DOWORD; DOWORD;
	    DOWORD; DOWORD; DOWORD; DOWORD;
	    DOWORD; DOWORD; DOWORD; DOWORD;
	}
	*d_bitmap++ = d_entry;
	if (dataoff>LIMIT/sizeof(DATATYPE)) return size;
    }
    dst[0]=dataoff*sizeof(DATATYPE);	/* byte pointer to map */
    map=(unsigned char *)&dst[dataoff];
    
#define DOBYTE if ( (d_entry += d_entry), (c= *c_bitmap++)) {\
	*map++=c; \
	d_entry++; }
    /*
     * second: compress the map
     */
    for (i=1; i<=DIR_SZ_DATA; i++ ) { /* ok ! */
	d_entry=0;
	for (j=8;j--;) {
	    DOBYTE; DOBYTE; DOBYTE; DOBYTE;
	}
	dst[i] = d_entry;
    }
    return (map - ((unsigned char *)dst)) ;
}

int
decompr(DATATYPE *src, int size, DATATYPE *dst)
{
    int i,j,k;
	/* temporary first level bitmap */
    BIT32 d_dir,
	*d_dirp=(BIT32 *)src + 1;

    unsigned char c,
	*c_bitmap= /* pointer to compressed bitmap */
	    ((unsigned char *)src)+ src[0];

    DATATYPE *d_ptr=	/* pointer to non-zero data */
	src + (1+ size/64/DSZ/DSZ);

    for (i=1; i<=size/64/DSZ/sizeof(d_dir); i++ ) { /* 4 times */
	if (d_dir= *d_dirp++) {
	    /* non-zero directory entry */
	    for (k=32; k; k--) { /* 32 times */
		if (d_dir & 0x80000000UL) {
		    /* non-zero bitmap entry -- load and parse */
		    c=*c_bitmap++;
#define WBYTE(i)    *dst++ = (c & i) ? *d_ptr++ : 0;
		    WBYTE(0x01);
		    WBYTE(0x02);
		    WBYTE(0x04);
		    WBYTE(0x08);
		    WBYTE(0x10);
		    WBYTE(0x20);
		    WBYTE(0x40);
		    WBYTE(0x80);
		} else {
		    bzero(dst, 32);
		    dst += 32 /DSZ;
		}
		d_dir += d_dir;
	    }
	} else {
	    bzero(dst, 1024);
	    dst += 1024 /DSZ;
	}
    }
}

int
emptycompr(DATATYPE *src, int size, DATATYPE *dst)
{
    int i;
    DATATYPE a=0;
    for (i=size/sizeof(DATATYPE)/32; i-- ; ) {
	*dst++ =*src++; *dst++ =*src++; *dst++ =*src++; *dst++ =*src++;
	*dst++ =*src++; *dst++ =*src++; *dst++ =*src++; *dst++ =*src++;
	*dst++ =*src++; *dst++ =*src++; *dst++ =*src++; *dst++ =*src++;
	*dst++ =*src++; *dst++ =*src++; *dst++ =*src++; *dst++ =*src++;
	*dst++ =*src++; *dst++ =*src++; *dst++ =*src++; *dst++ =*src++;
	*dst++ =*src++; *dst++ =*src++; *dst++ =*src++; *dst++ =*src++;
	*dst++ =*src++; *dst++ =*src++; *dst++ =*src++; *dst++ =*src++;
	*dst++ =*src++; *dst++ =*src++; *dst++ =*src++; *dst++ =*src++;
    }
    return (a==0) ? 0: 4096;
}

main(int argc, char *argv[])
{
    int swdev= -1;
    int npages=128;
    unsigned long offset=0;
    int cnt, i,j,k,l,ll;
    ctr byzero=0, wozero=0, lozero=0, lolozero=0;

fprintf(stderr,"BIT32 %d DATATYPE %d, u_char %d, u_short %d, u_long %d\n",
	sizeof(BIT32),
	sizeof(DATATYPE), sizeof(unsigned char), sizeof(unsigned short),
	sizeof(unsigned long) );

    tot_c.tv_sec= tot_c.tv_usec = 0;
    tot_d.tv_sec= tot_d.tv_usec = 0;

    if (argc>1) swdev=open(argv[1],0); /* readonly */
    if (argc>2) npages=atoi(argv[2]);
    if (argc>3) offset=atoi(argv[3]);
    if (npages<1 || npages>8192) npages=256; /* 1MB */
    if (offset<0 || offset>8192) offset=0; /* 0 */
    if (swdev <0) exit(1);

    bzero(locomp, sizeof(locomp));

    lseek(swdev, offset*PAGESIZE, 0);

    for (i=0; i<npages; i++) {
	cnt=read(swdev, buf,PAGESIZE);
	gettimeofday(&t1, NULL);
if (argc<=4) {
#ifdef	LZRW1
        lozero=lzrw1_compr((DATATYPE *)buf, PAGESIZE,(DATATYPE *) dst);
#else
        lozero=compr((DATATYPE *)buf, PAGESIZE,(DATATYPE *) dst);
#endif
	gettimeofday(&t2, NULL);
	if (lozero < PAGESIZE) {
#ifdef	LZRW1
	    lzrw1_decompr((DATATYPE *)dst, lozero, (DATATYPE *) temp);
#else
	    decompr((DATATYPE *)dst, PAGESIZE, (DATATYPE *) temp);
#endif
	    gettimeofday(&t3, NULL);
	    decomp++;
	}
	if (lozero < PAGESIZE && bcmp(buf, temp, PAGESIZE)) {
	    char *a=buf, *b=temp;
	    int ll;
	    for (ll=0; ll<PAGESIZE; ll++) if (*a++ != *b++) break;
	    fprintf(stdout,"Compression error on page %d at offset 0x%04x\n",
		i,ll);
	    print_buf(buf, ll+DSZ, "src");
	    print_buf(dst, lozero, "compr");
	    print_buf(temp, ll+DSZ, "decompr");
	} 
} else {
        lozero=gzip_compr((DATATYPE *)buf, PAGESIZE,(DATATYPE *) dst);
	
	gettimeofday(&t2, NULL);
	t3=t2;
}
	tot_c.tv_sec += (t2.tv_sec - t1.tv_sec);
	tot_c.tv_usec += (t2.tv_usec - t1.tv_usec);
	if (lozero < PAGESIZE) {
	    tot_d.tv_sec += (t3.tv_sec - t2.tv_sec);
	    tot_d.tv_usec += (t3.tv_usec - t2.tv_usec);
	}
	j= (lozero+GRAIN-1)/GRAIN;
	if (j<PAGESIZE/GRAIN) locomp[j]++;
    }
    printf("--- Compression statistics ---\n");
    l=0;
    lozero=0;
    for (i=0;i<PAGESIZE/GRAIN;i++) {
	l += locomp[i];
	lozero += locomp[i]*i*GRAIN;
	printf("<= %6d    %6d -- %6d\n",
		i*GRAIN, locomp[i], l
		);
    }
    lozero += (npages - l)*PAGESIZE;
    printf("others       %6d\ncompr. fact  %6d%%\n",
	npages - l,
	100*lozero/npages/PAGESIZE
	);
    tot_c.tv_usec += 1000000*tot_c.tv_sec;
    tot_c.tv_sec = tot_c.tv_usec /npages;
    tot_d.tv_usec += 1000000*tot_d.tv_sec;
    tot_d.tv_sec = tot_d.tv_usec /decomp;
    printf ("Compr:   Total %9d usec, %8d usec/page (%d pages)\n",
	tot_c.tv_usec, tot_c.tv_sec, npages);
    printf ("DeCompr: Total %9d usec, %8d usec/page (%d pages)\n",
	tot_d.tv_usec, tot_d.tv_sec, decomp);
}

print_buf(unsigned char *buf, int size, char *s)
{
    int i;
    printf("\n%s\n",s);
    for (i=0; i<size; i+= 4) {
	if ( (i& 0xf) ==0) printf("%04x: ",i);
	printf("%02x ", *buf++);
	printf("%02x ", *buf++);
	printf("%02x ", *buf++);
	printf("%02x%s", *buf++,
	    (i& 0xc) ==0xc ? "\n" : "   ");
    }
}