qbit.c

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

				break;
			}


	// write the index of the highest register needed to
	// encode the palette
	WRITE_QUAD (buf, reg.lastreg);


	//return the number of colours in this palette pass
	return (count - idx);
}


// ======================================
// dump registers for stuff that has changed
// -----------------------------------
void regout(REGISTERS *reg, STREAM *buf, Qlong const col)
{
	Qlong mask, tmpcol, shift;
	long i, maxreg;

	if (reg->init == 0)
	{
		reg->masks[0] = 3;
		reg->shifts[0] = 0;
		for(i = 1, mask = (reg->masks[0] << 2), shift = 2; i < 12; i++, mask <<= 2, shift += 2)
		{
			reg->masks[i] = mask;
			reg->shifts[i] = shift;
		}

		tmpcol = 0;
		for(i = 0; i < 12; i++)
		{
			tmpcol |= reg->masks[i];
			if (tmpcol >= col)
				break;
		}

		reg->lastreg = i;
		for(i = 0; i <= reg->lastreg; i++)
			reg->registers[i] = (1 << ((col & reg->masks[i]) >> reg->shifts[i]));

		reg->init = 1;
	}
	else
	{
		// get the highest 2 bits that match the last colour
		tmpcol = col ^ reg->current;
		for(maxreg = reg->lastreg; maxreg; maxreg--)
		{
			if (reg->masks[maxreg] & tmpcol)
				break;
		}


		// write out the number from the bottom up

		for(i = 0; i < maxreg; i++)
		{
			WRITE_QUAD(buf, reg->registers[i]);
			reg->registers[i] = 1 << ((col & reg->masks[i]) >> reg->shifts[i]);
		}

		reg->registers[maxreg] |= 1 << ((col & reg->masks[maxreg]) >> reg->shifts[maxreg]);
	}

	reg->current = col;
}




// =======================================
// decoder entry point
// ------------------------------------
Qlong decodeimage(
	Qbyte *buffer,
	Qlong width,
	Qlong height,
	Qlong depth,
	Qlong flags,
	Qlong options,
	QBITDATAHEADER *dataheader,
	Qbyte *data)
{

	METRICS metrics;
	STREAM buf;
	Qlong span;
	long i, maxpalette;

	if (flags)
	{
		if (flags != QBIT_COMPRESS)
			return QBIT_ERROR_UNKNOWN_FLAG;
	}

	getmetrics(&metrics, width, height, depth, flags, options, &span);
	metrics.startstream = buffer;


	// 16 bit masks start at the end of the masks and are
	// read backwards, nextmask is an array index
	metrics.masks = (Qint *)data;
	metrics.nextmask =  dataheader->maskcount - 1;;


 	// offset is the start of the encoded data
	buf.start = data + (dataheader->maskcount << 1);
	buf.current = buf.start;

	// determine if the first quad is the top or bottom
	// of the first byte
	buf.low = *(buf.current)? 0: 255;
	buf.current++;

	if (flags & QBIT_COMPRESS)
	{
		// read the size of the colour palette
		// and set up memory buffer for look ups
		maxpalette = 0;
		for(i = 28; i >= 0; i -= 4)
			maxpalette |= ((Qlong)readquad(&buf) << i);

		if (maxpalette)
			metrics.dhash = (Qlong *)malloc(maxpalette * 4);
	}


	decodetile(0, 0, &metrics, span >> 1, 0, 0, metrics.allbits, &buf);

	if ((flags & QBIT_COMPRESS) && (maxpalette))
	{
		// run final decompression pass and free
		// look palette
		uncollapse(0, 0, &metrics, &buf, 0);
		free(metrics.dhash);
	}

	return(0);
}



