Thread: Way to do scan lines

I learned from the below url that I have to do scan lines to construct the image from the indices, problem is I can't seem to get it right, the best I've gott so far is this:
PNG Specification: Chunk Specifications
PNG Specification: Data Representation

Code:

	if ( Image->Color & 1 )
	{
		ulong *targets = FullImg->addr;
		uchar *colours = Palette->addr;
		ulong mask = 0xFF;
		leng = (Image->Color & 2) + 1;
		mask >>= (CHAR_BIT * leng);

#if 0
		for ( size_t d = 0; d < Pixels; ++d )
		{
			ulong s = data[d];
			ulong *target = targets + d;
			uchar *source = colours + s;
			*target = 0;
			fill_at_end( target, 4, source, leng );
			//*target |= mask;
			//printf("target = 0x%08lX, index = %zu\n", *target, s );
		}
#else
		for ( uint x = 0; x < Image->SpanX; ++x )
		{
			for ( uint y = 0; y < Image->SpanY; ++y )
			{
				uint d = x * y;
				uint s = data[d];
				ulong *target = targets + d, colour = 0;
				uchar *source = colours + s;
				fill_at_end( &colour, 4, source, leng );
				*target = colour;
			}
		}

		for ( uint y = 0; y < Image->SpanY; ++y )
		{
			for ( uint x = 0; x < Image->SpanX; ++x )
			{
				uint d = x * y;
				uint s = data[d];
				ulong *target = targets + d, colour = 0;
				uchar *source = colours + s;
				fill_at_end( &colour, 4, source, leng );
				*target |= colour;
			}
		}
#endif
	}

Still struggling with the implementation but I got a bit further, no longer have half the image all dark, btw I'm using this image for verifying I'm programming the algorithm along the right lines:
File:PNG-Gradient hex.png - Wikipedia

This is what I have now:

Code:

	if ( Image->Color & 1 )
	{
		ulong *targets = FullImg->addr;
		uchar *colours = Palette->addr;
		ulong mask = 0xFF, p = 0, useY = false;
		uint SpanR = useY ? Image->SpanX : Image->SpanY;
		uint SpanI = useY ? Image->SpanY : Image->SpanX;
		leng = (Image->Color & 2) + 1;
		mask >>= (CHAR_BIT * leng);

		memset( targets, 0, FullImg->size );

		for ( uint i = 0; i < SpanI; ++i )
		{
			uint base = i * SpanR;
			p = 0;
			for ( uint r = 0; r < SpanR; ++r, ++p )
			{
				uint d = base + r;
				uint s = data[p];
				ulong *target = targets + d;
				uchar *source = colours + s;
				fill_at_end( target, 4, source, leng );
			}
		}
	}

Converted the scanline code a bit for putting into a dedicated function:

Code:

typedef struct _SCANLINE
{
	uint Depth, Flags, SpanR, SpanI, CMethod, FMethod, IMethod;
	BUFF *Palette, *Dst, *Src;
} SCANLINE;
...
void ScanLines( SCANLINE *Scan )
{
#if 0
	printf( "Depth: %u\n",			Scan->Depth	);
	printf( "Flags: 0x%08X\n",		Scan->Flags	);
	printf( "Compression Method: 0x%08X\n",	Scan->CMethod	);
	printf( "Filter Method: 0x%08X\n",	Scan->FMethod	);
	printf( "Interlace Method: 0x%08X\n",	Scan->IMethod	);
#endif

	if ( Scan->Flags & 1 )
	{
		ulong *targets = Scan->Dst->addr;
		uchar *sources = Scan->Src->addr;
		uchar *colours = Scan->Palette->addr;
		uint s = 0;
		uint SpanR = Scan->SpanR;
		uint SpanI = Scan->SpanI;
		uint Limit = Scan->Palette->used;
		uint size = (Scan->Flags & 2) + 1;

		memset( targets, 0, Scan->Dst->size );

		for ( uint i = 0; i < SpanI; ++i )
		{
			uint base = i * SpanR;
			for ( uint r = 0; r < SpanR; ++r, ++s )
			{
				uint d = base + r;
				uint c = sources[s % Limit];
				ulong *target = targets + d;
				uchar *colour = colours + c;
				fill_at_end( target, 4, colour, size );
			}
		}

		Scan->Dst->used = s;
	}
}

And this is what I get from the IDAT (Scan->Src) chunk of the wiki image mentioned:
pic (1).ppm - Google Drive

Still couldn't figure it out so in mean time I tried writing the diagonal version of scan lines, I messed up somewhere though as I just got a small mostly while strip at the top of the image, someone mind taking a look and seeing if they can spot the problem code because I'm having a brain fart on this one:

