Thread: Increment gone wrong

  1. #91
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,432
    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

  2. #92
    Registered User
    Join Date
    May 2012
    Location
    Arizona, USA
    Posts
    794
    Quote Originally Posted by awsdert View Post
    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
    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.

  3. #93
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,432
    Quote Originally Posted by christop View Post
    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.

  4. #94
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,432
    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;
    }

  5. #95
    Registered User
    Join Date
    Sep 2020
    Posts
    296
    Quote Originally Posted by awsdert View Post
    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:
    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.

  6. #96
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,432
    Quote Originally Posted by hamster_nz View Post
    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

  7. #97
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,432
    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 */
    	}

  8. #98
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,432
    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.

  9. #99
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,432
    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

  10. #100
    Registered User
    Join Date
    Sep 2020
    Posts
    296
    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.

  11. #101
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,432
    Quote Originally Posted by hamster_nz View Post
    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/

  12. #102

  13. #103
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,432
    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

  14. #104
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,432
    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()

  15. #105
    Registered User
    Join Date
    Sep 2020
    Posts
    296
    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
    Last edited by hamster_nz; 08-26-2021 at 04:20 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. hex increment
    By davidx in forum C Programming
    Replies: 3
    Last Post: 10-19-2019, 07:06 AM
  2. Two pre increment in one expression
    By h255874 in forum C Programming
    Replies: 4
    Last Post: 09-21-2019, 08:47 AM
  3. Post Increment an Pre Increment operators in c++
    By anil_ in forum C++ Programming
    Replies: 4
    Last Post: 11-12-2011, 08:27 PM
  4. can't get loop to increment
    By rivkyfried1 in forum C Programming
    Replies: 2
    Last Post: 10-11-2010, 04:03 AM
  5. Post increment and pre increment help
    By noob2c in forum C++ Programming
    Replies: 5
    Last Post: 08-05-2003, 03:03 AM

Tags for this Thread