Thread: Increment gone wrong

Just as I was going to answer I realise what you're on about, that's a doozy of a mistake, thanks

Originally Posted by hamster_nz

The question you need to ask yourself is not "How did that bug get there?" but "How did this bad a bug go undetected for so long?".

That allocator must have never been used to grow a memory allocation, as it would always allocate a new block memory.

Also, it would only "empty out" the tail of this newly allocated memory, possibly leaving random junk in the front of the block.

It went undetected because linux does it's job a little too well, I would prefer it to leave allocations uninitialised so that I can catch these sorts of problems earlier, anyways I managed to resolve the iDAT mis-read, struggling to fix the scanline mis-use though:

Code:

ulong FilterColour( IMAGE_PNG *Image, ulong pixel, ulong colour, ulong add, ulong FMethod )
{
	BUFFER *Into = AccessBuffer( Image->Buffers, Image->RawImg );
	ulong *into = Into->addr;
	ulong sx = Image->SpanX;
	ulong py = pixel / sx;
	ulong px = pixel % sx;
	ulong c;
	FILE *detailed = Image->Buffers->Alloc->detailed;

	switch ( FMethod )
	{
	case 1: colour = into[((py+1)*sx)+px]; break;
	case 2: colour = into[((py-1)*sx)+px]; break;
	default: colour = 0;
	}

	c = AddColour( colour, add );

	if ( detailed )
	{
		fprintf
		(
			detailed,
			"FilterColour( %p, %lu, %08lX, %08lX, %04lX ) c = %08lX\n",
			(void*)Image,
			pixel,
			colour,
			add,
			FMethod,
			c
		);
	}

	return c;
}

void ScanLines( IMAGE_PNG *Image )
{
	BUFFERS *Buffers = Image->Buffers;
	BUFFER *Into = AccessBuffer( Buffers, Image->RawImg );
	STREAM Stream = {0};
	STREAM_BUFFER_ID StreamID = {0};
	uchar *into = Into->addr;
	FILE *verbose = Buffers->Alloc->verbose;
	FILE *detailed = Buffers->Alloc->detailed;
	//uint size = (Image->Flags & 2) + 1;
	//uint bits = size * 8;
	//float gama = Image->Gama;

	int p = 0, x, y = 0;

	if ( verbose )
	{
		ECHO( verbose, fprintf( verbose, "ScanLines( %p )\n", (void*)Image ) );
		EchoImagePNGDetails( Image );
	}

	Stream.data = &(StreamID);
	Stream.DataCB = StreamDataFromBufferIndex;

	StreamID.id = Image->Lazy;
	StreamID.Buffers = Buffers;

	for ( p = 0, y = 0; y < Image->SpanY; ++y )
	{
		uint filter = StreamBits( &Stream, 8, true );
		uint add = 0;

		for ( x = 0; x < Image->SpanX; ++x, ++p )
		{
			uint dye = StreamBits( &Stream, 8, true );
			ECHO( detailed, );
			into[p] = add = FilterColour( Image, p, dye, add, filter );
			if ( detailed )
				fputc( '\n', detailed );
		}
	}
}

Lemme know if you spot what I'm doing wrong (assuming you're interested enough to look), since the link is now buried under many posts I'll add a new link for the project to this post

GLEngine