Code:

void ScanLinesDiagonally( SCANLINE *Scan )
{
#if 0
	printf( "Depth: %u\n",					Scan->Depth		);
	printf( "Flags: 0x%08X\n",				Scan->Flags		);
	printf( "Compression Method: 0x%08X\n",	Scan->CMethod	);
	printf( "Filter Method: 0x%08X\n",		Scan->FMethod	);
	printf( "Interlace Method: 0x%08X\n",	Scan->IMethod	);
#endif

	if ( Scan->Flags & 1 )
	{
		ulong *targets = Scan->Dst->addr;
		uchar *sources = Scan->Src->addr;
		uchar *colours = Scan->Palette->addr;
		uint SpanR = Scan->SpanR, r = 0, s = 0;
		uint SpanI = Scan->SpanI, i = 0;
		uint Limit = Scan->Palette->used;
		uint Pixels = SpanI * SpanR;
		uint size = (Scan->Flags & 2) + 1;
		int addR = 1, addI = 0;

		memset( targets, 0, Scan->Dst->size );

		for ( uint span = 0; s < Pixels; ++span )
		{
			if ( r == span )
			{
				addR = 1;
				addI = 0;
				do
				{
					uint base = (i % SpanI) * SpanR;
					uint d = base + (r % SpanR);
					uint c = sources[s % Limit];
					ulong *target = targets + d;
					uchar *colour = colours + c;
					fill_at_end( target, 4, colour, size );

					r += addR;
					i += addI;
					addR = -1;
					addI = 1;
					++s;
				}
				while ( i < span );
			}
			else
			{
				addR = 0;
				addI = 1;
				do
				{
					uint base = (i % SpanI) * SpanR;
					uint d = base + (r % SpanR);
					uint c = sources[s % Limit];
					ulong *target = targets + d;
					uchar *colour = colours + c;
					fill_at_end( target, 4, colour, size );

					r += addR;
					i += addI;
					addR = 1;
					addI = -1;
					++s;
				}
				while ( r < span );
			}
		}

		Scan->Dst->used = s;
	}
}

Found a vid that gave me rough idea of how to do it, although my implementation is definitely different to how they did it, also decided to rename the function to something easier to type and undertsand the purpose of, didn't resolve my incorrect image issue though, just gave me a bunch of squares more or less.
pic (2).ppm - Google Drive

Code:

void ScanLinesZigZag( SCANLINE *Scan )
{
#if 0
	printf( "Depth: %u\n",					Scan->Depth		);
	printf( "Flags: 0x%08X\n",				Scan->Flags		);
	printf( "Compression Method: 0x%08X\n",	Scan->CMethod	);
	printf( "Filter Method: 0x%08X\n",		Scan->FMethod	);
	printf( "Interlace Method: 0x%08X\n",	Scan->IMethod	);
#endif

	if ( Scan->Flags & 1 )
	{
		ulong *targets = Scan->Dst->addr;
		uchar *sources = Scan->Src->addr;
		uchar *colours = Scan->Palette->addr;
		uint SpanR = Scan->SpanR, r = 0, s = 0;
		uint SpanI = Scan->SpanI, i = 0;
		uint Limit = Scan->Palette->used;
		uint Pixels = SpanI * SpanR;
		uint size = (Scan->Flags & 2) + 1;
		int addR = 1, addI = 0;

		memset( targets, 0, Scan->Dst->size );

		for ( uint span = 0; s < Pixels; ++span )
		{
			if ( i % 2 == 0 )
			{
				addR = 1;
				addI = 0;
				do
				{
					uint base = i * SpanR;
					uint d = base + r;
					uint c = sources[s % Limit];
					ulong *target = targets + d;
					uchar *colour = colours + c;
					fill_at_end( target, 4, colour, size );

					r += addR;
					i += addI;
					addI = -1;
					++s;
				}
				while ( i );
			}
			else
			{
				addR = 0;
				addI = 1;
				do
				{
					uint base = i * SpanR;
					uint d = base + r;
					uint c = sources[s % Limit];
					ulong *target = targets + d;
					uchar *colour = colours + c;
					fill_at_end( target, 4, colour, size );

					r += addR;
					i += addI;
					addR = -1;
					++s;
				}
				while ( r );
			}
		}

		Scan->Dst->used = s;
	}
}

