coder_o2.c

好东西呢

/*********

Order2 : o2 on MSB's

S+P (512) Lossless :

			Lena	Zelda	Kuha	Checa(256)
Order1 	:	4.250	3.948	3.534	3.406
Order1+1:	4.207	3.911	3.517	3.310
Order1sb:	4.216	3.920	3.510	3.305
order2	:	4.222	3.928	3.511	3.308

We're uniformly beaten by the order1 coders.  This is
strong evidence that we can do no better than order1. (sigh)

	-> this is not quite right.  height data (golf courses)
		and digitial images (circles & crosses .256) are
		better under order2

------

todos :

	1. different order0 for each bit-position of residuals, ?
		(since the lowest bit-pos will be very random,
		highers should be more zero-skewed)

	2. different order1 contexts?  average of neighbor & parent?

**********/

#include <stdio.h>
#include <stdlib.h>
#include <crblib/inc.h>
#include <crblib/arithc.h>
#include <crblib/scontext.h>
#include <crblib/intmath.h>

extern int tune_param;

// #define SMEAR_PARENT // hurts 0.03 !?

#define ORDER2_TOTMAX		6000
#define ORDER2_INC			30
#define ORDER2_ESCINC		30

#define ORDER1_TOTMAX		10000
#define ORDER1_INC			30

#define MSB_RAWS			1
#define MSB_ALPHABET		(18 + MSB_RAWS)	/** # of bits **/

#define O2_MAX_PREV			3
#define O2_MAX_PARENT		5
#define O2_CONTEXTS 		(1 + O2_MAX_PREV + (O2_MAX_PREV+1)*O2_MAX_PARENT)
#define O1_MAX_PARENT		2	/** zero seems optimal, which makes this into order-1, not order-2 ! **/
#define O1_CONTEXTS			(O1_MAX_PARENT+1)

#define ORDER0_TOTMAX		16000	/** totally irrelevant **/
#define ORDER0_ALPHABET		2		/** binary **/
#define ORDER0_INC			10

#include "coder.h"

void coderO2_encodeBand(coder *me,int *band,int w,int h,int fullw,int *parent);
void coderO2_decodeBand(coder *me,int *band,int w,int h,int fullw,int *parent);

typedef struct {
	scontext *o0;
	scontext *sign_sc[3];
	scontext **o1,**o2;
	arithInfo *ari;
} myInfo;

void coderO2_init(coder *c)
{
myInfo *d;
int i;

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

	c->data = d;
	d->ari = c->arith;

	if ( (d->o0 = scontextCreate(c->arith,ORDER0_ALPHABET,0,
			ORDER0_TOTMAX,ORDER0_INC,true)) == NULL )
		errexit("ozero init failed");

	for(i=0;i<3;i++) {
		if ( (d->sign_sc[i] = scontextCreate(c->arith,2,0,1000,10,true)) == NULL )
			errexit("sign ozero init failed");
	}

	if ( (d->o1 = newarray(void *,O1_CONTEXTS)) == NULL )
		errexit("Order1_Init failed!");

	for(i=0;i<O1_CONTEXTS;i++) {
		if ( (d->o1[i] = scontextCreate(c->arith,MSB_ALPHABET,0,
				ORDER1_TOTMAX,ORDER1_INC,true)) == NULL )
			errexit("context o1 creation failed!");
	}

	if ( (d->o2 = newarray(void *,O2_CONTEXTS)) == NULL )
		errexit("Order2_Init failed!");

	for(i=0;i<O2_CONTEXTS;i++) {
		if ( (d->o2[i] = scontextCreate(c->arith,MSB_ALPHABET,
				ORDER2_ESCINC,ORDER2_TOTMAX,ORDER2_INC,false)) == NULL )
			errexit("context o2 creation failed!");
	}
}

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

		d = c->data;
		if ( d->o0 ) scontextFree(d->o0);
		for(i=0;i<3;i++) {
			if ( d->sign_sc[i] ) scontextFree(d->sign_sc[i]);
		}
		if ( d->o1 ) {
			for(i=0;i<O1_CONTEXTS;i++) {
				if ( d->o1[i] ) scontextFree(d->o1[i]);
			}
		}
		if ( d->o2 ) {
			for(i=0;i<O2_CONTEXTS;i++) {
				if ( d->o2[i] ) scontextFree(d->o2[i]);
			}
		}
		free(d);
		c->data = NULL;
	}
}