Okay I think I'm going in the right direction now as seem to be stopping a the correct pixel now, since I'm unfamiliar with the filtering and reconstruction, let alone the gamma and sBIT values that are included in a singular pixel image example (I'll add link at bottom of post), I need some ideas on how to correct the below:

Code:

ulong AddColours( ulong one, ulong two )
{
	ulong r1 = (one & 0xFF000000) >> 24;
	ulong g1 = (one & 0xFF0000) >> 16;
	ulong b1 = (one & 0xFF00) >> 8;
	ulong a1 = (one & 0xFF);
	ulong r2 = (two & 0xFF000000) >> 24;
	ulong g2 = (two & 0xFF0000) >> 16;
	ulong b2 = (two & 0xFF00) >> 8;
	ulong a2 = (two & 0xFF);
	one = 0;
	one |= ((r1 + r2) & 0xFF) << 24;
	one |= ((g1 + g2) & 0xFF) << 16;
	one |= ((b1 + b2) & 0xFF) << 8;
	one |= ((a1 + a2) & 0xFF);
	return one;
}

ulong SubColours( ulong one, ulong two )
{
	ulong r1 = (one & 0xFF000000) >> 24;
	ulong g1 = (one & 0xFF0000) >> 16;
	ulong b1 = (one & 0xFF00) >> 8;
	ulong a1 = (one & 0xFF);
	ulong r2 = (two & 0xFF000000) >> 24;
	ulong g2 = (two & 0xFF0000) >> 16;
	ulong b2 = (two & 0xFF00) >> 8;
	ulong a2 = (two & 0xFF);
	one = 0;
	one |= ((r1 - r2) & 0xFF) << 24;
	one |= ((g1 - g2) & 0xFF) << 16;
	one |= ((b1 - b2) & 0xFF) << 8;
	one |= ((a1 - a2) & 0xFF);
	return one;
}

ulong PaethPredictor( ulong a, ulong b, ulong c )
{
	ulong p = SubColours( AddColours( a, b ), c );
	ulong pa = SubColours( p, a );
	ulong pb = SubColours( p, b );
	ulong pc = SubColours( p, c );

	if ( pa <= pb && pa <= pc )
		return a;

	if ( pb <= pc )
		return b;

	return c;
}

ulong FilterColour( IMAGE_PNG *Image, long p, long x, uint filter )
{
	BUFFER *Lazy = AccessBuffer( Image->Buffers, Image->Lazy );
	uchar *lazy = Lazy->addr;
	ulong dye, a, b, c;
	FILE *detailed = Image->Buffers->Alloc->detailed;

	a = x - 1;
	b = x - (Image->SpanX + 1);
	c = b - 1;

	switch ( filter )
	{
	case 1: dye = AddColours( lazy[x], lazy[a] ); break;
	case 2: dye = AddColours( lazy[x], lazy[b] ); break;
	case 3: dye = AddColours( lazy[x], AddColours( lazy[a], lazy[b] ) / 2 );  break;
	case 4:
		dye = PaethPredictor
		(
			AddColours( lazy[x], lazy[a] ),
			AddColours( lazy[x], lazy[b] ),
			AddColours( lazy[x], AddColours( lazy[a], lazy[b] ) / 2 )
		);
		break;
	default: dye = lazy[x];
	}

	if ( detailed )
	{
		fprintf
		(
			detailed,
			"FilterColour( %p, %ld, %ld, %02X ) dye = %08lX\n",
			(void*)Image,
			p,
			x,
			filter,
			dye
		);
	}

	return dye;
}

void ScanLines( IMAGE_PNG *Image )
{
	BUFFERS *Buffers = Image->Buffers;
	BUFFER *Lazy = AccessBuffer( Buffers, Image->Lazy );
	BUFFER *Into = AccessBuffer( Buffers, Image->RawImg );
	uchar *into = Into->addr, *lazy = Lazy->addr;
	FILE *verbose = Buffers->Alloc->verbose;
	FILE *detailed = Buffers->Alloc->detailed;
	//uint size = (Image->Flags & 2) + 1;
	//uint bits = size * 8;
	//float gama = Image->Gama;

	long p = 0, x = 0, X, Y = 0;

	if ( verbose )
	{
		ECHO( verbose, fprintf( verbose, "ScanLines( %p )\n", (void*)Image ) );
		EchoImagePNGDetails( Image );
	}

	for ( p = 0, Y = 0; Y < Image->SpanY; ++Y )
	{
		uint filter = lazy[x];

		for ( X = 0, ++x; X < Image->SpanX; ++X, ++p, ++x )
		{
			ECHO( detailed, );
			into[p] = FilterColour( Image, p, x, filter );
			if ( detailed )
				fputc( '\n', detailed );
		}
	}
}

A reference for the filter method I've been using:
Writing a (simple) PNG decoder might be easier than you think

The suite of images I'm testing against (in addition to the one mentioned in the blog)
PngSuite - the official set of PNG test images

The specific image I'm starting with:
http://www.schaik.com/pngsuite/s01n3p01.png

Finally noticed part of what caused my filter to be wrong, I misunderstood how big the values I'm supposed to get are, here's the partially corrected algorithm:

Code:

uchar FilterColour( IMAGE_PNG *Image, long p, long x, uchar val, uint filter )
{
	BUFFER *Lazy = AccessBuffer( Image->Buffers, Image->Lazy );
	BUFFER *Into = AccessBuffer( Image->Buffers, Image->Lazy );
	uchar *into = Into->addr;
	uchar *lazy = Lazy->addr;
	uchar dye;
	long a, b, c;
	FILE *detailed = Image->Buffers->Alloc->detailed;

	a = x - 1;
	b = x - Image->SpanX;
	c = b - 1;

	switch ( filter )
	{
	case 1: dye = into[x] + into[a]; break;
	case 2: dye = into[x] + into[b]; break;
	case 3: dye = into[x] + ((into[a] - into[b]) / 2 );  break;
	case 4:
		dye = PaethPredictor
		(
			into[x] + into[a],
			into[x] + into[b],
			into[x] + (( into[a] - into[b] ) / 2 )
		);
		break;
	default: dye = into[x];
	}

	if ( detailed )
	{
		fprintf
		(
			detailed,
			"FilterColour( %p, %ld, %ld, %02X, %u ) dye = %02X\n",
			(void*)Image,
			p,
			x,
			val,
			filter,
			dye
		);
	}

	return dye + val;
}

void ScanLines( IMAGE_PNG *Image )
{
	BUFFERS *Buffers = Image->Buffers;
	BUFFER *Lazy = AccessBuffer( Buffers, Image->Lazy );
	BUFFER *Into = AccessBuffer( Buffers, Image->RawImg );
	uchar *into = Into->addr, *lazy = Lazy->addr;
	FILE *verbose = Buffers->Alloc->verbose;
	FILE *detailed = Buffers->Alloc->detailed;
	uint size = (Image->Flags & 2) + 1;
	//uint bits = size * 8;
	//float gama = Image->Gama;

	long p = 0, x = 0, X, Y = 0, B, b = 0;

	if ( verbose )
	{
		ECHO( verbose, fprintf( verbose, "ScanLines( %p )\n", (void*)Image ) );
		EchoImagePNGDetails( Image );
	}

	for ( p = 0, x = 0, Y = 0; Y < Image->SpanY; ++Y )
	{
		uint filter = lazy[b];
		//FlipBits( &filter, CHAR_BIT );

		for ( X = 0, ++b; X < Image->SpanX; ++X, ++p, ++b )
		{
			for ( B = 0; B < size; ++B, ++x )
			{
				ECHO( detailed, );
				into[x] = FilterColour( Image, p, x, lazy[b], filter );
				if ( detailed )
					fputc( '\n', detailed );
			}
			++x;
		}
	}
}

Originally Posted by hamster_nz

I worked out what I don't like the feel of in default_allocator(), and that is that the user must specify the "had" amount correctly for it to work correctly.

Quite often you don't keep track of the size of the allocation. Something like:

Code:

    new_length = strlen(my_string)+strlen(extra_string)+1;
    my_string = realloc(my_string, new_length);  // Ignoring error checking for clarity
    strcat(my_string, extra_string);

And default_allocator() this forces you to remember the length of any allocation that you intend to grow.

Well it intentionally modeled the same way lua expects it because I want to be able to grab that same allocator and user data that lua holds and pass it on to the buffer allocators, that unfortunately means I must include that parameter, otherwise I would agree with you to a certain extent

Realised this page:

Tutorial/Implementing a Basic PNG reader the handmade way | handmade.network Wiki

Laid out most of the filtering algorithm for me, since this currently breaks on the first line (putting aside my oversights on where to put the pixel data after the filtering) I must be doing something wrong before then, haven't seen it yet but I got some stuff to do before I go comparing my code to the page I just linked so if anyone's interested in looking before I do here's the new filter function (because it's probably an imperfect alteration to support colour) and a link for the full upload below it.

