ppmzesc.c

PPMz2压缩方式的源码

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <crblib/inc.h>
#include <crblib/arithc.h>
#include <crblib/intmath.h>
#include "ppmZEsc.h"
#include "config.h"

/*********************************************************************************************/

#define ORDERS 3

int order_bits[ORDERS] = { 7, 15, 16 };
#define order_size(x) (1<<order_bits[(x)])

struct PPMZEsc
{
	uword * esc[ORDERS];
	uword * tot[ORDERS];
};

const int ZEsc_INIT_ESC  =8;
const int ZEsc_INIT_TOT  =12;
const int ZEsc_INIT_SCALE=7;
const int ZEsc_ESC_INC   =17;
const int ZEsc_ESCTOT_INC=1;
const int ZEsc_TOT_INC   =17;

static void PPMZEsc_UpdateStats(PPMZEsc * ei,bool escape); //after GetStats only!

/*********************************************************************************************/

PPMZEsc * PPMZEsc_Create(void)
{
PPMZEsc *ei;
int i,j;

	if ( (ei = new(PPMZEsc)) ==NULL )
		return NULL;

	for(i=0;i<ORDERS;i++)
	{
		if ( (ei->esc[i] = malloc( order_size(i) * sizeof(uword) )) == NULL )
			PPMZEsc_Destroy(ei);
		if ( (ei->tot[i] = malloc( order_size(i) * sizeof(uword) )) == NULL )
			PPMZEsc_Destroy(ei);
	}

	/* seed tables, requires some knowledge of the hash */

	for(i=0;i<ORDERS;i++)
	{
		for(j=0;j<order_size(i);j++)
		{
		int esc,tot;
			esc = j & 0x3; tot = (j>>2)&0x7;
			ei->esc[i][j] = 1 + (ZEsc_INIT_SCALE * esc) + ZEsc_INIT_ESC;
			ei->tot[i][j] = 2 + (ZEsc_INIT_SCALE * tot) + ZEsc_INIT_TOT + ZEsc_INIT_ESC;
		}
	}

return ei;
}

void PPMZEsc_Destroy(PPMZEsc *ei)
{
	if ( ei )
	{
	int i;

		for(i=0;i<ORDERS;i++)
		{
			smartfree( ei->esc[i] );
			smartfree( ei->tot[i] );
		}

		free(ei);
	}
}

void PPMZEsc_Encode(PPMZEsc * ei,arithInfo *ari,ulong cntx,int escC,int totSymC,int order,int numParentSyms,bool escape)
{
int escP,totP;

	assert( escC >= 1 );

	PPMZEsc_GetStats(ei,&escP,&totP,cntx,escC,totSymC,order,numParentSyms);
	PPMZEsc_UpdateStats(ei,escape);

	arithEncBit(ari,totP-escP,totP,escape);

return;
}

bool PPMZEsc_Decode(PPMZEsc * ei,arithInfo *ari,ulong cntx,int escC,int totSymC,int order,int numParentSyms)
{
int escP,totP;
bool escape;

	assert( escC >= 1 );

	PPMZEsc_GetStats(ei,&escP,&totP,cntx,escC,totSymC,order,numParentSyms);

	escape = arithDecBit(ari,totP-escP,totP);

	PPMZEsc_UpdateStats(ei,escape);

return escape;
}

