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.