Code:

int Filter( IMAGE_PNG *Image, ulong pos, ulong p )
{
	BUFFERS *Buffers = Image->Buffers;
	BUFFER *Lazy = AccessBuffer( Buffers, Image->Lazy );
	BUFFER *Into = AccessBuffer( Buffers, Image->Lazy );
	uchar *into = Into->addr, *lazy = Lazy->addr;
	ulong x = p, X, SpanX = Image->SpanX;
	ulong size = (Image->Flags & 2) + 1, A, B, C = 0;
	uchar *a = (uchar*)&A, *b, *c, filter = lazy[pos++];
	FILE *detailed = Image->Buffers->Alloc->detailed;

	ECHO
	(
		detailed,
		fprintf
		(
			detailed,
			"Filter( %p, %7lu, %7lu ) filter = %u\n",
			(void*)Image, pos, p, filter
		)
	);

	switch ( filter )
	{
		/* raw */
		case 0:
			for ( X = 0; X < SpanX; ++X )
			{
				for ( B = 0; B < size; ++B, ++x, ++pos )
					into[x] = lazy[pos];

				x += sizeof(ulong) - size;
			}
			break;
		/* pixel behind */
		case 1:
			A = 0;
			for ( X = 0; X < SpanX; ++X )
			{
				for ( B = 0; B < size; ++B, ++x, ++pos )
					a[B] = into[x] = lazy[pos] + a[B];

				x += sizeof(ulong) - size;
			}
			break;
		/* pixel above */
		case 2:
			for ( X = 0; X < SpanX; ++X )
			{
				b = into + (x - (SpanX * sizeof(ulong)));

				for ( B = 0; B < size; ++B, ++x, ++pos )
					into[x] = lazy[pos] + b[B];

				x += sizeof(ulong) - size;
			}
			break;
		/* pixel average */
		case 3:
			A = 0;
			for ( X = 0; X < SpanX; ++X )
			{
				b = into + (x - (SpanX * sizeof(ulong)));

				for ( B = 0; B < size; ++B, ++x, ++pos )
				{
					uint a2 = a[B], b2 = b[B];
					a[B] = into[x] = lazy[pos] + ((a2 + b2) / 2);
				}

				x += sizeof(ulong) - size;
			}
			break;
		/* paeth predictor */
		case 4:
			A = 0;
			c = (uchar*)&C;
			for ( X = 0; X < SpanX; ++X )
			{
				uchar *t = b = into + (x - (SpanX * sizeof(ulong)));

				for ( B = 0; B < size; ++B, ++x, ++pos )
				{
					a[B] = into[x] =
						lazy[pos] + PaethPredictor( a[B], b[B], c[B] );
				}

				x += sizeof(ulong) - size;
				c = t;
			}
			break;
		default:
		{
			FILE *errors = Buffers->Alloc->errors;
			ECHO( errors, ECHO_ERR( errors, EINVAL ) );
			return EINVAL;
		}
	}

	return 0;
}

