coder_sh_o1sb.c

用C++语言实现的基于小波分析的源代码,实现了小波分析的诸多算法

//#define PACK_SIGNS_AND_RESIDUALS	
	/** helps compression 0.02 bpp, doesn't affect speed much ;
		turning this off does amortize the damage for small flush_quanta **/
//#define LOG
//#define DEBUG

/*********

SH_O1SB : Static-Huff Order1-SigBit

	(similar to _o1_sb_ the older arithcoder version)

see coder_sh_o1.c for more notes

**********/

#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/huffa.h>
#include <crblib/intmath.h>

#include "coder.h"

extern int tune_param;

#define SH_FLUSH_QUANTUM 	(1<<16)	/** this really hates to be small **/
#define MERGE_LEN			(1<<10)

#define ORDER1_RAWS			8		/** the optimum seems to be infinity, which turns this into a non-SB coder! **/

#define CN_MAX_PREV			4
#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_O1SB_init(coder *c);
void coderSH_O1SB_free(coder *c);
void coderSH_O1SB_flush(coder *c);
void coderSH_O1SB_encodeBand(coder *me,int *band,int w,int h,int fullw,int *parent);
void coderSH_O1SB_decodeBand(coder *me,int *band,int w,int h,int fullw,int *parent);

coder coderSH_O1SB = {
		"SH O1 SB",
		coderSH_O1SB_init,
		coderSH_O1SB_free,
		coderSH_O1SB_encodeBand,
		coderSH_O1SB_decodeBand,
		NULL,NULL,NULL,NULL,NULL,NULL,
		coderSH_O1SB_flush
	};

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

static void coderSH_O1SB_getHunk(myInfo *mi);
static void coderSH_O1SB_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_O1SB_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->merge_array = newarray(ubyte,alloc_len)) == NULL )
		errexit("malloc failed");

	if ( (d->signs_array = newarray(ubyte,alloc_len)) == NULL )
		errexit("malloc failed");
	if ( (d->residuals_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");

	if ( (d->residuals_bi = BitIO_Init(d->residuals_array)) == NULL )
		errexit("bitio init failed");

return;
}

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

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

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

		d = c->data;

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

		smartfree(d->merge_array);
		smartfree(d->signs_array);
		smartfree(d->residuals_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_O1SB_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_O1SB_putHunk(mi);
}

void coderSH_O1SB_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_O1SB_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_O1SB_putHunk(myInfo *mi)
{
int i,len,merged;
int n_signs,n_residuals;
struct LBitIOInfo * BII;
ubyte *merge_ptr;
#ifdef LOG
int signs_out,residuals_out;
#endif

/** flush out work bitios **/

	n_signs = BitIO_FlushWrite(mi->signs_bi);
	n_residuals = BitIO_FlushWrite(mi->residuals_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);
	cu_putExpanding_bii(n_residuals,BII,12,4);

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

#ifdef PACK_SIGNS_AND_RESIDUALS

	O0HuffArrayBII(mi->signs_array,n_signs,BII,true);

#ifdef LOG
	signs_out = LBitio_GetPos(BII);
#endif

	O0HuffArrayBII(mi->residuals_array,n_residuals,BII,true);

#ifdef LOG
	residuals_out = LBitio_GetPos(BII) - signs_out;
	printf("signs : %d -> %d , residuals : %d -> %d\n",n_signs,signs_out,n_residuals,residuals_out);
#endif

#endif //  PACK_SIGNS_AND_RESIDUALS

// 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_AND_RESIDUALS
	memcpy(mi->comp_ptr,mi->signs_array,n_signs); mi->comp_ptr += n_signs;
	memcpy(mi->comp_ptr,mi->residuals_array,n_residuals); mi->comp_ptr += n_residuals;
#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);
	BitIO_ResetArray(mi->residuals_bi,mi->residuals_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_O1SB_getHunk(myInfo *mi)
{
int i,len,merged;
int n_signs,n_residuals;
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);
	n_residuals = cu_getExpanding_bii(BII,12,4);

#ifdef LOG
	printf("coded : %d , signs : %d, residuals : %d\n",mi->coded_pels,n_signs,n_residuals);
#endif

// dehuff mi->signs_array 
// dehuff mi->residuals_array

#ifdef PACK_SIGNS_AND_RESIDUALS
	O0HuffArrayBII(mi->signs_array,n_signs,BII,false);
	O0HuffArrayBII(mi->residuals_array,n_residuals,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;

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

#ifndef PACK_SIGNS_AND_RESIDUALS
	memcpy(mi->signs_array,mi->comp_ptr,n_signs); mi->comp_ptr += n_signs;
	memcpy(mi->residuals_array,mi->comp_ptr,n_residuals); mi->comp_ptr += n_residuals;
#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

/** 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_ResetArray(mi->residuals_bi,mi->residuals_array);

	BitIO_InitRead(mi->signs_bi);
	BitIO_InitRead(mi->residuals_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;
	} else {

		if ( isneg(sym) ) { BitIO_WriteOneBit(mi->signs_bi); sym = -sym; }
		else BitIO_WriteZeroBit(mi->signs_bi);

		if ( sym < ORDER1_RAWS ) { 
			*(mi->sigbits[context])++ = sym;
		} else {
			int bits,msb;

			sym -= (ORDER1_RAWS-1); 	/** can't use zero **/
			bits = intlog2(sym);

#if 0
printf("%d %d\n",sym,bits);
#endif

			*(mi->sigbits[context])++ = bits + ORDER1_RAWS;

			msb = (1<<bits);

#ifdef DEBUG
			assert( sym >= msb );
#endif

			sym -= msb;

#ifdef DEBUG
			assert( sym < msb );
#endif

			for(msb>>=1;msb>=1;msb>>=1) {
				BitIO_WriteBit(mi->residuals_bi,((sym&msb)?1:0));
			}
		}
	}
}

static int decode_val(myInfo *mi,int context)
{
int bits;

	bits = *(mi->sigbits[context])++;
	if ( bits == 0 ) return 0;
	else if ( bits < ORDER1_RAWS ) {
		int sign;
		BitIO_ReadBit(mi->signs_bi,sign);
		if ( sign ) return -bits;
		else return bits;
	} else {
		int msb,sym,sign;

		msb = 1<<(bits - ORDER1_RAWS);
		sym = msb + ORDER1_RAWS - 1;
		for(msb>>=1;msb>=1;msb>>=1) {
			BitIO_ReadBit(mi->residuals_bi,sign);
			if ( sign ) sym += msb;
		}

#if 0
printf("%d %d\n",sym,bits-1);
#endif

		BitIO_ReadBit(mi->signs_bi,sign);
		if ( sign ) return -sym;
		else 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));
}