// =============================
// node decoder
// ------------------------
void decodetile(
	Qlong x,
	Qlong y,
	METRICS *metrics,
	Qlong segment,
	Qlong setbits,
	Qlong nobits,
	Qlong controlbits,
	STREAM *buf)
{

	Qlong masks[32];
	Qlong testbit, subcontrolbits, subsetbits, subnobits, getcontrolbits;
	Qbyte statebit, blockbit;
	long idx;

	getcontrolbits = metrics->allbits - (setbits | nobits);

	// read in the masks
	memset (masks, 0, 128);
	for (idx = 0, testbit = metrics->maxbit; testbit; testbit >>= 1, idx++)
		if (testbit & getcontrolbits)
			if (controlbits & testbit)
			{
				if (buf->low)
					masks[idx] = buf->current[0] & 15 | buf->current[1] & 240;
				else
					masks[idx] = *buf->current;

				buf->current++;
			}
			else
			{
				if (segment > 4)
				{
					// read the quad into the high bits
					if (buf->low)
 					{
						masks[idx] = (*buf->current << 4) & 240;
						buf->current++;
						buf->low = 0;
					}
					else
					{
						masks[idx] = *buf->current & 240;
						buf->low = 1;
					}
				}
			}


	// interpret the masks
	for (blockbit = 8, statebit = 128; blockbit; blockbit >>= 1, statebit >>= 1)
	{
		subnobits = nobits;
		subsetbits = setbits;
		subcontrolbits = 0;

		for (idx = 0, testbit = metrics->maxbit; testbit; testbit >>= 1, idx++)
			if (masks[idx] & blockbit)
			{
				if (masks[idx] & statebit)
					subsetbits |= testbit;
				else
				    subnobits |= testbit;
			}
			else
			    if (masks[idx] & statebit)
					subcontrolbits |= testbit;


		// rotate around the sub tiles top left -> right, bottom left -> right
		switch (blockbit)
		{
		case 4: case 1:

			x += segment;
			break;
		case 2:

			y += segment;
			x -= segment;
			break;
		}

		// recurse into this tile's subtiles
		if ((x < metrics->width) && (y < metrics->height))
			if (segment == 4)
				decodeblock(x,  y, metrics, subsetbits, subnobits);
			else
				decodetile(x,  y, metrics, segment >> 1, subsetbits, subnobits, subcontrolbits, buf);

	}

	if ((segment << 1) & metrics->collapsebits)
		uncollapse(x - segment, y - segment, metrics, buf, segment << 1);
}



// =================================
// leaf decoder
// --------------------------------
void decodeblock(
	const Qlong x,
	const Qlong y,
	METRICS *metrics,
	const Qlong setbits,
	const Qlong nobits)
{

	Qlong pixes[16];
	Qlong testbit, checkbits;
	Qint quad;
	Qlong *curpix;
	Qbyte *image;
	Qlong wrap;
	long i, j, xcount, ycount;


	memset(pixes, 0, 64);

	checkbits = ~(setbits | nobits);
	checkbits &= metrics->allbits;

	for (testbit = 1; testbit <= checkbits; testbit <<= 1)
		if (testbit & checkbits)
		{
			quad = metrics->masks[metrics->nextmask--];
			if (quad & 32768) pixes[0] |= testbit;
			if (quad & 16384) pixes[1] |= testbit;

			if (quad & 2048) pixes[2] |= testbit;
			if (quad & 1024) pixes[3] |= testbit;

			if (quad & 8192) pixes[4] |= testbit;
			if (quad & 4096) pixes[5] |= testbit;

			if (quad & 512) pixes[6] |= testbit;
			if (quad & 256) pixes[7] |= testbit;

			if (quad & 128) pixes[8] |= testbit;
			if (quad & 64) pixes[9] |= testbit;

			if (quad & 8) pixes[10] |= testbit;
			if (quad & 4) pixes[11] |= testbit;

			if (quad & 32) pixes[12] |= testbit;
			if (quad & 16) pixes[13] |= testbit;

 			if (quad & 2) pixes[14] |= testbit;
			if (quad & 1) pixes[15] |= testbit;
		}


	xcount = (x + 3) < metrics->width?  4: metrics->width - x;
	ycount = (y + 3) < metrics->height?  4: metrics->height - y;
	wrap = metrics->shifty - (xcount * metrics->bytedepth);

	curpix = pixes;
	image = LOCATION(x, y, metrics);
	for(i = 0; i < ycount; i++)
	{
		for(j = 0; j < xcount; j++, curpix++)
			switch(metrics->bytedepth)
			{
			case 3:

				PUT_COLOUR_TRUE_ADVANCE(image, (*curpix | setbits));
				break;
			case 2:

				PUT_COLOUR_HIGH_ADVANCE(image, (*curpix | setbits));
				break;
			case 4:

				PUT_COLOUR_DWORD_ADVANCE(image, (*curpix | setbits));
				break;
			case 1:

				*image++ = (*curpix | setbits) & 255;
				break;
			}

		curpix += (4 - xcount);
		image += wrap;
	}
}