int ScanLines( IMAGE_PNG *Image )
{
	uchar size = (Image->Flags & 2) + 1;
	ulong SpanY = Image->SpanY;
	ulong SpanX = Image->SpanX;
	ulong stride = 1 + (SpanX * size);
	ulong pos, p;

	for ( pos = 0, p = 0; p < Image->Pixels; pos += stride, p += SpanX )
	{
		int err = Filter( Image, pos, p * sizeof(ulong) );

		if ( err )
		{
			FILE *errors = Image->Buffers->Alloc->errors;
			ECHO( errors, ECHO_ERR( errors, err ) );
			return err;
		}
	}

	return 0;
}

Files * 6adf2fec1233cf4787643ef4ac1133b7c4b2a0e0 * Lee Shallis / glEngine * GitLab

Are you sure that you have allowed for the edge case where the filter attempts to address that that are to the left of, or above the visible image?

e.g. output_image[y][x] = output_image[y-1][x] + filtered_data[y][x]

when y is 0?

Oh, and a lot of the variable names make no sense to me : e.g. "lazy", and using both 'x' and 'X' (or 'A' and 'a') as variable names. Might be OK in a spec, but makes for poor code readability.

Originally Posted by hamster_nz

Oh, and this may potentially give different results on big endian or little endian platforms:

