qbit.c

Quad Tree Bit Plane Compression. A program to compress images. Qbit is an image viewer that loads

// quad tree bit plane compression
// Doug Houghton July 2, 2000
// revised April 28, 2002
// 
// ---------------------------------------------------
// THIS SOFTWARE IS FREE AND PROVIDED AS IS WITH NO GAURANTEE OF ANY KIND FOR 
// IT'S  QUALITY, ACCURACY OR RELIABILITY.  THE AUTHOR IS IN NO WAY LIABLE FOR 
// ANY DAMAGES RESULTING FROM OR RELATED TO THE USE OF THIS SOFTWARE. USE AT 
// OWN RISK.
// ---------------------------------------------------
#include <stdlib.h>
#include <string.h>
#include "qbit.h"

#define COLLAPSE_LEAF 16
#define COLLAPSE_CACHE_MAX 65535

typedef struct tagMETRICS
{
	Qbyte *startstream;
	Qlong width;
	Qlong height;
	Qlong bitdepth;
	Qlong bytedepth;
	Qlong nextmask;
	Qlong shifty;
	Qlong scanpad;
	Qlong bitlu[256];
	Qlong weight[256];
	Qlong unweight0[256];
	Qlong unweight1[256];
	Qlong unweight2[256];
	Qlong collapsebits;
	Qlong maxbit;
	Qlong allbits;
	Qlong leadingbits;
	Qlong *dhash;
	Qint *masks;
} METRICS;


typedef struct tagSTREAM
{
	Qbyte *start;
	Qbyte *current;
	Qbyte low;
}STREAM;


typedef struct tagREGISTERS
{
	Qlong init;
	Qlong current;
	Qlong lastreg;
	Qlong masks[12];
	Qlong registers[12];
	Qlong shifts[12];
}REGISTERS;

typedef struct tagCACHE
{
	Qlong colour;
	Qlong index;
}CACHE;


#define LOCATION(x,y,metrics) metrics->startstream + (y * metrics->shifty) + (x * metrics->bytedepth)

#define PUT_COLOUR_TRUE_ADVANCE(source, colour) {source[0] = (colour >> 16) & 255; source[1] = (colour >> 8) & 255; source[2] = colour & 255; source += 3;}
#define PUT_COLOUR_HIGH_ADVANCE(source, colour) {source[0] = (colour >> 8) & 255; source[1] = colour & 255; source += 2;}
#define PUT_COLOUR_DWORD_ADVANCE(source, colour) {source[0] = (colour >> 24) & 255; source[1] = (colour >> 16) & 255; source[2] = (colour >> 8) & 255; source[3] = colour & 255; source += 4;}

#define GET_COLOUR_TRUE(source) (Qlong)(source[0] << 16) | (source[1] << 8) | source[2]
#define GET_COLOUR_HIGH(source)	(Qlong)(source[0] << 8) | source[1]
#define GET_COLOUR_DWORD(source)	(Qlong)(source[0] << 24) | (source[1] << 16) | (source[2] << 8) | source[3]

#define UNMAP_TRUE(metrics, colour) (Qlong)metrics->unweight0[(colour >> 16) & 255] | metrics->unweight1[(colour >> 8) & 255] | metrics->unweight2[colour & 255]
#define UNMAP_HIGH(metrics, colour) (Qlong)metrics->unweight0[(colour >> 8) & 255] | metrics->unweight1[colour & 255]

#define MAPWEIGHT_TRUE(metrics, source) (Qlong)metrics->weight[source[0]] | (metrics->weight[source[1]] >> 1) | (metrics->weight[source[2]] >> 2)
#define MAPWEIGHT_HIGH(metrics, source) (Qlong)metrics->weight[source[0]] | (metrics->weight[source[1]] >> 1)

//#define READ_QUAD(buffer) buffer->low? *(buffer->current++) & 15:*(buffer->current) >> 4; {buffer->low = !buffer->low;}
#define WRITE_QUAD(buffer, quad) if (buffer->low){*(buffer->current) = (quad & 15); buffer->low = 0;} else { *(buffer->current) |= (quad << 4); buffer->current--; buffer->low = 255;}


