Increment gone wrong

Chips are about to burn so I'll edit this after taking them out of the oven, short of it is that on the first incrment code should be 1, not 8

Code:

for ( code = 0, cur_leng = 1; cur_leng <= max_leng; ++cur_leng ) { for ( uint j = 0; j < list.used; ++j ) { CODEWORD *word = _list + j; printf( "Code = " ); SeeBits( &code, max_leng ); putchar('\n'); if ( word->leng != cur_leng ) continue; word->code = code; printf( "_list[%u].code = ", j ); SeeBits( &code, word->leng ); putchar('\n'); ++code; } printf( "Final code for length %u = ", cur_leng ); SeeBits( &code, max_leng ); putchar('\n'); while ( !(code >> cur_leng) ) { uint value = code >> cur_leng; printf( "Code " ); SeeBits( &code, max_leng ); printf( " shifted by %u results in ", cur_leng ); SeeBits( &value, max_leng ); putchar('\n'); ++code; } printf( "Initial expected code for leng %u = ", cur_leng + 1 ); SeeBits( &code, cur_leng + 1 ); putchar('\n'); for ( i = 0; i < list.used; ++i ) { CODEWORD *word = _list + i; if ( word->leng >= cur_leng ) continue; if ( code == (word->code << (cur_leng - word->code)) ) code++; } printf( "Adjusted initial code for leng %u = ", cur_leng + 1 ); SeeBits( &code, cur_leng + 1 ); putchar('\n'); }

Code:

./a.out aba.gz PrintBytes( 0x559c1662c480, 41, 16 ) 1F 8B 0 0 0 0 0 0 0 3 1D C6 49 1 0 0 40 C0 AC A3 7F 88 3D 3C 20 2A 97 9D 37 5E 1D C 29 34 94 23 0 0 0 path = 'aba.gz', max readable bits = 328 gzip.magic = 1F8B, gzip.flags = 0, gzip.mtime = 0, zlib.xflags = 0, zlib.system = 0 gzip.flag_TEXT = false gzip.flag_HCRC = false gzip.flag_MORE = false gzip.flag_NAME = false gzip.flag_NOTE = false gzip.flag_RESERVED = 0 last = true, type = 2 lengc = 260, distc = 7, codec = 18, left = 7 0 _list[16].leng = 4, max_leng 4 1 _list[17].leng = 4, max_leng 4 2 _list[18].leng = 2, max_leng 4 3 _list[ 0].leng = 0, max_leng 4 4 _list[ 8].leng = 0, max_leng 4 5 _list[ 7].leng = 0, max_leng 4 6 _list[ 9].leng = 0, max_leng 4 7 _list[ 6].leng = 0, max_leng 4 8 _list[10].leng = 0, max_leng 4 9 _list[ 5].leng = 0, max_leng 4 10 _list[11].leng = 0, max_leng 4 11 _list[ 4].leng = 4, max_leng 4 12 _list[12].leng = 0, max_leng 4 13 _list[ 3].leng = 0, max_leng 4 14 _list[13].leng = 0, max_leng 4 15 _list[ 2].leng = 1, max_leng 4 16 _list[14].leng = 0, max_leng 4 17 _list[ 1].leng = 4, max_leng 4 i = 18 _list[ 0] = _list[ 1], code = 0, leng = 4 _list[ 1] = _list[ 2], code = 0, leng = 1 _list[ 2] = _list[ 4], code = 0, leng = 4 _list[ 3] = _list[16], code = 0, leng = 4 _list[ 4] = _list[17], code = 0, leng = 4 _list[ 5] = _list[18], code = 0, leng = 2 Code = 0000 Code = 0000 _list[1].code = 0 Code = 1000 Code = 1000 Code = 1000 Code = 1000 Final code for length 1 = 1000 Code 1000 shifted by 1 results in 0000 Initial expected code for leng 2 = 01 Adjusted initial code for leng 2 = 01 Code = 0100 Code = 0100 Code = 0100 Code = 0100 Code = 0100 Code = 0100 _list[5].code = 01 Final code for length 2 = 1100 Code 1100 shifted by 2 results in 0000 Initial expected code for leng 3 = 001 Adjusted initial code for leng 3 = 001 Code = 0010 Code = 0010 Code = 0010 Code = 0010 Code = 0010 Code = 0010 Final code for length 3 = 0010 Code 0010 shifted by 3 results in 0000 Code 1010 shifted by 3 results in 0000 Code 0110 shifted by 3 results in 0000 Code 1110 shifted by 3 results in 0000 Initial expected code for leng 4 = 0001 Adjusted initial code for leng 4 = 0001 Code = 0001 _list[0].code = 0001 Code = 1001 Code = 1001 _list[2].code = 1001 Code = 0101 _list[3].code = 0101 Code = 1101 _list[4].code = 1101 Code = 0011 Final code for length 4 = 0011 Code 0011 shifted by 4 results in 0000 Code 1011 shifted by 4 results in 0000 Code 0111 shifted by 4 results in 0000 Code 1111 shifted by 4 results in 0000 Initial expected code for leng 5 = 00001 Adjusted initial code for leng 5 = 00001 ...

Edit: Now that my chips are safe, the most relevant output is from this part:

Code:

Code = 0000 Code = 0000 _list[1].code = 0 Code = 1000 Code = 1000 Code = 1000 Code = 1000 Final code for length 1 = 1000 Code 1000 shifted by 1 results in 0000 Initial expected code for leng 2 = 01 Adjusted initial code for leng 2 = 01 Code = 0100 Code = 0100 Code = 0100 Code = 0100 Code = 0100 Code = 0100 _list[5].code = 01 Final code for length 2 = 1100 Code 1100 shifted by 2 results in 0000 Initial expected code for leng 3 = 001 Adjusted initial code for leng 3 = 001 Code = 0010 Code = 0010 Code = 0010 Code = 0010 Code = 0010 Code = 0010 Final code for length 3 = 0010 Code 0010 shifted by 3 results in 0000 Code 1010 shifted by 3 results in 0000 Code 0110 shifted by 3 results in 0000 Code 1110 shifted by 3 results in 0000 Initial expected code for leng 4 = 0001 Adjusted initial code for leng 4 = 0001 Code = 0001 _list[0].code = 0001 Code = 1001 Code = 1001 _list[2].code = 1001 Code = 0101 _list[3].code = 0101 Code = 1101 _list[4].code = 1101 Code = 0011 Final code for length 4 = 0011 Code 0011 shifted by 4 results in 0000 Code 1011 shifted by 4 results in 0000 Code 0111 shifted by 4 results in 0000 Code 1111 shifted by 4 results in 0000 Initial expected code for leng 5 = 00001 Adjusted initial code for leng 5 = 00001 ...

The rest I provided just for context, code is an unsigned integer so there's no funny pointer business going on, there's no opotunity to increment code,SeeBits() look like this:

Code:

void SeeBits( void * data, uint bits ) { for ( uint i = 0; i < bits; i += bitsof(uintmax_t) ) { uint left = bits - (i * bitsof(uintmax_t)); uint stop = (left < bitsof(uintmax_t)) ? left : bitsof(uintmax_t); uintmax_t mask = 1; uintmax_t value = GetBits ( data, bits, i * bitsof(uintmax_t), stop, false, false ); for ( mask <<= (stop - 1); mask; mask >>= 1 ) putchar( '0' + !!(value & mask) ); } }

And GetBits() looks like this:

Code:

uintmax_t GetBits( void * data, uint max, uint pos, uint bits, bool backwards, bool left_shifted ) { uchar *temp = data; uint end, i = 0; uintmax_t value = 0; if ( backwards ) { end = (bits <= pos) ? pos - bits : 0; while ( pos > end ) { uint B = --pos / CHAR_BIT; uint b = pos % CHAR_BIT; uchar bit = 1 << b; value <<= 1; value |= !!(temp[B] & bit); ++i; } } else { end = pos + bits; end = (end <= max) ? end : max; while ( pos < end ) { uint B = pos / CHAR_BIT; uint b = pos++ % CHAR_BIT; uchar bit = 1 << b; bool one = !!(temp[B] & bit); value <<= 1; value |= one; ++i; } } if ( left_shifted ) value <<= bits - i; return value; }

I see no chance for the value of "code" to be corrupted, any ideas?

1. Make your SeeBits / GetBits functions take const void * - just because.

2. Put a watchpoint on the variable which is troubling you.
Debugging – Types Of Data Breakpoints In GDB – mohit.io

Turned out I had somehow flipped them in GetBits so SeeBits only saw the flipped version, I'll have to fix that later but for now I'll focus on the deflate algrotihm

Well GetBits is a bloated kitchen-sink function trying to do too much.

bool backwards, bool left_shifted are needless complications.

For my scenario, they're not needless, I have used those values for various things, particularly quick checks on which way I should be reading the bits I'm on.

Are you decoding PNG 'deflate' compression by any chance?

Inspired by your earlier posts I decided that I would attempt this too, and am making good progress.

Shame the RFC is sort of mostly backwards (LSB to the left, MSB to the right). But luckily I am dyslexic, making it no more bother than normal.

Yes I will be doing that, finding this resource extremely helpful in that aspect, also lead me to find a bug in gzip where it sets the NAME flag incorrectly when giving shell input instead of a file

Understanding gzip

I dpn't know if it is of any value, but here is my prototype for getting and consuming bits from the compressed bitstream.

Code:

