coder_sh_o1.c

基于小波的图像压缩

//#define PACK_SIGNS	//helps about 0.007
//#define LOG
//#define DEBUG

/*********

SH_O1 : Static-Huff Order1	(not sigbit)

	(similar to _o1_sb_ the older arithcoder version)

compression is surprisingly competitive (off 0.1 bpp from bitplane) on
	hi-fi files (quantizer < 4) (at large quant, the probability of zero
	becomes too large for us).

at large quantizer (eg. 20) the histogram looks like :
	P(0) = 99.98 %
	P(1) = 00.02 %
	P(>1) = zero
Huffman does not handle this well.  We could compensate by run-lengthing
the zeros.

speed is much worse than anticipated (only slightly better than BP).

all arrays need to be self-extending !!! (copy order1-huff)

**********/

#include <stdio.h>
#include <stdlib.h>
#include <crblib/inc.h>
#include <crblib/bbitio.h>
#include <crblib/lbitio.h>
#include <crblib/codeutil.h>
#include <crblib/crc32.h>
#include <crblib/runtrans.h>

#include "coder.h"

extern int tune_param;

#define SH_FLUSH_QUANTUM 	(1<<17)	/** <> decreasing this hurts a lot, unfortunately! **/
#define MERGE_LEN			(1<<11)

#define ORDER1_RAWS			2
#define ORDER1_ALPHABET		(16 + ORDER1_RAWS)	/** # of bits **/

#define CN_MAX_PREV			2
#define CN_MAX_PARENT		4
#define CODE_CONTEXTS 		(1 + CN_MAX_PREV + (CN_MAX_PREV+1)*CN_MAX_PARENT)

/*** the protos and structs ******/

void coderSH_O1_init(coder *c);
void coderSH_O1_free(coder *c);
void coderSH_O1_flush(coder *c);
void coderSH_O1_encodeBand(coder *me,int *band,int w,int h,int fullw,int *parent);
void coderSH_O1_decodeBand(coder *me,int *band,int w,int h,int fullw,int *parent);

coder coderSH_O1 = {
		"StatHuff O1",
		coderSH_O1_init,
		coderSH_O1_free,
		coderSH_O1_encodeBand,
		coderSH_O1_decodeBand,
		NULL,NULL,NULL,NULL,NULL,NULL,
		coderSH_O1_flush
	};

typedef struct {
	coder *coder;
	int coded_pels;
	ubyte * comp_ptr;
	bitInfo * signs_bi;
		ubyte * signs_array;
	ubyte ** sigbits_array;
	ubyte ** sigbits;
	ubyte * merge_array;
} myInfo;

static void coderSH_O1_getHunk(myInfo *mi);
static void coderSH_O1_putHunk(myInfo *mi);

static void encode_val(myInfo *mi,int sym,int context);
static int decode_val(myInfo *mi,int context);

static int mcontext(int *cur_ptr,int parent,int x,int y,int width,int height,int fullw);

/********* the functions *********/

void coderSH_O1_init(coder *c)
{
myInfo *d;
int i,alloc_len;

	if ( (d = new(myInfo)) == NULL )
		errexit("malloc failed");

	d->coder = c;
	c->data = d;

	d->coded_pels = 0;
	d->comp_ptr = c->w->comp;

	alloc_len = c->w->width * c->w->height * c->w->planes;

	if ( (d->signs_array = newarray(ubyte,alloc_len)) == NULL )
		errexit("malloc failed");
	if ( (d->merge_array = newarray(ubyte,alloc_len)) == NULL )
		errexit("malloc failed");

	if ( (d->sigbits_array = newarray(ubyte *,CODE_CONTEXTS)) == NULL )
		errexit("malloc failed");
	if ( (d->sigbits = newarray(ubyte *,CODE_CONTEXTS)) == NULL )
		errexit("malloc failed");

	for(i=0;i<CODE_CONTEXTS;i++) {
		if ( (d->sigbits_array[i] = newarray(ubyte,alloc_len)) == NULL )
			errexit("malloc failed");
		d->sigbits[i] = d->sigbits_array[i];
	}

	if ( (d->signs_bi = BitIO_Init(d->signs_array)) == NULL )
		errexit("bitio init failed");

return;
}

void coderSH_O1_flush(coder *c)
{
	if ( c->data ) {
		myInfo *d;
		d = c->data;

		if ( d->coded_pels > 0 )
			coderSH_O1_putHunk(d);
	}
}

void coderSH_O1_free(coder *c)
{
	if ( c->data ) {
		myInfo *d;
		int i;

		d = c->data;

		if ( d->signs_bi ) BitIO_CleanUp(d->signs_bi);

		smartfree(d->signs_array);
		smartfree(d->merge_array);
		smartfree(d->sigbits);
		if( d->sigbits_array ) {
			for(i=0;i<CODE_CONTEXTS;i++) smartfree(d->sigbits_array[i]);
			free(d->sigbits_array);
		}

		free(d);
		c->data = NULL;
	}
}