The image that I linked in my 2nd post, I'm trying to reproduce it in *.ppm format, I can load the chunks just fine but converting the IDAT chunk/s back to a plain image ready for the *.ppm file it's going into, that *.ppm file is just to verify I loaded the *.png & reproduced it's image correctly, before trying to use it in learning texture stuff from opengl, don't want to use libpng because apparently it does not support custom allocator which makes it unsafe for multi-threading so I'm doing my own version which will be thread safe via the allocator, doesn't hurt to learn the format either (though I'm finding it badly explained)

After finding some documentation that provided more information on the IDAT format I found I have to implement the huffman decompression algorithm, I understand the concept but the problem is I don't understand how the bytes that should exist and the number of bits/turns are identified in the 1st place, it's all well and good using a table that's already understood but how does one understand the table to begin with? All I got is this as I was trying to analyse the table to get useful information on how to understand the table to begin with:

Code:

BUFF * DecompressHuffman( ALLOC *Alloc, BUFF *Dst, BUFF *Src, uint depth )
{
	uchar *dst;
	uchar *src = Src->addr;
	size_t bits = Src->used * CHAR_BIT;

	for ( size_t b = 0; b < bits; )
	{
		uchar key = 0, val = 0;

		for ( uint d = 0; d < depth; ++b, ++d )
		{
			size_t byte = b / CHAR_BIT;
			size_t bit = 1u << (b % CHAR_BIT);
			val <<= 1;
			val |= !!(src[byte] & bit);
		}

		printf( "val = '%c', key = 0x%02X\n", val, key );
	}

	Dst = buff_inc_only( Alloc, Dst, uchar, bits );

	if ( !Dst )
		return NULL;

	dst = Dst->addr;

	return Dst;
}

The documentation I found btw:
Writing a (simple) PNG decoder might be easier than you think

Edit: To ensure I'm getting it right I've chose to edit the call to use a premade table from someone else's documentation of huffman tables:

Code:

		uchar go_go_gophers[] =
		{
			0b01010110,
			0b01110010,
			0b00010001,
			0b01011001,
			0b11011000,

			0b11011011,
			0b00000010,
			0b10101100,
			0b1110110
		};
		memset( Data->addr, 0, Data->size );
		memcpy( Data->addr, go_go_gophers, 9 );
		Data->used = 9;
		DecompressHuffman( Alloc, FullImg, Data, Image->Depth );

Huffman Coding: A CS2 Assignment

I think I got closer, at the very least I realised none of the examples were including the table in the binary so for now I'm using manual table to match the tree mentioned in the document I linked in my previous post (feel like I could've worded that better but not my priority right now). This is how my code is looking (included the section that calls the function - renamed to decode because it is easier to type - so that anyone copy pasting the code to try an help doesn't have to work out where to put characters in the tree):

Code:

	if ( Image->Color & 1 )
	{
		SCANLINE scan = {0};

		scan.Palette = Palette;
		scan.Dst = FullImg;
		scan.Src = Data;

		scan.SpanR = Image->SpanX;
		scan.SpanI = Image->SpanY;
		scan.Depth = Image->Depth;
		scan.Flags = Image->Color;
		scan.CMethod = Image->CompressionMethod;
		scan.FMethod = Image->FilterMethod;
		scan.IMethod = Image->InterlaceMethod;

#if 0
		ScanLines( &scan );
#elif 0
		ScanLinesZigZag( &scan );
#else
		HUFFMAN_CHAR gophers[] =
		{
			{ 0, 13, { 4, 1 } },
				{ 0, 6, { 2, 3 } },
					{ 'g', 3, {0} },
					{ 'o', 3, {0} },
				{ 0, 7, { 5, 8 } },
					{ 0, 3, { 6, 7 } },
						{ 's', 1, {0} },
						{ ' ', 2, {0} },
					{ 0, 4, { 9, 12 } },
						{ 0, 2, { 10, 11 } },
							{ 'p', 1, {0} },
							{ 'h', 1, {0} },
						{ 0, 2, { 13, 14 } },
							{ 'e', 1, {0} },
							{ 'r', 1, {0} },
			{ 0, 0, {0} }
		};
		BUFF Table = {0};
		uchar go_go_gophers[] =
		{
#if 1
			0b01010110,
			0b01110010,
			0b00010001,
			0b01011001,
			0b11011000,

			0b11011011,
			0b00000010,
			0b10101100,
			0b11101100
#else
			0b10110011,
			0b01100110,
			0b11010001,
			0b01011001,
			0b11000000
#endif
		};
		Table.addr = gophers;
		Table.used = 8;
		memset( Data->addr, 0, Data->size );
		memcpy( Data->addr, go_go_gophers, 9 );
		Data->used = 9;
		DecodeHuffman( Alloc, &Table, FullImg, Data );
#endif
	}

	FullImg->used = Pixels;

	return Image;
}

