qbit.c

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

					{
						*data |= statebit;

						if (buf->low)
						{
							*(buf->current) = test;
							buf->current--;
						}
						else
						{
							*(buf->current) |= test & 240;
							buf->current--;
							*(buf->current) = test & 15;
						}
					}
					else
					{
						// there are no statebits without blockbits from the tilespan==4 block
						if (tilespan > 8)
						{
							if (buf->low)
							{
								*(buf->current) = test >> 4;
								buf->low = 0;
							}
							else
							{
								*(buf->current) |= (test & 240);
								buf->current--;
								buf->low = 1;
							}
						}
					}
				}
				break;
			}
		}
	}


	// update the fake bit control bits
	if (fakebit)
	{
		test = (128 | 8);
		for (i = 1; i <= metrics->bitdepth; i++, data++)
			if ((*data & test) == test)
				*data |= fakebit;
	}

	return (1);
}



// ==================================
// leaf encoder
// where a bit in all 16 pixels has the same value
// it is encoded into the control stream (data), otherwise
// it ends up written out as a 16 bit mask to raw
// ------------------------------
void encodeblock(
	Qlong x,
	Qlong y,
	METRICS *metrics,
	Qbyte *data)
{
	Qlong masks[32];
	Qlong *coverage;
	Qlong *mask;
	Qlong testbits;
	Qbyte blockbit, shift, inventbits;
	long j, i;

	memset (masks, 0, 128);

	inventbits = 0;

	coverage = data;

	for (blockbit = 8, shift = 12; blockbit; blockbit >>= 1, shift -= 4)
	{
		switch (blockbit)
		{
			case 4: case 1:
				x += 2;
				break;
			case 2:
				y += 2;
				x -= 2;
				break;
		}

		if ((y < metrics->height) && (x < metrics->width))
			getquad(coverage, x, y, metrics);
		else
			inventbits |= (15 << shift);

		mask = masks;
		for ( i = 0; i < metrics->bytedepth; i++)
			for (testbits = (15 << 28), j = 28; testbits; testbits >>= 4, j -= 4, mask++)
				*mask |= (testbits & coverage[i]) >> j << shift;
	}


	mask = masks;
	for (i = 0; i < metrics->bitdepth; i++, mask++, data++)
	{
		// or the invented bits onto the mask if
		// the mask has any coverage at all
		if (*mask)
			*mask |= inventbits;

		switch(*mask)
		{
		case 0:

			*data = 15;
			break;
		case 65535:

			*data = 255;
			break;
		default:

			*data = 0;
			metrics->masks[metrics->nextmask++] = (Qint)*mask;
			break;
		}
	}
}


// ========================================
// get coverage mask of four pixels
// ----------------------------------
void getquad(
	Qlong *coverage,
	const Qlong x,
	const Qlong y,
	METRICS *metrics)
{

	Qbyte *image;
	Qlong done;
	long i;

	image = LOCATION(x, y, metrics);

	done = 8;
	for (i = 0; i < metrics->bytedepth; i++)
		coverage[i] = metrics->bitlu[image[i]];

	image += metrics->bytedepth;

	if ((x + 1) < metrics->width)
	{
		done |= 4;
		for (i = 0; i < metrics->bytedepth; i++)
			coverage[i] |= (metrics->bitlu[image[i]] >> 1);
	}


	if ((y + 1) < metrics->height)
	{
		done |= 2;
		image = LOCATION(x, (y + 1), metrics);
		for (i = 0; i < metrics->bytedepth; i++)
			coverage[i] |= (metrics->bitlu[image[i]] >> 2);

		image += metrics->bytedepth;

		if ((x + 1) < metrics->width)
		{
			done |= 1;
			for (i = 0; i < metrics->bytedepth; i++)
				coverage[i] |= (metrics->bitlu[image[i]] >> 3);
		}
	}

	// set coverage outside the image to be the same as the control pixel
	if (done != 15)
	{
		for (i = 0; i < metrics->bytedepth; i++)
		{
			if ((done & 1) == 0) coverage[i] |= ((*coverage & metrics->leadingbits) >> 3);
			if ((done & 2) == 0) coverage[i] |= ((*coverage & metrics->leadingbits) >> 2);
			if ((done & 4) == 0) coverage[i] |= ((*coverage & metrics->leadingbits) >> 1);
		}
	}
}