// =============================
// uncollapse
// read the palette in from the data stream
// and assign colour values
// ---------------------------
void uncollapse(
	const Qlong x,
	const Qlong y,
	METRICS *metrics,
	STREAM *buf,
	const Qlong tilespan)
{

	Qbyte *image;
	Qlong height, width, col, wrap, level;
	long i, j;


	if (tilespan)
	{
		width = (x + tilespan) <= metrics->width? tilespan: metrics->width - x;
		height = (y + tilespan) <= metrics->height? tilespan: metrics->height - y;

		// read in the size of the palette
		// in register elements used
		level = readquad(buf);
	}
	else
	{
		// this was the first run
		width = metrics->width;
		height = metrics->height;
		level = (metrics->bitdepth >> 1) - 1;
	}


	// if this quadrant isn't palettized at this
	// level the quad will have all bits set
	if (level == 15)
		return;


	wrap = metrics->shifty - (width * metrics->bytedepth);

	// read in the palette
	readpal(metrics->dhash, 0, buf, level * 2);

	// write the sort back to the image
	// the first thing the compressor does is transform the colour
	// into a weighted value.  if this is the last decompression
	// pass, reditribute the bits
	image = LOCATION(x, y, metrics);
	for (i = 0; i < height; i++, image += wrap)
		for (j = 0; j < width; j++)
			switch(metrics->bytedepth)
			{
			case 3:

				col = metrics->dhash[GET_COLOUR_TRUE(image)];
				if (!tilespan) col = UNMAP_TRUE(metrics, col);
				PUT_COLOUR_TRUE_ADVANCE(image, col);
				break;
			case 2:

				col = metrics->dhash[GET_COLOUR_HIGH(image)];
				if (!tilespan) col = UNMAP_HIGH(metrics, col);
				PUT_COLOUR_HIGH_ADVANCE(image, col);
				break;
			case 4:

				col = metrics->dhash[GET_COLOUR_DWORD(image)];
				if (!tilespan) col = col;
				PUT_COLOUR_DWORD_ADVANCE(image, col);
				break;
			default:

				col = metrics->dhash[*image];
				if (!tilespan) col = col;
				*image = col & 255;
				image ++;
				break;
			}
}



// =======================================
// this is a recursive call to read the
// palette in from the "quad" stream
// -----------------------------------
Qlong *readpal(
	Qlong *pal,
	const Qlong mask,
	STREAM *buf,
	const Qlong shift)
{

	Qlong testmask;

	testmask = readquad(buf);

	if (shift)
	{
		if (testmask & 1)
			pal = readpal(pal, mask, buf, shift - 2);

		if (testmask & 2)
			pal = readpal(pal, mask | (1 << shift), buf, shift - 2);

		if (testmask & 4)
			pal = readpal(pal, mask | (2 << shift), buf, shift - 2);

		if (testmask & 8)
			pal = readpal(pal, mask | (3 << shift), buf, shift - 2);
	}
	else
	{
		if (testmask & 1)
			*pal++ = mask;

		if (testmask & 2)
			*pal++ = mask | 1;

		if (testmask & 4)
			*pal++ = mask | 2;

		if (testmask & 8)
			*pal++ = mask | 3;
	}

	return pal;
}



// ================================
// read and write one quads/bytes
//  to the stream
// --------------------------
Qbyte readquad(STREAM *buf)
{
	Qbyte tmp;

	if (buf->low)
	{
		tmp = *(buf->current) & 15;
		buf->current++;
		buf->low = 0;
	}
	else
	{
		tmp = *(buf->current) >> 4;
		buf->low = 1;
	}

	return tmp;
}