static uint32_t grab_bits(struct Inflate_data *d) { uint32_t bits=0; // Take the next 24 bits out of the data buffer if(d->byte+0 < d->len) bits |= d->data[d->byte+0]; if(d->byte+1 < d->len) bits |= d->data[d->byte+1] << 8; if(d->byte+2 < d->len) bits |= d->data[d->byte+2] << 16; if(d->bit == 0) return bits; // Don't need the 4th byte if(d->byte+3 < d->len) bits |= d->data[d->byte+3] << 24; return bits >> d->bit; } int consume_bits(struct Inflate_data *d, uint8_t count) { d->bit += count; d->byte += d->bit>>3; d->bit &= 0x7; if(verbose) printf("Consuming %i bits, now %d:%d\n",count, d->byte,d->bit); return (d->byte < d->len); }

Quote:

Originally Posted by hamster_nz

I dpn't know if it is of any value, but here is my prototype for getting and consuming bits from the compressed bitstream.

Code:

static uint32_t grab_bits(struct Inflate_data *d) { uint32_t bits=0; // Take the next 24 bits out of the data buffer if(d->byte+0 < d->len) bits |= d->data[d->byte+0]; if(d->byte+1 < d->len) bits |= d->data[d->byte+1] << 8; if(d->byte+2 < d->len) bits |= d->data[d->byte+2] << 16; if(d->bit == 0) return bits; // Don't need the 4th byte if(d->byte+3 < d->len) bits |= d->data[d->byte+3] << 24; return bits >> d->bit; } int consume_bits(struct Inflate_data *d, uint8_t count) { d->bit += count; d->byte += d->bit>>3; d->bit &= 0x7; if(verbose) printf("Consuming %i bits, now %d:%d\n",count, d->byte,d->bit); return (d->byte < d->len); }

Here's a tip:

Code:

byte = pos / CHAR_BIT; bit = pos % CHAR_BIT;

Quote:

Originally Posted by awsdert

Here's a tip:

Code:

byte = pos / CHAR_BIT; bit = pos % CHAR_BIT;

It's true what they say, premature optimization is the source of all evil :D....

(i.e. I am doing evil using >>3 and &7 )

Quote:

Originally Posted by hamster_nz

It's true what they say, premature optimization is the source of all evil :D....

(i.e. I am doing evil using >>3 and &7 )

I wouldn't call it a source of evil but in this case I would call it more confusing than need be, possibly slower too due to multiple if statements, as a side note I this is what I chose for bit stream management:

Code:

uint IncStreamCount( STREAM *stream, uint bits ) { uint rem = (stream->fed >= bits) ? bits : 0; stream->got >>= rem; stream->fed -= rem; stream->num += rem; return rem; } uintmax_t CopyStreamBits( STREAM *stream, uint bits, bool inc_count ) { uintmax_t val = 0; if ( stream->fed < bitsof(uintmax_t) ) { uint get = bitsof(uintmax_t) - stream->fed; get = (get <= stream->max - stream->pos) ? get : stream->max - stream->pos; val = GetBits ( stream->ptr, stream->max, stream->pos, get, false, false ); stream->got |= val << (bitsof(uintmax_t) - get); stream->fed += get; stream->pos += get; } val = stream->got & ~(~0ULL << bits); if ( inc_count ) IncStreamCount( stream, bits ); return val; }

Using a separate variable for current position versus stream position made it easier to retrieve bits multiple times before moving the stream pointer after identify what was what.

Edit: That "backwards" parameter of GetBits() was used for retrieving the target buffer size at the end of the *.gz file, the left_shifted parameter was solely for instances where I didn't want to complicate the local code further, it's already got unwieldly as it is (plan to clean up after), don't need it getting any further unwieldly.

The comment system of the mentioned documentation in a previous post is lacking when it comes to preformatted text o posting it here than linking to it in a comment on the document.

If anyone happens to see any misinterpretations please do let me know.

Link to document:
Understanding gzip

Section I'm following as best I can:
Dynamic Huffman: Parsing the Huffman tree

Output:

Code:

./a.out aba.gz path = 'aba.gz' PrintStreamDetails( 0x7fff6097e150 ): ptr = 0x55af47400480, pos = 0, num = 0, max = 328, fed = 0 PrintBytes( 0x55af47400480, 41, 16 ) 1F 8B 0 0 0 0 0 0 0 3 1D C6 49 1 0 0 40 C0 AC A3 7F 88 3D 3C 20 2A 97 9D 37 5E 1D C 29 34 94 23 0 0 0 PrintStreamDetails( 0x7fff6097e150 ): ptr = 0x55af47400480, pos = 136, num = 80, max = 328, fed = 56 gzip.magic = 1F8B, gzip.format = 0, gzip.flags = 0, gzip.mtime = 0, zlib.xflags = 0, zlib.system = 3 gzip.flag_TEXT = false, gzip.flag_HCRC = false, gzip.flag_MORE = false, gzip.flag_NAME = false, gzip.flag_NOTE = false, gzip.flag_RESERVED = 0 PrintStreamDetails( 0x7fff6097e150 ): ptr = 0x55af47400480, pos = 136, num = 80, max = 328, fed = 56 last = true, type = 2 lengc = 260, distc = 7, codec = 18, left = 60 pos = 212, max = 328, count = 267 left = 61, byte = 18, bit = 7 Code Table: main.c:647: _list[ 0]: from = 2, more = 0, copy = 0, leng = 1, fill = 'ÿ', code = 0 main.c:647: _list[ 1]: from = 18, more = 7, copy = 11, leng = 2, fill = 'ÿ', code = 10 main.c:647: _list[ 2]: from = 1, more = 0, copy = 0, leng = 4, fill = 'ÿ', code = 1100 main.c:647: _list[ 3]: from = 4, more = 0, copy = 0, leng = 4, fill = 'ÿ', code = 1101 main.c:647: _list[ 4]: from = 16, more = 2, copy = 3, leng = 4, fill = 'ÿ', code = 1110 main.c:647: _list[ 5]: from = 17, more = 3, copy = 3, leng = 4, fill = 'ÿ', code = 1111 main.c:742: _list[ 1]: from = 18, more = 7, copy = 11, leng = 2, fill = 'ÿ', code = 10 i = 0010 j = 1, copy = 97 lit = 'ÿ' (0), sym = 'ÿ' (0) ... lit = '`' (96), sym = 'ÿ' (0) main.c:742: _list[ 2]: from = 1, more = 0, copy = 0, leng = 4, fill = 'ÿ', code = 1100 lit = 'a' (97), sym = 'a' (97) main.c:742: _list[ 0]: from = 2, more = 0, copy = 0, leng = 1, fill = 'ÿ', code = 0 lit = 'b' (98), sym = 'b' (98) main.c:742: _list[ 1]: from = 18, more = 7, copy = 11, leng = 2, fill = 'ÿ', code = 10 i = 0010 j = 1, copy = 138 lit = 'c' (99), sym = 'ÿ' (0) ... lit = 'ì' (236), sym = 'ÿ' (0) main.c:742: _list[ 1]: from = 18, more = 7, copy = 11, leng = 2, fill = 'ÿ', code = 10 i = 0010 j = 1, copy = 19 lit = 'í' (237), sym = 'ÿ' (0) ... lit = 'ÿ' (255), sym = 'ÿ' (0) main.c:742: _list[ 3]: from = 4, more = 0, copy = 0, leng = 4, fill = 'ÿ', code = 1101 lit = ' ' (256), sym = ' ' (256) main.c:742: _list[ 4]: from = 16, more = 2, copy = 3, leng = 4, fill = 'ÿ', code = 1110 i = 1110 j = 4, copy = 3 lit = '' (257), sym = '' (257) lit = '' (258), sym = '' (257) lit = '' (259), sym = '' (257) main.c:742: _list[ 0]: from = 2, more = 0, copy = 0, leng = 1, fill = 'ÿ', code = 0 lit = '' (260), sym = '' (260) main.c:742: _list[ 5]: from = 17, more = 3, copy = 3, leng = 4, fill = 'ÿ', code = 1111 i = 1111 j = 5, copy = 3 lit = '' (261), sym = 'ÿ' (0) lit = '' (262), sym = 'ÿ' (0) lit = '' (263), sym = 'ÿ' (0) main.c:742: _list[ 0]: from = 2, more = 0, copy = 0, leng = 1, fill = 'ÿ', code = 0 lit = '' (264), sym = '' (264) main.c:742: _list[ 0]: from = 2, more = 0, copy = 0, leng = 1, fill = 'ÿ', code = 0 lit = ' ' (265), sym = ' ' (265) main.c:742: _list[ 0]: from = 2, more = 0, copy = 0, leng = 1, fill = 'ÿ', code = 0 lit = ' ' (266), sym = ' ' (266) PrintBytes( 0x55af474034a0, 0, 16 )

Handler:

Code:

void * RdHuffmanLengDistCodes ( STREAM *stream, BUFF *CodeWords, BUFF *Symbols, uint count, uint max_leng, uint start_with_literal ) { uint prv = 0, lit = start_with_literal, pos = 0; CODEWORD *codewords = CodeWords->addr; HUFFMAN_SYMBOL *symbols, *symbol; symbols = Symbols->addr = calloc( count + 1, sizeof(HUFFMAN_SYMBOL) ); if ( !symbols ) return NULL; while ( pos < count && stream->num < stream->max ) { CODEWORD *word = NULL; uint i = 0, j = 0, cur_leng = 1, copy = 1; uintmax_t val; for ( cur_leng = 1; cur_leng <= max_leng; ++cur_leng ) { i = RevBits( CopyStreamBits( stream, cur_leng, false ), cur_leng ); for ( j = 0; j < list.used; ++j ) { word = codewords + j; if ( word->leng == cur_leng && word->code == i ) { IncStreamCount( stream, cur_leng ); break; } } if ( j < list.used ) break; } if ( cur_leng > max_leng ) { printf ( "i = %u, j = %u, list.used = %u, cur_leng = %u\n", i, j, CodeWords->used, cur_leng ); return NULL; } val = CopyStreamBits( stream, word->more, true ); PrintCodeWord( word, __LINE__, j ); if ( word->from >= 16 ) { copy = (uint)(word->copy + val); printf( "i = " ); SeeBits( &i, max_leng ); printf( " j = %u, copy = %u\n", j, copy ); } for ( uint s = 0; s < copy; ++s, ++pos, ++lit ) { uint sym = 0; if ( word->from == 16 ) sym = prv; else if ( word->from < 16 ) sym = lit; symbol = symbols + pos; symbol->len = word->leng; symbol->sym = sym; symbol->val = pos; printf ( "lit = '%c' (%u), sym = '%c' (%u)\n", lit ? lit : -1, lit, sym ? sym : -1, sym ); } prv = lit; } return symbols; }

How it's called:

Code:

puts("Code Table:\n"); for ( uint j = 0; j < list.used; ++j ) { CODEWORD *word = _list + j; PrintCodeWord( word, __LINE__, j ); } leng_symbols = RdHuffmanLengDistCodes ( &stream, &list, &tree, lengc, max_leng, 0 ); if ( !leng_symbols ) return Return( ret, 1 ); dist_symbols = RdHuffmanLengDistCodes ( &stream, &list, &distances, distc, max_leng, lengc ); if ( !dist_symbols ) return Return( ret, 1 ); }

If anyone WAS trying to help (which I currently doubt) I found the information I needed:

RFC 1951 DEFLATE Compressed Data Format Specification ver 1.3

Quote:

HDIST + 1 code lengths for the distance alphabet,

encoded using the code length Huffman code

That was way to easy to overlook, they need more colour coding... and a better naming scheme

Here's the decoding of the first part of the first 'dynamic dictionary' data block in the image in the original post (the first uses a fixed dictionary), in preparation for reading the actual full dictionary:

Code:

Last block = false Compressed (dynamic dictionary) HLIT 286, HDIST 20, HCLEN 18 0 3 4 2 0 0 0 3 0 2 0 4 0 5 0 4 0 5 Code length table ================= 0: 2 00 1: 5 11110 2: 4 1100 3: 5 11111 4: 4 1101 5: 2 01 6: 3 100 7: 0 8: 0 9: 0 10: 0 11: 0 12: 0 13: 0 14: 0 15: 0 16: 0 17: 3 101 18: 4 1110

2 Attachment(s)

I've got the hard parts of the "deflate" uncompressing written - now seems to inflate the original PNG data just fine (although I've still got to verify the ADLER32 checksum.

Once again, maybe it will help clear up ambiguities in the spec...

Re-reading the spec, now I understand it and I see I haven't honored that "all code lengths form a single sequence"

Ah well, better fix it up...

1 Attachment(s)

Quote:

Originally Posted by hamster_nz

Re-reading the spec, now I understand it and I see I haven't honored that "all code lengths form a single sequence"

Ah well, better fix it up...

Dunno if it's of value to you but this is where I've got with just the deflation of the huffman data, currently got a bug with UIDs, specifically with getting the right length for length/literal symbols. As soon as that's fixed the only thing left to do is implement the look back through deflated data part of the code.

Also since you're working on PNGs anyways this resource should be helpful (don't remember if I mentioned it in a previous post but here it is anyways):

PngSuite - the official set of PNG test images

I ran you code against a test file, and got this output:

Code:

main.c:281: symbols[ 0] (0x5560170045f0): src = 0, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 4, uid = 0010 main.c:281: symbols[ 4] (0x556017004690): src = 4, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 4, uid = 0011 main.c:281: symbols[ 5] (0x5560170046b8): src = 5, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 4, uid = 0100 main.c:281: symbols[ 6] (0x5560170046e0): src = 6, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 4, uid = 0101 main.c:281: symbols[ 7] (0x556017004708): src = 7, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 3, uid = 110 main.c:281: symbols[ 8] (0x556017004730): src = 8, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 2, uid = 10 main.c:281: symbols[ 9] (0x556017004758): src = 9, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 3, uid = 111 main.c:281: symbols[ 10] (0x556017004780): src = 10, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 4, uid = 0110 main.c:281: symbols[ 11] (0x5560170047a8): src = 11, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 3, uid = 000

The first shortest Hufman code should be always be all zeros.

So assuming your length table is correct, here's how they should be generated:

We start with "length 2" codes - "00" -

Assign to the length 2 codes, in order they appear in the table:

Code:

main.c:281: symbols[ 0] len = 4, main.c:281: symbols[ 4] len = 4, main.c:281: symbols[ 5] len = 4, main.c:281: symbols[ 6] len = 4, main.c:281: symbols[ 7] len = 3, main.c:281: symbols[ 8] len = 2, 00 main.c:281: symbols[ 9] len = 3, main.c:281: symbols[ 10] len = 4, main.c:281: symbols[ 11] len = 3,

At this point next symbol that would be assigned is "01". Add a '0' to it and do the threes:

Code:

main.c:281: symbols[ 0] main.c:281: symbols[ 4] main.c:281: symbols[ 5] main.c:281: symbols[ 6] main.c:281: symbols[ 7] 010 main.c:281: symbols[ 8] 00 main.c:281: symbols[ 9] 011 main.c:281: symbols[ 10] main.c:281: symbols[ 11] 100

At this point next symbol that would be assigned is "101". Add a '0' to it and do the fours:

Then do the same again (Lengths 4):

Code:

main.c:281: symbols[ 0] 1010 main.c:281: symbols[ 4] 1011 main.c:281: symbols[ 5] 1100 main.c:281: symbols[ 6] 1101 main.c:281: symbols[ 7] 010 main.c:281: symbols[ 8] 00 main.c:281: symbols[ 9] 011 main.c:281: symbols[ 10] 1110 main.c:281: symbols[ 11] 100