Code:

ulong A;
uchar *a = (uchar*)&A;

That one doesn't matter about endian, A always starts at 0 before filtering begins and by means of B as a byte index receives the same values as into[x], this results in the pixel "behind" being access via the value of A, as for above the pixel, yeah I hadn't thought about the y = 0 situation, I can rectify that later, the test images won't produce that situation anyways

Originally Posted by hamster_nz

Are you sure that you have allowed for the edge case where the filter attempts to address that that are to the left of, or above the visible image?

e.g. output_image[y][x] = output_image[y-1][x] + filtered_data[y][x]

when y is 0?

Oh, and a lot of the variable names make no sense to me : e.g. "lazy", and using both 'x' and 'X' (or 'A' and 'a') as variable names. Might be OK in a spec, but makes for poor code readability.

I've only chosen those names so I know what they're supposed to represent in the docs, I usually use similar names if I'm using the one often but need to see what the purpose of the not so often used variable is, so in the case of a & A I can see A is supposed to be what a points to, whereas a is supposed to be a pointer but must always have a valid address in the loops it's used in, x is used to match the name given in the docs and X exists only because x is currently being used to represent pixel byte, when I don't need names matching those in the docs anymore I will use better names, lazy on the other hand is just a left over name from misunderstanding the deflation process, I'll rename it once I think of a good name, dunno why but I like my names to be of the same length where ever possible so if anyone thinks of a good name for "decompressed output" that fits the 4 letter length I've gone with so far I'm all eyes

Originally Posted by christop

In default_allocator, you can simplify the allocation line to this:

Code:

tmp = realloc( ptr, get );

because realloc will allocate new memory if the pointer is null.

Also, you can remove if ( ptr ) above free( ptr ); because free does nothing if the pointer is null (of course, you can find some old, non-standards-compliant C libraries, e.g., PalmOS, that do the wrong thing, but those are extremely obscure and esoteric at this point, and if you wanted to support ancient platforms like that you could write wrapper functions around the broken functions, rather than litter your code with unnecessary if statements).

I once had a bad experience on a modern linux distro when I made that assumption so I just assume the implementation is buggy and wrap around them, keeps the code simple rather than litter with #ifdefs for the sake of an instruction or 2s worth of time saving

After some serious effort I've simplified the loading process for chunks which in turn simplified passing their relative data to the right places, particularly zlib so it should now be impossible for zlib to corrupt the stream position (assuming it was at any point), haven't gotten round to re-naming certain variables I had planned on doing but should be easier to see what is happening at relevant points. Some names have become more generic in the process (for instance IMAGE_PNG became just IMAGE), if anyone is interested in taking a look before I go back to it tomorrow then here's the link:

Files * 5eb8fabd0e8aa4809c286155f53f1e6b2c475d3e * Lee Shallis / glEngine * GitLab

The current critical bug is that the resulting image is 0 pixels according to eog so if you're taking a look I suggest taking a look at the output pic.ppm (which I haven't done yet, plan to do so tomorrow)