coder coderO2 = {
		"order 2",
		coderO2_init,
		coderO2_free,
		coderO2_encodeBand,
		coderO2_decodeBand
	};

static void mcontext(int *cur_ptr,int *parent_ptr,int x,int y,int width,int height,int fullw,
	int *cntx1_ptr,int *cntx2_ptr,int *sign_ptr)
{
int neighbors,parent;

	/** 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;
	}

if ( neighbors == 0 ) *sign_ptr = 2;
else if ( isneg(neighbors) ) *sign_ptr = 1;
else *sign_ptr = 0;

#ifdef SMEAR_PARENT
if ( x >= 2 && x < (width-2) ) {
	parent = abs(parent_ptr[0] + parent_ptr[0] + parent_ptr[-1] + parent_ptr[1] + 2);
	parent >>= 2;
} else {
	parent = abs(*parent_ptr);
}
#else
	parent = abs(*parent_ptr);
#endif // SMEAR_PARENT

*cntx1_ptr = min(O1_MAX_PARENT,parent);

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

*cntx2_ptr = min(O2_MAX_PREV,neighbors) + (O2_MAX_PREV+1)*(min(O2_MAX_PARENT,parent));

}

static void encode_val(myInfo *mi,int sym,int cntx1,int cntx2)
{
	if ( sym < MSB_RAWS ) {
		if ( ! scontextEncode(mi->o2[cntx2],sym) )
			scontextEncode(mi->o1[cntx1],sym);
	} else {
		int bits,msb;
		sym -= (MSB_RAWS-1); 	/** can't use zero **/
		bits = intlog2(sym);
		msb = (1<<bits);
		sym -= msb;
		bits += MSB_RAWS;

		if ( ! scontextEncode(mi->o2[cntx2],bits) )
			scontextEncode(mi->o1[cntx1],bits);

		/** sym < msb now **/
		msb>>=1;
		for(;msb>=1;msb>>=1) {
			scontextEncode(mi->o0,(sym&msb)?1:0);
		}
	}
}

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

if ( (bits = scontextDecode(mi->o2[cntx2])) == - 1) {
	bits = scontextDecode(mi->o1[cntx1]);
	scontextAdd(mi->o2[cntx2],bits);
}

	if ( bits < MSB_RAWS ) {
		return bits;
	} else {
		int msb,sym,top;
		bits -= MSB_RAWS;
		msb = 1<<bits;
		sym = 0;
		for(top = msb>>1;top>=1;top>>=1) {
			if ( scontextDecode(mi->o0) ) sym += top;
		}
		sym += msb + MSB_RAWS - 1;
		return sym;
	}
}

void coderO2_encodeBand(coder *me,int *band,int width,int height,int fullw,int *parent)
{
int x,y,val,cntx1,cntx2,sign,sign_cntx;
int *dp,*pp,*dpp,*ppp;
myInfo *mi = ((myInfo *)me->data);
scontext **sign_sc = ((myInfo *)me->data)->sign_sc;

	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++) {
			mcontext(dpp,ppp,x,y,width,height,fullw,&cntx1,&cntx2,&sign_cntx);

			val = *dpp++;	if ( x&1 ) ppp++;

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

			encode_val(mi,val,cntx1,cntx2);

			if ( val != 0 )
				scontextEncode(sign_sc[sign_cntx],sign);
		}
		if ( y & 1 ) pp += fullw;
		dp += fullw;
	}
}

void coderO2_decodeBand(coder *me,int *band,int width,int height,int fullw,int *parent)
{
int x,y,val,cntx1,cntx2,sign_cntx;
int *dp,*pp,*dpp,*ppp;
myInfo *mi = ((myInfo *)me->data);
scontext **sign_sc = ((myInfo *)me->data)->sign_sc;

	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++) {
			mcontext(dpp,ppp,x,y,width,height,fullw,&cntx1,&cntx2,&sign_cntx);

			val = decode_val(mi,cntx1,cntx2);
			if ( val != 0 )
				if ( scontextDecode(sign_sc[sign_cntx]) ) val = -val;

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