Thread: Way to do scan lines

Originally Posted by awsdert

It's not spamming, I'm seeking help to speed up my progress, I'd appreciate help, not sarcasm

Agreed, for social human beings, this could indeed help with the progress. It was not sarcastic at all.

Originally Posted by ghoul

Agreed, for social human beings, this could indeed help with the progress. It was not sarcastic at all.

Every response I think of to this feels a little sarcastic and adds nothing to the topic of this thread so I'm just not gonna leave one... besides this post

Finally got a non-hacked single colour image:

Code:

uint glen_extra[32] =
{
	0, 0, 0, 0, 0, 0, 0, 0, 1, 1,
	1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
	4, 4, 4, 4, 5, 5, 5, 5, 5, 0
};

uint glen_base_lengths[32] =
{
	 3,  4,  5,   6,   7,   8,   9,  10,  11, 13,
	15, 17, 19,  23,  27,  31,  35,  43,  51, 59,
	67, 83, 99, 115, 131, 163, 195, 227, 258,  0
};

uint gdis_extra[32] =
{
	0, 0,  0,  0,  1,  1,  2,  2,  3,  3,
	4, 4,  5,  5,  6,  6,  7,  7,  8,  8,
	9, 9, 10, 10, 11, 11, 12, 12, 13, 13,
	0
};

uint gdis_base_lengths[32] =
{
	    1,    2,    3,    4,    5,    7,    9,    13,    17,    25,
	   33,   49,   65,   97,  129,  193,  257,   385,   513,   769,
	 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577,
	    0
};

void ScanLines( SCANLINE *Scan )
{
	uint size = (Scan->Flags & 2) + 1;
	uint Depth = Scan->Depth;
	size_t max = Scan->Data->used * CHAR_BIT;
	size_t num = max / Depth;
	HUFFMAN_NODE *tree, *base;
	max = num * Depth;
	PrintScanLines( Scan );
	//PrintBits( Scan->Palette, size, size * CHAR_BIT, "Palette" );
	//PrintBits( Scan->Into, 64, Scan->Depth * 64, "Into" );
#if 0
	UseHuffman1stBit( Scan->Alloc, Scan->Into, Scan->Data, max );
	PrintBits( Scan->Data, 64, Scan->Depth * 64, NULL );
#endif

	if ( Scan->Flags & 1 )
	{
		ulong *into = Scan->Into->addr;
		uint t = 0;
		//uint m = 1u << (CHAR_BIT - 1);
		uint Depth = Scan->Depth;
		size_t pixels = Scan->SpanI * Scan->SpanR;
		bool final_block = false;

		tree = Scan->Huffman->addr;
		memset( into, 0, Scan->Into->size );

		for ( size_t b = 0; !final_block && t < pixels; )
		{
			uint header = GetForewardBits( Scan->Data, b, 3 ), type;
			uint glen = GetForewardBits( Scan->Data, b + 3, 5 );
			size_t glen_pos = b + 8;
			//uint glen_code = 257 + glen;
			uint glen_bits = glen_extra[glen];
			uint glen_leng = glen_base_lengths[glen] +
				GetForewardBits( Scan->Data, b + 8, glen_bits );
			size_t gdis_pos = glen_pos + 5 + glen_bits;
			uint gdis = GetForewardBits( Scan->Data, gdis_pos, 5 );
			uint gdis_bits = gdis_extra[gdis];
			uint gdis_leng = gdis_base_lengths[glen] +
				GetForewardBits( Scan->Data, gdis_pos + 5, gdis_bits );
			size_t data_pos = gdis_pos + 5 + gdis_bits, pos = 0;
			size_t count = 0;
			ulong *dst = into + t;

			base = tree;
			type = header & 0x3;
			final_block = !!(header & 4);

			if ( type == 3 )
			{
				//final_block = true;
				*dst = 0xC0FFEE;
			}
			else if ( type == 2 )
			{
				uint maxbits = CHAR_BIT * sizeof(ulong);
				uint h = GetForewardBitsR( Scan->Data, b + count, maxbits );

				for ( size_t bit = 1ULL << (maxbits - 1); bit; ++count, bit >>= 1 )
				{
					bool dir = !!(h & bit);
					pos = base->nxt[dir];
					base = tree + pos;
				}

				*dst = base->val;
			}
			else if ( type == 1 )
			{
				/* FIXME: This is probably not correct */
				uint h = GetForewardBitsR( Scan->Data, b + count, Depth );
				count = Depth;

				for ( size_t bit = 1ULL << (Depth - 1); bit; bit >>= 1 )
				{
					bool dir = !!(h & bit);
					pos = base->nxt[dir];
					base = tree + pos;
				}

				*dst = base->val;
			}
			else
			{
				for ( uint dis = 0; dis < gdis_leng; ++dis )
				{
					for
					(
						uint len = 0;
						t < pixels && len < glen_leng;
						len += Depth, ++t, count += Depth
					)
					{
						uint c = GetForewardBits( Scan->Data, data_pos, Depth );
						dst = into + t;
						*dst = GetForewardBitsR( Scan->Palette, c, size * 8 );
					}
				}
			}

#if 1 && !defined( USING_EOG )
			if ( t < CHAR_BIT )
				printf
				(
					"%u value = 0x%08lX header = %X, type = %u, "
					"b = %5zu, b + count = %5zu, "
					"glen = %2u, glen_bits = %2u, glen_leng = %5u, "
					"gdis = %2u, gdis_bits = %2u, gdis_leng = %5u\n",
					t, *dst, header, type, b, b + count,
					glen, glen_code, glen_bits, glen_leng,
					gdis, gdis_bits, gdis_leng
				);
#endif

			*dst <<= 8;
			*dst |= 0xFF;
			b = data_pos + count;
			++t;
		}

		Scan->Into->used = t;
	}
}