// encode
int encodetile(Qlong, Qlong, Qlong, METRICS *, STREAM *, Qbyte *, Qlong);
void encodeblock(Qlong, Qlong, METRICS *, Qbyte *);
void getquad(Qlong *, Qlong, Qlong, METRICS *);
Qlong collapseall(METRICS *, STREAM *);
Qlong bin(Qlong, Qlong, Qlong *, Qlong);
Qlong collapse(Qlong, Qlong, METRICS *, STREAM *, Qlong, Qlong);
void regout(REGISTERS *, STREAM *, Qlong);


// decode
void decodetile(Qlong, Qlong, METRICS *, Qlong, Qlong, Qlong, Qlong, STREAM *);
void decodeblock(Qlong, Qlong, METRICS *, Qlong, Qlong);
void uncollapse(Qlong, Qlong, METRICS *, STREAM *, Qlong);
Qlong *readpal(Qlong *, Qlong, STREAM *, Qlong);
Qbyte readquad(STREAM *);


//
void getmetrics(METRICS *, Qlong, Qlong, Qlong, Qlong, Qlong, Qlong *);


// debug
long debugcount;
long getdebugcount(void) {return(debugcount);}



// ================================================
// this function is called by both decoding
// and encoding processes.  i set's up the
// metrics struct with lookup tables, image dimentions,
// data pointers etc...
// ---------------------------------------
void getmetrics(
	METRICS *metrics,
	Qlong width,
	Qlong height,
	Qlong depth,
	Qlong flags,
	Qlong options,
	Qlong *span)
{

	long i, j, align;
	Qlong bit, shift;

	if (options & QBIT_OPTION_INT_ALIGNED)
		align = 2;
	else if (options & QBIT_OPTION_NOT_ALIGNED)
		align = 0;
	else
		align = 4;

	metrics->width = width;
	metrics->height = height;
	metrics->bitdepth = depth;
	metrics->bytedepth = depth / 8;
	metrics->shifty = width * metrics->bytedepth;

	if (align)
		metrics->scanpad = (metrics->shifty % align)? align - (metrics->shifty % align): 0;
	else
		metrics->scanpad = 0;

	metrics->shifty += metrics->scanpad;


	metrics->maxbit = 128;
	metrics->allbits = 255;
	for (i = 1; i < metrics->bytedepth; i++)
	{
		metrics->maxbit *= 256;
		metrics->allbits *= 256;
		metrics->allbits |= 255;
	}

	metrics->leadingbits = 8;
	for (i = 1; i < 8; i++)
	{
		metrics->leadingbits *= 16;
		metrics->leadingbits |= 8;
	}

	// generate a look up table for getting coverage masks
	for (i = 0; i < 256; i++)
	{
		metrics->bitlu[i] = 0;
		for(bit = 128, j = 24; bit; bit >>= 1, j -= 3)
			metrics->bitlu[i] |= (i & bit) << j;
	}

	// square the image
	*span = 4;
	while ((*span < metrics->width) || (*span < metrics->height))
		*span <<= 1;

	metrics->collapsebits = 0;

	if (flags & QBIT_COMPRESS)
	{
		// process every second level down to the last
		// make sure to skip the first tilesize
		for(bit = COLLAPSE_LEAF; bit < (*span >> 1) ; bit <<= 2)
			metrics->collapsebits |= bit;

		for (i = 0; i < 256; i++)
		{
			metrics->weight[i] = 0;
			switch(depth)
			{
			case 24:

				for(bit = 128, shift = 16; bit; shift -= 2, bit >>= 1)
					metrics->weight[i] |= (i & bit) << shift;

				// mapping to undo the weighting
				metrics->unweight0[i] =
					  ((i & 128) << 16)	// 1 of 0
					| ((i & 64) << 9) 	// 1 of 1
					| ((i & 32) << 2) 	// 1 of 2
					| ((i & 16) << 18) 	// 2 of 0
					| ((i & 8) << 11) 	// 2 of 1
					| ((i & 4) << 4) 	// 2 of 2
					| ((i & 2) << 20) 	// 3 of 0
					| ((i & 1) << 13); 	// 3 of 1

				metrics->unweight1[i] =
					  ((i & 128) >> 2)	// 3 of 2
					| ((i & 64) << 14)  // 4 of 0
					| ((i & 32) << 7) 	// 4 of 1
					| (i & 16) 			// 4 of 2
					| ((i & 8) << 16)  	// 5 of 0
					| ((i & 4) << 9) 	// 5 of 1
					| ((i & 2) << 2)  	// 5 of 2
					| ((i & 1) << 18); 	// 6 of 0

				metrics->unweight2[i] =
					  ((i & 128) << 3)	// 6 of 1
					| ((i & 64) >> 4)  	// 6 of 2
					| ((i & 32) << 12) 	// 7 of 0
					| ((i & 16) << 5)	// 7 of 1
					| ((i & 8) >> 2)  	// 7 of 2
					| ((i & 4) << 14) 	// 8 of 0
					| ((i & 2) << 7)  	// 8 of 1
					| (i & 1); 	// 8 of 2
				break;
			case 16:


				for(bit = 128, shift = 8; bit; shift -= 1, bit >>= 1)
					metrics->weight[i] |= (i & bit) << shift;

				// mapping to undo the weighting
				metrics->unweight0[i] =
					  ((i & 128) << 8)	// 1 of 0
					| ((i & 64) << 1) 	// 1 of 1
					| ((i & 32) << 9) 	// 2 of 0
					| ((i & 16) << 2) 	// 2 of 1
					| ((i & 8) << 10) 	// 3 of 0
					| ((i & 4) << 3) 	// 3 of 1
					| ((i & 2) << 11) 	// 4 of 0
					| ((i & 1) << 4); 	// 4 of 1

				metrics->unweight1[i] =
					  ((i & 128) << 4)	// 5 of 0
					| ((i & 64) >> 3)  	// 5 of 1
					| ((i & 32) << 5)	// 6 of 0
					| ((i & 16) >> 2)	// 6 of 1
					| ((i & 8) << 6)  	// 7 of 0
					| ((i & 4) >> 1) 	// 7 of 1
					| ((i & 2) << 7)  	// 8 of 0
					| (i & 1); 			// 8 of 1
				break;
			}
		}
	}
}



