cfamily.c

一个简单而且快速的无损压缩算法。包含源代码实现

/* Rodzina kodow moja (wersja bez adjusted binary codes, dla glebi do 16 bpp, ograniczenie dlugosci do 32 bitow) R. Starosolski, W. Skarbek: Modified Golomb-Rice Codes for Lossless Compression of Medical Images", Proceedings of International Conference on E-health in Common Europe, pp. 423-37, Krakow, 2003 */

#include "cfamily.h"
#include "bppmask.h"

static const unsigned int bitat[32] ={
							0x00000001,0x00000002,0x00000004,0x00000008,
							0x00000010,0x00000020,0x00000040,0x00000080,
							0x00000100,0x00000200,0x00000400,0x00000800,
							0x00001000,0x00002000,0x00004000,0x00008000,
							0x00010000,0x00020000,0x00040000,0x00080000,
							0x00100000,0x00200000,0x00400000,0x00800000,
							0x01000000,0x02000000,0x04000000,0x08000000,
							0x10000000,0x20000000,0x40000000,0x80000000 /* [31]*/
							};

static unsigned int nGRcodewords[MAXNUMCODES];		/* dla kolejnych kodow liczby niezmodyfikowanych slow kodu GR w kodzie */
static unsigned int notGRcwlen[MAXNUMCODES];		/* dla kolejnych kodow dlugosc slowa kodowego nie-GR*/
static unsigned int notGRprefixlen[MAXNUMCODES];	/* dla kolejnych kodow dlugosc prefiksu slowa kodowego nie-GR */
static unsigned int notGRsuffixlen[MAXNUMCODES];	/* dla kolejnych kodow dlugosc sufiksu slowa kodowego nie-GR */


/* funkcje krytyczne dla predkosci, na razie tylko kodowanie, eksportowane */


/* argumenty: wartosc do zakodowania:n, numer kodu:l, adres, gdzie nalezy zapisac slowo kodowe:tcw */
void GolombCoding(const unsigned int n, const unsigned int l, 
				  unsigned int * const codeword, unsigned int * const codewordlen)
{
	if(n<nGRcodewords[l])
	{
		(*codeword) = bitat[l] | n & bppmask[l]; 
		(*codewordlen) = (n>>l)+l+1;
	}
	else
	{
		(*codeword) = n-nGRcodewords[l];
		(*codewordlen) = notGRcwlen[l];
	}
}


unsigned int GolombCodeLen(const unsigned int n, const unsigned int l)
{
	if(n<nGRcodewords[l])
		return (n >> l)+1+l;
	else
		return  notGRcwlen[l];
}


/* funkcje nie krytyczne, nie eksportowane */

#include "ceillog2.h"
#include "exitit.h"
#include "clalloc.h"

static unsigned int lzeroes[256];	/* liczba wiodacych zer w bajcie, inicjalizowane w familyinit */

/* pobierz z bufora ile bitow */
void eatbits(unsigned int ile, struct bitinstatus * bs)
{
	bs->bits<<=ile;
	while(ile>bs->inthebyte)
	{
		ile-=bs->inthebyte;
		bs->bits|=(bs->thebyte<<ile);
		bs->thebyte=*bs->readptr++;
		bs->inthebyte=8;
	}
	bs->inthebyte-=ile;
	bs->bits|=(bs->thebyte>>bs->inthebyte);
	if(!bs->inthebyte)
	{
		bs->thebyte=*bs->readptr++;
		bs->inthebyte=8;
	}
}

/* pobierz ile bitow i zwroc jako najmlodsze bity wyniku */
unsigned int getbits(const unsigned int ile, struct bitinstatus * bs)
{
	if(ile)
	{
		const unsigned result=bs->bits>>(32-ile);
		eatbits(ile, bs);
		return result;
	}
	else
		return 0;
}

/* pobierz bity az do napotkania 1 albo do przeczytania max zer */
/* zwr骳 liczbe przeczytanych zer */
/* z bufora usun przeczytane zera i jedynke jezeli byla przeczytana */

unsigned int eatzeroes(const unsigned int max, struct bitinstatus * bs)
{
	if(!(bs->bits & ~bppmask[32-max]))
	{
		eatbits(max, bs);
		return max;
	}
	else
	{
		int cntr=lzeroes[bs->bits>>24];
		if (bs->bits<=0x00ffffff)
		{
			cntr+=lzeroes[bs->bits>>16];
			if (bs->bits<=0x00ffff)
			{
				cntr+=lzeroes[bs->bits>>8];
				if (bs->bits<=0x00ff)
				{
					cntr+=lzeroes[bs->bits>>8];
				}
			}
		}
		eatbits(cntr+1, bs);
		return cntr;
	}
}

/* funkcje eksportowane */


/* rodzina (GOLOMB_MYJPEGLS), przerobiona na glebie do 16+ bpp (sprawdzone do 20) */
/* ograniczenie dlugosci sprawdzone do 32+ bit (40) */
/* ostatnia grupa (golomb lub limit32) kodowana */
/* z prefiksem bez jedynki na koncu, kody binarne */
/* bpp-bitowe lub krotsze */


unsigned int GolombDecoding(const unsigned int l, struct bitinstatus * bs)
{
  /* prefix */

	const unsigned result=eatzeroes(notGRprefixlen[l], bs);

	if (notGRprefixlen[l] != result) /* Golomb */
		return (result<<l)|getbits(l, bs) ;
	else     /* cus innego */
		return nGRcodewords[l]+getbits(notGRsuffixlen[l], bs);	
}

void bitinstatusinit(struct bitinstatus * bs)
{
	bs->bits=*bs->readptr++;	// nowe
	bs->bits<<=8;
	bs->bits|=*bs->readptr++;
	bs->bits<<=8;
	bs->bits|=*bs->readptr++;
	bs->bits<<=8;
	bs->bits|=*bs->readptr++;

	bs->thebyte=*bs->readptr++;
	bs->inthebyte=8;
}


/* inicjalizacja  */
void familyinit(int bpp, int limit)
{
	int l;

	assert(limit<=32);
	assert(bpp<=MAXNUMCODES);
	assert(limit>bpp);

	for (l=0; l<bpp; l++)	/* wypelnij precalc */
	{
		int altprefixlen, altcodewords;

		altprefixlen = limit-bpp;
		if (altprefixlen > (int)(bppmask[bpp-l]))
			altprefixlen=bppmask[bpp-l];

	    altcodewords=bppmask[bpp]+1-(altprefixlen<<l);

		nGRcodewords[l]=(altprefixlen<<l);
		notGRcwlen[l]=altprefixlen+ceil_log_2(altcodewords);
		notGRprefixlen[l]=altprefixlen;				/* needed for decoding only */
		notGRsuffixlen[l]=ceil_log_2(altcodewords); /* needed for decoding only */
	}

	{												/* needed for decoding only */
		int i;
		
		lzeroes[0]=8;
		i=1;
		l=1;

		while (l<256)
		{
			int n=0x01<<(i-1);
			for (; n>0; n--)
				lzeroes[l++]=8-i;

			i++;
		}
	}

	return;
}


/* zwolnienie struktur rodziny kodow - dla porzadku*/
void familyfree()
{
	return;
}