void coderSH_O1_encodeBand(coder *me,int *band,int width,int height,int fullw,int *parent)
{
int x,y;
int *dp,*pp,*dpp,*ppp;
myInfo *mi = ((myInfo *)me->data);

	dp = band;
	pp = parent;
	for(y=0;y<height;y++) {
		dpp = dp; ppp = pp;
		if ( coder_timetostop(me) ) { coder_didstop(me,y); return; }
		for(x=0;x<width;x++) {
			encode_val(mi,*dpp++, mcontext(dpp,*ppp,x,y,width,height,fullw) );

			if ( x&1 ) ppp++;
		}
		if ( y & 1 ) pp += fullw;
		dp += fullw;
	}

	mi->coded_pels += width*height;
	if ( mi->coded_pels >= SH_FLUSH_QUANTUM ) 
		coderSH_O1_putHunk(mi);
}

void coderSH_O1_decodeBand(coder *me,int *band,int width,int height,int fullw,int *parent)
{
int x,y;
int *dp,*pp,*dpp,*ppp;
myInfo *mi = ((myInfo *)me->data);

	if ( mi->coded_pels == 0 )
		coderSH_O1_getHunk(mi);

	dp = band;
	pp = parent;
	for(y=0;y<height;y++) {
		dpp = dp; ppp = pp;
		if ( coder_timetostopd(me,y) ) return;
		for(x=0;x<width;x++) {
			*dpp++ = decode_val(mi, mcontext(dpp,*ppp,x,y,width,height,fullw) );

			if ( x&1 ) ppp++;
		}
		if ( y & 1 ) pp += fullw;
		dp += fullw;
	}

	mi->coded_pels -= width*height;
}

static void coderSH_O1_putHunk(myInfo *mi)
{
int i,len,merged;
int n_signs;
struct LBitIOInfo * BII;
ubyte *merge_ptr;

/** flush out work bitios **/

	n_signs = BitIO_FlushWrite(mi->signs_bi);

/** write mi->coded_pels, other lengths **/

	if ( (BII = LBitIO_Init(mi->comp_ptr)) == NULL  )
		errexit("lbitio init failed!");

	cu_putExpanding_bii(mi->coded_pels,BII,15,4);
	cu_putExpanding_bii(n_signs,BII,12,4);

// huff mi->signs_array into mi->code_bi

#ifdef PACK_SIGNS
	O0HuffArrayBII(mi->signs_array,n_signs,BII,true);
#endif

// huff all the sigbits

	merge_ptr = mi->merge_array;
	merged = 0;

	for(i=0;i<CODE_CONTEXTS;i++) {
		len = mi->sigbits[i] - mi->sigbits_array[i];
		cu_putExpanding_bii(len,BII,12,4);
		if ( len <= MERGE_LEN ) {
			memcpy(merge_ptr,mi->sigbits_array[i],len);
			merge_ptr += len; merged += len;
		}
	}

	O0HuffArrayBII_RT(mi->merge_array,merged,BII,true);	

	for(i=0;i<CODE_CONTEXTS;i++) {
		len = mi->sigbits[i] - mi->sigbits_array[i];
		if ( len > MERGE_LEN ) {
			O0HuffArrayBII_RT(mi->sigbits_array[i],len,BII,true);	
		}
	}

	len = LBitIO_FlushWrite(BII);
	mi->comp_ptr += len;

#ifndef PACK_SIGNS
	memcpy(mi->comp_ptr,mi->signs_array,n_signs); 
	mi->comp_ptr += n_signs;
#endif

#ifdef DEBUG
	*((ulong *)mi->comp_ptr) = crc32(mi->merge_array,merged);
	mi->comp_ptr += 4;
#endif

#ifdef LOG
	printf("putHunk : %d -> %d\n",mi->coded_pels,len);
#endif

/** now reset for another pass **/

	BitIO_ResetArray(mi->signs_bi,mi->signs_array);

	for(i=0;i<CODE_CONTEXTS;i++) mi->sigbits[i] = mi->sigbits_array[i];

	mi->coded_pels = 0;

	/** fix up the main coding structures in case this is the last
	*	Hunk we're decoding
	***/

	arithEncodeReInit(mi->coder->arith,mi->comp_ptr);
}