BUFF * DecodeHuffman( ALLOC *Alloc, BUFF *Table, BUFF *Dst, BUFF *Src )
{
	uchar *dst;
	uchar *src = Src->addr;
	HUFFMAN_CHAR *tree, *n;
	size_t bits = Src->used * CHAR_BIT, i = 0, b, end = bits;

#if 0
	Table->used = 0;
	Table = buff_inc_only( Alloc, Table, HUFFMAN_CHAR, Src->used );

	if ( !Table )
		return NULL;
#endif

	tree = Table->addr;

	printf( "%s\n", (char*)src );

	while ( i != end )
	{
		uint spaces = 0, gs = 0, os  = 0;
		char *str = Dst->addr;
		char add[2] = {0};
		memset( str, 0, Dst->size );
		b = i;
		n = tree;

		for ( b = i; b != end; ++b )
		{
			size_t byte = b / CHAR_BIT;
			size_t bit = 1u << (CHAR_BIT - (b % CHAR_BIT));
			bool dir = !!(src[byte] & bit);

			n = tree + n->nxt[dir];

			if ( n->sym )
			{
				gs += (n->sym == 'g');
				os += (n->sym == 'o');
				spaces += (n->sym == ' ');
				add[0] = n->sym;
				strcat( str,  add );
				n = tree;
				//printf( "sym = '%c', num = %d, guess = %u, guessed = %u\n", ch->sym, ch->num, guess, guessed );
			}
		}

		//if ( gs == 3 )
		//if ( spaces == 2 && gs == 3 && os == 3 )
		if ( strstr( str, "her" ) == str )
			printf( "%s\n", str );
		++i;
	}

	Dst = buff_inc_only( Alloc, Dst, uchar, bits );

	if ( !Dst )
		return NULL;

	dst = Dst->addr;

	return Dst;
}

Finally got somewhere, turned out I just read the data wrong from the source document, I was supposed to flip the bits when putting them into the bytes:

Code:

		BUFF Tree = {0};
		uchar go_go_gophers[] =
		{
#if 0
			0b01010110,
			0b01110010,
			0b00010001,
			0b01011001,
			0b11011000,

			0b11011011,
			0b00000010,
			0b10101100,
			0b1110110
#elif 0
			0b10110011,
			0b01100110,
			0b11010001,
			0b01011001,
			0b11000
#else
			0b11001101,
			0b01100110,
			0b10001011,
			0b10011010,
			0b11
#endif
		};
		Tree.addr = gophers;
		Tree.used = 8;
		memset( Data->addr, 0, Data->size );
		memcpy( Data->addr, go_go_gophers, 9 );
		Data->used = 9;
		DecodeHuffman( Alloc, &Tree, FullImg, Data );
#endif
	}

	FullImg->used = Pixels;

	return Image;
}

BUFF * DecodeHuffman( ALLOC *Alloc, BUFF *Tree, BUFF *Dst, BUFF *Src )
{
	uchar *dst;
	uchar *src = Src->addr;
	HUFFMAN_CHAR *tree = Tree->addr, *n = tree;
	size_t bits = Src->used * CHAR_BIT, i = 0, b, end = bits;

	for ( b = 0; b < bits; ++b )
	{
		size_t byte = b / CHAR_BIT;
		size_t bit = 1u << (b % CHAR_BIT);
		bool dir = !!(src[byte] & bit);

		n = tree + n->nxt[dir];

		if ( n->sym[0] )
		{
			strcat( str, n->sym );
			n = tree;
		}
	}

	Dst = buff_inc_only( Alloc, Dst, uchar, bits );

	if ( !Dst )
		return NULL;

	dst = Dst->addr;

	return Dst;
}

Still getting some garbage though, I think that might just be an overlooked size statement though

Found some more information on IDAT format (which gave at least some of what I was looking for in regards it's contents and how it should be handled), modified a duplicate of Scanlines & renamed the original to ScanlinesIR (for Y/Imaginary by X/Real), got as far as the below with another PNG that had just one color (easier to read the data and see where I'm going wrong).

Tutorial/Implementing a Basic PNG reader the handmade way | handmade.network Wiki (Look for "Fun Part Starts Here")

Output:

Code:

./a.out
0 'IHDR'
1 'PLTE'
2 'IDAT'
3 'IEND'
Bit Depth: 1
Colour Type: 0x00000003
Compression Method: 0x00000000
Filter Method: 0x00000000
Interlace Method: 0x00000000
SpanX = 256
SpanY = 256
Depth: 1
Bytes: 1
Expect: 65792
Given: 31
Given * Bytes: 31
Flags: 0x00000003
Compression Method: 0x00000000
Filter Method: 0x00000000
Interlace Method: 0x00000000
Palette Contents:
	 127 127 127
Data Contents:
	 0 0 0 0 0 0 0 0 0 0
	 0 0 0 0 0 0 0 0 0 0
	 0 0 0 0 0 0 0 0 0 0
	 0 0 0 0 0 0 0 0 0 0
~
Last 3 numbers should be '0x7F7F7F00 0 1' for this image
~
0 0xD0D0B500 0 1
1 0x00D0D000 1 1
2 0x00D0D000 1 1
3 0xD0D0B500 0 1
4 0x00D0D000 1 1
5 0xD0D0B500 0 1
6 0xD0D0B500 0 1
7 0xD0D0B500 0 1
8 0x00D0D000 1 1
...

Scanlines():

Code:

void ScanLines( SCANLINE *Scan )
{
	uint bytes = (Scan->Flags & 2) + 1;
	PrintScanLines( Scan );
	PrintData( Scan->Palette, bytes * CHAR_BIT, bytes, "Palette" );
	PrintData( Scan->Data, Scan->Depth * 10, 10, NULL );

	if ( Scan->Flags & 1 )
	{
		ulong *into = Scan->Into->addr;
		uchar *data = Scan->Data->addr;
		uchar *dyes = Scan->Palette->addr;
		uint b = 0, t = 0;
		uint m = 1u << (CHAR_BIT - 1);
		uint SpanR = Scan->SpanR;
		uint SpanI = Scan->SpanI;
		uint Depth = Scan->Depth;
		uint size = (Scan->Flags & 2) + 1;
		uint bytes = (Depth / CHAR_BIT) + !!(Depth % CHAR_BIT);
		uint expect = SpanI * (SpanR + 1 * bytes);
		bool huffman = false;

		memset( into, 0, Scan->Into->size );

		while ( b < expect )
		{
			uint c = 0, d;
			ulong *dst = into + t;
			uchar *dye;

			for ( d = 0; d < Depth; ++d, ++b )
			{
				uint B = b / CHAR_BIT;
				uint M = m >> (b % CHAR_BIT);
				//uint M = 1 << (b % CHAR_BIT);
				c <<= 1;
				c |= !!(data[B] & M);
			}

			*dst = 0;
			dye = dyes + c;
			fill_at_end( dst, 4, dye, size );

#if 1 && !defined( USING_EOG )
			printf( "%u 0x%08lX %u %u\n", t, *dst, c, d );
#endif

			huffman = !huffman;
			// if ( !huffman )
				++t;
		}

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

Anyone able to see where I'm going wrong?

I managed to load the first single colour image correctly, currently hacky as I ignored the huffman bits under the condition there was only one colour in the palette, working on using those bits next.

Had some success understanding the IDAT bits now, some, not complete success:

Code:

0 'IHDR'
1 'PLTE'
2 'IDAT'
3 'IEND'
SpanX = 256
SpanY = 256
Depth: 1
Bytes: 1
Expect: 65792
Given: 31
Given * Bytes: 31
Flags: 0x00000003
Compression Method: 0x00000000
Filter Method: 0x00000000
Interlace Method: 0x00000000
0 value = 0x00ED8168 header = 0, type = 0
1 value = 0x000D01C1 header = 4, type = 0

Code:

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 = header;
			size_t count = 0, pos = 0;
			ulong *dst = into + t;

			base = tree;

			if ( header & 4 )
			{
				type ^= 4;
				final_block = true;
			}

			if ( type == 3 )
			{
				//final_block = true;
				*dst = 0xC0FFEE;
			}
			else if ( type == 2 )
			{
				uint maxbits = CHAR_BIT * sizeof(ulong);
				uint h = GetForewardBitsR( Scan->Data, b, 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, 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
			{
				count = size * 8;
				*dst = GetForewardBitsR( Scan->Data, b, count );
			}

#if 1 && !defined( USING_EOG )
			if ( t < CHAR_BIT )
				printf( "%u value = 0x%08lX header = %X, type = %u\n", t, *dst, header, type );
#endif

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

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

I can at least read the bit headers correctly now, next will be to use the types correctly as currently. Not sure about the colour tree I built from palette though, I'll revist that after I get a more "complete" image out of the few bytes I'm given by the file

Originally Posted by ghoul

Create a thread, spam it till the end of time....

hello awsdert

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