Thread: Increment gone wrong

Turned out the 0 pixel issue was caused by accidentally using the wrong name when extracting rows, now I'm just trying to figure out why the filter value comes out wrong which is causing the failure scenario to be seen on basn0g01.png (and surely others besides), if anyone has any ideas I'm all eyes, for now though I will get my daily japanese language revision done and read the bible before I start comparing my zlib code (which is the only possible cause I can think of)

Edit: Files * 84cbb3d3a8c6df028bfd317581a165f2d88255e3 * Lee Shallis / glEngine * GitLab

Originally Posted by christop

That sounds like a distro that I'd avoid if they have such egregious bugs in their C library. Do you recall which distro it was? There's a lot of software out there that assumes it can safely pass a null pointer to free and realloc, because both are guaranteed by the standards to work. I'd expect problems left and right if the C library in that distro had that kind of bug (unless you were actually using a different C library than the rest of the distro, like musl or dietlibc?).

Either way, if free and/or realloc don't work the way they're supposed to, it's a bug in the library that should be reported to the maintainer of that library.

Nope, don't remember, was quite a while back, either way since I like to make a habit of programing for worst case scenario I just do so, at the very least it makes porting between systems easier and thus more likely that others will try the code on their systems because they don't have to put as much effort into getting it to compile & run.

While I've yet to reproduce the image correctly I seem to have figured out where I was going wrong in regards the incorrect filter value, was not supposed to treat the extracted bytes as a byte stream but rather a bit stream:

Code:

int Filter( IMAGE *Image, BIT *pos, ulong p )
{
	BUFFERS *Buffers = Image->Buffers;
	BUFFER *Data = AccessBuffer( Buffers, Image->DataID );
	BUFFER *View = AccessBuffer( Buffers, Image->ViewID );
	uchar *view = View->addr, *data = Data->addr;
	ulong size = (Image->Flags & 2) + 1, A, B, C = 0;
	ulong x = p, col, Cols = Image->Cols, RowSize = Cols * sizeof(ulong);
	uchar *a = (uchar*)&A, *b, *c, filter = 0, bit;
	FILE *errors = Buffers->Alloc->errors;
	FILE *detailed = Image->Buffers->Alloc->detailed;

	ForeBits( &filter, data, pos->abs, 3 );

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

	AddBit( pos, data, 3 );

	if ( filter > 1 && x < RowSize )
	{
		ECHO( errors, ECHO_ERR( errors, EINVAL ) );
		return EINVAL;
	}

	switch ( filter )
	{
		/* raw */
		case 0:
			for ( col = 0; col < Cols; ++col )
			{
				uchar raw[sizeof(ulong)] = {0};

				ForeBits( raw, data, pos->abs, Image->Depth );
				AddBit( pos, data, Image->Depth );

				for ( B = 0; B < size; ++B, ++x )
					view[x] = raw[B];

				x += sizeof(ulong) - size;
			}
			break;
		/* pixel behind */
		case 1:
			A = 0;
			for ( col = 0; col < Cols; ++col )
			{
				uchar raw[sizeof(ulong)] = {0};

				ForeBits( raw, data, pos->abs, Image->Depth );
				AddBit( pos, data, Image->Depth );

				for ( B = 0; B < size; ++B, ++x )
					a[B] = view[x] = raw[B] + a[B];

				x += sizeof(ulong) - size;
			}
			break;
		/* pixel above */
		case 2:
			for ( col = 0; col < Cols; ++col )
			{
				uchar raw[sizeof(ulong)] = {0};

				ForeBits( raw, data, pos->abs, Image->Depth );
				AddBit( pos, data, Image->Depth );

				b = view + (x - RowSize);

				for ( B = 0; B < size; ++B, ++x )
					view[x] = raw[B] + b[B];

				x += sizeof(ulong) - size;
			}
			break;
		/* pixel average */
		case 3:
			A = 0;
			for ( col = 0; col < Cols; ++col )
			{
				uchar raw[sizeof(ulong)] = {0};

				ForeBits( raw, data, pos->abs, Image->Depth );
				AddBit( pos, data, Image->Depth );

				b = view + (x - RowSize);

				for ( B = 0; B < size; ++B, ++x )
					a[B] = view[x] = raw[B] + (((uint)a[B] + (uint)b[B]) / 2);

				x += sizeof(ulong) - size;
			}
			break;
		/* paeth predictor */
		case 4:
			A = 0;
			c = (uchar*)&C;
			for ( col = 0; col < Cols; ++col )
			{
				uchar raw[sizeof(ulong)] = {0};
				uchar *t = b = view + (x - RowSize);

				ForeBits( raw, data, pos->abs, Image->Depth );
				AddBit( pos, data, Image->Depth );

				for ( B = 0; B < size; ++B, ++x )
					a[B] = view[x] =
						raw[B] + PaethPredictor( a[B], b[B], c[B] );

				x += sizeof(ulong) - size;
				c = t;
			}
			break;
		default:
			ECHO( errors, ECHO_ERR( errors, EINVAL ) );
			return EINVAL;
	}

	return 0;
}