// ===================================
// encoder entry point
// ===================================
Qlong encodeimage(
	Qbyte *image,
	Qlong width,
	Qlong height,
	Qlong depth,
	Qlong flags,
	Qlong options,
	QBITDATAHEADER *dataheader,
	Qbyte *buffer,
	Qlong buffersize)
{

	METRICS metrics;
	STREAM buf;
	Qbyte  *tmpdata;
	Qlong span, maxcol, tmpdatasize;
	long i;

	// this will be set with the total data size and the number of
	// 16 bit masks at the start of the quad stream
	dataheader->size = 0;
	dataheader->maskcount = 0;

	if (!image)
		return QBIT_ERROR_NULL_IMAGE;

	// sanity check
	if ((depth != 16) && (depth != 24) && (depth != 32))
		return QBIT_ERROR_UNSUPPORTED_COLOUR_DEPTH;;

	if (buffersize < depth)
		return QBIT_ERROR_OUT_OF_BUFFER_SPACE;;


	getmetrics(&metrics, width, height, depth, flags, options, &span);


	// output buffer uses half bytes
	buf.start = buffer;
	buf.current = (buffer + (buffersize - 1));
	buf.low = 1;


	if (flags & QBIT_COMPRESS)
	{
		// compression may run against a copy of the image
		// and calls the first colour collapse function
		if (options & QBIT_OPTION_NO_COPY)
			metrics.startstream = image;
		else
		{
			metrics.startstream = (Qbyte *)malloc(height * metrics.shifty);
			memcpy(metrics.startstream, image, height * metrics.shifty);
		}

		maxcol = collapseall(&metrics, &buf);
	}
	else
		metrics.startstream = image;


	// set up a temporary buffer
	tmpdatasize = 0;
	for(i = (long)span; i >= 2; i >>= 1)
		tmpdatasize += depth;

	tmpdata = (Qbyte *)malloc(tmpdatasize);

	metrics.masks = (Qint *)buffer;
	metrics.nextmask = 0;


	// recursively encode the image
	encodetile(0, 0, span >> 1, &metrics, &buf, tmpdata, maxcol);
	dataheader->maskcount = metrics.nextmask;


	// pack the first header onto end of compressed data
	for (i = metrics.bitdepth - 1; i >= 0; i--)
	{
		if (buf.low)
		{
			*(buf.current) = tmpdata[i];
			buf.current--;
		}
		else
		{
			*(buf.current) |= (tmpdata[i] & 240);
			buf.current--;
			*(buf.current) = (tmpdata[i] & 15);
		}
	}


	// fre hte tmp buffer used to pass
	// information up the tree
	free(tmpdata);


	if (flags & QBIT_COMPRESS)
	{
		// write colour count tp "start" of quad stream
		for(i = 0; i <= 28; i += 4)
			WRITE_QUAD ((&buf), ((maxcol & (15 << i)) >> i));

		// free palette table used by collapse preprocess
		if (maxcol)
			free(metrics.dhash);

		// compression may have setup a copy of the image
		if ((options & QBIT_OPTION_NO_COPY) == 0)
			free(metrics.startstream);
	}


	// set the last of the last byte (first read) true
	// if the most leftmost quad in the data stream is used
	if (buf.low)
	{
		*(buf.current) = 255;
	}
	else
	{
		buf.current--;
		*(buf.current) = 0;
	}


	// the control stream was written to the end of bufffer,
	// move it so it follows the 16 bit masks
	buffer += (dataheader->maskcount << 1);

	if (buf.current < buffer)
		return QBIT_ERROR_OUT_OF_BUFFER_SPACE;;

	dataheader->size = buffersize - (buf.current - buf.start);
	memmove(buffer, buf.current, dataheader->size);

	//
	dataheader->size += (dataheader->maskcount << 1);

	return (0);
}