Since the multi-colour image I want to test on uses the same chunks I'll give that a test in a sec, just gotta upload this code and report to job center since I need evidence that I'm trying to raise the likelyhood I'll be employed instead of being a leach

Well that was a bust, hit a segfault, I only managed to track down the issue to IndexHuffmanTree(), here's how it's used:

Code:

size_t IndexHuffmanTree( BUFF *Tree, size_t pos, size_t num )
{
	size_t nxt;
	HUFFMAN_NODE *tree = Tree->addr, *base, *leaf;

	if ( num <= 2 )
	{
		leaf = tree + pos;
		memset( leaf, 0, sizeof(HUFFMAN_NODE) * 2 );
		return pos;
	}

	base = tree + pos;
	memset( base, 0, sizeof(HUFFMAN_NODE) );
	base->nxt[0] = IndexHuffmanTree( Tree, pos, num + 1 / 2 );
	nxt = base->nxt[0] + 1;

	for ( leaf = base; leaf->nxt[1]; leaf = tree + nxt )
		nxt = leaf->nxt[1];

	base->nxt[1] = nxt;
	return nxt;
}

BUFF * BuildHuffmanTree( ALLOC *Alloc, BUFF *Tree, BUFF *Data, uint bits )
{
	size_t all = Data->used * CHAR_BIT;
	size_t num = all / bits;
	size_t max = num * bits;
	size_t need, n, h;
	HUFFMAN_NODE *tree, *base;

	for ( n = 1ULL << ((sizeof(size_t) * CHAR_BIT) - 1); n; n >>= 1 )
	{
		if ( num & n )
			break;
	}

	need = num;
	for ( n >>= 1; n; n >>= 1 )
	{
		if ( need & n )
			need ^= n;
	}

	h = need * 2;
	for ( n = h, need = 0; n > 1; need += n, n /= 2 );

	Tree = buff_inc_only( Alloc, Tree, HUFFMAN_NODE, need );

	if ( !Tree )
		return NULL;

	max = IndexHuffmanTree( Tree, 0, h );
	tree = Tree->addr;

	for ( h = 0, n = 0; h < max; ++h )
	{
		base = tree + h;

		if ( base->nxt[0] )
			continue;

		base->val = GetForewardBitsR( Data, n * bits, bits );
		base->val <<= 8;
		++n;
	}

	return Tree;
}

It's sole purpose is to construct the all the branches & leafs of the tree in order so they can be filled after. Anyone seeing what I'm not seeing?

Edit: Never mind, just found it, I failed to encase the `num + 1` in brackets in the self call of IndexHuffmanTree(), still didn't get the image I was expecting though