int ScanLines( IMAGE *Image )
{
	ulong Cols = Image->Cols;
	ulong RowSize = Cols * sizeof(ulong);
	ulong p;
	BUFFER *Data = AccessBuffer( Image->Buffers, Image->DataID );
	BIT pos;

	SetBit( &pos, Data->addr, 0 );

	for ( p = 0; p < Image->Pixels; p += RowSize )
	{
		int err = Filter( Image, &pos, p );

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

	return 0;
}

Originally Posted by hamster_nz

What you said there makes little sense to me. I think you need to carefully consider the structure of the file and re-evaluate how you are processing it.

Map out what the possible inputs are (the different filter methods, greyscale, RGB, with/without alpha, with/without a pallet, 1/2/4/8/16 bits per channel) and how you take all these and map them though your common output format.

Don't try to go from start format to output format in one bit of code, it's too hard.

Aside from an unprocessed gamma chunk (merely sitting in thelist of chunks atm) the image I'm testing on now only has 1 IHDR, 1IDAT & 1 IEND chunk each so I'm pretty sure I'm working with raw values here at the moment, for reference I changed the test image I'm working with to ./pngsuite/basn0g01.png, only black & white there so 1 bit makes sense, likely I just need to multiply the values against something (possibly that gamma value) that produces 0xFF to get the only 2 values should be getting 0x00 & 0xFF

Gotta go to the bank so I'll leave this problem here, maybe someone can figure what I'm doing wrong.

Code:

	float gamma = 1.0;

	if ( GammaID >= 0 )
	{
		ulong val = 0;
		CHUNK *Chunk = chunks + GammaID;
		BUFFER *Gamma = AccessBuffer( Buffers, Chunk->DataID );
		ForeBits( &val, Gamma->addr, 0, Chunk->Size * 8 );
		large_endian_to_local_endian( &val, Chunk->Size );
		gamma = *((float*)&val);
		/* Resulting output value is 0.0 which is likely incorrect, already tried bit shifting val before the endian fix, same result */
	}

I found a bug in my zlib code, specifically when declaring the length of a UID (after the type symbols, so either code or loop symbols), since it's not something I can figure out on the spot I'm gonna dump the hole function use for both (since they can be read the same even if I have to assume the rest):

Code:

void * LoadZlibHuffs( ZLIB *zlib, uint starting_lit )
{
	uint lit = starting_lit;
	ZLIB_SYMBOLS_ID id = lit ? ZLIB_SYMBOLS_ID_LOOP : ZLIB_SYMBOLS_ID_CODE;
	ZLIB_SYMBOLS *Types = &(zlib->Symbols[ZLIB_SYMBOLS_ID_TYPE]);
	ZLIB_SYMBOLS *Symbols = &(zlib->Symbols[id]);
	int pos = 0, used = 0, stop = Symbols->foresee;
	BUFFER *Entries = AccessBuffer( zlib->Buffers, Symbols->entries );
	ZLIB_SYMBOL *symbols, *symbol;
	STREAM *Stream = zlib->Stream;
	FILE *errors = zlib->Buffers->Alloc->errors;

	symbols = ExpandZlibSymbolsBuffer( Symbols, stop + 1 );

	if ( !symbols )
	{
		ECHO
		(
			errors,
			fputs( "Couldn't allocate memory for symbols\n", errors );
			ECHO_ERR( errors, ENOMEM )
		);
		return NULL;
	}

	memset( symbols, 0, Entries->size );
	//stop += !starting_lit;

	while ( pos < stop && Stream->err != EOF )
	{
		int i = 0, copy = 0;
		uintmax_t val;
		ZLIB_SYMBOL *type = SeekZlibSymbol( Stream, Types );

		if ( !type )
		{
			ECHO
			(
				errors,
				fputs( "Couldn't find symbol!\n", errors );
				EchoZlibSymbolsListDetails( errors, zlib, ZLIB_SYMBOLS_ID_TYPE );
				ECHO_ERR( errors, EINVAL )
			);
			return NULL;
		}

		val = StreamBits( Stream, type->get, true );

		copy = (uint)(type->cpy + val);

		i = 0;

		do
		{
			if ( pos >= Entries->have )
			{
				ECHO( errors, ECHO_ERR( errors, ERANGE ) );
				return NULL;
			}

			symbol = symbols + pos;
			symbol->src = pos;
			symbol->lit = lit;

			if ( !copy || (!starting_lit && lit >= 256) )
			{
				symbol->use = true;

				if ( starting_lit )
				{
					symbol->len = type->len + 1;
					symbol->get = implied_loop_data.get[pos];
					symbol->cpy = implied_loop_data.cpy[pos];
				}
				else
				{
					symbol->len = (lit >= 256) ? 4 : used + 1;
					symbol->cpy = (lit > 256) ? used : 0;
				}

				if ( symbol->len > Symbols->longest )
					Symbols->longest = symbol->len;

				++used;
			}

			++lit;
			++pos;
			++i;
		}
		while ( i < copy );
	}

	Entries->used = stop + 1;

	InitZlibSymbolUIDs( Symbols );

	SortZlibSymbolsByUID( zlib, id );

	return symbols;
}

Look for the line containing "if ( !copy || (!starting_lit && lit >= 256) )" then look at the else statement contained inside, that's where the bug lays, I believe it only occurs on code symbols, loop & type symbols appear to be fine as is since their lengths are more explicit than implicit in nature.

For anyone that was trying to help this is what I've managed to come up with so far:

Code:

			if ( !copy || (!starting_lit && lit >= 256) )
			{
				if ( starting_lit )
				{
					symbol->len = type->len + 1;
					symbol->get = implied_loop_data.get[pos];
					symbol->cpy = implied_loop_data.cpy[pos];
				}
				else
				{
					symbol->use = true;
					symbol->len = len;
					symbol->cpy = (lit > 256) ? used : 0;

					++uid;

					if ( uid >= max )
					{
						int left = Symbols->foresee - pos;

						max *= 2;
						len *= 2;

						if ( left <= pos )
							max *= 2;
					}
				}

Just need some way to trigger that 2nd max * 2 as the current method "if ( left <= pos )" doesn't work, supposed to stop doubling once there's enough bits for the remaining UIDs to set

Originally Posted by hamster_nz

I did try taking a look at your code, but without comments to let me know what each step was doing I was unable to follow what was being attempted.

Huh, I thought the function names were enough, mind pointing me to where you were looking at that wasn't enough?

Edit: Since the links are starting to get buried again I'll list out all the ones I still have open and add the rest to a later post that I will likely have to make

RFC 1951 DEFLATE Compressed Data Format Specification ver 1.3
Understanding gzip
Let&#39;s implement zlib.decompress()
How PNG Works. The Portable Network Graphics (PNG) has… | by Colt McAnlis | Medium
PngSuite - the official set of PNG test images
https://pyokagan.name/blog/2019-10-14-png/

Just in case anyone who is/was having a look, I've done a new upload:

Files * 3de1a604aba875d3e6c40ed1813dd1c6449c5bde * Lee Shallis / glEngine * GitLab

Found another document for zlib decompression, btw I briefly plugged in the official libary to check wether my filters were ok, only check one image but after a couple of edits it's now coming out fine so I know the problem lies solely in my zlib code

assorted/Deflate (zlib) compressed data format.asciidoc at main * libyal/assorted * GitHub

I think I figured out the source of my zlib code fault, fixing it on the other hand is proving difficult as I don't know what to actually use there, I believe the fault lies in how I decide the lookup/repeat values in ExpandZlibStreamType2()

Here's the whole algorithm at a very high level:

1. Read in the three 5-bit values, hlit, hdist and hclen. Note that these need to have 257, 1 and 4 added to the 5-bit binary values that are read.


2. Set the value of a 19-entry code length table to zero


3. Read in hclen count of 3-bit values, and then use those to fill some of the 19-entry code length table, in this order:
16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15


4. Create Huffman codewords for the non-zero length values in that table.


5. Zero out a larger code length table, that has hlit+hdisk entries.


6. Read in data using the codewords generated in step 4, and populate the lengths in the larger length table zeroed in step 5 (codes greater than 15 encode repeats and blocks of zero).


7. Create Huffman codewords for the non-zero length values in the first 'hlit' entries of the larger length table - these are the 'literal+repeat' codewords.


8. Then create a second set of Huffman codewords, for 'hdist' entries in the table starting at 'hlit'. These are the 'distance' codewords.

9. Use the 'leteral+repeat' codewords, and the 'distance' codewords to decode the compressed data.

Those are the steps that your code needs to take.

Here is the log of this process:

Code:

Compressed (dynamic dictionary)
  HLIT 282, HDIST 29, HCLEN 13
Codelen table
    0:  4 1100
    4:  4 1101
    5:  3 000
    6:  3 001
    7:  3 010
    8:  3 011
    9:  3 100
   10:  3 101
   11:  4 1110
   12:  5 11110
   16:  6 111110
   17:  7 1111110
   18:  7 1111111
Reading in literal/length plus distance dictionary lengths
Literal/Repeat Length table
   10:  7 1011010
   32:  5 00100
   33:  9 111101000
   34:  8 11100010
   35: 12 111111111100
   37:  8 11100011
   38:  8 11100100
   39:  9 111101001
   40:  7 1011011
   41:  6 011110
   42:  9 111101010
   43:  7 1011100
   44:  6 011111
   45:  8 11100101
   46:  9 111101011
   47:  9 111101100
   48:  7 1011101
   49:  6 100000
   50:  6 100001
   51:  7 1011110
   52:  7 1011111
   53:  7 1100000
   54:  7 1100001
   55:  7 1100010
   56:  7 1100011
   57:  7 1100100
   58:  8 11100110
   59:  7 1100101
   60:  8 11100111
   61:  8 11101000
   62:  8 11101001
   63: 11 11111110010
   64: 11 11111110011
   65: 10 1111101100
   66: 10 1111101101
   67:  9 111101101
   68: 10 1111101110
   69:  9 111101110
   70:  9 111101111
   71: 11 11111110100
   72: 10 1111101111
   73:  9 111110000
   76:  8 11101010
   77: 11 11111110101
   78:  9 111110001
   79: 10 1111110000
   80: 12 111111111101
   82: 11 11111110110
   83: 10 1111110001
   84: 10 1111110010
   85: 10 1111110011
   87: 12 111111111110
   90: 11 11111110111
   91:  9 111110010
   92: 11 11111111000
   93:  8 11101011
   94: 11 11111111001
   95:  7 1100110
   97:  6 100010
   98:  8 11101100
   99:  7 1100111
  100:  6 100011
  101:  6 100100
  102:  7 1101000
  103:  8 11101101
  104:  7 1101001
  105:  6 100101
  106: 11 11111111010
  107:  9 111110011
  108:  7 1101010
  109:  8 11101110
  110:  6 100110
  111:  6 100111
  112:  7 1101011
  114:  6 101000
  115:  6 101001
  116:  6 101010
  117:  7 1101100
  118:  9 111110100
  119:  8 11101111
  120:  9 111110101
  121:  8 11110000
  122: 10 1111110100
  123: 10 1111110101
  124: 10 1111110110
  125:  7 1101101
  256: 12 111111111111
  257:  4 0000
  258:  4 0001
  259:  5 00101
  260:  5 00110
  261:  5 00111
  262:  5 01000
  263:  5 01001
  264:  5 01010
  265:  5 01011
  266:  5 01100
  267:  5 01101
  268:  6 101011
  269:  5 01110
  270:  6 101100
  271:  7 1101110
  272:  7 1101111
  273:  7 1110000
  274:  8 11110001
  275:  8 11110010
  276:  8 11110011
  277: 10 1111110111
  278: 10 1111111000
  279: 11 11111111011
  280: 11 11111111100
  281: 11 11111111101
Distance table
    0:  7 1111100
    2:  9 111111110
    3:  9 111111111
    4:  8 11111100
    5:  8 11111101
    6:  6 111100
    7:  7 1111101
    8:  5 10110
    9:  4 0000
   10:  5 10111
   11:  5 11000
   12:  4 0001
   13:  4 0010
   14:  4 0011
   15:  4 0100
   16:  4 0101
   17:  5 11001
   18:  4 0110
   19:  4 0111
   20:  4 1000
   21:  5 11010
   22:  4 1001
   23:  5 11011
   24:  4 1010
   25:  5 11100
   26:  5 11101
   27:  6 111101
   28:  8 11111110