static void coderSH_O1_getHunk(myInfo *mi)
{
int i,len,merged;
int n_signs;
struct LBitIOInfo * BII;
ubyte *merge_ptr;

/** read mi->coded_pels, other lengths **/

	if ( (BII = LBitIO_Init(mi->comp_ptr)) == NULL  )
		errexit("lbitio init failed!");

	LBitIO_InitRead(BII);

	mi->coded_pels = cu_getExpanding_bii(BII,15,4);
	n_signs = cu_getExpanding_bii(BII,12,4);

// dehuff mi->signs_array 

#ifdef PACK_SIGNS
	O0HuffArrayBII(mi->signs_array,n_signs,BII,false);
#endif

// huff all the sigbits

	merged = 0;

	for(i=0;i<CODE_CONTEXTS;i++) {
		mi->sigbits[i] = mi->sigbits_array[i] + cu_getExpanding_bii(BII,12,4);
		len = mi->sigbits[i] - mi->sigbits_array[i];
		if ( len <= MERGE_LEN ) merged += len;
	}

	O0HuffArrayBII_RT(mi->merge_array,merged,BII,false);
	merge_ptr = mi->merge_array;

	for(i=0;i<CODE_CONTEXTS;i++) {
		len = mi->sigbits[i] - mi->sigbits_array[i];
		if ( len <= MERGE_LEN ) {
			memcpy(mi->sigbits_array[i],merge_ptr,len);
			merge_ptr += len;
		} else {
			O0HuffArrayBII_RT(mi->sigbits_array[i],len,BII,false);	
		}
	}

// done

	len = LBitIO_GetPos(BII) - 4;	/* <> same as flushWrites' return? */
	mi->comp_ptr += len;

#ifndef PACK_SIGNS
	memcpy(mi->signs_array,mi->comp_ptr,n_signs); 
	mi->comp_ptr += n_signs;
#endif

#ifdef DEBUG
	/**/ {
	ulong crc;
	crc = *((ulong *)mi->comp_ptr); 
	mi->comp_ptr += 4;
	if ( crc == crc32(mi->merge_array,merged) ) {
		errputs("crc checked OK");
	} else {
		errputs("crc failed on signs Uh-Oh");
		dbf();
	}
	/**/ }
#endif

#ifdef LOG
	printf("getHunk : %d -> %d\n",len,mi->coded_pels);
#endif

/** get ready to read from this unpacked hunk **/

	for(i=0;i<CODE_CONTEXTS;i++) mi->sigbits[i] = mi->sigbits_array[i];

	BitIO_ResetArray(mi->signs_bi,mi->signs_array);
	BitIO_InitRead(mi->signs_bi);

	/** fix up the main coding structures in case this is the last
	*	Hunk we're decoding
	***/

	arithDecodeReInit(mi->coder->arith,mi->comp_ptr);
}

static void encode_val(myInfo *mi,int sym,int context)
{
	if ( sym == 0 ) { 	
		*(mi->sigbits[context])++ = 0;
		return;
	} else {
		int sign;

		if ( isneg(sym) ) { sign = 1; sym = -sym; }
		else sign = 0;

		while ( sym >= 0xFF ) {
			*(mi->sigbits[context])++ = 0xFF;
			sym -= 0xFF;
		}
		*(mi->sigbits[context])++ = sym;

		BitIO_WriteBit(mi->signs_bi,sign);
	}

}

static int decode_val(myInfo *mi,int context)
{
	if ( *(mi->sigbits[context]) == 0 ) {
		mi->sigbits[context]++;
		return 0;
	} else {
		int sign,sym,t;

		sym  = 0;
		do {
			t = *(mi->sigbits[context])++;
			sym += t;
		} while( t == 0xFF );

		BitIO_ReadBit(mi->signs_bi,sign);
		if ( sign ) sym = -sym;

		return sym;
	}
}

static int mcontext(int *cur_ptr,int parent,int x,int y,int width,int height,int fullw)
{
int neighbors;

	/** cur_ptr[0] is about to be coded **/

	if ( x==0 ) {
		if ( y == 0 ) {
			neighbors = 0;
		} else {
			neighbors = (cur_ptr[-fullw] + cur_ptr[-fullw+1]) >> 1;
		}
	} else if ( y == 0 ) {
		neighbors = cur_ptr[-1];
	} else if ( x == (width-1) ) {
		neighbors = (cur_ptr[-1] + cur_ptr[-fullw] + cur_ptr[-fullw] + cur_ptr[-fullw-1]) >> 2;
	} else {
		neighbors = (cur_ptr[-1] + cur_ptr[-fullw] + cur_ptr[-fullw+1] + cur_ptr[-fullw-1]) >> 2;
	}

parent = abs(parent);
neighbors = abs(neighbors);
parent = intlog2(parent+1);
neighbors = intlog2(neighbors);

return min(CN_MAX_PREV,neighbors) + (CN_MAX_PREV+1)*(min(CN_MAX_PARENT,parent));
}