// ==================================
// node encoder
// ------------------------------
int encodetile(
	Qlong x,
	Qlong y,
	Qlong tilespan,
	METRICS *metrics,
	STREAM *buf,
	Qbyte *data,
	Qlong maxcount)
{

	Qbyte blockbit, statebit, fakebit, test;
	Qlong mymax;
	long i;

	fakebit = 0;

	memset(data, 0, metrics->bitdepth);


	//  iterate the quadrants backwards
	for (blockbit = 1, statebit = 16; blockbit <= 8; blockbit <<= 1, statebit <<= 1)
	{
		// tile into the image recursively backwards
		switch (statebit)
		{
		case 32: case 128: x -= tilespan; break;
		case 64: x += tilespan; y -= tilespan; break;
		case 16: y += tilespan; x += tilespan; break;
		}

		data += metrics->bitdepth;
		if ((x < metrics->width) && (y < metrics->height))
		{
			// compression preprocess
			if (tilespan & metrics->collapsebits)
				mymax = collapse(x, y, metrics, buf, tilespan, maxcount);
			else
				mymax = maxcount;

			// sub call out and advance pointer to one past the end of the sub block of control bytes
			if (tilespan > 4)
				encodetile(x, y, tilespan >> 1, metrics, buf, data, mymax);
			else
				encodeblock(x, y, metrics, data);
		}
		else
		{
			// simulate no coverage for area outside actual image
			memset(data, 15, metrics->bitdepth);
			fakebit |= statebit;
		}

		// analyse the control bits passed into sub call and populate
		// the appropriate bits in quadmask
		for (i = metrics->bitdepth; i; i--)
		{
			data--;

			// get this sub quadrants data bits
			test = *(data + metrics->bitdepth);

			switch (test)
			{
			case 15:

				// a block of no bits, set the blockbit clear the statebit
				*data |= blockbit;
				break;
			case 255:

				// block of bits, set the blockbit and the statebit
				*data |= blockbit;
				*data |= statebit;
				break;
			default:

				// there are no partial block bits for the 16 pixel block
				if (tilespan > 4)
				{
	 				if (test & 15)