// =================================
// compression pre process,
// removes unused colour value and
// writes reconstruct data to buf
// -----------------------------
Qlong collapseall(
	METRICS *metrics,
	STREAM *buf)
{

	CACHE cache[COLLAPSE_CACHE_MAX + 1];
	REGISTERS reg;
	Qlong *pal;
	Qbyte *image;
	Qlong col, count, idx, testbit, bit, colbase;
	long i, j;


	pal = (Qlong *)malloc(((metrics->allbits >> 5) + 1) * 4);
	memset(pal, 0, ((metrics->allbits >> 5) + 1) * 4);


	count = 0;
	image = metrics->startstream;
	for (i = 0; i < metrics->height; i++, image += metrics->scanpad)
	{
		for (j = 0; j < metrics->width; j++)
		{
			switch(metrics->bytedepth)
			{
			case 3:

				col = MAPWEIGHT_TRUE(metrics, image);
				image += 3;
				break;
			case 2:

				col = MAPWEIGHT_HIGH(metrics, image);
				image += 2;
				break;
			case 4:

				col = GET_COLOUR_DWORD(image);
				image += 4;
 				break;
			case 1:

				col = (Qlong)*image++;
				break;
			}

			bit = 1 << (col & 31);

			if ((pal[col >> 5] & bit) == 0)
			{
				count++;
			    pal[col >> 5] |= bit;
			}
		}
	}

	metrics->dhash = (Qlong *)malloc(count * 4);
	memset(metrics->dhash, 0, count * 4);

	// this stores tempory lookups into the palette in
	// order skip the binary search
	memset(cache, 0, (COLLAPSE_CACHE_MAX + 1) * 8);

	// write out the palette map
	// and load the palette array
	reg.init = 0;
	idx = count - 1;
	for(i = (metrics->allbits >> 5); i >= 0; i--)
		if (pal[i])
		{
			colbase = i << 5;
			for(j = 31, testbit = (1 << 31); j >= 0; j--, testbit >>= 1)
				if (pal[i] & testbit)
				{
					col = colbase | j;

					cache[col & COLLAPSE_CACHE_MAX].colour = col;
					cache[col & COLLAPSE_CACHE_MAX].index = idx;

					metrics->dhash[idx--] = col;
					regout(&reg, buf, col);
				}
		}


	// write the last colour out
	for(i = 0; i <= reg.lastreg; i++)
		WRITE_QUAD(buf, reg.registers[i]);


	free(pal);


	// update the image at metrics->startstream
  	image = metrics->startstream;
	for (i = 0; i < metrics->height; i++, image += metrics->scanpad)
	{
		for (j = 0; j < metrics->width; j++)
		{
			switch(metrics->bytedepth)
			{
			case 3:

				col = MAPWEIGHT_TRUE(metrics, image);
				break;
			case 2:

 				col = MAPWEIGHT_HIGH(metrics, image);
				break;
			case 4:

				col = GET_COLOUR_DWORD(image);
				break;
			case 1:

				col = (Qlong)*image;
				break;
			}

			if (cache[col & COLLAPSE_CACHE_MAX].colour == col)
				idx = cache[col & COLLAPSE_CACHE_MAX].index;
			else
			{
				idx = bin(0, count - 1, metrics->dhash, col);
				cache[col & COLLAPSE_CACHE_MAX].colour = col;
				cache[col & COLLAPSE_CACHE_MAX].index = idx;
			}

			switch(metrics->bytedepth)
			{
			case 3:

				PUT_COLOUR_TRUE_ADVANCE(image, idx);
				break;
			case 2:

				PUT_COLOUR_HIGH_ADVANCE(image, idx);
				break;
			case 4:

				PUT_COLOUR_DWORD_ADVANCE(image, idx);
				break;
			case 1:

				*image++ = idx & 255;
				break;
			}
		}
	}

	return (count);
}



// ===================================
// binary search
// -------------------------------
Qlong bin(const Qlong lbnd, const Qlong ubnd, Qlong *pal, const Qlong test)
{
	Qlong mid;

	mid = (ubnd + lbnd) >> 1;
	if (pal[mid] == test)
		return mid;
	else
		if (pal[mid] > test)
			return bin (lbnd, mid - 1, pal, test);
		else
			return bin (mid + 1, ubnd, pal, test);
}



// =================================
// compression pre process,
// removes unused colour value and
// writes recontruct data to buf
// -----------------------------
Qlong collapse(
	Qlong x,
	Qlong y,
	METRICS *metrics,
	STREAM *buf,
	Qlong tilespan,
	Qlong count)
{

	REGISTERS reg;
	Qbyte *image;
	Qlong height, width, idx, col, mycount, wrap;
	long i, j;


	if (count == 0)
	{
		WRITE_QUAD(buf, 15);
		return 0;
	}


	// get the dimensions of the operation
	width = (x + tilespan) <= metrics->width? tilespan: metrics->width - x;
	height = (y + tilespan) <= metrics->height? tilespan: metrics->height - y;
	wrap = metrics->shifty - (width * metrics->bytedepth);

	memset(metrics->dhash, 0, count * 4);

	mycount = 0;

	// mark the hash table with used colours
	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 = GET_COLOUR_TRUE(image);
				image += 3;
				break;
			case 2:

				col = GET_COLOUR_HIGH(image);
				image += 2;
				break;
			case 4:

				col = GET_COLOUR_DWORD(image);
				image += 4;
				break;
			case 1:

				col = *image++;
				break;
			}

			if (!metrics->dhash[col])
			{
				metrics->dhash[col] = 1;
				mycount++;
			}
		}



	// conditions where we should skip the palette
	// write all bits meaning no palette
	if ((mycount * 3) > (width * height * 2))
	{
		WRITE_QUAD(buf, 15);
		return 0;
	}

	if ((mycount * 3) > (count * 2))
	{
		WRITE_QUAD(buf, 15);
		return 0;
	}


	// output the palette
	reg.init = 0;
	idx = count;
	for(i = (count - 1); i >= 0; i--)
		if (metrics->dhash[i])
		{
			metrics->dhash[i] = --idx;
			regout(&reg, buf, i);
		}


	// write the last colour out
	for(i = 0; i <= reg.lastreg; i++)
		WRITE_QUAD(buf, reg.registers[i]);


	// write the palette index back to the image
 	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)];
				PUT_COLOUR_TRUE_ADVANCE(image, (col - idx));
				break;
			case 2:

				col = metrics->dhash[GET_COLOUR_HIGH(image)];
				PUT_COLOUR_HIGH_ADVANCE(image, (col - idx));
				break;
			case 4:

				col = metrics->dhash[GET_COLOUR_DWORD(image)];
				PUT_COLOUR_DWORD_ADVANCE(image, (col - idx));
				break;
			case 1:

				col = metrics->dhash[*image];
				*image++ = col & 255;