bool PPMZEsc_hash(ulong *hashPtr,ulong cntx,int escC,int totSymC,int PPMorder,int numParentSyms,PPMZEsc *ei)
{
int counts,totP,totC;

	// <> this is only used by PPMDet, everyone else uses See
	//  hence we ignore the Order

	totC = escC + totSymC;
	
	assert( escC >= 1 );
	assert( totC >= 2 );

	// cap it to 2 bits:
	if ( numParentSyms > 3 ) numParentSyms = 3;

/*
	switch(PPMorder) 
	{ // map it to 2 bits
		case 0: case 1: PPMorder = 0; break;
		case 2: case 3: PPMorder = 1; break;
		case 4: case 5: PPMorder = 2; break;
		default: PPMorder = 3; break;
	}
*/

	switch(escC-1) 
	{
		case 0: counts = 0; break;
		case 1: counts = 1; break;
		case 2: counts = 2; break;
		case 3: counts = 3; break;
		default: return false; // don't handle escapes higher than 3
	}

	switch(totC-2)
	{
		case 0: totP = 0; break;
		case 1: totP = 1; break;
		case 2: totP = 2; break;
		case 3: case 4: totP = 3; break;
		case 5: case 6: totP = 4; break;
		case 7: case 8: case 9: totP = 5; break;
		case 10: case 11: case 12: totP = 6; break;
		default: totP = 7; break;
	}
	counts += totP << 2; // total of 5 bits

	/*** this (&0x3) from two next characters is the 'a'/'A'/' '/'\n' flag ***/

/*	hashPtr[2] = counts + (( (cntx&0x7F) + (((cntx>>13)&0x3)<<7) + (PPMorder<<9) )<<5);

	hashPtr[1] = counts + (( ((cntx>>5)&0x3) + (((cntx>>13)&0x3)<<2)
				+ (((cntx>>21)&0x3)<<4) + (((cntx>>29)&0x3)<<6) + (PPMorder<<8) )<<5);

	hashPtr[0] = counts + (PPMorder<<5);
*/

	hashPtr[2] = counts + (( (cntx&0x7F) + (((cntx>>13)&0x3)<<7) + (numParentSyms<<9) )<<5);

	hashPtr[1] = counts + (( ((cntx>>5)&0x3) + (((cntx>>13)&0x3)<<2)
				+ (((cntx>>21)&0x3)<<4) + (((cntx>>29)&0x3)<<6) + (numParentSyms<<8) )<<5);

	hashPtr[0] = counts + (numParentSyms<<5);

return true;
}

static bool hashOk;
static ulong hash[ORDERS]; // save from getP to updateP

void PPMZEsc_GetStats(PPMZEsc * ei,int *escPptr,int *totPptr,ulong cntx,int escC,int totSymC,int PPMorder,int numParentSyms)
{
	
	if ( ! (hashOk = PPMZEsc_hash(hash,cntx,escC,totSymC,PPMorder,numParentSyms,ei)) )
	{
		*escPptr = escC;
		*totPptr = escC + totSymC;
		return;
	}

	{
	int e1,e2,e0,t1,t2,t0,h1,h2,h0;
	int esc,tot;

		// blend by entropy

		e2 = ei->esc[2][hash[2]]; t2 = ei->tot[2][hash[2]];
		e1 = ei->esc[1][hash[1]]; t1 = ei->tot[1][hash[1]];
		e0 = ei->esc[0][hash[0]]; t0 = ei->tot[0][hash[0]];

		h2 = (t2<<12)/(t2 * ilog2r(t2) - e2 * ilog2r(e2) - (t2-e2) * ilog2r(t2-e2) + 1);
		h1 = (t1<<12)/(t1 * ilog2r(t1) - e1 * ilog2r(e1) - (t1-e1) * ilog2r(t1-e1) + 1);
		h0 = (t0<<12)/(t0 * ilog2r(t0) - e0 * ilog2r(e0) - (t0-e0) * ilog2r(t0-e0) + 1);

		tot = (h0 + h1 + h2);
		esc = (e2*h2/t2 + e1*h1/t1 + e0*h0/t0);

		while ( tot >= 16000 )
		{
			tot >>= 1; esc >>= 1;
		}

		if ( esc < 1 ) esc = 1;
		if ( esc >= tot ) tot = esc + 1;

		*escPptr = esc;
		*totPptr = tot;
	}
}

static void PPMZEsc_UpdateStats(PPMZEsc * ei,bool escape)
{
ulong h;
int order;

	if ( ! hashOk )
		return;

	for(order=ORDERS-1;order>=0;order--)
	{
	uword *pEsc,*pTot;

		h = hash[order];
		pEsc = ei->esc[order] + h;
		pTot = ei->tot[order] + h;

		if ( escape )
		{
			*pEsc += ZEsc_ESC_INC;
			*pTot += ZEsc_ESC_INC + ZEsc_ESCTOT_INC;
		}
		else
		{
			*pTot += ZEsc_TOT_INC;
		}

		if ( *pTot > 16000 )
		{
			*pTot >>= 1;
			*pEsc >>= 1;
			if ( *pEsc < 1 )
				*pEsc = 1;
		}
	}
}