All done (but we seem to be one code short (1111)!

Here's my code for that, with error checking removed for clarity:

Code:

void codetable_generate(struct Codetable_entry *table, size_t len) { uint32_t next_code = 0; for(uint32_t pass_len = 1; pass_len < 16; pass_len++) { for(size_t i = 0; i < len; i++) { if(table[i].length == pass_len) { table[i].code = reverse(next_code,pass_len); next_code++; } } next_code <<= 1; } }

'reverse(x,y)' just flips the last 'y' bits around in 'x' - i.e. reverses the bit ordering in the lowest 'y' bits.

I *think* this is what you want in BuildCodes():

Code:

void BuildCodes( BUFF *Symbols, uint longest ) { uint uid = 0; HUFFMAN_SYMBOL *symbols = Symbols->addr; for ( uint len = 1; len <= longest; ++len ) { for ( uint i = 0; i < Symbols->used; ++i ) { if ( symbols[i].len == len ) symbols[i].uid = uid++; } uid <<= 1; } }

Seems to be better:

Code:

main.c:281: Hidden Symbols, used = 13 main.c:281: symbols[ 0] (0x55d7b4b7a5f0): src = 0, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 4, uid = 1010 main.c:281: symbols[ 4] (0x55d7b4b7a690): src = 4, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 4, uid = 1011 main.c:281: symbols[ 5] (0x55d7b4b7a6b8): src = 5, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 4, uid = 1100 main.c:281: symbols[ 6] (0x55d7b4b7a6e0): src = 6, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 4, uid = 1101 main.c:281: symbols[ 7] (0x55d7b4b7a708): src = 7, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 3, uid = 010 main.c:281: symbols[ 8] (0x55d7b4b7a730): src = 8, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 2, uid = 00 main.c:281: symbols[ 9] (0x55d7b4b7a758): src = 9, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 3, uid = 011 main.c:281: symbols[ 10] (0x55d7b4b7a780): src = 10, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 4, uid = 1110 main.c:281: symbols[ 11] (0x55d7b4b7a7a8): src = 11, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 3, uid = 100 main.c:285: Hidden Symbols, used = 13

Bit ordering might need to be reversed - I didn't look too far into it..

Quote:

Originally Posted by hamster_nz

I ran you code against a test file, and got this output:

Code:

main.c:281: symbols[ 0] (0x5560170045f0): src = 0, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 4, uid = 0010 main.c:281: symbols[ 4] (0x556017004690): src = 4, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 4, uid = 0011 main.c:281: symbols[ 5] (0x5560170046b8): src = 5, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 4, uid = 0100 main.c:281: symbols[ 6] (0x5560170046e0): src = 6, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 4, uid = 0101 main.c:281: symbols[ 7] (0x556017004708): src = 7, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 3, uid = 110 main.c:281: symbols[ 8] (0x556017004730): src = 8, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 2, uid = 10 main.c:281: symbols[ 9] (0x556017004758): src = 9, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 3, uid = 111 main.c:281: symbols[ 10] (0x556017004780): src = 10, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 4, uid = 0110 main.c:281: symbols[ 11] (0x5560170047a8): src = 11, use = true, sym = '' ( 0), lit = '' ( 0), get = 0, len = 3, uid = 000

The first shortest Hufman code should be always be all zeros.

So assuming your length table is correct, here's how they should be generated:

We start with "length 2" codes - "00" -

Assign to the length 2 codes, in order they appear in the table:

Code:

main.c:281: symbols[ 0] len = 4, main.c:281: symbols[ 4] len = 4, main.c:281: symbols[ 5] len = 4, main.c:281: symbols[ 6] len = 4, main.c:281: symbols[ 7] len = 3, main.c:281: symbols[ 8] len = 2, 00 main.c:281: symbols[ 9] len = 3, main.c:281: symbols[ 10] len = 4, main.c:281: symbols[ 11] len = 3,

At this point next symbol that would be assigned is "01". Add a '0' to it and do the threes:

Code:

main.c:281: symbols[ 0] main.c:281: symbols[ 4] main.c:281: symbols[ 5] main.c:281: symbols[ 6] main.c:281: symbols[ 7] 010 main.c:281: symbols[ 8] 00 main.c:281: symbols[ 9] 011 main.c:281: symbols[ 10] main.c:281: symbols[ 11] 100

At this point next symbol that would be assigned is "101". Add a '0' to it and do the fours:

Then do the same again (Lengths 4):

Code:

main.c:281: symbols[ 0] 1010 main.c:281: symbols[ 4] 1011 main.c:281: symbols[ 5] 1100 main.c:281: symbols[ 6] 1101 main.c:281: symbols[ 7] 010 main.c:281: symbols[ 8] 00 main.c:281: symbols[ 9] 011 main.c:281: symbols[ 10] 1110 main.c:281: symbols[ 11] 100

All done (but we seem to be one code short (1111)!

I did say there was a bug with UIDs, thank you for the code you provided after this though

Quote:

Originally Posted by hamster_nz

Here's my code for that, with error checking removed for clarity:

Code:

void codetable_generate(struct Codetable_entry *table, size_t len) { uint32_t next_code = 0; for(uint32_t pass_len = 1; pass_len < 16; pass_len++) { for(size_t i = 0; i < len; i++) { if(table[i].length == pass_len) { table[i].code = reverse(next_code,pass_len); next_code++; } } next_code <<= 1; } }

'reverse(x,y)' just flips the last 'y' bits around in 'x' - i.e. reverses the bit ordering in the lowest 'y' bits.

Colour me surprised that such a simple change would fix all of them (I had fixed the code & length UIDs but distance ones got mess up, this resolved that a lot better), thanks :)

1 Attachment(s)

Hit a crash with the final section of my code, since I need to do some shopping I figured I dump it here and see if I get lucky by the time I get back and someone both felt like looking through it and found the bug. If you do look I recommend just downloading the attached file, compile and search for the "Deflating data..." string, at least you'll have the syntax highlighting then.

A reminder of the document I was refering to when making this code:
Understanding gzip

The Code:

Code:

i = 0; j = 0; while ( stream.num < stream.max ) { leng_symbol = IdentifyNextSymbol( &stream, &Tree, leng_longest, true ); if ( !leng_symbol ) { PrintStreamDetails( &stream ); return Return( ret, EINVAL ); } //puts("Found:\n"); PrintSymbol( leng_symbol, __LINE__, leng_symbol->uid ); if ( leng_symbol->sym < 256 ) { j = i++; lazy[j] = leng_symbol->sym; } else { uint lookup, stop; dist_symbol = IdentifyNextSymbol( &stream, &Dist, dist_longest, true ); if ( !dist_symbol ) { PrintStreamDetails( &stream ); return Return( ret, EINVAL ); } lookup = CopyStreamBits( &stream, dist_symbol->get, true ); lookup += hufd_extra_bits_array[dist_symbol->src]; lookup = j - lookup; for ( j = 0; j < dist_symbol->len; ++j ) lazy[i++] = lazy[lookup++]; j = i - 1; PrintSymbol( dist_symbol, __LINE__, dist_symbol->uid ); } }

The Output:

Code:

./a.out aba.gz path = 'aba.gz' PrintStreamDetails( 0x7fffcc29b530 ): ptr = 0x56257145d480, pos = 0, num = 0, max = 328, fed = 0, got = PrintBytes( 0x56257145d480, 41, 16 ) 1F 8B 8 0 0 0 0 0 0 3 1D C6 49 1 0 0 40 C0 AC A3 7F 88 3D 3C 20 2A 97 9D 37 5E 1D C 29 34 94 23 0 0 0 PrintStreamDetails( 0x7fffcc29b530 ): ptr = 0x56257145d480, pos = 136, num = 80, max = 328, fed = 56, got = 00010000000000000000000000000001010010011100011000011101 gzip.magic = 1F8B, gzip.format = 8, gzip.flags = 0, gzip.mtime = 0, zlib.xflags = 0, zlib.system = 3 gzip.flag_TEXT = false, gzip.flag_HCRC = false, gzip.flag_MORE = false, gzip.flag_NAME = false, gzip.flag_NOTE = false, gzip.flag_RESERVED = 0 PrintStreamDetails( 0x7fffcc29b530 ): ptr = 0x56257145d480, pos = 136, num = 80, max = 296, fed = 56, got = 00010000000000000000000000000001010010011100011000011101 last = true, type = 2 lengc = 260, distc = 7, codec = 18, left = 60 pos = 212, max = 296, count = 267 left = 61, byte = 18, bit = 7 main.c:757: Code Symbols, used = 16 main.c:757: symbols[ 0] (0x5625714604d0): src = 2, use = true, sym = 'ÿ' ( 0), lit = 'ÿ' ( 0), get = 0, cpy = 0, len = 1, uid = 0 main.c:757: symbols[ 2] (0x562571460520): src = 18, use = true, sym = 'ÿ' ( 0), lit = 'ÿ' ( 0), get = 7, cpy = 11, len = 2, uid = 10 main.c:757: symbols[ 12] (0x5625714606b0): src = 1, use = true, sym = 'ÿ' ( 0), lit = 'ÿ' ( 0), get = 0, cpy = 0, len = 4, uid = 1100 main.c:757: symbols[ 13] (0x5625714606d8): src = 4, use = true, sym = 'ÿ' ( 0), lit = 'ÿ' ( 0), get = 0, cpy = 0, len = 4, uid = 1101 main.c:757: symbols[ 14] (0x562571460700): src = 16, use = true, sym = 'ÿ' ( 0), lit = 'ÿ' ( 0), get = 2, cpy = 3, len = 4, uid = 1110 main.c:757: symbols[ 15] (0x562571460728): src = 17, use = true, sym = 'ÿ' ( 0), lit = 'ÿ' ( 0), get = 3, cpy = 3, len = 4, uid = 1111 main.c:878: RdHuffmanLengDistCodes( 0x7fffcc29b530, 0x56256f60e420, 0x56256f60e440, 260, 0 ) main.c:771: Length Symbols, used = 16 main.c:771: symbols[ 0] (0x5625714607d0): src = 97, use = true, sym = 'a' ( 97), lit = 'a' ( 97), get = 0, cpy = 0, len = 1, uid = 0 main.c:771: symbols[ 2] (0x562571460820): src = 98, use = true, sym = 'b' ( 98), lit = 'b' ( 98), get = 0, cpy = 0, len = 2, uid = 10 main.c:771: symbols[ 12] (0x5625714609b0): src = 256, use = true, sym = 'ÿ' (256), lit = 'ÿ' (256), get = 0, cpy = 0, len = 4, uid = 1100 main.c:771: symbols[ 13] (0x5625714609d8): src = 257, use = true, sym = 'ÿ' (257), lit = 'ÿ' (257), get = 2, cpy = 0, len = 4, uid = 1101 main.c:771: symbols[ 14] (0x562571460a00): src = 258, use = true, sym = 'ÿ' (257), lit = 'ÿ' (258), get = 2, cpy = 0, len = 4, uid = 1110 main.c:771: symbols[ 15] (0x562571460a28): src = 259, use = true, sym = 'ÿ' (257), lit = 'ÿ' (259), get = 2, cpy = 0, len = 4, uid = 1111 main.c:878: RdHuffmanLengDistCodes( 0x7fffcc29b530, 0x56256f60e420, 0x56256f60e460, 7, 260 ) main.c:785: Distance Symbols, used = 4 main.c:785: symbols[ 0] (0x562571460a60): src = 0, use = true, sym = 'ÿ' (260), lit = 'ÿ' (260), get = 0, cpy = 0, len = 2, uid = 00 main.c:785: symbols[ 1] (0x562571460a88): src = 4, use = true, sym = 'ÿ' (264), lit = 'ÿ' (264), get = 0, cpy = 0, len = 2, uid = 01 main.c:785: symbols[ 2] (0x562571460ab0): src = 5, use = true, sym = 'ÿ' (265), lit = 'ÿ' (265), get = 0, cpy = 0, len = 2, uid = 10 main.c:785: symbols[ 3] (0x562571460ad8): src = 6, use = true, sym = 'ÿ' (266), lit = 'ÿ' (266), get = 0, cpy = 0, len = 2, uid = 11 main.c:806: main() Deflating data... main.c:820: symbols[ 0] (0x5625714607d0): src = 97, use = true, sym = 'a' ( 97), lit = 'a' ( 97), get = 0, cpy = 0, len = 1, uid = 0 main.c:820: symbols[ 2] (0x562571460820): src = 98, use = true, sym = 'b' ( 98), lit = 'b' ( 98), get = 0, cpy = 0, len = 2, uid = 10 main.c:820: symbols[ 0] (0x5625714607d0): src = 97, use = true, sym = 'a' ( 97), lit = 'a' ( 97), get = 0, cpy = 0, len = 1, uid = 0 main.c:820: symbols[ 0] (0x5625714607d0): src = 97, use = true, sym = 'a' ( 97), lit = 'a' ( 97), get = 0, cpy = 0, len = 1, uid = 0 double free or corruption (out) main.c:820: symbols[ 2] (0x562571460820): src = 98, use = true, sym = 'b' ( 98), lit = 'b' ( 98), get = 0, cpy = 0, len = 2, uid = 10 main.c:820: symbols[ 2] (0x562571460820): src = 98, use = true, sym = 'b' ( 98), lit = 'b' ( 98), get = 0, cpy = 0, len = 2, uid = 10 main.c:820: symbols[ 2] (0x562571460820): src = 98, use = true, sym = 'b' ( 98), lit = 'b' ( 98), get = 0, cpy = 0, len = 2, uid = 10 main.c:820: symbols[ 0] (0x5625714607d0): src = 97, use = true, sym = 'a' ( 97), lit = 'a' ( 97), get = 0, cpy = 0, len = 1, uid = 0 main.c:820: symbols[ 14] (0x562571460a00): src = 258, use = true, sym = 'ÿ' (257), lit = 'ÿ' (258), get = 2, cpy = 0, len = 4, uid = 1110 main.c:847: symbols[ 1] (0x562571460a88): src = 4, use = true, sym = 'ÿ' (264), lit = 'ÿ' (264), get = 0, cpy = 0, len = 2, uid = 01 main.c:820: symbols[ 0] (0x5625714607d0): src = 97, use = true, sym = 'a' ( 97), lit = 'a' ( 97), get = 0, cpy = 0, len = 1, uid = 0 main.c:820: symbols[ 0] (0x5625714607d0): src = 97, use = true, sym = 'a' ( 97), lit = 'a' ( 97), get = 0, cpy = 0, len = 1, uid = 0 main.c:820: symbols[ 13] (0x5625714609d8): src = 257, use = true, sym = 'ÿ' (257), lit = 'ÿ' (257), get = 2, cpy = 0, len = 4, uid = 1101 main.c:847: symbols[ 1] (0x562571460a88): src = 4, use = true, sym = 'ÿ' (264), lit = 'ÿ' (264), get = 0, cpy = 0, len = 2, uid = 01 main.c:820: symbols[ 2] (0x562571460820): src = 98, use = true, sym = 'b' ( 98), lit = 'b' ( 98), get = 0, cpy = 0, len = 2, uid = 10 main.c:820: symbols[ 0] (0x5625714607d0): src = 97, use = true, sym = 'a' ( 97), lit = 'a' ( 97), get = 0, cpy = 0, len = 1, uid = 0 main.c:820: symbols[ 15] (0x562571460a28): src = 259, use = true, sym = 'ÿ' (257), lit = 'ÿ' (259), get = 2, cpy = 0, len = 4, uid = 1111 main.c:847: symbols[ 0] (0x562571460a60): src = 0, use = true, sym = 'ÿ' (260), lit = 'ÿ' (260), get = 0, cpy = 0, len = 2, uid = 00 main.c:820: symbols[ 12] (0x5625714609b0): src = 256, use = true, sym = 'ÿ' (256), lit = 'ÿ' (256), get = 0, cpy = 0, len = 4, uid = 1100 main.c:847: symbols[ 0] (0x562571460a60): src = 0, use = true, sym = 'ÿ' (260), lit = 'ÿ' (260), get = 0, cpy = 0, len = 2, uid = 00 main.c:820: symbols[ 15] (0x562571460a28): src = 259, use = true, sym = 'ÿ' (257), lit = 'ÿ' (259), get = 2, cpy = 0, len = 4, uid = 1111 main.c:847: symbols[ 0] (0x562571460a60): src = 0, use = true, sym = 'ÿ' (260), lit = 'ÿ' (260), get = 0, cpy = 0, len = 2, uid = 00 main.c:820: symbols[ 2] (0x562571460820): src = 98, use = true, sym = 'b' ( 98), lit = 'b' ( 98), get = 0, cpy = 0, len = 2, uid = 10 main.c:820: symbols[ 2] (0x562571460820): src = 98, use = true, sym = 'b' ( 98), lit = 'b' ( 98), get = 0, cpy = 0, len = 2, uid = 10 main.c:820: symbols[ 14] (0x562571460a00): src = 258, use = true, sym = 'ÿ' (257), lit = 'ÿ' (258), get = 2, cpy = 0, len = 4, uid = 1110 main.c:847: symbols[ 0] (0x562571460a60): src = 0, use = true, sym = 'ÿ' (260), lit = 'ÿ' (260), get = 0, cpy = 0, len = 2, uid = 00 main.c:820: symbols[ 0] (0x5625714607d0): src = 97, use = true, sym = 'a' ( 97), lit = 'a' ( 97), get = 0, cpy = 0, len = 1, uid = 0 main.c:820: symbols[ 0] (0x5625714607d0): src = 97, use = true, sym = 'a' ( 97), lit = 'a' ( 97), get = 0, cpy = 0, len = 1, uid = 0 main.c:820: symbols[ 0] (0x5625714607d0): src = 97, use = true, sym = 'a' ( 97), lit = 'a' ( 97), get = 0, cpy = 0, len = 1, uid = 0 main.c:820: symbols[ 12] (0x5625714609b0): src = 256, use = true, sym = 'ÿ' (256), lit = 'ÿ' (256), get = 0, cpy = 0, len = 4, uid = 1100 main.c:847: symbols[ 0] (0x562571460a60): src = 0, use = true, sym = 'ÿ' (260), lit = 'ÿ' (260), get = 0, cpy = 0, len = 2, uid = 00 main.c:820: symbols[ 0] (0x5625714607d0): src = 97, use = true, sym = 'a' ( 97), lit = 'a' ( 97), get = 0, cpy = 0, len = 1, uid = 0 main.c:820: symbols[ 0] (0x5625714607d0): src = 97, use = true, sym = 'a' ( 97), lit = 'a' ( 97), get = 0, cpy = 0, len = 1, uid = 0 main.c:820: symbols[ 14] (0x562571460a00): src = 258, use = true, sym = 'ÿ' (257), lit = 'ÿ' (258), get = 2, cpy = 0, len = 4, uid = 1110 main.c:847: symbols[ 1] (0x56257 make: *** [GNUmakefile:2: run] Aborted (core dumped) Compilation failed.

Judging by the lack of replies I take it no one felt like it, no biggie, eventually "fixed" it, I say fixed because I got passed the section only to encounter a crash during the attempt to free memory on the way out, here's my current code (with mini makefile and the test archives)

deflate.zip - Google Drive

I just tested it with a gz file I made with "echo test | gzip > a.gz" and it crashed out.

Cause was around line 680 - with a buffer overflow.

Code:

lengi = RevBits( CopyStreamBits( &stream, 7, true ), 7 ) - 1; bits = leng_extra_bits_array[lengi];

lengi is unsigned, so if CopyStreamBits returns 0, then lengi gets set to 4294967295, and of course leng_extra_bits_array[4294967295] is a crash.

Quote:

Originally Posted by hamster_nz

I just tested it with a gz file I made with "echo test | gzip > a.gz" and it crashed out.

Cause was around line 680 - with a buffer overflow.

Code:

lengi = RevBits( CopyStreamBits( &stream, 7, true ), 7 ) - 1; bits = leng_extra_bits_array[lengi];

lengi is unsigned, so if CopyStreamBits returns 0, then lengi gets set to 4294967295, and of course leng_extra_bits_array[4294967295] is a crash.

Strange, that should only be reached under a type 1 scenario, the one used for the "hello hello hello hello" test (hello.gz in the zip I provided), well either way I should probably add a check that it's in bounds anyways

Edit:
For now, to get the output, add this after the assignment:

Code:

if ( lengi >= 32 ) return Return( ret, err );

Edit 2: btw I'm going to bed in case anyone responds after I've shut the computer down (need to reset after an update anyways)

Oh, thanks for that link to the test images... It is proving invaluable.

One thing I find really fascinating about zlib compression is that nowhere in the file can you point to a set of bits and say "those bits encode that letter" - so if the compressed file contains a capital A there never is 8 bits that represent the capital A symbol.

It's all indirectly implied.

Quote:

engi is unsigned, so if CopyStreamBits returns 0, then lengi gets set to 4294967295, and of course leng_extra_bits_array[4294967295] is a crash.

What are you talking about? 0 fits in an unsigned int.

Code:

#include <stdio.h> int f() { return 0; } int main() { unsigned int lengi = f(); printf("lengi: %u", lengi); }

Output:
lengi: 0

Quote:

Originally Posted by thmm

What are you talking about? 0 fits in an unsigned int.

Code:

#include <stdio.h> int f() { return 0; } int main() { unsigned int lengi = f(); printf("lengi: %u", lengi); }

Output:
lengi: 0

You did look at the code included in the post, where one is subtracted from the value returned before it is assigned?

No I didn't. I just saw the comment.

Yeah, I prefer a different compression I thought up that uses some similar concepts but is a LOT easier to deal with, basically the 1st 64 bits should read ".HUFFMAN" to make it clear that it's huffman type compression, the nibble that follows should have 1 added and be multiplied against 4 to get the size of each element, the next 12 bit are reserved for flags I haven't decided yet, the next bits (size decided by aforementioned (nibble + 1) * 4) are for the expected number of elements in the resulting data, I think I'll probably just make it a flag holder, next follows a list of indices (their size is as previously explained with the (nibble + 1) * 4) with a prefix bit that says to whether or not to use everything from the index itself to what comes before the next index provided so the shortest list could be 1 0000 1 1111, those 2 are the only required indices, these indices have a 1:1 relationship with the values to add into the buffer later, the huffman codes are to be generated in the same order, until the last index is reached, whatever your final next code is is gonna be the code of the last index anyways, it will be considered uncompressed data if more than a qtr of the available indices are used before getting the huffman codes in which case every value from here on until will be for the buffer or in the case of compressed data huffman tree to pull the value to put into the buffer, the will be only one prefix bit to these values, that tells you to either use it as uncompressed data/huffman code or to read 2 counts (again size is determine by (nibble + 1) * 4) to 1. minus from current value count and 2. begin copying existing values upto the 2nd count read

So "hello hello hello hello" could result in something like this (I've given interpretations, not bit representations in most cases):
".HUFFMAN" 10 00 24 [1 '\0', 0 1, 1 ' ', 0 33, 1 'e', 0 'f', 1 'h', 0 'i', 1 'l', 0 'm', 1 'o', 0 'p', 0 255] 0 'h' 0 'e' 0 'l' 0 'l' 0 'o' 0 ' ' 1 6 17 0 '\0'

I still need to do a bit more thinking on it but I like it better than zlib, it's a lot clearer what is what after all

Quote:

Originally Posted by awsdert

Yeah, I prefer a different compression I thought up that uses some similar concepts but is a LOT easier to deal with, basically the 1st 64 bits should read ".HUFFMAN" to make it clear that it's huffman type compression, the nibble that follows should have 1 added and be multiplied against 4 to get the size of each element, the next 12 bit are reserved for flags I haven't decided yet, the next bits (size decided by aforementioned (nibble + 1) * 4) are for the expected number of elements in the resulting data, I think I'll probably just make it a flag holder, next follows a list of indices (their size is as previously explained with the (nibble + 1) * 4) with a prefix bit that says to whether or not to use everything from the index itself to what comes before the next index provided so the shortest list could be 1 0000 1 1111, those 2 are the only required indices, these indices have a 1:1 relationship with the values to add into the buffer later, the huffman codes are to be generated in the same order, until the last index is reached, whatever your final next code is is gonna be the code of the last index anyways, it will be considered uncompressed data if more than a qtr of the available indices are used before getting the huffman codes in which case every value from here on until will be for the buffer or in the case of compressed data huffman tree to pull the value to put into the buffer, the will be only one prefix bit to these values, that tells you to either use it as uncompressed data/huffman code or to read 2 counts (again size is determine by (nibble + 1) * 4) to 1. minus from current value count and 2. begin copying existing values upto the 2nd count read

So "hello hello hello hello" could result in something like this (I've given interpretations, not bit representations in most cases):
".HUFFMAN" 10 00 24 [1 '\0', 0 1, 1 ' ', 0 33, 1 'e', 0 'f', 1 'h', 0 'i', 1 'l', 0 'm', 1 'o', 0 'p', 0 255] 0 'h' 0 'e' 0 'l' 0 'l' 0 'o' 0 ' ' 1 6 17 0 '\0'

I still need to do a bit more thinking on it but I like it better than zlib, it's a lot clearer what is what after all

I feel there has been a lot of research put into zlib's scheme that shouldn't be discounted so quickly. For example, the way the code tables are bootstrapped is pretty neat and effective.

Or for another perspective, it's always good to implement following an existing standard, as it means you don't have to write the documentation :wink:

Why'd you think I copied some of the concepts? For example the look back feature, or the huffman code usage, there are places for storing the huffman codes sure, and that's part of the reason I left room for flags but in cases like this it is better not to store them at all, for the example of "hello hello hello hello" it is is also possible with my algorithm to go so small that it's almost just the string itself, for example:

".HUFFMAN" 10 01 24 0 'h' 0 'e' 0 'l' 0 'l' 0 'o' 0 ' ' 1 6 17 0 '\0'

64 + 4 + 12 + 8 + (8 * 1) + (7 * 8) + (2 * 8) results in 168 bits or 21 bytes, literally smaller than the source string which is something not even the zlib compression can do, there's even room for me to add another 3 bytes for extra flags if I deem necessary, and thinking about it I just decided on a method for psuedo infinite flags, just use a flag in that 1st nibble to say more flags expected, if I move the psuedo NO_LIST flag I cooked up in the example I just provided to the first nibble of flags then I can further reduce the size to 20 bytes, then if I introduce a pseudo NO_SIZE flag to that 1st nibble also then I can further reduce the bytes to 19 bytes, whereas gzip needed a whole 29 bytes which is contrary the purpose of compression

Edit: For streams that can't get an EOF error a lookup at the end can be introduced that is a simple 1 0000 0000, which basically says "because we are copying 0 values stop reading the stream here".

Edit 2: As another space saving if ".HUF" is available as a "magic number" then I can further reduce that 19 to 15 bytes, nearly half the original 24 bytes

1 Attachment(s)

Fixed the crash, now my problem is missing data, this is what I get versus what I should get:

Code:

abaabbbaba babaaaaba bbbaa abaabbbabaababbaababaaaabaaabbbbbaa

zlib encoding for "hello hello hello hello" would be

3 bits - list block, uses default codeblook.
8 bits - h
8 bits - e
8 bits - l
8 bits - l
8 bits - o
8 bits - space
8 bits - Symbol 268 - repeat of length 17, including the extra bit
6 bits - distance code 4, distance of 6 bytes, including one extra bit
7 bits - End of block code

That makes 72 bits (9 bytes). to encode 184 bits (23 bytes).

Whatever metadata you want to wrap around it is pretty much a moot point - if it is 10 or 15 bytes won't make a difference when you are encoding things longer than a tens of bytes.

1 Attachment(s)

PNG decoding progress going quite well - all the Basic images in PngSuite convert correctly to PPM.

Might look at interlacing tonight..

Quote:

Originally Posted by hamster_nz

zlib encoding for "hello hello hello hello" would be

3 bits - list block, uses default codeblook.
8 bits - h
8 bits - e
8 bits - l
8 bits - l
8 bits - o
8 bits - space
8 bits - Symbol 268 - repeat of length 17, including the extra bit
6 bits - distance code 4, distance of 6 bytes, including one extra bit
7 bits - End of block code

That makes 72 bits (9 bytes). to encode 184 bits (23 bytes).

Whatever metadata you want to wrap around it is pretty much a moot point - if it is 10 or 15 bytes won't make a difference when you are encoding things longer than a tens of bytes.

I was more thinking about the resulting file as a whole, sure there are cases where zlib is more appropriate, I was simply saying in this case picking zlib inside gzip results in wasted space whereas the encoding I thought up saves space as an archive (which is obviously the point of an archive, if I were to convert it to just an encoding gzip could make use of the scrapping the remain 4 bytes of the "magic number" it would bring the size down to 11 bytes, then if ( disinclude the null character as you did then it goes further to just barely under 11 bytes I think

4 + 4 + (7 * 1) + (6 * 8) + (2 * 8) = 4 + 4 + 7 + 48 + 16 = 79 / 8 = 9 r7 = 10 bytes

If I also introduce a further flag that tells of a multiplier for look back / copy bit lengths and reduce their default size to 4 bits also then I save another byte giving the same 9 bytes in a simpler form at 71 bits, if you restrain yourself by saying that further efficiency is impossible, you'll never find improvements.

Edit: BTW I did the math after stating barely under 11 bytes

1 Attachment(s)

Since you've managed to implement the deflate algorithm correctly (unless I've misunderstood you somewhere) I'll ask you, can you see where I'm going wrong here?

Output of length/distance construction:

Code:

main.c:782: Code Symbols, foresee = 18, longest = 4, have = 32, used = 16 main.c:782: symbols[ 0] (0x5598b41d14d0): src = 2, use = true, sym = 0, get = 0, cpy = 0, len = 1, name = '?', lit = 'ÿ' ( 0), uid = 0 main.c:782: symbols[ 2] (0x5598b41d1528): src = 18, use = true, sym = 0, get = 7, cpy = 11, len = 2, name = '?', lit = 'ÿ' ( 0), uid = 10 main.c:782: symbols[ 12] (0x5598b41d16e0): src = 1, use = true, sym = 0, get = 0, cpy = 0, len = 4, name = '?', lit = 'ÿ' ( 0), uid = 1100 main.c:782: symbols[ 13] (0x5598b41d170c): src = 4, use = true, sym = 0, get = 0, cpy = 0, len = 4, name = '?', lit = 'ÿ' ( 0), uid = 1101 main.c:782: symbols[ 14] (0x5598b41d1738): src = 16, use = true, sym = 0, get = 2, cpy = 3, len = 4, name = '?', lit = 'ÿ' ( 0), uid = 1110 main.c:782: symbols[ 15] (0x5598b41d1764): src = 17, use = true, sym = 0, get = 3, cpy = 3, len = 4, name = '?', lit = 'ÿ' ( 0), uid = 1111 main.c:909: RdHuffmanLengDistCodes( 0x7fff047ee6a0, 0x5598b397a4c0, 0x5598b397a500, 0 ) main.c:958: symbols[ 12] (0x5598b41d16e0): src = 1, use = true, sym = 0, get = 0, cpy = 0, len = 4, name = 'Code Symbol', lit = 'ÿ' ( 0), uid = 1100 main.c:970: symbols[ 97] (0x5598b41d2b0c): src = 97, use = true, sym = 0, get = 0, cpy = 1, len = 1, name = 'Leng Symbol', lit = 'a' ( 97), uid = 0 main.c:958: symbols[ 0] (0x5598b41d14d0): src = 2, use = true, sym = 0, get = 0, cpy = 0, len = 1, name = 'Code Symbol', lit = 'ÿ' ( 0), uid = 0 main.c:970: symbols[ 98] (0x5598b41d2b38): src = 98, use = true, sym = 0, get = 0, cpy = 2, len = 2, name = 'Leng Symbol', lit = 'b' ( 98), uid = 00 main.c:958: symbols[ 13] (0x5598b41d170c): src = 4, use = true, sym = 0, get = 0, cpy = 0, len = 4, name = 'Code Symbol', lit = 'ÿ' ( 0), uid = 1101 main.c:970: symbols[256] (0x5598b41d4660): src = 256, use = true, sym = 0, get = 0, cpy = 4, len = 4, name = 'Leng Symbol', lit = 'ÿ' (256), uid = 0000 main.c:958: symbols[ 14] (0x5598b41d1738): src = 16, use = true, sym = 0, get = 2, cpy = 3, len = 4, name = 'Code Symbol', lit = 'ÿ' ( 0), uid = 1110 main.c:970: symbols[257] (0x5598b41d468c): src = 257, use = true, sym = 3, get = 0, cpy = 0, len = 4, name = 'Leng Symbol', lit = 'ÿ' (257), uid = 0000 main.c:958: symbols[ 14] (0x5598b41d1738): src = 16, use = true, sym = 0, get = 2, cpy = 3, len = 4, name = 'Code Symbol', lit = 'ÿ' ( 0), uid = 1110 main.c:970: symbols[258] (0x5598b41d46b8): src = 258, use = true, sym = 4, get = 0, cpy = 0, len = 4, name = 'Leng Symbol', lit = 'ÿ' (258), uid = 0000 main.c:958: symbols[ 14] (0x5598b41d1738): src = 16, use = true, sym = 0, get = 2, cpy = 3, len = 4, name = 'Code Symbol', lit = 'ÿ' ( 0), uid = 1110 main.c:970: symbols[259] (0x5598b41d46e4): src = 259, use = true, sym = 5, get = 0, cpy = 0, len = 4, name = 'Leng Symbol', lit = 'ÿ' (259), uid = 0000 main.c:909: RdHuffmanLengDistCodes( 0x7fff047ee6a0, 0x5598b397a4c0, 0x5598b397a540, 260 ) main.c:958: symbols[ 0] (0x5598b41d14d0): src = 2, use = true, sym = 0, get = 0, cpy = 0, len = 1, name = 'Code Symbol', lit = 'ÿ' ( 0), uid = 0 main.c:963: symbols[ 0] (0x5598b41d4750): src = 0, use = true, sym = 0, get = 0, cpy = 0, len = 2, name = 'Dist Symbol', lit = 'ÿ' (260), uid = 00 main.c:958: symbols[ 0] (0x5598b41d14d0): src = 2, use = true, sym = 0, get = 0, cpy = 0, len = 1, name = 'Code Symbol', lit = 'ÿ' ( 0), uid = 0 main.c:963: symbols[ 4] (0x5598b41d4800): src = 4, use = true, sym = 0, get = 0, cpy = 0, len = 2, name = 'Dist Symbol', lit = 'ÿ' (264), uid = 00 main.c:958: symbols[ 0] (0x5598b41d14d0): src = 2, use = true, sym = 0, get = 0, cpy = 0, len = 1, name = 'Code Symbol', lit = 'ÿ' ( 0), uid = 0 main.c:963: symbols[ 5] (0x5598b41d482c): src = 5, use = true, sym = 0, get = 0, cpy = 0, len = 2, name = 'Dist Symbol', lit = 'ÿ' (265), uid = 00 main.c:958: symbols[ 0] (0x5598b41d14d0): src = 2, use = true, sym = 0, get = 0, cpy = 0, len = 1, name = 'Code Symbol', lit = 'ÿ' ( 0), uid = 0 main.c:963: symbols[ 6] (0x5598b41d4858): src = 6, use = true, sym = 0, get = 0, cpy = 0, len = 2, name = 'Dist Symbol', lit = 'ÿ' (266), uid = 00

Related code:

Code:

while ( pos < Symbols->foresee && stream->num < stream->max ) { uint i = 0, copy = 0; uintmax_t val; code = IdentifyNextSymbol( stream, Codes, true, false ); if ( !code ) { #if 0 Symbols->entries.used = pos; printf( PFX_FORMAT " pos = %u\n", PFX_VALUES, pos ); PrintSymbols( Codes, __LINE__, "Code Symbols" ); PrintSymbols( Symbols, __LINE__, name ); PrintStreamDetails( stream, __LINE__ ); #endif return EINVAL; } //PrintStreamDetails( stream ); val = CopyStreamBits( stream, code->get, true ); //PrintSymbol( code, __LINE__, j ); copy = (uint)(code->cpy + val); //if ( copy ) printf( "copy = %3u\n", copy ); i = 0; do { if ( pos >= Symbols->entries.have ) { printf( PFX_FORMAT " pos = %u\n", PFX_VALUES, pos ); PrintSymbols( Symbols, __LINE__, name ); return ERANGE; } symbol = symbols + pos; symbol->src = pos; symbol->lit = lit; if ( !copy || (!start_with_literal && lit >= 256) ) { symbol->use = true; PrintSymbol( code, __LINE__, code->uid, "Code Symbol" ); if ( start_with_literal ) { symbol->len = code->len + 1; symbol->get = code->get; PrintSymbol( symbol, __LINE__, pos, "Dist Symbol" ); } else { symbol->sym = (lit > 256) ? used : 0; symbol->len += (lit < 256) ? code->src : 4; symbol->cpy = (code->src < 16) ? code->src : 0; PrintSymbol( symbol, __LINE__, pos, "Leng Symbol" ); } if ( symbol->len > Symbols->longest ) Symbols->longest = symbol->len; ++used; } ++lit; ++pos; ++i; } while ( i < copy ); }

Defaltation Output:

Code:

main.c:812: main() Deflating data... main.c:826: symbols[ 0] (0x5598b41d1a60): src = 97, use = true, sym = 0, get = 0, cpy = 1, len = 1, name = 'leng_symbol', lit = 'a' ( 97), uid = 0 main.c:826: symbols[ 2] (0x5598b41d1ab8): src = 98, use = true, sym = 0, get = 0, cpy = 2, len = 2, name = 'leng_symbol', lit = 'b' ( 98), uid = 10 main.c:826: symbols[ 0] (0x5598b41d1a60): src = 97, use = true, sym = 0, get = 0, cpy = 1, len = 1, name = 'leng_symbol', lit = 'a' ( 97), uid = 0 main.c:826: symbols[ 0] (0x5598b41d1a60): src = 97, use = true, sym = 0, get = 0, cpy = 1, len = 1, name = 'leng_symbol', lit = 'a' ( 97), uid = 0 main.c:826: symbols[ 2] (0x5598b41d1ab8): src = 98, use = true, sym = 0, get = 0, cpy = 2, len = 2, name = 'leng_symbol', lit = 'b' ( 98), uid = 10 main.c:826: symbols[ 2] (0x5598b41d1ab8): src = 98, use = true, sym = 0, get = 0, cpy = 2, len = 2, name = 'leng_symbol', lit = 'b' ( 98), uid = 10 main.c:826: symbols[ 2] (0x5598b41d1ab8): src = 98, use = true, sym = 0, get = 0, cpy = 2, len = 2, name = 'leng_symbol', lit = 'b' ( 98), uid = 10 main.c:826: symbols[ 0] (0x5598b41d1a60): src = 97, use = true, sym = 0, get = 0, cpy = 1, len = 1, name = 'leng_symbol', lit = 'a' ( 97), uid = 0 main.c:826: symbols[ 14] (0x5598b41d1cc8): src = 258, use = true, sym = 4, get = 0, cpy = 0, len = 4, name = 'leng_symbol', lit = 'ÿ' (258), uid = 1110 main.c:856: symbols[ 2] (0x5598b41d47a8): src = 5, use = true, sym = 0, get = 0, cpy = 0, len = 2, name = 'dist_symbol', lit = 'ÿ' (265), uid = 10 main.c:861: lookup = 4 main.c:826: symbols[ 13] (0x5598b41d1c9c): src = 257, use = true, sym = 3, get = 0, cpy = 0, len = 4, name = 'leng_symbol', lit = 'ÿ' (257), uid = 1101 main.c:856: symbols[ 3] (0x5598b41d47d4): src = 6, use = true, sym = 0, get = 0, cpy = 0, len = 2, name = 'dist_symbol', lit = 'ÿ' (266), uid = 11 main.c:861: lookup = 3 main.c:826: symbols[ 15] (0x5598b41d1cf4): src = 259, use = true, sym = 5, get = 0, cpy = 0, len = 4, name = 'leng_symbol', lit = 'ÿ' (259), uid = 1111 main.c:856: symbols[ 1] (0x5598b41d477c): src = 4, use = true, sym = 0, get = 0, cpy = 0, len = 2, name = 'dist_symbol', lit = 'ÿ' (264), uid = 01 main.c:861: lookup = 6 main.c:826: symbols[ 0] (0x5598b41d1a60): src = 97, use = true, sym = 0, get = 0, cpy = 1, len = 1, name = 'leng_symbol', lit = 'a' ( 97), uid = 0 main.c:826: symbols[ 0] (0x5598b41d1a60): src = 97, use = true, sym = 0, get = 0, cpy = 1, len = 1, name = 'leng_symbol', lit = 'a' ( 97), uid = 0 main.c:826: symbols[ 0] (0x5598b41d1a60): src = 97, use = true, sym = 0, get = 0, cpy = 1, len = 1, name = 'leng_symbol', lit = 'a' ( 97), uid = 0 main.c:826: symbols[ 15] (0x5598b41d1cf4): src = 259, use = true, sym = 5, get = 0, cpy = 0, len = 4, name = 'leng_symbol', lit = 'ÿ' (259), uid = 1111 main.c:856: symbols[ 1] (0x5598b41d477c): src = 4, use = true, sym = 0, get = 0, cpy = 0, len = 2, name = 'dist_symbol', lit = 'ÿ' (264), uid = 01 main.c:861: lookup = 5 main.c:826: symbols[ 2] (0x5598b41d1ab8): src = 98, use = true, sym = 0, get = 0, cpy = 2, len = 2, name = 'leng_symbol', lit = 'b' ( 98), uid = 10 main.c:826: symbols[ 14] (0x5598b41d1cc8): src = 258, use = true, sym = 4, get = 0, cpy = 0, len = 4, name = 'leng_symbol', lit = 'ÿ' (258), uid = 1110 main.c:856: symbols[ 0] (0x5598b41d4750): src = 0, use = true, sym = 0, get = 0, cpy = 0, len = 2, name = 'dist_symbol', lit = 'ÿ' (260), uid = 00 main.c:861: lookup = 4 main.c:826: symbols[ 0] (0x5598b41d1a60): src = 97, use = true, sym = 0, get = 0, cpy = 1, len = 1, name = 'leng_symbol', lit = 'a' ( 97), uid = 0 main.c:826: symbols[ 0] (0x5598b41d1a60): src = 97, use = true, sym = 0, get = 0, cpy = 1, len = 1, name = 'leng_symbol', lit = 'a' ( 97), uid = 0 main.c:826: symbols[ 12] (0x5598b41d1c70): src = 256, use = true, sym = 0, get = 0, cpy = 4, len = 4, name = 'leng_symbol', lit = 'ÿ' (256), uid = 1100 PrintBytes( 0x5598b41d14a0, 0, 16 ) abaabbbaaaabaa

Related Code:

Code:

else if ( type == 2 ) { uint count = 0; uint i = 0, j = 0; HUFFMAN_SYMBOL *codes, *code, *leng_symbol, *dist_symbol; int err; LengSymbols.foresee = CopyStreamBits( &stream, 5, true ) + 257; DistSymbols.foresee = CopyStreamBits( &stream, 5, true ) + 1; CodeSymbols.foresee = CopyStreamBits( &stream, 4, true ) + 4; PrintSymbols( &DistSymbols, __LINE__, "Distance Symbols" ); PrintSymbols( &LengSymbols, __LINE__, "Length Symbols" ); PrintSymbols( &CodeSymbols, __LINE__, "Code Symbols" ); PrintStreamDetails( &stream, __LINE__ ); i = CodeSymbols.foresee; codes = ReAllocSymbols( &CodeSymbols, i < 32 ? 32 : i + 1 ); if ( !codes ) return Return( ret, ENOMEM ); for ( i = 0; i < CodeSymbols.foresee; ++i ) { static uint adjust[] = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15, 19 }; code = codes + adjust[i]; code->src = adjust[i]; code->get = hufd_extra_bits_array[code->src]; code->cpy = hufd_repeat_bits_array[code->src]; code->len = CopyStreamBits( &stream, 3, true ); code->use = !!(code->len); if ( code->len > CodeSymbols.longest ) CodeSymbols.longest = code->len; } CodeSymbols.entries.used = i + 1; count = LengSymbols.foresee + DistSymbols.foresee; printf( "pos = %u, max = %u, count = %u\n", stream.pos, stream.max, count ); size = stream.num; printf( "left = %u, byte = %zu, bit = %zu\n", stream.fed , size / CHAR_BIT, size % CHAR_BIT ); BuildCodes( &CodeSymbols ); SortSymbolsByUID( &CodeSymbols ); PrintSymbols( &CodeSymbols, __LINE__, "Code Symbols" ); err = RdHuffmanLengDistCodes ( &stream, &CodeSymbols, &LengSymbols, 0, "Length Symbols" ); if ( err ) return Return( ret, err ); //PrintSymbols( &LengSymbols, __LINE__, "Length Symbols" ); err = RdHuffmanLengDistCodes ( &stream, &CodeSymbols, &DistSymbols, LengSymbols.foresee, "Distance Symbols" ); if ( err ) return Return( ret, err ); //PrintSymbols( &DistSymbols, __LINE__, "Distance Symbols" ); printf("%s:%u: %s() Deflating data...\n", __FILE__, __LINE__, __func__ ); i = 0; j = 0; while ( stream.num < stream.max ) { leng_symbol = IdentifyNextSymbol( &stream, &LengSymbols, true, false ); if ( !leng_symbol ) { PrintStreamDetails( &stream, __LINE__ ); return Return( ret, EINVAL ); } //puts("Found:\n"); PrintSymbol( leng_symbol, __LINE__, leng_symbol->uid, "leng_symbol" ); if ( leng_symbol->lit == 256 ) break; else if ( leng_symbol->lit < 256 ) { if ( i == Lazy.size ) { printf("%s:%u: Hit buffer limit!\n", __FILE__, __LINE__ ); return Return( ret , ERANGE ); } j = i++; lazy[j] = leng_symbol->lit; } else { uint dref; uint lookup; static uint extends[8] = { 0, 0, 0, 0, 1, 1, 2, 0 }; dist_symbol = IdentifyNextSymbol( &stream, &DistSymbols, true, false ); if ( !dist_symbol ) { PrintStreamDetails( &stream, __LINE__ ); return Return( ret, EINVAL ); } dref = dist_symbol->src; PrintSymbol( dist_symbol, __LINE__, dist_symbol->uid, "dist_symbol" ); lookup = leng_symbol->sym; lookup += CopyStreamBits( &stream, extends[dref], true ); printf( "%s:%u: lookup = %3u\n", __FILE__, __LINE__, lookup ); lookup = i - lookup; for ( j = 0; j < leng_symbol->cpy; ++j ) { if ( i == Lazy.size ) { printf("%s:%u: Hit buffer limit!\n", __FILE__, __LINE__ ); return Return( ret , ERANGE ); } lazy[i++] = lazy[lookup++]; } j = i - 1; //PrintSymbol( dist_symbol, __LINE__, dist_symbol->uid ); } } }

There's only 1 instance of "else if ( type == 2 )" in the attached file so if you want to get more information you can just search for that to get your starting point.

The second table will never work - there are two entries of length 1, so that uses both codes '0' & '1', leaving no other possible codes for longer length codes.

A few posts ago supplied an edited bit of your code that assigned code symbols correctly, as well as a walk through of the assignment algorithm.

It would pay to revisit that, after working out why your table has too many entries with short lengths.

If you can post a ASCII hex dump of *just* the zlib data I will turn up the debug level on my code and print out the code tables.

3 Attachment(s)

I got a few spare minutes.

Attached is a program that should decode a .gz file less than 8kb, and if you add "-v" on the command line it will print out things like code tables/dictionaries along the way.

Code:

$ echo "Hi there" | gzip > a.gz $ ./main2 a.gz Have loaded 29 bytes from file Last block = true Compressed (default dictionary) data: 48 'H' data: 69 'i' data: 20 ' ' data: 74 't' data: 68 'h' data: 65 'e' data: 72 'r' data: 65 'e' data: 0a End of block 256 This is the last block

It assumes that the zlib data start at byte 10.

Don't judge the code too harshly - it's just a hack to test my understanding, not production ready.

So here I'm gziping up the source file "inflate.c", then decoding it with 'verbose' enabled:

Code:

$ cat inflate.c | gzip > abc.gz $ ./main2 -v abc.gz | more

And here is the output showing the code tables that were used:

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 ......

Quote:

Originally Posted by hamster_nz

The second table will never work - there are two entries of length 1, so that uses both codes '0' & '1', leaving no other possible codes for longer length codes.

A few posts ago supplied an edited bit of your code that assigned code symbols correctly, as well as a walk through of the assignment algorithm.

It would pay to revisit that, after working out why your table has too many entries with short lengths.

I've just double checked the data (no modifications from what I posted) and there's no duplicate lengths, are you sure you're not confusing symbols from 2 different tables? I added the names to make clear which table/tree they're from.

Quote:

Originally Posted by hamster_nz

If you can post a ASCII hex dump of *just* the zlib data I will turn up the debug level on my code and print out the code tables.

Did you mean this?

Code:

main.c:782: Code Symbols, foresee = 18, longest = 4, have = 32, used = 16 main.c:782: symbols[ 0] (0x5598b41d14d0): src = 2, use = true, sym = 0, get = 0, cpy = 0, len = 1, name = '?', lit = 'ÿ' ( 0), uid = 0 main.c:782: symbols[ 2] (0x5598b41d1528): src = 18, use = true, sym = 0, get = 7, cpy = 11, len = 2, name = '?', lit = 'ÿ' ( 0), uid = 10 main.c:782: symbols[ 12] (0x5598b41d16e0): src = 1, use = true, sym = 0, get = 0, cpy = 0, len = 4, name = '?', lit = 'ÿ' ( 0), uid = 1100 main.c:782: symbols[ 13] (0x5598b41d170c): src = 4, use = true, sym = 0, get = 0, cpy = 0, len = 4, name = '?', lit = 'ÿ' ( 0), uid = 1101 main.c:782: symbols[ 14] (0x5598b41d1738): src = 16, use = true, sym = 0, get = 2, cpy = 3, len = 4, name = '?', lit = 'ÿ' ( 0), uid = 1110 main.c:782: symbols[ 15] (0x5598b41d1764): src = 17, use = true, sym = 0, get = 3, cpy = 3, len = 4, name = '?', lit = 'ÿ' ( 0), uid = 1111 main.c:808: Length Symbols, foresee = 260, longest = 4, have = 261, used = 16 main.c:808: symbols[ 0] (0x560a164e1a60): src = 97, use = true, sym = 0, get = 0, cpy = 1, len = 1, name = '?', lit = 'a' ( 97), uid = 0 main.c:808: symbols[ 2] (0x560a164e1ab8): src = 98, use = true, sym = 0, get = 0, cpy = 2, len = 2, name = '?', lit = 'b' ( 98), uid = 10 main.c:808: symbols[ 12] (0x560a164e1c70): src = 256, use = true, sym = 0, get = 0, cpy = 4, len = 4, name = '?', lit = 'ÿ' (256), uid = 1100 main.c:808: symbols[ 13] (0x560a164e1c9c): src = 257, use = true, sym = 3, get = 0, cpy = 0, len = 4, name = '?', lit = 'ÿ' (257), uid = 1101 main.c:808: symbols[ 14] (0x560a164e1cc8): src = 258, use = true, sym = 4, get = 0, cpy = 0, len = 4, name = '?', lit = 'ÿ' (258), uid = 1110 main.c:808: symbols[ 15] (0x560a164e1cf4): src = 259, use = true, sym = 5, get = 0, cpy = 0, len = 4, name = '?', lit = 'ÿ' (259), uid = 1111 main.c:809: Distance Symbols, foresee = 7, longest = 2, have = 8, used = 4 main.c:809: symbols[ 0] (0x560a164e4750): src = 0, use = true, sym = 0, get = 0, cpy = 0, len = 2, name = '?', lit = 'ÿ' (260), uid = 00 main.c:809: symbols[ 1] (0x560a164e477c): src = 4, use = true, sym = 0, get = 0, cpy = 0, len = 2, name = '?', lit = 'ÿ' (264), uid = 01 main.c:809: symbols[ 2] (0x560a164e47a8): src = 5, use = true, sym = 0, get = 0, cpy = 0, len = 2, name = '?', lit = 'ÿ' (265), uid = 10 main.c:809: symbols[ 3] (0x560a164e47d4): src = 6, use = true, sym = 0, get = 0, cpy = 0, len = 2, name = '?', lit = 'ÿ' (266), uid = 11

Just in case you didn't realise that's what those commented out PrintSymbols() calls produce when given the final tables, they iterate through the all the nodes up until it hits the used count and prints only those whose "use" boolean is equal to true, otherwise it only prints info about the table.

Edit: Ah, btw that "len" member is only used for generating the UIDs later (I deem UID less confusing than code when code is also used for the code table, confusing to say every code, leng & dist symbol has a code member, less confusing to say they all have a UID for huffman purposes).

The "get" member is for how many extra bits need to be read after the symbol's UID is found in the stream/buffer/file.

The "lit" member will always be of the original leng "alphabet" which is why it's used as the value to be put in the target buffer

Currently the "sym" member is being used for for how to look back

The "cpy" member is naturally supposed to hold the base number of characters to copy, the number obtained from using the "get" member to read more of the stream is added to this.

The "src" member is supposed to hold the non-huffman code mentioned in the tables of this document: Understanding gzip

I think that about covers the potentially confusing members

Quote:

Originally Posted by hamster_nz

I got a few spare minutes.

Attached is a program that should decode a .gz file less than 8kb, and if you add "-v" on the command line it will print out things like code tables/dictionaries along the way.

Code:

$ echo "Hi there" | gzip > a.gz $ ./main2 a.gz Have loaded 29 bytes from file Last block = true Compressed (default dictionary) data: 48 'H' data: 69 'i' data: 20 ' ' data: 74 't' data: 68 'h' data: 65 'e' data: 72 'r' data: 65 'e' data: 0a End of block 256 This is the last block

It assumes that the zlib data start at byte 10.

Don't judge the code too harshly - it's just a hack to test my understanding, not production ready.

So here I'm gziping up the source file "inflate.c", then decoding it with 'verbose' enabled:

Code:

$ cat inflate.c | gzip > abc.gz $ ./main2 -v abc.gz | more

And here is the output showing the code tables that were used:

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 ......

TBH I find that output to be unclear about what the values represent, part of the reason I print the member names is so I can more easily see what should've been what compared to what it actually is. Did look through you're code but didn't find what I was looking for so at present it wasn't of help to me, thx anyways

Finally got that blasted algorithm right, for anyone wanting to reference my code (which I've already cleaned up a bit prior to getting the algorithm right) here's where it's uploaded:
Gitlab upload instance

Just don't expect it to be super clean, I literally only just got it right just now, I'll do a cleaner version for my paw project later.

We want, ney demand, a 'leasons learned' briefing! :)

What was the thing(s) you figured out, discovered or uncovered that allowed you to get the algorithm working?

Some vagueness or ambiguity in the spec? Some bit/byte ordering issues in the code?

What are the things that might trip up the next person who attempts this and finds themselves reading through this thread?

It was those hard coded values, they had indistinct naming (even in the docs) which got me confused, after I moved the related stuff to their own files and renamed them to match the files (I had an #if 1 statement for the implied code data at one point) I was able to see & compare to the tables provided here:

Understanding gzip

With that I was able to experiment until I got it right. Still think the design of the encoding leaves much to be desired :|

The bit of RFC 1951 that I came unstuck on for a while was this:

Code:

0 - 15: Represent code lengths of 0 - 15 16: Copy the previous code length 3 - 6 times. The next 2 bits indicate repeat length (0 = 3, ... , 3 = 6) Example: Codes 8, 16 (+2 bits 11), 16 (+2 bits 10) will expand to 12 code lengths of 8 (1 + 6 + 5) 17: Repeat a code length of 0 for 3 - 10 times. (3 bits of length) 18: Repeat a code length of 0 for 11 - 138 times (7 bits of length)

The meaning of codes 17 and 18 just escaped me for hours. Now I understand what it is trying to say I can understand it perfectly. :D

Oh, and a lot of the jargon used is from coding/communication theory, and has a subtly different meaning than the same jargon used in the wider programming domain.

It's not so much the jargon that was the problem for me but just understanding where to put the implied data and how to use it, that problem is now over and I will always have my upload for reference... provided gitlab has appropriately prepared for that predicted solar flair or something that supposed to happen in 2025 I thnk... or was it 2023? Either way it's supposed to effect every electronic device in the world so I'm considering just doing a mass print of my code as a fallback

For anyone that was looking through my deflation code I've done a cleanup up, the main loop is now easier to understand and the deflation types are properly separated into functions (made it convenient to use the type as an index to a function instead of if statements)

Gitlab - Awsdert - Deflate

Right, this is potentially the final edit to the localised version of the zlib code, before I try to plug it into my PNG code I'd like anyone interested to have a glance through the code looking for any problems or potential problems they see (besides somewhat messy code)

GitLab - Awsdert - Deflate

I made it so the allocator can be defined by the developer, same with output files or streams (like stdout or stderr)

By the lack of responses I can see that either no-one was interested or they didn't find any problems, I'm betting the former, oh well I just deal with them as they crop up during the port process, I'll leave the code up there for others to reference though, even if the code is messy it at least makes it easier to understand the flow of analysis for the zlib format.

Quote:

Originally Posted by awsdert

By the lack of responses I can see that either no-one was interested or they didn't find any problems, I'm betting the former, oh well I just deal with them as they crop up during the port process, I'll leave the code up there for others to reference though, even if the code is messy it at least makes it easier to understand the flow of analysis for the zlib format.

Perhaps some of us do not have accounts with GitLab, and prefer NOT to create yet another account we don't need or want! If you want people to download your code, then make it publicly, and freely accessible.

Quote:

Originally Posted by rstanley

Perhaps some of us do not have accounts with GitLab, and prefer NOT to create yet another account we don't need or want! If you want people to download your code, then make it publicly, and freely accessible.

It is though, you download the same way you download with github, just instead of the domain being github.com it gitlab.com, literally no difference in download method

Edit: Didn't realise gitlab defaulted to private access, changing it now

Are you sure that this is correct?

Code:

int ExpandZlibArchiveType0( ZLIB *zlib ) { STREAM *Stream = zlib->Stream; BUFFER *Into = GrabBuffer( zlib->Buffers, zlib->Into ); uchar *into = Into->addr; uint leng = StreamBits( Stream, 16, true ); FlipBits( &leng, 16 ); Stream->have = Stream->used + (leng * 8); while ( Stream->used < Stream->have ) into[Into->used++] = (uchar)StreamBits( Stream, 8, true ); return 0; }

It might pay to run some test data though it and verify... here's the section of the RFC:

Code:

3.2.4. Non-compressed blocks (BTYPE=00) Any bits of input up to the next byte boundary are ignored. The rest of the block consists of the following information: 0 1 2 3 4... +---+---+---+---+================================+ | LEN | NLEN |... LEN bytes of literal data...| +---+---+---+---+================================+ LEN is the number of data bytes in the block. NLEN is the one's complement of LEN.

Is this supposed to happen?

Code:

$ gzip < main.c > a.gz $ ./a.out -f a.gz Segmentation fault

Quote:

Originally Posted by hamster_nz

Is this supposed to happen?

Code:

$ gzip < main.c > a.gz $ ./a.out -f a.gz Segmentation fault

No it's not, I'll check it out later but for now I'm working on integrating my zlib code into my png code, weird though, I was sure it was working correctly as I tested on the examples given in the reference document I gave in a prior post (I've close th tab now so can't copy the url like I did before), anyways took me all day to fix all the compile time bugs during the integration so gonna take a break tonight, there's a segfault now but again I will leave that for 2mw, if anyone feels like looking through the png code to find potential causes for the segfault then here's the link:

Files * 5cfb24d92752ca48e7ef3bd3ec93bbd603d3ef26 * Lee Shallis / glEngine * GitLab

Not expecting anyone to do so but I'm not psychic, I could be wrong with my assumption, bonus if there is, no skin off of my nose if there isn't.

Quote:

Originally Posted by hamster_nz

Are you sure that this is correct?

Code:

int ExpandZlibArchiveType0( ZLIB *zlib ) { STREAM *Stream = zlib->Stream; BUFFER *Into = GrabBuffer( zlib->Buffers, zlib->Into ); uchar *into = Into->addr; uint leng = StreamBits( Stream, 16, true ); FlipBits( &leng, 16 ); Stream->have = Stream->used + (leng * 8); while ( Stream->used < Stream->have ) into[Into->used++] = (uchar)StreamBits( Stream, 8, true ); return 0; }

It might pay to run some test data though it and verify... here's the section of the RFC:

Code:

3.2.4. Non-compressed blocks (BTYPE=00) Any bits of input up to the next byte boundary are ignored. The rest of the block consists of the following information: 0 1 2 3 4... +---+---+---+---+================================+ | LEN | NLEN |... LEN bytes of literal data...| +---+---+---+---+================================+ LEN is the number of data bytes in the block. NLEN is the one's complement of LEN.

You were right I had implement that wrong, should be fixed now, just struggling to understand why type 1 deflation is not producing the expected string now, rather it comes out empty

Quote:

Originally Posted by awsdert

You were right I had implement that wrong, should be fixed now, just struggling to understand why type 1 deflation is not producing the expected string now, rather it comes out empty

Fixed the source of the bug, I haven't directly handled the "End Block" though so I think that is the last bug if any, for now though, back to PNG code

I tried this - output is wrong too:

[code]
$ echo "aaaaaabbbbbaaaaacccccdddddd" | gzip > a.gz

$ ./a.out --verbose -f a.gz
main.c:28: ArgHasIssue( '--verbose', '(null)' )
main.c:9: ArgHasIssue( '-f', 'a.gz' )
LoadGzipDetails( 0x7ffff68bc7e0, 28 )
Gzip Header: magic = 1F8B, format = 08, flags = 00000000, xflags = 00, system = 03
Flag States: TEXT = false, HCRC = false, MORE = false, NAME = false, NOTE = false, RESERVED = 0
Expected Size = 28
gzip.c:128: Stream Details: ptr = 0x7ffff68bc7e0, byte = 33, took = 264, used = 80, have = 232
Zlib Expansion Result:
aaaaaa

Quote:

Originally Posted by hamster_nz

I tried this - output is wrong too:

[code]
$ echo "aaaaaabbbbbaaaaacccccdddddd" | gzip > a.gz

$ ./a.out --verbose -f a.gz
main.c:28: ArgHasIssue( '--verbose', '(null)' )
main.c:9: ArgHasIssue( '-f', 'a.gz' )
LoadGzipDetails( 0x7ffff68bc7e0, 28 )
Gzip Header: magic = 1F8B, format = 08, flags = 00000000, xflags = 00, system = 03
Flag States: TEXT = false, HCRC = false, MORE = false, NAME = false, NOTE = false, RESERVED = 0
Expected Size = 28
gzip.c:128: Stream Details: ptr = 0x7ffff68bc7e0, byte = 33, took = 264, used = 80, have = 232
Zlib Expansion Result:
aaaaaa

Looked into it, turned out there was a left over break statement from when I split up the code from it's huge block in main() during early stages, that break was meant to be for code 256 only, went and moved it while I was implmenting support for the code again, I really hope thats the last issue in the deflation algorithm

This is the closest thread topic to my newest problem, I finally realised why I've been failing to extract the right raw image from png files, turns out I misunderstood the IDAT chunk, after correcting that I found that my bit stream function is faulty, it somehow works for "<= bitsof(uintmax_t) " (to be accurate I've only read upto 32 bits at a time so far) but as soon as it was need for a larger block it resulted in it the bits being ignored, here's the code for the stream functions 1st:

Code:

void StreamUsed( STREAM *Stream, uint bits ) { intmax_t max = BUFSIZ; max *= CHAR_MAX; Stream->took += bits; Stream->used += bits; if ( Stream->eod && Stream->took >= max ) Stream->err = EOF; } long StreamBlock( STREAM * Stream ) { void *src = Stream->feed; long add = -1; memset( src, 0, BUFSIZ ); if ( Stream->eod ) Stream->err = EOF; else { add = Stream->DataCB( src, Stream->data, Stream->byte, BUFSIZ ); Stream->eod = (add < BUFSIZ); } return add; } int StreamData( STREAM *Stream, void *dst, intmax_t get, bool use ) { BIT d, s; intmax_t const max = ((intmax_t)BUFSIZ) * CHAR_BIT; intmax_t num = max - Stream->took; void * src = Stream->feed; SetBit( &d, dst, 0 ); if ( Stream->byte < 1 ) { Stream->took = 0; num = StreamBlock( Stream ); if ( num < 0 ) return EOF; if ( !num ) return ENODATA; Stream->byte = num; num *= CHAR_BIT; } while ( d.abs < get ) { intmax_t take = get - d.abs, bits = Stream->took; while ( bits >= max ) { num = StreamBlock( Stream ); if ( num < 0 ) return EOF; if ( !num ) return ENODATA; Stream->byte += num; num *= CHAR_BIT; bits -= max; Stream->took = 0; EchoStreamDetails( stdout, Stream ); } SetBit( &s, src, Stream->took ); if ( num < take ) take = num; for ( bits = 0; bits < take; ++bits ) { if ( *(s.byte) & s.mask ) *((uchar*)(d.byte)) |= d.mask; IncBit( &d, dst ); IncBit( &s, src ); } if ( use ) StreamUsed( Stream, take ); else if ( get > num ) return ERANGE; } return 0; }

And here's what is being passed to it when I noticed it was ignoring the bits:

Code:

else if ( ansi_cmpi( Entry->Type, "IDAT" ) == 0 ) { uint cmf = StreamBits( Stream, 8, true ); uint mod = StreamBits( Stream, 8, true ); uint chk; idat = ExpandBuffer( IDAT, 1, IDAT->used + leng ); if ( !idat ) { fprintf( errout, "Not enough space to append IDAT data\n" ); return NULL; } leng -= 4; err = StreamData( &StreamFile, idat + IDAT->used, leng * 8, true ); chk = StreamBits( &StreamFile, 8, true ) << 8; chk |= StreamBits( &StreamFile, 8, true ); IDAT->used += leng; if ( verbose ) { EchoStreamDetails( verbose, &StreamFile ); ECHO ( verbose, fprintf ( verbose, "cmf = %02X, mod = %02X, chk = %04X, " "leng = %5" PRIuMAX ", IDAT->used = %7u\n", cmf, mod, chk, leng, IDAT->used ) ); EchoStreamDetails( verbose, &StreamFile ); } if ( err ) { ECHO( errors, ECHO_ERR( errors, err ) ); return NULL; } }

Local Output:

Code:

view/png.c:309: 2 'IDAT' 111 Stream Details: End Of Data = true, End Of Stream = false, data = 0x7ffc4e9fd188, byte = 184, took = 1328, used = 1328 view/png.c:356: cmf = 00, mod = 00, chk = 5220, leng = 107, IDAT->used = 107 Stream Details: End Of Data = true, End Of Stream = false, data = 0x7ffc4e9fd188, byte = 184, took = 1328, used = 1328

That 1st line in the output represents chunk number, chunk type and the leng variable you see mentioned in the code (leng of the chunk), anyone have any ideas what's causing StreamData() to ignore the bits it's supposed to be putting in "idat"?

Edit: Never mind, failed to notice that I was only printing after the readout, moving the first printout to before the readout gave me the expected output for the details, didn't resolve my issue with IDAT somehow being read wrong though.

Edit 2: If anyone was planning to help me understand what's going wrong with the IDAT readout the current upload is here:
Files * d700e396122a99a8ab07a489accbb5596abd6c49 * Lee Shallis / glEngine * GitLab
Look for png.c then LoadImagePNG(), then just look for the if statement that compares the entry type to the string IDAT, that should be the highest code statement you need to look at, stream code is in stream.h/stream.c, BIT is defined in common.h (forgive the somewhat poorly organised code, my focus has been getting the images extracted right and learning opengl, cleaner versions will eventually be put in paw with minimal header dependencies)

I suggest you concentrate on getting your zlib deflate code to work flawlessly with lots of different gzip files before you stack things on top of it.

Code:

hamster@hamster-acer5:~/uc-evidence/deflate$ gzip < main.c > a.gz hamster@hamster-acer5:~/uc-evidence/deflate$ ./a.out -f a.gz zlib.c:812: last = 1, type = 10 zlib.c:326: Couldn't find symbol! Symbols List Details: foresee: 14, longest = 6, highest = 64 Error 0x00000016 (22) 'Invalid argument' main.c:197: Error 0xFFFFFFFF (-1) 'Unknown error -1'

It definately hasn't been tested enough.

I think I already fixed that one, probably didn't copy it over to the original code, was just a lack of support for allocating memory at that point I think, I'll go ahead and copy that over now before going to bed

Edit: Here's the upload with the later fixes included:

deflate * 821d8f1fcada79c0dd4bdbf65eefd16bbe8bdb34 * Lee Shallis / UC-Evidence * GitLab

Pulled those changes down, rebuilt and retried. Same result.

Code:

$ gzip < main.c > a.gz $ ./a.out -f a.gz zlib.c:820: last = 1, type = 10, Stream->used = 83 zlib.c:318: Couldn't find symbol! Symbols List Details: foresee: 14, longest = 6, highest = 64 Error 0x00000016 (22) 'Invalid argument' main.c:197: Error 0xFFFFFFFF (-1) 'Unknown error -1'

Quote:

Originally Posted by hamster_nz

Pulled those changes down, rebuilt and retried. Same result.

Code:

$ gzip < main.c > a.gz $ ./a.out -f a.gz zlib.c:820: last = 1, type = 10, Stream->used = 83 zlib.c:318: Couldn't find symbol! Symbols List Details: foresee: 14, longest = 6, highest = 64 Error 0x00000016 (22) 'Invalid argument' main.c:197: Error 0xFFFFFFFF (-1) 'Unknown error -1'

After adding some print statements to track the results of tables I found it's not the reading of the encoding thats the issue, its the point that I move each symbol to an index that matches it's uid (for speed during the deflation process):

Code:

typedef struct _ZLIB_SYMBOL { uint uid; uint src; uint val; uint sym; uint lit; uint len; uint get; uint cpy; uint use; uint nxt[2]; } ZLIB_SYMBOL; ... int CompareSymbols( void const *A, void const *B ) { ZLIB_SYMBOL const *a = A, *b = B; if ( a->use != b->use ) return b->use - a->use; if ( a->len != b->len ) return a->len - b->len; return a->uid - b->uid; } ... int SortZlibSymbolsByUID( ZLIB *zlib, int id ) { uint j = 0; ZLIB_SYMBOLS *Symbols = &(zlib->Symbols[id]); BUFFER *Entries = AccessBuffer( zlib->Buffers, Symbols->entries ); ZLIB_SYMBOL *symbols = Entries->addr, *dst, *src; FILE *verbose = zlib->Buffers->Alloc->verbose; if ( verbose && !quiet_zlib ) { ECHO ( verbose, fprintf( verbose, "Prior to qsort() " ); EchoZlibSymbolsListDetails( verbose, zlib, id ) ); } qsort( symbols, Entries->used, sizeof(ZLIB_SYMBOL), CompareSymbols ); if ( verbose && !quiet_zlib ) { ECHO ( verbose, fprintf( verbose, "Prior to manual " ); EchoZlibSymbolsListDetails( verbose, zlib, id ) ); } symbols = GrowZlibSymbolsBuffer( zlib, id, Symbols->highest + 1 ); if ( !symbols ) return ENOMEM; for ( j = Entries->used - 1; j; --j ) { src = symbols + j; dst = symbols + src->uid; if ( src->uid > j ) { *dst = *src; /* This is where I'm loosing data when I shouldn't be (in theory anyways) */ memset( src, 0, sizeof(ZLIB_SYMBOL) ); } } Entries->used = Symbols->highest + 1; return 0; }

I've added a comment to the point I can see is causing the error down the line, although in theory shouldn't be, any ideas on how to fix it? Or even better any ideas on how to fob off the duty to CompareSymbols()?

Welp, just tried this method instead:

Code:

for ( j = Entries->used - 1; j; --j ) { ZLIB_SYMBOL tmp; src = symbols + j; dst = symbols + src->uid; tmp = *src; memset( src, 0, sizeof(ZLIB_SYMBOL) ); *dst = tmp; }

Thought maybe forcing the data back in after clearing src might fix the issue, it did not.

After further investigation it turned out to be right before the manual sort, during the allocation, since the GrowZlibSymbolsBuffer() just defers to ExpandBuffer() I'll skip to that one instead:

Code:

void * ExpandBuffer( BUFFER *Buffer, int nsize, int nwant ) { ALLOC *Alloc = Buffer->Alloc; uchar *tmp = Buffer->addr; size_t get, had = Buffer->size; nwant = (nwant > 0) ? nwant : 0; get = nwant * nsize; if ( nsize < 1 ) return NULL; if ( get <= had ) return tmp; tmp = Alloc->alloc( Alloc->ud, tmp, had, get ); if ( !tmp ) return NULL; Buffer->addr = tmp; Buffer->size = get; Buffer->have = get / nsize; return tmp; } /* Just in case this is what Alloc->alloc points to atm */ void * default_allocator( void *ud, void *ptr, size_t had, size_t get ) { uchar *tmp; (void)ud; if ( !get ) { if ( ptr ) free( ptr ); return NULL; } tmp = ptr ? malloc( get ) : realloc( ptr, get ); if ( !tmp ) return NULL; if ( get > had ) memset( tmp + had, 0, get - had ); return tmp; }

Quote:

Originally Posted by awsdert

After adding some print statements to track the results of tables I found it's not the reading of the encoding thats the issue, its the point that I move each symbol to an index that matches it's uid (for speed during the deflation process):

Code:

typedef struct _ZLIB_SYMBOL { uint uid; uint src; uint val; uint sym; uint lit; uint len; uint get; uint cpy; uint use; uint nxt[2]; } ZLIB_SYMBOL; ... int CompareSymbols( void const *A, void const *B ) { ZLIB_SYMBOL const *a = A, *b = B; if ( a->use != b->use ) return b->use - a->use; if ( a->len != b->len ) return a->len - b->len; return a->uid - b->uid; } ... int SortZlibSymbolsByUID( ZLIB *zlib, int id ) { uint j = 0; ZLIB_SYMBOLS *Symbols = &(zlib->Symbols[id]); BUFFER *Entries = AccessBuffer( zlib->Buffers, Symbols->entries ); ZLIB_SYMBOL *symbols = Entries->addr, *dst, *src; FILE *verbose = zlib->Buffers->Alloc->verbose; if ( verbose && !quiet_zlib ) { ECHO ( verbose, fprintf( verbose, "Prior to qsort() " ); EchoZlibSymbolsListDetails( verbose, zlib, id ) ); } qsort( symbols, Entries->used, sizeof(ZLIB_SYMBOL), CompareSymbols ); if ( verbose && !quiet_zlib ) { ECHO ( verbose, fprintf( verbose, "Prior to manual " ); EchoZlibSymbolsListDetails( verbose, zlib, id ) ); } symbols = GrowZlibSymbolsBuffer( zlib, id, Symbols->highest + 1 ); if ( !symbols ) return ENOMEM; for ( j = Entries->used - 1; j; --j ) { src = symbols + j; dst = symbols + src->uid; if ( src->uid > j ) { *dst = *src; /* This is where I'm loosing data when I shouldn't be (in theory anyways) */ memset( src, 0, sizeof(ZLIB_SYMBOL) ); } } Entries->used = Symbols->highest + 1; return 0; }

I've added a comment to the point I can see is causing the error down the line, although in theory shouldn't be, any ideas on how to fix it? Or even better any ideas on how to fob off the duty to CompareSymbols()?

Your problem is in here, from "buffer.c".

Code:

#include "memory.h" void * default_allocator( void *ud, void *ptr, size_t had, size_t get ) { uchar *tmp; (void)ud; if ( !get ) { if ( ptr ) free( ptr ); return NULL; } tmp = ptr ? malloc( get ) : realloc( ptr, get ); if ( !tmp ) return NULL; if ( get > had ) memset( tmp + had, 0, get - had ); return tmp; } ...

Quote:

Originally Posted by hamster_nz

Your problem is in here, from "buffer.c".

Code:

#include "memory.h" void * default_allocator( void *ud, void *ptr, size_t had, size_t get ) { uchar *tmp; (void)ud; if ( !get ) { if ( ptr ) free( ptr ); return NULL; } tmp = ptr ? malloc( get ) : realloc( ptr, get ); if ( !tmp ) return NULL; if ( get > had ) memset( tmp + had, 0, get - had ); return tmp; } ...

I'm not seeing the cause, if you've already seen it then enlighten me please

It's in there. Clear as day.

Just read the code very carefully.

Quote:

Originally Posted by hamster_nz

It's in there. Clear as day.

Just read the code very carefully.

I assume you found it, and just didn't bother replying?

Quote:

Originally Posted by hamster_nz

I assume you found it, and just didn't bother replying?

Just didn't notice the message until just now, wasn't expecting a fast response since I figured you were probably doing something else and just checking occasionally like I do

Quote:

Originally Posted by hamster_nz

...

Code:

if ( get > had ) memset( tmp + had, 0, get - had );

...

are you thinking this is the cause, I don't see how as that only touches new memory, not old memory

Quote:

Originally Posted by awsdert

are you thinking this is the cause, I don't see how as that only touches new memory, not old memory

Explain to me what you think the line does:

Code:

tmp = ptr ? malloc( get ) : realloc( ptr, get );

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

Quote:

Originally Posted by awsdert

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

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.

Quote:

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; } } }